企业官网建设流程全解析

简介：面向山东科技大学编译原理课程的 LL(1) 语法分析实验资料，适合正在完成递归下降或预测分析作业的本科生参考。资源以 C++ 源码与完整实验报告为核心，在 Code::Blocks 中可直接编译运行；对应题目要求对 E→TG、G→+TG|-TG|ε、T→FM、M→*FM|/FM|ε、F→(E)|i 文法构造 LL(1) 分析器，覆盖 FIRST/FOLLOW 集计算、预测分析表生成和输入符号串识别等关键步骤。压缩包整体约 1.08MB，文件数量与类型明细未在页面中列出，但核心内容便于直接对照实验要求使用。目前已有 914 人学习下载，说明其对同类编译原理实验具有一定参考价值。通过源码可逐步跟踪 LL(1) 判定流程，配套报告则能帮助理解语法分析原理与实验步骤，适合课程设计或期末复习时备查。

1. 把LL(1)分析器当实验做，到底在训练什么

LL(1)分析法是语法分析阶段最经典的自上而下方法，山东科技大学2022年编译原理实验把它作为“语法分析”专题的必做题目，目的不是让你背出一张预测分析表，而是逼你在一周内把“文法→FIRST/FOLLOW→预测分析表→表驱动分析器”这条链路完整地走通。这套流程做完，你对自顶向下分析的认知会从“看得懂课件”变成“能随手写出一个能跑的分析器”。适合做这个实验的人有两类：一类是正在学编译原理、想把原理课上的公式变成可运行程序的学生；另一类是工作中需要手写小型解析器、但不想直接上yacc/ANTLR的开发者。接下来按实验从零到一的路子来，每一步都给出可以抄的代码和参数，最后把那些让程序莫名翻车的细节一并讲清楚。

2. 动手前先做文法手术：消除左递归与提取左公因子

“LL(1)”这个名字本身就交代了它的约束：从左到右扫描输入，推导时始终选择最左非终结符，每一步只向前看1个输入符号来做决定。这意味着当分析器站在某个非终结符A面前时，它只能根据当前的1个输入符号，从A的所有产生式里挑一条执行。如果文法在A上有两个产生式都以同一个终结符开头，或者更糟的是存在左递归，分析器要么陷入无限循环，要么根本不知道该选谁。所以在写任何代码之前，先把文法改造成LL(1)可处理的形式，这一步不做，后面的FIRST/FOLLOW和建表全是白费。

2.1 为什么LL(1)对文法这么挑剔

先看左递归。假设文法里有E→E+T这一条，分析器要推导E时，按规则先展开最左的E，结果产生式右边第一个符号还是E，于是又开始推导E，永远在原地打转。理论上讲，只要产生式右边第一个非终结符和左边相同，就会造成“无限推导”，这就是直接左递归。还有一种间接左递归，比如A→B，B→A这种两跳以上的循环，同样致命。LL(1)使用最左推导，等于要求每一步都能用当前输入符号做“唯一决策”，左递归让决策永远做不出来。

左公因子的问题不一样。A→αβ1和A→αβ2两条产生式的前缀完全相同，当输入符号是FIRST(α)里的某个终结符时，分析器不知道应该选β1还是β2。这不至于死循环，但会让预测分析表在M[A,a]的位置产生两个条目，也就是冲突，文法因此被判定为非LL(1)。所以“消左递归、提左公因子”是LL(1)分析器实现里的前置手术，手术后还要重新验证文法仍然接受原来的语言——变换不能改变语言本身，只改变推导方式。比如，下面这段Java代码用来检测一个文法是否存在直接或间接左递归，我在实验里通常先把文法读进来，跑一遍这个检查再决定要不要做变换：

// 检测文法是否存在左递归，返回true表示存在 // grammar: key=非终结符, value=该非终结符的所有产生式右部（按空格分词） boolean hasLeftRecursion(Map<String, List<String>> grammar) { for (String nonTerminal : grammar.keySet()) { // 记录从当前非终结符出发能到达的非终结符 Set<String> reachable = new HashSet<>(); Queue<String> queue = new LinkedList<>(); // 把所有右部第一个符号（非终结符）当作入口 for (String production : grammar.get(nonTerminal)) { String firstSymbol = production.split(" ")[0]; if (grammar.containsKey(firstSymbol)) { if (firstSymbol.equals(nonTerminal)) return true; // 直接左递归 if (reachable.add(firstSymbol)) queue.offer(firstSymbol); } } // BFS 扩展：沿着右部第一个符号继续找 while (!queue.isEmpty()) { String symbol = queue.poll(); if (symbol.equals(nonTerminal)) return true; for (String production : grammar.getOrDefault(symbol, Collections.emptyList())) { String firstSymbol = production.split(" ")[0]; if (grammar.containsKey(firstSymbol) && reachable.add(firstSymbol)) { queue.offer(firstSymbol); } } } } return false; }

这里把产生式右部按空格拆开取第一个符号，如果它是非终结符，就沿着它继续寻路。每次扩展都判断是否回到了起点自身，一旦回到自身就说明存在左递归。参数grammar的key集合必须是全部非终结符，value里每个产生式的右部要保证第一个符号能被提取出来。注意这里只检查了第一个符号，因为左递归的定义就是右部第一个符号能推导回自身，如果第一个符号是终结符，这条产生式一定安全。

2.2 消除直接左递归：从E→E+T到E→TE′

直接左递归的通用消除公式不复杂。假设A→Aα1|Aα2|...|Aαn|β1|...|βm，其中βj不以A开头，变换后得到A→β1A′|β2A′|...|βmA′，A′→α1A′|α2A′|...|αnA′|ε。关键点是原来所有以A开头的递归产生式，右边新增一个A′放在末尾；不以A开头的产生式，右边统一追加一个A′。A′用空串ε作为出口，防止推导无限延续。

看一下算术表达式文法的实际操作。原始文法有三条产生式E→E+T|T，T→TF|F，F→(E)|id。对E做消除，E→T E′，E′→+T E′|ε。对T做消除，T→F T′，T′→F T′|ε。F本身没有左递归，保持不动。变换后的文法没有左递归，同时接受的语言还是原来的算术表达式。这里有个容易忘的点：E′和T′都是新增非终结符，它们的FOLLOW集会参与后面建表，所以变换后要重新计算全部集合，不能在原文法的FIRST/FOLLOW上打补丁。

实验里我一般不用程序自动消除左递归，因为教科书文法就那么几条，手工转换更快且不容易错。但如果你拿到的文法有几十条产生式，建议写个通用的转换函数：遍历每个非终结符A的所有产生式，把以A开头的放进alphaList，其余放进betaList，然后按公式拼接。注意间接左递归需要先按某种拓扑序处理，教材里的算法是先对非终结符排序，再做两轮替换，把间接左递归转成直接左递归，最后统一消除。下面给出直接左递归的Java实现：

// 消除非终结符A的直接左递归，返回变换后的产生式右部列表 // productions: A的所有产生式右部，例如 ["E + T", "T"] // epsilon: 空串标记 List<String> eliminateDirectLeftRecursion( String A, List<String> productions, String epsilon) { List<String> beta = new ArrayList<>(); // 不以A开头的右部 List<String> alpha = new ArrayList<>(); // 以A开头的右部 for (String p : productions) { if (p.startsWith(A + " ")) { alpha.add(p.substring(A.length() + 1)); } else { beta.add(p); } } if (alpha.isEmpty()) return productions; // 没有直接左递归 String A1 = A + "'"; // 新非终结符名，注意别和已有符号撞名 List<String> result = new ArrayList<>(); // A -> β A' for (String b : beta) result.add(b + " " + A1); // A' -> α A' for (String a : alpha) result.add(A1 + " -> " + a + " " + A1); // A' -> ε result.add(A1 + " -> " + epsilon); return result; }

输入productions里的右部格式用空格分隔单词，如“E + T”。startsWith(A+" ")判断右部第一个符号是否为A，substring截掉A和后面的空格，剩下的就是α。变换结果里A′的产生式以字符串列表形式返回，调用方需要把这些产生式挂到grammar的A′条目下。注意A′这个名字在原始文法里不能已经存在，否则会覆盖原产生式，实验里一般用A1、A2这类不冲突的名字。

2.3 提取左公因子：先把悬空else之类的问题拆掉

左公因子的典型场景是if语句。文法通常写成S→if E then S else S|if E then S，两条产生式共享前缀“if E then S”，分析器看到if时不知道该选哪条。提取后变成S→if E then S S′，S′→else S|ε。这样语义上else的匹配仍然遵循“就近匹配”规则，同时给了分析器一个确定的选择：看到else就进S′的第二条产生式，看到其他符号就选ε。

提取左公因子的通用做法是找到同一非终结符下产生式的最长公共前缀γ，然后A→γ A′，A′→β1|...|βn。如果前缀后面还有公共前缀就继续递归提取。这里有个程度问题：提取左公因子不一定能把所有非LL(1)文法变成LL(1)文法，有些语言本质上不是LL(1)的，怎么提都没用。判断标准就是后面要讲的预测分析表是否有冲突。所以别把提取左公因子当成万能药，做完后一定要用建表来验证。

2.4 手术后的自检：用一条输入串走一遍最左推导

文法改写完，先别急着写程序，手工拿一条输入串走一遍最左推导，验证每一步的选择是否唯一。以消除左递归后的表达式文法为例，输入串是“id + id * id”。推导过程是：E→T E′→F T′ E′→id T′ E′→id E′（T′选ε）→id + T E′→id + F T′ E′→id + id T′ E′→id + id * F T′ E′→id + id * id T′ E′→id + id * id。每走一步都观察当前栈顶符号和下一个输入符号，确认只有一个产生式可以选。如果中间某一步出现了两个可选项，那就要回到文法检查是否还有左公因子没提干净。

这个自检同时也能帮你建立“栈顶符号 + 输入符号 → 产生式”的映射直觉，后面写表驱动循环时会很顺手。我在实验里发现，很多人的程序错在建表逻辑，但真正的问题是文法没有彻底改造，手工推导一遍能把这类问题挡在写代码之前。

3. FIRST与FOLLOW集计算：LL(1)分析表的地基

预测分析表M[A,a]要回答的问题是：当栈顶是非终结符A，而输入符号是a时，应该用A的哪条产生式来展开。填表的依据是FIRST集和FOLLOW集。FIRST集描述“一个符号串能推导出的第一个终结符有哪些”，FOLLOW集描述“某个非终结符后面可能紧跟哪些终结符”。这两个集合算错了，分析表必然填错，程序跑起来就是各种“表里查不到条目”的报错。这一节把两条集合的计算规则和一套不会算错的迭代写法拆开讲。

3.1 FIRST集的计算规则：四条规则与一轮一轮迭代

FIRST集针对文法符号X定义。规则不复杂。第一条，如果X是终结符，FIRST(X)就是{X}。第二条，如果X是ε，FIRST(X)包含ε。第三条，如果X是非终结符且存在产生式X→Y1Y2...Yk，那么依次看Y1,Y2,...，把FIRST(Yi)里的非ε元素都加入FIRST(X)，直到遇到某个Yi的FIRST不含ε才停止；如果Y1到Yk的FIRST全部含ε，就把ε也加入FIRST(X)。第四条，对任何产生式右部α=Y1Y2...Yk，FIRST(α)的计算方式和第三条相同：从Y1开始逐个累加非ε元素，中途遇到FIRST含ε的符号就继续往后看，直到遇见不含ε的符号为止；如果α能推导出ε，则ε∈FIRST(α)。

这四条规则里最容易忽略的是终止条件。累加FIRST(Yi)的非ε元素后，只有FIRST(Yi)包含ε时才继续检查Yi+1，一旦遇到FIRST不含ε的符号立刻停止。很多实现把这步写成无条件遍历，结果把后续符号的FIRST错误地塞了进来，集合就会偏大。手动算的时候也容易犯同样的错，尤其在产生式右部有连续两个非终结符时。下面给一个FIRST集的Java实现，用不动点迭代：不断遍历所有产生式，能加就加，直到某一轮集合没有任何变化才停止：

// 计算所有文法符号的FIRST集 // grammar: key=非终结符, value=产生式右部列表 // terminals: 终结符集合（不含ε），epsilon: 空串标记 Map<String, Set<String>> computeFirstSets( Map<String, List<String>> grammar, Set<String> terminals, String epsilon) { Map<String, Set<String>> first = new HashMap<>(); // 初始化：终结符的FIRST是自身，非终结符的FIRST为空 for (String nt : grammar.keySet()) first.put(nt, new HashSet<>()); for (String t : terminals) { Set<String> s = new HashSet<>(); s.add(t); first.put(t, s); } boolean changed = true; while (changed) { changed = false; for (String nonTerminal : grammar.keySet()) { for (String production : grammar.get(nonTerminal)) { String[] symbols = production.split(" "); Set<String> before = new HashSet<>(first.get(nonTerminal)); boolean canDeriveEpsilon = true; for (String symbol : symbols) { if (symbol.equals(epsilon)) { // 产生式右部本身就是ε，把ε加入 first.get(nonTerminal).add(epsilon); canDeriveEpsilon = true; break; } // 把当前符号FIRST中的非ε元素加进来 for (String f : first.getOrDefault(symbol, Collections.emptySet())) { if (!f.equals(epsilon)) first.get(nonTerminal).add(f); } // 当前符号FIRST不含ε，则停止 if (!first.getOrDefault(symbol, Collections.emptySet()).contains(epsilon)) { canDeriveEpsilon = false; break; } } // α能推导出ε时，把ε加入FIRST(A) if (canDeriveEpsilon) first.get(nonTerminal).add(epsilon); if (!before.equals(first.get(nonTerminal))) changed = true; } } } return first; }

这里的grammar结构和前面检测左递归用的是同一套：key是非终结符，value是产生式右部字符串列表，产生式右部已经按空格分割好。terminals集合需要手工传入，包含所有终结符和ε标记。调用的前提是终结符集合里恰好包含了全部不会被展开的符号，如果漏掉某个终结符，getOrDefault会返回空集，FIRST计算结果会比实际小，查表时就会出现“找不到条目”。这个“漏终结符”的坑我在实验里踩过一次，症状是分析合法的输入串到某个符号就报错，排查半天发现只是初始化集合少了一个分号。

3.2 FOLLOW集的计算：三条规则和结束符的作用

FOLLOW集的定义是：在文法推导过程中，紧跟非终结符A之后可能出现的一切终结符集合。初始时把$（或#）加入FOLLOW(S)，S是文法开始符号。三条计算规则。第一条，如果有产生式A→αBβ，那么把FIRST(β)中除ε之外的所有元素加入FOLLOW(B)。第二条，如果有产生式A→αB，或A→αBβ且β能推导出ε，那么把FOLLOW(A)的全部元素加入FOLLOW(B)。第三条反复应用第一条和第二条，直到集合不再变化。

这里容易弄混的是第二条的后半句。β能推导出ε，意味着B后面实际上可以没有东西，那B后面可能出现的就是FOLLOW(A)里的终结符。判断β能否推导出ε，要基于第一步算好的FIRST集：β里每个符号的FIRST都包含ε。我用程序实现时，会单独写一个方法判断一个符号串是否可空，而不是在FOLLOW循环里重复一段容易出错的逻辑。下面这个Java方法实现FOLLOW集计算：

// 计算所有非终结符的FOLLOW集 // grammar: 文法，startSymbol: 开始符号，epsilon: 空串标记 // first: 3.1节算好的FIRST集，endMarker: 结束符（一般用"$"） Map<String, Set<String>> computeFollowSets( Map<String, List<String>> grammar, String startSymbol, String epsilon, Map<String, Set<String>> first, String endMarker) { Map<String, Set<String>> follow = new HashMap<>(); for (String nt : grammar.keySet()) follow.put(nt, new HashSet<>()); follow.get(startSymbol).add(endMarker); // 开始符号的FOLLOW必须有结束符 boolean changed = true; while (changed) { changed = false; for (String nonTerminal : grammar.keySet()) { for (String production : grammar.get(nonTerminal)) { String[] symbols = production.split(" "); for (int i = 0; i < symbols.length; i++) { String B = symbols[i]; if (!grammar.containsKey(B)) continue; // 终结符没有FOLLOW Set<String> before = new HashSet<>(follow.get(B)); // 快照 String beta = i + 1 < symbols.length ? String.join(" ", Arrays.copyOfRange(symbols, i + 1, symbols.length)) : ""; // 规则1：FIRST(β)的非ε元素加入FOLLOW(B) for (String f : firstOfString(beta, first, epsilon)) { if (!f.equals(epsilon)) follow.get(B).add(f); } // 规则2：β为空或可空时，FOLLOW(A)加入FOLLOW(B) if (beta.isEmpty() || canDeriveEpsilon(beta, first, epsilon)) { for (String f : follow.get(nonTerminal)) { follow.get(B).add(f); } } if (!before.equals(follow.get(B))) changed = true; } } } } return follow; }

规则2里判断β是否为空串或可空用的canDeriveEpsilon方法，检查β经过推导能否变成ε，判断标准是β中每个符号的FIRST都包含ε。注意β为空串时也满足条件，对应的就是产生式右部以B结束的情况，此时FOLLOW(A)整体加入FOLLOW(B)。这里的first参数必须来自computeFirstSets的返回值，不能在FOLLOW计算里重新算一遍FIRST，否则同一轮迭代里集合之间互相覆盖，结果不稳定。我在代码里用before快照来检测变化，确保每一轮的增量都基于本轮之前的状态，避免同一轮内连锁更新导致顺序依赖。

3.3 计算顺序：为什么先FIRST后FOLLOW，并且一轮一轮慢慢来

FIRST和FOLLOW的计算都依赖不动点迭代：每轮扫描所有产生式，把能加入的符号加入，直到某轮完全没有变化。先算FIRST的原因很简单，FOLLOW规则1需要FIRST(β)，规则2的可空判断也依赖FIRST。FIRST没算完就动FOLLOW，等于用半成品数据去加工，最后结果必然错。

常见误区是只迭代一轮就觉得算完了。FIRST集的计算可能一轮就稳定，也可能要多轮，因为A的FIRST可能来自B，而B的FIRST又来自C，逐级传递。我在实现里用while(changed)循环，每轮结束后检查状态，直到没有任何set发生变化为止。调试时可以打印每轮结束后所有集合的内容，手动对比一下，确认自己在第几轮稳定。实验里给学生的建议是：先用手工算两三个非终结符的FIRST，再用程序输出对比，能搜到的大多数实现都长这样，但迭代轮数和终止条件各有各的写法，对着教材步骤逐行核对最保险。

3.4 手工验证：一个四产生式文法从FIRST到FOLLOW的完整演算

纸上得来终觉浅，给一个小文法做完整演算。文法G：E→TE′，E′→+TE′|ε，T→FT′，T′→FT′|ε，F→(E)|id。终结符集合是{(,),+,,id}，ε单独处理，开始符号E。

先算FIRST。F的FIRST是{(,id}。T′的FIRST：产生式T′→FT′贡献；T′→ε贡献ε，所以FIRST(T′)={*,ε}。T的FIRST：T→FT′，F的FIRST是{(,id}，都非ε，所以FIRST(T)={(,id}。E′的FIRST：产生式E′→+TE′贡献+；E′→ε贡献ε，所以FIRST(E′)={+,ε}。E的FIRST：E→TE′，T的FIRST是{(,id}，非ε，所以FIRST(E)={(,id}。

再算FOLLOW。初始化FOLLOW(E)={$}。扫描产生式E→TE′，规则1把FIRST(E′)的非ε元素+加入FOLLOW(T)；规则2因E′可空，把FOLLOW(E)即{$}加入FOLLOW(T)。所以FOLLOW(T)={+,$}。扫描E′→+TE′，规则1中β为空串，没有贡献；规则2因β为空，把FOLLOW(E′)加入FOLLOW(T)。FOLLOW(E′)目前没有，所以暂不加入。扫描T→FT′，规则1把FIRST(T′)的非ε元素加入FOLLOW(F)；规则2因T′可空，把FOLLOW(T)即{+,$}加入FOLLOW(F)。FOLLOW(F)={,+,$}。继续扫描T′→FT′，规则2把FOLLOW(T′)加入FOLLOW(F)。再扫描F→(E)，规则1把FIRST())即)}加入FOLLOW(E)，所以FOLLOW(E)={$,)}。第二轮扫描后FOLLOW(E′)从FOLLOW(E)继承{$,)}。最终FOLLOW(E)=FOLLOW(E′)={$,)}，FOLLOW(T)=FOLLOW(T′)={+,$,)}，FOLLOW(F)={,+,$,)}。

这个演算过程建议大家在程序里加一行调试输出，每轮迭代后打印全部FOLLOW集合，和手工结果对得上再继续。程序里如果直接在原集合上逐个add会丢中间状态，最好每轮快照比较。

4. 构造预测分析表并用表驱动LL(1)分析器跑起来

FIRST和FOLLOW算完，接下来建预测分析表M。表是个二维结构：行是非终结符，列是全部终结符加上结束符$。单元格M[A,a]存放的内容是“A应该用哪条产生式展开”，或者为空表示error。建表规则一句话：对每条产生式A→α，把α能推导出的所有第一个终结符对应的列都填上这条产生式；如果α可空，再把FOLLOW(A)里的每个终结符对应列也填上这条产生式。出现任何单元格被填了两条不同产生式，这个文法就不是LL(1)文法。

4.1 预测分析表的填充规则与冲突判定

具体填充分两步。第一步，对每条产生式A→α，取出FIRST(α)中所有非ε终结符a，把M[A,a]写入这条产生式。第二步，如果α可空（包括α本身就是ε的情况），那么对FOLLOW(A)中每个终结符b，把M[A,b]也写入这条产生式。注意这里FIRST(α)和FIRST(A)不是一回事。填表用的是右部α的FIRST，不是左部A的FIRST。这个细节很多人写错，症状是某些合法输入串走到某一步时分析表查不到条目。

冲突判定就是看填表过程中是否有单元格被写了第二次并且内容不同。程序里可以用Map<String,List >来存，填表时先取已有列表，如果列表里已经有产生式且和当前要填的不一样，就记录一条冲突。实验报告里一般要求列出冲突产生的位置，方便说明该文法为什么不是LL(1)。下面代码完成建表和冲突检测：

// 构造预测分析表 // grammar: 文法, first: FIRST集, follow: FOLLOW集, epsilon: 空串标记 // 返回表，key=非终结符+","+终结符, value=产生式列表（形如"A->alpha"） Map<String, List<String>> buildParsingTable( Map<String, List<String>> grammar, Map<String, Set<String>> first, Map<String, Set<String>> follow, String epsilon) { Map<String, List<String>> table = new HashMap<>(); boolean conflict = false; for (String A : grammar.keySet()) { for (String alpha : grammar.get(A)) { // 计算 FIRST(alpha) Set<String> firstAlpha = firstOfString(alpha, first, epsilon); // 第一步：FIRST(alpha)的非ε元素填入 for (String a : firstAlpha) { if (!a.equals(epsilon)) { String key = A + "," + a; List<String> list = table.getOrDefault(key, new ArrayList<>()); list.add(A + "->" + alpha); if (list.size() > 1) conflict = true; // 冲突检测 table.put(key, list); } } // 第二步：alpha可空时，FOLLOW(A)的元素填入 if (alpha.equals(epsilon) || canDeriveEpsilon(alpha, first, epsilon)) { for (String b : follow.get(A)) { String key = A + "," + b; List<String> list = table.getOrDefault(key, new ArrayList<>()); list.add(A + "->" + alpha); if (list.size() > 1) conflict = true; table.put(key, list); } } } } if (conflict) System.out.println("文法不是LL(1)文法，存在表冲突"); return table; }

这里的firstOfString方法是3.1节里说的那个针对符号串计算FIRST的工具函数，逻辑跟FIRST(X)第四条规则完全一致：从串的第一个符号开始逐个累加，遇到FIRST含ε的符号继续，遇到不含ε的停止。canDeriveEpsilon同样依赖first集合判断当前串能否推空。这套结构把建表和计算分开，出问题时容易定位：先确认FIRST/FOLLOW，再确认是填充逻辑错了还是文法本身有冲突。注意key用逗号拼接A和a，如果产生式里包含逗号可能会撞key，实验文法简单，不会遇到。如果自己扩展，建议用内部类Cell{A,a}并重写equals/hashCode。

4.2 判断一个文法是不是LL(1)：三种典型冲突

预测分析表无冲突，是LL(1)文法的充要条件。表冲突一般有三种形态。第一种是FIRST冲突，比如产生式A→αβ1|αβ2共享前缀α，FIRST(αβ1)和FIRST(αβ2)有交集，导致同一单元格出现两条产生式。这种要靠提取左公因子解决。第二种是FIRST/FOLLOW冲突，比如A→α和A→β两条产生，α可空，那么FIRST(β)里如果含有FOLLOW(A)里的某个终结符，就会在β可推导出的那些终结位列上同时填入两条产生式。第三种是FOLLOW/FOLLOW冲突，一般发生在ε产生式和其它产生式共存且FOLLOW集合相交的情况，本质上也是“看到某个输入符号时，选ε还是选别的展开”的歧义。

实验里遇到冲突时，不要急着改建表代码。先用程序打印冲突的完整信息——哪个单元格、哪两条产生式、各自来自哪个规则步骤——再回到文法去改。我见过同学把建表逻辑改来改去，最后发现是文法里有一处间接左递归没消除干净。判断一个文法能不能用LL(1)，标准答案就是建表看冲突，没有捷径。

4.3 表驱动分析器的数据结构：栈、输入带、产生式表

分析器运行时的核心数据结构有四块：分析栈、输入缓冲、预测分析表、产生式列表。分析栈存放文法符号（终结符和非终结符），初始时先把$压栈，再把开始符号压栈，栈顶在最上层。输入缓冲区存放待分析的符号串，末尾加上$作为结束标记。预测分析表就是上一节建好的M。产生式列表用于把表的动作翻译成实际推导。

分析过程中的每一步都看栈顶符号X和当前输入符号a。如果X是终结符且X==a，说明匹配成功，pop栈顶，输入指针后移；如果X==$且a==$，说明分析成功结束；如果X是非终结符，则查表M[X,a]，得到一条产生式，先把栈顶的X弹掉，再把产生式右部逆序压栈（右部从左到右第一个符号要被先展开，所以压栈时要让第一个符号最后压入，处于栈顶）；如果查表结果是空，报告错误。

这里最容易出错的是逆序压栈。产生式X→Y1Y2...Yk，展开后栈里原来的X被替换成Y1Y2...Yk，但栈是后进先出，为了让Y1成为新的栈顶，压栈顺序必须是Yk,Yk-1,...,Y1。如果压栈顺序反了，分析器会把整个输入串反向推导，结果看起来像在跑另一个文法。下面给出主循环代码：

// 表驱动LL(1)分析器主循环 // inputTokens: 输入符号列表（末尾已加$） // table: 4.1节建好的预测分析表，epsilon: 空串标记 boolean parse( List<String> inputTokens, String startSymbol, String endMarker, Map<String, List<String>> table, String epsilon) { Deque<String> stack = new ArrayDeque<>(); stack.push(endMarker); // 结束符先入栈 stack.push(startSymbol); // 开始符号再入栈 int index = 0; // 输入指针 while (!stack.isEmpty()) { String top = stack.peek(); String lookahead = inputTokens.get(index); if (top.equals(endMarker) && lookahead.equals(endMarker)) { return true; // 栈和输入同时到达$，接受 } if (isTerminal(top)) { // 终结符必须和当前输入一致才能匹配 if (top.equals(lookahead)) { stack.pop(); index++; } else { System.out.println("期望 " + top + "，但读到 " + lookahead); return false; } } else { // 非终结符查表 String key = top + "," + lookahead; List<String> productions = table.getOrDefault(key, new ArrayList<>()); if (productions.isEmpty()) { System.out.println("表项为空: " + key); return false; } if (productions.size() > 1) { System.out.println("表项冲突: " + key); return false; } String production = productions.get(0); // 形如 A->alpha String right = production.substring(production.indexOf("->") + 2); stack.pop(); // 弹出A if (!right.equals(epsilon)) { String[] symbols = right.split(" "); // 逆序压栈，保证第一个符号最后压入 for (int i = symbols.length - 1; i >= 0; i--) { stack.push(symbols[i]); } } } } return false; }

主循环里的逆序压栈是整个函数的灵魂。isTerminal方法判断栈顶是否为终结符，判断标准是“不在grammar的key集合里”。注意ε在栈里不应该出现，因为产生式右部为ε时不需要压入任何符号，弹出A后直接continue即可；如果压入了ε，后面所有查表都会因为ε不是终结符也不是非终结符而直接翻车。我的做法是在代码里把ε标记单独定义，所有用到ε的地方都走同一个常量，避免字符串比较写错。

4.4 关键动作细节：什么时候展开、什么时候匹配、什么时候报错

分析器所有动作都发生在主循环的三个分支里。第一个分支，栈顶是终结符X且X==当前输入a，执行匹配：弹出X，输入指针加一。第二个分支，栈顶是非终结符A，查表M[A,a]拿到唯一产生式A→β，执行展开：弹出A，把β逆序压栈。第三个分支，栈顶和输入都是$，接受并结束。除此之外的情况都是报错，包括终结符不等、表项为空。

展开动作里有一个反直觉的点：分析器不检查产生式右部β的FIRST是否真的包含a。它只依赖建表时保证的“M[A,a]里存放的产生式是唯一且可用的”。所以如果建表逻辑有bug，分析器不会立刻暴露，而是会在后续匹配时出现终结符不匹配或查不到表项的错误，而且报错位置往往离真正的问题很远。我在调试时遇到莫名其妙的分析失败，第一反应不是看主循环，而是回去打印预测分析表的几个关键单元格——比如M[E,(]、M[T,id]——逐条核对是不是填对了。

ε产生式的处理也值得单独说。A→ε在表里对应M[A,b]中b∈FOLLOW(A)的那些单元格。当栈顶是A、输入是b时，查表得到A→ε，动作是弹出A但不压入任何东西。这一步相当于“跳过”A，让分析继续看A后面的符号。很多初学者会把ε当成一个真实的输入符号来处理，甚至在栈里压入ε，这是错的。ε只存在于产生式右部，不出现在栈里，也不出现在输入串里。

注意：调试时建议把每一步的栈内容、当前输入符号和采取的动作都打印出来。看一眼栈的变化比猜半天“哪里错了”高效得多。

5. 避坑：LL(1)实现里反复翻车的六个细节

LL(1)分析器代码量不大，但真正让它稳定跑通，坑全在细节。下面六条来自我自己的实验和帮同学调试时见到的真实翻车情况，每一条都是“现象→原因→解决”的结构，直接对着排查就行。

5.1 左递归没消除干净，程序一跑就死循环

现象：分析器在某个非终结符上一直展开同一个产生式，输入指针完全不动，程序超时或者栈溢出。比如文法里残留E→E+T，栈顶E永远被替换成E+T，栈越来越长。

原因：消左递归时只处理了直接左递归，间接左递归漏掉了。A→B，B→A这种两跳以上的递归，BFS检查左递归的代码能查到，但很多人把它转成直接左递归后再消的时候漏了某一边。

解决：先用2.1节的检测代码跑一遍，把间接左递归先替换成直接左递归，再做消除。消除后再次检测确认干净，再继续算FIRST。这一步值得花时间，后面所有工作都建立在文法无左递归的前提下。

5.2 FIRST集把ε漏了，导致FOLLOW集连锁出错

现象：FIRST集看起来“差不多对”，但FOLLOW集缺了几个终结符，建表后某些合法输入串卡在空表项。

原因：计算FIRST时，产生式右部全部符号都可空的情况下，忘记把ε加入左部非终结符的FIRST。比如T′→FT′|ε，如果把ε漏掉，FIRST(T′)就只剩{}，那么T的FOLLOW计算里判断“T′可空”就会失败，FOLLOW(T)缺掉$等符号。

解决：在computeFirstSets的迭代里，如果产生式右部符号串可以推空，必须把ε加入左部FIRST集。判断“右部可空”时，注意右部为空串（即产生式本身就是A→ε）也算可空。打印FIRST集后逐条检查，ε是否真的出现在该出现的集合里。

5.3 逆序压栈的方向搞反，推导出的符号序列完全颠倒

现象：分析器不报错，但接受了一串“反的”输入。输入是“id + id”，分析器却能用“id id +”通过。这种错误最隐蔽，因为程序逻辑自洽，结果全错。

原因：展开A→Y1Y2时，先把Y1压栈再把Y2压栈，导致栈顶是Y2而不是Y1。正确的顺序是逆序压栈，保证右部第一个符号最后入栈、处于栈顶。

解决：主循环里先弹出A，再for循环从symbols.length-1往下压到0。代码写完后，拿一个三步以内的推导手工模拟一遍，确认栈变化和自己的推导过程一致。这一步能挡住大多数方向性错误。

5.4 终结符与输入符号的类型混用，查表永远查不到

现象：代码里把终结符、非终结符都存在同一个List 里，有的地方用String，有的地方用Integer编号，建表时一会儿写的是符号名字，一会儿写的是终结符编号，导致查表时key对不上。

原因：数据结构设计时不统一。名字和编号两套体系并存，中间转换漏了一处。

解决：统一用字符串表示文法符号，终结符、非终结符、$、ε都各有明确的定义。isTerminal方法统一判断“不在grammar.keySet里”就是终结符，不要在其它地方再建一套终结符判断。如果感觉类型不清，建议给终结符和非终结符定义两个Set，初始化时一次性划分好。

5.5 表项冲突时把程序改成“取第一条”来规避

现象：建表程序检测到某个单元格有两条产生式，直接取第一条继续跑，程序看起来正常，但某些输入串按照错误的产生式推导，最终在匹配阶段报“期望X读到Y”的错误。

原因：这是掩耳盗铃式的修复。LL(1)文法的挑错标准就是表冲突，冲突存在说明文法本身不是LL(1)，取第一条只是把错误后移，并没有消除。

解决：遇到冲突，打印单元格和产生式列表，回到文法层面解决。该提左公因子的提公因子，该处理左递归的处理左递归。如果怎么改都有冲突，那要承认这个文法不是LL(1)，考虑换LR分析或改写文法，而不是在表驱动循环里作弊。

5.6 输入串末尾忘记加$，结尾判断永远等不到

现象：分析到最后栈顶是$，输入已经空了，程序还在循环中，或者越界取输入符号。

原因：输入缓冲区没有追加结束符$，匹配到最后一个真实符号后，输入指针指向数组末尾之外。

解决：在输入符号列表末尾追加$，同时在主循环里先判断栈顶和当前输入是否都是$。还要注意inputTokens.get(index)在index超出列表长度时要先做边界检查，否则Java会抛IndexOutOfBoundsException。我在parse方法开头对输入做了非空校验，末尾统一append($)，这样所有分支都不用再单独判断输入是否耗尽。

6. 从能跑到跑稳：测试用例、错误恢复与实验报告写法

程序能在主循环里跑通一条输入串，只是第一步。想让实验拿高分或者让分析器真正可用，还要补三块：边界测试、错误恢复、报告里的设计说明。

6.1 用边界输入串验证分析器

至少准备五类输入串，覆盖正常路径和异常路径：

把每个用例的分析过程打印出来，最后对照手工推导，确认每一步展开都一致。空串这个用例特别容易忽略，但它是检验结束符处理是否正确的唯一途径。

6.2 错误恢复的两种策略

实验一般只要求检测错误，不要求恢复。如果要做得更完整，常见做法是恐慌模式：当查表失败时，丢弃输入符号直到遇到同步词法单元（比如分号或右括号），再继续分析。另一种是短语级恢复，在栈顶或输入中做局部替换，代价较高。做实验时建议用恐慌模式，且把错误位置打印清楚，这比强行恢复更有教学意义。

6.3 实验报告里老师想看到的内容

报告至少包含文法改造前后对比、FIRST/FOLLOW集合的演算过程、预测分析表的填充逻辑截图、三个以上测试用例及对应推导过程。我最想强调的一点是：把消除左递归前后的文法并排写出来，把FIRST集迭代过程中每一轮的变化写出来，这些过程性内容比最终代码更有说服力。

回到做实验本身，我最大的教训是：不要在没手工演算过一遍的情况下直接写代码。FIRST、FOLLOW、预测分析表这三样东西，手工算通一次，程序就只是“翻译”而已；跳过去直接写程序，调试时间至少翻倍。这是我带实验课几年看到的最高频翻车原因。希望帮到你。

本文还有配套的精品资源，点击获取