编译器实践四 之 FIRST集合,NULLABLE集合,FOLLOW集合
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了编译器实践四 之 FIRST集合,NULLABLE集合,FOLLOW集合,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2200字,纯文字阅读大概需要4分钟。
内容图文
闲来无事,就把龙书拿出来有看了看,把最近学的总结一下。
FIRST(X) 集合定义: 可从X推导得到的串的首符号的集合,其中X是任意文法符号。如果X=>······=>ε ,那么ε也在FIRST(X)中。(定义来自龙书)
算法伪代码(非准确版):
<span style="font-size:14px;">foreach(nonterminal N) FIRST(N) = {} while(some set is changing) foreach (production p: N->β1 … βn) if (β1== a …) FIRST(N)∪= {a} if (β1== M …) FIRST(N)∪= FIRST(M)</span>
NULLABLE集合的归纳定义:
1基本情况:
X ->ε
2归纳情况:
X -> Y1 … Yn
Y1, …, Yn 是n个非终结符,且都属于NULLABLE集
算法伪代码:
<span style="font-size:14px;"></span><pre name="code" class="cpp">NULLABLE = {}; while (NULLABLE is still changing) foreach (production p: X-> β) if (β== ε) NULLABLE ∪= {X} if (β== Y1 … Yn) if (Y1∈ NULLABLE && … && Yn ∈NULLABLE) NULLABLE ∪= {X}
这个很好理解吧。
我们先不急看FOLLOW集合,再看看先前FIRST的伪代码吧,这哥伪代码粗略一看,感觉是对的,可是一细想,如果说B1是非终结符,但是如果B1->ε成立的话,那么是否要往后考虑一下?答案是正确的,这时还要FIRST(X) U= FIRST(B2),如果B2->ε仍然成立的话,继续FIRST(X) U= FIRST(B3),,依次类推。
新的求FIRST集合伪代码:
foreach(nonterminal N) FIRST(N) = {} while(some set is changing) foreach (production p: N->β1 … βn) foreach (βi from β1 upto βn) if (βi== a …) FIRST(N) ∪= {a} break if (βi== M …) FIRST(N)∪= FIRST(M) if (M is not in NULLABLE) break
接下来就是FOLLOW集合了:
对于非终结符号X,FOLLOW(A) 被定义为可能在某些句型中紧跟在X右边的总结符号集合。(定义来自龙书)
举个例子:如果存在S=>aBcd(a,b,d是文法符号串),这样c就在FOLLOW(B)中。
FOLLOW集的不动点算法:
<span style="font-size:14px;">foreach(nonterminal N) FOLLOW(N) = {} while(some set is changing) foreach (production p: N->β1 … βn) temp = FOLLOW(N) foreach (βi from βn downto β1) // 逆序! if (βi== a …) temp = {a} if (βi== M …) FOLLOW(M)∪= temp if (M is not NULLABLE) temp = FIRST(M) else temp∪= FIRST(M) </span>
好的,完成了这一步,我们就可以得到任意串的FIRST集合,
如下伪代码:
foreach(production p) FIRST_S(p) = {} calculte_FIRST_S(production p: N->β1 … βn) foreach (βi from β1 to βn) if (βi== a …) FIRST_S(p)∪= {a} return; if (βi== M …) FIRST_S(p)∪= FIRST(M) if (M is not NULLABLE) return; FIRST_S(p)∪= FOLLOW(N)
好了,就总结到这里。
若有错误的地方,水平有限,还望指出。
谢谢
与君共勉
版权声明:本文为博主原创文章,未经博主允许不得转载。
原文:http://blog.csdn.net/lionel_d/article/details/47133321
内容总结
以上是互联网集市为您收集整理的编译器实践四 之 FIRST集合,NULLABLE集合,FOLLOW集合全部内容,希望文章能够帮你解决编译器实践四 之 FIRST集合,NULLABLE集合,FOLLOW集合所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。