计算语法的 FOLLOW() 集

Question

我正在阅读 Compilers: Principles, Techniques, and Tools (2nd Edition) 并且正在尝试计算以下语法的 FOLLOW() 组：

S  →  iEtSS' | a
S' →  eS | ε
E  →  b

其中 S, S', E 是 非终结符 符号，S 是 start 符号，i, t, a, e, b 是 terminal 符号， ε 是空字符串。

到目前为止我做了什么

FOLLOW(S) = {$} ∪ FOLLOW(S')
FOLLOW(S') = FOLLOW(S)
FOLLOW(E) = FIRST(tSS') - {ε} = FIRST(t) - {ε} = {t} - {ε} = {t}

其中 $ 是 输入右端标记。

说明

$ ∈ FOLLOW(S)，因为S是开始符号。我们还知道 S' → eS，所以 FOLLOW(S') 中的所有内容都在 FOLLOW(S) 中。因此，FOLLOW(S) = {$} ∪ FOLLOW(S').

我们也知道 S → iEtSS'，所以 FOLLOW(S) 中的所有内容都在 FOLLOW(S') 中。因此，FOLLOW(S') = FOLLOW(S)。

问题是我无法计算 FOLLOW(S)，因为我不知道 FOLLOW(S')。有什么想法吗？

Answer 1

文中描述的简单算法是最小不动点计算。您基本上循环遍历非终结符，将终结符放入后续集合，直到完成整个循环而没有任何变化。

由于从任何后续集中都没有删除任何内容，并且终端的数量是有限的，因此算法必须终止。通常只需要几个周期。

Computing the FOLLOW() set of a grammar