1. 从SLR(1)到LR(1)为什么需要向前看符号1.1 SLR(1)的局限性那些年我们误报的冲突编译原理学到语法分析这一层很多人第一次真正卡住的地方不是LR(0)而是SLR(1)的冲突问题。我自己当年做词法分析实验、接着啃语法分析的时候也在这里来回撞墙。回顾一下SLR(1)的核心思路是在LR(0)项目集规范族的基础上遇到归约动作时用非终结符的FOLLOW集来判断是否应该归约。这个方案在大多数场景下都能用但它的“软肋”非常明显——FOLLOW集是全局的它把这个非终结符在所有可能上下文中的后继终结符都塞进了一个集合里抹掉了具体的上下文信息。这种全局化的处理会带来两个直接后果。第一本来在某个特定状态下不可能出现的终结符因为它在别的上下文里会出现于是也被放进了归约判断中导致“假冲突”。第二真正的冲突判断不够精确本该能分清的移进/归约选择被错误地标记为冲突。典型例子就是经典的赋值语句文法S - L R | R L - * R | id R - L在LR(0)项目集规范族中会有一个状态同时包含S - L . R和R - L .这两个项目。SLR(1)在判断R - L .是否归约时查的是FOLLOW(R)而FOLLOW(R)里既包含也包含$和*等符号。结果就是当输入符号是时既可以选择按照S - L . R移进也可以按照R - L .归约产生移进-归约冲突。可实际上如果状态里明确知道当前期待的是那就不该用R - L归约。SLR(1)判断不出来是因为它不知道“这个L是在什么上下文里被推导出来的”。注意FOLLOW集冲突不是文法本身的错而是分析方法精度不够的体现。理解这一点对后面理解LR(1)和LALR(1)的定位非常关键。1.2 LR(1)的核心创新给每个项目配上精确的展望符LR(1)的突破点很朴素但很有效既然全局FOLLOW集不够精确那就为每个项目单独维护一个“向前看符号”集合也就是这一章反复出现的“搜索符”或“展望符”。LR(1)项目的一般形式写作[A - α . β, a]其中a是一个终结符甚至可以是$输入结束符。它的语义非常直接在当前的语法分析上下文里当我们已经识别出α部分的句型之后如果接下来输入的符号是a那么使用产生式A - αβ进行归约是合法的。这个“向前看符号”不再是全局的而是跟随项目一起在项目集规范族中流动的。共享同一个核心即LR(0)项目部分相同但向前看符号不同的项目被视为不同项目。这就使得分析精度大幅度提高大量在SLR(1)中出现的冲突自然消失了。用一个不太严谨但很直观的类比SLR(1)像是问“这个非终结符后面可能跟哪些符号”而LR(1)是问“在这个具体的语法位置这个非终结符后面实际能跟哪些符号”。后者的信息量更小、更精准因此决策更准确。1.3 SLR(1)、LR(1)、LALR(1)的对比定位为了在脑子里建立清晰的地图我习惯把这三个东西放在一起看分析方法向前看信息状态数量能力实战使用情况SLR(1)非终结符的FOLLOW集与LR(0)相同较少最弱教学为主LR(1)每个项目独立的搜索符最多可能爆炸最强规范LR手写分析器、教学LALR(1)合并同心项目集后的搜索符与LR(0)相同介于两者之间工具生成主流这个表不是拿来背的而是在选择实现方案时用来自查的。如果你在写一个手工分析器、文法规模不大、追求最强的分析能力那么LR(1)值得投入。如果你要用工具链比如yacc/bison这类生成分析表背后多数用的是LALR(1)因为它在状态数量和能力之间取得了很好的平衡。我在学这一章的时候最大的误区就是把LR(1)当成“比SLR(1)更高级的东西”然后机械地背算法。后来做实验才明白LR(1)的真正价值是“用精确的上下文信息替代了模糊的全局信息”它的算法复杂不是因为概念难而是因为搜索符需要在项目集传播的过程中准确传递。理解了这一点闭包和GOTO函数的写法就顺理成章了。2. LR(1)项目集规范族的构造算法拆解与手工推演2.1 闭包(Closure)函数向前看符号是怎么传递的LR(1)的闭包运算和LR(0)的闭包运算长得很像但多了向前看符号的传播逻辑这是整个算法最容易写错的地方。先给出严谨的算法描述再解释为什么这么写。对于一个LR(1)项目[A - α . B β, a]闭包运算要把它“展开”成B的所有产生式对应的项目。对于每个形如B - γ的产生式加入新项目[B - . γ, b]其中b属于FIRST(βa)。如果β可以推导出空串那么b就应该包括a本身。这里的关键点是新项目里的向前看符号b不是随便取的它是通过“β后面跟着什么、a本身又是什么”推出来的。也就是说向前看符号沿着推导链传播了下去。我把它总结为一句话闭包展开时新项目的搜索符 FIRST(β)如果β不能推空则不包含原搜索符如果β能推空则还要并入原项目的搜索符a。为什么这么设计因为在A - αBβ这个上下文里B后面跟着β。当我们识别完B之后真正决定能否归约的是β能推导出的第一个终结符。如果β能推出空串那么B后面的东西退化成a所以a也要考虑进来。举个例子文法片段S - B b B - a对于项目[S - . B b, $]β bFIRST(b) {b}所以加入[B - . a, b]。你看搜索符是b而不是$因为B后面紧跟的是b。这就是LR(1)比SLR(1)精确的地方SLR(1)会查FOLLOW(B)而FOLLOW(B)恰好也包含b但LR(1)是通过局部推导精确计算出来的不会混入其他上下文的符号。提示写闭包函数的时候最稳妥的方法是双层循环遍历项目集合和产生式并注意当β能推导出ε时要把原搜索符一起并入。我实验时就是因为漏了这个ε分支导致在含空产生式的文法上报了诡异的冲突。2.2 GOTO函数状态之间的转移逻辑GOTO函数的定义看起来很简单GOTO(I, X) 就是项目集I中所有形如[A - α . X β, a]的项目把点右移一位得到[A - α X . β, a]然后求闭包。搜索符在这个过程中原封不动地带过去。这里有一个很容易被忽略的细节点右移之后向前看符号不变。为什么因为点右移只是表示我们“又识别了一个符号X”但识别完整个产生式后要归约时用到的向后看符号取决于这个项目诞生时的上下文而不是当前已经识别的部分。换句话说搜索符是刻在这个项目“基因”里的不会因为点移动而改变。我在手工推演时习惯把所有项目集画成DFA的节点每条边标上转移符号。这个过程虽然繁琐但是非常值得手动做一两遍。原因很简单你只有亲手处理过一次“同一个核心项目、不同搜索符分别出现在不同状态里”的情况才能真切理解LR(1)的状态为什么会膨胀。2.3 手工推演一个完整的LR(1)项目集规范族我们拿一个能体现LR(1)威力的经典文法来推。继续用上面那个需要消解SLR(1)冲突的文法S - S S - L R | R L - * R | id R - L先做增广文法加入S - S。初始项目集 I0 是[S - . S, $]的闭包。第一步展开闭包S - . S 后面没有β只有原来的搜索符$。S的产生式有两个S - L R和S - R都加入搜索符$[S - . S, $] [S - . L R, $] [S - . R, $]继续展开 L 和 R。对于[S - . L R, $]β 是 RFIRST( R) {}所以加入[L - . * R, ]、[L - . id, ]。对于[S - . R, $]β为空搜索符保持$加入[R - . L, $]。R的产生式只有R - L继续展开L时β为空搜索符保持$加入[L - . * R, $]、[L - . id, $]。整理一下 I0[S - . S, $] [S - . L R, $] [S - . R, $] [R - . L, $] [L - . * R, ] [L - . * R, $] [L - . id, ] [L - . id, $]关键点来了L - . * R出现了两次一个搜索符是来自S-LR上下文一个是$来自R-L上下文。在LR(0)里它们本来是同一个项目在LR(1)里被拆成了两个。这就是精度的来源也是状态膨胀的根源。继续算GOTO(I0, S)得到S - S .搜索符$GOTO(I0, L) 得到S - L . R和R - L .前者搜索符$后者搜索符$。注意这个状态中S - L . R期待而R - L .的搜索符是$。因此当输入是时只移进当输入是$时只归约冲突自然消失了。这就是LR(1)相对SLR(1)的核心优势所在。而如果用SLR(1)R - L .的归约判断用FOLLOW(R){ , $, * }遇到时就会和移进产生冲突。同样的文法LR(1)状态下就干净了。2.4 构造过程中的两个典型陷阱第一个陷阱是忘记“点后是终结符时不再求闭包”。闭包只展开点后面的非终结符如果点是终结符或者点在末尾就不再展开。我见过不少人写代码时顺手把求闭包写在了无条件分支上导致状态数量异常增多。第二个陷阱是搜索符集合的更新时机。在GOTO运算里搜索符是直接继承的在闭包里新搜索符是通过FIRST计算得到的。这两个地方混淆的话会导致分析表要么多出冲突要么对该归约的地方不归约。实操心得手工推演项目集的时候我强烈建议用一个表格记录“核心项目 - 搜索符集合”并且每加入一个新项目就对照一下已有项目是不是核心相同、搜索符可以合并。不合并会把项目集写得太散合并错了又会丢掉精度。这个度需要在做题中反复找。3. LR(1)分析表构造从项目集到可执行表格3.1 ACTION表和GOTO表的填充规则有了项目集规范族构造分析表就是机械动作了。规则如下若项目[A - α . a β, b]且 GOTO(I, a) J则在 ACTION[I, a] 填入sj移进到状态J。若项目[A - α ., a]且 A 不是 S则在 ACTION[I, a] 填入rj按产生式 j 归约。若项目[S - S ., $]则在 ACTION[I, $] 填入acc接受。对非终结符A若 GOTO(I, A) J则在 GOTO 表里填入 J。这套规则看着简单但真正填表的时候有一处必须留意同一个格子不能同时填入两个不同的动作。如果出现就是冲突。LR(1)文法保证不会出现移进-归约冲突和归约-归约冲突如果你在推演中真的遇到了说明文法不是LR(1)的或者是哪一步算错了。3.2 完整案例给赋值语句文法造一张分析表延续上一节的状态编号。我给它按推演顺序编号I0初始状态I1 GOTO(I0, S)I2 GOTO(I0, L)I3 GOTO(I0, R)其他状态继续展开……为了不把篇幅全耗在状态展开上这里给出关键状态的填表结果帮助你对照检查自己的推演状态项目核心部分输入符号动作I0S-.S, S-.LR, ...id / *移进到对应状态I1S-S.$accI2S-L.R / R-L.移进I2同上$按 R-L 归约I7L-id. / $按 L-id 归约看 I2 这个状态就是LR(1)精度的集中体现。同一个核心项目S-L.R和R-L.因为搜索符不同遇到移进、遇到$归约。如果换成SLR(1)这个状态就会因为FOLLOW集冲突而无法决策。注意填表时如果ACTION的某一行出现了多个动作先别急着认定文法有错。要仔细回查项目集构造过程中的搜索符计算尤其是FIRST集合是否算漏了ε。我遇到过的假冲突八成是搜索符传递错误导致的。3.3 状态数量爆炸LR(1)的现实代价LR(1)的分析能力最强但代价也很明显状态数量可能比LR(0)膨胀数倍甚至十几倍。原因在2.3节已经看到了同一个LR(0)核心因为搜索符不同会被拆成多个状态。这个代价在教科书级的小文法上无所谓但放到真实编程语言的文法上状态数量可能会从几百飙到几千分析表内存占用和生成时间都变得不可接受。这就是为什么工程上很少直接用规范的LR(1)而是退一步用LALR(1)。我个人的经验是理解LR(1)的时候不要纠结状态数量那是工程权衡问题先把算法吃透尤其是搜索符的传递逻辑因为LALR(1)的合并逻辑正是建立在LR(1)的项目集之上的。LR(1)是理解LALR(1)的必经之路跳过它直接看LALR(1)的合并算法很容易只记住“合并同心项目集”这个结论却不知道为什么有些文法在LALR(1)下会出现新的归约-归约冲突。4. LALR(1)教科书之外的工程折中4.1 同心项目集的合并原理LALR(1)的核心动作是把“同心”的LR(1)项目集合并。所谓同心就是两个项目集去掉向前看符号之后核心的LR(0)项目完全相同。合并的方式很朴素把这些同心项目集的搜索符并起来。用生活化的说法LR(1)把每个项目集“身份证”上的搜索符记得清清楚楚导致出现很多只差一个搜索符的“双胞胎状态”LALR(1)觉得没必要分那么细就把这些双胞胎强行合并成一个人搜索符取并集。这么一来状态数量和LR(0)、SLR(1)一样少但分析能力比SLR(1)强得多因为它用的是项目级别的搜索符而不是全局FOLLOW集。合并过程本身不难难的是合并后可能出现归约-归约冲突。原因在于两个原本分得很开的同心状态各自负责不同的上下文合并之后它们的搜索符混在了一起可能导致某个输入符号同时触发两条不同产生式的归约。4.2 LALR(1)与LR(1)的行为差异这两者的差异用一个对照表说清楚对比维度LR(1)LALR(1)状态数量多与LR(0)相同分析能力最强略低于LR(1)合并对象不合并合并同心项目集可能的新冲突无本身无冲突时可能出现归约-归约冲突工具使用较少主流生成器默认关键结论是任何LALR(1)能处理的文法LR(1)都能处理反过来不成立。也就是说LR(1)的适用范围严格大于LALR(1)。但工程上愿意用LALR(1)是因为状态数量的差距带来的内存和效率优势远大于那一点点能力损失。这里有一个经典结论值得记住LALR(1)合并同心项目集不会引入新的移进-归约冲突只会引入归约-归约冲突。原因也不难理解移进动作取决于当前输入符号合并前每个状态各自的移进决策是一致且确定的合并后不会改变移进分支但两个状态各自的归约可能在不同输入符号下触发合并后搜索符一取并集某些输入符就可能同时满足两个归约条件。4.3 工具链中LALR(1)的实际应用在真实的编译器或解析器开发中如果你用现成的分析器生成工具你想自己实现一个LR(1)解析器的话需要自己写项目集构造、状态管理和分析表生成。步骤并不复杂但要留意状态编号的稳定性和重复状态检测。我个人的做法是给每个状态算一个哈希值把核心项目和搜索符排好序后拼成字符串做键这样能快速判断状态是否已经存在避免重复构造。而如果使用现成的表格驱动解析器通常需要先准备一张ACTION/GOTO表然后写一个通用的驱动器用一个状态栈和符号栈循环读取输入根据栈顶状态和当前输入符号查表执行移进、归约或接受。驱动器本身与文法无关替换表格就能换文法。这也是LR类分析器的魅力所在。5. 常见问题排查与学习路径建议5.1 高频错误速查表我在学习和做题过程中踩过的坑整理成一张速查表供你对照现象可能原因排查方法闭包展开后项目集异常大对终结符也求了闭包检查是否只对点后非终结符求闭包搜索符总是为空FIRST计算漏了ε分支重新计算FIRST集确认能推空的非终结符分析表出现假冲突搜索符传递错误逐个项目回溯搜索符来源LALR(1)合并后出现归约-归约冲突文法本身不是LALR(1)检查同心项目集合并后的搜索符并集归约动作该做却没做ACTION表填充时漏了搜索符检查[A-α., a]中的每个a是否都填了5.2 从LR(0)到LR(1)的递进学习建议我建议的学习顺序不是从LR(0)一路冲到LR(1)而是先搞明白每一个阶段“为什么不够用”。LR(0)不够是因为它完全不看输入符号就决策冲突太多SLR(1)不够是因为它的FOLLOW集太粗LR(1)够精确但状态太多LALR(1)是在状态数量和分析能力之间找平衡。每一步的演进动机都对应着一个具体的失败案例把这些案例亲手推演一遍比死记算法有效得多。另外LR(1)部分一定要动手做题至少完整手工推演两个文法。一个含空产生式的一个含移进-归约冲突的。推演的时候用纸笔把每一步的搜索符来源都标出来。这个过程大概会花你一两个小时但对后续理解分析表构造、理解LALR(1)的合并都有直接帮助。提示做实验或刷选择题时先判断题目考的是哪一层是闭包搜索符计算、GOTO转移、还是分析表填充。不同层次的题检查点不一样别混着查。5.3 面试与实验中容易问到的点编译原理相关的面试或实验答辩里LR(1)部分最常被追问的无非几个方向。一是“为什么要用向前看符号SLR(1)为什么不行”这需要一个具体的冲突案例来回答光背定义是说不清的。二是“LR(1)和LALR(1)的区别”要能说清状态数量和分析能力的取舍。三是“归约-归约冲突和移进-归约冲突分别在什么情况下出现”这个需要结合项目集的形态来说明。我个人在回答这类问题时习惯先讲一个最小的失败案例再引出对应的解决方案。比如先讲赋值语句文法在SLR(1)下的冲突再说明LR(1)如何通过为项目单独维护搜索符来解决。这种“问题驱动”的讲法比直接罗列算法步骤更有说服力也更能体现你真的动手推演过。学到这里语法分析这条线基本从LR(0)到LALR(1)就走通了。回头再看词法分析里那些有限自动机会发现底层的状态机思想是一脉相承的词法分析用有限状态自动机识别单词语法分析用带栈的自动机识别句型。理解了状态和转移也就理解了编译器前端最核心的一块。后续如果继续往下学语法制导翻译和中间代码生成这些分析表里的移进、归约动作正好就是挂载语义动作的入口。