如何找到递归语法的 FIRST 和 FOLLOW 集？

Question

假设我有以下CFG。

A -> B | Cx | EPSILON
B -> C | yA
C -> B | w | z

现在，如果我尝试查找

FIRST(C) = FIRST(B) U FIRST(w) U FIRST(z)
         = FIRST(C) U FIRST(yA) U {w, z}

也就是说，我在循环。因此，我假设我必须将其转换为具有立即左递归的形式，我可以按如下方式进行。

A -> B | Cx | EPSILON
B -> C | yA
C -> C | yA | w | z

现在，如果我尝试计算第一个集合，我想我可以按如下方式完成。

FIRST(C) = FIRST(C) U FIRST(yA) U FIRST(w) U FIRST(z)
         = { y, w, z } // I ignore FIRST(C)
FIRST(B) = FIRST(C) U FIRST(yA)
         = { y, w, z }
FIRST(A) = FIRST(B) U FIRST(Cx) U FIRST(EPSILON)
         = { y, w, z, EPSILON }

我说得对吗？

但即使我就在那里，当我尝试从该语法计算 FOLLOW 集时，我仍然运行遇到问题。

FOLLOW(A) = { $ } U FOLLOW(B) U FOLLOW(C)

我从第 2 条规则得到 FOLLOW(B)，从第 3 条规则得到 FOLLOW(C)。但是现在要计算 FOLLOW(B)，我需要 FOLLOW(A)（来自第一个语法规则）所以我又陷入了循环。

有什么帮助吗？提前致谢！

Answer 1

由于 FIRST 和 FOLLOW 是（通常）递归的，因此将它们视为要求解的方程组很有用；该解决方案可以使用简单的增量算法来实现，该算法包括重复应用所有右侧，直到在一个循环中没有任何集合发生变化。

所以让我们采用给定语法的 FOLLOW 关系：

A → B | Cx | ε
B → C | yA
C → B | w | z

我们可以直接推导出方程：

FOLLOW(A) = FOLLOW(B) ∪ {$}
FOLLOW(B) = FOLLOW(A) ∪ FOLLOW(C)
FOLLOW(C) = FOLLOW(B) ∪ {x}

所以我们最初将所有后续集设置为{}，然后继续。

第一轮：

FOLLOW(A) = {} ∪ {$} = {$}
FOLLOW(B) = {$} ∪ {} = {$}
FOLLOW(C) = {$} U {x} = {$,x}

第二轮：

FOLLOW(A) = {$} ∪ {$} = {$}
FOLLOW(B) = {$} ∪ {$,x} = {$,x}
FOLLOW(C) = {$,x} U {x} = {$,x}

第三轮：

FOLLOW(A) = {$,x} ∪ {$} = {$,x}
FOLLOW(B) = {$} ∪ {$,x} = {$,x}
FOLLOW(C) = {$,x} U {x} = {$,x}

第四轮：

FOLLOW(A) = {$,x} ∪ {$} = {$,x}
FOLLOW(B) = {$,x} ∪ {$,x} = {$,x}
FOLLOW(C) = {$,x} U {x} = {$,x}

到这里我们就停止了，因为上一轮没有做任何改变。

这个算法必须终止，因为符号的数量是有限的，每一轮只能将符号添加到步骤中。它不是最有效的技术，尽管在实践中通常已经足够好了。

如何找到递归语法的 FIRST 和 FOLLOW 集？

How to find FIRST and FOLLOW sets of a recursive grammar?

compiler-construction

context-free-grammar