LL(1)Grammer的例子不是LALR？

Question

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

谢谢.

Answer 1

一些谷歌搜索为非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),通过查看第一组备选方案来做出决策,其中')'和']'总是出现在不同的备选方案中.