LL(1)文法讲解之二 Follow集的计算.doc

《LL(1)文法讲解之二 Follow集的计算.doc》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、FOLLOW集的那些事儿一、学习FOLLOW集运算的重要性（男生必看）mm说：“我爱你。”他脸红了，他不想害她：“我没钱，更没有房子和车。”mm盯着他的眼睛：“我知道。”“我的月薪只有一千五。”mm的目光仍然坚定无比：“以后会多的。”他用颤抖的双手拿出一支烟叼在嘴上：“我每天要抽一包烟，一喝酒就闹事。”mm笑了，“以后有我在，你放心。”他的脊梁上冒起一阵寒意，结结巴巴地对她说：“其实……其实我很流氓……幼儿园就喜欢去女厕所，小学就没了初吻，中学就……”mm没等他说完就软在了他的怀里，声音细若蚊鸣：“早知道你好

2、色，你老偷偷瞄我…”他抱紧了mm，温热娇小的身体让他热血沸腾。这时他忽然想到了一件很重要的事情，他决定把这事告诉mm......五秒钟后mm抬头问他：“真的？”他决然地点点头。mm沉默片刻挣开他的怀抱抬手给了他一个耳光，她愤怒地朝他喊道：“你丫竟然不懂编译原理中的FOLLOW集！” 二、为什么需要FOLLOW集运算在开讲之前，吾先假设汝应该而且必须已经明白了FIRST集的作用—帮助编译器在语法分析时无回溯、敏捷高效、一键式地挑选用来替换某个非终结符的多个候选式中的一个。所以，FIRST集的思想对于建设一个和谐

3、的语法分析器是多么的重要啊！（摘自<万老师学编译>之“FIRST集,他好我也好，耶！”）但是科学的发展观告诉我们花无百日好，人无完人，FIRST集也有其自身的制约，那就是，对于包含ε的候选式不能用FIRST来说明何时用ε来替换。补充说明：在文法中，如果某个非终结符的候选式是ε，就说明该非终结符代表的语法成分在句子中是可选的（可有可无，不是必须得）。例如，如下的文法试图刻画一个最简单的C文法（蓝色标注的是终结符）：→<预处理><函数><预处理>→#include<<文件名>><函数>→void<标识符

4、>（）{}…………以上文法有个缺点：就是按其描述，我们所写的C程序中必须有<预处理>部分，但实际上预处理语句是可有可无的，所以我们这样改写以上文法：→<预处理><函数><预处理>→#include<<文件名>>

5、ε<函数>→void<标识符>（）{}…………这样，对于以上文法，如果我们只用每个候选式的FIRST集来指导语法分析器进行无回溯的语法分析就行不得也哥哥。举例说明如下：现在需要分析以下句子（实际上就是一个完整的C代码）是否符合文法：#includevoidmain(){}首

6、先，从非终结符开始替换，必然是用<预处理><函数块>来替换，因为我们没有其他选择所以说选择是人生最初的烦恼，呵呵，如果不需要选择，贾宝玉还是依红偎翠的翩翩少年郎。。。。。如果一个文法的每个非终结符都只有一个候选式该多好啊，作业会更容易，考试会更简单，天空会更蓝。但正如没有选择的人生是简单的，所以一个文法如果没有选择时的纠结也是简单的，描述能力是很弱的。。对于替换得到的句型<预处理><函数块>，按最左替换，我们下一步的任务是选择<预处理>的哪个候选式来替换？这时就是FIRST集的showti

7、me了，语法分析器会向这两个候选式的FIRST集求助,显然，因为候选式#include<<文件名>>的FIRST集包括当前要分析的句子的首单词#，所以我们选择候选式#include<<文件名>>去替换<预处理>，哈哈，soeasy。但是，如果我们要分析的是以下句子呢（缺预处理语句）？voidmain(){}首先，从非终结符开始替换，用<预处理><函数块>来替换，得到的句型<预处理><函数块>，按最左替换，我们下一步的任务是选择<预处理>的哪个候选式来替换？只有继续借助于FIRST集了。因为

8、候选式#include<<文件名>>的FIRST集是{#}，不包括当前要分析的句子的首符号；而候选式ε的FIRST集是{ε}，也不包括当前要分析的句子的首符号void，所以，voidmain(){}不是正确的句子。咦，貌似不对啊，明明我们可以这样替换的：将<预处理>替换为ε，这样我们得到句型<函数>，然后再将<函数>用候选式void<标识符>（）{}替换就能证明句子voidmain(){}是符合文法的。这说明对于候选式为ε的情况，其FIRST集{ε}无法帮助语法分析器挑选正确的替换候选式。所以，我们应该针对候

9、选式为ε的情况，特事特办。就本例来说，我们是否应该将<预处理>用其ε候选式进行替换，有两种办法：其一，因为<预处理>肯定不能用其#include<<文件名>>这条候选式进行替换，这是必死无疑的（因为这种替换只会得到以#起始的句子），所以我们姑且用ε候选式替换<预处理>，如果后续的推导得不到要分析的句子，则说明在这一步的替换也是不正确的，从而说明要分析的句子不正确。咦，这种方法怎么这么眼熟，kao，原