Почему грамматика LL не может быть рекурсивной?

В книге драконов грамматика LL определяется следующим образом:

Грамматика LL тогда и только тогда, когда для любого произведения A -> a|b применяются следующие два условия:

FIRST(a) и FIRST(b) не пересекаются. Это означает, что они не могут оба получить EMPTY
Если b может выводить EMPTY, то a не может выводить строку, начинающуюся с FOLLOW(A), то есть FIRST(a) и FOLLOW(A) должна быть непересекающейся.

И я знаю, что грамматика LL не может быть рекурсивной, но какова формальная причина? Думаю, леворекурсивная грамматика будет противоречить правилу 2, верно? например, я написал следующую грамматику:

S->SA|empty
A->a

Поскольку FIRST(SA) = {a, empty} и FOLLOW(S) ={$, a}, то FIRST(SA) и FOLLOW(S) не пересекаются, поэтому эта грамматика не LL. Но я не знаю, является ли это левая рекурсия make FIRST(SA) и FOLLOW(S) непересекающейся, или есть какая-то другая причина? Положите это по-другому, верно ли, что каждая леворекурсивная грамматика будет иметь произведение, которое нарушит условие 2 грамматики LL?

Ответ 1

ОК, я понимаю, если грамматика содержит леворекурсивное производство, например:

S->SA

Тогда каким-то образом он должен содержать другое производство, чтобы "закончить" рекурсию, скажем:

S->B

И поскольку FIRST (B) является подмножеством FIRST (SA), поэтому они являются совместными, это нарушает условие 1, конфликт при заполнении записей таблицы анализа, соответствующих терминалам, как в FIRST (B), так и в FIRST (SA). Резюмируя, левая рекурсивная грамматика может привести к тому, что FIRST-набор из двух или более производств имеет общие терминалы, что нарушает условие 1.

Ответ 2

Считайте свою грамматику:

S->SA|empty
A->a

Это сокращение для трех правил:

S -> SA
S -> empty
A -> a

Теперь рассмотрим строку aaa. Как это было сделано? Вы можете читать только один символ за раз, если у вас нет взгляда, поэтому вы начинаете как это (у вас есть S как символ начала):

S -> SA
S -> empty
A -> a

Хорошо, вы создали первый a. Но теперь вы не можете применять больше правил, потому что больше нет терминалов. Вы застряли!

Что вы должны были сделать, так это:

S -> SA
S -> SA
S -> SA
S -> empty
A -> a
A -> a
A -> a

Но вы не знаете этого, не читая всю строку. Вам понадобится бесконечное количество просмотров.

В общем смысле да каждая леворекурсивная грамматика может иметь неоднозначные строки без бесконечного вида. Посмотрите еще раз на пример: для S существует два разных правила. Какой из них мы должны использовать?

Ответ 3

Грамматика LL(k) - это та, которая позволяет построить детерминированный парсер спуска только с символами k. Проблема с левой рекурсией состоит в том, что она не позволяет определить, какое правило применять, пока не будет проверена полная входная строка, что делает требуемый k потенциально бесконечным.

Используя ваш пример, выберите k и дайте парсеру последовательность ввода длины n >= k:

aaaaaaa...

Парсер не может решить, следует ли ему применять S->SA или S->empty, если посмотреть на символы k впереди, потому что решение будет зависеть от того, сколько раз S->SA было выбрано до этого, и это информация - синтаксический анализатор не имеет.

Анализатор должен будет выбрать S->SA ровно n раз и S->empty один раз, и невозможно решить, что правильно, посмотрев первые k символы во входном потоке.

Чтобы знать, синтаксический анализатор должен был бы изучить всю входную последовательность и подсчитать количество раз S->SA, но такой синтаксический анализатор выйдет за пределы определения LL(k).

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