企业官网建设流程全解析

简介：面向编译原理课程实验与SLR(1)语法分析学习者的Java实现资料包，重点解决自底向上语法分析中文法表示、消除左递归与左公因子、FOLLOW集和闭包计算、GOTO集构造、分析表生成及移进归约解析流程等关键问题。压缩包共85个文件，以76个Java源码为主体，配合6个XML配置、1个iml项目文件及少量说明文件，整体约40KB，结构轻量，便于按模块阅读与调试。已有523人学习，适合需要对照课程实验理解SLR(1)分析器实现细节的读者。源码可帮助梳理从文法预处理到分析表构建的完整链路，观察状态转换与归约动作的组织方式，并可作为实验报告、课程设计或期末复习的参考材料，提升对编译原理自底向上解析方法的直观认识。

1. 从一份跑不动的实验说起：SLR(1) 语法分析器到底难在哪

编译原理实验做到语法分析这一节，很多人是在这里第一次卡住的：文法给了E -> E+T | T，要求手工算 FIRST、FOLLOW，画出 LR(0) 项目集规范族，再填一张 SLR(1) 分析表。照着课件一步步抄还行，可只要换一条带左递归或者空产生式的文法，项目集个数就对不上，表里还会冒出移进-归约冲突，最后连“是文法本身不是 SLR(1)”还是“我自己算错了”都分不清。

这份用 Java 写的 SLR(1) 语法分析器实验包，做的事就是把上面这套流程从笔算搬进代码：读入文法，自动算出 FIRST/FOLLOW，构造项目集规范族，填出 ACTION/GOTO 表，再把 token 串喂进去跑完整的一遍移进-归约，每一步都打印出来。适合两类人——正在赶编译原理实验、想要一份能对答案的参考实现；以及想把表驱动解析真正写一遍、搞明白状态机怎么和栈配合的人。

2. 工程结构拆解：一个纯 Java 分析器的分层与数据模型

2.1 一条从字符串到 accept 的完整链路

拿到这个包，先别急着编译，把它的执行链路在脑子里过一遍，后面看代码会顺很多。整个程序其实是一条单向流水线：文本文法 → Grammar 对象 → FIRST/FOLLOW 集合 → LR(0) 项目集规范族 → SLR(1) 分析表 → 双栈驱动程序 → accept / error。

前面四步是纯粹的“算”，跟输入无关，只要文法不变，结果就不变，所以很多实现会把这四步的结果缓存下来或者干脆导出成文件。后面两步是“跑”，每来一个 token 串就要重新走一遍，靠的是前面算好的那张表。

这个划分方式带来的第一个好处是：调试的时候你能精确定位问题出在“算”还是“跑”。如果分析表打印出来就跟课件对不上，那不用往下看了，问题一定在 FIRST/FOLLOW 或者 CLOSURE 里；如果表是对的但跑出来的结果不对，那问题一定在栈操作或者词法切分上。血泪经验是很多人一上来就盯着主循环看，看了半天其实表本身就错了。

第二个好处是可测试。FirstFollow、LR0Builder、SLRTable这三块都是纯函数式的输入输出，给定文法就有唯一正确答案，特别适合写单元测试；而Parser依赖前面的结果，测试成本高一些。做二次开发时，我会优先保证前三个类的接口稳定，把变化都挡在 UI 和输入格式那一层。

2.2 目录结构与各包职责

这类实验工程通常不会用 Maven 或者 Gradle，就是一个src目录加javac直接编。常见做法是按职责分包，让每个包只依赖它下面那一层，别互相引用。典型的目录长这样：

依赖方向是ui → parse → lr → grammar，lexer被parse调用。这条线别反过来，一旦Grammar开始import某个 UI 类，后面想脱开控制台做 Web 版或者单元测试就会很难受。

提示：如果你拿到的版本把所有逻辑塞在一个Main.java里（实验作业里很常见），不建议推倒重来。先按这张表把方法一个个搬进对应的类，编译通过一次搬一个，比一次性重写安全得多。

2.3 三件套数据模型：Production、Item、ItemSet

整个算法最底层的三个类，写对了后面省一半事，写错了就是无穷无尽的玄学 bug。

Production的关键是必须有稳定编号。项目集里我们不会存字符串，存的是“第几条产生式的圆点在第几位”，编号就是这条产生式的身份证。

public class Production { private final int id; // 全局唯一编号，Item 判等靠它 private final String left; // 左部非终结符 private final List<String> right; // 右部符号序列，空列表表示 ε public Production(int id, String left, List<String> right) { this.id = id; this.left = left; this.right = Collections.unmodifiableList(new ArrayList<>(right)); } public int size() { return right.size(); } public String symbolAt(int i) { return right.get(i); } @Override public String toString() { return left + " -> " + (right.isEmpty() ? "ε" : String.join(" ", right)); } // getters 略 }

right用Collections.unmodifiableList包一层，是为了防止后面某个地方不小心add进去。这种 bug 极难查——你的产生式集合会在运行过程中悄悄变长，项目集数量跟着变，但代码逻辑看起来完全正常。参数上注意right存的是符号名字符串，不是索引，因为调试打印时要能直接看出E -> E + T。

Item是 LR(0) 项目，本质就两个整数：

public class Item { private final int prodId; // 对应哪条产生式 private final int dot; // 圆点位置，取值 0..right.size() public Item(int prodId, int dot) { this.prodId = prodId; this.dot = dot; } // 圆点后面的符号；已到末尾返回 null，表示这是可归约项目 public String nextSymbol(Grammar g) { Production p = g.getProduction(prodId); return dot < p.size() ? p.symbolAt(dot) : null; } public boolean isReduce() { return dot == -1 || isAtEnd; } @Override public boolean equals(Object o) { if (!(o instanceof Item)) return false; Item other = (Item) o; return prodId == other.prodId && dot == other.dot; } @Override public int hashCode() { return prodId * 31 + dot; } }

equals和hashCode必须一起重写，这是最容易翻车的地方。只重写equals的话，HashSet<Item>会用默认的对象地址算哈希，两个逻辑上相同的项目会被当成不同的，闭包里的去重就失效了，结果就是项目集永远收敛不了、状态数爆炸。prodId * 31 + dot这个写法不是为了什么哈希质量，就是为了让两个字段都参与计算，够用。

ItemSet负责给整个状态一个唯一标识，BFS 建规范族的时候靠它判重：

public class ItemSet { private final Set<Item> items = new LinkedHashSet<>(); private final String key; // 排序后拼接，作为 Map 的键 public ItemSet(Collection<Item> kernel) { items.addAll(kernel); this.key = buildKey(); } private String buildKey() { return items.stream() .map(i -> i.getProdId() + "@" + i.getDot()) .sorted() // 排序！否则同一集合会算出不同 key .collect(Collectors.joining(",")); } // getItems()、getKey() 略 }

这里的sorted()是硬性要求。项目集内部是LinkedHashSet，插入顺序取决于闭包的遍历顺序，如果不排序直接拼字符串，同一组项目在不同路径下会得到不同的 key，于是同一个状态被当成两个，规范族里出现一堆“同核不同号”的重复状态。现象就是状态数比课件多出好几倍，而且分析表里全是重复行。排序之后 key 就只跟内容有关，跟怎么走过来的无关。

3. 表驱动核心：从文法算出 FIRST/FOLLOW 与分析表

3.1 产生式解析与 FIRST 集的不动点迭代

文法读入看起来是最没技术含量的一步，但它决定了后面所有步骤的输入质量。文本格式一般长这样：

E -> E + T | T T -> T * F | F F -> ( E ) | id

写读入的时候注意三件事：箭头可能是->也可能是→，候选式分隔的竖线可能是半角|也可能是全角｜，每段要trim。全角符号的问题在中文输入法下极其常见，肉眼几乎看不出来。

public static Grammar parse(List<String> lines) { Grammar g = new Grammar(); int id = 0; for (String raw : lines) { String line = raw.trim(); if (line.isEmpty() || line.startsWith("#")) continue; // 支持注释行 String[] parts = line.split("->|→"); // 兼容中英文箭头 if (parts.length < 2) throw new IllegalArgumentException("产生式格式错误: " + line); String left = parts[0].trim(); g.addNonTerminal(left); // 右部按 | 拆候选式，全角竖线先归一成半角 for (String alt : parts[1].replace('｜', '|').split("\\|")) { List<String> rhs = new ArrayList<>(); for (String sym : alt.trim().split("\\s+")) { if (!sym.isEmpty()) rhs.add(sym); } g.addProduction(new Production(id++, left, rhs)); // 注意：空 rhs 表示 ε } } g.inferTerminals(); // 没在左部出现过的符号就是终结符 return g; }

id的自增顺序就是产生式在文件里的出现顺序，这一点很重要——后面分析表里r3这种归约动作，人眼要靠这个编号回查是哪条产生式，顺序乱了调试成本翻倍。inferTerminals()是偷懒但实用的做法：所有在左部出现过的进非终结符集合，剩下的都是终结符，省得再让用户单独声明。

FIRST 集的计算是个典型的不动点迭代：一直扫产生式，直到某一轮下来没有任何集合变大为止。

private void buildFirst() { // 终结符的 FIRST 就是它自己 for (String t : grammar.getTerminals()) { first.computeIfAbsent(t, k -> new HashSet<>()).add(t); } boolean changed = true; while (changed) { changed = false; for (Production p : grammar.getProductions()) { Set<String> target = first.computeIfAbsent(p.getLeft(), k -> new HashSet<>()); List<String> rhs = p.getRight(); if (rhs.isEmpty()) { // A -> ε changed |= target.add(EPSILON); continue; } boolean allNullable = true; for (String sym : rhs) { // 逐个符号往右推 Set<String> fs = first.getOrDefault(sym, Collections.emptySet()); for (String s : fs) { if (!EPSILON.equals(s)) changed |= target.add(s); } if (!fs.contains(EPSILON)) { allNullable = false; break; } } if (allNullable) changed |= target.add(EPSILON); // 右部整体可空 } } }

循环里的changed |= target.add(s)是个小技巧：Set.add返回布尔值表示是否真的插入了新元素，用按位或累积起来，就能在遍历结束后知道这一轮有没有变化。参数上EPSILON用字符串"ε"或者常量"#"都行，但要跟你文法里的符号体系区分开，别跟终结符撞名。

如果你的实验文法不含空产生式（大部分表达式文法都是这样），这段代码里的allNullable分支永远走不到，但留着没坏处，换成带可空非终结符的文法时不用改。

3.2 FOLLOW 集：从开始符号倒推

FOLLOW 集的规则只有三条，但实现的时候最容易漏掉“右部后缀可空”的情况。

规则是：开始符号的 FOLLOW 里放$；对产生式A -> αBβ，把FIRST(β) - {ε}加进FOLLOW(B)；如果β能推出空串，再把FOLLOW(A)整个加进FOLLOW(B)。

private void buildFollow() { // 开始符号的 FOLLOW 一定含结束符，缺了这个永远走不到 acc follow.computeIfAbsent(grammar.getStartSymbol(), k -> new HashSet<>()).add("$"); boolean changed = true; while (changed) { changed = false; for (Production p : grammar.getProductions()) { List<String> rhs = p.getRight(); for (int i = 0; i < rhs.size(); i++) { String b = rhs.get(i); if (!grammar.isNonTerminal(b)) continue; Set<String> target = follow.computeIfAbsent(b, k -> new HashSet<>()); // β 是 rhs[i+1 .. end]，边扫边判断是否可空 boolean betaNullable = true; for (int j = i + 1; j < rhs.size(); j++) { Set<String> fs = first.get(rhs.get(j)); for (String s : fs) { if (!EPSILON.equals(s)) changed |= target.add(s); } if (!fs.contains(EPSILON)) { betaNullable = false; break; } } if (betaNullable) { changed |= target.addAll(follow.getOrDefault(p.getLeft(), Collections.emptySet())); } } } } }

外层这个while (changed)同样不能省。FOLLOW 是有传播性的：A -> B C里FOLLOW(C)要并进FOLLOW(B)，而B的 FOLLOW 变了之后，如果有别的地方依赖它，又得重新算一轮。只扫一遍的结果会偏小，症状是某些该归约的格子空着，跑到一半就“无动作”报错。

startSymbol的确定方式有两种：默认取第一条产生式的左部，或者在增广文法里显式指定。前一种在手工扩展文法（S' -> S）时容易出错——第一条可能是S' -> S，那FOLLOW(S')拿到$是没用的，真正需要的是FOLLOW(S)含$。我一般会在Grammar里单独存一个startSymbol字段，由读入时显式赋值，别靠猜。

3.3 CLOSURE 与 GOTO：项目集规范族的 BFS 构造

CLOSURE 的逻辑一句话能说完：如果项目里圆点后面是个非终结符B，那就把所有左部为B的产生式以“圆点在最左”的形式加进来，反复直到不再新增。

private Set<Item> closure(Set<Item> kernel) { Set<Item> result = new LinkedHashSet<>(kernel); Deque<Item> queue = new ArrayDeque<>(kernel); while (!queue.isEmpty()) { Item item = queue.poll(); String next = item.nextSymbol(grammar); // 圆点后的符号 if (next == null || !grammar.isNonTerminal(next)) continue; for (Production p : grammar.byLeft(next)) { // 左部为 next 的所有产生式 Item fresh = new Item(p.getId(), 0); // 圆点放在最前 if (result.add(fresh)) queue.push(fresh); // 只有新加进去的才需要继续展开 } } return result; }

if (result.add(fresh))这个判断是性能关键，也是正确性关键。只有真正新增的项目才需要入队继续展开，否则遇到A -> A a | b这种左递归文法就会无限入队。byLeft(next)是Grammar里预建的索引（Map<String, List<Production>>），避免每次都遍历全部产生式。

GOTO 更简单，就是挑出圆点后面是x的项目，把圆点往右挪一格：

private Set<Item> goTo(Set<Item> state, String x) { Set<Item> moved = new LinkedHashSet<>(); for (Item item : state) { if (x.equals(item.nextSymbol(grammar))) { moved.add(new Item(item.getProdId(), item.getDot() + 1)); } } return moved; // 返回的是内核，外层还要再求一次 closure }

注意goTo返回的是内核，调用方必须再套一层closure()才是完整状态。这个分工不清是新手常犯的错，忘了套闭包的结果就是状态里的项目少了一大半，分析表大片空白。

规范族的构造用 BFS，配一个Map<String, Integer>按 key 判重：

public List<ItemSet> build() { Map<String, Integer> index = new HashMap<>(); List<ItemSet> states = new ArrayList<>(); Deque<Integer> queue = new ArrayDeque<>(); // 0 号状态：增广产生式 S' -> ·S 的闭包 ItemSet start = new ItemSet(closure(Collections.singleton(new Item(0, 0)))); index.put(start.getKey(), 0); states.add(start); queue.push(0); while (!queue.isEmpty()) { int i = queue.poll(); for (String x : grammar.allSymbols()) { // 终结符 + 非终结符都要试 Set<Item> moved = goTo(states.get(i).getItems(), x); if (moved.isEmpty()) continue; ItemSet target = new ItemSet(closure(moved)); Integer j = index.get(target.getKey()); if (j == null) { // 新状态 j = states.size(); index.put(target.getKey(), j); states.add(target); queue.push(j); } transitions.put(i + "|" + x, j); // 记录 GOTO 边，填表要用 } } return states; }

allSymbols()必须同时包含终结符和非终结符。只遍历终结符是个很隐蔽的错误：项目集能建出来，但 GOTO 表里所有非终结符的转移都是空的，归约之后找不到下一个状态。

3.4 填 ACTION/GOTO 表并做冲突判定

有了状态和转移，填表就是照着定义走。圆点后面是终结符就填移进，圆点到底就填归约，归约的列由 FOLLOW 集决定——这就是 SLR(1) 里那个 “S” 的含义，用 FOLLOW 集来消解 LR(0) 消不掉的冲突。

public void buildTable(List<ItemSet> states) { for (int i = 0; i < states.size(); i++) { for (Item item : states.get(i).getItems()) { String next = item.nextSymbol(grammar); if (next != null) { if (grammar.isTerminal(next)) { setAction(i, next, "s" + gotoState(i, next)); // 移进 } // 圆点后是非终结符的情况只进 GOTO 表，不进 ACTION } else { Production p = grammar.getProduction(item.getProdId()); if (p.getLeft().equals(grammar.getAugmentedStart())) { setAction(i, "$", "acc"); // S' -> S· 接受 } else { for (String a : follow.get(p.getLeft())) { setAction(i, a, "r" + p.getId()); // 按 FOLLOW 集归约 } } } } } } private void setAction(int state, String terminal, String act) { String old = action[state].get(terminal); if (old != null && !old.equals(act)) { // 同一个格子被填了两次且动作不同 —— 这就是冲突 conflicts.add(String.format("状态 %d 遇 %s：%s 与 %s 冲突", state, terminal, old, act)); return; } action[state].put(terminal, act); }

setAction里的冲突检测是必须要有的，别嫌麻烦。没有它的话，后面填的动作会直接覆盖前面的，程序照样能跑，但分析结果在某些输入上莫名其妙地错，而且完全看不出原因。有了这个conflicts列表，跑完直接打印，是“文法本身不是 SLR(1)”还是“我哪一步算错了”一目了然。

冲突分两种：移进-归约冲突（同一个格子既要移进又要归约）和归约-归约冲突（同一个格子两条产生式都要归约）。前者多半是文法本身的问题，比如经典的赋值语句文法S -> L = R | R、L -> * R | id、R -> L，它在 SLR(1) 下就是有冲突的，得上 LALR(1)；后者一般是 FIRST/FOLLOW 算错了，或者两条产生式的右部完全一样。

4. 分析过程模拟：状态栈、符号栈与输入指针怎么配合

4.1 移进-归约主循环

表建好之后，驱动程序其实只有三十行。核心是三个东西：状态栈、符号栈、输入指针。状态栈顶决定当前行，输入指针指向的 token 决定当前列，查表得到动作。

public boolean parse(List<String> tokens) { Deque<Integer> states = new ArrayDeque<>(); Deque<String> symbols = new ArrayDeque<>(); states.push(0); // 初始状态入栈 int ip = 0; while (true) { int s = states.peek(); String a = ip < tokens.size() ? tokens.get(ip) : "$"; String act = table.getAction(s, a); if (act == null) { return fail("状态 " + s + " 遇到 " + a + " 无可用动作"); } if ("acc".equals(act)) { return true; // 接受 } if (act.startsWith("s")) { states.push(Integer.parseInt(act.substring(1))); // 移进：压新状态 symbols.push(a); // 压当前符号 ip++; // 指针右移 } else { Production p = grammar.getProduction(Integer.parseInt(act.substring(1))); for (int k = 0; k < p.size(); k++) { // 弹出 |右部| 个符号 states.pop(); symbols.pop(); } int from = states.peek(); // 弹出后的栈顶 symbols.push(p.getLeft()); // 左部入符号栈 Integer to = table.getGoto(from, p.getLeft()); if (to == null) { return fail("GOTO[" + from + "," + p.getLeft() + "] 为空"); } states.push(to); // 新状态入栈 } } }

几个参数值得说清楚。act用字符串"s3"/"r5"/"acc"编码，解析时靠首字母判断，好处是打印出来直接可读，分析过程表往实验报告里一贴就行；坏处是每次都要substring+parseInt，性能一般，但对一个实验规模的输入完全够。如果你要做成工具，可以换成两个 int 数组加一个动作类型枚举，热路径上快不少。

symbols这个栈在纯识别场景下其实可以省掉——状态栈单独就能驱动。但保留它有两个好处：出错时能打印出“已经读到哪了”的符号上下文，以及做语义动作（比如建语法树）时可以直接从符号栈上取子树。

4.2 归约动作的栈操作细节

归约那三行是整段代码里最容易写错的地方，也是排查时最该先看的地方。

第一条：弹多少个。产生式右部长度是p.size()，但两个栈各弹p.size()次，一共2 * p.size()个元素。写成一个循环里两个pop()就不会错，别写成for (k < p.size() * 2)然后在里面交替 pop，那样一旦某个栈空了就分不清是谁的问题。

第二条：弹完之后栈顶是什么。归约是“把右部换成左部”，右部被弹掉之后，状态栈顶就是右部第一个符号之前那个状态，也就是 GOTO 表的行索引。所以from = states.peek()必须放在弹出循环之后，放在之前就取错了。

第三条：ε 产生式。p.size() == 0的时候，弹出循环一次都不执行，from就是当前栈顶，symbols.push(p.getLeft())直接压一个非终结符上去。这个分支不需要特殊处理，但写的时候要意识到它存在，否则看到A -> ε会怀疑代码漏了逻辑。

注意：如果归约过程中抛NoSuchElementException，八成是状态栈被弹空了。原因通常不是归约弹多了，而是前面的移进动作压错了状态号，或者分析表里某个 GOTO 填成了-1而不是不填。

4.3 词法分析器怎么把源码变成终结符流

实验包里通常配一个极简的词法分析器，把id + id * id这样的串切成[id, +, id, *, id, $]。这个 Lexer 不需要支持浮点数、字符串字面量、注释，只要能正确识别标识符、数字和单字符运算符就够了。

public List<String> tokenize(String source) { List<String> tokens = new ArrayList<>(); int i = 0; while (i < source.length()) { char c = source.charAt(i); if (Character.isWhitespace(c)) { i++; continue; } if (Character.isLetter(c)) { // 标识符整体归一成终结符 id int j = i; while (j < source.length() && Character.isLetterOrDigit(source.charAt(j))) j++; tokens.add("id"); // 注意：不保留原词，只留类别 i = j; } else if (Character.isDigit(c)) { // 数字归一成 num int j = i; while (j < source.length() && Character.isDigit(source.charAt(j))) j++; tokens.add("num"); i = j; } else { tokens.add(String.valueOf(c)); // 运算符、括号原样保留 i++; } } tokens.add("$"); // 结束符，必须有 return tokens; }

关键点是归一化。文法里的终结符是id、num这种类别名，不是具体的x、count、123，所以词法阶段必须把词素映射成类别，否则分析表里查不到列。这也意味着如果你想在归约时拿到具体值（比如算表达式的值），得另开一个并行列表存词素，不能用 token 串本身。

$是结束符，两边都要对上：词法这里加，FOLLOW(开始符号) 那里也加，分析表acc那一格也是按$填的。三处任意一处漏了，最后都走不到接受状态。

4.4 分析过程的输出：一张能交实验报告的表

实验报告里要的那张表，一般是这样的五列：步骤、状态栈、符号栈、剩余输入、动作。在parse循环里每轮开头打印一行就行。

private void trace(int step, Deque<Integer> states, Deque<String> symbols, List<String> tokens, int ip, String act) { System.out.printf("%-4d %-22s %-22s %-24s %s%n", step, joinReverse(states), // 栈底在左，栈顶在右 joinReverse(symbols), String.join(" ", tokens.subList(ip, tokens.size())), act == null ? "error" : act); }

joinReverse是因为Deque用push压栈，迭代顺序是从栈顶到栈底，而报告里习惯栈底在左。这个细节不改也能跑，但对着课件一行行核的时候会非常别扭，很容易误判成栈操作写反了。

打印的量也要控制一下。一个二十来 token 的表达式，归约步骤能到五六十步，全打出来刷屏；只打关键步骤（移进、归约、接受）又不够交作业。我的做法是全打，但输出重定向到文件，同时在控制台只打最后结果和错误信息。

5. 排查清单：跑 SLR(1) 分析器时最容易翻车的五处

5.1 文法读入阶段的坑

坑一：产生式被悄悄吃掉一条。

现象：打印出来的产生式列表比源文件少，或者某条产生式右部只有第一个符号，E -> E + T变成了E -> E。程序不报错，继续往下跑，但 FIRST/FOLLOW 全错。

原因：分隔符没处理干净。最常见的是全角竖线｜和全角箭头→，split("\\|")对全角竖线完全不生效，整行被当成一个候选式；其次是行尾有不可见字符，split("\\s+")之后最后一个符号带着\r（Windows 换行在 Linux 上读），跟文法里的T对不上，于是被当成终结符。

解决：读入后先做字符归一（replace('｜','|').replace('→','-')之类），每行trim()，切分符号时用split("\\s+")再过滤空串。更重要的是加一步自检：解析完立刻把所有产生式按id打印一遍，人眼扫一眼对不对，比后面调试半小时省事。

坑二：javac报“编码 GBK 的不可映射字符”。

现象：源码里有中文注释或者中文字符串提示，编译直接失败，或者编译过了但控制台输出乱码。

原因：源文件是 UTF-8，javac在某些平台上默认按 GBK 解码。实验包里带了中文提示语的尤其容易中招。

解决：编译时显式指定javac -encoding UTF-8 -d out src/**/*.java，运行时加-Dfile.encoding=UTF-8。这一步建议直接写进run.bat/run.sh，别每次手敲。

5.2 集合与状态机阶段的坑

坑三：FOLLOW 集少了$，永远走不到 acc。

现象：分析表建完了，最后那个接受状态里$那一格是空的；跑输入的时候所有 token 都吃完了，报“状态 X 遇到 $ 无可用动作”。

原因：$加到错误的非终结符上。如果文法做了增广（多了一条S' -> S），把$加进了FOLLOW(S')而不是FOLLOW(S)，那S'的 FOLLOW 根本没人用——归约到S的时候查的是FOLLOW(S)。

解决：startSymbol显式存字段，读入时明确指定是S而不是S'，别靠“第一条产生式的左部”去猜。加完之后打一行日志FOLLOW(S) = {$, ...}，肉眼确认含$。

坑四：项目集数量爆炸，状态数比课件多好几倍。

现象：助教给的参考答案里规范族有 12 个状态，你的程序跑出 30 多个，分析表里一堆看起来一模一样的行。

原因：ItemSet判等失败。具体有两种：Item只重写了equals没重写hashCode，放进HashSet里按地址比较，逻辑相同的项目被视为不同；或者ItemSet的 key 拼接时没对项目排序，同一组项目因为插入顺序不同生成了不同的字符串。

解决：Item老老实实两个字段都参与equals和hashCode；ItemSet.getKey()里对项目列表做一次排序再拼接。验证方法很直接：打印每个状态的 item 数量，如果有两个状态的 item 集合完全一样但编号不同，就是这个 bug。

5.3 分析表与运行阶段的坑

坑五：把文法本身的移进-归约冲突当成代码 bug 反复改。

现象：某几条文法跑起来报冲突，怎么调都消不掉；换成课件上的简单表达式文法就一切正常。

原因：这是 SLR(1) 的能力边界，不是实现问题。SLR(1) 用 FOLLOW 集做归约的看符集合，粒度比较粗，像S -> L = R | R这种文法在 SLR(1) 下必然冲突，需要 LALR(1) 的向前看信息才能区分。

解决：先跑一遍标准表达式文法确认实现正确，再拿有冲突的文法去试。如果标准文法全对、只有复杂文法冲突，那就是文法超纲，别改代码。要处理的话两条路：改写文法消除冲突，或者把归约的看符集合换成项目级的向前看符号集（往 LR(1)/LALR(1) 走）。

还有个小坑顺手记一下：归约弹栈时抛NoSuchElementException。基本只有两个原因——分析表里某个动作填错了状态号，或者 GOTO 表某个格子填了-1而不是留空。前者回头查填表逻辑，后者在getGoto里把-1当null处理掉就行。

6. 二次开发：把它从作业改成能复用的分析引擎

6.1 先做解耦：把算法从 UI 里拔出来

如果拿到的是把所有逻辑塞在Main里的版本，第一件该干的事不是加功能，是拆。目标很明确：让FirstFollow、LR0Builder、SLRTable这三个类完全不知道System.out的存在。具体做法是把所有System.out.println换成往一个List<String> log里加，由调用方决定打印还是写文件还是塞进界面。

拆完之后拼一个门面类，把整条链路封一次：

public class SLREngine { private final Grammar grammar; private final SLRTable table; private final List<String> conflicts; public SLREngine(Grammar g) { this.grammar = g; this.table = new SLRTable(g, new FirstFollow(g).compute(), new LR0Builder(g).build()); } // 外部只需要这两个方法，不关心内部有几步 public List<String> getConflicts() { return table.getConflicts(); } public ParseResult parse(List<String> tokens) { return new Parser(grammar, table).run(tokens); } }

这个改动看着不起眼，但后面的所有工作都靠它：写单元测试不用重定向标准输出，做 Web 版直接把ParseResult序列化成 JSON，批量跑测试用例就是一个for循环。

6.2 验证方法：拿三组文法做回归

改完算法一定要有回归手段，不然改一处崩三处，自己都不知道。我一般准备三组固定文法：

第三组特别重要——它验证的是“该报错的时候确实报错了”。很多改造把冲突检测顺手删了，程序反而看起来更“顺畅”，实际上是错的。

6.3 往后走一步：从 SLR(1) 到 LALR(1)

真要把这个实验包用起来，最自然的延伸是 LALR(1)。改动量其实不大：把Item从(prodId, dot)扩成(prodId, dot, lookahead)，closure里在加入新项目时按FIRST(βa)算向前看符号，最后把所有“同心”（圆点位置完全相同、只有向前看符号不同）的状态合并成一个。

合并那一步是主要工作量，也是最容易踩坑的地方：合并后可能产生新的归约-归约冲突（LALR 特有的冲突），得在合并完再跑一遍冲突检测。验证方式是拿那些 SLR(1) 下有冲突、LALR(1) 下无冲突的文法去跑，冲突列表变空就说明改对了。

坦白说我第一次做这个改造的时候，图省事直接在Item里加了 lookahead 但没做状态合并，跑出来的状态数比 LR(1) 还多，分析表大得离谱，查了大半天才发现是“只扩了项目、没合并状态”。从那以后我每次动项目集结构，都强制先跑一遍那三组回归文法，把状态数、冲突数、第一个测试用例的分析步骤数三个数字打出来跟改之前对，对不上就不往下走。希望帮到你。

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