Java实现LL1语法分析：从First集到预测分析表的完整实践

简介面向编译原理课程的LL(1)语法分析实验资源源自山东科技大学2022年编译原理实验内容包含完整的CodeBlocks工程代码和实验报告适合正在学习编译原理、需要完成类似实验或想深入理解LL(1)分析方法的学生与自学者。压缩包大小约1.08MB主要文件类型为可直接编译运行的源码文件和文字版实验报告报告对LL(1)分析中的关键步骤有详细推导目前已有913人学习或下载可用于课程实验、期末复习或毕业设计参考。通过资源中的代码读者可以快速验证对给定文法的分析过程该文法覆盖加减乘除及括号表达式涉及E→TG、G→TG|-TG、T→FM、M→*FM|/FM、F→(E)等产生式借助完整的预测分析表驱动能够判断任意输入符号串是否符合文法。报告还详细说明了FIRST集合、FOLLOW集合的求解方法以及预测分析表的构建步骤便于对照代码加深理解。1. LL1分析法在编译原理实验里的位置它到底解决了什么LL1分析法是编译原理实验里最典型的自顶向下语法分析实现22年山科大编译原理实验把语法分析单独拎出来要求实现LL1背后其实是在考察两件事First集与Follow集算得对不对以及驱动程序能不能按预测分析表机械地完成匹配。LL1这三个字母分别代表从左到右扫描输入、最左推导、向前看1个token它把文法规则全部映射成一张二维预测分析表分析器本身就是一个查表加进出栈的循环。这个实验适合两类人一类是被递归下降分析法里各种手写分支绕晕的学生另一类是已经跑过词法分析、想用Java快速体验一遍完整语法分析流程的开发者。把LL1实现一遍你就会明白为什么教材要花一整章讲First集和Follow集——表面是集合运算实际是文法可预测性的判断依据。下面从集合计算开始一步步把整个分析器搭起来。2. 从文法到预测分析表First集与Follow集的计算实现很多同学写LL1直接跳去写驱动循环结果预测分析表构造不对一跑就崩。First集和Follow集是整个实验的地基这两套集合算错一个符号后面驱动循环里查表就会得到错误产生式或者查不到表项。这一章先解决集合计算并且用不动点迭代实现避免文法里出现互相引用时递归调用栈溢出。2.1 First集计算为什么要用不动点迭代First集的定义是一个文法符号能推导出的所有终结符首符的集合。对于产生式A - X1 X2 ... Xn求First(A)时要依次看右部每个符号如果X1是终结符直接把它加入First(A)并结束如果X1是非终结符把First(X1)里除ε以外的符号全部并入First(A)只有当X1能推导出ε时才继续看X2。右部所有符号都能推导出ε时ε才加入First(A)。由于文法里可能存在A - B、B - A这种互引用按教材上那种“逐个产生式推导”的方式手算容易漏项。更稳的做法是循环扫描所有产生式直到所有集合都不再变化也就是不动点迭代。下面是Java实现/** * 迭代计算所有非终结符的FIRST集 * productions: ListProductionProduction包含left(String)和right(ListString) * nonTerminals / terminals: 预先收集好的符号集合 */ public MapString, SetString buildFirstSet() { MapString, SetString first new HashMap(); for (String nt : nonTerminals) { first.put(nt, new HashSet()); } boolean changed true; while (changed) { changed false; for (Production p : productions) { SetString firstOfLeft first.get(p.left); // 右部是否所有符号都可空能推导出ε boolean allNullable true; for (String symbol : p.right) { if (terminals.contains(symbol)) { // 终结符直接加入ε不在这里处理 if (!symbol.equals(ε) firstOfLeft.add(symbol)) { changed true; } allNullable false; break; } // 非终结符把它的FIRST去掉ε后并入左部 for (String s : first.get(symbol)) { if (!s.equals(ε) firstOfLeft.add(s)) { changed true; } } // 该符号不能推导出ε停止继续向后扫描 if (!first.get(symbol).contains(ε)) { allNullable false; break; } } // 右部全部可空说明左部能推导出ε if (allNullable firstOfLeft.add(ε)) { changed true; } } } return first; }这段代码里最值得注意的就是allNullable标志。例如产生式E - T E | ε第二条产生式右部为空列表循环体不执行allNullable保持true于是ε被加入First(E)。如果右部是T E先处理TT的First不含ε于是allNullable置为false并break不会继续看E。外层while (changed)循环是这套实现的精髓。手写递归求First时遇到A - B且B - A这种文法直接栈溢出不动点迭代不会因为每个集合只增不减终结符数量有限迭代必然收敛。我一般会把最大迭代次数设为非终结符数量的两倍加一防止程序死循环实验里不必写这么严但心里要有这个数。2.2 Follow集计算看右侧和后继而不是看左侧Follow集的定义比First集绕一层对非终结符AFollow(A)是在所有句型中紧跟在A之后可能出现的终结符集合。它不是看A产生什么而是看A出现在哪些产生式的右部、A后面跟了什么。教材给的两条规则要记牢。规则一对产生式A - α B β把First(β)中除ε以外的符号并入Follow(B)。规则二如果A - α B或者A - α B β且β能推导出ε那么把Follow(A)并入Follow(B)。另外开始符号的Follow集里要放上输入结束符#。规则二很容易被忽略尤其是“β能推导出ε”这条。因为Follow集也存在传播关系同样用不动点迭代实现/** * 计算FOLLOW集依赖buildFirstSet的结果 * startSymbol: 文法开始符号输入串结尾符记为# */ public MapString, SetString buildFollowSet( MapString, SetString first) { MapString, SetString follow new HashMap(); for (String nt : nonTerminals) { follow.put(nt, new HashSet()); } follow.get(startSymbol).add(#); boolean changed true; while (changed) { changed false; for (Production p : productions) { ListString right p.right; for (int i 0; i right.size(); i) { String B right.get(i); if (!nonTerminals.contains(B)) continue; SetString followB follow.get(B); if (i right.size() - 1) { // 规则二的第一种情况A - α BB在末尾 for (String s : follow.get(p.left)) { if (followB.add(s)) changed true; } } else { // 规则一A - α B β取FIRST(β)去掉ε ListString beta right.subList(i 1, right.size()); SetString firstBeta computeFirstOfSequence(beta, first); for (String s : firstBeta) { if (!s.equals(ε) followB.add(s)) { changed true; } } // 规则二的第二种情况β可推导出ε if (firstBeta.contains(ε)) { for (String s : follow.get(p.left)) { if (followB.add(s)) changed true; } } } } } } return follow; }这里新增了一个辅助函数computeFirstOfSequence(beta, first)它计算一个符号序列的First集从beta第一个符号开始并入其First如果可空则继续处理下一个直到遇到不可空符号或序列结束若整个序列可空则返回结果里包含ε。这个函数是对2.1节右部处理逻辑的复用写成一个独立方法能让Follow计算代码清晰很多。我见过有人把Follow计算写成只遍历一遍产生式结果E - T E这种产生式里E的Follow迟迟算不出完整的#和)。原因就是Follow信息跨多个产生式传播一轮扫描不够。所以这里必须也用while (changed)包起来。2.3 验证计算结果拿经典算术文法对答案实现完两套集合后先别急着写驱动用一个标准文法做自检。下面这套消除左递归后的算术表达式文法是编译原理教材第三版的常见例题也适合用来验证代码E - T E E - T E | ε T - F T T - * F T | ε F - ( E ) | id用上面的代码跑完后关键集合应该得到这些值非终结符First集Follow集E{ (, id }{ #, ) }E{ , ε }{ #, ) }T{ (, id }{ , #, ) }T{ *, ε }{ , #, ) }F{ (, id }{ *, , #, ) }注意F的Follow里有*因为来自T - * F T中F后面直接跟了T而T可空所以Follow(T)的、#、)也传播给了F。如果你的输出里F的Follow缺了#或)基本可以断定规则二没实现完整回头检查计算顺序。3. 用 Java 跑通 LL1 驱动预测分析表与查表循环怎么落地集合算对了预测分析表就只是个“填格子”的过程。LL1分析器核心就三步查表、压栈、匹配。但细节坑很多比如产生式右部压栈为什么要逆序、ε产生式怎么处理、表项冲突怎么发现。这一章直接给出可运行的Java代码。3.1 构造预测分析表填表规则与冲突检测预测分析表是一个二维矩阵行是非终结符列是终结符加#。对每个产生式A - α按两条规则填对First(α)中每个终结符a把该产生式填入M[A, a]。如果ε在First(α)中则对Follow(A)中每个符号b把该产生式填入M[A, b]。第二条规则是LL1分析的特殊之处。E - ε这个产生式不匹配任何终结符它只在遇到Follow(E)里的符号时才“空降”弹栈让E从栈中消失继续处理后续输入。代码实现/** * 构造预测分析表 * 返回类型: Map非终结符, Map终结符, 产生式 * 如果同一个格子被两个不同产生式占用说明文法不是LL(1) */ public MapString, MapString, Production buildTable( MapString, SetString first, MapString, SetString follow) { MapString, MapString, Production table new HashMap(); for (Production p : productions) { SetString firstOfRight computeFirstOfSequence(p.right, first); // 规则一FIRST(α)中每个终结符都填该产生式 for (String a : firstOfRight) { if (a.equals(ε)) continue; Production old putIntoTable(table, p, p.left, a); if (old ! null !old.equals(p)) { throw new IllegalStateException( 文法不是LL(1)M[ p.left , a ] 冲突); } } // 规则二ε在FIRST(α)中时FOLLOW(A)的每个符号都填该产生式 if (firstOfRight.contains(ε)) { for (String b : follow.get(p.left)) { Production old putIntoTable(table, p, p.left, b); if (old ! null !old.equals(p)) { throw new IllegalStateException( 文法不是LL(1)M[ p.left , b ] 冲突); } } } } return table; } private Production putIntoTable( MapString, MapString, Production table, Production p, String nonTerminal, String terminal) { MapString, Production row table.computeIfAbsent(nonTerminal, k - new HashMap()); return row.put(terminal, p); }这里的冲突检测是血泪经验。很多同学遇到文法含左递归或公共前缀时驱动跑出来行为诡异就是因为表里同一个格子被后一个产生式覆盖了前一个静默丢失。用put返回旧值来判断冲突能让你在构造表时立刻知道文法不是LL1而不是在分析阶段排查半天。3.2 LL1驱动循环栈、输入缓冲区、查表的机械步骤预测分析表建好后驱动算法可以描述成一个循环初始化栈压入#再压入开始符号输入串末尾加#。取栈顶符号X和当前输入符号a。若X是终结符且等于a弹栈读下一个输入符号。若X是非终结符查M[X, a]找到产生式则弹栈把右部逆序压栈ε不压查不到则报错。反复执行直到栈空栈空且输入读完则接受。逆序压栈是新手最容易想不通的地方。因为栈是后进先出产生式右部第一个符号应最早被展开处理所以它必须最后入栈。比如面对E - T E压栈顺序是E、T、这样在栈顶下一步就能和输入匹配。核心代码public boolean parse(String inputWithSpaces, MapString, MapString, Production table) { DequeString stack new ArrayDeque(); stack.push(#); stack.push(startSymbol); // 输入串建议用空格分词如 id id * id String[] tokens inputWithSpaces.split( ); ListString inputList new ArrayList(Arrays.asList(tokens)); inputList.add(#); int pos 0; System.out.println( 分析步骤 ); while (!stack.isEmpty()) { String top stack.pop(); String lookahead inputList.get(pos); if (terminals.contains(top) || top.equals(#)) { // 栈顶是终结符必须和当前输入匹配 if (top.equals(lookahead)) { pos; System.out.println(top 匹配成功); } else { System.err.println(语法错误期望 top 但读到 lookahead 位置 pos); return false; } } else { // 栈顶是非终结符查表 Production p table.get(top).get(lookahead); if (p null) { System.err.println(语法错误非终结符 top 无法接受 lookahead 位置 pos); return false; } // 右部逆序压栈ε不压入 ListString right new ArrayList(p.right); Collections.reverse(right); for (String symbol : right) { if (!symbol.equals(ε)) stack.push(symbol); } System.out.println(top - p.right 应用); } } // 正常情况下循环结束时 pos 指向 #输入也被消费完 return pos inputList.size() - 1; }这个驱动函数有几个地方要注意。第一tokens按空格切分实验里最好在测试代码里把输入写成id id * id这种空格分隔形式避免自己写词法切分引入额外bug。第二出错信息里带上当前token和第几个位置排错时一眼看出问题出现在哪个输入符号附近。第三while循环退出条件只有stack.isEmpty()如果输入串提前消费完而栈里还有非终结符查表会因lookahead越界报错所以输入末尾加#是必须的。3.3 手动走一遍id id * id验证驱动逻辑用3.1节的算术表达式文法跑id id * id前几步应该是这样步骤栈栈顶在左剩余输入动作1E #id id * id #E - T E2E T #id id * id #T - F T3E T F #id id * id #F - id4E T id #id id * id #匹配 id5E T # id * id #T - ε查 Follow(T) 得 第五步是关键栈顶T面对输入M[T, ]里存的产生式是T - ε所以右部为空什么都不压栈T直接消失成功把处理权交还给E。这就是LL1处理空产生式的典型过程。如果你在驱动里把ε当作普通符号压栈这一步就会永远匹配不上程序直接报错。4. LL1 实验最容易翻车的四个坑从死循环到文件编码LL1实现本身不算复杂但翻车点都很隐蔽往往不是算法大错而是某些边界条件没处理。这一章写我在这个实验里最常见的四个坑每条按现象、原因、解决来写可以直接对照排查。4.1 左递归文法让驱动进程永远停不下来现象程序跑某个文法或某条输入时卡住栈无限增长内存耗尽或CPU占满。比如直接用E - E T | T这个产生式构造文法。原因左递归产生式E - E T的First(E)里包含E自身能推导出的终结符填表时 M[E, ] 会指向E - E T。驱动循环每次遇到E都把它展开成E TE重新进栈加上原有的E栈里E越堆越多永远消不下去。解决先把文法改写成等价的无左递归形式。标准做法是把左递归转成右递归E - E α | β改写成E - β E和E - α E | ε。改写后重新计算First和Follow再建表问题随即消失。注意不只是直接左递归E - A T且A - E这种间接左递归也要处理实验一般不要求但要心里有数。4.2 公共前缀导致表项冲突现象构造预测分析表时明明没报错驱动跑一些输入时采用了错误的产生式导致中间某一步栈顶和输入无法匹配。原因文法存在公共前缀比如S - if E then S else S | if E then S两个产生式右部的First集都包含if表项M[S, if]被后一个产生式覆盖前一个分支永远走不到或者做了冲突检测直接抛异常。解决提取左因子将公共部分提出来S - if E then S SS - else S | ε。提取后要重新算集合和表。这里有一个排查技巧冲突检测抛出的异常消息里会打印非终结符和终结符比如M[S, if] 冲突看到这个组合直接去文法里找以if开头的多个产生式即可。4.3 ε的空串传播顺序导致Follow集算错现象某个非终结符的Follow集里多了或者少了终结符表现是输入串该接受时被拒绝或者反过来接受了非法串。例如3.3节的文法F的Follow少了#。原因Follow计算依赖First的可空性判断而可空性本身需要多次迭代才能传播到位。如果只遍历一遍产生式T - * F T | ε这种规则中F的Follow要等T的Follow先算好才能完整传播顺序稍有不符就漏项。解决全部改用不动点迭代这一点在2.2节已经强调。复查方式很简单把每个非终结符的Follow集打印出来对照教材给的答案核对。不要试图通过调整产生式遍历顺序来“碰巧”算对因为文法一换就坏。4.4 从文件读文法时被BOM和编码坑现象在main方法里硬编码文法字符串时一切正常改成从文件读文法后第一条产生式的左部怎么都匹配不上报“未知非终结符”。用文本编辑器看文件内容完全正常。原因Windows记事本保存UTF-8文件时会在文件头写入三个字节的BOMEF BB BFJava读取后第一个字符变成不可见的\uFEFF。如果你用这个字符去查非终结符集合自然查不到。同理文件里如果有中文注释用FileReader按GBK读取时也可能读到乱码交换进去。解决读取文法文件时跳过BOM头或者统一用UTF-8无BOM编码保存。代码里可以这样处理BufferedReader reader new BufferedReader( new InputStreamReader( new FileInputStream(file), StandardCharsets.UTF_8)); // 处理BOM读第一行前检查首字符 String line reader.readLine(); if (line ! null line.startsWith(\uFEFF)) { line line.substring(1); }这一条属于玄学翻车但每年都有人耗一下午在这里。多花30秒规范化输入编码能省掉大量无意义的排查时间。5. 把 LL1 从跑通做到能排错跟踪打印与错误定位技巧实验做到能跑通几条合法输入只是及格真正拉开差距的是非法输入出现时你能不能快速定位问题。这一章讲两个我常用的排错技巧都改动量极小但对调试效率提升明显。第一个技巧是在驱动循环里加一个计数器每步打印当前序号、栈内容、剩余输入和被选用的产生式。前面3.3节的跟踪表就是手工模拟的实际程序里把栈打印成字符串即可。调试时盯着栈的变化能立刻看出某一步是不是错误地压入了不该出现的符号或者该弹栈时没弹。第二个技巧是让错误信息携带“期望-实际”对。当查表失败时报错信息写成第 pos 个token附近非终结符 E 期望接受 、#、)但读到 id。这里的期望集合就是Follow(E)实际读到的是当前输入token。这样做的好处是定位不靠肉眼扫整个分析栈而是直接告诉你文法在哪个非终结符上、什么上下文环境下出的错。我在实验里把这条信息输出到控制台后非法输入的排错时间缩短了至少一半。再进一步可以把预测分析表导出成文本文件检查。对每个非终结符打印一行“在哪些终结符下选择哪条产生式”人工扫一遍就能发现漏填的表项。这套方法不仅适用于课程实验后面你接触递归下降分析器或者手写JSON解析器时同样能用——把“当前状态”和“期望输入”打印出来永远是排查解析问题最快的方式。我自己的习惯是写完LL1后先用合法输入跑通再用三条非法输入故意触发报错确认错误信息里能看到期望集合和实际token才算这个实验真正结束。这个习惯后来帮我解决了不少实际项目里的配置解析问题——解析器好不好用不只看它能接受什么更看它拒绝时能不能告诉你为什么。希望帮到你。本文还有配套的精品资源点击获取