如何在FOLLOW集中删除循环依赖

Question

考虑一下简短的语法

S -> Bc | DB
B -> ab | cS
D -> d | epsilon

第一组是

FIRST(S) ={a,c,d}
FIRST(B) = { a,c }
FIRST(D)= { d, epsilon }

在它里面

Follow(S)={ Follow(B) }

和

Follow(B) ={ c , Follow(S) }

我的问题是如何解决这个循环依赖？

Answer 1

这种循环依赖一开始就不应该存在。这是查找“follow”的算法：

\n\n

将所有跟随组初始化为 {}，但 S 除外，它初始化为 {$}。
\n虽然有变化，但对于每个 A\xe2\x88\x88V 执行：
\n 对于每个 Y \xe2\x86\x92 \xce\xb1A\xce\xb2 执行：
\n follow(A) = follow(A) \ xe2\x88\xaa first(\xce\xb2)
\n 如果 \xce\xb2 \xe2\x87\x92* \xce\xb5，也执行： follow(A) = follow(A) \xe2\x88\xaa follow (是)

\n\n

因此，在您的情况下，您应该得到：
\nFollow(S)={c,$}
\nFollow(B)={c,$}
\nFollow(D)={a,c}

\n