parsing - LL(1) 语法的示例不是 LALR？

Question

我现在正在我的编译理论类(class)中学习解析器。我需要找到一个在 LL(1) 中但不在 LALR 中的语法示例。我知道它应该存在。请帮我想出这个问题的最简单的例子。

Answer 1

Some googling提出这个非 LALR(1) 语法的示例，即 LL(1):

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

LALR(1)构造失败，因为E和F之间存在reduce-reduce冲突。在LR(0)状态集合中，有一个状态由以下组成

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

S 和 X 上下文都需要它。这些项目的 LALR(1) 前瞻集因此混合了源自 S 和 X 产品的标记。这对于 LR(1) 来说是不同的，这些情况有不同的状态。

对于 LL(1)，决策是通过查看第一组替代方案来做出的，其中“)”和“]”总是出现在不同的替代方案中。