context-free-grammar – 如何在FOLLOW集中删除循环依赖

发布时间：2020-12-14 05:02:28 所属栏目：百科来源：网络整理

导读：考虑一下简短的语法 S - Bc | DBB - ab | cSD - d | epsilon 第一组是 FIRST(S) ={a,c,d}FIRST(B) = { a,c }FIRST(D)= { d,epsilon } 在它里面 Follow(S)={ Follow(B) } 和 Follow(B) ={ c,Follow(S) } 我的问题是如何解决这个循环依赖？解决方法这种循环

考虑一下简短的语法

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) }

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

解决方法

这种循环依赖不应该从那里开始.这是找到’follow’的算法：

初始化所有关注组到{},除了S是init到{$}.
虽然有变化,但每个A∈V都有：
对于每个Y→αAβ做：
跟随(A)=跟随(A)∪第一(β)
如果β?*ε,也可以：跟随(A)=跟随(A)∪跟随(Y)

所以在你的情况下,你应该得到：按照(S)= {C,$}跟随(B)= {C,$}按照(d)= {A,C}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!