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

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

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

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

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

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

S->SA|empty
A->a

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


grammar ll left-recursion
person wangshuaijie    schedule 23.04.2013    source источник
comment
Теоретическая проблема заключается в том, что LA(S->SA) и LA(S->e) содержат a. Смотрите мой ответ для более интуитивного объяснения.   -  person Apalala    schedule 24.04.2013

Ответы (3)


arrow_upward
15
arrow_downward

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

S->SA

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

S->B

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

person wangshuaijie    schedule 23.04.2013

arrow_upward
12
arrow_downward

Обратите внимание на свою грамматику:

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. Какой из них мы должны использовать?

person Emil Vikström    schedule 23.04.2013
comment
Спасибо за ваш ответ, но, пожалуйста, поймите, о чем я прошу, да, мы не можем решить, какое правило для S использовать, потому что FIRST(SA) и FOLLOW(S) являются совместными, мой вопрос: это левая рекурсия, которая делает FIRST (SA) и FOLLOW(S) совместные? Спасибо. - person wangshuaijie; 23.04.2013
comment
@wangshuaijie Ваш вопрос относится к S->SX|e формам, и ответ будет да. В более общем случае будет пересечение наборов опережающего просмотра (LA) для разных правил для S, если есть S->SX. Пересечения в наборах LA для одного и того же нетерминального символа означают, что детерминированное решение для правильного правила не может быть принято на определенных входных данных. - person Apalala; 24.04.2013

arrow_upward
9
arrow_downward

Грамматика 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).

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

person Apalala    schedule 23.04.2013