parsing - LL(1) 文法。有自递归规则怎么计算follow set？

Question

根据这个paper的规则:

1. If A is the start nonterminal, put EOF in FOLLOW(A)
   Find the productions with A on the right-hand-side:
2. For each production X → αAβ, put FIRST(β) − {EPSILON } in FOLLOW(A)
3. If EPSILON is in FIRST(β) then put FOLLOW(X) into FOLLOW(A)
4. For each production X → αA, put FOLLOW(X) into 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](*)