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

Question

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

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

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

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

1

parsing theory ll-grammar lr-grammar

Источник

user1236401 10 дек '12 в 21:36

2 ответа

Решение

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

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

S->aa|Aaaa

A->ε

3

Источник

user1236401 10 дек '12 в 22:29

Другие вопросы по тегам parsing theory ll-grammar lr-grammar

user763305 09 фев '13 в 17:07 2013-02-09 17:07 · Accepted Answer · 2013-02-09 17:07

Теорема: Если грамматика есть LL(3), но не LR(2), то грамматика имеет ε-произведения.

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

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

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