0

在此页面上，作者解释了如何确定 CFG 的 FOLLOW 集。在标题语法分析目标：FOLLOW Sets下，他说：

制作跟随集的步骤

约定：a、b 和 c 代表终端或非终端。a* 表示零个或多个终端或非终端（可能两者）。a+ 代表一个或多个... D 是非终结符。

  1. 将输入结束标记 ($) 放入起始规则的后续集中。
  2. 假设我们有一个规则 R → a*Db。First(b) 中的所有内容（ε 除外）都添加到 Follow(D)。如果 First(b) 包含 ε，则 Follow(R) 中的所有内容都放入 Follow(D)。
  3. 最后，如果我们有规则 R → a*D，那么 Follow(R) 中的所有内容都放在 Follow(D) 中。
  4. 终端的跟随集是一个空集。

到目前为止，一切都很好。但是在这个项目下面的框中，我们读到：

[...] 规则 1 (N → V = E) 的第 2 步表明 first(=) 在 Follow(V) 中。

现在这是我不明白的部分。当他说 First(=) 在 Follow (V) 中时，他显然将 = 映射到 b 并将 V 映射到 D（b 和 D 来自第一个框中的说明）。但(a*)(D)(b)不匹配()(V)(=)E。

我完全看错了，还是作者可能写a*Db而不是a*Dba*？

（特别是如果您在wikipedia上阅读此内容：“项目 I [A → α • B β, x] 的 FOLLOW(I) 是可以出现在非终结符 B 之后的终结符集，其中 α, β 是任意符号字符串，并且x 是一个任意的前瞻终端。")

4

1 回答 1

1

是的，他的意思是：

R → a* D b*

并且由于b*可能是零符号，即ε，因此不需要第二条规则。请记住，它FIRST是在任意符号序列上定义的。

换句话说，对于：

A → α B β

  1. 中的每个终端FIRST(β)都在 中FOLLOW(B)，并且
  2. 如果β ⇒* ε，则 中的所有内容都在FOLLOW(A)中FOLLOW(B)。

以下是 Aho、Sethi 和 Ullman 在龙书中所说的：

形式上，我们说LR(1)item对于可行前缀 γ[A → α·β, a]是有效的，如果有一个推导
S ⇒* δAw ⇒ δαβw
，其中γ = δαand是ora的第一个符号，并且是。wwa$

（⇒上面的 被标记rm，意思是right-most derivation；换句话说，在每个推导步骤中，最右边的非终结符被它的一个产生式替换。因此，w只包含终结符。）

换句话说，如果我们已经达到某个点，我们已经决定这可能是下一个减少并且可能会遵循，那么该LR(1)项目是有效的（可能适用） ；在解析的当前点，我们已经读取了 α。所以如果遵循β，那么减少是可能的。我们还不知道，除非 β 是空序列，但我们需要记住这一事实，以防 β 可以推导出空序列。AaA a

我希望这会有所帮助。这里已经很晚了，我太累了，不能再检查一遍了。明天吧...

于 2013-09-18T06:15:30.490 回答