4

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

考虑下面列出的语法 G

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

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

4

1 回答 1

9

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

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

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

S -> E . $

如果后面是+or*符号，则不能将此 E 简化为 S，因为E后面可以跟着+or*继续构建一个更大的表达式：

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

这要求我们向前看一个标记以知道在该状态下要做什么：转移（+或*）或减少（$）。

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) 属于子集关系。

更新

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

于 2012-04-13T23:46:06.847 回答