假设我有以下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集，我认为可以按以下方式完成它。
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)
我从第二条规则获得FOLLOW(B)，从第三条规则获得FOLLOW(C)。但是现在要计算FOLLOW(B)，我需要FOLLOW(A)(根据第一语法规则)，因此我又陷入了循环。
有什么帮助吗？
提前致谢!
最佳答案
由于FIRST和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}
我们在这里停止，因为上一轮没有进行任何更改。
该算法必须终止，因为符号数量有限，并且每一轮只能向步骤添加符号。尽管通常它在实践中已经足够好，但这不是最有效的技术。
关于compiler-construction - 如何找到递归语法的第一套和第二套？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/29197332/