FOLLOW 已消除左因式分解的语法集

Question

我想知道某个NonTerminal的FOLLOW集是什么，当一个语法的左递归被消除时，就像下面的示例语法。

让我们假设这个语法

1 E → T E’
2 E’→ + T E’ 
3 E’→ ε
4 T → F T’
5 T’→ * F T’
6 T’→ ε
7 F → ( E ) 
8 F → id

示例 1：

我们先来看看第4行-第8行的部分

4 T → F T’
5 T’→ * F T’
6 T’→ ε
7 F → ( E ) 
8 F → id

在这种情况下 FOLLOW(F) 是...正确吗？

{*}

解释：

1. 如果 T' 重复，则 F 后跟 +。另一方面，如果 T' 扩展为 ε，则 F 后跟 ε。

示例 2：

当我们扩大上下文并查看整个语法时，是否正确，该语法的 F 的完整 FOLLOW-Set 是...？

-> {'+', '*', ')', '$'}

解释：

1. 查看第 5 行。如果 T' 重复，则 F 后跟'*'。另一方面，如果 T' 扩展为 ε，则 F 之后是 ε。因此，规则是将 FOLLOW(T') 添加到 FOLLOW(F)。

-> {'*'}

2. 如果第4行的T'再次展开为ε，则规则为FOLLOW(F)加上FOLLOW(T)。

3. 如果第2行的E'再次展开为T'，那么T后面跟着+。如果 E' 扩展为 ε，则 T 后跟 ε。规则“将 FOLLOW(E') 添加到 FOLLOW(T) 再次适用

-> {'+'}

4. 同<2>一样适用。如果第 1 行中的 E' 扩展为 ε，规则“将 FOLLOW(E) 添加到 FOLLOW(T)”。这是

-> {')'}

此致

冯·斯波茨

编辑：

根据 rici 的答案更正了 FOLLOW-Sets 不包含'ε'。这就是规则

If A -> αB, add FOLLOW(A) to FOLLOW(B)

是为了.

还有 rici 的提示，T 的 Follow 是 E，如示例 2 中所述：(4) 因此接受符号 '$' 也属于 Follow(F)。

Answer 1

FOLLOW(F) 是 {'+', '*', ')', $}（其中 $ 是结束标记）。

以下集合从不包含 ε。计算 FOLLOW 时需要考虑 ε，但不将其添加到任何 FOLLOW 集中。