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

Question

我被一个试题深深地困住了，我正试图从编译器的期末考试中试一试。如果有人能帮我解释一下，我会非常感激的。谢谢

考虑下面列出的语法G

$

• E =E

1. S =E + T *
2. T=T*F* F
3. F = ident ( E )

其中+* ident ()是终端符号，$是file的末尾。( a)这个语法是LR( 0 )吗？证明你的答案是正确的。( b)语法SLR( 1)是吗？证明你的答案是正确的。( c)这个语法是LALR( 1 )吗？证明你的答案是正确的。

Answer 1

如果可以证明语法是LR(0)，那么当然是SLR(1)和LALR(1)，因为LR(0)的限制性更强。

不幸的是，语法不是LR(0)。

例如，假设您刚刚识别了E：

S -> E . $

如果下面是+或*符号，则不能将这个E降为S，因为E后面可以是+或*，它们继续构建更大的表达式：

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

这要求我们向前看一看，知道在这种状态下应该做什么:移位(+或*)或减少($)。

SLR(1)增加展望，并利用后续集信息进行缩减(总比没有好，但从语法全局获取的后续集信息并不是上下文敏感的，就像LALR(1)中特定于状态的查找集)。

在单反(1)下，上述冲突消失了，因为只有当S -> E符号位于S的后续集合中时，才会考虑到S的约简，而在后续的S集合中唯一的东西是EOF符号$。如果输入符号不是$ (和+一样)，那么就不考虑缩减；会发生与约简不冲突的移位。

因此，语法并不会因为这种冲突而不成为SLR(1)。然而，它可能有一些其他的冲突。浏览一下，我看不到一个；但是要正确地“证明这个答案是正确的”，必须生成所有LR(0)状态项，并通过验证SLR(1)约束没有违反的例程。(对SLR(1)使用简单的LR(0)项，因为SLR(1)不会以任何新的方式增加这些项。记住，它只是使用语法中的后续信息来消除冲突。)

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

更新

红龙书(编译器:原则、技术和工具，Aho，Sethi，Ullman，1988)在一组示例中使用了完全相同的语法，这些示例显示了规范LR(0)项集和相关DFA的派生，以及填充解析表的一些步骤。这在4.7节，从例子4.34开始。