Из Википедии, бесплатной энциклопедии
  (Перенаправлено с парсера сверху вниз )
Перейти к навигации Перейти к поиску

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

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

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

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

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

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

Например:

его строка будет A = acdf

будет соответствовать и попытается найти следующее. Тогда бы попробовали. Как и следовало ожидать, некоторые языки более неоднозначны, чем другие. Для однозначного языка, в котором все продукты для нетерминального порождают отдельные строки: строка, созданная одним продуктом, не начинается с того же символа, что и строка, созданная другим продуктом. Однозначный язык может быть проанализирован грамматикой LL (1), где (1) означает, что синтаксический анализатор читает вперед по одному токену за раз. Для синтаксического анализа неоднозначного языка парсером LL он должен смотреть вперед более чем на 1 символ, например LL (3).

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

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

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

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

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

Ключевая идея состоит в том, чтобы сохранять результаты применения синтаксического анализатора pв позиции jв memotable и повторно использовать результаты всякий раз, когда возникает такая же ситуация. Frost, Hafiz и Callaghan [4] [5] также используют мемоизацию для отказа от избыточных вычислений, чтобы приспособить любую форму CFG за полиномиальное время ( Θ (n 4 ) для леворекурсивных грамматик и Θ (n 3 ) для не леворекурсивных грамматик. ). Их алгоритм нисходящего синтаксического анализа также требует полиномиального пространства для потенциально экспоненциальных неоднозначных деревьев синтаксического анализа с помощью «компактного представления» и «группировки локальных неоднозначностей». Их компактное представление сравнимо с TomitaКомпактное представление восходящего синтаксического анализа . [8]

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

Примеры [ править ]

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

  • Синтаксические анализаторы грамматики с определенными предложениями [9]
  • Парсер с рекурсивным спуском
  • Предиктивный синтаксический анализатор
  • Парсер Эрли

См. Также [ править ]

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

Ссылки [ править ]

  1. ^ Дик Грюн; Кериэль Дж. Х. Джейкобс (29 октября 2007 г.). Методы синтаксического анализа: Практическое руководство . Springer Science & Business Media. ISBN 978-0-387-68954-8.
  2. ^ Ахо, Альфред В .; Сетхи, Рави ; Ульман, Джеффри Д. (1986). Компиляторы, принципы, методы и инструменты (Отв. С исправ. Ред.). Аддисон-Уэсли Паб. Co. ISBN 978-0201100884. CS1 maint: обескураженный параметр ( ссылка )
  3. ^ Ахо, Альфред В .; Ульман, Джеффри Д. (1972). Теория синтаксического анализа, перевода и компиляции (том 1: синтаксический анализ) (Repr. Ed.). Энглвуд Клиффс, Нью-Джерси: Прентис-Холл. ISBN 978-0139145568. CS1 maint: обескураженный параметр ( ссылка )
  4. ^ a b c Фрост Р., Хафиз Р. и Каллаган П. (2007) « Модульный и эффективный анализ сверху вниз для неоднозначных леворекурсивных грамматик ». 10-й Международный семинар по технологиям синтаксического анализа (IWPT), ACL-SIGPARSE , страницы: 109–120 , июнь 2007 г., Прага.
  5. ^ a b c Фрост, Р., Хафиз, Р. и Каллаган, П. (2008) « Комбинаторы синтаксического анализа для неоднозначных леворекурсивных грамматик ». 10-й Международный симпозиум по практическим аспектам декларативных языков (PADL), ACM-SIGPLAN , том 4902/2008, страницы: 167-181, январь 2008 г., Сан-Франциско.
  6. ↑ Frost, R. и Hafiz, R. (2006) « Новый алгоритм нисходящего синтаксического анализа для устранения неоднозначности и левой рекурсии за полиномиальное время ». Уведомления ACM SIGPLAN , том 41, выпуск 5, страницы: 46 - 54.
  7. ^ Норвиг, П. (1991) « Методы автоматической запоминания с приложениями для контекстно-свободного синтаксического анализа ». Журнал - Компьютерная лингвистика Том 17, Выпуск 1, Страницы: 91 - 98.
  8. ↑ Tomita, M. (1985) « Эффективный синтаксический анализ естественного языка ». Клувер, Бостон, Массачусетс .
  9. ^ Перейра, Фернандо CN и Дэвид HD Уоррен. « Грамматики с определенными предложениями для анализа языка - обзор формализма и сравнение с расширенными сетями переходов ». Искусственный интеллект 13.3 (1980): 231-278.

Внешние ссылки [ править ]

  • X-SAIGA - ВЫПОЛНЯЕМЫЕ ХАРАКТЕРИСТИКИ ГРАММАТИКИ