如何找到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集合,我想我可以按如下方式完成它.

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个规则得到(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}

在这里我们停止,因为在上一轮没有做出任何改变.

该算法必须终止,因为存在有限数量的符号,并且每一轮只能向步骤添加符号.它不是最有效的技术,尽管它在实践中通常足够好.