如何找到 FIRST 和 FOLLOW

Question

我想为以下 CFG 找到 FIRST 和 FOLLOW：

S -> O | M
M -> iEtMeM | a
O -> iEtS | iEtMeO
E -> b

我做了左分解，所以我得到：

S -> O | M
M -> iEtMeM | a
O -> iEtO'
O'-> S | MeO
E -> b

第一组：

FIRST(S) = FIRST(O)|FIRST(M) = {i,a}
FIRST(M) = {i,a}
FIRST(O) = {i}
FIRST(O') = FIRST(S)|FIRST(M) = {i,a}
FIRST(E) = {b}

现在我找不到 S 的 FOLLOW 集，因为我不知道 FOLLOW(O') 是什么：

FOLLOW(S) = {$, FOLLOW(O')}

Answer 1

~~其实只有FOLLOW(S) = {$}。~~

所以，我忽略了右边提到的 S 边。以下更正：

首先我们通过添加产生式S' ->S$得到扩充文法，然后 FOLLOW(S') = {$}.

然后我们有

来自 S' -> S$ 和 O' -> S

关注（S）=第一（$）+关注（O'）
来自 M -> iEtMeM、O' -> MeO 和 S -> M

跟随（M）=第一个（eM）+第一个（eO）+跟随（S）
来自 S -> O 和 O' -> MeO

关注(O) = 关注(S) + 关注(O')
来自 O -> iEtO'

关注(O') = 关注(O)
来自 M -> iEtMeM 和 O -> iEtO'

跟随（E）=第一个（tMeM）+第一个（tO'）

"problem"是对的相互递归定义 FOLLOW(S)、FOLLOW(O) 和 `FOLLOW(O') - 这意味着每个这些跟随集的一部分是其他集的子集，因此它们是等于。

如果一个代表一组包含约束，由以上等式，作为图形（以非终端符号作为节点），每组相互递归的定义形成一个强连接组件。用新的替换每个 SCC 节点将产生一个DAG，代表一组非递归方程，然后可以通过 "evaluated" in 拓扑顺序。

比如说，我们用节点 N 替换对应于符号 S、O 和 O' 的节点。等式变为：

FOLLOW(N) = FIRST($) + FOLLOW(N)
FOLLOW(M) = FIRST(eM) + FIRST(eO) + FOLLOW(N)
FOLLOW(N) = FOLLOW(N) + FOLLOW(N)
FOLLOW(N) = FOLLOW(N)
FOLLOW(E) = FIRST(tMeM) + FIRST(tO')

并通过剪掉多余的部分：

FOLLOW(N) = FIRST($) = {$}
FOLLOW(M) = FIRST(eM) + FIRST(eO) + FOLLOW(N) = {e, $}
FOLLOW(E) = FIRST(tMeM) + FIRST(tO') = {t}

并且，由于 N 代表 S、O 或 O'，我们得到：

FOLLOW(S`) = FOLLOW(S) = FOLLOW(O) = FOLLOW(O`) = {$}
FOLLOW(M) = {e, $}
FOLLOW(E) = {t}

如何找到 FIRST 和 FOLLOW

How to find FIRST and FOLLOW

compiler-construction

context-free-grammar