Анализ сверху вниз - Top-down parsing

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

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

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

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

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

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

Например:

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

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

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

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

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

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

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

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

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

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

Примеры

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

• Грамматика с определенным предложением парсеры^[9]
• Парсер с рекурсивным спуском
• Предиктивный парсер
• Парсер Эрли

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

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

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

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

внешняя ссылка

• Икс-САЙГА - ВЫПОЛНЯЕМЫЕ ОСОБЕННОСТИ ГРАММАТИКИ