相信我每个学编译原理的人都曾在FIRST集和FOLLOW集面前怀疑过人生。教材先抛给你一长串形式化定义再配一个“请计算下列文法的FIRST与FOLLOW”的例题然后你盯着草稿纸完全不知道第一步该写什么。尤其当文法里出现E、T这种带撇的符号再加一个ε空产生式整个人就懵了。这篇文章我打算用最直白的方式把FIRST集和FOLLOW集讲透。不管你是期末备考、正在做语法分析实验还是准备面试被问到LL(1)分析这篇文章都能帮你把这块骨头啃下来。我会从“为什么要算这两个集合”开始到手算规则、完整例题、预测分析表最后再给一个可以直接跑通的Java求解器代码。看完之后再遇到类似题目你应该可以闭着眼睛算出来。1. FIRST集和FOLLOW集到底在解决什么问题1.1 语法分析器的工作方式先说一个很多人混淆的点词法分析和语法分析是两回事。词法分析负责把源代码字符串拆成一个个token比如关键字、标识符、运算符语法分析则是在token流之上判断这些token能不能按照文法规则组成合法的句子。你做的“词法分析实验”一般是写状态机识别关键字这和FIRST/FOLLOW没关系。但如果你做的是递归下降或表驱动的语法分析FIRST和FOLLOW就是绕不开的基础工具。语法分析常用的方法分两类自顶向下和自底向上。LL(1)分析是自顶向下分析的典型代表它的核心思路是从开始符号出发不断选择产生式把非终结符展开直到整个输入串都被匹配掉。问题来了——当某个非终结符对应多条产生式时到底选哪一条FIRST集和FOLLOW集就是用来回答这个问题的。1.2 没有FIRST/FOLLOW会怎样举个直观的例子。文法里有两条产生式S - if E then S S - while E do S现在语法分析器读到了一个if它当然知道该选第一条。但如果两个候选式都以同一个终结符开头呢比如E - T E - T E两条产生式都能以T开头分析器一看当前输入是id根本分不清该展开成T还是T E。这种冲突如果不消除自顶向下分析就没法做。FIRST集能帮你回答“这条产生式展开后第一个可能出现的终结符是什么”而FOLLOW集能回答“当某个非终结符可以被替换成空串时它后面可能跟着什么终结符”。有了这两个信息分析器就相当于拿到了一张路线图走到每个路口都知道该往哪拐。1.3 一个不太严谨但很好用的类比你可以把FIRST集理解为路牌上写的“这条路往前走会遇到哪些站牌”。比如F - ( E )路牌上写着(和id那FIRST(F)就是{ (, id }。FOLLOW集更像是“你从这条路出去之后下一个路口可能遇到什么”。比如F如果在T - * F T这个产生式里出现那F后面紧跟一个*所以*要进FOLLOW(F)。如果后面跟着的符号串能推导出空串那还得再把“这条路尽头之后可能遇到什么”继续传过来。记住这两个直觉后面看定义就轻松多了。2. FIRST集的定义、求解规则与手算实战2.1 FIRST集的定义与三条求解规则正式定义是这样的对任意文法符号串αFIRST(α)是α经过任意步推导后可能出现在串首的所有终结符的集合。如果α能推导出空串那么ε也在FIRST(α)中。这个定义一长串翻译成人话就是你把一条产生式右侧看成一个句子这个句子将来被展开后第一个字可能是什么把这些可能的“字”收集起来就是FIRST集。如果这个句子有可能整句消失也就是推导成空串那ε也要算进去。求解FIRST集只需要记住三条规则规则一如果产生式形如A - aα其中a是终结符那么直接把a加入FIRST(A)。规则二如果产生式形如A - Bα其中B是非终结符那么把FIRST(B)去掉ε后整个加入FIRST(A)如果B能推导出ε继续处理α直到遇到一个不能推导出ε的符号为止。规则三如果产生式形如A - ε直接把ε加入FIRST(A)。规则二最容易被忽略。它强调的是“传播”要一层层来B能推空才轮到看αB不能推空α就不用看了。很多人算错就是把FIRST(B)整个拿过来用连ε也带上了还硬把后面符号的FIRST也塞进去这就全乱了。2.2 手算案例经典表达式文法我拿教材里出现频率最高的表达式文法来演示。先看文法1. E - T E 2. E - T E | ε 3. T - F T 4. T - * F T | ε 5. F - ( E ) | id字母E、T、F是表达式、项、因子三个层次的意思带撇的是它们后面的尾巴。整个文法描述了id id * id这类算术表达式的结构。第一步先把所有非终结符列出来E、E、T、T、F。终结符有、*、(、)、id。从最简单的开始算。先算F。第5条产生式说F - ( E )右侧第一个符号是(终结符直接加入FIRST(F)F - id右侧第一个符号是id也加入。所以FIRST(F) { (, id }再算T。第4条产生式T - * F T右侧第一个符号*是终结符加入另外T - ε按照规则三把ε加入。所以FIRST(T) { *, ε }接着算E。第2条产生式E - T E右侧第一个符号是终结符加入还有E - ε加入ε。所以FIRST(E) { , ε }然后算T。第3条产生式T - F T右侧第一个符号是F非终结符。把FIRST(F)去掉ε后加进来也就是(, id。那要不要继续看T要看F能不能推导出ε。这里FIRST(F)没有εF不能推空所以T就不用看了。于是FIRST(T) { (, id }最后算E。第1条产生式E - T E右侧第一个符号是T把FIRST(T)去掉ε后加进来还是(, id。因为T不能推空E不用看。所以FIRST(E) { (, id }到这里FIRST集全部算完。注意E和T以及F的FIRST一样这在表达式文法里很常见因为E归根到底要展开成TT归根到底要展开成F而F只以终结符开头。2.3 FIRST集手算时的三个易错信号手算FIRST集最容易出错的点有三个。第一个是ε被误传播。比如你算T - F TF的FIRST是{(, id}没有ε那T的*就千万不能进FIRST(T)。很多同学算到一半习惯性把右侧所有符号的FIRST都并起来结果把*也塞进去了这就是典型的“传播过度”。第二个是ε被漏掉。只要文法里有A - εε就必须出现在FIRST(A)里。漏掉ε的后果很严重因为后面判断“能否推空”全靠这个标记。第三个是分不清“FIRST(A)”和“FIRST(α)”。FIRST(A)是单个非终结符的FIRST(α)是符号串的。考试经常先让你求FIRST(A)再让你求FIRST(T E)这种符号串的FIRST。求FIRST(T E)要先把FIRST(T)去掉ε拿过来再看T能否推空如果能还要继续看E。做题时一定要看清题目问的是单个符号还是符号串。3. FOLLOW集的定义、求解规则与手算实战3.1 FOLLOW集的定义与三条求解规则FOLLOW集的定义对某个非终结符AFOLLOW(A)是“在推导过程中紧跟A之后可能出现的终结符集合”。如果A是文法开始符号通常把结束标记$或#也放进FOLLOW(A)。定义里有两个关键点。第一FOLLOW集只针对非终结符不存在“FOLLOW(α)”这种说法。第二FOLLOW集中永远不会出现ε因为“A后面跟一个空串”这个说法没有意义我们说“A后面没东西”时用的是结束标记$来表示。求解FOLLOW集同样三条规则规则一如果A是开始符号把$加入FOLLOW(A)。规则二对于产生式A - αBβ把FIRST(β)去掉ε之后的所有终结符加入FOLLOW(B)。规则三对于产生式A - αB也就是B在产生式末尾或者A - αBβ且β能推导出ε此时把FOLLOW(A)整个加入FOLLOW(B)。规则三是最难理解的。为什么B在末尾要把左部的FOLLOW传给B因为A后面能跟什么B作为A展开的最后一个部分它后面同样能跟什么。如果β能推空其实就等价于B后面跟了一个“看不见的ε”那B还是要看A后面的终结符。3.2 手算案例表达式的FOLLOW怎么一步步出来还用刚才那个表达式文法。1. E - T E 2. E - T E | ε 3. T - F T 4. T - * F T | ε 5. F - ( E ) | id先把所有FOLLOW集合初始化为空。然后规则一E是开始符号FOLLOW(E)里加入$。接下来开始扫描每一条产生式。扫描第5条F - ( E )。右侧括号里是EE后面紧跟)所以)加入FOLLOW(E)。目前FOLLOW(E) { $, ) }扫描第1条E - T E。右侧第一个非终结符是TT后面是E。把FIRST(E)去掉ε后加入FOLLOW(T)。FIRST(E) {, ε}去掉ε剩{}所以加入FOLLOW(T)。再看E能不能推空能它有E - ε。根据规则三FOLLOW(E)要整个传给FOLLOW(T)。FOLLOW(E)现在是{$, )}也加入FOLLOW(T)。所以FOLLOW(T) { , $, ) }接着看第1条产生式的末尾E在末尾根据规则三FOLLOW(E)要传给FOLLOW(E)。于是FOLLOW(E) { $, ) }扫描第2条E - T E。T后面跟的是E把FIRST(E)去掉ε加入FOLLOW(T)还是{}E能推空所以FOLLOW(E)也传给FOLLOW(T)FOLLOW(E)现在是{$, )}。因此FOLLOW(T)仍然是{, $, )}没有新东西。这条产生式末尾的E也要继承左部FOLLOW(E)但FOLLOW(E)里已经是{$, )}了所以无变化。扫描第3条T - F T。F后面跟TFIRST(T) {*, ε}去掉ε后*加入FOLLOW(F)。T能推空所以FOLLOW(T)传给FOLLOW(F)。FOLLOW(T)现在是{, $, )}加入FOLLOW(F)。因此FOLLOW(F) { *, , $, ) }再看第3条产生式末尾的T继承左部FOLLOW(T)得到FOLLOW(T) { , $, ) }扫描第4条T - * F T。F后面跟TFIRST(T)去掉ε后*加入FOLLOW(F)T能推空FOLLOW(T)传给FOLLOW(F)FOLLOW(T)是{, $, )}。FOLLOW(F)还是{*, , $, )}没新东西。末尾T继承左部FOLLOW(T)也无变化。到这里一轮扫完得到的结果FOLLOW(E) { $, ) } FOLLOW(E) { $, ) } FOLLOW(T) { , $, ) } FOLLOW(T) { , $, ) } FOLLOW(F) { *, , $, ) }实际做题时至少要完整扫两遍因为第一轮产生的FOLLOW值可能影响第二轮。比如FOLLOW(E)一开始只有$如果第一轮就把FOLLOW(E)传给FOLLOW(T)了那一开始FOLLOW(T)可能缺)。要再扫一轮)才会传到FOLLOW(T)。所以建议扫到“一整轮没有任何变化”为止。3.3 进阶案例全员可空的文法如何求解再看一个极端案例能帮你把FOLLOW的“可空传递”这一关彻底打通。文法如下S - A B C A - a | ε B - b | ε C - c | ε这个文法里A、B、C都能推空S是开始符号。先算FIRST。FIRST(A) {a, ε}FIRST(B) {b, ε}FIRST(C) {c, ε}。S的FIRST要小心S - A B CA能推空所以看BB能推空再看CC能推空于是整个右侧可以推空所以FIRST(S) {a, b, c, ε}。再看FOLLOW。S是开始符号FOLLOW(S) {$}。扫描S - A B C。A后面跟B CB C的FIRST是{b, c, ε}去掉ε后{b, c}加入FOLLOW(A)。因为B C能推空FOLLOW(S)也要传给FOLLOW(A)。所以FOLLOW(A) { b, c, $ }B后面跟CC的FIRST是{c, ε}去掉ε后{c}加入FOLLOW(B)。C能推空FOLLOW(S)传给FOLLOW(B)。所以FOLLOW(B) { c, $ }C在末尾FOLLOW(S)传给FOLLOW(C)。所以FOLLOW(C) { $ }这个例子非常清晰地展示了什么叫“可空链式传递”。A后面本来只跟B C但由于B C都可能消失A后面就变得和S后面一样什么都能出现。面试时如果能把这个例子讲明白基本就能证明你是真的懂FOLLOW而不是背了三条规则。4. 从FIRST/FOLLOW到预测分析表4.1 预测分析表FIRST和FOLLOW的最终归宿算完FIRST和FOLLOW如果不把它们用起来总觉得像在空转。它们最经典的应用就是构造LL(1)预测分析表。预测分析表的结构是行对应非终结符列对应终结符包括结束符$。表格中每个单元放一条产生式表示“当栈顶是这个非终结符、当前输入是这个终结符时应该用哪条产生式展开”。填表规则有两条对于产生式A - α对FIRST(α)中的每个终结符a在表格M[A, a]位置填入这条产生式。特别地如果FIRST(α)中包含ε则对FOLLOW(A)中的每个终结符b在M[A, b]位置填入这条产生式。如果FOLLOW(A)中有$在M[A, $]位置也填入。第一条规则很好理解展开α开头可能出现的符号就用它来索引。第二条规则是关键当产生式能推空时FIRST里只有ε没法凭“开头符号”选只能看A后面允许跟什么终结符也就是FOLLOW(A)。拿表达式文法来填表。E - T E这一个产生式FIRST(T E) FIRST(T) {(, id}所以M[E, (]和M[E, id]都填E - T E。E - T EFIRST( T E) {}所以M[E, ]填这条。E - εFIRST(ε) {ε}看FOLLOW(E) {$, )}所以M[E, $]和M[E, )]都填E - ε。把所有产生式都填完就得到下面这张表非终结符id*()$EE - T EE - T EEE - T EE - εE - εTT - F TT - F TTT - εT - * F TT - εT - εFF - idF - ( E )注意看E这一行遇到用它自己的产生式遇到)和$就推空。这就是FOLLOW集在表里的直接作用。4.2 表驱动的LL(1)分析怎么跑填完表之后整个分析过程就是机械操作了。准备一个栈初始化时把$和开始符号E压入栈。再看当前输入符号和栈顶做匹配如果栈顶是终结符且和当前输入相同弹出栈顶输入指针后移。如果栈顶是非终结符X查表M[X, 当前输入]如果表项是一条产生式X - Y1 Y2 ... Yk把X弹出再把Yk ... Y2 Y1逆序压入栈。如果栈顶是$且当前输入也是$分析成功。比如输入id id * id一开始栈里是$E当前输入id。查表M[E, id]得到E - T E就把E弹出压入E、T顺序是逆序压栈顶变成T。然后继续查表M[T, id]得到T - F T继续展开。整个过程就是不断“查表、展开、匹配”不需要任何回溯效率非常高。这也是LL(1)分析器被称为“预测分析器”的原因——它预测的是下一步该用哪条产生式。4.3 LL(1)文法的判断标准如果填预测分析表时发现某个格子只有一个产生式这个文法就是LL(1)的吗不完全是但如果某个格子出现了两个或更多产生式那这个文法一定不是LL(1)。判断LL(1)文法的常用条件是这样对文法中每个非终结符A的任意两条产生式A - α和A - β必须满足FIRST(α)和FIRST(β)不相交。如果β能推导出ε那么FIRST(α)和FOLLOW(A)也不相交。第二条其实就是“ε产生式冲突条件”。举个冲突例子S - a A A - b | ε这里FIRST(b) {b}FIRST(ε) {ε}两者不相交。但A能推空就要看FIRST(b)和FOLLOW(A)是否相交。FOLLOW(A)包含$FIRST(b)是{b}不相交所以这个文法是LL(1)。如果改成S - a A A - a | εFOLLOW(A)里可能就有a那就和FIRST(A)中的a冲突了表里M[A, a]会出现两个产生式不是LL(1)。实际做题时不需要背定理直接填表看冲突比背条件快得多。5. 用Java手写一个FIRST/FOLLOW求解器5.1 为什么推荐写代码验证纸上算完再用代码跑一遍特别能检验自己有没有理解透。我第一次手算的时候总觉得“扫两遍肯定够了吧”结果遇到一个带间接递归的文法好几轮都在变。写成代码用“直到一轮结束集合不再变化”的循环来做才彻底明白教材里的“不动点算法”到底在说什么。我把求解器用Java写了出来。代码的结构很直观先读入文法再迭代计算FIRST然后迭代计算FOLLOW最后打印结果。为了让你直接对比手算结果我用的是前面那个表达式文法。5.2 Java实现的数据结构与核心算法整个求解器用到几个核心数据结构productionsMap键是非终结符值是该非终结符的所有产生式右部列表。nonTerminals产生式左侧符号的集合。terminals所有右侧符号中去掉非终结符和ε后的集合。first和follow两个Map键是非终结符值是对应的FIRST/FOLLOW集合。核心算法就是两段while循环每轮扫描所有产生式如果某个集合增加了元素就再扫一轮直到没有任何变化。这种方法叫“不动点迭代”优点是代码逻辑和教材算法几乎一一对应缺点是效率不是最高但文法规模小完全够用。计算FIRST时对每条产生式的右侧符号从左到右处理遇到终结符就加入遇到非终结符就把它FIRST去掉ε后加入并判断它能否推空如果能就继续看下一个符号否则停止。整条右侧都能推空时ε才加入。计算FOLLOW时扫描每条产生式右侧的每个非终结符。看它后面跟着的符号串的FIRST把去掉ε的终结符加进它的FOLLOW。如果后面的符号串能推空或者它就在产生式末尾把左部非终结符的FOLLOW也加进来。5.3 完整代码与运行结果以下是完整的Java代码直接复制就能跑。import java.util.*; public class FirstFollow { static final String EPSILON ε; static final String END $; static MapString, ListListString productions new LinkedHashMap(); static SetString nonTerminals new LinkedHashSet(); static SetString terminals new LinkedHashSet(); static MapString, SetString first new HashMap(); static MapString, SetString follow new HashMap(); public static void main(String[] args) { String[] grammar { E - T E, E - T E | ε, T - F T, T - * F T | ε, F - ( E ) | id }; // 1. 解析文法收集非终结符和终结符 for (String rule : grammar) { String[] parts rule.split( - ); String left parts[0].trim(); nonTerminals.add(left); productions.put(left, new ArrayList()); for (String alt : parts[1].split(\\|)) { String[] symbols alt.trim().split(\\s); productions.get(left).add(new ArrayList(Arrays.asList(symbols))); } } for (String A : nonTerminals) { for (ListString right : productions.get(A)) { for (String sym : right) { if (!nonTerminals.contains(sym) !sym.equals(EPSILON)) { terminals.add(sym); } } } } // 2. 初始化 FIRST、FOLLOW for (String A : nonTerminals) { first.put(A, new HashSet()); follow.put(A, new HashSet()); } String start grammar[0].split( - )[0].trim(); follow.get(start).add(END); // 开始符号的 FOLLOW 加结束符 // 3. 迭代计算 FIRST boolean changed true; while (changed) { changed false; for (String A : productions.keySet()) { for (ListString right : productions.get(A)) { int oldSize first.get(A).size(); boolean allNullable true; for (String sym : right) { if (sym.equals(EPSILON)) { // A - ε break; } if (!nonTerminals.contains(sym)) { // 终结符 first.get(A).add(sym); allNullable false; break; } else { // 非终结符 SetString fs new HashSet(first.get(sym)); fs.remove(EPSILON); first.get(A).addAll(fs); if (!first.get(sym).contains(EPSILON)) { allNullable false; break; } } } if (allNullable) { first.get(A).add(EPSILON); } if (first.get(A).size() ! oldSize) { changed true; } } } } // 4. 迭代计算 FOLLOW changed true; while (changed) { changed false; for (String A : productions.keySet()) { for (ListString right : productions.get(A)) { for (int i 0; i right.size(); i) { String B right.get(i); if (!nonTerminals.contains(B)) { continue; // 只处理非终结符 } SetString firstBeta firstOfSequence( new ArrayList(right.subList(i 1, right.size()))); int oldSize follow.get(B).size(); SetString toAdd new HashSet(firstBeta); toAdd.remove(EPSILON); follow.get(B).addAll(toAdd); if (firstBeta.contains(EPSILON) || i right.size() - 1) { follow.get(B).addAll(follow.get(A)); } if (follow.get(B).size() ! oldSize) { changed true; } } } } } // 5. 输出结果 for (String A : nonTerminals) { System.out.println(FIRST( A ) first.get(A)); } System.out.println(); for (String A : nonTerminals) { System.out.println(FOLLOW( A ) follow.get(A)); } } // 计算符号串的 FIRST 集合 static SetString firstOfSequence(ListString symbols) { SetString result new HashSet(); boolean allNullable true; for (String sym : symbols) { if (!nonTerminals.contains(sym)) { // 终结符 result.add(sym); allNullable false; break; } else { SetString fs new HashSet(first.get(sym)); fs.remove(EPSILON); result.addAll(fs); if (!first.get(sym).contains(EPSILON)) { allNullable false; break; } } } if (allNullable) { result.add(EPSILON); } return result; } }运行这段代码输出结果如下FIRST(E) [(, id] FIRST(E) [, ε] FIRST(T) [(, id] FIRST(T) [*, ε] FIRST(F) [(, id] FOLLOW(E) [$, )] FOLLOW(E) [$, )] FOLLOW(T) [$, , )] FOLLOW(T) [$, , )] FOLLOW(F) [$, *, , )]和前面手算的结果完全一致。我建议你在自己机器上跑一遍然后把代码里的文法换成课上作业那道题看输出和自己手算是否一致。如果对不上多半是某个能推空的非终结符没识别出来或者FOLLOW回合太少。一个小提示代码里split( - )是按“空格-大于号-空格”分割所以文法输入时符号之间必须用空格隔开比如T - * F T不能写成T-*FT。这是为了减少解析复杂度方便你把精力放在核心算法上。6. 考试和面试里最常见的坑以及怎么避开6.1 作业和考试中最容易失分的五个点每年期末都有大量学生在FIRST/FOLLOW上丢分丢分点基本集中在下面这五类。第一FOLLOW里出现ε。这是最典型的错误。有人会写FOLLOW(E) {$, ), ε}这是不对的。FOLLOW集定义的是“后面跟的终结符”空串不是终结符永远不能出现在FOLLOW里。如果算出来FOLLOW里有ε说明你把某个FIRST集合整个复制过来了没有去掉ε。第二FIRST里漏掉ε。文法里只要存在A - εε就必须进FIRST(A)。有些同学看A还有别的产生式比如A - a | ε就给FIRST(A)写了{a}把ε忘了。这样后面判断可空性时整个分析表都会错。第三FIRST过度传播。还是T - F T这种情况F不能推空却把T的FIRST也拿过来了。判断依据很简单当前符号能推空才继续看下一个不能推空立刻停止。第四FOLLOW没有处理“可空后继”。比如A - αBβ中β能推空FOLLOW(A)必须传给FOLLOW(B)。很多人只加了FIRST(β)却没有把左部FOLLOW传过来导致FOLLOW集合不完整。第五构造预测分析表时把ε产生式放错列。A - ε应该按FOLLOW(A)去填表而不是在FIRST(A)里找列。你想想FIRST(ε) {ε}表格里根本没有ε这一列不看FOLLOW还能看谁为了方便你考前自查我整理了一份速查表错误类型错误示例正确做法FOLLOW里出现εFOLLOW(E) {$, ), ε}FOLLOW集永远不含εFIRST漏掉εFIRST(A) {a}实际有A - ε有ε产生式就必须加εFIRST传播过度FIRST(T) {(, id, *}当前符号不能推空就停止忘记可空后继没把FOLLOW(A)传给FOLLOW(B)β可空时必须传预测分析表ε放错列把ε产生式填在M[A, ε]按FOLLOW(A)填在对应终结符列6.2 面试高频考点一览面试题一般不会让你真的去算一大张文法但会通过概念题考察你是否真的理解这两个集合。最常见的问题是“FIRST集和FOLLOW集分别解决什么问题”。你可以这样答FIRST集回答“一个产生式展开后可能以哪些终结符开头”用来在多个候选式中做选择FOLLOW集回答“一个非终结符后面可能跟着哪些终结符”专门用来处理能推导出ε的产生式选择问题。两者合起来构成LL(1)分析中“仅凭当前输入符号就能确定产生式”的决策依据。第二个高频问题是“为什么左递归文法不是LL(1)”。你可以说对于A - Aα | β这种文法FIRST(Aα)和FIRST(β)一定相交因为FIRST(Aα)包含FIRST(β)填预测分析表时必然冲突。所以做LL(1)分析前必须先消除左递归。第三个问题是“LL(1)的缩写各代表什么”。L表示从左到右扫描输入第二个L表示产生最左推导1表示每一步只需向前看1个输入符号。FIRST和FOLLOW就是用来支撑这个“1”的核心工具。第四个问题是“如何判断一个文法是不是LL(1)”。最稳妥的回答是计算出FIRST/FOLLOW后构造预测分析表如果表中每个单元格至多有一个产生式就是LL(1)。如果想从定义上证明就检查同一非终结符的所有候选式FIRST两两不相交如果某个候选式能推空还要保证该候选式的FIRST和该非终结符的FOLLOW不相交。7. 写在最后一些实战建议和延伸方向7.1 手算建议考试手算时我习惯准备一张白纸把非终结符列成表格一边是一列FIRST一边是一列FOLLOW。算FIRST时按产生式序号一条条过每过一轮在表格下面画一条横线再扫第二轮直到没有变化。算FOLLOW时重点圈出所有带ε的产生式。因为它们一旦出现就意味着“可空传递”可能发生FOLLOW的内容会被左部FOLLOW影响。扫描时每遇到一个形如A - αBβ的式子先看β的FIRST再看β能不能推导出ε两件事都要做。还有一个习惯帮我避免了很多低级错误每算完一步用“是否含ε”来检验一下。比如FIRST(T)里有ε说明T可空那么所有右侧包含T的产生式都要考虑“T消失”的情况。这个检验逻辑贯穿整个FOLLOW计算。7.2 学完FIRST/FOLLOW之后建议继续深挖什么如果你学到这里还意犹未尽或者面试想进一步展示深度我建议把这三件事搞明白。先看递归下降分析和表驱动分析的等价性。递归下降分析本质上是手写版的预测分析每个非终结符对应一个函数函数内部根据当前输入符号决定调用哪个非终结符的函数。你理解了FIRST/FOLLOW后再回头写递归下降对“为什么这里要判断if (lookahead )”这种代码会有豁然开朗的感觉。再看自底向上分析里的LR(1)和LALR(1)。FIRST/FOLLOW在LR分析中甚至衍生出FIRST_S和LA集合这类更复杂的概念。你会发现LL和LR虽然分析方向相反但底层对“前瞻符号”的依赖是相似的。理解了FIRST/FOLLOW再学LR会轻松不少。最后可以研究一下错误恢复机制。预测分析表填完之后如果输入串不合法分析器应该怎么报错很多教材会讲“恐慌模式”按照FOLLOW集合来跳过输入中的错误符号。也就是说FOLLOW集合不光能帮你做正确分析还能帮你从错误中恢复。这一步算是把这两个集合的价值榨干净了。我个人体会是FIRST/FOLLOW是编译原理里少有的“投入产出比很高”的知识点。花半小时彻底弄懂手算方法再花半小时把代码跑通之后无论是考试、课设还是面试题里遇到LL(1)你都会很从容。如果你正在准备期中或期末建议一定亲手把表达式文法从头到尾算三遍再拿一道自己文法的题练一遍。算到不再需要翻定义的时候你就算真正拿下这块内容了。