Пример для грамматики LL (1), которая НЕ LALR?

Question

Я сейчас изучаю парсеры на моем курсе теории компиляции.Мне нужно найти пример для грамматики, который находится в LL (1), но не в LALR.Я знаю, что это должно существовать.пожалуйста, помогите мне придумать самый простой пример этой проблемы.

Answer 1

Некоторый поиск в Google приводит этот пример для грамматики не-LALR (1), которая является LL (1):

S ::= '(' X 
    | E ']' 
    | F ')'
X ::= E ')' 
    | F ']'
E ::= A
F ::= A
A ::= ε

Конструкция LALR (1) терпит неудачу, потому что существует конфликт уменьшения-уменьшения между E и F. В наборе состояний LR (0) существует состояние, состоящее из

E ::= A . ;
F ::= A . ;

, что необходимо для контекстов S и X. Таким образом, наборы LALR (1) для этих предметов смешивают токены, происходящие из произведений S и X. Это отличается для LR (1), где для этих случаев существуют разные состояния.

При использовании LL (1) решения принимаются на основе ПЕРВЫХ наборов альтернатив, где ')' и ']' всегда встречаются в разных альтернативах.

Answer 2

Из книги Дракона (Второе издание, стр. 242):

Класс грамматик, которые могут быть проанализированы с помощью методов LR, является надлежащей надмножеством класса грамматик, которые можно анализировать с помощьюПредиктивный или LL методы.Чтобы грамматика была LR (k), мы должны быть в состоянии распознать вхождение правой стороны произведения в форме с прямым предложением, с k входными символами предвкушения.Это требование намного менее строгое, чем требование для грамматик LL (k), где мы должны быть в состоянии распознать использование произведения, видя только первые k символов того, что выводит правая сторона.Таким образом, неудивительно, что грамматики LR могут описывать больше языков, чем грамматики LL.