Какие грамматики можно анализировать с помощью рекурсивного спуска без возврата?

TL;DR

Для подходящего определения того, что это за парсер рекурсивного спуска, абсолютно правильно, что только LL (k) языки могут быть проанализированы рекурсивным спуском.

Lua можно проанализировать с помощью синтаксического анализатора рекурсивного спуска именно потому, что язык - это LL (k); то есть для Lua существует грамматика LL (k). [Примечание 1]

1. Язык LL (k) может иметь грамматики, отличные от LL (k).

Язык называется LL (k), если существует грамматика LL (k), которая распознает язык. Это не означает, что каждая грамматика, распознающая язык, является LL (k); может быть любое количество грамматик не-LL (k), распознающих язык. Таким образом, тот факт, что некоторая грамматика не является LL (k), абсолютно ничего не говорит о самом языке.

2. Многие практические языки программирования описываются неоднозначной грамматикой.

В формальной теории языка язык неоднозначен по своей сути, только если Каждая грамматика языка неоднозначна. Вероятно, можно с уверенностью сказать, что ни один практический язык программирования не является неоднозначным по своей сути, поскольку практические языки программирования детерминированно анализируются (каким-то образом). [Заметка 2].

Поскольку написание строго однозначной грамматики может быть утомительным, в документации по языку довольно часто встречается неоднозначная грамматика вместе с текстовым материалом, который указывает, как должны быть разрешены неоднозначности.

Например, многие языки (включая Lua) задокументированы с помощью грамматики, которая явно не включает приоритет операторов, что позволяет использовать простое правило для выражений:

exp ::= exp Binop exp | Unop exp | term

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

Другой распространенный пример неоднозначных справочных грамматик, которые можно устранить механически, - это двусмысленность "dangling else", обнаруженная в такие языки, как C (но не в Lua). Грамматика:

if-statement ::= "if" '(' exp ')' stmt
               | "if" '(' exp ')' stmt "else" stmt

конечно неоднозначно; намерение состоит в том, чтобы синтаксический анализ был «жадным». Опять же, двусмысленность не присуща. Существует механическое преобразование, которое дает однозначную грамматику, примерно такую:

matched-statement ::= matched-if-stmt | other-statement
statement         ::= matched-if-stmt | unmatched-if-stmt
matched-if-stmt   ::= "if" '(' exp ')' matched-statement "else" matched-statement 
unmatched-if-stmt ::= "if" '(' exp ')' statement
                    | "if" '(' exp ')' matched-statement "else" unmatched-if-stmt

Генераторы парсеров часто неявно выполняют это преобразование. (Для генератора синтаксического анализатора LR преобразование фактически реализуется путем удаления действий сокращения, если они конфликтуют с действием сдвига. Это проще, чем преобразование грамматики, но имеет точно такой же эффект.)

Итак, Lua (и другие языки программирования) не по своей сути неоднозначны; и поэтому они могут быть проанализированы с помощью алгоритмов синтаксического анализа, которые требуют однозначных детерминированных синтаксических анализаторов. В самом деле, может быть даже немного удивительно, что существуют языки, для которых все возможные грамматики неоднозначны. Как указано в цитированной выше статье Википедии, существование таких языков было доказано Рохитом Парихом в 1961 году; простой пример неоднозначного по своей сути контекстно-свободного языка:

{anbmcmdn|n,m≥0} ∪ {anbncmdm|n,m≥0}.

3. Жадный LL (1) парсинг Lua-операторов присваивания и вызова функций.

Как и в случае с конструкцией dangling else, описанной выше, устранение неоднозначности последовательностей операторов Lua выполняется только путем разрешения жадного синтаксического анализа. Интуитивно процедура проста; он основан на запрете двух последовательных операторов (без точки с запятой), где второй начинается с токена, который может продолжить первый.

На практике в этом преобразовании нет необходимости; это может быть сделано неявно во время построения парсера. Так что я не собираюсь создавать здесь полную грамматику Lua. Но я верю, что небольшого подмножества грамматики Lua здесь достаточно, чтобы проиллюстрировать, как может работать преобразование.

Следующее подмножество (в значительной степени основанное на справочной грамматике) демонстрирует в точности двусмысленность, указанную в OP:

program        ::= statement-list
statement-list ::= Ø
                 | statement-list statement
statement      ::= assignment | function-call | block | ';'
block          ::= "do" statement-list "end"
assignment     ::= var '=' exp
exp            ::= prefixexp                          [Note 3]
prefixexp      ::= var | '(' exp ')' | function-call
var            ::= Name | prefixexp '[' exp ']'
function-call  ::= prefixexp '(' exp ')'

(Примечание: (Я использую Ø для представления пустой строки, а не ε, λ или %empty.)

Грамматика Lua as является леворекурсивной, поэтому она явно не является LL (k) (независимо от неоднозначности). Удаление левой рекурсии может быть выполнено механически; Я сделал достаточно этого здесь, чтобы продемонстрировать, что это подмножество LL (1). К сожалению, преобразованная грамматика не сохраняет структуру дерева синтаксического анализа, что является классической проблемой грамматик LL (k). Обычно восстановить правильное дерево синтаксического анализа во время синтаксического анализа с рекурсивным спуском несложно, и я не буду вдаваться в подробности.

Предоставить LL (1) версию exp просто, но результат устраняет различие между var (который может быть назначен) и function-call (который не может):

exp          ::= term exp-postfix
exp-postfix  ::= Ø
               | '[' exp ']' exp-postfix
               | '(' exp ')' exp-postfix 
term         ::= Name | '(' exp ')' 

Но теперь нам нужно воссоздать различие, чтобы иметь возможность анализировать как операторы присваивания, так и вызовы функций. Это прямолинейно (но не способствует пониманию синтаксиса, ИМХО):

a-or-fc-statement ::= term a-postfix
a-postfix         ::= '=' exp 
                    | ac-postfix
c-postfix         ::= Ø
                    | ac-postfix
ac-postfix        ::= '(' exp ')' c-postfix
                    | '[' exp ']' a-postfix

Чтобы сделать жадный синтаксический анализ однозначным, нам нужно запретить (из грамматики) любое вхождение S1 S2, где S1 заканчивается на exp, а S2 начинается с '('. Фактически, нам нужно различать разные типы операторов, в зависимости от от того, начинается ли оператор с ( и независимо от того, заканчивается ли оператор на exp. (На практике существует только три типа, потому что нет операторов, которые начинаются с ( и не заканчиваются exp. . [Примечание 4])

statement-list ::= Ø
                 | s1 statement-list
                 | s2 s2-postfix
                 | s3 s2-postfix
s2-postfix     ::= Ø
                 | s1 statement-list
                 | s2 s2-postfix
s1             ::= block | ';'
s2             ::= Name a-postfix
s3             ::= '(' exp ')' a-postfix

4. Что такое анализ рекурсивного спуска и как его можно изменить, чтобы включить устранение неоднозначности?

В наиболее распространенном использовании синтаксический анализатор рекурсивного спуска с предсказанием представляет собой реализацию алгоритма LL (k), в котором каждый нетерминал отображается на процедуру. Каждая нетерминальная процедура начинается с использования таблицы возможных опережающих последовательностей длиной k, чтобы решить, какую альтернативную продукцию для этого нетерминального устройства использовать, а затем просто «выполняет» производственный символ за символом: терминальные символы заставляют следующий входной символ использовать быть отвергнутым, если он совпадает, или сообщать об ошибке, если он не совпадает; нетерминальные символы вызывают вызов нетерминальной процедуры.

Таблицы упреждающих последовательностей могут быть построены с использованием наборов FIRST _k и FOLLOW _k. (Производство A→ω отображается на последовательность α терминалов, если α ∈ FIRSTk(ω FOLLOWk(A)).) [Примечание 5]

С этим определением синтаксического анализа рекурсивного спуска рекурсивный анализатор спуска может обрабатывать точно и только языки LL (k). [Примечание 6]

Однако согласование парсеров LL (k) и рекурсивного спуска игнорирует важный аспект парсера рекурсивного спуска, а именно то, что это, прежде всего, программа, обычно написанная в некотором полном по Тьюрингу программировании. язык. Если этой программе позволено немного отклониться от жесткой структуры, описанной выше, она сможет анализировать гораздо больший набор языков, даже языки, которые не являются контекстно-независимыми. (См., Например, контекстную чувствительность языка C, указанную в примечании 2.)

В частности, очень легко добавить правило «по умолчанию» к таблице, отображающей опережающие просмотры в продуктах. Это очень заманчивая оптимизация, поскольку она значительно уменьшает размер таблицы просмотра вперед. Обычно правило по умолчанию используется для нетерминалов, альтернативы которых включают пустую правую часть, которая в случае грамматики LL (1) будет отображаться на любой символ в FOLLOW, установленном для нетерминальный. В этой реализации таблица просмотра вперед включает только просмотры из набора ПЕРВЫЙ, а синтаксический анализатор автоматически создает пустую правую часть, соответствующую немедленному возврату для любого другого символа. (Как и аналогичная оптимизация в парсерах LR (k), эта оптимизация может задерживать распознавание ошибок, но они все равно распознаются до того, как будет прочитан дополнительный токен.)

Анализатор LL (1) не может включать в себя нетерминал, допускающий значение NULL, чьи наборы FIRST и FOLLOW содержат общий элемент. Однако, если синтаксический анализатор рекурсивного спуска использует оптимизацию по «правилу по умолчанию», этот конфликт никогда не будет замечен во время построения синтаксического анализатора. Фактически, игнорирование конфликта позволяет создать «жадный» синтаксический анализатор на основе (определенных) недетерминированных грамматик.

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

Я не собираюсь предоставлять полное доказательство вышеупомянутого утверждения, но первым делом нужно заметить, что любой нетерминал можно переписать как дизъюнкцию новых нетерминалов, каждый с одним отдельным ПЕРВЫМ токен и, возможно, новый нетерминал с пустой правой стороной. Затем необходимо "всего лишь" удалить нетерминалы из набора FOLLOW нетерминалов, допускающих значение NULL, путем создания новых дизъюнкций.