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

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

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

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

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

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

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

Например:

$A\rightarrow aBC$
$B\rightarrow c\mid cd$
$C\rightarrow df\mid eg$

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

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

Обычным решением этой проблемы является использование 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 ]}
Парсер рекурсивного спуска
Прогнозирующий парсер
Парсер Эрли

См. также

Ссылки

^ Дик Грюн; Сериэль Дж. Х. Джейкобс (29 октября 2007 г.). Техники синтаксического анализа: Практическое руководство . Springer Science & Business Media. ISBN 978-0-387-68954-8 .
^ Ахо, Альфред В .; Сетхи, Рави ; Уллман, Джеффри Д. (1986). Составители, принципы, приемы и инструменты (Отв. с исправлениями. Под ред.). Паб Аддисон-Уэсли. компании ISBN 978-0201100884 .
^ Ахо, Альфред В .; Уллман, Джеффри Д. (1972). Теория синтаксического анализа, перевода и компиляции (Том 1: Синтаксический анализ) (Переиздание). Энглвуд Клиффс, Нью-Джерси: Прентис-Холл. ISBN 978-0139145568 .
^ Jump up to: ^а ^б ^с Фрост Р., Хафиз Р. и Каллаган П. (2007) « Модульный и эффективный нисходящий анализ неоднозначных леворекурсивных грамматик ». 10-й международный семинар по технологиям синтаксического анализа (IWPT), ACL-SIGPARSE , страницы: 109–120, июнь 2007 г., Прага. Архивировано из оригинала 12 ноября 2018 года.
^ Jump up to: ^а ^б ^с Фрост Р., Хафиз Р. и Каллаган П. (2008) « Комбинаторы анализаторов неоднозначных леворекурсивных грамматик ». 10-й Международный симпозиум по практическим аспектам декларативных языков (PADL), ACM-SIGPLAN , том 4902/2008, страницы: 167-181, январь 2008 г., Сан-Франциско.
^ Фрост, Р. и Хафиз, Р. (2006) « Новый алгоритм нисходящего анализа для учета неоднозначности и левой рекурсии за полиномиальное время ». Уведомления ACM SIGPLAN , том 41, выпуск 5, страницы: 46–54. дои : 10.1145/1149982.1149988
^ Скотт, Элизабет; Джонстон, Адриан. «Разбор GLL» (PDF) . dotat.at . Лондонский университет .
^ Скотт, Элизабет; Джонстон, Адриан. «Структурирование алгоритма анализа GLL для повышения производительности» (PDF) . dotat.at . Лондонский университет .
^ Норвиг, П. (1991) « Методы автоматического запоминания с приложениями для контекстно-свободного анализа ». Журнал - Компьютерная лингвистика, том 17, выпуск 1, страницы: 91–98.
^ Томита, М. (1985) « Эффективный анализ естественного языка ». Клювер, Бостон, Массачусетс .
^ Перейра, Фернандо CN и Дэвид HD Уоррен. « Грамматики определенных предложений для языкового анализа — обзор формализма и сравнение с расширенными сетями переходов ». Искусственный интеллект 13.3 (1980): 231-278.

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

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

[GruneJacobs2007-1] Дик Грюн; Сериэль Дж. Х. Джейкобс (29 октября 2007 г.). Техники синтаксического анализа: Практическое руководство . Springer Science & Business Media. ISBN 978-0-387-68954-8 .

[AhoSethiUllman_1986-2] Ахо, Альфред В .; Сетхи, Рави ; Уллман, Джеффри Д. (1986). Составители, принципы, приемы и инструменты (Отв. с исправлениями. Под ред.). Паб Аддисон-Уэсли. компании ISBN 978-0201100884 .

[AhoUllman_1972-3] Ахо, Альфред В .; Уллман, Джеффри Д. (1972). Теория синтаксического анализа, перевода и компиляции (Том 1: Синтаксический анализ) (Переиздание). Энглвуд Клиффс, Нью-Джерси: Прентис-Холл. ISBN 978-0139145568 .

[FrostHafizCallaghan_2007-4] Jump up to: ^а ^б ^с Фрост Р., Хафиз Р. и Каллаган П. (2007) « Модульный и эффективный нисходящий анализ неоднозначных леворекурсивных грамматик ». 10-й международный семинар по технологиям синтаксического анализа (IWPT), ACL-SIGPARSE , страницы: 109–120, июнь 2007 г., Прага. Архивировано из оригинала 12 ноября 2018 года.

[FrostHafizCallaghan_2008-5] Jump up to: ^а ^б ^с Фрост Р., Хафиз Р. и Каллаган П. (2008) « Комбинаторы анализаторов неоднозначных леворекурсивных грамматик ». 10-й Международный симпозиум по практическим аспектам декларативных языков (PADL), ACM-SIGPLAN , том 4902/2008, страницы: 167-181, январь 2008 г., Сан-Франциско.

[FrostHafiz2006-6] Фрост, Р. и Хафиз, Р. (2006) « Новый алгоритм нисходящего анализа для учета неоднозначности и левой рекурсии за полиномиальное время ». Уведомления ACM SIGPLAN , том 41, выпуск 5, страницы: 46–54. дои : 10.1145/1149982.1149988

[7] Скотт, Элизабет; Джонстон, Адриан. «Разбор GLL» (PDF) . dotat.at . Лондонский университет .

[8] Скотт, Элизабет; Джонстон, Адриан. «Структурирование алгоритма анализа GLL для повышения производительности» (PDF) . dotat.at . Лондонский университет .

[Norvig_1991-9] Норвиг, П. (1991) « Методы автоматического запоминания с приложениями для контекстно-свободного анализа ». Журнал - Компьютерная лингвистика, том 17, выпуск 1, страницы: 91–98.

[Tomita1985-10] Томита, М. (1985) « Эффективный анализ естественного языка ». Клювер, Бостон, Массачусетс .

[11] Перейра, Фернандо CN и Дэвид HD Уоррен. « Грамматики определенных предложений для языкового анализа — обзор формализма и сравнение с расширенными сетями переходов ». Искусственный интеллект 13.3 (1980): 231-278.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

v т и Алгоритмы разбора
Сверху вниз	Эрли LL Рекурсивный спуск Хвостовая рекурсия
Вверх дном	Приоритет Простой Оператор Маневровый двор ЛР Простой смотреть вперед Канонический Обобщенный ГАЛОЧКА Рекурсивное восхождение Shift-уменьшить
Смешанное, другое	Комбинатор Диаграмма Левый угол Статистический
Связанные темы	ПЭГ Определенная грамматика предложения Детерминированный анализ Динамическое программирование Мемоизация Генератор парсера ЛАЛР Дерево разбора АСТ Бессканерный парсинг История создания компилятора Сравнение генераторов парсеров Грамматика приоритета операторов