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

FOLLOW集的那些事儿 一、学习FOLLOW集运算的重要性（男生必看） mm说：“我爱你。”脸红了，不想害她：“我没钱，更没有房子和车。”mm盯着的眼睛：“我知道。”“我的月薪只有一千五。”mm的目光仍然坚定无比：“以后会多的。”用颤抖的双手拿出一支烟叼在嘴上：“我每天要抽一包烟，一喝酒就闹事。”mm笑了，“以后有我在，你放心。”的脊梁上冒起一阵寒意，结结巴巴地对她说：“其实……其实我很流氓……幼儿园就喜欢去女厕所，小学就没了初吻，中学就……”mm没等说完就软在了的怀里，声音细若蚊鸣：“早知道你好色，你老偷偷瞄我…”抱紧了mm，温热娇小的身体让热血沸腾。这时忽然想到了一件很重要的事情，决定把这事告诉mm......五秒钟后mm抬头问：“真的？”地点点头。mm沉默片刻挣开的怀抱抬手给了一个耳光，她愤怒地朝喊道：你丫竟然！”?FOLLOW集运算 在开讲之前，吾先假设汝应该而且必须已经明白了FIRST集的作用—帮助编译器在语法分析时无回溯、敏捷高效、一键式地挑选用来替换某个非终结符的多个候选式中的一个。 所以，FIRST集的思想对于建设一个和谐的语法分析器是多么的重要啊！（摘自万老师学编译之“FIRST集,他好我也好，耶！”） 但是科学的发展观告诉我们花无百日好，人无完人，FIRST集也有其自身的制约，那就是，对于包含ε的候选式不能用FIRST来说明何时用ε来替换。 补充说明：在文法中，如果某个非终结符的候选式是ε，就说明该非终结符代表的语法成分在句子中是可选的（可有可无，不是必须得）。例如，如下的文法试图刻画一个最简单的C文法（蓝色标注的是终结符）： C程序 →预处理 函数 预处理 → # include 文件名 函数→ void 标识符 （ ） { } ………… # include 文件名 | ε 函数→ void 标识符 （ ） { } ………… 这样，对于以上文法，如果我们只用每个候选式的FIRST集来指导语法分析器进行无回溯的语法分析就行不得也哥哥。举例说明如下： 现在需要分析以下句子（实际上就是一个完整的C代码）是否符合文法： # include stdio.h void main() { } 首先，从非终结符C程序开始替换，必然是用预处理 函数块来替换C程序，因为我们没有其他选择。对于替换得到的句型预处理 函数块，按最左替换，我们下一步的任务是选择预处理的哪个候选式来替换？这时就是FIRST集的show time了，语法分析器会向这两个候选式的FIRST集求助,显然，因为候选式 # include 文件名 的FIRST集包括当前要分析的句子的首单词#，所以我们选择候选式 # include 文件名 去替换预处理，哈哈，so easy。 但是，如果我们要分析的是以下句子呢（缺预处理语句）？ void main() { } 首先，从非终结符C程序开始替换，用预处理 函数块来替换C程序，得到的句型预处理 函数块，按最左替换，我们下一步的任务是选择预处理的哪个候选式来替换？只有继续借助于FIRST集了。因为候选式 # include 文件名 的FIRST集是{#}，不包括当前要分析的句子的首符号；而候选式ε的FIRST集是{ε}，也不包括当前要分析的句子的首符号void， 所以，void main() { } 不是正确的句子。咦，貌似不对啊，明明我们可以这样替换的：将预处理替换为ε，这样我们得到句型函数，然后再将函数用候选式void 标识符 （ ） { }替换就能证明句子void main() { }是符合文法的。 这说明对于候选式为ε的情况，其FIRST集{ε}无法帮助语法分析器挑选正确的替换候选式。所以，我们应该针对候选式为ε的情况，特事特办。 就本例来说，我们是否应该将预处理用其ε候选式进行替换，有两种办法： 其一，因为预处理肯定不能用其# include 文件名 这条候选式进行替换，这是必死无疑的（因为这种替换只会得到以#起始的句子），所以我们姑且用ε候选式替换预处理，如果后续的推导得不到要分析的句子，则说明在这一步的替换也是不正确的，从而说明要分析的句子不正确。咦，这种方法怎么这么眼熟，kao，原来不就是回溯嘛，穿了马甲就以为我们不认识了。不行不行，回溯效率太低，而且不能及时发现错误（就像长颈鹿要等水淹到脖子才知道踩到了水坑）。 其二，C程序经替换后成为句型：预处理 函数，按文法分析，如果要分析的句子void main() { }是正确的，则该句子的首单词void应该是预处理的某个候选式的FIRST集的，但是由于现在预处理可以被替换为ε，则句型：预处理 函数被替换为函数，这样，如果要分析