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

Question

我在一个我正在尝试的编译器样本期末考试中遇到了一个问题。如果有人能帮我解释一下，我将不胜感激。谢谢

考虑下面列出的语法 G

S = E $

E = E + T |电话

T = T * F |传真

F = ident | (电子 )

其中 + * ident ( ) 是终结符和 $是文件结尾。
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

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

SLR(1) 增加了lookahead，并利用follow-set信息进行缩减(总比没有好，但是从语法中全局获得的follow-set信息不是上下文敏感的，就像LALR中的state-specific lookahead sets( 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(编译器:原则、技术和工具，Aho、Sethi、Ullman，1988 年)在一组示例中使用完全相同的语法，这些示例展示了规范 LR(0) 项集和相关 DFA 的推导，以及填写解析表的一些步骤。这是第 4.7 节，从示例 4.34 开始。