分类： 架构设计与优化
2016-08-02 15:08:30
笔者使用的是 刘坚编著的《编译原理基础（第二版）》2008年9月第2版 2012年5月第8次印刷的版本。
书P74页中
算法3.5 计算X的FIRST集合
输入：文法符号X。
输出：X的FIRST集合。
方法：应用下述规则，
（1）若X是终结符，则FIRST(X) = {X}。
（2）若X是非终结符且有X→ε，则加入ε到FIRST(X)中。
（3）若X是非终结符且有X→Y1Y2…Yk，并令Y0=ε，Yk+1=ε，则从左到右对所有j(0≤j≤k),若a∈FIRST(Yj+1)且ε∈FIRST(Yj),则加入a到FIRST(X)中。
以下为自己的一些想法，如有纰漏，还望指正！
首先，解释一下什么是FIRST集：
对于一个符号X最后转化为实例（只由终结符组成）时，这个实例的第一个字符（如果实例长度为0则用ε表示这个字符）的所有可能情况组成的集合称为X的FIRST集合，简称FIRST(X)。
对于算法3.5执行流程，我的理解是这样的：
规则（1）：对于终结符a，因为它的实例只有a一个，所以FIRST(a)必然是{a}。
规则（2）：对于非终结符A，存在文法 A→ε，那么A的实例为空，即长度为0所以用ε表示该实例的第一个字符，将ε加入到FIRST(A)中。
规则（3）：对于非终结符A，存在文法 A→BCDE，将该文法的右部看成εBCDEε，
①判断ε∈FIRST(ε)，如果符合的话则将FIRST(B)加入到FIRST(A)中；
②判断ε∈FIRST(B)，如果符合的话则将FIRST(C)加入到FIRST(A)中；
③判断ε∈FIRST(C)，如果符合的话则将FIRST(D)加入到FIRST(A)中；
④判断ε∈FIRST(E)，如果符合的话则将ε加入到FIRST(A)中。
对于规则（1）（2）较为容易理解，我也并没有什么可改进的。
对于规则（3）我的理解如下：
按照FIRST集的定义，对于文法A→BCDE，FIRST(A)是指A的所有实例第一个字符的集合，那么我们将BCDE转换为实例有两种可能：
1) B不为空时，这时符号A的第一个字符必然属于B不为空时的所有可能第一个字符的集合，即应该将 FIRST(B)-{ε} 加入 FIRST(A) ；
2) B为空时，这时文法A→BCDE就缩减成A→CDE，这个时候只需要重复上面的步骤即可。
那么我们需要考虑的问题是如下：
算法3.5 为什么要做
从左到右对所有j(0≤j≤k),若a∈FIRST(Yj+1)且ε∈FIRST(Yj),则加入a到FIRST(X)中
我们再看上面的算法执行流程：
①判断ε∈FIRST(ε)，如果符合的话则将FIRST(B)加入到FIRST(A)中；
②判断ε∈FIRST(B)，如果符合的话则将FIRST(C)加入到FIRST(A)中；
③判断ε∈FIRST(C)，如果符合的话则将FIRST(D)加入到FIRST(A)中；
④判断ε∈FIRST(E)，如果符合的话则将ε加入到FIRST(A)中。
~
在第一步做看似毫无意义的判断ε∈FIRST(ε)的原因是：符号B作为文法A→BCDE右部的第一个符号，必然需要将FIRST(B)加入到FIRST(A)中，所以判断本身并不重要，但做判断后能提高算法的统一性和表达的简洁性，如果单列出来，算法会显得过于冗长；
在后续步骤中，不断判断ε∈FIRST(B/C/D/E)的原因是：考虑到B/C/D/E有可能为空，则文法形式可能会不断缩减，极端的实例是BCDE都为空，则文法变成A→ε，所以在最后将ε加入FIRST(A)。
这么看来算法3.5好像没有什么问题，但我注意到：
推论：如果B绝对不为空，即文法A→BCDE绝对不会缩减成A→CDE，这时会怎么样？也就是说无论CDE是否可能为空，那么文法一定是A→B……，那么对于这个文法，FIRST(A)必然等于FIRST(B)。
那么按照这个设定（ε 不属于FIRST(B)，ε∈FIRST(C)），我们再看算法的执行过程
①判断ε∈FIRST(ε)，符合！将FIRST(B)加入到FIRST(A)中；
②判断ε∈FIRST(B)，不符合；
③判断ε∈FIRST(C)，符合！将FIRST(D)加入到FIRST(A)中；
这个时候FIRST(A)包含了FIRST(B)和FIRST(D)，但是按照我们推论，FIRST(A)必然等于FIRST(B)，而FIRST(B)和FIRST(D)之间的关系是不明确的，所以按照算法3.5得到的结果存在问题！
所以我认为该算法应该做一定修改，以下是我做出修改后的算法
算法3.5改 计算X的FIRST集合
输入：文法符号X。
输出：X的FIRST集合。
方法：应用下述规则，
（1）若X是终结符，则FIRST(X) = {X}。
（2）若X是非终结符且有X→ε，则加入ε到FIRST(X)中。
（3）若X是非终结符且有X→Y1Y2…Yk，对于j(1≤j≤k)，若ε∈FIRST(Yj)，则将到 FIRST(Yj)-{ε} 加入 FIRST(X)中，其中若j=k，则将ε加入 FIRST(X)中；否则，将FIRST(Yj)加入 FIRST(X)中，直接结束算法。
按照这个修改后的算法执行设定（ε?FIRST(B)，ε∈FIRST(C)）：
①判断ε∈FIRST(B)，不符合！将FIRST(B)加入到FIRST(A)中，结束算法；
这时FIRST(A)等于FIRST(B)，符合预期。
原创文章，转载请全文转载并注明出处
http://www.cnblogs.com/777777-716/p/5003960.html
| S→ABc |
| A→a|ε |
| B→b|ε |
| First集合求法: |
| 能 由非终结符号推出的所有的开头符号或可能的ε，但要求这个开头符号是终结符号。如此题A可以推导出a和ε，所以FIRST（A）=｛a，ε｝；同理 FIRST（B）={b,ε};S可以推导出aBc，还可以推导出bc，还可以推导出c，所以FIRST(S）=｛a，b，c｝ |
| Follow集合的求法: |
| 紧跟随其后面的终结符号或＃。但文法的识别符号包含＃，在求的时候还要考虑到ε。 具体做法是把所有包含你要求的符号的产生式都找出来，再看哪个有用。 Follow（S）=｛＃｝ |
| 如求A的，产生式：S→ABc A→a|ε ，但只有S→ABc 有用。跟随在A后年的终结符号是FIRST（B）=｛b，ε｝，当FIRST（B）的元素为ε时，跟随在A后的符号就是c，所以 Follow（A）=｛b，c｝ 同理Follow（B）=｛c｝ |
明天就考试了，在这里纠结这个问题。
一，要知道什么是终结符和非终结符。
终结符：通俗的说就是不能单独出现在推导式左边的符号，也就是说终结符不能再进行推导。
非终结符：不是终结符的都是非终结符。（非男即女，呵呵）
如：A——>B，则A是非终结符。
（一般书上终结符用小写，非终结符用大写。）
二，文法产生语言句子的基本思想：从识别符号（开始符）开始，把当前产生的符号串中的非终结符替换为相应规则右部的符号串，直到全部由终结符组成。
三，FIRST集求法
First集合最终是对产生式右部的字符串而言的，但其关键是求出非终结符的First集合，由于终结符的First集合就是它自己，所以求出非终结符的First集合后，就可很直观地得到每个字符串的First集合。
1. 直接收取：对形如U－>a…的产生式（其中a是终结符），把a收入到First(U)中
2. 反复传送：对形入U－>P…的产生式（其中P是非终结符），应把First(P)中的全部内容传送到First(U)中【意思就是只需要把第一个非终结符的First集传过去~这个地方是要注意的地方，也是难点】。
四，FOLLOW集的求法
Follow集合是针对非终结符而言的，Follow(U)所表达的是句型中非终结符U所有可能的后随终结符号的集合，特别地，“#”是识别符号的后随符。注意Follow集合是从开始符号S开始推导。
1. 直接收取：注意产生式右部的每一个形如“…Ua…”的组合，把a直接收入到Follow(U)中。因a是紧跟在U后的终结符。
2．直接收取：对形如“…UP…”(P是非终结符)的组合，把First(P)直接收入到Follow(U)中【在这里，如果First（P）中有空字符，那么就要把左部（假设是S）的Follow（S）送入到Follow（U）中。还有就是Follow集中是没有空字符的】。
3. 直接收取：若S－>…U，即以U结尾，则#∈Follow(U)
4．*反复传送：对形如U－>…P的产生式（其中P是非终结符），应把Follow(U)中的全部内容传送到Follow(P)中。
Ps：Follow集比First要复杂一点，不过记住算法多做练习就是小Case啦。
