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

Question

В dragon book Л.Л. грамматика определяется следующим образом:

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

1. FIRST(a) и FIRST(b) не пересекаются. Это означает, что они не могут одновременно получить EMPTY

2. Если 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. Но я не знаю, является ли левая рекурсия FIRST(SA) и FOLLOW(S) не разделенной, или есть какая-то другая причина? Положите это по-другому, верно ли, что каждая леворекурсивная грамматика будет иметь производство, которое нарушит условие 2 грамматики LL?

Answer 1

Хорошо, я понять это, если грамматика содержит левое рекурсивное производство, как:

S->SA 

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

S->B 

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

Answer 2

Рассмотрим грамматику:

S->SA|empty 
A->a 

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

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

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

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

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

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

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

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

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

Answer 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).

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