读龙书学编译原理 语法分析(8)...

考试昨天下午就算考完了, SE考的好像不太理想啊, 概念多实践少的科目果然不适合我啊(复习的时候, 坚持不了5分钟就开始玩手机, 真是日了狗, 然后开始自责, 然后循环...) 唯一一个好消息是好像我dbi是年级最高分, 不过对于这种没什么技术含量的考试分的高低其实也没什么重要, 不挂科其实都还行吧... 自从昨天下午考完之后, 晚上也没什么兴趣去学习, 看了两部电影, 今天睡了个大觉, 下午吃了一波釜山烤肉, 晚上刚了一波日本烧烤 烧鸟... 经济状况很不理想啊, 不过偶尔吃吃改善一下生活质量还是挺好的... 上面的也算是一些闲话吧, 虽然说是说在写技术博客, 但有时候还是想当日记记一记的, 暑假其实从今天就算开始了, 那么以后更新的可能会比较频繁... 不过23号还要和毛里求斯的同学去上海玩一波, 毕竟下个学期去英国就碰不到他们了, 所以这可能是最后一次一起出去玩, 也算是对这一年来一起的一个总结吧... 暑假就目前来看有这么几件事 :

近一点的 : 1. 正则表达式的引擎(最简版本)

　　　　　2.六月的六级考试

远一点的 : 1. 弄完编译原理, 手动实现编译器... (如果不亲自实现, 那自学编译原理还有什么意义? 毕竟学习编译原理就是为了装逼嘛, 不能show me the code 怎么能叫装逼)

　　　　　2. 如果还有时间, 看看是学C++ 还是操作系统... 到时候再说吧.

好了, 进入正题... 上一节介绍了first集的求解算法, 这一节就讲讲follow集的求解算法 (follow集的作用在于提出更加严密的first集求解算法..)

这个算法的关键在于, 他是逆序的, 也就是从推导式的最后一个符号(终结符或者是非终结符)往前推, 如果是可空的, 那么之前的temp可以传递下去, 也就是说之前一个非终结符的follow集合也可以作为下一个非终结符的follow集合(因为当前非终结符可以为空)...

最后就是first集合的严密算法, 好好感受一下大自然的力量 - .-, 可以看出这个算法不是针对某个非终结符来求解的, 而是针对具体的某一条推导式来求解的, 因为从生产分析表的角度上看, 实际上同一个非终结符的不同推导式必须要对应不相交的fisrt集合(因为如果first集合相交了, 也就是给定某个非终结符然后给定你读入的下一个token, 结果发现有两条推导式可以选择, 产生冲突显然是ll(1)不允许的), 所以我们生产表的时候应该是根据产生式的不同, 比如此时是产生式1,  产生式左部的非终结符是S, 右侧的first集合是a, 我们就可写table[S][a] = 1; 而如果不限定某条产生式那么我们如何知道此时table[S][a]应该对应什么呢 ?

所以总结起来ll(1)算法的总过程就是 :

1. 算出所有元素的first集合, follow集合, nullable与否...

2. 根据上面的结果对于每一条推导式计算first_s然后得出分析表...

原文：http://www.cnblogs.com/nzhl/p/5515973.html