期末前一周老师发下来一批“编译原理复习题LR分析练习题”看着满屏带点的产生式和状态转移宿舍里直接安静了几秒。背模板应付词法分析和LL(1)还行到了LR分析这里题目是真要你动手画自动机、填分析表、正面对抗移进-归约冲突的。我花了两天半把这类题目彻底啃了一遍这篇文章就是完整的复盘从为什么LR分析容易“看了答案也写不出来”到项目集规范族怎么构造、SLR(1)分析表怎么填、LR(1)和LALR到底在什么场合登场最后一并给出我自己的刷题顺序和自检清单。准备期末、准备考研复试、甚至打算补考重修的同学都可以直接照着这套方法论走。1. LR分析为什么最容易“看了答案也写不出来”1.1 从一道练习题说起网上流传的LR分析复习题题干通常很短但解题量非常大。常见的有这么几个层次将文法转换为增广文法并对产生式编号写出文法的所有LR(0)项目构造LR(0)项目集规范族画出识别活前缀的DFA计算FIRST集和FOLLOW集构造SLR(1)分析表判断该文法是否为SLR(1)文法如果不是分析冲突再尝试用LR(1)或LALR处理。表面看是七步实际上是一个链条前一步错一个点后面全部跟着乱。我见过不少同学拿答案对照时觉得“每一步都能看懂”但自己从头写就卡住。最常见的问题不是看不懂归约而是不知道每一步里的细节该落在哪里。举个例子项目集闭包计算时很多人会把点后面的非终结符的产生式漏掉填SLR分析表时归约动作只写了某个状态忘了归约应该在哪些终结符上执行。这些细节不是“懂不懂原理”的问题而是“有没有形成规范工序”的问题。1.2 自底向上分析到底在干什么LR分析是自底向上的分析方向是“从输入串一步步归约回开始符号”。可以把它想象成反向推导正向推导是从开始符号反复用产生式展开到句子而自底向上分析则是从句子开始不断把句柄归约成产生式左部最终回到开始符号。这里最关键的是“句柄”概念。分析器维护一个栈输入符号按顺序压进去当栈顶一段符号串匹配到某个产生式的右部同时这个右部恰好是当前最左归约的位置就执行一次归约把这段右部弹出换成左部非终结符。什么时候移进、什么时候归约就是分析表说了算。分析表分为ACTION表和GOTO表ACTION负责看当前状态和当前输入终结符决定移进、归约、接受或报错GOTO负责归约之后根据新得到的非终结符跳转状态。LR这个名字里L表示从左到右扫描输入R表示构造最右推导的逆过程也就是最左归约。记住这个方向很重要因为它决定了你每次归约的都是当前栈中最靠右的句柄而不是随便找一个能匹配的产生式右部就归约。2. 做题前的三板斧FIRST、FOLLOW和LR(0)项目集2.1 FOLLOW集SLR分析的“裁判”SLR(1)和LR(0)最大的区别就是SLR分析表在归约时多了一个限制条件只有当前输入终结符属于左部非终结符的FOLLOW集才允许执行这条归约。所以FOLLOW集算错后面的冲突判断、填表全都会跟着错。FOLLOW集的定义是在规范推导过程中可能出现在某个非终结符之后的所有终结符集合。计算规则用得最多的有四条开始符号S的FOLLOW集中一定包含$若有产生式A → αBβ则把FIRST(β)中除ε之外的所有终结符放入FOLLOW(B)若产生式是A → αB也就是B后面没有东西则FOLLOW(A)中的全部元素放入FOLLOW(B)若产生式A → αBβ且FIRST(β)包含ε则同样要把FOLLOW(A)放入FOLLOW(B)。很多同学会忽略第四条。判断“β能不能推导出空串”时不能光看β本身是不是ε还要看β里的非终结符是否都能推出ε。实际算的时候我习惯用迭代法先给每个非终结符建空集合把$放进取FOLLOW(开始符号)然后反复扫所有产生式直到所有集合都不再变化为止。因为有循环依赖比如后面要讲的某个经典文法里FOLLOW(L)和FOLLOW(R)互相包含必须迭代到收敛只扫一遍很容易漏。2.2 项目与项目集闭包不要把“项目”想复杂LR(0)项目就是在产生式右部的某个位置加一个圆点表示“已经看到了圆点前面的部分正在等待圆点后面的部分”。比如产生式E → E T可以产生四个项目E → · E T还没看到任何右部符号属于初始期待状态E → E · T已经看到E等待E → E · T已经看到E等待TE → E T ·右部全部看到说明句柄已经形成可以归约。如果圆点在最后一个符号后面这个项目就叫归约项目如果圆点后面是终结符叫移进项目如果圆点后面是非终结符叫待约项目。还有一种是S → S ·叫接受项目。这样分类不是考试为了考定义而是你后面填ACTION表时看到什么类型就知道该写什么动作。项目集闭包的计算方法一句话就能说清从一个状态的核心项目出发不停地看圆点后面的符号如果是非终结符B就把B的所有产生式写成B → · γ 加进这个状态直到没有新项目为止。可以把它理解为“分析器已经到达这个位置时所有可能接下来要匹配的产生式都提前列出来”。用生活类比就是你在排队时不知道队伍前面具体哪个窗口会开于是把所有可能窗口的业务都提前准备好。2.3 把LR(0)自动机完整画一遍极简文法示范概念说太多没用用一个极小文法把DFA画一遍。文法GS → aS | b增广文法为S → S S → aS S → b项目集I0是闭包{S → · S}展开后为I0: S → · S S → · aS S → · b从I0可以看到开始符号S说明S → S · 已经形成这就是接受状态I1。看到a移进到I2看到b移进到I3。I2: S → a · S S → · aS S → · b这里很典型点后面是S所以又把S的两个产生式作为闭包项目加进来。从I2继续分析看到S转移到I4看到a回到I2看到b进入I3。I3: S → b ·归约项目对应归约S → b。 I4: S → aS ·归约项目对应归约S → aS。完整的状态转移可以这样写出来I0 --S-- I1I0 --a-- I2I0 --b-- I3I2 --S-- I4I2 --a-- I2I2 --b-- I3画成图就是一个典型的DFA。注意点和边的含义边上的符号就是项目集中圆点后面看到的那个符号转过去之后圆点往右移一位再做闭包。这就是识别活前缀的自动机所有练习题的骨架都在这里。3. 完整推演算术表达式文法的SLR(1)分析表是怎么填出来的3.1 增广文法与编号写表的第一动作任何LR分析表练习题第一步永远是写增广文法并编号目的只有一个让接受动作有一个唯一的归约目标。原开始符号E可能出现在其他产生式右部的后面不能直接用E归约来代表“整个句子分析完了”所以引入E → E。增广文法(0) E → E (1) E → E T (2) E → T (3) T → T * F (4) T → F (5) F → (E) (6) F → id编号是为了在分析表里写归约动作时能直接写r1、r2这样的简写。如果编号乱了后面的表就没法填。接下来算FOLLOW集这个文法的依赖关系虽然不复杂但很容易在FOLLOW(F)这块翻车。先说结论FOLLOW(E) {$, , )} FOLLOW(T) {$, , ), *} FOLLOW(F) {$, , ), *}最容易被问到的点是FOLLOW(F)里的*哪来的。看产生式T → T * FF位于右部末尾所以FOLLOW(T)里的符号都要放进FOLLOW(F)。这一步是被忽略的高频错误。很多人会想当然地认为FOLLOW(T)包含FOLLOW(F)方向正好反了终结符集合是从前面传递给末尾的非终结符不是从后面的F往前传。3.2 项目集规范族构造这11个状态怎么来的全称构造会很长我把完整状态转移列出来。起点I0是闭包{E → · E}I0: E → · E E → · E T E → · T T → · T * F T → · F F → · (E) F → · id从I0看E到接受状态附近I1: E → E · E → E · TI1的状态比较特殊E → E · 是接受项目E → E · T 又允许继续移进这就是一个随时可能触发“接受还是继续归约”的状态节点。这里是靠输入符号来区分的只有当前符号是$时才接受遇到就移进。从I0看T得到I2I2: E → T · T → T · * F这里出现了移进-归约冲突候选E → T · 想归约成ET → T · * F 想移进*。SLR(1)的裁判方式是看当前符号是否在FOLLOW(E)中。FOLLOW(E) {$, , )}不在其中所以面对时不会选择归约E → T只能选择移进。这就是SLR(1)消解冲突的标准流程。继续完整列一遍所有状态I3: T → F · I4: F → ( · E) E → · E T E → · T T → · T * F T → · F F → · (E) F → · id I5: F → id · I6: E → E · T T → · T * F T → · F F → · (E) F → · id I7: T → T * · F F → · (E) F → · id I8: F → (E ·) E → E · T I9: E → E T · T → T · * F I10: T → T * F · I11: F → (E) ·状态转移表如下当前状态输入符号目标状态I0EI1I0TI2I0FI3I0(I4I0idI5I1I6I2*I7I4EI8I4TI2I4FI3I4(I4I4idI5I6TI9I6FI3I6(I4I6idI5I7FI10I7(I4I7idI5I8I6I8)I11I9*I7写项目集规范族时最容易漏的是“同一个目标状态被多个来源复用”。比如I2既从I0看T得到也从I4看T得到I3既从I0看F得到也从I4看F得到。做题时宁可多花时间把每个状态的来源标出来后面检查时能省很多事。3.3 填ACTION/GOTO表FOLLOW集在这里派上用场有了DFA和FOLLOW集填表就是机械工作。ACTION表看当前状态和输入终结符GOTO表看归约后得到非终结符时的跳转。完整的ACTION表如下状态id*()$0s5s41s6acc2r2s7r2r23r4r4r4r44s5s45r6r6r6r66s5s47s5s48s6s119r1s7r1r110r3r3r3r311r5r5r5r5GOTO表为状态ETF01234823693710观察状态2的动作id和(列是空的因为状态2下这两个符号不可能出现遇到、)、$时归约E → T遇到时移进。这就是2.1里FOLLOW集发挥作用的地方。再看状态9遇到、)、$归约E → E T遇到移进状态10则统一归约T → T * F因为FOLLOW(T)里包含了所有可能到达这里的终结符。这里有个易错点归约动作的符号集合不是“这个状态里所有可能看到的终结符”而是“这个状态里归约项目的左部FOLLOW集”。两个集合在有些状态下确实重合但绝不能混为一谈。3.4 拿输入串验证idid*id一步步走完填完表必须验证。我用idid*id完整走一遍状态栈只写编号符号栈也不省略步骤状态栈符号栈输入串动作10idid*id$s520 5idid*id$r6按GOTO(0,F)330 3Fid*id$r4按GOTO(0,T)240 2Tid*id$r2按GOTO(0,E)150 1Eid*id$s660 1 6Eid*id$s570 1 6 5Eid*id$r6按GOTO(6,F)380 1 6 3EF*id$r4按GOTO(6,T)990 1 6 9ET*id$s7100 1 6 9 7ET*id$s5110 1 6 9 7 5ET*id$r6按GOTO(7,F)10120 1 6 9 7 10ET*F$r3按GOTO(6,T)9130 1 6 9ET$r1按GOTO(0,E)1140 1E$acc每一步的归约动作都要先弹出右部长度个状态再查GOTO表。比如第12步归约T → T * F右部长度是3弹出9、7、10三个状态回到6再查GOTO(6,T)9。这一步非常容易写错因为弹出状态数量是按右部符号数算的和栈里实际压了几个状态必须严格对应。4. 冲突处理SLR(1)翻车的经典案例与LR(1)/LALR的真身4.1 一个让SLR(1)失效的文法算表达式文法虽然能用SLR(1)处理但只是“能处理”而已不能体现SLR的局限。真正让SLR(1)当场翻车的经典文法长这样S → L R | R L → * R | id R → L增广文法编号后(0) S → S (1) S → L R (2) S → R (3) L → * R (4) L → id (5) R → L算FOLLOW集时要小心循环依赖。FOLLOW(S)初始为{$}由S → L R得到FOLLOW(L)至少含由S → R得到FOLLOW(R)含$由R → LFOLLOW(R)要放入FOLLOW(L)由L → * RFOLLOW(L)要放入FOLLOW(R)。迭代收敛后FOLLOW(L) {, $} FOLLOW(R) {, $}构造LR(0)项目集只挑冲突状态看。I0闭包I0: S → · S S → · L R S → · R L → · * R L → · id R → · L从I0看L得到I2: S → L · R R → L ·问题来了这个状态里当前符号如果等于一方面S → L · R 需要移进另一方面R → L · 可以归约成R。SLR(1)判断归约R → L是否可行要看当前符号是否在FOLLOW(R)中。可FOLLOW(R) {, $}正好在里面于是SLR(1)裁定“既可以移进也可以归约R → L”冲突无法消解。注意这不是文法本身二义造成的。这个文法是明确的、无二义的它只是LR(1)文法不是SLR(1)文法。SLR用了全局的FOLLOW集来判断归约条件而这个全局信息太粗糙了。4.2 LR(1)项目里的“前瞻符号”怎么救场LR(1)项目把归约条件做得更精细形式是[A → α · β, a]其中a表示当前必须看到的前瞻终结符。用人话说SLR(1)判断“R → L · 能不能归约”时问的是“R后面可能跟着哪些符号”答案是{, $}LR(1)判断同样的归约时问的是“在当前这个状态下真正能让R后面出现的符号有哪些”答案往往比FOLLOW集更小。在I0中做LR(1)闭包前瞻会这样传播[S → · S, $] [S → · L R, $] [S → · R, $] [L → · * R, ] [L → · id, ] [R → · L, $]注意L的项目lookahead来自S → L RL后面直接跟着所以是R的项目来自S → RR后面是$所以是$。从I0看L后得到[S → L · R, $] [R → L ·, $]这时[R → L ·, $]的lookahead是$不是{, $}。于是状态里遇到时只允许移进遇到$时才允许归约R → L冲突被干净利落地消解了。这就是LR(1)比SLR(1)更强大的根本原因每个项目记住了自己真正需要的前瞻符号而不是引用全局FOLLOW集。闭包计算LR(1)前瞻时规则是如果有项目[A → α · Bβ, a]则对B的产生式B → · γ其lookahead要从FIRST(βa)取。也就是说把“β后面再跟上a”里能推出的第一个终结符作为新项目的前瞻。这个细节是LR(1)题目的重灾区容易漏掉的是β能推导出ε的情况。4.3 LALR合并什么时候能省什么时候不能省LR(1)自动机状态数可能远大于LR(0)为了控制规模考试里还有LALR。LALR的做法是把“同心项目集”合并也就是去掉lookahead之后核心相同的LR(1)项目集合并成一个。一般情况下如果LR(1)分析表没有冲突合并后的LALR不会产生移进-归约冲突但可能产生归约-归约冲突。原因是两组不同lookahead的归约项目在合并后lookahead取并集原本不重叠的归约条件可能互相重叠。做题时只需要记住合并之后一定要重新检查归约-归约冲突。有些教材习题会在合并后的状态里放两个归约项目它们的lookahead恰好重叠于是一个状态里出现“同一输入符号对应两个不同归约动作”LALR就不成立。这种题考查的正是对“同心合并取并集”的深刻理解而不只是会不会合并。5. 复习策略与刷题自检清单5.1 推荐刷题顺序同样是练习题顺序不对会浪费大量时间。我的建议是先从小文法啃起不要一上来就做综合大题。第一步挑选只含两三个产生式的极简文法反复练LR(0)项目集闭包和DFA构造目标是闭包无遗漏第二步挑一个不含冲突的小文法完整填SLR分析表并跑输入串重点感受ACTION和GOTO的协作关系第三步用算术表达式文法这类带少量冲突但能被SLR消解的文法练FOLLOW集消解冲突第四步用S → L R | R那类SLR(1)失效的文法练LR(1)项目和LALR合并。顺序的逻辑是每一层都建立在前一层的计算能力上。如果FOLLOW集一算就算错直接去做LR(1)前瞻传播就是空中楼阁。5.2 阅卷老师最喜欢扣分的六个细节结合我做题和改卷的经验下面这六个细节出现的频率最高每一项都值得考前专门检查细节错误表现正确做法增广文法忘了加S → S任何LR题先加增广产生式再编号闭包完整性漏掉点后非终结符的产生式看到点后是B必须把B的所有产生式写成B → · γFOLLOW循环依赖只扫一遍就结束迭代到集合不再变化必要时写两轮归约符号集合把所有终结符都填进归约动作只填左部FOLLOW集内的终结符LR(1)前瞻传播只复制上层产生式的全局FOLLOW用FIRST(βa)逐项计算LALR归约冲突合并后不再检查归约-归约冲突合并后逐个归约项目检查lookahead是否有重叠我自己的经验是步骤越机械化越容易因为“手滑”丢分。每次写完闭包先数一遍项目数再数一遍转移边数两个数对不上基本就是漏闭包了。5.3 我的考前自检清单答题字符串写作模板化之后我每次交卷前会按下面的清单快速过一遍产生式编号从0开始了吗增广产生式编号是0吗每个项目集的闭包里是否遗漏了“点后非终结符”的新增产生式DFA的每条边上转移符号是否都是项目里圆点后面的那个符号GOTO表里归约后要压入的状态是否按“弹出右部长度个状态后再查表”得到SLR判断冲突时归约条件用的是左部FOLLOW集还是当前状态下所有符号LR(1)项目的lookahead是否逐项目计算过FIRST(βa)而不是直接复制上一层的集合如果做了LALR合并合并后的状态是否存在两个归约项目共用同一个lookahead这套清单看着简单但真能拦住绝大多数低级错误。我刷完一份复习题后隔一天再拿清单复盘每次都能抓到至少一个当初没发现的笔误。这也是我把这类题目从“会做”变成“稳做”的关键一步。最后再分享一个小技巧。做题时我会把每个项目集的“核”先圈出来也就是最初从上一个状态转移过来的那些项目闭包新增的项目不作特殊标记只是排在后面对齐。这样返工检查时只看每组的核是否对得上转移边就够不用把整页闭包重算一遍。复习本身也是同样的道理先把框架核对清楚再去抠细节LR分析的所有练习到最后拼的就是这种有条不紊的工序感。