Синтаксический анализ сверху вниз

Техника разбора

Синтаксический анализ сверху вниз в информатике — это стратегия синтаксического анализа , при которой сначала рассматривается самый высокий уровень дерева синтаксического анализа , а затем обрабатывается дерево синтаксического анализа, используя правила переписывания формальной грамматики . ^[1] LL-парсеры — это тип парсера, использующий стратегию анализа сверху вниз.

Синтаксический анализ сверху вниз — это стратегия анализа неизвестных взаимосвязей данных путем выдвижения гипотезы об общих структурах дерева синтаксического анализа и последующего рассмотрения того, совместимы ли известные фундаментальные структуры с этой гипотезой. Это происходит при анализе как естественных языков, так и компьютерных языков .

Синтаксический анализ сверху вниз можно рассматривать как попытку найти крайние левые производные входного потока путем поиска деревьев синтаксического анализа с использованием нисходящего расширения заданных формальных грамматических правил. Инклюзивный выбор используется для устранения двусмысленности путем расширения всех альтернативных правых частей грамматических правил. ^[2]

Простые реализации нисходящего анализа не завершаются для леворекурсивных грамматик, а нисходящий анализ с обратным отслеживанием может иметь экспоненциальную временную сложность относительно длины входных данных для неоднозначных CFG . ^[3] Однако Фростом, Хафизом и Каллаганом были созданы более сложные нисходящие анализаторы, ^{[4] [5]} которые учитывают неоднозначность и левую рекурсию за полиномиальное время и которые генерируют представления потенциально экспоненциального числа полиномиального размера. деревьев разбора.

Приложение языка программирования

Компилятор анализирует входные данные языка программирования во внутреннее представление , сопоставляя входящие символы с производственными правилами . Продукционные правила обычно определяются с использованием формы Бэкуса-Наура . Парсер LL — это тип синтаксического анализатора, который выполняет синтаксический анализ сверху вниз, применяя каждое производственное правило к входящим символам, работая от крайнего левого символа, полученного по производственному правилу, а затем переходя к следующему производственному правилу для каждого нетерминального символа. столкнулся. Таким образом, синтаксический анализ начинается слева от стороны результата (правой стороны) производственного правила и сначала оценивает нетерминалы слева и, таким образом, продолжается вниз по дереву синтаксического анализа для каждого нового нетерминала, прежде чем перейти к следующему. символ производственного правила.

Например:

• ${\displaystyle A\rightarrow aBC}$
• ${\displaystyle B\rightarrow c\mid cd}$
• ${\displaystyle C\rightarrow df\mid eg}$

который создает строку A = acdf

будет соответствовать и попытается сопоставить следующий. Тогда бы судили. Как и следовало ожидать, некоторые языки более неоднозначны, чем другие. Для однозначного языка, в котором все продукты для нетерминала создают разные строки, строка, созданная одним продуктом, не будет начинаться с того же символа, что и строка, созданная другим продуктом. Однозначный язык может быть проанализирован с помощью грамматики LL(1), где (1) означает, что анализатор считывает по одному токену за раз. Чтобы неоднозначный язык мог быть проанализирован анализатором LL, анализатор должен просмотреть более 1 символа вперед, например LL(3). ${\displaystyle A\rightarrow aBC}$ ${\displaystyle B\rightarrow c\mid cd}$ ${\displaystyle C\rightarrow df\mid eg}$

Обычным решением этой проблемы является использование LR-парсера , который представляет собой разновидность парсера со сдвигом-сокращением и выполняет синтаксический анализ снизу вверх .

Учет левой рекурсии при синтаксическом анализе сверху вниз

Формальная грамматика , содержащая левую рекурсию, не может быть проанализирована с помощью наивного анализатора рекурсивного спуска , если она не преобразована в слабо эквивалентную праворекурсивную форму. Однако недавние исследования показывают, что леворекурсивные грамматики (наряду со всеми другими формами общих CFG ) можно разместить в более сложном нисходящем анализаторе с помощью сокращения. Алгоритм распознавания , который учитывает неоднозначные грамматики и сокращает постоянно растущий объем прямого леворекурсивного анализа путем наложения ограничений на глубину в отношении длины ввода и текущей позиции ввода, описан Фростом и Хафизом в 2006 году. ^[6] Этот алгоритм был расширен до полный алгоритм синтаксического анализа для реализации косвенной (путем сравнения ранее вычисленного контекста с текущим контекстом), а также прямой левой рекурсии за полиномиальное время, а также для генерации компактных представлений полиномиального размера потенциально экспоненциального числа деревьев синтаксического анализа для весьма неоднозначных грамматик Фроста, Хафиз и Каллаган в 2007 году. ^[4] С тех пор алгоритм был реализован в виде набора комбинаторов синтаксического анализатора , написанных на языке программирования Haskell . Детали реализации этого нового набора комбинаторов можно найти в статье авторов ^[5] , представленной на PADL'08. На сайте X-SAIGA можно найти дополнительную информацию об алгоритмах и деталях реализации.

Кроме того, можно использовать стек со структурой графа (GSS) в дополнение к вышеупомянутому сокращению, чтобы обеспечить левую рекурсию путем «объединения» стеков с общими префиксами и предотвращения бесконечной рекурсии, тем самым уменьшая количество и содержимое каждого стека, тем самым уменьшение временной и пространственной сложности синтаксического анализатора. Это приводит к алгоритму, известному как обобщенный анализ LL, в котором вы используете GSS, сокращение левой рекурсии и анализатор LL(k) для анализа входных строк относительно заданного CFG. ^{[7] [8]}

Временная и пространственная сложность синтаксического анализа сверху вниз

Когда нисходящий синтаксический анализатор пытается проанализировать неоднозначные входные данные относительно неоднозначной конфигурации CFG, ему может потребоваться экспоненциальное количество шагов (относительно длины входных данных), чтобы опробовать все альтернативы CFG и создать все возможные деревья синтаксического анализа. , что в конечном итоге потребует экспоненциального объема памяти. Проблема экспоненциальной временной сложности в нисходящих анализаторах, построенных как наборы взаимно рекурсивных функций, была решена Норвигом в 1991 году. ^[9] Его метод аналогичен использованию динамического программирования и наборов состояний в алгоритме Эрли (1970): и таблицы в алгоритме CYK Кока, Янгера и Касами.

Основная идея состоит в том, чтобы сохранить результаты применения парсера pв jзапоминающемся месте и повторно использовать результаты всякий раз, когда возникает одна и та же ситуация. Фрост, Хафиз и Каллаган ^{[4] [5]} также используют мемоизацию для отказа от избыточных вычислений, чтобы приспособить любую форму CFG за полиномиальное время ( Θ (n ⁴ ) для леворекурсивных грамматик и Θ (n ³ ) для нелеворекурсивных грамматик ). Их алгоритм нисходящего анализа также требует полиномиального пространства для потенциально экспоненциальных неоднозначных деревьев анализа посредством «компактного представления» и «группировки локальных неоднозначностей». Их компактное представление сравнимо с компактным представлением восходящего синтаксического анализа Томиты . ^[10]

Используя PEG, еще одно представление грамматик, парсеры Packrat предоставляют элегантный и мощный алгоритм синтаксического анализа. См. раздел «Разбор грамматики выражений» .

Примеры

Некоторые из парсеров, использующих нисходящий анализ, включают:

• Анализаторы грамматики определенных предложений ^[11]
• Парсер рекурсивного спуска
• Прогнозирующий парсер
• Парсер Эрли

Смотрите также

• Анализ снизу вверх
• Разбор
• Разбор грамматики выражений

Рекомендации

1. Дик Грюн; Сериэль Дж. Джейкобс (29 октября 2007 г.). Методы синтаксического анализа: Практическое руководство. Springer Science & Business Media. ISBN 978-0-387-68954-8.
2. Ахо, Альфред В .; Сетхи, Рави ; Уллман, Джеффри Д. (1986). Составители, принципы, приемы и инструменты (Отв. с исправлениями. Под ред.). Паб Аддисон-Уэсли. ISBN компании 978-0201100884.
3. Ахо, Альфред В .; Уллман, Джеффри Д. (1972). Теория синтаксического анализа, трансляции и компиляции (Том 1: Синтаксический анализ) (Переиздание). Энглвуд Клиффс, Нью-Джерси: Прентис-Холл. ISBN 978-0139145568.
4. Фрост Р., Хафиз Р. и Каллаган П. (2007) «Модульный и эффективный нисходящий анализ неоднозначных леворекурсивных грамматик». 10-й международный семинар по технологиям синтаксического анализа (IWPT), ACL-SIGPARSE , страницы: 109–120, июнь 2007 г., Прага. Архивировано из оригинала 12 ноября 2018 года.
5. Фрост Р., Хафиз Р. и Каллаган П. (2008) «Комбинаторы парсеров для неоднозначных леворекурсивных грамматик». 10-й Международный симпозиум по практическим аспектам декларативных языков (PADL), ACM-SIGPLAN , том 4902/2008, страницы: 167-181, январь 2008 г., Сан-Франциско.
6. Фрост Р. и Хафиз Р. (2006) «Новый алгоритм нисходящего анализа для учета неоднозначности и левой рекурсии за полиномиальное время». Уведомления ACM SIGPLAN , том 41, выпуск 5, страницы: 46–54. doi : 10.1145/1149982.1149988
7. http://dotat.at/tmp/gll.pdf ^{[ пустой URL-адрес PDF ]}
8. https://pure.royalholloway.ac.uk/portal/files/26408385/postprint.pdf ^{[ пустой URL-адрес PDF ]}
9. Норвиг, П. (1991) «Методы автоматического запоминания с приложениями для контекстно-свободного анализа». Журнал - Компьютерная лингвистика, том 17, выпуск 1, страницы: 91–98.
10. Томита, М. (1985) «Эффективный анализ естественного языка». Клювер, Бостон, Массачусетс .
11. Перейра, Фернандо CN и Дэвид HD Уоррен. «Грамматики определенных предложений для языкового анализа - обзор формализма и сравнение с расширенными сетями переходов». Искусственный интеллект 13.3 (1980): 231-278.

Внешние ссылки

• X-SAIGA – ИСПОЛНИТЕЛЬНЫЕ СПЕЦИФИКАЦИИ ГРАММАТИК