简介面向山东科技大学编译原理课程的 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→ET这一条分析器要推导E时按规则先展开最左的E结果产生式右边第一个符号还是E于是又开始推导E永远在原地打转。理论上讲只要产生式右边第一个非终结符和左边相同就会造成“无限推导”这就是直接左递归。还有一种间接左递归比如A→BB→A这种两跳以上的循环同样致命。LL(1)使用最左推导等于要求每一步都能用当前输入符号做“唯一决策”左递归让决策永远做不出来。左公因子的问题不一样。A→αβ1和A→αβ2两条产生式的前缀完全相同当输入符号是FIRST(α)里的某个终结符时分析器不知道应该选β1还是β2。这不至于死循环但会让预测分析表在M[A,a]的位置产生两个条目也就是冲突文法因此被判定为非LL(1)。所以“消左递归、提左公因子”是LL(1)分析器实现里的前置手术手术后还要重新验证文法仍然接受原来的语言——变换不能改变语言本身只改变推导方式。比如下面这段Java代码用来检测一个文法是否存在直接或间接左递归我在实验里通常先把文法读进来跑一遍这个检查再决定要不要做变换// 检测文法是否存在左递归返回true表示存在 // grammar: key非终结符, value该非终结符的所有产生式右部按空格分词 boolean hasLeftRecursion(MapString, ListString grammar) { for (String nonTerminal : grammar.keySet()) { // 记录从当前非终结符出发能到达的非终结符 SetString reachable new HashSet(); QueueString 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→ET到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→ET|TT→TF|FF→(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: 空串标记 ListString eliminateDirectLeftRecursion( String A, ListString productions, String epsilon) { ListString beta new ArrayList(); // 不以A开头的右部 ListString 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 ; // 新非终结符名注意别和已有符号撞名 ListString 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 )判断右部第一个符号是否为Asubstring截掉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...YkFIRST(α)的计算方式和第三条相同从Y1开始逐个累加非ε元素中途遇到FIRST含ε的符号就继续往后看直到遇见不含ε的符号为止如果α能推导出ε则ε∈FIRST(α)。这四条规则里最容易忽略的是终止条件。累加FIRST(Yi)的非ε元素后只有FIRST(Yi)包含ε时才继续检查Yi1一旦遇到FIRST不含ε的符号立刻停止。很多实现把这步写成无条件遍历结果把后续符号的FIRST错误地塞了进来集合就会偏大。手动算的时候也容易犯同样的错尤其在产生式右部有连续两个非终结符时。下面给一个FIRST集的Java实现用不动点迭代不断遍历所有产生式能加就加直到某一轮集合没有任何变化才停止// 计算所有文法符号的FIRST集 // grammar: key非终结符, value产生式右部列表 // terminals: 终结符集合不含εepsilon: 空串标记 MapString, SetString computeFirstSets( MapString, ListString grammar, SetString terminals, String epsilon) { MapString, SetString first new HashMap(); // 初始化终结符的FIRST是自身非终结符的FIRST为空 for (String nt : grammar.keySet()) first.put(nt, new HashSet()); for (String t : terminals) { SetString 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( ); SetString 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: 结束符一般用$ MapString, SetString computeFollowSets( MapString, ListString grammar, String startSymbol, String epsilon, MapString, SetString first, String endMarker) { MapString, SetString 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 SetString before new HashSet(follow.get(B)); // 快照 String beta i 1 symbols.length ? String.join( , Arrays.copyOfRange(symbols, i 1, symbols.length)) : ; // 规则1FIRST(β)的非ε元素加入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的完整演算纸上得来终觉浅给一个小文法做完整演算。文法GE→TE′E′→TE′|εT→FT′T′→FT′|εF→(E)|id。终结符集合是{(,),,,id}ε单独处理开始符号E。先算FIRST。F的FIRST是{(,id}。T′的FIRST产生式T′→FT′贡献T′→ε贡献ε所以FIRST(T′){*,ε}。T的FIRSTT→FT′F的FIRST是{(,id}都非ε所以FIRST(T){(,id}。E′的FIRST产生式E′→TE′贡献E′→ε贡献ε所以FIRST(E′){,ε}。E的FIRSTE→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。这个细节很多人写错症状是某些合法输入串走到某一步时分析表查不到条目。冲突判定就是看填表过程中是否有单元格被写了第二次并且内容不同。程序里可以用MapString,List 来存填表时先取已有列表如果列表里已经有产生式且和当前要填的不一样就记录一条冲突。实验报告里一般要求列出冲突产生的位置方便说明该文法为什么不是LL(1)。下面代码完成建表和冲突检测// 构造预测分析表 // grammar: 文法, first: FIRST集, follow: FOLLOW集, epsilon: 空串标记 // 返回表key非终结符,终结符, value产生式列表形如A-alpha MapString, ListString buildParsingTable( MapString, ListString grammar, MapString, SetString first, MapString, SetString follow, String epsilon) { MapString, ListString table new HashMap(); boolean conflict false; for (String A : grammar.keySet()) { for (String alpha : grammar.get(A)) { // 计算 FIRST(alpha) SetString firstAlpha firstOfString(alpha, first, epsilon); // 第一步FIRST(alpha)的非ε元素填入 for (String a : firstAlpha) { if (!a.equals(epsilon)) { String key A , a; ListString 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; ListString 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是终结符且Xa说明匹配成功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( ListString inputTokens, String startSymbol, String endMarker, MapString, ListString table, String epsilon) { DequeString 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; ListString 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→ET栈顶E永远被替换成ET栈越来越长。原因消左递归时只处理了直接左递归间接左递归漏掉了。A→BB→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 用边界输入串验证分析器至少准备五类输入串覆盖正常路径和异常路径测试输入预期结果验证点id接受单符号最简输入(idid)*id接受括号嵌套与运算符优先级idid报错并报告位置连续运算符检测(id报错并报告位置括号不匹配空串按文法定义处理结束符边界把每个用例的分析过程打印出来最后对照手工推导确认每一步展开都一致。空串这个用例特别容易忽略但它是检验结束符处理是否正确的唯一途径。6.2 错误恢复的两种策略实验一般只要求检测错误不要求恢复。如果要做得更完整常见做法是恐慌模式当查表失败时丢弃输入符号直到遇到同步词法单元比如分号或右括号再继续分析。另一种是短语级恢复在栈顶或输入中做局部替换代价较高。做实验时建议用恐慌模式且把错误位置打印清楚这比强行恢复更有教学意义。6.3 实验报告里老师想看到的内容报告至少包含文法改造前后对比、FIRST/FOLLOW集合的演算过程、预测分析表的填充逻辑截图、三个以上测试用例及对应推导过程。我最想强调的一点是把消除左递归前后的文法并排写出来把FIRST集迭代过程中每一轮的变化写出来这些过程性内容比最终代码更有说服力。回到做实验本身我最大的教训是不要在没手工演算过一遍的情况下直接写代码。FIRST、FOLLOW、预测分析表这三样东西手工算通一次程序就只是“翻译”而已跳过去直接写程序调试时间至少翻倍。这是我带实验课几年看到的最高频翻车原因。希望帮到你。本文还有配套的精品资源点击获取