LR(0)分析全流程：从文法到分析表的手算与代码实现

自学编译原理到语法分析这一章很多人是这么卡住的词法分析用有限自动机啃下来了递归下降也手写过结果翻到LR分析迎面撞上项目活前缀闭包项目集规范族这一串术语书上三页纸画了七八个状态转移图看完感觉懂了合上书又不知道DFA是怎么冒出来的。我当初做课设的时候也是这样最后是逼着自己把LR(0)的分析表手推了六遍才算真正理解它在干什么。这篇笔记只讲一件事LR(0)分析到底怎么从一份文法一步一步推出一张能跑的分析表。我会用两个规模很小的文法做完整推演——一个是龙书里的经典例子用来演示标准流程另一个是刻意挑的会在LR(0)阶段翻车的文法用来告诉你这套方法的边界在哪里。中间我会把CLOSURE、GOTO、ACTION/GOTO表的构造全部拆到可以手算的程度再附一份能直接跑的Python实现和一个Java版本的落点建议。适合正在啃编译原理课本、准备课设实验或者面试前想把LR家族脉络理一遍的人。1. 为什么LR(0)值得单独拎出来啃一遍1.1 自底向上分析到底在解决什么问题先说清楚LR分析的位置。词法分析是把字符流切成token语法分析是把token流还原成一棵语法树。自顶向下的递归下降是从开始符号出发猜着往下推自底向上恰好反过来——从输入串出发不停地找当前的这一小段能不能用某个产生式的右部替换成左部一路往上归约直到归约成开始符号为止。这个找一小段往回缩的动作术语叫归约reduce而被缩掉的那一小段就叫句柄handle。直觉上很好理解给你一个算术表达式id id * id你一眼就知道先算id * id因为它优先级高。语法分析器不会看优先级它只会看当前栈顶的内容和下一个输入符号判断此刻该不该归约、该归约哪条产生式。LR分析要解决的就是把这个该不该归约的决策预先算好做成一张表运行时查表就行不用现场推理。自底向上分析最怕的是什么是归约错了顺序。比如A - a和B - a两条产生式都在当前栈顶正好是a你按哪条归约选错了后面全会崩而且没法回退LR分析器不带回溯。所以LR的核心工作就是把所有可能的栈状态 未来输入的组合提前枚举清楚保证每一步决策唯一。1.2 LR(0)在整个LR家族里的坐标LR这个名字拆开看L表示从左到右扫描输入R表示反向构造最右推导。括号里的数字指的是做决策时向前看几个输入符号。LR(0)就是向前看零个符号——也就是说它只根据当前栈里的状态决定动作完全不看下一个输入是什么。这是最朴素、最弱的一种也因此是最好理解的。往上有SLR(1)看一个符号用FOLLOW集过滤、LR(1)每个项目带一个搜索符、LALR(1)把LR(1)的项目集合并压缩工业界用得最多。为什么建议从LR(0)开始因为LR(1)、LALR(1)的构造流程是LR(0)的超集。项目、闭包、GOTO、项目集规范族、分析表填法这一整套骨架完全一样区别只是每个项目后面多带了一个搜索符集合。你把LR(0)的骨架搭稳了后面加搜索符只是多一层数据结构的事但如果你直接跳到LALR(1)会因为搞不清搜索符到底在哪个环节参与运算而彻底懵掉。1.3 动手之前必须先过一遍的四个前置概念在往下走之前有几件事得先确认自己清楚否则后面的推导会处处别扭推导与归约的方向。推导是S α β归约是反着来。分析栈里存的其实就是一条从开始符号到当前句型的推导路径的前缀。最右推导规范推导。LR分析反向构造的是最右推导也就是说每一步被归约的都是当前句型的句柄归约序列正好是最右推导的逆序。前缀与活前缀。栈里的内容不能是随便什么符号串它必须是一个规范句型的前缀而且不能越过句柄的右端。满足这个条件的前缀叫活前缀viable prefix。LR分析器的整个DFA本质就是在识别当前栈内容是不是一个合法活前缀。文法的增广。LR分析要求开始符号只出现在一条产生式的左部。如果原文法里有别的产生式也用到了开始符号就得先做增广引入S。这个细节很多人不当回事后面会专门讲它引发的坑。2. 项目、闭包与GOTOLR(0)自动机的三块地基2.1 增广文法与结束符的约定先说增广。给定文法G我们构造G新增一个非终结符S不在原文法里出现过并加入产生式S - S。同时约定S是G的开始符号。这一步看起来是多余的实际上它解决了一个致命问题分析什么时候结束需要一个唯一可识别的信号。如果没有增广当栈里归约出开始符号S时分析器不知道是该接受还是继续归约万一还有别的产生式右部能匹配呢。有了S - S当且仅当我们在点已经移到S产生式最右端的状态读到结束符时才执行接受动作。结束符我习惯用$或#表示它是输入串末尾的一个虚拟符号不属于文法符号集。有些教材用#有些用$本质一样看实验要求统一就行——别一份代码里混用两种这是新手常见的手滑。2.2 四种项目类型怎么一眼区分**项目item**这个概念是LR分析的灵魂。一条产生式A - XYZ加上一个点表示我们已经分析到哪了就构成一个项目。这条产生式最多能派生出四个项目A - ·XYZ点在最左还没识别任何东西A - X·YZ识别了XA - XY·Z识别了XYA - XYZ·整条右部都识别完了可以归约按点的位置项目分成四类这个分类直接决定了它在分析表里对应什么动作项目形态名称点后面是什么含义A - α·aβ移进项目终结符 a期待读入终结符 aA - α·Bβ待约项目非终结符 B期待先归约出非终结符 BA - α·归约项目无整条右部识别完毕可归约S - S·接受项目无特例归约成增广开始符号这四类的判定我建议直接写成代码里的分支先看点是否越界没越界再看点后面符号是终结符还是非终结符越界了再判断左部是不是增广符号。逻辑清楚不容易错。2.3 CLOSURE把期待展开成具体项目项目集不是随便凑的它必须是**闭包closure**的结果。闭包的作用是把我现在期待一个非终结符B这种模糊状态展开成B的所有产生式都还没开始这样一批具体项目。规则很直白如果项目集里有一个待约项目A - α·Bβ那么对B的每一条产生式B - γ都应该把B - ·γ加进这个项目集。而且这个规则要反复应用——新加进来的项目如果又是待约项目还得继续展开直到集合不再增长为止。举个手算的例子。设有文法(0) S - S (1) S - C C (2) C - c C (3) C - d初始项目集只有S - ·S。因为它点后面是S非终结符所以把S的产生式加进来I0 { S - ·S, S - ·C C, C - ·c C, C - ·d }再检查新加的三个项目S - ·CC点后面是C要把C的产生式加进来——C - ·cC和C - ·d已经在集合里了不用重复加。C - ·cC和C - ·d点后面都是终结符停。于是I0就是这四个项目。这里有个细节同一个项目只能出现一次。所以实现CLOSURE的时候必须用一个能去重的容器集合否则展开会无限循环下去。这是后面坑那一节要重点讲的。2.4 GOTO状态之间怎么跳有了项目集接下来要算状态转移。这是最容易和CLOSURE搞混的地方一定要把职责分清CLOSURE解决的是同一个状态内部项目集该包含哪些项目GOTO解决的是从一个状态读到某个符号后跳到哪个新状态GOTO的定义给定项目集I和文法符号XGOTO(I, X)是先把I里所有形如A - α·Xβ的项目的点右移一位变成A - αX·β得到一个新集合然后对这个新集合求闭包。注意最后那一步求闭包是必须的。很多人第一次写代码漏了这一步结果状态数少得离谱分析表里全是空动作。记住一句话GOTO的结果一定是一个闭包不是一个裸的点移位集合。对I0而言GOTO(I0, S)把S - ·S移点得到S - S·闭包还是它自己GOTO(I0, C)把S - ·CC移点得到S - C·C再求闭包把C的产生式加回来GOTO(I0, c)把C - ·cC移点得到C - c·C再求闭包GOTO(I0, d)把C - ·d移点得到C - d·闭包就是它自己项目集规范族也叫LR(0)项目集规范族就是把这套操作一直迭代下去直到不再产生新项目集为止最终得到的状态集合加上转移关系就构成了一台识别活前缀的DFA。3. 用 S-CC / C-cC|d 完整走一遍状态机与分析表3.1 从I0到I6的状态构造接着上面的文法我把所有状态完整推一遍。这份推导建议你在纸上跟着画一遍比看十遍书管用。I0 { S-·S, S-·CC, C-·cC, C-·d } GOTO(I0, S) { S-S· } I1 GOTO(I0, C) { S-C·C, C-·cC, C-·d } I2 GOTO(I0, c) { C-c·C, C-·cC, C-·d } I3 GOTO(I0, d) { C-d· } I4 GOTO(I2, C) { S-CC· } I5 GOTO(I2, c) I3 GOTO(I2, d) I4 GOTO(I3, C) { C-cC· } I6 GOTO(I3, c) I3 GOTO(I3, d) I4一共七个状态转移关系一目了然。这里有几个点值得停下来看一眼第一I3自己转移到自己GOTO(I3,c)I3。这不是笔误。C - cC这种递归产生式天生会形成自环含义是可以连续读入任意多个c。这个自环是DFA能处理不定长输入的关键没有它c^100 d这种串就识别不了。第二I4、I5、I6都是归约状态点的位置都在最右端三个项目分别是C-d·、S-CC·、C-cC·对应文法里的第3、1、2条产生式。记住这个对应关系填表时要用。第三I1是接受状态唯一项目是S-S·。它是整个DFA的出口。3.2 ACTION表移进、归约、接受、报错四选一构造完DFA就可以填分析表了。LR分析器有主控程序两张表一张叫ACTION表处理终结符一张叫GOTO表处理非终结符。分析栈里同时压入状态和文法符号实际实现时通常只压状态符号靠产生式长度反推。ACTION表的填写规则逐项对应项目类型若状态i里有移进项目A - α·aβ且GOTO(i, a) j则ACTION[i][a] sj移进j状态若状态i里有归约项目A - α·A不是增广开始符号则对所有终结符和结束符ACTION[i][a] rk按第k条产生式归约若状态i里有接受项目S - S·则ACTION[i][$] acc其余格子全部填报错error请注意第二条里对所有终结符这个措辞——这就是LR(0)最鲜明的特征也是它致命的弱点。归约动作不看下一个输入是什么一言不合就归约。后面第4节会专门讲它带来的麻烦。对上例填出来的ACTION表是这样状态cd$0s3s41acc2s3s43s3s44r3r3r35r16r2r2r2状态4对应产生式C - d第3条所以在c、d、$上全部归约状态5是S - CC第1条只在$上归约——等等这里为什么不是所有终结符这是个必须澄清的点。严格按LR(0)的定义状态5也应该在c和d上归约。但S - CC归约完之后栈顶会变成S而S后面不可能再接c或d看文法S只出现在S - S里所以那些动作永远不会被触发。手算的时候把它们省略掉不影响正确性但写代码时为了和教材一致建议老老实实全部填上别自作聪明做剪枝否则实验对拍的时候会因为表格diff对不上而浪费时间。3.3 GOTO表与状态转移GOTO表只在识别出非终结符时使用填写规则是若GOTO(i, A) jA是非终结符则GOTO[i][A] j其余格子填空上例的GOTO表状态SC0122536其他状态没有非终结符转移。这张表很小但它是归约之后该往哪跳的唯一依据一旦某个格子填错分析器就会在归约后跳到错误的状态然后在下一次查表时报错——而且报错位置会离真正的错误点很远非常难查。3.4 用输入串 cdd 验证一遍手工推一遍分析过程能验证表是不是填对了。输入串cdd$分析栈初始是[0]。步骤栈剩余输入动作10c d d $状态0读c查表得s3压入320 3d d $状态3读d得s4压入430 3 4d $状态4读d得r3C-d弹1个状态40 3d $归约后栈顶3查GOTO(3,C)6压入650 3 6d $状态6读d得r2C-cC弹2个状态60d $归约后栈顶0查GOTO(0,C)2压入270 2d $状态2读d得s4压入480 2 4$状态4读$得r3C-d弹1个90 2$查GOTO(2,C)5压入5100 2 5$状态5读$得r1S-CC弹2个110$查GOTO(0,S)1压入1120 1$状态1读$得acc接受整个过程没有任何一步需要回头看输入全靠查表。这就是LR分析器的运行方式写出来其实就是个几十行的while循环。4. 冲突判定LR(0)什么时候会撑不住4.1 移进-归约冲突是怎么产生的前面反复强调LR(0)归约时不看输入符号这个特性会直接导致一种尴尬局面某个状态里既有移进项目又有归约项目。这时分析器就懵了——当前栈顶既可以说该读下一个符号了又可以说该归约了两条路都说得通。用这个文法演示(0) S - S (1) S - a S (2) S - a它的项目集是这样的I0 { S-·S, S-·aS, S-·a } I1 GOTO(I0, S) { S-S· } (接受) I2 GOTO(I0, a) { S-a·S, S-a·, S-·aS, S-·a } (冲突!) I3 GOTO(I2, S) { S-aS· } GOTO(I2, a) I2看I2。它里面有两个项目值得注意S-a·S要求读入一个S而S得从终结符a开始所以实际是期待读入aS-a·表示已经识别完一个a可以归约了。于是在I2上读到a时到底该移进还是该归约LR(0)没法决定这就是移进-归约冲突。4.2 归约-归约冲突与它的典型场景另一类冲突更棘手同一个状态里有两个不同的归约项目也就是栈顶的这一段内容可以按两条不同的产生式归约。用这个文法演示(0) S - S (1) S - A a (2) S - b (3) A - b构造出来的I0和关键状态是I0 { S-·S, S-·Aa, S-·b, A-·b } I1 GOTO(I0, A) { S-A·a } I2 GOTO(I0, b) { S-b·, A-b· } (冲突!)I2里两个项目都归约完了一个要归约成S一个要归约成A。LR(0)在这里依然只能掷骰子。这两类冲突合起来就是课本上说的一个文法是LR(0)文法当且仅当它的项目集规范族里不存在冲突。判定逻辑其实很好写对每个项目集统计移进项目的终结符集合、归约项目集合如果归约项目数 ≥ 2归约-归约冲突如果归约项目数 1 且移进终结符集合非空移进-归约冲突。4.3 看零个符号到底错在哪把两类冲突放到一起看根因是同一个LR(0)在决定归约时假装任何输入符号都可能跟在后面。以S - aS | a为例。当栈里是a时如果后面跟的是$输入是aaa...a的最后一个a那当然应该归约如果后面跟的还是a那就得继续移进。LR(0)因为不看下一个符号只能把这两种情况当成一种于是冲突。换个角度理解LR(0)把归约的适用场景定义得太宽了。它把所有终结符都算作合法的后继实际上远没那么多。这个观察直接引出了下一节的修补方案。5. SLR(1)给LR(0)打的补丁与它的剩余缺口5.1 用FOLLOW集把归约动作筛一遍SLR(1)的思路特别朴素归约成非终结符A那么A之后本来就应该跟FOLLOW(A)里的符号如果当前输入符号不在FOLLOW(A)里这次归约根本不可能成立干脆不填这个动作。还是拿S - aS | a举例。算一下FOLLOW(S)S出现在S - S的末尾所以$属于FOLLOW(S)S也出现在S - aS的末尾这条产生式不引入新符号。所以FOLLOW(S) {$}。于是在I2里归约项目S - a·就只在$上填归约动作a 上不填。这样一来I2在读到a时只有移进这一个选择冲突消失了。这个文法在LR(0)阶段失败但在SLR(1)阶段通过。再看归约-归约那个例子。FOLLOW(S) {$}FOLLOW(A) {a}。于是在I2里S - b·只在$上归约A - b·只在 a 上归约两者的作用域完全不重叠冲突同样解决。5.2 补丁失效的经典案例悬空else但SLR(1)不是万能的。经典的悬空else问题就是它搞不定的一个状态里同时出现移进else和归约if-else两个动作且else恰好也在FOLLOW集里SLR(1)的筛选起不到作用。根本原因在于SLR(1)用的FOLLOW集是整个文法全局算出来的粒度太粗。它没有区分在这个具体位置A后面到底能跟什么。LR(1)的做法是给每个项目单独带一个搜索符只在特定上下文中生效粒度细得多LALR(1)则把LR(1)中核心项目相同、只有搜索符不同的状态合并起来既保留了大部分分析能力又把状态数压回可接受范围。这四者的关系可以这样理解方法向前看符号数冲突解决能力状态数规模LR(0)0最弱实际文法基本都要冲突最少SLR(1)1用全局FOLLOW集过滤同LR(0)LR(1)1每个项目独立搜索符最多可能爆炸LALR(1)1合并同心项目集能力接近LR(1)与LR(0)同量级面试里爱问为什么工业界用LALR(1)而不是LR(1)答案就在状态数这一列——LR(1)的状态数在真实语言文法上可能比LALR(1)多出一个数量级内存和构造时间的代价不划算。6. 手写一个LR(0)分析器从数据结构到跑通6.1 文法与项目的内部表示理论讲完该动手了。LR(0)分析器的结构其实非常清晰一共四块项目表示、CLOSURE、GOTO、主控程序。先说项目怎么存。项目必须可哈希因为要放进集合里去重。我用一个三元组(左部, 右部元组, 点的位置)表示__hash__和__eq__都基于这三个字段。右部用tuple而不是list因为list不可哈希——这个细节不注意代码会直接抛异常。class Item: __slots__ (lhs, rhs, dot) def __init__(self, lhs, rhs, dot): self.lhs lhs self.rhs tuple(rhs) self.dot dot def __eq__(self, other): return (self.lhs, self.rhs, self.dot) (other.lhs, other.rhs, other.dot) def __hash__(self): return hash((self.lhs, self.rhs, self.dot)) def __repr__(self): r list(self.rhs) r.insert(self.dot, ·) return f{self.lhs} - { .join(r)}文法对象需要维护三样东西产生式列表带编号便于填归约动作、左部到右部列表的映射闭包展开要用、终结符与非终结符集合。class Grammar: def __init__(self, text, start): self.prods [] # [(lhs, rhs_tuple), ...] 带编号 self.prod_of {} # lhs - [rhs_tuple, ...] self.start start for line in text.strip().splitlines(): lhs, rhs line.split(-) lhs lhs.strip() rhs tuple(rhs.split()) if rhs.strip() else (ε,) self.prods.append((lhs, rhs)) self.prod_of.setdefault(lhs, []).append(rhs) self.lhs_set set(self.prod_of) self.terminals set() for lhs, rhs in self.prods: for s in rhs: if s not in self.lhs_set and s ! ε: self.terminals.add(s) self.terminals.add($)注意空产生式的处理A - ε的右部是空串我用一个占位符ε表示长度算作0。后面归约时的弹栈数量要用真实长度不能把ε当成一个符号弹掉。6.2 CLOSURE与GOTO的实现细节CLOSURE我用工作队列实现比反复全量扫描高效逻辑也更清楚def closure(self, items): result set(items) work list(items) while work: it work.pop() if it.dot len(it.rhs): sym it.rhs[it.dot] if sym in self.lhs_set and sym ! ε: for rhs in self.prod_of[sym]: new Item(sym, rhs, 0) if new not in result: result.add(new) work.append(new) return frozenset(result)这里有两个坑要注意。第一sym in self.lhs_set的判断必须在it.dot len(it.rhs)之后否则数组越界第二返回frozenset而不是普通set因为项目集要作为字典的键来查状态编号可变对象不能当键。GOTO就三行def goto(self, items, sym): moved {Item(it.lhs, it.rhs, it.dot 1) for it in items if it.dot len(it.rhs) and it.rhs[it.dot] sym} return self.closure(moved) if moved else frozenset()千万别忘了末尾那个self.closure。我见过太多实现只做了点移位就返回结果状态数少一半分析表全是空的。6.3 构造项目集规范族与两张表状态机的构建就是个广度优先搜索用一个字典记录项目集 → 状态编号天然去重def build_states(self): start_item Item(self.start , (self.start,), 0) I0 self.closure({start_item}) states [I0] index {I0: 0} trans {} queue deque([I0]) while queue: cur queue.popleft() i index[cur] syms {it.rhs[it.dot] for it in cur if it.dot len(it.rhs)} for sym in syms: nxt self.goto(cur, sym) if nxt not in index: index[nxt] len(states) states.append(nxt) queue.append(nxt) trans[(i, sym)] index[nxt] return states, trans填表逻辑直接照搬第3节的规则另外加一个冲突收集方便判断文法的能力边界def build_table(self, states, trans): action, goto, conflicts {}, {}, [] for i, I in enumerate(states): action[i] {} for it in I: if it.dot len(it.rhs): a it.rhs[it.dot] if a in self.terminals: act (s, trans[(i, a)]) if a in action[i] and action[i][a] ! act: conflicts.append((i, shift-reduce, a)) action[i][a] act else: if it.lhs self.start : action[i][$] (acc,) else: prod (it.lhs, it.rhs) k self.prods.index(prod) for a in self.terminals: act (r, k) if a in action[i] and action[i][a] ! act: conflicts.append((i, conflict, a)) action[i][a] act for (i, sym), j in trans.items(): if sym in self.lhs_set: goto[(i, sym)] j return action, goto, conflicts6.4 主控程序二十行跑完一次分析主控程序是所有LR分析器共用的写一次能一直用def parse(self, tokens, action, goto): stack, pos [0], 0 tokens list(tokens) [$] trace [] while True: s, a stack[-1], tokens[pos] act action[s].get(a) if act is None: trace.append(f状态{s}遇{a}报错) return False, trace if act[0] s: trace.append(f移进 {a}) stack.append(act[1]); pos 1 elif act[0] r: lhs, rhs self.prods[act[1]] trace.append(f归约 {lhs} - { .join(rhs)}) for _ in range(len(rhs)): stack.pop() stack.append(goto[(stack[-1], lhs)]) else: trace.append(接受) return True, trace归约那一步的len(rhs)要特别注意空产生式的情况。如果rhs是(ε,)长度是1会多弹一个状态。正确做法是在读入文法时就把空产生式的右部存成空元组()用ε只作为显示用的标记。这是我踩过的一个真实坑症状是分析if语句这种带空分支的结构时莫名报错。6.5 如果实验要求用Java写课设里用Java的不少说几个数据结构上的对应关系。项目类实现equals和hashCodeIDE自动生成即可字段是左部、右部List、点位置项目集用SetItem再包一层不可变对象当HashMap的键。右部建议在文法解析阶段就转换成ListString之后只读不改避免迭代过程中的并发修改问题。状态编号的映射可以用MapSetItem, Integer但要注意HashSet的hashCode是基于元素计算的只要项目类的hashCode写对这个映射就是可靠的。转移关系用MapInteger, MapString, Integer存比一维数组加偏移量好懂得多。7. 实验里最容易翻车的六个坑7.1 项目集不去重导致无穷递归这是出现频率最高的一个。CLOSURE如果用list存项目、用indexOf判断存在性或者干脆不做判重程序会在C - ·cC这样的递归产生式上无限展开——因为展开出来的新项目看起来和之前的不一样其实是同一个对象的不同副本。判断项目相等必须基于内容不能基于引用。用Set 正确的hash/equals是唯一稳妥的解法。7.2 增广文法忘了加或者加错了漏掉增广这一步最典型的症状是分析到最后一步不知道该怎么办或者干脆没有接受状态。另一种错误是增广符号和原文法里的符号重名——比如原文法里已经有个非终结符叫S那必须换一个没出现过的符号。写代码时最好在构造文法阶段就检查一遍S是不是真的不在原文法符号集里。7.3 空产生式引发的连锁问题A - ε这种产生式会同时影响三个地方闭包展开时右部长度算0、归约时弹栈数量算0、FOLLOW集计算时要按ε在最后一个位置还得考虑A - ε导致FOLLOW(A)并到前面符号的FOLLOW里。任何一处漏掉分析结果都会错而且错得很隐蔽——通常是某些特定输入串才失败。7.4 冲突检测写反了有人把移进项目和归约项目的判断条件写反导致能分析的文法报冲突有冲突的文法反而通过。我的建议是拿两个已知的测试文法验证S-CC, C-cC|d应该无冲突S-aS|a应该报移进-归约冲突。两个都对上了检测逻辑就基本可靠。7.5 分析表的行列索引对不上ACTION表和GOTO表经常被合并成一个二维数组终结符在前、非终结符在后。这种写法性能好但列映射一旦算错症状是分析器能跑但结果乱跳。调试时我习惯先把状态打印出来再单独打印每一行和手算的结果逐格比对——手算虽然慢但它是唯一可靠的基准。7.6 面试里会被追问的几个点最后整理几个和LR(0)相关的常见问题顺便当复习清单LR(0)和SLR(1)的区别是什么归约动作的填表范围。LR(0)对所有终结符都填归约SLR(1)只用FOLLOW集里的符号填。活前缀和句柄是什么关系活前缀是不越过句柄右端的规范句型前缀句柄本身也是一个活前缀而且它的右端恰好是某个规范句型的句柄边界。为什么说文法不是LR(0)文法不等于语言不能LR(0)分析因为文法可以改写。同一个语言可能存在等价的LR(0)文法也可能不存在——这是文法层面的性质不是语言层面的。LALR(1)会不会引入新的冲突会。合并同心项目集时可能把两个原本不冲突的状态并成一个冲突状态这叫归约-归约冲突的新增虽然概率不高但理论上确实存在。这也是为什么有些工具允许你在LALR和LR之间切换。我自己做完这套推演之后最大的体会是LR分析的难点不在算法本身而在把状态里有哪些项目和这个状态该做什么动作这两件事的因果关系看透。项目是可能性分析表是决策中间的桥就是归约时向前看的符号数量。把LR(0)这一步彻底弄清楚再往上加搜索符真的就只是在数据结构上多挂一个集合而已。