SLR(1)语法分析器实现：FOLLOW集、项目集去重与冲突排查

简介：面向高校编译原理课程实验的学习者与 Java 开发者，这份 SLR(1) 语法分析器项目围绕自底向上的解析流程展开，可用于理解文法表示、左递归与左公因子处理、FOLLOW 集和闭包构造、GOTO 集生成、分析表建立以及移进归约解析等关键环节。压缩包共 85 个文件，约 40KB，其中 76 个 Java 源文件承载核心实现与测试代码，6 个 XML 和 1 个 iml 文件用于 Maven 与 IDEA 工程配置，源码、测试和资源目录的划分便于对照实验步骤阅读和修改。已有 523 人学习，适合需要完成课程实验、复盘 SLR(1) 分析表构造或参考 Java 实现细节的读者。项目提供了较完整的解析器代码框架、模块组织方式和调试切入点，也便于把状态转换、冲突处理与归约规则落到具体代码中，对实验报告撰写、代码走读及理解分析表驱动解析的执行脉络均有参考价值。

1. 为什么 SLR(1) 比 LR(0) 只多看一眼，却能消掉大半冲突

很多人第一次做编译原理实验里的 SLR(1) 语法分析器，用 Java 写完闭包运算和 FOLLOW 集，运行后却发现状态数比教材多出一倍，归约动作整片缺失，控制台打印的冲突位置完全无法理解。这件事的关键在于：难点不在算法公式，而在两个工程细节——项目集的相等性判断，以及 FOLLOW 集这个「全局向前看集合」到底被允许粗略到什么程度。语法分析器本质上是把文法编译成一张 ACTION/GOTO 表，再用双栈驱动查表；SLR(1) 相对 LR(0) 的全部增量，就是在归约时多问了一句「这个非终结符后面能跟什么」。把这句话背后的定点计算和状态去重搞明白，那些难解释的冲突报错才会变成可以推理的东西。

2. LR(0) 项目集规范族：闭包为什么必须跑到不动点

构造分析表的第一步不是填表，而是把文法变成一台状态机。这台状态机的每个状态是一个「项目集合」，集合里的每个项目记录了我们「已经识别到产生式右部的哪个位置」。听上去很朴素，但如果想不清楚集合怎么闭合、状态怎么去重，后面所有工作都会建立在错误的基础上。

2.1 项目、增广文法与 CLOSURE 的定点过程

LR(0) 项目写成A → α·β，圆点左边的 α 是已经压在栈里、确认属于这个产生式的部分，圆点右边是还没见到的部分。为了让「接受」有一个统一的表示，先给文法加一条增广产生式S' → S，这样接受动作就等价于在某个状态里看到S' → S·。闭包运算的规则只有一条：如果集合里有A → α·Bβ，且 B 是非终结符，那么 B 的每一条产生式都要以B → ·γ的形式加进来，因为此时栈顶正期待一个 B，而 B 的一切可能开头都得考虑。

用 Java 实现时，项目本身不要写成带字符串的对象，它只需要两个整数。

// 项目 = 产生式编号 + 圆点位置，两个 int 就是全部状态 static final class Item { final int prod; // 第几条产生式 final int dot; // 圆点位置，取值 0..right.length Item(int prod, int dot) { this.prod = prod; this.dot = dot; } // 圆点后面的符号，null 表示圆点已经在末尾（归约项） Symbol next() { Production p = Grammar.get(prod); return dot < p.right.length ? p.right[dot] : null; } @Override public boolean equals(Object o) { if (!(o instanceof Item)) return false; Item x = (Item) o; return prod == x.prod && dot == x.dot; // 值相等，不是引用相等 } @Override public int hashCode() { return prod * 131 + dot; } }

闭包本身用一个工作表（worklist）来扩散，而不是递归。原因很实际：左递归文法A → Aα在递归写法下会直接导致无限递归，而工作表写法里「只有新项目才入队」这条判断，天然保证了终止，因为项目总数是固定的，等于所有产生式右部长度加一之和。

Set<Item> closure(Set<Item> kernel) { Deque<Item> work = new ArrayDeque<>(kernel); Set<Item> result = new LinkedHashSet<>(kernel); // LinkedHashSet 保序，方便对照教材 while (!work.isEmpty()) { Item it = work.poll(); Symbol next = it.next(); if (next == null || !next.isNonTerminal()) continue; // 终结符或已到末尾，不展开 for (int p : grammar.productionsOf(next)) { Item fresh = new Item(p, 0); // B → ·γ if (result.add(fresh)) work.push(fresh); // 只有真正新增的项目才继续扩散 } } return result; }

productionsOf返回以某个非终结符为左部的产生式编号列表，用 Map 预先建好索引，避免每次闭包都扫全表。这一步看着不起眼，但闭包会被调用几百次，索引化之后构造速度能差一个数量级。

2.2 GOTO 与规范族：状态是广度优先扩展出来的

有了闭包，GOTO 就很好定义：把集合里所有圆点后面是 X 的项目挑出来，把圆点往右挪一格，得到一组「核项目」，再对它们求闭包。规范族就是把 GOTO 反复应用直到不再产生新集合，本质是图上的一次广度优先遍历。

Map<String, Integer> stateIndex = new LinkedHashMap<>(); // 规范化 key -> 状态号 List<Set<Item>> states = new ArrayList<>(); Map<Integer, Map<Symbol, Integer>> goTo = new HashMap<>(); Deque<Integer> queue = new ArrayDeque<>(); Set<Item> i0 = closure(Set.of(new Item(augmentedProd, 0))); // S' → ·S stateIndex.put(keyOf(i0), 0); states.add(i0); queue.add(0); while (!queue.isEmpty()) { int id = queue.poll(); // 只对圆点后面真正出现过的符号求 GOTO，不是对全部文法符号求 for (Symbol x : symbolsAfterDot(states.get(id))) { Set<Item> target = closure(gotoSet(states.get(id), x)); String k = keyOf(target); Integer exist = stateIndex.get(k); // 靠规范化 key 去重 if (exist == null) { exist = states.size(); stateIndex.put(k, exist); states.add(target); queue.add(exist); } goTo.computeIfAbsent(id, v -> new LinkedHashMap<>()).put(x, exist); } }

选择LinkedHashMap而不是HashMap是有意为之：它让状态编号的生成顺序稳定可复现。同一份文法，两次运行得到的编号完全一致，断点调试时才能把教材上的状态图和控制台输出对应起来。如果换了无序容器，状态编号会漂移，你会怀疑自己填错了表，其实只是容器在变化。

注意：symbolsAfterDot只收集圆点右侧紧邻的符号，不要遍历整个终结符表，否则会生成一堆空转移，状态数虚高。

2.3 Java 里的相等性：项目集去重失败才是状态爆炸的真凶

项目集是集合，集合的相等性与元素的排列顺序无关。如果直接拿LinkedHashSet.toString()当 key，闭包扩散顺序一变，同一个集合就会得到两个不同的字符串，于是被当成两个状态。症状是状态数翻倍、GOTO 表里出现本不该有的自环。

// 规范化 key：每个项目压成 "产生式@圆点"，排序后拼接，消除顺序影响 String keyOf(Set<Item> set) { return set.stream() .map(i -> i.prod + "@" + i.dot) .sorted() .collect(Collectors.joining(",")); }

这里的做法是以排序来统一顺序。状态数上前几十个的时候，排序的开销可以忽略；如果文法更大，可以改用位集：给每个项目分配一个全局下标，一个状态就是一个BitSet，hashCode用BitSet.hashCode()，比较和哈希都是位运算，速度会快很多。用位集做 LR(0) 规范族，是一般实现里性价比最高的一个优化点。

3. FOLLOW 集：SLR(1) 用来判断归约时机的集合

LR(0) 的困境在于：一个状态里只要出现归约项，它就想归约，根本不管下一个输入符号是什么。这等于假设这个非终结符后面接任何东西都合理，冲突自然大面积出现。SLR(1) 的解法很朴素——查一下这个非终结符的 FOLLOW 集，只对 FOLLOW 里的符号才归约。

3.1 FIRST/FOLLOW 的定点递推实现

FOLLOW 的计算是一条不断把集合合并进上级集合的规则。A → αBβ时，FIRST(β) 里除空串以外的符号全进 FOLLOW(B)；如果 β 能推出空串（或者 β 本身就是空的），那 FOLLOW(A) 整个并进 FOLLOW(B)。写起来就是一个「一直算到本轮没有任何集合发生变化」的循环。

void buildFollow() { follow.get(startSymbol).add("$"); // 句末标记，全篇只此一处凭空产生 boolean changed = true; while (changed) { // 定点迭代，收敛即停 changed = false; for (Production p : grammar.all()) { for (int i = 0; i < p.right.length; i++) { String b = p.right[i]; if (!grammar.isNonTerminal(b)) continue; // 取 β = right[i+1..] 的 FIRST，空串用 "ε" 表示 Set<String> firstBeta = firstOfSuffix(p.right, i + 1); changed |= follow.get(b).addAll(minusEpsilon(firstBeta)); if (firstBeta.contains("ε")) { changed |= follow.get(b).addAll(follow.get(p.left)); } } } } }

firstOfSuffix要能从右往左算：从 β 的第一个符号开始，如果它不能推出空串，结果就到此为止；能推出空串才继续看下一个，最后所有符号都能推空，才把 ε 放进去。这段逻辑写错的地方都集中在「能不能推空」这一步：很多人只判断了X → ε这种显式空产生式，漏掉了A → BC、B → ε、C → ε这种间接推空，导致 FOLLOW 集偏小，归约动作整片缺失。

迭代次数的上界是「所有 FOLLOW 集合元素总数」，实际文法通常三轮左右就稳定了，所以不必担心性能。真正会出问题的是没有变更检测，写死循环跑固定次数——多了浪费，少了不收敛，而且错得很隐蔽。

3.2 归约填表：为什么只看 FOLLOW(A) 就是对的

理解 SLR(1) 的关键，是搞清「当下栈里的内容」代表什么。归约项A → α·出现在状态 i，意味着从栈底到栈顶的这一段，刚刚被识别成 α，可以安全地折叠成 A。折叠之后，栈里剩下的是某个前缀 γ，形成 γA。

此时下一个输入符号 a 能不能接受，取决于「γA 后面跟 a」是不是某个合法句子的前缀。FOLLOW(A) 的定义正是「所有可能紧跟在 A 后面的终结符」，所以只要 a ∈ FOLLOW(A)，就不能排除这种可能。

这里有个容易忽略的点：FOLLOW(A) 是一个「必要条件式」的判断，也就是把条件放宽了。它是可靠的，因为合法情形一个不漏；它不精确，因为把所有可能跟随 A 的符号都塞了进来，不管当前是哪个上下文。这种粗略正是 SLR(1) 冲突的来源，也是它比 LR(1) 简单的原因。

填表规则整理成一张表更清楚：

3.3 SLR(1) 处理不了的冲突：FOLLOW 集粒度太粗

有一个经典文法能把 SLR(1) 的边界暴露得很干净：S → L = R | R，L → * R | id，R → L。在识别到L的那个状态里，同时存在移进项S → L·= R和归约项R → L·。而 FOLLOW(R) 里恰好含=（因为R出现在S → L = R的右部），于是遇到=时，移进和归约冲突了。

但稍微想一下就知道，R → L归约出来的这个 R 根本不可能后接=——=只会跟在L后面，不会跟在R后面。SLR(1) 分不清「这个 L 是从哪条路径来的」，因为 FOLLOW 是全局的，不区分上下文。LR(1) 给每个项目配一个独立的向前看符号集合，把这份上下文信息保留下来，冲突就消失了。这也说明一件事：SLR(1) 的能力上限由文法决定，不是代码写得不够好。

4. 分析表构造与双栈驱动：从表到运行的那一步

表和驱动是两件事。构造表是编译期工作，驱动是运行期工作。很多人表填对了，驱动写错，症状是「解析到一半突然跳到不存在的状态」，然后怀疑人生。

4.1 ACTION 表的四类动作与填表冲突的处理

ACTION 表的每格可能是移进、归约、接受、报错四种之一。填表时一定会遇到同一格被写两次的情况，这时怎么处理，直接反映了实现的质量。

// 统一入口：已存在动作时记录冲突，绝不静默覆盖 void put(int state, String a, Action act) { Map<String, Action> row = table.computeIfAbsent(state, k -> new HashMap<>()); Action old = row.get(a); if (old == null) { row.put(a, act); return; } if (old.equals(act)) return; // 同一动作重复填，忽略 conflicts.add(new Conflict(state, a, old, act)); // 移进/归约 或 归约/归约 }

填表顺序上，一般先遍历移进项，再遍历归约项。理由并不是「移进优先」这条教科书规则，而是归约条件本身更宽松：FOLLOW 是真实跟随符号的超集，让归约覆盖移进，等于把所有能靠移进继续走下去的分支提前终止，把文法悄悄改坏了。正确的姿态是：一旦冲突，就说明这份文法不满足 SLR(1)，应该报出来看，而不是拿优先级规则强行补救，掩盖矛盾。

归约项之间也可能冲突，也就是同一个状态、同一个符号上出现两条不同的归约产生式。这种归约/归约冲突在 SLR(1) 里基本无法靠 FOLLOW 解决，只能改写文法或者换更强的分析法。

4.2 双栈驱动：状态栈与符号栈为什么要分开

驱动循环维护两个栈。状态栈存的是 DFA 的状态编号，符号栈存的是已经识别完并归约后的文法符号。两者长度始终差一：初始时状态栈只有一个 0，符号栈是空的。

归约A → α（长度 k）时，弹掉 k 个状态和 k 个符号，然后拿「弹完之后的新栈顶状态」去查 GOTO 表，用 A 得到新状态并压栈。这个顺序不能反：如果先压栈再查 GOTO，你用的就是旧栈顶，会跳到一个和当前上下文无关的状态上。

4.3 Java 驱动循环实现与可断点调试的结构

boolean parse(List<String> input) { Deque<Integer> stateStack = new ArrayDeque<>(); Deque<String> symbolStack = new ArrayDeque<>(); stateStack.push(0); int pos = 0; input.add("$"); // 句末标记，与分析表里的 accept 项对应 while (true) { int s = stateStack.peek(); String a = input.get(pos); Action act = actionTable.getOrDefault(s, Map.of()).get(a); if (act == null) { // 表格里的空项 = 错误入口 reportError(s, a, pos); return false; } switch (act.type) { case SHIFT: symbolStack.push(a); stateStack.push(act.target); pos++; // 只有移进才消耗输入 break; case REDUCE: Production p = grammar.get(act.prod); for (int i = 0; i < p.right.length; i++) { // 空产生式长度 0，一次都不弹 stateStack.pop(); symbolStack.pop(); } symbolStack.push(p.left); // 关键：弹栈之后再取栈顶查 GOTO stateStack.push(goTo.get(stateStack.peek()).get(p.left)); break; case ACCEPT: return true; default: break; } } }

代码里有两个容易出错的地方。第一是空产生式：长度 0，循环体一次都不执行，看起来什么都没做，但如果代码里写了「至少弹一个」的保护，反而会破坏语义。第二是错误处理的位置：act == null就是文法意义上的错误入口，所有恢复策略都从这里展开——恐慌模式的做法是不断弹状态栈，直到某个状态对当前符号有动作；或者跳过输入符号，直到能继续。把reportError里打印出当前状态号、栈中的符号序列和剩余输入，比任何日志都有用。

5. 避坑与排查：SLR(1) 实验里最常见的五处翻车

5.1 状态数比教材多出一倍：项目集去重没做规范化

现象：教材上 12 个状态，程序跑出 20 多个，而且 GOTO 表里有明显不该存在的转移。

原因：项目集的 key 用了插入顺序相关的表示（比如直接toString()），闭包扩散顺序不同就产生不同的 key，同一个集合被建成两个状态。

解决：key 一律用「项目下标排序后拼接」或位集。加一句自检——构造完规范族后，遍历所有状态，两两比较 key，只要有重复，就说明去重函数有问题。

5.2 归约动作整片缺失：FOLLOW 迭代没收敛

现象：输入串在某个位置突然报错，而手工推演明明能归约；打印 FOLLOW 表，发现某些非终结符的集合是空的。

原因：一是忘了把$放进开始符号的 FOLLOW；二是「能推出空串」判断只看了显式空产生式，没处理间接推空；三是迭代写成了固定一轮。

解决：把迭代写成「本轮有变化就继续」，并在收敛后断言每个非终结符的 FOLLOW 非空（开始符号尤其要检查）。

5.3 空产生式导致栈下溢或死循环

现象：解析到某处抛NoSuchElementException，或者驱动循环原地打转不前进。

原因：归约空产生式时误弹了一个状态；或者填表时把空产生式的归约动作填到了不该填的符号上，导致归约和移进反复交替。

解决：归约时严格按p.right.length弹栈；加一个「上一次动作 + 当前状态号」的循环检测，连续两次相同就打印现场并退出，别让它无限跑。

5.4 终结符与非终结符判定错乱

现象：闭包展开时项目数异常膨胀，或者某些本该展开的项目没有展开。

原因：文法里用大小写区分终结符与非终结符，但某个符号既出现在左部又出现在右部，判定函数前后不一致；或者词法阶段产出的 token 名与分析表里的终结符拼写不一致（比如id与ID）。

解决：先扫一遍文法，建立终结符/非终结符两个集合，冲突直接报错；token 名统一用小写，并且在词法输出和填表之间只保留一个映射点。

5.5 冲突被静默覆盖：填表用了 put 而不是带冲突检测的写入口

现象：程序不报冲突，解析结果却对某些输入给出错误结论，换个输入又能过。

原因：HashMap.put直接把旧动作覆盖掉了，冲突被隐藏。看起来「没有冲突」，其实是有人替你做了决定。

解决：所有写表动作走同一个入口，冲突列表非空就在构造阶段打印出来（状态号、符号、两个动作），再决定是修文法还是换分析法。

6. 从 SLR(1) 到 LR(1)、LALR(1)：那一个向前看符号的代价

把 SLR(1) 写通之后，最自然的疑问是：既然问题出在 FOLLOW 太粗，为什么不在每个项目上单独挂一个向前看集合？答案是完全可以，这就是 LR(1)。项目从A → α·β变成[A → α·β, a]，闭包里[A → α·Bβ, a]会展开出[B → ·γ, b]，其中 b 取自 FIRST(βa)。冲突确实消失了，代价是状态数暴涨，一份中等规模的文法轻轻松松从几十个状态变成几百个。

LALR(1) 是折中路线上的一招：把 LR(1) 项目集族里「核心项目相同、只有向前看集合不同」的那些状态合并成一个。合并后状态数回到 LR(0) 的量级，向前看信息保留了大部分，能力介于 SLR(1) 和 LR(1) 之间。多数生成器选的就是这条路。

如果更想从工程上验证「SLR(1) 到底差在哪」，可以做一个对照实验：同一份文法，分别跑 SLR(1) 和 LALR(1) 构造，把两者的冲突列表并排打印。LR(0) 能过而 SLR(1) 报冲突，说明 FOLLOW 判断过于宽泛；SLR(1) 能过而 LALR(1) 也报冲突，那基本是文法本身有二义性，改分析法没用，得回去改文法。这个实验的成本很低，但能让人彻底分清「分析法的能力边界」和「文法本身的问题」。

我最初的直觉是：状态越多越强，表越大越保险。后来发现反过来才对——SLR(1) 的价值恰恰在于它足够小，小到你能把每个状态的产生式来源手画在纸上；一旦这个状态是怎么从闭包长出来的、归约动作为什么只认 FOLLOW、弹栈后为什么必须用新栈顶查 GOTO 这三件事在脑子里连成一条线，LR(1) 和 LALR(1) 就只是「项目多挂一个集合」的增量。从那以后我每次搭分析器，都强制先把增广文法和项目集规范族打印出来对一遍，再动填表的代码，省下的调试时间远比打印花的多。希望帮到你。

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