尧图网页设计 语法分析：项目集规范族、分析表与Java实现)
1. 为什么我重新捡起 LR(0) 分析我在把编译原理学习笔记写到第七篇时终于绕不开 LR(0) 分析。前面几篇大多停留在词法分析实验用 Java 写一个 Lexer把正则表达式转成 NFA再转 DFA最后给每个单词打上 token 类型。那部分做完很多人会产生一种错觉——编译原理好像就是状态机加表格。等到语法分析这一章尤其是 LR(0) 分析才发现前面那些自动机思想只是热身真正的“栈加状态加分析表”的思考方式从这里才开始成型。LR(0) 分析是自底向上语法分析里最基础、最干净也最严格的一种模型。它从左到右扫描输入串构造最右推导的逆过程并且在做归约决策时不需要向前看任何输入符号所以叫 LR(0)。它能做的事情很具体给定一个上下文无关文法构造 LR(0) 项目集规范族生成一张 ACTION 表和一张 GOTO 表然后用一个状态栈配合输入指针完成移进、归约、接受和报错。很多编译原理课程设计、面试题、选择题都会围绕这套流程反复出题因为它足够机械也足够暴露你是否真正理解了“项目”“闭包”“GOTO”“冲突”这些概念。这篇笔记适合正在做编译原理实验的人也适合已经学过一遍但一遇到项目集规范族就发懵的人。我会尽量不用那种“先定义再证明”的教材腔而是把 LR(0) 分析拆成一条可以手推、可以写代码、可以排查错误的路线。你如果只会 Java 基础语法也能看懂后面的代码骨架你如果正准备面试也可以直接拿里面的冲突排查表和易错点去复习。1.1 词法分析实验之后语法分析这道坎词法分析实验的产出通常很直观输入一段源代码输出一串 token每个 token 有类型、值、行号。比如int a 10;会变成KEYWORD(int)、ID(a)、ASSIGN、NUMBER(10)、SEMI。这部分用 Java 写起来很舒服因为正则、状态机、字符流处理都是看得见摸得着的东西。但语法分析不一样它不再关心单个单词长什么样而是关心这些单词能不能按照文法组成一棵语法树。很多人第一次接触 LR(0) 分析时最大的障碍不是算法本身而是不知道“项目”到底在描述什么。教材上写A - α . β圆点表示分析位置。这句话单独看很抽象放到栈里就清楚了圆点左边是已经识别并压入栈的部分圆点右边是还没处理的部分。分析器每走一步要么把下一个输入符号移进栈让圆点右移一格要么发现某个产生式右部已经全部识别完就把这一串符号归约成左部非终结符。LR(0) 分析的核心就是提前把所有可能的圆点位置算出来组成项目集再根据项目集之间的跳转关系生成分析表。所以词法分析实验和 LR(0) 分析之间并不是割裂的。词法分析给出 token 流LR(0) 分析消费 token 流。你在词法阶段用 DFA 识别单词在语法阶段用项目集 DFA 识别句型。两者都依赖自动机只是一个跑在字符上一个跑在 token 上。理解这一点之后LR(0) 项目集规范族就不再是凭空冒出来的表格而是语法分析器脑子里的“状态地图”。1.2 LR(0) 的定位最严格也最干净的自底向上模型LR(0) 里的“0”不是零个状态也不是零个产生式而是零个向前看符号。它在决定归约时只看当前栈顶状态里有没有归约项目不看下一个输入符号是什么。这个设计让 LR(0) 分析表非常容易构造但也让它的适用范围很窄。只要一个状态里同时存在“可以移进”和“可以归约”的项目LR(0) 就不知道该怎么办这就是移进/归约冲突。如果同一个状态里有两个不同的归约项目还会出现归约/归约冲突。不过LR(0) 的价值并不因为它弱而降低。相反它是理解 SLR(1)、LALR(1)、LR(1) 的必经台阶。SLR(1) 只是在 LR(0) 的归约动作上加了 FOLLOW 集限制LALR(1) 进一步合并同心项目集并携带更精确的搜索符LR(1) 则给每个项目都配上搜索符分析能力最强但状态数也最多。你如果跳过 LR(0) 直接看 LALR会觉得自己在背表你如果先把 LR(0) 的项目集规范族亲手推一遍再看 SLR 和 LALR就会发现它们只是在对 LR(0) 的冲突打补丁。我在实际复习时有一个习惯每学一种 LR 分析都拿同一条小文法去推。比如S - C C、C - c C | d这条经典文法LR(0) 没有冲突SLR 也没有冲突很适合用来对照。等推到表达式文法E - E T | T、T - T * F | F、F - ( E ) | id时冲突开始出现你就能清楚看到 LR(0) 在哪里卡住SLR 又是用哪个集合把它救回来。这种对照式学习比单独背定义有效得多。1.3 这篇笔记适合谁如果你正在做编译原理课程设计已经写完词法分析下一步准备接语法分析那么这篇笔记可以直接当作 LR(0) 部分的实现路线。如果你正在准备考试或面试需要快速判断“这个文法是不是 LR(0) 文法”“项目集里为什么会有冲突”“ACTION 表和 GOTO 表怎么填”后面的速查表可以拿来就用。如果你只是对编译器感兴趣想找一个不算太大的切入点LR(0) 也是一个很好的起点因为它把“栈”“状态”“归约”这些概念压缩在几百行代码里跑通之后成就感很足。需要提前说明的是LR(0) 分析并不要求你先把所有形式语言理论都学完。你只要会集合运算知道什么是终结符、非终结符、产生式能看懂简单的栈操作就可以开始。真正难的地方在于细心项目集闭包容易漏项GOTO 容易忘了闭包归约填表容易和 SLR 搞混。后面我会把这些问题一个个拆开并给出我踩过的坑。2. LR(0) 的核心概念和设计思路拆解LR(0) 分析看起来表格很多但核心概念只有五个增广文法、LR(0) 项目、CLOSURE 闭包、GOTO 函数、项目集规范族。把这五个东西连起来就是一条完整的构造流水线。很多人学到这里会陷入“每个词都认识连起来不知道在干什么”的状态原因是教材习惯先给定义再给算法而实际思考顺序应该是反过来的先问分析器需要知道什么再问项目怎么表达这些知识最后问项目集怎么组织成表。分析器在某个时刻需要知道两件事第一栈里的符号串目前可能对应哪些产生式的哪个位置第二如果下一个输入符号是某个终结符应该移进还是归约归约又要用哪条产生式。LR(0) 项目的圆点就是用来回答第一件事的项目集就是所有可能位置的集合CLOSURE 用来把“待约项目”展开成“准备识别这个非终结符”的项目GOTO 用来描述吃掉一个符号之后项目集怎么跳转。ACTION 和 GOTO 表则是把这些跳转关系翻译成机器能查的表格。2.1 增广文法把接受动作变成唯一目标在构造 LR(0) 分析表之前第一步永远是增广文法。假设原文法的开始符号是S我们引入一个新的开始符号S并添加产生式S - S。这个动作看起来很多余但它解决了一个关键问题分析器什么时候知道整个输入串已经成功识别了如果没有增广开始符号S可能出现在其他产生式右部分析器看到S被归约出来时无法确定它是作为整个句子的开始符号还是只是某个更大结构的一部分。增广之后只有S - S .这个项目代表“整个输入已经归约到开始符号”此时遇到输入结束符$就可以执行接受动作。增广还有一个好处它让接受状态唯一。LR(0) 项目集规范族里S - S .所在的状态就是接受状态。这个状态通常只有一个项目不会和其他项目混在一起。如果原文法开始符号出现在右部比如S - A S那么S可能在多个位置被归约接受条件会变得模糊。增广之后S只出现在新产生式左部不会出现在任何右部所以S - S .是独一无二的。实际写代码时我建议把增广产生式放在产生式列表的第 0 条并用一个单独的类或结构体表示产生式编号、左部、右部列表。这样后面项目只需要记录“产生式编号 圆点位置”不用反复存左部和右部字符串。很多初学者构造项目集时直接用字符串拼接结果去重和比较都很痛苦。用编号加圆点位置项目相等判断就是两个整数比较效率高也不容易出错。2.2 LR(0) 项目圆点代表“我走到哪了”LR(0) 项目的形式是A - α . β其中A - αβ是文法产生式。圆点把右部分成两半左边α是已经识别并压栈的部分右边β是还没处理的部分。根据圆点位置项目可以分为四类。圆点后面是终结符的项目叫移进项目比如A - α . a β遇到输入符号a时应该移进。圆点后面是非终结符的项目叫待约项目比如A - α . B β它本身不直接触发动作但会通过闭包把B的产生式加进来。圆点在末尾的项目叫归约项目比如A - α .表示这个产生式右部已经全部识别完可以把α归约成A。增广开始符号对应的S - S .是接受项目。理解项目的关键是把圆点看成“进度条”。例如产生式C - c C可能的项目有三个C - . c C、C - c . C、C - c C .。第一个表示还没开始识别第二个表示已经吃掉了c正在等待C第三个表示整个右部c C已经识别完可以归约成C。分析器栈里存的不是符号串本身而是状态号但状态号背后对应的就是这些项目。你看到状态 3 里有C - c . C就知道当前栈顶刚刚处理完一个c接下来要识别一个C。有一个常见误区把圆点左边的符号理解成“已经归约完成的非终结符”。其实左边可以是终结符也可以是非终结符甚至是空串。比如C - . c C圆点在最左边左边为空C - c . C左边是终结符cC - c C .左边是c C两个符号。分析器在移进和归约过程中栈里的符号会不断变化项目集只是在抽象层面描述“当前可能处于哪些进度”。2.3 CLOSURE 与 GOTO项目集的两条腿CLOSURE 闭包解决的是“待约项目展开”的问题。假设当前项目集里有一个项目A - α . B β圆点后面是非终结符B。分析器如果想继续推进就必须先识别出一个B。那么B怎么识别当然是用B的产生式。所以闭包操作会把所有B - . γ形式的项目加入当前项目集。如果这些新加入的项目圆点后面又是非终结符还要继续展开直到项目集不再增大为止。这个过程很像“计划分解”你要完成A当前卡在B于是把B的所有子计划列出来子计划里又卡在C继续列C的子计划。GOTO 函数解决的是“吃掉一个符号之后去哪里”。给定项目集I和文法符号XGOTO(I, X)的计算分两步先从I中找出所有圆点后面正好是X的项目把圆点向右移动一格然后对移动后的项目集合求闭包。得到的新项目集就是GOTO(I, X)。如果X是终结符这个动作对应分析表中的移进如果X是非终结符对应分析表中的 GOTO 跳转。换句话说ACTION 表负责终结符GOTO 表负责非终结符两者合起来就是项目集 DFA 的转移边。我刚开始学时总是把闭包和 GOTO 的顺序搞反。记住一个口诀先移动再闭包。GOTO 不是先闭包再移动而是先筛选出能移动的项目移动圆点最后才求闭包。如果你先闭包再移动会把很多不该移动的项目也带进去项目集立刻爆炸。这个顺序在手工推项目集时尤其重要写代码时也一样gotoSet函数内部必须先遍历原项目集找到圆点后匹配X的项目生成新项目再去调用closure。2.4 项目集规范族与 DFA为什么状态能代表分析进度把所有项目集放在一起用 GOTO 关系连起来就得到项目集规范族。它本质上是一个确定有限自动机每个项目集是一个状态每个文法符号是一条转移边。初始项目集是CLOSURE({S - . S})接受项目集包含S - S .。DFA 的接受状态就是分析器可以接受输入的状态。这个 DFA 不是用来识别单词的而是用来识别“语法分析进度”的。输入串每读一个 tokenDFA 就沿着移进边跳一步归约发生时DFA 会沿着 GOTO 边跳回某个状态相当于把一串已识别的符号折叠成一个非终结符。为什么状态能代表分析进度因为栈顶状态对应的项目集包含了当前栈里符号串所有可能的产生式位置。分析器不需要记住整个栈里每个符号的具体值只需要记住状态号。状态号加上 GOTO 表就足以恢复出“如果现在归约应该跳到哪个状态”。这也是 LR 分析比递归下降更省心的原因递归下降要靠函数调用栈隐式保存进度LR 分析把进度显式地做成状态和表。表一旦构造正确分析过程就是机械查表没有回溯也没有递归深度风险。项目集规范族的规模可能很大。对于表达式文法手工推十几个状态很正常对于真实编程语言状态数可能上千。所以实际编译器很少手写 LR 表而是用工具生成。但学习阶段一定要手推至少一条小文法否则你只会用工具遇到冲突不知道怎么改文法。我的建议是先推S - C C、C - c C | d再推表达式文法最后再去看工具生成的表。这样从简单到复杂不会被状态数吓退。3. 从零构造 LR(0) 分析表一条文法走到底理论讲完必须落到一条具体文法上。我选下面这条经典 LR(0) 文法S - C C C - c C C - d终结符集合是{ c, d }非终结符集合是{ S, C }。增广之后得到0: S - S 1: S - C C 2: C - c C 3: C - d这条文法生成的句子是“两个 C 拼接”每个 C 要么是d要么是c后面再跟一个 C。比如d d、c d d、c c d d都是合法句子。它没有左递归也没有空产生式状态数少而且 LR(0) 没有冲突非常适合作为第一条手推文法。你把它推熟之后再去看更复杂的表达式文法会轻松很多。3.1 选一条小文法避免一上来被规模吓退很多人一上来就拿E - E T | T、T - T * F | F、F - ( E ) | id练手结果项目集推到十几个状态闭包展开一大片很快就乱了。表达式文法当然重要但它包含左递归、多个优先级层次、括号嵌套项目集数量多冲突也典型。初学阶段用它容易把“项目集构造”和“冲突处理”两件事混在一起。先拿S - C C这条文法可以只关注项目、闭包、GOTO、分析表不被冲突干扰。这条文法还有一个好处它能展示“同一个非终结符在不同位置被识别”的情况。C既出现在S - C C的第一个位置也出现在第二个位置还出现在C - c C的末尾。项目集里会看到S - C . C、C - c . C等不同进度。分析器需要区分这些位置而 LR(0) 项目集正好能把它们分开。你手工推一遍就能明白为什么状态 2 和状态 3 看起来很像但 GOTO 行为不同。另外这条文法的输入串短。比如c d d分析过程只有十来步栈变化可以完整写在纸上。d d更短但看不出C - c C的递归归约c c d d稍长但也在可接受范围内。我建议先用d d验证基本移进归约再用c d d验证递归归约。两个例子跑通LR(0) 分析的骨架就立起来了。3.2 手工构造项目集规范族初始项目集I0由增广产生式的项目S - . S求闭包得到。闭包过程如下先有S - . S圆点后是S所以加入S的所有产生式项目S - . C C。这个项目圆点后是C所以加入C的所有产生式项目C - . c C和C - . d。此时没有新的待约项目闭包结束。因此I0: S - . S S - . C C C - . c C C - . d从I0出发分别对S、C、c、d求 GOTO。对SI0中只有S - . S圆点后是S移动圆点得到S - S .闭包无新增。所以I1 GOTO(I0, S): S - S .对CI0中S - . C C圆点后是C移动得到S - C . C。闭包展开圆点后是C加入C - . c C、C - . d。所以I2 GOTO(I0, C): S - C . C C - . c C C - . d对cI0中C - . c C圆点后是c移动得到C - c . C。闭包展开圆点后是C加入C - . c C、C - . d。所以I3 GOTO(I0, c) GOTO(I2, c) GOTO(I3, c): C - c . C C - . c C C - . d对dI0中C - . d圆点后是d移动得到C - d .。闭包无新增。所以I4 GOTO(I0, d) GOTO(I2, d) GOTO(I3, d): C - d .继续从I2对C求 GOTOI2中S - C . C圆点后是C移动得到S - C C .闭包无新增。所以I5 GOTO(I2, C): S - C C .从I3对C求 GOTOI3中C - c . C圆点后是C移动得到C - c C .闭包无新增。所以I6 GOTO(I3, C): C - c C .最终项目集规范族包含I0到I6共七个状态。转移关系可以整理成GOTO(I0, S) I1GOTO(I0, C) I2GOTO(I0, c) I3GOTO(I0, d) I4GOTO(I2, C) I5GOTO(I2, c) I3GOTO(I2, d) I4GOTO(I3, C) I6GOTO(I3, c) I3GOTO(I3, d) I4注意I3对c的 GOTO 是它自己因为C - . c C移动后还是C - c . C闭包后又加入C - . c C和C - . d和I3完全相同。这种自循环在递归产生式中很常见。手工推的时候建议每构造一个新项目集就和已有的项目集比较一下如果项目集合相同直接复用编号不要重复创建状态。3.3 填 ACTION 与 GOTO 表有了项目集规范族和 GOTO 关系就可以填分析表了。填表规则有四条如果项目A - α . a β在状态i中且a是终结符并且GOTO(i, a) j那么ACTION[i, a] shift j。如果项目A - α .在状态i中那么对每个终结符a和输入结束符$都填ACTION[i, a] reduce A - α。如果项目S - S .在状态i中那么ACTION[i, $] accept。如果GOTO(i, A) j其中A是非终结符那么GOTO[i, A] j。这里要特别提醒严格 LR(0) 的归约动作是对所有终结符都填不看 FOLLOW 集。很多教材为了减少表项只对 FOLLOW 集填归约那其实已经带上了 SLR(1) 的味道。初学阶段一定要区分清楚否则后面学 SLR 时会不知道“多出来的 FOLLOW 限制”到底加在哪里。根据上面的项目集ACTION 表和 GOTO 表如下。r1表示按产生式 1S - C C归约r2表示按产生式 2C - c C归约r3表示按产生式 3C - d归约。状态cd$SC0s3s4121acc2s3s453s3s464r3r3r35r1r1r16r2r2r2这张表里状态 4 只有归约项目C - d .所以对所有终结符都执行r3。状态 6 只有归约项目C - c C .所以对所有终结符都执行r2。状态 5 只有归约项目S - C C .所以对所有终结符都执行r1。状态 1 有接受项目S - S .所以遇到$执行acc。状态 0、2、3 都有移进项目所以对c和d分别移进到状态 3 和 4。GOTO 部分只填非终结符状态 0 对S跳到 1对C跳到 2状态 2 对C跳到 5状态 3 对C跳到 6。你可能会问状态 5 对c和d也填r1会不会在输入还没结束时就错误归约在 LR(0) 分析里这种“多余归约”是允许的因为分析器后面迟早会遇到错误。只要归约动作和移进动作没有冲突表就是可用的。实际输入c d d在状态 5 时已经读到$所以会正常执行r1。如果输入是c d d c状态 5 遇到c也会先归约S - C C然后进入状态 1再遇到c时报错。错误发现得晚一点但不影响正确性。3.4 跑一遍输入串移进归约栈变化拿输入串c d d走一遍能最直观地看到移进和归约如何配合。输入末尾加上$所以待处理串是c d d $。分析栈初始为状态 0。下面这张表记录了每一步的状态栈、剩余输入和动作。步骤状态栈剩余输入动作10c d d $状态 0 遇 c移进到 320 c 3d d $状态 3 遇 d移进到 430 c 3 d 4d $状态 4 遇 d按 C - d 归约40 c 3 C 6d $GOTO(3, C)6状态 6 遇 d按 C - c C 归约50 C 2d $GOTO(0, C)2状态 2 遇 d移进到 460 C 2 d 4$状态 4 遇 $按 C - d 归约70 C 2 C 5$GOTO(2, C)5状态 5 遇 $按 S - C C 归约80 S 1$GOTO(0, S)1状态 1 遇 $接受第 3 步归约C - d时栈顶是d 4右部长度是 1所以弹出状态 4暴露状态 3。因为GOTO(3, C)6所以压入C 6。第 4 步归约C - c C时栈顶是c 3 C 6右部长度是 2弹出状态 6 和 3暴露状态 0。因为GOTO(0, C)2所以压入C 2。这里注意归约弹出的是右部长度对应的状态数不是符号数因为栈里存的是状态。符号本身不需要存状态号已经隐含了符号信息。第 7 步归约S - C C时栈顶是C 2 C 5右部长度是 2弹出状态 5 和 2暴露状态 0。因为GOTO(0, S)1压入S 1。最后状态 1 遇到$执行接受。整个过程没有回溯每一步都是查表决定这就是 LR 分析的魅力。你如果能在纸上完整写出这张表说明已经理解了移进、归约、GOTO 的配合方式。3.5 Java 实现 LR(0) 的关键数据结构和代码骨架用 Java 实现 LR(0) 分析器不需要一上来就写几千行。核心结构只有几个产生式、项目、项目集、闭包、GOTO、规范族、分析表。下面是一段简化骨架重点展示思路省略了完整的错误处理和界面代码。import java.util.*; class Production { int id; String lhs; ListString rhs; Production(int id, String lhs, ListString rhs) { this.id id; this.lhs lhs; this.rhs rhs; } } class Item { int prodId; int dot; Item(int prodId, int dot) { this.prodId prodId; this.dot dot; } 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 Objects.hash(prodId, dot); } } public class LR0Builder { ListProduction grammar new ArrayList(); MapString, ListInteger prodByLhs new HashMap(); SetString terminals new HashSet(); SetString nonTerminals new HashSet(); // 求闭包不断展开圆点后面的非终结符 SetItem closure(SetItem items) { SetItem result new HashSet(items); DequeItem queue new ArrayDeque(items); while (!queue.isEmpty()) { Item item queue.poll(); Production p grammar.get(item.prodId); if (item.dot p.rhs.size()) continue; String symbol p.rhs.get(item.dot); if (!nonTerminals.contains(symbol)) continue; for (int pid : prodByLhs.getOrDefault(symbol, Collections.emptyList())) { Item newItem new Item(pid, 0); if (result.add(newItem)) { queue.add(newItem); } } } return result; } // GOTO先移动圆点再求闭包 SetItem gotoSet(SetItem items, String symbol) { SetItem moved new HashSet(); for (Item item : items) { Production p grammar.get(item.prodId); if (item.dot p.rhs.size() p.rhs.get(item.dot).equals(symbol)) { moved.add(new Item(item.prodId, item.dot 1)); } } return closure(moved); } }这段代码里closure用队列避免递归过深gotoSet严格遵守“先移动再闭包”。接下来构造项目集规范族时可以用一个ListSetItem states保存所有状态再用MapString, Integer做状态去重。状态 key 可以把项目排序后拼成字符串例如prodId.dot|prodId.dot。每生成一个新项目集先查 key 是否已存在如果不存在分配新状态号并加入队列继续对每个文法符号求 GOTO。填表阶段遍历每个状态和每个项目。如果项目是移进项目查GOTO表得到目标状态填shift如果项目是归约项目对所有终结符填reduce如果是接受项目对$填accept。冲突检测也在这一步如果同一个表格单元已经被填过并且新动作和旧动作不同就记录冲突。实际写代码时我建议把 ACTION 表设计成MapInteger, MapString, ActionAction 可以是字符串也可以是枚举。调试时把表按状态号排序输出一眼就能看出哪一行有冲突。4. LR(0) 冲突排查与常见坑LR(0) 分析表构造过程中冲突几乎是必然会遇到的。没有冲突的 LR(0) 文法其实不多大多数实用文法都需要更强的分析方法。但冲突并不可怕可怕的是不知道冲突从哪里来。很多人看到“移进/归约冲突”就懵了其实只要回到项目集找到那个同时包含移进项目和归约项目的状态问题就定位了一半。剩下的一半是判断应该改文法、换分析方法还是调整优先级。我在调试 LR(0) 分析器时习惯按“项目集 - GOTO - 分析表”的顺序排查。先确认项目集闭包有没有漏项再确认 GOTO 是不是先移动再闭包最后看分析表填表规则有没有和 SLR 搞混。大部分错误都不是算法不会而是细节顺序错了。下面把典型冲突和排查方法拆开讲。4.1 移进/归约冲突为什么同一个状态里会有两个声音移进/归约冲突出现在一个状态同时包含移进项目和归约项目时。比如状态里有A - α . a β和B - γ .。遇到输入符号a时分析器有两个选择一是移进a沿着A - α . a β继续二是按B - γ .归约把栈顶的γ折叠成B。LR(0) 不看下一个输入符号之外的信息它只看当前状态所以不知道应该移进还是归约于是冲突。经典的例子是悬空 else 文法S - if E then S S - if E then S else S S - other在if E then S . else S和S - if E then S .同时存在的状态里遇到else既可以移进也可以归约。大多数语言规定else与最近的if匹配所以选择移进。这个选择不是 LR(0) 自动做出来的而是人为规定优先级。另一个例子是表达式文法E - E E | E * E | id遇到或*时既有移进又有归约需要规定*优先级高于并且和*左结合。排查移进/归约冲突时先找到冲突状态打印该状态所有项目。如果归约项目对应的产生式是A - α .看看输入符号是否可能在FOLLOW(A)中。如果是SLR(1) 可能能解决如果不在可能是文法本身有优先级问题。对于表达式通常不靠改文法而是靠优先级和结合性声明。对于课程设计如果老师要求纯 LR(0)那就必须改文法把二义性消掉或者接受这个文法不是 LR(0) 文法。4.2 归约/归约冲突文法二义性的影子归约/归约冲突出现在同一个状态里有多个归约项目时。比如状态里同时有A - α .和B - β .遇到某个输入符号时分析器不知道应该归约成A还是归约成B。这种冲突通常说明文法有二义性或者虽然文法无二义但 LR(0) 的粗粒度项目集无法区分两个归约的上下文。举一个简化例子S - A S - B A - x B - x当分析器识别完x后可能归约成A也可能归约成B而两者都能到达S。此时状态里会同时存在A - x .和B - x .产生归约/归约冲突。要解决它要么合并A和B要么改文法让x的上下文不同要么使用 LR(1) 这类携带搜索符的分析方法。SLR(1) 在这种情况下也可能帮不上忙因为FOLLOW(A)和FOLLOW(B)可能重叠。归约/归约冲突比移进/归约冲突更麻烦因为它往往意味着文法设计有问题。实际排查时我会先看两个归约项目的左部非终结符是否可以合并。如果它们语义相同只是名字不同合并最简单。如果语义不同就要检查文法是否真的需要两个不同的产生式或者是否可以通过提取公因子、分层改写来消除。实在不行就升级到 LALR(1) 或 LR(1)。4.3 SLR(1) 怎么救场以及为什么它不总是够SLR(1) 的“S”是 Simple 的意思。它在 LR(0) 的基础上只改了一件事归约动作不再对所有终结符都填而是只对归约产生式左部非终结符的 FOLLOW 集填。回到前面的状态 4项目C - d .如果按 SLR只对FOLLOW(C)里的符号填r3。在这条文法里FOLLOW(C) { c, d, $ }所以看起来和 LR(0) 全填差不多。但在有冲突的文法里FOLLOW 集限制可以排除掉一些不该归约的输入符号从而消除移进/归约冲突。SLR 的局限在于 FOLLOW 集太粗。它只知道“某个非终结符后面可能跟哪些终结符”不知道“在当前这个具体状态下它后面到底能跟哪些终结符”。如果两个不同归约项目的 FOLLOW 集有重叠SLR 仍然冲突。LALR(1) 通过给每个项目附加更精确的搜索符把同心项目集合并既减少了状态数又比 SLR 更强。LR(1) 则给每个项目单独配搜索符分析能力最强但状态数可能非常多。学习顺序上LR(0) 到 SLR 到 LALR 到 LR(1)每一步都在解决上一步的不足理解这条线索比死记表更有用。实际用工具生成分析器时像 Yacc、Bison 这类工具默认使用 LALR(1)遇到冲突会报告出来让你通过优先级或改文法解决。你在课程设计里如果手写 LR(0)可以先实现 LR(0)再把归约填表改成 FOLLOW 集就得到了 SLR(1)。代码改动很小但分析能力提升明显。这也是为什么很多教材把 LR(0) 和 SLR(1) 放在一起讲前者是骨架后者是第一次有效增强。4.4 调试速查表从项目到分析表逐层定位下面这张表是我自己排查 LR(0) 问题时总结的速查表。遇到分析器行为不对可以按现象逐层往上找。现象可能原因排查方法项目集数量异常多闭包漏了去重或 GOTO 没有复用相同项目集给每个项目集生成排序 key比较是否重复某个状态缺少待约项目闭包只展开了一层没有用队列继续展开检查闭包是否循环到项目集不再增大GOTO 目标错误先闭包再移动而不是先移动再闭包打印移动前后的项目集合确认圆点位置归约动作填得太多把 LR(0) 和 SLR(1) 搞混确认是否对所有终结符填还是只对 FOLLOW 填分析表出现冲突状态里同时有移进和归约项目或多个归约项目打印冲突状态的所有项目找左部和圆点位置输入串错误地被接受接受状态判断错或归约产生式编号错检查S - S .是否只对应$的 accept输入串合法却报错GOTO 表填错或状态栈弹出长度错单步打印状态栈、剩余输入、动作和手工表对照我踩过最多的坑是“项目集去重”。早期我用字符串直接表示项目比如S-.CC结果空格、箭头、圆点位置稍微不一致就生成重复状态。后来改成“产生式编号 圆点位置”的整数对再去重问题立刻消失。另一个坑是归约弹出长度。归约时应该弹出右部长度个状态而不是弹出整个栈。比如C - c C右部长度是 2就弹出栈顶两个状态然后暴露新栈顶查 GOTO 表压入左部非终结符对应的状态。这个细节写错表现就是分析到一半状态栈乱掉后面全是错误。5. 面试、课程设计和后续学习的高频问题LR(0) 分析不仅是课程内容也是编译原理面试和选择题的高频考点。面试官不会让你现场推十几个状态但很可能问你“LR(0) 项目有哪几类”“CLOSURE 和 GOTO 的区别”“LR(0) 和 SLR(1) 差在哪里”“移进/归约冲突怎么解决”。课程设计则更看重你能不能把词法分析、语法分析、语法树构建串起来。下面按面试题、课程设计、学习路线三个角度收尾。5.1 编译原理选择题里 LR(0) 的易错点第一类易错点是“归约动作是否消耗输入符号”。答案是归约不消耗输入符号归约只弹栈、查 GOTO、压栈输入指针不动。移进才消耗输入符号。第二类易错点是 ACTION 表和 GOTO 表的列。ACTION 表的列是终结符加上$GOTO 表的列是非终结符。很多人把非终结符填进 ACTION或者把终结符填进 GOTO表立刻失效。第三类易错点是接受项目。接受动作发生在S - S .所在状态遇到$时执行不是遇到任意符号都接受。第四类易错点是增广文法。题目如果没写增广你要自己加S - S如果题目已经加了就不要重复加。还有一类选择题喜欢问“某个状态包含哪些项目”。这种题没有捷径只能老老实实求闭包。求闭包时记住只对圆点后面的非终结符展开不要对所有非终结符展开。比如项目S - C . C圆点后是C才加入C的产生式项目圆点前的C已经处理过了不需要再展开。很多错误答案就是多加了项目或者漏加了递归产生式。面试题还可能问“LR(0) 文法是否一定是无二义文法”。答案是不一定LR(0) 文法是无二义文法的子集但无二义文法不一定是 LR(0) 文法。LR(0) 对文法限制很强很多无二义文法会产生 LR(0) 冲突。5.2 把 LR(0) 放进 Java 版课程设计的最小闭环如果你正在做 Java 版编译原理课程设计LR(0) 分析可以作为一个独立模块接在词法分析后面。最小闭环是词法分析器输出 token 列表语法分析器用 LR(0) 表消费 token遇到归约时构建语法树节点最后输出语法树或中间代码。具体包结构可以这样安排lexer包负责字符流和 tokengrammar包负责产生式、项目、闭包、GOTOparser包负责分析表、状态栈、移进归约主循环ast包负责语法树节点main负责串联流程。主循环的伪代码很简单DequeInteger stateStack new ArrayDeque(); stateStack.push(0); int pos 0; while (true) { int state stateStack.peek(); String symbol tokens.get(pos).type; // 或 $ Action action actionTable.get(state).get(symbol); if (action null) { reportError(state, symbol, pos); break; } if (action.type SHIFT) { stateStack.push(action.target); pos; } else if (action.type REDUCE) { Production p grammar.get(action.prodId); for (int i 0; i p.rhs.size(); i) { stateStack.pop(); } int gotoState gotoTable.get(stateStack.peek()).get(p.lhs); stateStack.push(gotoState); // 这里可以构建 AST 节点 } else if (action.type ACCEPT) { break; } }这段代码里stateStack存状态号pos指向当前 token。移进时压入目标状态并前进归约时先弹出右部长度个状态再用暴露出的栈顶状态和产生式左部查 GOTO压入新状态。构建语法树时可以在归约动作里创建一个父节点把弹出的右部节点作为子节点。这样词法分析得到的 token 最终会变成一棵语法树。错误恢复可以先做最简单的遇到空表项就报错并停止。如果课程设计要求更健壮可以加入同步符号集跳过一些 token 继续分析。5.3 从 LR(0) 到 SLR(1)、LALR(1)、LR(1) 的学习路线LR(0) 学完之后最自然的下一步是 SLR(1)。你只需要把归约填表规则从“所有终结符”改成“FOLLOW 集”再重新检查冲突。很多在 LR(0) 里有冲突的文法到 SLR 就通过了。接着学 LALR(1)重点是理解“同心项目集”和“搜索符传播”。LALR 的状态数和 LR(0) 接近但分析能力接近 LR(1)所以实际工具用得多。最后学 LR(1)理解每个项目带搜索符的完整形式。虽然手推 LR(1) 表很累但它是理解 LALR 合并为什么可能引入归约/归约冲突的关键。练习路线可以这样安排先用S - C C推 LR(0)再用表达式文法推 LR(0) 和 SLR观察冲突变化然后用悬空 else 文法看移进/归约冲突如何靠优先级解决最后找一个 LALR 工具生成的冲突报告对照项目集看它为什么报冲突。你如果能把同一条文法在 LR(0)、SLR、LALR 下的表都推一遍编译原理语法分析这一章基本就通了。面试时再问 LR(0) 和 SLR 的区别你脑子里浮现的就不是定义而是一张张具体的表。我自己在实际手推和写代码的过程中体会最深的一点是LR(0) 分析最怕的不是算法难而是细节乱。项目编号、圆点位置、闭包顺序、GOTO 复用、归约弹栈长度任何一个小地方错了最后表都会出问题。我的习惯是先用一条极小的文法跑通全流程再换成复杂文法。还有一个小技巧每构造完一个项目集就立刻写出它的 GOTO 转移不要等所有项目集都推完再回头补。这样你随时都能发现闭包或去重的问题不会等到最后面对一堆状态号发呆。 编译原理LR(0)语法分析：项目集规范族、分析表与Java实现
1. 为什么我重新捡起 LR(0) 分析我在把编译原理学习笔记写到第七篇时终于绕不开 LR(0) 分析。前面几篇大多停留在词法分析实验用 Java 写一个 Lexer把正则表达式转成 NFA再转 DFA最后给每个单词打上 token 类型。那部分做完很多人会产生一种错觉——编译原理好像就是状态机加表格。等到语法分析这一章尤其是 LR(0) 分析才发现前面那些自动机思想只是热身真正的“栈加状态加分析表”的思考方式从这里才开始成型。LR(0) 分析是自底向上语法分析里最基础、最干净也最严格的一种模型。它从左到右扫描输入串构造最右推导的逆过程并且在做归约决策时不需要向前看任何输入符号所以叫 LR(0)。它能做的事情很具体给定一个上下文无关文法构造 LR(0) 项目集规范族生成一张 ACTION 表和一张 GOTO 表然后用一个状态栈配合输入指针完成移进、归约、接受和报错。很多编译原理课程设计、面试题、选择题都会围绕这套流程反复出题因为它足够机械也足够暴露你是否真正理解了“项目”“闭包”“GOTO”“冲突”这些概念。这篇笔记适合正在做编译原理实验的人也适合已经学过一遍但一遇到项目集规范族就发懵的人。我会尽量不用那种“先定义再证明”的教材腔而是把 LR(0) 分析拆成一条可以手推、可以写代码、可以排查错误的路线。你如果只会 Java 基础语法也能看懂后面的代码骨架你如果正准备面试也可以直接拿里面的冲突排查表和易错点去复习。1.1 词法分析实验之后语法分析这道坎词法分析实验的产出通常很直观输入一段源代码输出一串 token每个 token 有类型、值、行号。比如int a 10;会变成KEYWORD(int)、ID(a)、ASSIGN、NUMBER(10)、SEMI。这部分用 Java 写起来很舒服因为正则、状态机、字符流处理都是看得见摸得着的东西。但语法分析不一样它不再关心单个单词长什么样而是关心这些单词能不能按照文法组成一棵语法树。很多人第一次接触 LR(0) 分析时最大的障碍不是算法本身而是不知道“项目”到底在描述什么。教材上写A - α . β圆点表示分析位置。这句话单独看很抽象放到栈里就清楚了圆点左边是已经识别并压入栈的部分圆点右边是还没处理的部分。分析器每走一步要么把下一个输入符号移进栈让圆点右移一格要么发现某个产生式右部已经全部识别完就把这一串符号归约成左部非终结符。LR(0) 分析的核心就是提前把所有可能的圆点位置算出来组成项目集再根据项目集之间的跳转关系生成分析表。所以词法分析实验和 LR(0) 分析之间并不是割裂的。词法分析给出 token 流LR(0) 分析消费 token 流。你在词法阶段用 DFA 识别单词在语法阶段用项目集 DFA 识别句型。两者都依赖自动机只是一个跑在字符上一个跑在 token 上。理解这一点之后LR(0) 项目集规范族就不再是凭空冒出来的表格而是语法分析器脑子里的“状态地图”。1.2 LR(0) 的定位最严格也最干净的自底向上模型LR(0) 里的“0”不是零个状态也不是零个产生式而是零个向前看符号。它在决定归约时只看当前栈顶状态里有没有归约项目不看下一个输入符号是什么。这个设计让 LR(0) 分析表非常容易构造但也让它的适用范围很窄。只要一个状态里同时存在“可以移进”和“可以归约”的项目LR(0) 就不知道该怎么办这就是移进/归约冲突。如果同一个状态里有两个不同的归约项目还会出现归约/归约冲突。不过LR(0) 的价值并不因为它弱而降低。相反它是理解 SLR(1)、LALR(1)、LR(1) 的必经台阶。SLR(1) 只是在 LR(0) 的归约动作上加了 FOLLOW 集限制LALR(1) 进一步合并同心项目集并携带更精确的搜索符LR(1) 则给每个项目都配上搜索符分析能力最强但状态数也最多。你如果跳过 LR(0) 直接看 LALR会觉得自己在背表你如果先把 LR(0) 的项目集规范族亲手推一遍再看 SLR 和 LALR就会发现它们只是在对 LR(0) 的冲突打补丁。我在实际复习时有一个习惯每学一种 LR 分析都拿同一条小文法去推。比如S - C C、C - c C | d这条经典文法LR(0) 没有冲突SLR 也没有冲突很适合用来对照。等推到表达式文法E - E T | T、T - T * F | F、F - ( E ) | id时冲突开始出现你就能清楚看到 LR(0) 在哪里卡住SLR 又是用哪个集合把它救回来。这种对照式学习比单独背定义有效得多。1.3 这篇笔记适合谁如果你正在做编译原理课程设计已经写完词法分析下一步准备接语法分析那么这篇笔记可以直接当作 LR(0) 部分的实现路线。如果你正在准备考试或面试需要快速判断“这个文法是不是 LR(0) 文法”“项目集里为什么会有冲突”“ACTION 表和 GOTO 表怎么填”后面的速查表可以拿来就用。如果你只是对编译器感兴趣想找一个不算太大的切入点LR(0) 也是一个很好的起点因为它把“栈”“状态”“归约”这些概念压缩在几百行代码里跑通之后成就感很足。需要提前说明的是LR(0) 分析并不要求你先把所有形式语言理论都学完。你只要会集合运算知道什么是终结符、非终结符、产生式能看懂简单的栈操作就可以开始。真正难的地方在于细心项目集闭包容易漏项GOTO 容易忘了闭包归约填表容易和 SLR 搞混。后面我会把这些问题一个个拆开并给出我踩过的坑。2. LR(0) 的核心概念和设计思路拆解LR(0) 分析看起来表格很多但核心概念只有五个增广文法、LR(0) 项目、CLOSURE 闭包、GOTO 函数、项目集规范族。把这五个东西连起来就是一条完整的构造流水线。很多人学到这里会陷入“每个词都认识连起来不知道在干什么”的状态原因是教材习惯先给定义再给算法而实际思考顺序应该是反过来的先问分析器需要知道什么再问项目怎么表达这些知识最后问项目集怎么组织成表。分析器在某个时刻需要知道两件事第一栈里的符号串目前可能对应哪些产生式的哪个位置第二如果下一个输入符号是某个终结符应该移进还是归约归约又要用哪条产生式。LR(0) 项目的圆点就是用来回答第一件事的项目集就是所有可能位置的集合CLOSURE 用来把“待约项目”展开成“准备识别这个非终结符”的项目GOTO 用来描述吃掉一个符号之后项目集怎么跳转。ACTION 和 GOTO 表则是把这些跳转关系翻译成机器能查的表格。2.1 增广文法把接受动作变成唯一目标在构造 LR(0) 分析表之前第一步永远是增广文法。假设原文法的开始符号是S我们引入一个新的开始符号S并添加产生式S - S。这个动作看起来很多余但它解决了一个关键问题分析器什么时候知道整个输入串已经成功识别了如果没有增广开始符号S可能出现在其他产生式右部分析器看到S被归约出来时无法确定它是作为整个句子的开始符号还是只是某个更大结构的一部分。增广之后只有S - S .这个项目代表“整个输入已经归约到开始符号”此时遇到输入结束符$就可以执行接受动作。增广还有一个好处它让接受状态唯一。LR(0) 项目集规范族里S - S .所在的状态就是接受状态。这个状态通常只有一个项目不会和其他项目混在一起。如果原文法开始符号出现在右部比如S - A S那么S可能在多个位置被归约接受条件会变得模糊。增广之后S只出现在新产生式左部不会出现在任何右部所以S - S .是独一无二的。实际写代码时我建议把增广产生式放在产生式列表的第 0 条并用一个单独的类或结构体表示产生式编号、左部、右部列表。这样后面项目只需要记录“产生式编号 圆点位置”不用反复存左部和右部字符串。很多初学者构造项目集时直接用字符串拼接结果去重和比较都很痛苦。用编号加圆点位置项目相等判断就是两个整数比较效率高也不容易出错。2.2 LR(0) 项目圆点代表“我走到哪了”LR(0) 项目的形式是A - α . β其中A - αβ是文法产生式。圆点把右部分成两半左边α是已经识别并压栈的部分右边β是还没处理的部分。根据圆点位置项目可以分为四类。圆点后面是终结符的项目叫移进项目比如A - α . a β遇到输入符号a时应该移进。圆点后面是非终结符的项目叫待约项目比如A - α . B β它本身不直接触发动作但会通过闭包把B的产生式加进来。圆点在末尾的项目叫归约项目比如A - α .表示这个产生式右部已经全部识别完可以把α归约成A。增广开始符号对应的S - S .是接受项目。理解项目的关键是把圆点看成“进度条”。例如产生式C - c C可能的项目有三个C - . c C、C - c . C、C - c C .。第一个表示还没开始识别第二个表示已经吃掉了c正在等待C第三个表示整个右部c C已经识别完可以归约成C。分析器栈里存的不是符号串本身而是状态号但状态号背后对应的就是这些项目。你看到状态 3 里有C - c . C就知道当前栈顶刚刚处理完一个c接下来要识别一个C。有一个常见误区把圆点左边的符号理解成“已经归约完成的非终结符”。其实左边可以是终结符也可以是非终结符甚至是空串。比如C - . c C圆点在最左边左边为空C - c . C左边是终结符cC - c C .左边是c C两个符号。分析器在移进和归约过程中栈里的符号会不断变化项目集只是在抽象层面描述“当前可能处于哪些进度”。2.3 CLOSURE 与 GOTO项目集的两条腿CLOSURE 闭包解决的是“待约项目展开”的问题。假设当前项目集里有一个项目A - α . B β圆点后面是非终结符B。分析器如果想继续推进就必须先识别出一个B。那么B怎么识别当然是用B的产生式。所以闭包操作会把所有B - . γ形式的项目加入当前项目集。如果这些新加入的项目圆点后面又是非终结符还要继续展开直到项目集不再增大为止。这个过程很像“计划分解”你要完成A当前卡在B于是把B的所有子计划列出来子计划里又卡在C继续列C的子计划。GOTO 函数解决的是“吃掉一个符号之后去哪里”。给定项目集I和文法符号XGOTO(I, X)的计算分两步先从I中找出所有圆点后面正好是X的项目把圆点向右移动一格然后对移动后的项目集合求闭包。得到的新项目集就是GOTO(I, X)。如果X是终结符这个动作对应分析表中的移进如果X是非终结符对应分析表中的 GOTO 跳转。换句话说ACTION 表负责终结符GOTO 表负责非终结符两者合起来就是项目集 DFA 的转移边。我刚开始学时总是把闭包和 GOTO 的顺序搞反。记住一个口诀先移动再闭包。GOTO 不是先闭包再移动而是先筛选出能移动的项目移动圆点最后才求闭包。如果你先闭包再移动会把很多不该移动的项目也带进去项目集立刻爆炸。这个顺序在手工推项目集时尤其重要写代码时也一样gotoSet函数内部必须先遍历原项目集找到圆点后匹配X的项目生成新项目再去调用closure。2.4 项目集规范族与 DFA为什么状态能代表分析进度把所有项目集放在一起用 GOTO 关系连起来就得到项目集规范族。它本质上是一个确定有限自动机每个项目集是一个状态每个文法符号是一条转移边。初始项目集是CLOSURE({S - . S})接受项目集包含S - S .。DFA 的接受状态就是分析器可以接受输入的状态。这个 DFA 不是用来识别单词的而是用来识别“语法分析进度”的。输入串每读一个 tokenDFA 就沿着移进边跳一步归约发生时DFA 会沿着 GOTO 边跳回某个状态相当于把一串已识别的符号折叠成一个非终结符。为什么状态能代表分析进度因为栈顶状态对应的项目集包含了当前栈里符号串所有可能的产生式位置。分析器不需要记住整个栈里每个符号的具体值只需要记住状态号。状态号加上 GOTO 表就足以恢复出“如果现在归约应该跳到哪个状态”。这也是 LR 分析比递归下降更省心的原因递归下降要靠函数调用栈隐式保存进度LR 分析把进度显式地做成状态和表。表一旦构造正确分析过程就是机械查表没有回溯也没有递归深度风险。项目集规范族的规模可能很大。对于表达式文法手工推十几个状态很正常对于真实编程语言状态数可能上千。所以实际编译器很少手写 LR 表而是用工具生成。但学习阶段一定要手推至少一条小文法否则你只会用工具遇到冲突不知道怎么改文法。我的建议是先推S - C C、C - c C | d再推表达式文法最后再去看工具生成的表。这样从简单到复杂不会被状态数吓退。3. 从零构造 LR(0) 分析表一条文法走到底理论讲完必须落到一条具体文法上。我选下面这条经典 LR(0) 文法S - C C C - c C C - d终结符集合是{ c, d }非终结符集合是{ S, C }。增广之后得到0: S - S 1: S - C C 2: C - c C 3: C - d这条文法生成的句子是“两个 C 拼接”每个 C 要么是d要么是c后面再跟一个 C。比如d d、c d d、c c d d都是合法句子。它没有左递归也没有空产生式状态数少而且 LR(0) 没有冲突非常适合作为第一条手推文法。你把它推熟之后再去看更复杂的表达式文法会轻松很多。3.1 选一条小文法避免一上来被规模吓退很多人一上来就拿E - E T | T、T - T * F | F、F - ( E ) | id练手结果项目集推到十几个状态闭包展开一大片很快就乱了。表达式文法当然重要但它包含左递归、多个优先级层次、括号嵌套项目集数量多冲突也典型。初学阶段用它容易把“项目集构造”和“冲突处理”两件事混在一起。先拿S - C C这条文法可以只关注项目、闭包、GOTO、分析表不被冲突干扰。这条文法还有一个好处它能展示“同一个非终结符在不同位置被识别”的情况。C既出现在S - C C的第一个位置也出现在第二个位置还出现在C - c C的末尾。项目集里会看到S - C . C、C - c . C等不同进度。分析器需要区分这些位置而 LR(0) 项目集正好能把它们分开。你手工推一遍就能明白为什么状态 2 和状态 3 看起来很像但 GOTO 行为不同。另外这条文法的输入串短。比如c d d分析过程只有十来步栈变化可以完整写在纸上。d d更短但看不出C - c C的递归归约c c d d稍长但也在可接受范围内。我建议先用d d验证基本移进归约再用c d d验证递归归约。两个例子跑通LR(0) 分析的骨架就立起来了。3.2 手工构造项目集规范族初始项目集I0由增广产生式的项目S - . S求闭包得到。闭包过程如下先有S - . S圆点后是S所以加入S的所有产生式项目S - . C C。这个项目圆点后是C所以加入C的所有产生式项目C - . c C和C - . d。此时没有新的待约项目闭包结束。因此I0: S - . S S - . C C C - . c C C - . d从I0出发分别对S、C、c、d求 GOTO。对SI0中只有S - . S圆点后是S移动圆点得到S - S .闭包无新增。所以I1 GOTO(I0, S): S - S .对CI0中S - . C C圆点后是C移动得到S - C . C。闭包展开圆点后是C加入C - . c C、C - . d。所以I2 GOTO(I0, C): S - C . C C - . c C C - . d对cI0中C - . c C圆点后是c移动得到C - c . C。闭包展开圆点后是C加入C - . c C、C - . d。所以I3 GOTO(I0, c) GOTO(I2, c) GOTO(I3, c): C - c . C C - . c C C - . d对dI0中C - . d圆点后是d移动得到C - d .。闭包无新增。所以I4 GOTO(I0, d) GOTO(I2, d) GOTO(I3, d): C - d .继续从I2对C求 GOTOI2中S - C . C圆点后是C移动得到S - C C .闭包无新增。所以I5 GOTO(I2, C): S - C C .从I3对C求 GOTOI3中C - c . C圆点后是C移动得到C - c C .闭包无新增。所以I6 GOTO(I3, C): C - c C .最终项目集规范族包含I0到I6共七个状态。转移关系可以整理成GOTO(I0, S) I1GOTO(I0, C) I2GOTO(I0, c) I3GOTO(I0, d) I4GOTO(I2, C) I5GOTO(I2, c) I3GOTO(I2, d) I4GOTO(I3, C) I6GOTO(I3, c) I3GOTO(I3, d) I4注意I3对c的 GOTO 是它自己因为C - . c C移动后还是C - c . C闭包后又加入C - . c C和C - . d和I3完全相同。这种自循环在递归产生式中很常见。手工推的时候建议每构造一个新项目集就和已有的项目集比较一下如果项目集合相同直接复用编号不要重复创建状态。3.3 填 ACTION 与 GOTO 表有了项目集规范族和 GOTO 关系就可以填分析表了。填表规则有四条如果项目A - α . a β在状态i中且a是终结符并且GOTO(i, a) j那么ACTION[i, a] shift j。如果项目A - α .在状态i中那么对每个终结符a和输入结束符$都填ACTION[i, a] reduce A - α。如果项目S - S .在状态i中那么ACTION[i, $] accept。如果GOTO(i, A) j其中A是非终结符那么GOTO[i, A] j。这里要特别提醒严格 LR(0) 的归约动作是对所有终结符都填不看 FOLLOW 集。很多教材为了减少表项只对 FOLLOW 集填归约那其实已经带上了 SLR(1) 的味道。初学阶段一定要区分清楚否则后面学 SLR 时会不知道“多出来的 FOLLOW 限制”到底加在哪里。根据上面的项目集ACTION 表和 GOTO 表如下。r1表示按产生式 1S - C C归约r2表示按产生式 2C - c C归约r3表示按产生式 3C - d归约。状态cd$SC0s3s4121acc2s3s453s3s464r3r3r35r1r1r16r2r2r2这张表里状态 4 只有归约项目C - d .所以对所有终结符都执行r3。状态 6 只有归约项目C - c C .所以对所有终结符都执行r2。状态 5 只有归约项目S - C C .所以对所有终结符都执行r1。状态 1 有接受项目S - S .所以遇到$执行acc。状态 0、2、3 都有移进项目所以对c和d分别移进到状态 3 和 4。GOTO 部分只填非终结符状态 0 对S跳到 1对C跳到 2状态 2 对C跳到 5状态 3 对C跳到 6。你可能会问状态 5 对c和d也填r1会不会在输入还没结束时就错误归约在 LR(0) 分析里这种“多余归约”是允许的因为分析器后面迟早会遇到错误。只要归约动作和移进动作没有冲突表就是可用的。实际输入c d d在状态 5 时已经读到$所以会正常执行r1。如果输入是c d d c状态 5 遇到c也会先归约S - C C然后进入状态 1再遇到c时报错。错误发现得晚一点但不影响正确性。3.4 跑一遍输入串移进归约栈变化拿输入串c d d走一遍能最直观地看到移进和归约如何配合。输入末尾加上$所以待处理串是c d d $。分析栈初始为状态 0。下面这张表记录了每一步的状态栈、剩余输入和动作。步骤状态栈剩余输入动作10c d d $状态 0 遇 c移进到 320 c 3d d $状态 3 遇 d移进到 430 c 3 d 4d $状态 4 遇 d按 C - d 归约40 c 3 C 6d $GOTO(3, C)6状态 6 遇 d按 C - c C 归约50 C 2d $GOTO(0, C)2状态 2 遇 d移进到 460 C 2 d 4$状态 4 遇 $按 C - d 归约70 C 2 C 5$GOTO(2, C)5状态 5 遇 $按 S - C C 归约80 S 1$GOTO(0, S)1状态 1 遇 $接受第 3 步归约C - d时栈顶是d 4右部长度是 1所以弹出状态 4暴露状态 3。因为GOTO(3, C)6所以压入C 6。第 4 步归约C - c C时栈顶是c 3 C 6右部长度是 2弹出状态 6 和 3暴露状态 0。因为GOTO(0, C)2所以压入C 2。这里注意归约弹出的是右部长度对应的状态数不是符号数因为栈里存的是状态。符号本身不需要存状态号已经隐含了符号信息。第 7 步归约S - C C时栈顶是C 2 C 5右部长度是 2弹出状态 5 和 2暴露状态 0。因为GOTO(0, S)1压入S 1。最后状态 1 遇到$执行接受。整个过程没有回溯每一步都是查表决定这就是 LR 分析的魅力。你如果能在纸上完整写出这张表说明已经理解了移进、归约、GOTO 的配合方式。3.5 Java 实现 LR(0) 的关键数据结构和代码骨架用 Java 实现 LR(0) 分析器不需要一上来就写几千行。核心结构只有几个产生式、项目、项目集、闭包、GOTO、规范族、分析表。下面是一段简化骨架重点展示思路省略了完整的错误处理和界面代码。import java.util.*; class Production { int id; String lhs; ListString rhs; Production(int id, String lhs, ListString rhs) { this.id id; this.lhs lhs; this.rhs rhs; } } class Item { int prodId; int dot; Item(int prodId, int dot) { this.prodId prodId; this.dot dot; } 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 Objects.hash(prodId, dot); } } public class LR0Builder { ListProduction grammar new ArrayList(); MapString, ListInteger prodByLhs new HashMap(); SetString terminals new HashSet(); SetString nonTerminals new HashSet(); // 求闭包不断展开圆点后面的非终结符 SetItem closure(SetItem items) { SetItem result new HashSet(items); DequeItem queue new ArrayDeque(items); while (!queue.isEmpty()) { Item item queue.poll(); Production p grammar.get(item.prodId); if (item.dot p.rhs.size()) continue; String symbol p.rhs.get(item.dot); if (!nonTerminals.contains(symbol)) continue; for (int pid : prodByLhs.getOrDefault(symbol, Collections.emptyList())) { Item newItem new Item(pid, 0); if (result.add(newItem)) { queue.add(newItem); } } } return result; } // GOTO先移动圆点再求闭包 SetItem gotoSet(SetItem items, String symbol) { SetItem moved new HashSet(); for (Item item : items) { Production p grammar.get(item.prodId); if (item.dot p.rhs.size() p.rhs.get(item.dot).equals(symbol)) { moved.add(new Item(item.prodId, item.dot 1)); } } return closure(moved); } }这段代码里closure用队列避免递归过深gotoSet严格遵守“先移动再闭包”。接下来构造项目集规范族时可以用一个ListSetItem states保存所有状态再用MapString, Integer做状态去重。状态 key 可以把项目排序后拼成字符串例如prodId.dot|prodId.dot。每生成一个新项目集先查 key 是否已存在如果不存在分配新状态号并加入队列继续对每个文法符号求 GOTO。填表阶段遍历每个状态和每个项目。如果项目是移进项目查GOTO表得到目标状态填shift如果项目是归约项目对所有终结符填reduce如果是接受项目对$填accept。冲突检测也在这一步如果同一个表格单元已经被填过并且新动作和旧动作不同就记录冲突。实际写代码时我建议把 ACTION 表设计成MapInteger, MapString, ActionAction 可以是字符串也可以是枚举。调试时把表按状态号排序输出一眼就能看出哪一行有冲突。4. LR(0) 冲突排查与常见坑LR(0) 分析表构造过程中冲突几乎是必然会遇到的。没有冲突的 LR(0) 文法其实不多大多数实用文法都需要更强的分析方法。但冲突并不可怕可怕的是不知道冲突从哪里来。很多人看到“移进/归约冲突”就懵了其实只要回到项目集找到那个同时包含移进项目和归约项目的状态问题就定位了一半。剩下的一半是判断应该改文法、换分析方法还是调整优先级。我在调试 LR(0) 分析器时习惯按“项目集 - GOTO - 分析表”的顺序排查。先确认项目集闭包有没有漏项再确认 GOTO 是不是先移动再闭包最后看分析表填表规则有没有和 SLR 搞混。大部分错误都不是算法不会而是细节顺序错了。下面把典型冲突和排查方法拆开讲。4.1 移进/归约冲突为什么同一个状态里会有两个声音移进/归约冲突出现在一个状态同时包含移进项目和归约项目时。比如状态里有A - α . a β和B - γ .。遇到输入符号a时分析器有两个选择一是移进a沿着A - α . a β继续二是按B - γ .归约把栈顶的γ折叠成B。LR(0) 不看下一个输入符号之外的信息它只看当前状态所以不知道应该移进还是归约于是冲突。经典的例子是悬空 else 文法S - if E then S S - if E then S else S S - other在if E then S . else S和S - if E then S .同时存在的状态里遇到else既可以移进也可以归约。大多数语言规定else与最近的if匹配所以选择移进。这个选择不是 LR(0) 自动做出来的而是人为规定优先级。另一个例子是表达式文法E - E E | E * E | id遇到或*时既有移进又有归约需要规定*优先级高于并且和*左结合。排查移进/归约冲突时先找到冲突状态打印该状态所有项目。如果归约项目对应的产生式是A - α .看看输入符号是否可能在FOLLOW(A)中。如果是SLR(1) 可能能解决如果不在可能是文法本身有优先级问题。对于表达式通常不靠改文法而是靠优先级和结合性声明。对于课程设计如果老师要求纯 LR(0)那就必须改文法把二义性消掉或者接受这个文法不是 LR(0) 文法。4.2 归约/归约冲突文法二义性的影子归约/归约冲突出现在同一个状态里有多个归约项目时。比如状态里同时有A - α .和B - β .遇到某个输入符号时分析器不知道应该归约成A还是归约成B。这种冲突通常说明文法有二义性或者虽然文法无二义但 LR(0) 的粗粒度项目集无法区分两个归约的上下文。举一个简化例子S - A S - B A - x B - x当分析器识别完x后可能归约成A也可能归约成B而两者都能到达S。此时状态里会同时存在A - x .和B - x .产生归约/归约冲突。要解决它要么合并A和B要么改文法让x的上下文不同要么使用 LR(1) 这类携带搜索符的分析方法。SLR(1) 在这种情况下也可能帮不上忙因为FOLLOW(A)和FOLLOW(B)可能重叠。归约/归约冲突比移进/归约冲突更麻烦因为它往往意味着文法设计有问题。实际排查时我会先看两个归约项目的左部非终结符是否可以合并。如果它们语义相同只是名字不同合并最简单。如果语义不同就要检查文法是否真的需要两个不同的产生式或者是否可以通过提取公因子、分层改写来消除。实在不行就升级到 LALR(1) 或 LR(1)。4.3 SLR(1) 怎么救场以及为什么它不总是够SLR(1) 的“S”是 Simple 的意思。它在 LR(0) 的基础上只改了一件事归约动作不再对所有终结符都填而是只对归约产生式左部非终结符的 FOLLOW 集填。回到前面的状态 4项目C - d .如果按 SLR只对FOLLOW(C)里的符号填r3。在这条文法里FOLLOW(C) { c, d, $ }所以看起来和 LR(0) 全填差不多。但在有冲突的文法里FOLLOW 集限制可以排除掉一些不该归约的输入符号从而消除移进/归约冲突。SLR 的局限在于 FOLLOW 集太粗。它只知道“某个非终结符后面可能跟哪些终结符”不知道“在当前这个具体状态下它后面到底能跟哪些终结符”。如果两个不同归约项目的 FOLLOW 集有重叠SLR 仍然冲突。LALR(1) 通过给每个项目附加更精确的搜索符把同心项目集合并既减少了状态数又比 SLR 更强。LR(1) 则给每个项目单独配搜索符分析能力最强但状态数可能非常多。学习顺序上LR(0) 到 SLR 到 LALR 到 LR(1)每一步都在解决上一步的不足理解这条线索比死记表更有用。实际用工具生成分析器时像 Yacc、Bison 这类工具默认使用 LALR(1)遇到冲突会报告出来让你通过优先级或改文法解决。你在课程设计里如果手写 LR(0)可以先实现 LR(0)再把归约填表改成 FOLLOW 集就得到了 SLR(1)。代码改动很小但分析能力提升明显。这也是为什么很多教材把 LR(0) 和 SLR(1) 放在一起讲前者是骨架后者是第一次有效增强。4.4 调试速查表从项目到分析表逐层定位下面这张表是我自己排查 LR(0) 问题时总结的速查表。遇到分析器行为不对可以按现象逐层往上找。现象可能原因排查方法项目集数量异常多闭包漏了去重或 GOTO 没有复用相同项目集给每个项目集生成排序 key比较是否重复某个状态缺少待约项目闭包只展开了一层没有用队列继续展开检查闭包是否循环到项目集不再增大GOTO 目标错误先闭包再移动而不是先移动再闭包打印移动前后的项目集合确认圆点位置归约动作填得太多把 LR(0) 和 SLR(1) 搞混确认是否对所有终结符填还是只对 FOLLOW 填分析表出现冲突状态里同时有移进和归约项目或多个归约项目打印冲突状态的所有项目找左部和圆点位置输入串错误地被接受接受状态判断错或归约产生式编号错检查S - S .是否只对应$的 accept输入串合法却报错GOTO 表填错或状态栈弹出长度错单步打印状态栈、剩余输入、动作和手工表对照我踩过最多的坑是“项目集去重”。早期我用字符串直接表示项目比如S-.CC结果空格、箭头、圆点位置稍微不一致就生成重复状态。后来改成“产生式编号 圆点位置”的整数对再去重问题立刻消失。另一个坑是归约弹出长度。归约时应该弹出右部长度个状态而不是弹出整个栈。比如C - c C右部长度是 2就弹出栈顶两个状态然后暴露新栈顶查 GOTO 表压入左部非终结符对应的状态。这个细节写错表现就是分析到一半状态栈乱掉后面全是错误。5. 面试、课程设计和后续学习的高频问题LR(0) 分析不仅是课程内容也是编译原理面试和选择题的高频考点。面试官不会让你现场推十几个状态但很可能问你“LR(0) 项目有哪几类”“CLOSURE 和 GOTO 的区别”“LR(0) 和 SLR(1) 差在哪里”“移进/归约冲突怎么解决”。课程设计则更看重你能不能把词法分析、语法分析、语法树构建串起来。下面按面试题、课程设计、学习路线三个角度收尾。5.1 编译原理选择题里 LR(0) 的易错点第一类易错点是“归约动作是否消耗输入符号”。答案是归约不消耗输入符号归约只弹栈、查 GOTO、压栈输入指针不动。移进才消耗输入符号。第二类易错点是 ACTION 表和 GOTO 表的列。ACTION 表的列是终结符加上$GOTO 表的列是非终结符。很多人把非终结符填进 ACTION或者把终结符填进 GOTO表立刻失效。第三类易错点是接受项目。接受动作发生在S - S .所在状态遇到$时执行不是遇到任意符号都接受。第四类易错点是增广文法。题目如果没写增广你要自己加S - S如果题目已经加了就不要重复加。还有一类选择题喜欢问“某个状态包含哪些项目”。这种题没有捷径只能老老实实求闭包。求闭包时记住只对圆点后面的非终结符展开不要对所有非终结符展开。比如项目S - C . C圆点后是C才加入C的产生式项目圆点前的C已经处理过了不需要再展开。很多错误答案就是多加了项目或者漏加了递归产生式。面试题还可能问“LR(0) 文法是否一定是无二义文法”。答案是不一定LR(0) 文法是无二义文法的子集但无二义文法不一定是 LR(0) 文法。LR(0) 对文法限制很强很多无二义文法会产生 LR(0) 冲突。5.2 把 LR(0) 放进 Java 版课程设计的最小闭环如果你正在做 Java 版编译原理课程设计LR(0) 分析可以作为一个独立模块接在词法分析后面。最小闭环是词法分析器输出 token 列表语法分析器用 LR(0) 表消费 token遇到归约时构建语法树节点最后输出语法树或中间代码。具体包结构可以这样安排lexer包负责字符流和 tokengrammar包负责产生式、项目、闭包、GOTOparser包负责分析表、状态栈、移进归约主循环ast包负责语法树节点main负责串联流程。主循环的伪代码很简单DequeInteger stateStack new ArrayDeque(); stateStack.push(0); int pos 0; while (true) { int state stateStack.peek(); String symbol tokens.get(pos).type; // 或 $ Action action actionTable.get(state).get(symbol); if (action null) { reportError(state, symbol, pos); break; } if (action.type SHIFT) { stateStack.push(action.target); pos; } else if (action.type REDUCE) { Production p grammar.get(action.prodId); for (int i 0; i p.rhs.size(); i) { stateStack.pop(); } int gotoState gotoTable.get(stateStack.peek()).get(p.lhs); stateStack.push(gotoState); // 这里可以构建 AST 节点 } else if (action.type ACCEPT) { break; } }这段代码里stateStack存状态号pos指向当前 token。移进时压入目标状态并前进归约时先弹出右部长度个状态再用暴露出的栈顶状态和产生式左部查 GOTO压入新状态。构建语法树时可以在归约动作里创建一个父节点把弹出的右部节点作为子节点。这样词法分析得到的 token 最终会变成一棵语法树。错误恢复可以先做最简单的遇到空表项就报错并停止。如果课程设计要求更健壮可以加入同步符号集跳过一些 token 继续分析。5.3 从 LR(0) 到 SLR(1)、LALR(1)、LR(1) 的学习路线LR(0) 学完之后最自然的下一步是 SLR(1)。你只需要把归约填表规则从“所有终结符”改成“FOLLOW 集”再重新检查冲突。很多在 LR(0) 里有冲突的文法到 SLR 就通过了。接着学 LALR(1)重点是理解“同心项目集”和“搜索符传播”。LALR 的状态数和 LR(0) 接近但分析能力接近 LR(1)所以实际工具用得多。最后学 LR(1)理解每个项目带搜索符的完整形式。虽然手推 LR(1) 表很累但它是理解 LALR 合并为什么可能引入归约/归约冲突的关键。练习路线可以这样安排先用S - C C推 LR(0)再用表达式文法推 LR(0) 和 SLR观察冲突变化然后用悬空 else 文法看移进/归约冲突如何靠优先级解决最后找一个 LALR 工具生成的冲突报告对照项目集看它为什么报冲突。你如果能把同一条文法在 LR(0)、SLR、LALR 下的表都推一遍编译原理语法分析这一章基本就通了。面试时再问 LR(0) 和 SLR 的区别你脑子里浮现的就不是定义而是一张张具体的表。我自己在实际手推和写代码的过程中体会最深的一点是LR(0) 分析最怕的不是算法难而是细节乱。项目编号、圆点位置、闭包顺序、GOTO 复用、归约弹栈长度任何一个小地方错了最后表都会出问题。我的习惯是先用一条极小的文法跑通全流程再换成复杂文法。还有一个小技巧每构造完一个项目集就立刻写出它的 GOTO 转移不要等所有项目集都推完再回头补。这样你随时都能发现闭包或去重的问题不会等到最后面对一堆状态号发呆。