LR(0)或SLR(1)或LALR(1)

Question

我很难坚持我正在尝试从编译器的样本期末考试中提出的问题.如果有人可以帮我解释,我将非常感激.谢谢

考虑下面列出的语法G.

1. S = E. $
2. E = E +T | Ť
3. T = T *F | F
4. F = ident| (Ë)

其中+*ident()是终端符号并且$是文件的结尾.a)这个语法LR(0)？证明你的答案.b)语法单反(1)？证明你的答案.c)这个语法LALR(1)？证明你的答案.

Answer 1

如果你可以证明语法是LR(0)那么它当然是SLR(1)和LALR(1)因为LR(0)更具限制性.

不幸的是,语法不是LR(0).

比如假设你刚刚认出了E:

S -> E . $

如果后面的内容是a +或*符号,则不能将此E减少为S ,因为E可以跟随+或*继续构建更大的表达式:

S -> E . $
E -> E . + T
T -> T . * F

这要求我们向前看一个令牌以了解在该状态下该做什么:转移(+或*)或减少($).

SLR(1)增加了前瞻,并利用后续信息进行缩减(总比没有好,但是从语法中全局获得的跟随信息不是上下文敏感的,比如LALR中的状态特定的前瞻集( 1)).

在SLR(1)下,上述冲突消失了,因为S -> E仅当前瞻符号在后续集合中时才考虑减少S,并且后续集合中的唯一内容S是EOF符号$.如果输入符号不是$,+则不考虑减少; 发生了与减少不相冲突的转变.

所以语法不会因为SLR(1)这种冲突而失败.但是,它可能还有其他冲突.透过它看,我看不到一个; 但要正确地"证明答案",你必须生成所有LR(0)状态项,并完成验证不违反SLR(1)约束的例程.(对于SLR(1),您使用简单的LR(0)项,因为SLR(1)不会以任何新的方式扩充这些项.请记住,它只使用从语法中剔除的后续信息来消除冲突.)

如果是SLR(1)则LALR(1)按子集关系下降.

更新

Red Dragon Book(编译器:Principles,Techniques and Tools,Aho,Sethi,Ullman,1988)在一组示例中使用完全相同的语法,这些示例显示了规范LR(0)项集和相关DFA的推导,以及填写解析表的一些步骤.这是在4.7节,从例4.34开始.