企业官网建设流程全解析

简介：压缩包内是编译原理实验二“LL（1）语法分析器”的完整实现，面向高校计算机专业学生及编译原理课程设计者，解决LL（1）文法预测分析表构造、输入串合法性判断与语法错误报错问题。整包共十三个文件，包含可直接运行的可执行程序、源代码、实验报告文档、程序设计思想文档、开发环境工程配置文件以及讲解视频，压缩包总大小二十四点八一兆字节。其中源码支持输入给定文法后自动生成预测分析表，并对从键盘读入的输入串判断是否为该文法的句子，正确则通过、错误则报错；讲解视频完整演示操作流程，实验报告与思想文档则详细梳理了从首符号集、后跟符号集到预测分析表构建的设计思路。目前已有三千一百零一人学习，适合需要完成课程实验、撰写报告或深入理解自顶向下语法分析原理的读者参考。

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 ) | id

LL(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 { Map<String, List<List<String>>> grammar = new HashMap<>(); Set<String> nonTerminals = new HashSet<>(); Set<String> terminals = new HashSet<>(); Map<String, Set<String>> first = new HashMap<>(); Map<String, Set<String>> 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.Entry<String, List<List<String>>> e : grammar.entrySet()) { String A = e.getKey(); for (List<String> rhs : e.getValue()) { Set<String> s = firstOfSequence(rhs); if (first.get(A).addAll(s)) { changed = true; } } } } } public Set<String> firstOfSequence(List<String> seq) { Set<String> res = new HashSet<>(); if (seq.isEmpty()) { res.add("ε"); return res; } boolean allNullable = true; for (String sym : seq) { Set<String> fs = first.get(sym); Set<String> 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.Entry<String, List<List<String>>> e : grammar.entrySet()) { String A = e.getKey(); for (List<String> rhs : e.getValue()) { for (int i = 0; i < rhs.size(); i++) { String B = rhs.get(i); if (!isNonTerminal(B)) { continue; } Set<String> after = firstOfSequence(rhs.subList(i + 1, rhs.size())); Set<String> 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 实现稀疏预测分析表，自带冲突检测

一张二维表在代码里最常见的建模方式是Map<String, Map<String, List<String>>>：外层键是非终结符，内层键是终结符，值是产生式右部符号列表。稀疏表比二维数组更省空间，也更方便做冲突检测。

下面这个PredictiveTableBuilder直接复用FirstFollowCalculator的firstOfSequence，把“FIRST(α) 是否含 ε”这件事交给上一章的代码处理，builder 里不用再重复造轮子。

import java.util.*; public class PredictiveTableBuilder { public Map<String, Map<String, List<String>>> 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 (List<String> rhs : calc.grammar.get(A)) { Set<String> 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; } List<String> 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(E+T) 和 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; Deque<String> stack = new ArrayDeque<>(); List<String> tokens; int index = 0; int step = 0; int maxSteps = 1000; public Ll1Parser(FirstFollowCalculator calc, PredictiveTableBuilder builder, List<String> 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 { List<String> 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(); } }

循环里只有三种情况，边界条件写清楚后基本不会越界。栈顶是终结符且等于输入，就“匹配”，弹出栈顶并消费输入；栈顶是终结符但不等于输入，说明输入里混进了非终结符不该出现的位置，跳过这个非法输入；栈顶是非终结符则查表，查到产生式就弹出非终结符，再把右部符号逆序压栈。逆序压栈是为了让下一个要匹配的符号出现在栈顶，这正好对应最左推导的顺序。

三个参数要解释一下。maxSteps=1000是兜底护栏，用来防止左递归残余或错误恢复逻辑不完善时无限循环；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] 为空”，或者明明输入是id+id，第一轮匹配就失败。

原因：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运行，否则所有断言静默跳过。这也是我当年踩过的坑，代码白写了半天，还以为验证全过。跑起来之后，再用随机生成器造几十条表达式，分成“合法组”和“非法组”挨个过一遍，比提交后等判分反馈踏实得多。验证脚本放得越早，后面调整文法时越敢动手。希望这些经验，能让你少走一点我第一次做这个实验时走过的弯路，祝实验顺利。

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