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

Question

Согласно "Парсеру рекурсивного спуска" в Википедии, рекурсивный спуск без обратного отслеживания (так называемый предиктивный анализ) возможен только для грамматик LL(k).

В другом месте я читал, что реализация Lua использует такой парсер. Тем не менее, язык не является LL(k). На самом деле, Луа по своей сути неоднозначен: делает a = f(g)(h)[i] = 1 имею в виду a = f(g); (h)[i] = 1 или же a = f; (g)(h)[i] = 1? Эта двусмысленность разрешается жадностью в синтаксическом анализаторе (поэтому вышеизложенное разбирается как ошибочное a = f(g)(h)[i]; = 1).

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

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

Answer 1

TL;DR

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

Lua может быть проанализирован с помощью синтаксического анализатора с рекурсивным спуском именно потому, что язык LL(k); то есть грамматика LL(k) существует для Lua. [Примечание 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

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

Другим распространенным примером неоднозначных эталонных грамматик, которые могут быть механически устранены, является неоднозначность "висячего другого", встречающаяся в таких языках, как 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

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

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

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

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 так же является леворекурсивной, поэтому она явно не 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 для нетерминала. В этой реализации таблица предварительного просмотра включает в себя только элементы предварительного просмотра из набора FIRST, и анализатор автоматически создает пустую правую часть, соответствующую немедленному возврату, для любого другого символа. (Как и в случае аналогичной оптимизации в синтаксических анализаторах LR(k), эта оптимизация может задержать распознавание ошибок, но они все еще распознаются до считывания дополнительного токена.)

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

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

Я не собираюсь предоставлять полное доказательство вышеупомянутого утверждения, но первый шаг заключается в том, чтобы заметить, что любой нетерминал может быть переписан как дизъюнкция новых нетерминалов, каждый из которых имеет отдельный отдельный токен FIRST и, возможно, новый нетерминал с пустой правой стороной. Тогда "только" необходимо удалить нетерминалы из набора FOLLOW обнуляемых нетерминалов путем создания новых дизъюнкций.

---

Заметки

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

2. Существуют языки программирования, которые не могут быть детерминированно проанализированы с помощью контекстно-свободной грамматики. Наиболее известный пример - это, вероятно, Perl, но есть и хорошо известная конструкция C (x)*y который может быть проанализирован только детерминистически с использованием информации о символе x - будь то имя переменной или псевдоним типа - и трудности с правильным синтаксическим анализом выражений C++ с использованием шаблонов. (См., Например, вопросы Почему C++ не может быть проанализирован с помощью анализатора LR(1)? Является ли C++ контекстно-зависимым или контекстно-зависимым?)

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

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

5. Существуют детерминированные грамматики LL(k), которые не могут создать однозначные таблицы синтаксического анализа с использованием этого алгоритма, который Сиппу и Сойсалон-Сойнинен называют алгоритмом Strong LL(k). Можно дополнить алгоритм, используя дополнительное состояние синтаксического анализа, аналогичное состоянию в синтаксическом анализаторе LR(k). Это может быть удобно для определенных грамматик, но это не меняет определения языков LL(k). Как показывают Sippu и Soisalon-Soininen, из любой грамматики LL(k) можно получить механическую грамматику SLL(k), которая дает точно такой же язык. (См. Теорему 8.47 в томе 2).

6. Алгоритм рекурсивного определения является точной реализацией синтаксического анализатора LL(k) на основе канонического стека, где стек синтаксического анализатора неявно создается во время выполнения синтаксического анализатора с использованием комбинации текущего продолжения и стека записей активации.