Анализ сверху вниз

Техника анализа

Нисходящий анализ в информатике — это стратегия анализа , при которой сначала рассматривается самый высокий уровень дерева анализа и выполняется спуск по дереву анализа с использованием правил переписывания формальной грамматики . ^[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 предоставляют элегантный и мощный алгоритм синтаксического анализа. См. Parsing expression grammar .

Примеры

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

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

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

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

Ссылки

1. Дик Грюн; Сериэль Дж. Х. Якобс (29 октября 2007 г.). Методы анализа: практическое руководство. Springer Science & Business Media. ISBN 978-0-387-68954-8.
2. Ахо, Альфред В .; Сети, Рави ; Ульман, Джеффри Д. (1986). Компиляторы, принципы, методы и инструменты (Переп. с исправлениями. ред.). Addison-Wesley Pub. Co. ISBN 978-0201100884.
3. Ахо, Альфред В.; Ульман , Джеффри Д. (1972). Теория синтаксического анализа, перевода и компиляции (Том 1: синтаксический анализ.) (Переиздание). Энглвуд Клиффс, Нью-Джерси: Prentice-Hall. ISBN 978-0139145568.
4. Frost, R., Hafiz, R. и Callaghan, P. (2007) " Modular and Efficient Top-Down Parsing for Ambiguous Left-Recursive Grammars " 10th International Workshop on Parsing Technologies (IWPT), ACL-SIGPARSE , Страницы: 109 - 120, июнь 2007, Прага. Архивировано из оригинала 12 ноября 2018.
5. Frost, R., Hafiz, R. и Callaghan, P. (2008) " Комбинаторы синтаксических анализаторов для неоднозначных леворекурсивных грамматик". 10-й Международный симпозиум по практическим аспектам декларативных языков (PADL), ACM-SIGPLAN , том 4902/2008, страницы: 167-181, январь 2008 г., Сан-Франциско.
6. Frost, R. и Hafiz, R. (2006) "Новый алгоритм нисходящего анализа для учета неоднозначности и левой рекурсии за полиномиальное время". ACM SIGPLAN Notices , том 41, выпуск 5, страницы: 46 - 54. doi :10.1145/1149982.1149988
7. Скотт, Элизабет; Джонстон, Адриан. «GLL Parsing» (PDF) . dotat.at . Лондонский университет .
8. Скотт, Элизабет; Джонстон, Адриан. «Структурирование алгоритма синтаксического анализа GLL для повышения производительности» (PDF) . dotat.at . Лондонский университет .
9. Норвиг, П. (1991) «Методы автоматического запоминания с применением к контекстно-свободному синтаксическому анализу». Журнал - Computational Linguistics Том 17, Выпуск 1, Страницы: 91 - 98.
10. Томита, М. (1985) «Эффективный синтаксический анализ естественного языка». Клувер, Бостон, Массачусетс .
11. Перейра, Фернандо КН и Дэвид HD Уоррен. «Грамматики с определенным предложением для анализа языка — обзор формализма и сравнение с расширенными сетями переходов». Искусственный интеллект 13.3 (1980): 231-278.

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

• X-SAIGA - Исполняемые спецификации грамматик