用Java实现SLR(1)语法分析器：从FIRST/FOLLOW到ACTION/GOTO表的完整实践

做编译原理实验的时候十个里面有九个都要写到语法分析器。我这次要折腾的是用Java实现一个SLR(1)语法分析器从给定文法开始自动构造LR(0)项目集族计算FIRST、FOLLOW集合生成ACTION/GOTO分析表再写一个总控程序驱动状态栈完成输入串的移进、归约和接受判断。这套东西做完之后你对编译原理里自底向上分析这条线的理解会扎实很多。如果你正卡在课程设计的某个环节或者只是想搞清楚SLR(1)到底是怎么从文法一步步变成一张表的这篇内容应该能给你省下不少反复翻书的时间。我自己当时做这个实验的时候最大的感受是理论课上半小时能讲完的算法到了代码里到处都是细节坑。闭包死循环、终结符识别错误、归约项目把冲突漏掉、分析表某个格子被覆盖了还不知道……这些我全都遇到过。所以这篇文章不只是把步骤列出来我会把每个关键选择的理由和调试中踩过的坑一起讲清楚。1. SLR(1)在整个编译实验里到底解决什么问题1.1 你要交付的不是一个算法而是一条自动化链路语法分析器在编译器里的位置是接在词法分析之后。词法分析给你一堆token语法分析负责判断这些token组成的序列是否符合文法规则并在分析过程中构建语法树——或者至少要能给出是否符合这个结论。实验要求的SLR(1)语法分析器本质上是一条自动化的流水线输入一个上下文无关文法输出一张可以在运行时驱动分析的分析表。SLR(1)全称是Simple LR(1)它是LR(0)的一种改进也是最容易上手的LR类分析方法。之所以叫简单是因为它只在LR(0)自动机的基础上做了非常谨慎的一步扩展归约时不再对所有终结符都施行而是只对FOLLOW集合中出现的终结符施行。我见过不少同学理解偏这个实验的交付目标以为重点是把驱动分析器那个循环写出来。其实驱动循环本身很短真正的重头戏在前面三段FIRST/FOLLOW集合计算、LR(0)项目集规范族构造、ACTION/GOTO表生成。你只要把这三段打通驱动循环几乎就是抄一遍书上几十行的伪代码。1.2 为什么选SLR(1)而不是LL(1)或LR(0)很多人在动手前会纠结一个问题明明LL(1)分析器也可以做为什么实验要指定用SLR(1)边界完全不同。LL(1)是自顶向下的预测分析它对文法左递归很敏感有了左递归基本就要先改写文法而文法改写是另一个大坑。LR系列是自底向上分析天然能处理左递归而且识别能力比LL(1)强。它也不是没有代价——分析表和自动机的构造复杂度高了好几个量级但这恰恰是这个实验想让你练的东西。那为什么不直接用LR(0)呢LR(0)分析表的构造规则太粗暴只要某个项目集里出现一个归约项目圆点在最右边就对所有终结符都做对应的归约动作完全不看下一个输入符号是什么。这导致大量本可以正常工作的文法在LR(0)下会产出冲突表。SLR(1)修复了这个问题归约动作只在FOLLOW集合允许的符号上出现冲突数量大幅下降。用一句话总结选型SLR(1)是在LR(0)自动机骨架上加了一点前瞻信息。它比LR(0)实用得多又比LR(1)实现简单是实验里性价比最高的选择。2. 先搞定两个前置集合FIRST和FOLLOW是SLR(1)的地基2.1 FIRST集合的迭代计算与Java实现要点FIRST集合在SLR(1)里的直接用途有两个一是计算FOLLOW集合二是在归约项目上帮你确定归约动作的候选符号。它的定义不难理解对任意文法符号串αFIRST(α)是所有可能从这里推导出的终结符的集合如果α能推导出空串就把空串ε也放进去。实际编码时我建议用迭代不动点写法而不是递归写法。递归写法在碰到间接左递归时会非常烧脑还要自己处理访问标记。迭代写法的思路是不断循环扫描所有产生式尝试往集合里加新元素直到某一轮一个元素都没加进去为止。每轮都加到满这件事在数学上叫求最小不动点。// 假设 first 已经初始化为 HashMapString, SetString元素为 boolean changed true; while (changed) { changed false; for (Production p : grammar.getProductions()) { String left p.getLeft(); ListString right p.getRight(); boolean allNullable true; for (String symbol : right) { if (isTerminal(symbol)) { if (first.get(left).add(symbol)) changed true; allNullable false; break; } else { for (String s : first.get(symbol)) { if (!s.equals(epsilon) first.get(left).add(s)) changed true; } if (!first.get(symbol).contains(epsilon)) { allNullable false; break; } } } if (allNullable) { if (first.get(left).add(epsilon)) changed true; } } }有几个细节值得单独拎出来说。第一isTerminal的判断必须统一标准。我实验里惯用的方式是用小写字母或大写字母区分终结符与非终结符或者直接在文法输入文件里用一个数组明确列出所有终极符。最忌讳的是在代码里到处用字符串比较判断后面调试到项目集的时候一个小小的判断偏差会让你怀疑人生。第二单字符的终结符可以直接用char处理但为了以后扩展到多字符终结符比如关键字、运算符最好一开始就把所有文法符号统一用String表示。我在实现时曾经把左部放在一个变量里、右部用一个List 后期扩展加多字符token时一点没费劲。第三迭代法停止条件。加引用一个sentinels或changed标志都可以但我建议用changed标志因为判断两个Set是否完全相等还要做一次完整比较代价更大。2.2 FOLLOW集合为什么要等FIRST完成后才能做FOLLOW(A)表示在某些句型中紧跟在非终结符A之后可能出现的一切终结符集合。计算FOLLOW必须用上FIRST结果所以二者有严格先后顺序。FOLLOW的计算规则有三条写代码前一定要把它们翻译成循环里的操作而不是死记教材公式对开始符号把结束符$加入FOLLOW(开始符号)。对形如 A → αBβ 的产生式FOLLOW(B) 从 FIRST(β) 中取所有元素去掉ε。对形如 A → αB 的产生式或者 A → αBβ 且 β 可推导出εFOLLOW(B) 要并入 FOLLOW(A)。第3条是初学最容易漏的。我写这段代码时先跑了一轮结果那个经典表达式文法的归约表怎么都对不上查来查去发现就是尾部可空这个分支写漏了导致FOLLOW(T)少收了很多符号。下面是修正后的核心片段for (Production p : grammar.getProductions()) { ListString right p.getRight(); for (int i 0; i right.size(); i) { String symbol right.get(i); if (isTerminal(symbol)) continue; SetString firstOfTail new HashSet(); boolean tailNullable true; for (int j i 1; j right.size(); j) { String next right.get(j); if (isTerminal(next)) { firstOfTail.add(next); tailNullable false; break; } firstOfTail.addAll(first.get(next)); if (first.get(next).contains(epsilon)) { firstOfTail.remove(epsilon); } else { tailNullable false; break; } } if (!firstOfTail.isEmpty()) { follow.get(symbol).addAll(firstOfTail); } if (tailNullable || i right.size() - 1) { follow.get(symbol).addAll(follow.get(p.getLeft())); } } }这段代码里最容易被忽略的就是那个i right.size() - 1当被处理的非终结符是产生式右部最后一个符号时不管后面有没有β都必须并入FOLLOW(左部)。整个FOLLOW计算同样用changed标志循环直到集合不再扩张。初学时常犯的另一个错误是忘记整个外层while要再跑一轮——因为在一次扫描中刚更新完的FOLLOW集合可能要立刻被后面的产生式使用一轮扫描往往不够。不动点迭代就是要反复扫描直到完全收敛。经验之谈FIRST和FOLLOW集合计算是整个项目里最容易出隐性bug的部分。如果你最后发现分析表某个地方多了一个不该有的归约动作十有八九是这里少加了一个符号。调试时先把这两个集合逐条打印出来和手工算的结果对一遍再往下走。3. 核心环节构造LR(0)项目集族并生成ACTION/GOTO表3.1 项目、闭包和GOTO函数LR(0)项目是带有圆点的产生式圆点表示分析器当前已经看到了产生式右部的哪些部分。比如产生式 E → E T对应四个项目E → ·E T还没看到任何符号E → E· T已经看到EE → E · T已经看到E和E → E T·整个右部都看完了其中圆点在最后的项目叫归约项目代表当前状态已经完整识别出这个产生式可以考虑用这个产生式进行归约。项目集族就是一些项目集合的集合。初始项目集I0是增广文法开始产生式比如 E → E的闭包。闭包操作规定如果一个项目形如 A → α·Bβ圆点后面紧跟着非终结符B那么所有形如 B → ·γ 的项目也在这个项目集里。我在Java里的LR(0)项目类就三个字段产生式对象、圆点位置、以及一个nextSymbol()方法——返回圆点后面的符号如果圆点在末尾就返回null。实现闭包时最关键的一点是闭包计算要反复进行因为新加入的项目可能会让新的非终结符出现在圆点后从而需要继续加入新项目直到集合稳定。SetLR0Item closure(SetLR0Item items) { SetLR0Item result new HashSet(items); boolean changed true; while (changed) { changed false; for (LR0Item item : new ArrayList(result)) { String next item.getNextSymbol(); if (next null || isTerminal(next)) continue; for (Production p : productionsByLeft.getOrDefault(next, List.of())) { LR0Item newItem new LR0Item(p, 0); if (result.add(newItem)) changed true; } } } return result; }实现时要小心一个事productionsByLeft要预先按左部建好Map。没有这个索引每次闭包都全表扫描所有产生式文法一大就慢得离谱。而且闭包里的newItem每次都new一个新对象如果LR0Item对equals/hashCode实现不好Set的去重就形同虚设。我建议LR0Item直接基于产生式编号圆点位置实现equals/hashCode这样既快又稳。GOTO函数则简单多了给定项目集I和文法符号X把I中所有圆点后面正好是X的项目圆点后移一位再对得到的新集合求一次闭包。比如GOTO({E → E·T, E → E·}, ) 就是 {E → E·T}再对T求闭包得到 {E → E·T, T → ·id...}。3.2 从项目集到分析表SLR(1)归约动作的精髓有了项目集和GOTO下一步就是用BFS式的worklist算法生成所有项目集。从I0开始对每个项目集、每个文法符号终结符和非终结符都算计算GOTO如果结果非空且是新项目集就加入列表不断处理直到没有新项目集。生成ACTION/GOTO表的规则可以浓缩成三句话移进如果项目 A → α·aβ 在Ii中且 GOTO(Ii, a)Ij那么 ACTION[i, a] 移进到j。这个a必须是终结符。归约如果项目 A → α· 在Ii中那么对FOLLOW(A)里的每个终结符aACTION[i, a] 按 A → α 归约。注意这里必须用FOLLOW(A)过滤——这正是SLR(1)和LR(0)的决定性区别。接受如果项目 S → S· 在Ii中那么ACTION[i, $] accept。GOTO表对非终结符A如果 GOTO(Ii, A)Ij那么GOTO[i, A]j。我在写表填充逻辑的时候遇到过一个很典型的问题如果某个ACTION格子里已经填了移进动作后面又冒出归约动作就发生移进-归约冲突如果已经填了归约动作又来了另一个归约动作就是归约-归约冲突。这两种冲突都说明这个文法不是SLR(1)文法。但更重要的是你要在写表的时候就主动检测冲突并停下来而不是等运行时输入串错了才追查。我当时的代码是这样做的if (action[i].containsKey(symbol)) { throw new GrammarConflictException(状态 i 在符号 symbol 上发生冲突已有 action[i].get(symbol) 试图写入 newAction); }这行检查能帮你节省大量排查时间。如果文法里真的有冲突早期的错误信息直接告诉你状态号和冲突符号比你在分析串的时候猜半天要有效得多。3.3 一张分析表的完整生成结果示例我实验里拿来做基准测试的文法是E - E E - E T | T T - id手工推一遍FIRST/FOLLOW之后生成的分析表示意如下状态id$ET0S3121S4acc2r(E→T)r(E→T)3r(T→id)r(T→id)4S355r(E→ET)r(E→ET)表里的S3表示移进到状态3r(E→T)表示按产生式E→T归约acc表示接受。空着的地方都是分析错误。我特别喜欢拿这张表做单元测试因为它足够小可以手算验证。只要代码生成的表和这张表逐格一致项目集构造和前两个集合计算基本就是对的。等这个文法跑通再换带有左递归、公共前缀的法式来压测。4. 总控程序状态栈、符号栈与分析驱动的Java实现4.1 表驱动分析器的栈模型分析表生成之后驱动部分简单清爽。你需要两个栈状态栈和符号栈还有一个当前输入符号lookahead。状态栈的栈顶代表当前所在的自动机状态符号栈记录已经看过的终结符和非终结符。初始时状态栈压入0符号栈压入哨兵$。整个分析过程其实就是在两个栈之间同步地做移进和归约。移进动作的本质是把当前输入符号压入符号栈把对应的新状态压入状态栈然后读下一个输入符号。归约动作的本质是根据产生式右部的长度从两个栈同时弹出若干元素把产生式左部压入符号栈再查GOTO表把新状态压入状态栈。我发现一个特别容易绕晕的点就是归约时弹栈的数量。产生式 A → β 右部长度是|β|那么弹出的状态数和符号数都必须正好是这个数。如果你在某个产生式上多弹了一个或少弹了一个栈结构立刻发散后面的查表全是错的。我在驱动循环里加了一个显式断言来守卫这个不变量。4.2 驱动循环与错误处理DequeInteger stateStack new ArrayDeque(); DequeString symbolStack new ArrayDeque(); stateStack.push(0); symbolStack.push($); String lookahead getNextToken(); // 从输入串取下一个终结符 while (true) { int state stateStack.peek(); Action action actionTable[state].get(lookahead); if (action null) { throw new SyntaxException(非法输入状态 state 符号 lookahead); } switch (action.getType()) { case SHIFT: stateStack.push(action.getTargetState()); symbolStack.push(lookahead); lookahead getNextToken(); break; case REDUCE: Production prod action.getProduction(); int len prod.getRight().size(); for (int i 0; i len; i) { stateStack.pop(); symbolStack.pop(); } String left prod.getLeft(); symbolStack.push(left); int prevState stateStack.peek(); Integer nextState gotoTable[prevState].get(left); if (nextState null) throw new SyntaxException(GOTO表无入口); stateStack.push(nextState); break; case ACCEPT: return true; default: throw new IllegalStateException(未知动作类型); } }错误处理这块课程要求通常是检测到错误并报错即可不要求做错误恢复。所以我在驱动循环里对查表失败的格子直接抛异常简单明了。如果你想做得更完善一点可以在报错时把当前状态栈和符号栈的内容打出来帮助定位错误发生的文法位置。4.3 测试输入串时最容易忽略的细节我周围做这个实验的同学里有一半最后不是算法写错而是输入串的处理方式出了问题。主要有三个坑。第一个坑是输入串末尾必须带上$。分析器依赖$做accept判断你如果喂进去一个不带$的串表里查不到对应的列永远得不到正确结果。第二个坑是终结符的匹配要事先分词。比如输入串写成id id你要先把空格去掉或者用正则切出一个个token再喂给驱动循环。如果你直接把idid当成一个一个char处理那id会被拆成i和d两个字符整个分析全部错乱。我实验里专门写了一个极简的分词器负责从输入字符串里读取下一个终结符。第三个坑是空串。如果文法中含有ε产生式比如 E → ε那么输入串为空时分析器也应该正常工作。但很多实现没处理这种情况因为getNextToken在没有token时返回null驱动循环直接在查表时报错。要让代码支持ε产生式需要在词法层面定义一个表示空的终结符让它能正确驱动归约和accept。5. 我实际编码时踩过的坑和调试方法5.1 闭包计算写成死循环我最早写闭包的时候没有意识到新加入的项目也可能带着新的圆点后非终结符直接在foreach循环里一边遍历一边把新项目加入同一个Set。理论上这也没错但我在迭代器里修改集合Java直接抛出ConcurrentModificationException。换成new HashSet(result)做快照之后再遍历倒是能跑通了但如果你用的快照只取了一次仍然可能出现这一轮新加入的项目本来还该触发更多闭包却被遗漏的问题。正确做法是像我上面代码那样用while changed标志做外层循环反复扫描直到集合不再变化。闭包计算本质上和FIRST/FOLLOW一样也是一个固定点迭代。想通这一点你就不会再犯只扫一遍的错误。5.2 终结符判定与空串ε处理我用的文法里终结符只有小写字母单词比如id、、*非终结符是大写字母。看起来很好区分但在项目集构造里只要你有一处把这种终结符误判成非终结符GOTO函数就会把它的目标状态放到GOTO表里去而漏掉ACTION表里的移进动作分析器跑起来必崩。更隐蔽的是ε的处理。在FIRST集合里ε有明确含义但在分析表构造时归约项目 A → α· 对应的归约动作永远不该包含ε因为输入串里不会出现一个叫ε的token。我早期代码把FIRST集合整个搬过来直接用于FOLLOW结果FOLLOW里混进了ε归约表的符号列里出现了ε驱动循环永远查不到这个token。后来我定了一条规矩FIRST集合里可以出现ε但所有用到FIRST结果去填充FOLLOW或分析表的地方都必须显式remove(epsilon)。为此我在代码里加了一个过滤函数所有集合合并都走这个函数彻底断了ε外传的可能。5.3 用分阶段打印定位冲突来源这个实验最大的调试困难在于它是一条串行流水线前面一个环节的错要到很后面的环节才会以莫名其妙的冲突形式爆发。如果你直接看最终分析表可能完全看不出来哪个集合算错了。我采用的调试策略是分阶段打印。第一步打印每个非终结符的FIRST和FOLLOW集合用手工结果核对。第二步打印全部项目集每个项目集一行逐条检查闭包是否少项。第三步打印最终分析表用我上面那个三产生式的基准文法逐格比对。三个阶段各留下一份文本输出任何一步出现问题直接定位到对应函数去debug。这个习惯帮我解决了一个特别顽固的问题有一次归约动作和移进动作冲突我盯着分析表看了一个多小时最后发现是FOLLOW计算时把A → αBβ中β为可空的判断写错了导致FOLLOW(B)里多了一个本不该出现的终结符最终在某个状态上产生虚假冲突。如果没有第一阶段打印FOLLOW集合我可能还在后面翻驱动循环的代码。6. SLR(1)的边界在哪里以及如何向LR(1)扩展6.1 一个典型的SLR(1)无能为力的文法SLR(1)的局限在于它用FOLLOW集合作为归约条件的全部依据而FOLLOW集合是整个文法层面的全局信息太粗糙了。一个典型的反例是带悬空else的文法S - if E then S S - if E then S else S S - other在分析到if E then S·这个状态时如果下一个输入符号是else分析器面临两难是把这个S归约掉还是移进else继续匹配更长的if语句SLR(1)只查FOLLOW(S)而FOLLOW(S)由于第二条产生式的存在必然包含else于是它认为else时可以归约同时又因为第一条产生式后可以合法地跟着else而想移进冲突就此产生。这个文法其实语法上并没有歧义悬空else的语义是else尽量匹配最近的if正确的做法应当是在这个特定状态下选择移进。但SLR(1)拿到的全局FOLLOW信息做不到这种精细判断它不知道这个else是不是真的跟着当前这条if语句。6.2 从SLR(1)到LR(1)的最小改动思路LR(1)的解法是给每一个项目额外附带一个前瞻终结符。比如归约项目写成 [A → α·, a] 的形式意思是只有当下一个输入符号是a时才用这个产生式归约。这样每个归约动作都被精确限制在局部上下文里而不是全局FOLLOW集合悬空else的冲突就能被消解。如果你在这个实验之后想做扩展改动不算大项目结构从产生式圆点位置变成产生式圆点位置前瞻符集合闭包操作里新增一个计算前瞻符集合的步骤归约动作也按每个项目自己的前瞻符集合来填ACTION表。原理上一个晚上就能理清实现量比SLR(1)多出大概三成但效果立竿见影——很多SLR(1)下无解的文法在LR(1)下都能顺利出表。之后再往后走一步把拥有相同核心项目、不同前瞻符的状态合并就是LALR(1)分析器的雏形。我在把SLR(1)跑通之后就把代码里项目集相关的类抽成了接口然后额外实现了一个LR(1)版本。因为数据结构一开始就多用Set和Map组装改成LR(1)项目时只需要替换项目对象的equals/hashCode和闭包逻辑驱动循环完全复用。如果你时间充裕强烈建议也试一试这会让你对前瞻信息到底存放在哪里这个问题有本质上的理解。另外提醒一句实验报告的书写也别全放在最后一天赶。哪怕中间只写了FIRST/FOLLOW两张集合表先把运行结果截下来后面再补原理分析都会轻松很多。分析表生成的打印输出是你调试和报告都能用的第一手素材保留好它能少很多返工。