Интуитивно понятно, что синтаксический анализатор LALR (1) формируется путем запуска с анализатора LR (1) и многократного объединения состояний вместе, когда эти состояния идентичны, за исключением просмотра вперед. Следовательно, синтаксический анализатор LR (1) и LALR (1) для грамматики будет одинаковым всякий раз, когда нет никаких состояний такого рода, которые можно было бы объединить вместе.
В этом случае таблицы синтаксического анализа для двух парсеры будут полностью идентичны. Таблицы GOTO будут одинаковыми, потому что два анализатора имеют одинаковые состояния и одинаковые переходы, а таблицы ACTION будут одинаковыми, потому что элементы сдвига и уменьшения в каждом состоянии одинаковы.
Я считаю, что Speci c Требование, которое должно выполняться для автоматов LALR (1) и LR (1), чтобы быть одинаковыми, состоит в том, что синтаксические анализаторы LR (0) и LR (1) грамматики должны быть идентичны друг другу, игнорируя опережающие просмотры. В частности:
- Если парсеры LR (0) и LR (1) одинаковы, игнорируя опережающие просмотры, то в парсере LR (1) нет состояний, которые можно было бы объединить вместе, поэтому LR (1 ) синтаксический анализатор совпадает с синтаксическим анализатором LALR (1).
- Если синтаксический анализатор LALR (1) и синтаксический анализатор LR (1) одинаковы, то никакие состояния в анализаторе LR (1) не были бы объединены все вместе. Поскольку количество состояний в парсере LALR (1) для грамматики всегда совпадает с количеством состояний LR (0), это означает, что парсеры LR (1) и LR (0) имеют одинаковое количество состояний. Это означает, что они могут отличаться только в просмотре вперед.
Другими словами, да, это возможно. Точнее:
Теорема : грамматика G имеет идентичные парсеры LALR (1) и LR (1) тогда и только тогда, когда она имеет идентичные LR ( 0) и LR (1), игнорируя опережающие просмотры.
Это означает, что любая грамматика, имеющая это свойство, должна быть LR (0), и в этом случае вы не захотите использовать LALR ( 1) парсер. Однако не все грамматики LR (0) обладают этим свойством. Например, рассмотрим эту грамматику:
S -> aTbT
T -> c
Вот парсер LR (1):
(1)
S' -> .S [$]
S -> .aTbT [$]
(2)
S -> a.TbT [$]
T -> .c [b]
(3)
T -> c. [b]
(4)
S -> aT.bT [$]
(5)
S -> aTb.T [$]
T -> .c [$]
(6)
T -> c. [$]
(7)
S -> aTbT. [$]
(8)
S' -> S [$]
Здесь состояния (3) и (6) будут объединены в LALR (1) синтаксический анализатор, поэтому синтаксические анализаторы LR (1) и LALR (1) не совпадают. Однако вы можете проверить, что эта грамматика действительно LR (0), показывая, что только подмножество грамматик LR (0) имеет это свойство.