Анализ: грамматика в LL (3), но не в LR (2)

Question

Я пытаюсь доказать, что LL (3) не является подмножеством LR (2).

Интуитивно это легко, но я не могу указать свою интуицию на поиск такой грамматики.

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

Answer 1

теорему: Если грамматика LL (3), но не LR (2), то есть грамматика & эпсилон; -productions.

Доказательство: грамматики является LL (3), если всегда можно определить ручку в правой сентенционной форме после прочтения три символов мимо начал ручки.

Грамматика - это LR (2), если всегда можно идентифицировать дескриптор в правой условной форме после прочтения двух символов за конец ручки.

Если грамматика LL (3), но не LR (2), то чтение трех символов за начало дескриптора иногда должно содержать больше информации, чем чтение двух символов за конец дескриптора. Это может произойти только в том случае, если дескриптор пуст.

Answer 2

Ну, очевидно, трюк заключается в использовании ε-постановок.

Следующая грамматика будет работать:

S->aa|Aaaa 

A->ε