parsing - LL(1) 语法。如果有自递归规则，如何计算跟随集？

Question

根据本文的规则：

1. 如果 A 是开始非终结符，则将 EOF 放入 FOLLOW(A)
   找到右侧带有 A 的产生式：
2. 对于每个产生式 X → αAβ，将 FIRST(β) − {EPSILON } 放入 FOLLOW(A)
3. 如果 EPSILON 在 FIRST(β) 中，则将 FOLLOW(X) 放入 FOLLOW(A)
4. 对于每个产生式 X → αA，将 FOLLOW(X) 放入 FOLLOW(A)

我的语法中有下一段：

 ...
    A -> C B
    B -> , A
    C -> EPSILON
    C -> =
    B -> ;
 ...

当我尝试根据规则 4 计算 FOLLOW(B) 时，我必须计算 FOLLOW(A)，反之亦然。所以我有 StackOverflowException 因为自递归。

我应该怎么办？

Answer 1

你不使用递归。您进行迭代，FOLLOW根据上一次迭代计算的结果计算集合：

1. 如果 A 是开始非终结符，则将EOF（指示输入结束的新终结符）放入 F[0](A)。

2. 对于每个产生式 X → αAβ，将 FIRST(β) − {EPSILON} 放入 F[n](A)，

3. 如果 EPSILON 在 FIRST(β) 中，则将 F[n-1](X) 放入 F[n](A)

4. 对于每个产生式 X → αA，将 F[n-1](X) 放入 F[n](A)。

5. 当 F[n](*) == F[n-1](*) 时停止

跟随(*) == F[n](*)