LL(1)语法分析器实现全流程：从FIRST/FOLLOW到预测分析表

简介压缩包内是编译原理实验二“LL1语法分析器”的完整实现面向高校计算机专业学生及编译原理课程设计者解决LL1文法预测分析表构造、输入串合法性判断与语法错误报错问题。整包共十三个文件包含可直接运行的可执行程序、源代码、实验报告文档、程序设计思想文档、开发环境工程配置文件以及讲解视频压缩包总大小二十四点八一兆字节。其中源码支持输入给定文法后自动生成预测分析表并对从键盘读入的输入串判断是否为该文法的句子正确则通过、错误则报错讲解视频完整演示操作流程实验报告与思想文档则详细梳理了从首符号集、后跟符号集到预测分析表构建的设计思路。目前已有三千一百零一人学习适合需要完成课程实验、撰写报告或深入理解自顶向下语法分析原理的读者参考。1. LL(1)语法分析器是编译原理实验里第一道“决策题”第一次看到“编译原理实验二 LL(1)语法分析器.zip”这个任务名时我一度以为把书上的预测分析算法抄进代码就够了。真开始写才发现这门实验要交付的不是一个能跑通的函数而是一台会判断句子合法性的小机器输入是词法分析器给的 token 串输出是“接受 / 拒绝”中途还要打印出每一步最左推导用的哪个产生式。做完它编译原理在你脑子里会从“会背定义”变成“能让定义跑起来”。这套东西适合三种人正被实验课卡住的学生、想补自顶向下语法分析短板的在职开发者以及单纯想用几百行代码搭出完整语法分析骨架的人。2. 从文法到FIRST/FOLLOW集两套做法一条保命路线FIRST 集和 FOLLOW 集是 LL(1) 的地基。我的血泪经验是集合算错后面整条链路全废而且错误会藏得很深——你以为是主循环的问题其实是集合多了一个 ε、少了一个终结符。所以动手写代码之前先拿一道小文法手推一遍再用程序去校验。两条路都走通后面的预测分析表和分析栈才敢说稳。2.1 先用手推一组集合小文法的 FIRST 不该落在代码里很多学校的实验题会给一个带左递归的算术表达式文法比如最经典的这组E - E T | T T - T * F | F F - ( E ) | idLL(1) 不允许左递归常见做法是先把直接左递归改成右递归E - T E E - T E | ε T - F T T - * F T | ε F - ( E ) | id这套文法是绝大多数“LL(1)语法分析器”作业的默认样本先用它手推。求 FIRST 时从最底层的 F 往上推FIRST(F) { (, id } FIRST(T) FIRST(F) { (, id } FIRST(E) FIRST(T) { (, id } FIRST(E) { , ε } FIRST(T) { *, ε }求 FOLLOW 时先把输入结束符放进开始符FOLLOW(E) { ), $ } FOLLOW(E) FOLLOW(E) { ), $ } FOLLOW(T) { , ), $ } FOLLOW(T) FOLLOW(T) { , ), $ } FOLLOW(F) { *, , ), $ }容易漏的是 FOLLOW(F)。在产生式T - F T里F 后面跟的是 T所以 FIRST(T) 里的 * 要进 FOLLOW(F)又因为 T 可以推导出 ε所以 FOLLOW(T) 整体要继承给 F。这就是课本里反复强调的“β 可空时把 FOLLOW(A) 继承给 FOLLOW(B)”。手推的价值是让你对每个集合的来历有直觉。代码跑出来的数字再漂亮也替代不了这一步——后面填表一旦程序报“冲突”你得能一眼看出是 FIRST 的问题还是 FOLLOW 的问题。2.2 用 Java 自动求 FIRST/FOLLOW集合迭代计算的机械化如果你在“java编译原理”这个搜索组合里点进来多半是想用 Java 交差。这挺合理HashMap、HashSet、ArrayDeque 正好覆盖文法、集合、栈三类数据结构基本不用自己写链表。下面这个FirstFollowCalculator是自动求 FIRST/FOLLOW 的最小实现核心思想是“不动点迭代”——不断把新符号加入集合直到所有集合都不再变化。import java.util.*; public class FirstFollowCalculator { MapString, ListListString grammar new HashMap(); SetString nonTerminals new HashSet(); SetString terminals new HashSet(); MapString, SetString first new HashMap(); MapString, SetString follow new HashMap(); String startSymbol; public FirstFollowCalculator(String start) { startSymbol start; } public void addRule(String lhs, String... rhs) { grammar.computeIfAbsent(lhs, k - new ArrayList()) .add(new ArrayList(Arrays.asList(rhs))); nonTerminals.add(lhs); for (String s : rhs) { if (!s.equals(ε) !isNonTerminal(s)) { terminals.add(s); } } } public boolean isNonTerminal(String s) { return !s.equals(ε) Character.isUpperCase(s.charAt(0)); } public void computeFirst() { for (String t : terminals) { first.put(t, new HashSet(Collections.singleton(t))); } for (String nt : nonTerminals) { first.put(nt, new HashSet()); } boolean changed true; while (changed) { changed false; for (Map.EntryString, ListListString e : grammar.entrySet()) { String A e.getKey(); for (ListString rhs : e.getValue()) { SetString s firstOfSequence(rhs); if (first.get(A).addAll(s)) { changed true; } } } } } public SetString firstOfSequence(ListString seq) { SetString res new HashSet(); if (seq.isEmpty()) { res.add(ε); return res; } boolean allNullable true; for (String sym : seq) { SetString fs first.get(sym); SetString add new HashSet(fs); add.remove(ε); res.addAll(add); if (!fs.contains(ε)) { allNullable false; break; } } if (allNullable) { res.add(ε); } return res; } public void computeFollow() { for (String nt : nonTerminals) { follow.put(nt, new HashSet()); } follow.get(startSymbol).add($); boolean changed true; while (changed) { changed false; for (Map.EntryString, ListListString e : grammar.entrySet()) { String A e.getKey(); for (ListString rhs : e.getValue()) { for (int i 0; i rhs.size(); i) { String B rhs.get(i); if (!isNonTerminal(B)) { continue; } SetString after firstOfSequence(rhs.subList(i 1, rhs.size())); SetString add new HashSet(after); add.remove(ε); if (follow.get(B).addAll(add)) { changed true; } if (after.contains(ε)) { if (follow.get(B).addAll(follow.get(A))) { changed true; } } } } } } } }关键在两个点。第一firstOfSequence处理“符号序列可空”时不能简单把每个符号的 FIRST 并起来就完事中间某个符号不可空后面符号的 FIRST 就进不来序列整体也不会有 ε。第二FOLLOW 迭代里rhs.subList(i 1, rhs.size())可能是空列表这时firstOfSequence返回{ε}正好表达“右边没有符号左侧非终结符继承 FOLLOW(A)”。这套实现不递归、不依赖调用深度遇到几十条产生式的文法也不会栈溢出。唯一要注意的是非终结符判定用了“首字符大写”约定所以终结符id、、(都不能大写开头如果你想用ID表示标识符得先改成小写或换一种判定方式。2.3 ε的传递规则是算错 FIRST/FOLLOW 的头号原因手推和编程里翻车最多的都是 ε 的传递而不是那些长产生式。举一个典型反例S - A B A - a | ε B - b | ε如果只把直接产生式A - ε里的 ε 放进 FIRST(A)而不继续向上传递会得到 FIRST(S) 只有{a}。正确结果应该是{a, b, ε}因为 A 可空B 的b会进入 FIRST(S)A、B 都可空整个 S 可空。这个错误在代码里的表现是firstOfSequence遍历到第一个可空符号就 break或者把 ε 无脑留在结果集里。我上面实现的写法是“把当前符号 FIRST 中的 ε 去掉后再并集”并用allNullable单独记录“是否全部可空”最后才把 ε 加回去。这样空串不会污染中间阶段的集合逻辑也跟课本定义对齐。FOLLOW 侧的 ε 传递同样隐蔽。比如S - A B里若 B 可空FOLLOW(A) 必须继承 FOLLOW(S)如果漏掉“B 可空”这个条件A 后面跟的结束符就永远算不全。这类问题在实验报告里最难解释因为程序不会报错只会让某个输入串莫名其妙被拒绝。遇到这种情况先别调主循环回头把 FIRST 和 FOLLOW 逐条打出来跟手推结果对一遍。3. 预测分析表 M[A][a]从集合到二维决策表FIRST 和 FOLLOW 算完下一步是把它俩合成一张预测分析表。这张表是 LL(1) 分析器的“决策黑匣子”遇到非终结符 A 和当前输入 a查表就知道该用哪条产生式展开。表的构造规则就三条但第三条的触发条件值得反复确认。3.1 三步填表法FIRSTα、ε兜底、FOLLOW广播对文法里的每个产生式A - α按下面三步填表1. 对 FIRST(α) 里的每个终结符 a不含 ε把 A - α 填入 M[A, a] 2. 若 FIRST(α) 含 ε对 FOLLOW(A) 里的每个符号 a含 $把 A - α 填入 M[A, a] 3. 其余表项留空表示语法错误用前面那份消除了左递归的算术文法最终预测分析表长这样| | * | ( | ) | id | $ E | | | E-TE | | E-TE | E | E-TE| | | E-ε | | E-ε T | | | T-FT | | T-FT | T | T-ε | T-*FT| | T-ε | | T-ε F | | | F-(E) | | F-id |这张表要跟实验报告一起交的话注意id列和(列的内容经常被抄错。E 和 T 的第 1 条产生式一模一样都是E-TE和T-FT区别只在触发符号上E 和 T 的 ε 产生式则同时出现在/)/$和*/)/$三列里因为它们的 FOLLOW 集包含了这些符号。3.2 用 HashMap 实现稀疏预测分析表自带冲突检测一张二维表在代码里最常见的建模方式是MapString, MapString, ListString外层键是非终结符内层键是终结符值是产生式右部符号列表。稀疏表比二维数组更省空间也更方便做冲突检测。下面这个PredictiveTableBuilder直接复用FirstFollowCalculator的firstOfSequence把“FIRST(α) 是否含 ε”这件事交给上一章的代码处理builder 里不用再重复造轮子。import java.util.*; public class PredictiveTableBuilder { public MapString, MapString, ListString table new HashMap(); FirstFollowCalculator calc; public PredictiveTableBuilder(FirstFollowCalculator calc) { this.calc calc; } public void build() { for (String nt : calc.nonTerminals) { table.put(nt, new HashMap()); } for (String A : calc.nonTerminals) { for (ListString rhs : calc.grammar.get(A)) { SetString select new HashSet(calc.firstOfSequence(rhs)); if (select.contains(ε)) { select.remove(ε); select.addAll(calc.follow.get(A)); } for (String t : select) { if (t.equals(ε)) { continue; } ListString old table.get(A).put(t, rhs); if (old ! null !old.equals(rhs)) { throw new IllegalArgumentException( 表项 M[ A , t ] 冲突: old 和 rhs); } } } } } }这个select集合就是教材里常说的 SELECT 集SELECT(A - α) FIRST(α) - {ε} ∪ FOLLOW(A)当 FIRST(α) 含 ε 时。代码里先算 FIRST(α)如果含 ε 就移除并并入 FOLLOW(A)逻辑跟 3.1 的三步填表法一一对应不会漏。3.3 表项冲突等于文法不是 LL(1)别拿“覆盖”当修复put返回旧值这个特性是专门用来抓冲突的。很多初版代码写成table.get(A).put(t, rhs)遇到冲突静默覆盖程序能跑但文法已经被悄悄换了。一个 LL(1) 文法要求每个表项最多只能有一个产生式一旦冲突说明原文法存在左递归或公共左因子必须先改写文法而不是在表上做覆盖。最典型的情况是没消除左递归就拿来填表。比如直接对E - E T | T填表FIRST(ET) 和 FIRST(T) 里都含(、id于是 M[E, (] 和 M[E, id] 各有两个产生式builder 立刻抛异常。如果你拿到的是带左递归的题目原文第一件事就是做消除而不是把左递归产生式从表里删掉——删掉等于改文法但实验的判分点往往是你会不会自己把文法改对。另外说一句这张表只负责句法决策跟符号表还没关系符号表是语义分析阶段再接进来的东西。但在 LL(1) 实验里你能把表完整建出来并且能证明每个格子没有冲突语法分析的核心工作就已经完成一半了。4. 主循环与分析栈跑出最左推导实验报告才立得住有了预测分析表剩下的工作是一个循环维护一条分析栈不断比对栈顶符号和当前输入符号查表展开或匹配终结符。这一步是实验结果是否好看的关键——同样一个“接受”有人只打印一个布尔值有人能打印出完整的最左推导过程后者在课程设计报告里的说服力完全不同。4.1 最小可运行的 LL(1) 主循环栈、表、输入三者如何联动Ll1Parser是我一般推荐的写法初始化时把$压入栈底再把开始符E压栈输入串末尾补一个$然后循环处理直到栈空。import java.util.*; public class Ll1Parser { FirstFollowCalculator calc; PredictiveTableBuilder builder; DequeString stack new ArrayDeque(); ListString tokens; int index 0; int step 0; int maxSteps 1000; public Ll1Parser(FirstFollowCalculator calc, PredictiveTableBuilder builder, ListString input) { this.calc calc; this.builder builder; tokens new ArrayList(input); tokens.add($); } public boolean parse() { stack.push($); stack.push(calc.startSymbol); while (!stack.isEmpty()) { if (step maxSteps) { System.out.println(超过最大步数判定失败); return false; } String top stack.peek(); String lookahead tokens.get(index); if (top.equals(lookahead)) { System.out.printf(步骤 %d: 匹配 %s%n, step, top); stack.pop(); index; } else if (!calc.isNonTerminal(top)) { System.out.printf(步骤 %d: 栈顶终结符 %s 与输入 %s 不匹配跳过输入%n, step, top, lookahead); if (index tokens.size() - 1) { index; } else { stack.pop(); } } else { ListString production builder.table.get(top).get(lookahead); if (production null) { System.out.printf(步骤 %d: 表项 M[%s, %s] 为空%n, step, top, lookahead); if (calc.follow.get(top).contains(lookahead)) { stack.pop(); } else if (index tokens.size() - 1) { index; } else { stack.pop(); } } else { System.out.printf(步骤 %d: 展开 %s - %s%n, step, top, production); stack.pop(); for (int i production.size() - 1; i 0; i--) { String sym production.get(i); if (!sym.equals(ε)) { stack.push(sym); } } } } } return index tokens.size(); } }循环里只有三种情况边界条件写清楚后基本不会越界。栈顶是终结符且等于输入就“匹配”弹出栈顶并消费输入栈顶是终结符但不等于输入说明输入里混进了非终结符不该出现的位置跳过这个非法输入栈顶是非终结符则查表查到产生式就弹出非终结符再把右部符号逆序压栈。逆序压栈是为了让下一个要匹配的符号出现在栈顶这正好对应最左推导的顺序。三个参数要解释一下。maxSteps1000是兜底护栏用来防止左递归残余或错误恢复逻辑不完善时无限循环index tokens.size() - 1用来保证tokens.get(index)不越界因为末尾那个$是最后一个有效下标production.size() - 1的逆序遍历时遇到ε直接不压栈避免把空产生式再压进去造成原地踏步。4.2 输出“最左推导”的两种写法以及步数上限实验报告中“最左推导”有两种展示方式。第一种就是上面代码里的做法打印“步骤 动作 栈内容 剩余输入”因为每一步展开的都是当前栈顶也就是当前句型最左边的非终结符所以这个日志天然就是最左推导的轨迹。第二种是维护一个StringBuilder保存完整句型每次展开时把句型里的第一个非终结符替换成对应右部打印成教材里那种E T E F T E id T E第二种好看但实现时要处理多字符符号替换位置容易错我一般只在课程设计报告需要“展示过程”时才用。第一种日志虽然朴实但信息量更大判分老师能看到每一步用到的产生式和栈状态反而更好确认你的分析器是真的在按 LL(1) 流程工作。maxSteps这个参数建议做成构造函数的入参而不是写死在类里。调试左递归文法时可以调大到 10000 看它怎么死循环交作业时调回 1000 保证程序不会卡死。每次改动文法后顺手把 maxSteps 调小跑一遍能尽早暴露表冲突和递归问题。4.3 错误恢复用 FOLLOW 集做同步符号能跑满所有实验要求很多实验只要求分析器“报错”但如果你想让程序像一个真正的编译器那样报完错还能继续分析就要做错误恢复。LL(1) 最常见的策略是“FOLLOW 集同步”当栈顶是 A 且输入是 a而 M[A,a] 为空时看 a 是否在 FOLLOW(A) 里——如果是说明 A 已经推导完把 A 弹出栈如果不是丢掉输入符号 a继续看下一个输入。上面代码的错误处理分支就是这套逻辑。比课本再多加一层保障当输入已经只剩$但仍匹配不上时直接弹栈而不是继续跳输入否则会卡在“栈空但 index 没到末尾”的死局。错误恢复跑通后你可以在实验报告里写“程序能连续报出三个错误而不崩溃”这通常是加分项。5. 避坑LL(1) 实验最容易翻车的五个细节这个实验的坑很集中多数翻车点都围绕“集合算错”“字符串比较”“空产生式处理”三件事。下面五条是我见过出现频率最高的按现象到解决列出来。5.1 现象表项冲突被 HashMap 静默覆盖文法“假通过”程序跑几个正确用例都通过换个输入就接受了本该拒绝的句子。打印预测分析表发现某个格子只剩一个产生式另一个产生式不见了。原因table.get(A).put(t, rhs)的返回值没检查。Java 的put本身就会覆盖旧值不是报错。二义性文法、左递归文法、公共左因子文法这三种情况都会触发覆盖但被覆盖后程序表面不报错问题会延迟到主循环才暴露。解决填表时检查put的返回值如 3.2 的代码所示冲突直接抛异常。这一步能让你在第一时间知道“文法有问题”而不是把时间耗在调主循环上。消除左递归、提取公共左因子之后冲突自然消失。5.2 现象FOLLOW 集多出一个 # 或 $程序提前接受输入串明明还有好几个符号没消费程序却返回接受或者$和#在集合里同时出现导致某些输入被诡异放行。原因输入结束符被当成普通终结符写进了产生式右部或者你同时用了$和#两个符号表示结束FOLLOW 计算时两个都被传播开了。很多教材用#代码里用$一旦混用终结符集合里同时存在$和#FOLLOW 集就被污染了。解决在程序里定义一个常量EOF $只把它放进follow.get(startSymbol)永远不出现在产生式右部。拿到作业题目先看一眼它规定用$还是#统一改写不要两边混着来。5.3 现象左递归文法“看起来也能跑通”但一提交就翻车直接用题目给的E - E T | T建表builder 抛冲突把冲突产生式删掉后程序能跑几个用例但遇到id id这种简单输入步数上限被触发或输出顺序明显不对。原因LL(1) 的核心假设就是“从左到右、最左推导、每次看一个符号”左递归会让 FIRST 集合自己撞自己表项必定冲突。删产生式是掩耳盗铃因为文法被改后语言已经变了。解决先消除左递归再算集合这是实验题里默认要求的一步。判断一个文法要不要做消除可以看它有没有形如A - Aα的直接左递归或者两条不同产生式右部有相同前缀。5.4 现象空产生式展开后程序一直在“原地踏步”日志里连续几十行都是一种“展开 A - ε”步数逼近 maxSteps程序不崩溃也不前进。原因A - ε被压栈后如果代码没有把它从栈里真正弹出或者弹出后没有改变输入位置而当前输入又恰好不在 FOLLOW(A) 里下一次循环 A 又会以同样方式被展开形成死循环。解决展开产生式时先stack.pop()再压右部ε直接跳过不压栈。另外在错误恢复分支里优先“跳输入”而不是“弹栈顶”两条路交替使用才不会卡住。maxSteps 作为兜底一旦触发就打印当前栈状态方便定位到底卡在哪个符号上。5.5 现象id 和终结符永远匹配不上报错信息像天书代码逻辑看着完全正确输出却总是“M[T, id] 为空”或者明明输入是idid第一轮匹配就失败。原因Java 的比较的是引用不是字符串内容。从输入串切出来的id和文法表里的id可能不是同一个对象即使内容相同也可能返回 false。这类错误在String比较里出现频率极高教科书不会写但实验课上一抓一大把。解决所有符号比较一律用equals主循环里的top.equals(lookahead)、表项 key 的get、集合的contains都别用。想更稳妥一点可以把终结符定义成enum但普通实验用String.equals就完全够了。6. 收尾给 LL(1) 分析器写一套自动验证比手动点“运行”有用分析器写完第一件事不是拿两个用例试跑而是写一个自动验证的入口把已知文法、预期表项、正反用例全部断言进去。这样每次改代码后跑一次比手点“运行”按钮高效得多也能防止你调好一个用例、改坏另一个用例。import java.util.*; public class Ll1Verifier { public static void main(String[] args) { FirstFollowCalculator calc new FirstFollowCalculator(E); calc.addRule(E, T, E); calc.addRule(E, , T, E); calc.addRule(E, ε); calc.addRule(T, F, T); calc.addRule(T, *, F, T); calc.addRule(T, ε); calc.addRule(F, (, E, )); calc.addRule(F, id); calc.computeFirst(); calc.computeFollow(); PredictiveTableBuilder builder new PredictiveTableBuilder(calc); builder.build(); assert builder.table.get(E).get(id) .equals(Arrays.asList(T, E)) : E[id] 表项错误; assert builder.table.get(E).get() .equals(Arrays.asList(, T, E)) : E[] 表项错误; Ll1Parser ok new Ll1Parser(calc, builder, Arrays.asList(id, , id, *, id)); assert ok.parse() : 合法输入被拒绝; Ll1Parser bad new Ll1Parser(calc, builder, Arrays.asList(id, , *)); assert !bad.parse() : 非法输入被接受; System.out.println(验证通过); } }.java里直接写assert有个坑Java 默认不开启断言必须用java -ea Ll1Verifier运行否则所有断言静默跳过。这也是我当年踩过的坑代码白写了半天还以为验证全过。跑起来之后再用随机生成器造几十条表达式分成“合法组”和“非法组”挨个过一遍比提交后等判分反馈踏实得多。验证脚本放得越早后面调整文法时越敢动手。希望这些经验能让你少走一点我第一次做这个实验时走过的弯路祝实验顺利。本文还有配套的精品资源点击获取