翻到龙书讲 LR(1) 的那几页时多数人的第一反应都是同一个疑问SLR(1) 不是已经把活干完了吗无非就是拿 FOLLOW 集来判断归约时机为什么还要再折腾出一套带“前瞻符号”的项目我当年也是这么想的直到题目里出现了一个 FOLLOW 集自带的“误伤”场景——本该移进的时候表里却填了归约编译器直接报冲突。那一刻才明白LR(1) 的价值不在于它多复杂而在于它把判断精度从“非终结符级别”下沉到了“单个项目级别”。这篇笔记就顺着这条思路走一遍先用一个 SLR(1) 处理不了的文法引出问题再把 LR(1) 项目的定义、闭包运算、GOTO 迁移讲清楚然后手工把一个 14 个状态的项目集族完整推一遍最后落到 LALR(1) 的同心集合并和那些手推时最容易翻车的细节。适合正在学编译原理、要交实验报告、或者准备考试和面试的同学零基础也能跟下来有基础的人可以重点看后面的踩坑部分。1. 为什么 SLR(1) 会在这里翻车1.1 拿一个“看起来没问题”的文法开刀要理解 LR(1) 存在的必要性最直接的办法是找一个 SLR(1) 会失败的文法然后盯着它失败的那一步看。经典教材里反复出现的这个文法就是最好的靶子(0) S → S (1) S → L R (2) S → R (3) L → * R (4) L → id (5) R → L这套文法描述的是“左值和右值”的语言L是左值可以出现在赋值号左边R是右值可以出现在赋值号右边*R表示指针解引用id就是标识符。看起来人畜无害但它在 SLR(1) 下会直接卡死。失败点在哪个状态我们来算一下。从初始状态出发读到L之后进入的状态里会同时存在两个项目一个是S → L·R意思是“我已经看到L接下来如果遇到就继续移进”另一个是R → L·意思是“我已经把L规约成了一个R的候选随时可以归约”。1.2 冲突现场FOLLOW 集把也算进了归约前瞻问题就出在R → L·这个项目上。SLR(1) 判定“什么时候可以归约”用的是 FOLLOW 集只要当前读入的符号落在FOLLOW(R)里就允许归约。那我们算一下FOLLOW(R)到底包含哪些符号。从S → L R这条产生式看R出现在末尾所以FOLLOW(R)包含FOLLOW(S)也就是$。从S → R看R在末尾同样把$加进来。关键的来了从L → * R看R后面跟着的其实是L的跟随符而L又出现在S → L R里所以也进到了FOLLOW(L)再通过R → L这条产生式FOLLOW(L)又并进了FOLLOW(R)。绕了一圈FOLLOW(R) { , $ }。于是麻烦出现了在“读到L”的那个状态里遇到输入符号时SLR(1) 会同时认为“可以移进”来自S → L·R和“可以归约”因为在FOLLOW(R)里。这就是标准的移进-归约冲突。可实际上一个真正的解析器在“左值后面跟等号”的位置是绝对不该把L归约成R的——因为接下来它要处理的是赋值语句而不是右值。1.3 LR(1) 的破局点把前瞻精确到“项目”级别冲突的根源在于 FOLLOW 集是全局信息它是所有能出现在R后面的终结符的并集太粗了。在那个特定状态里R → L·这个归约项真正的合法前瞻其实只有$也就是整个输入结束、这个语句确实是个右值表达式的场景根本不该出现在它的前瞻里。LR(1) 的做法就是把这个信息精确化不再用一个“非终结符级别的 FOLLOW 集”而是给每一个项目单独配一个前瞻符号。写法上就是把项目从[R → L·]变成[R → L·, $]中括号里逗号后面的$就是这个归约项被允许触发的时候当前必须读到的符号。这样一来在这个状态里遇到时因为[R → L·, $]的前瞻是$而不是,SLR 里那个冲突自然就消失了。用一个类比SLR 像是拿一张全城地图去判断某个路口该不该转弯LR(1) 则是给每个路口单独发了一张精确的路牌。2. LR(1) 项目到底是什么从[A→α·β]到[A→α·β, a]2.1 前瞻符号 a 的含义一个 LR(1) 项目的标准形式是[A → α·β, a]其中α和β都是文法符号串圆点·表示当前解析位置a是一个终结符或结束符$称为前瞻符号。它的准确含义是只有当这一个项目被选中做归约、并且下一个待读入的输入符号正好是a时才允许用产生式A → αβ进行归约。注意这里的a不是“项目现在看到什么”而是“项目将来归约时输入流的第一个未读符号应该是谁”。这个区分特别重要很多人一开始会把前瞻符号和当前的移进符号搞混。举个例子[L → id·, ]说的不是“现在看到了”而是“如果我已经成功识别出一个id作为左值并且下一个符号是那么我可以确定这就是L → id的归约”。而[L → id·, $]则是“识别出的这个id后面跟着输入结束符时才归约成L”也就是它被当作独立的右值表达式使用。2.2 CLOSURE 的求法与“第一分量”传播LR(1) 的闭包运算CLOSURE(I)是整套机制的发动机公式如下对I中每一个形如[A → α·Bβ, a]的项目如果后面紧跟的B是一个非终结符那么对B的每一条产生式B → γ以及FIRST(βa)中的每一个终结符b把项目[B → ·γ, b]加入闭包。对比 SLR 或者 LR(0) 的闭包这里多出来的关键就是那个FIRST(βa)。β是圆点后面B之后的部分a是当前项目自带的前瞻符号。为什么要把β和a拼起来算 FIRST因为当B → γ归约完之后紧接着要处理的要么是β里的符号要么如果β能推出空串就轮到外层项目原本的前瞻a了。于是新产生出来的项目[B → ·γ, b]的前瞻就应该是FIRST(βa)里的每一个符号。我举个具体例子帮你建立直觉。假设闭包里有项目[S → a·Ad, $]那么对产生式A → c我们要算的 FIRST 是FIRST(d$) {d}于是新项目是[A → ·c, d]。这个d的含义是在“已经看到a、接下来期待A”的语境里一旦把c归约成A后面紧跟着的一定是d所以只有前瞻为d时这个归约才合法。这个传播过程是 LR(1) 里最绕、也最容易写错的地方后面第 6 节我会专门讲踩坑。2.3 GOTO 与前瞻符号的继承链GOTO(I, X)的定义是把I里所有形如[A → α·Xβ, a]的项目的圆点向右移过X得到[A → αX·β, a]然后对这些新项目求一次闭包。这里有个非常关键、但容易被忽视的点圆点移动时前瞻符号a原封不动地带过去。为什么可以原样带因为前瞻符号描述的是“这条产生式将来归约时的上下文约束”而圆点向右移只是说明“我已经多识别了一个符号 X”并没有改变归约发生时的输入环境所以前瞻不该被改动。正因为这条“原样继承”的规则LR(1) 才能把每个归约点的前瞻信息精确地传递到最终的分析表里。如果你在 GOTO 的时候手贱把前瞻换掉或者丢掉整个表就会遭殃——这几乎是我手推 LR(1) 时犯过最多的错误。3. 手工推完一个 14 个状态的 LR(1) 项目集族3.1 增广文法与 I0 的闭包展开为了把算法走一遍我们换一个更紧凑、但同样很能说明问题的文法。这套文法有个漂亮的特性它是 LR(1) 的却不是LALR(1) 的正好留到第 5 节用来说明问题。(0) S → S (1) S → a A d (2) S → b B d (3) S → a B e (4) S → b A e (5) A → c (6) B → c先算 FIRST 集FIRST(S) {a, b}FIRST(A) {c}FIRST(B) {c}。这些后面闭包运算要用到。初始项目集I0从增广项目[S → ·S, $]出发它的前瞻是$因为整个输入读完才算接受。对它求闭包圆点后是S对S的四条产生式展开。S → aAd展开成[S → ·aAd, $]S → bBd展开成[S → ·bBd, $]依此类推。这些新项目圆点后都是终结符闭包到此为止。于是I0 { [S → ·S, $] [S → ·aAd, $] [S → ·bBd, $] [S → ·aBe, $] [S → ·bAe, $] }3.2 逐层推进从 I1 到 I13接下来沿每个可移进的符号算 GOTO。GOTO(I0, S)把[S → ·S, $]的圆点移过S得到I1 {[S → S·, $]}这是接受状态。GOTO(I0, a)处理圆点前是a的两个项目得到[S → a·Ad, $]和[S → a·Be, $]。对它们求闭包。第一个项目圆点后是A要算FIRST(d$) {d}因为A后面跟着d再后面是$所以加入[A → ·c, d]第二个项目圆点后是B要算FIRST(e$) {e}加入[B → ·c, e]。于是I2 { [S → a·Ad, $] [S → a·Be, $] [A → ·c, d] [B → ·c, e] }请注意这里A → ·c和B → ·c的前瞻分别是d和e——这两个不同的前瞻正是后面它还能当 LR(1) 用、却当不了 LALR(1) 用的伏笔。GOTO(I0, b)同理处理圆点前是b的两个项目得到I3 { [S → b·Bd, $] [S → b·Ae, $] [B → ·c, d] [A → ·c, e] }注意I3里B → ·c的前瞻是dA → ·c的前瞻是e跟I2正好是反的。这个“反”就是 LR(1) 与 LALR(1) 分道扬镳的地方。继续往下推I4 GOTO(I2, A) { [S → aA·d, $] } I5 GOTO(I2, B) { [S → aB·e, $] } I6 GOTO(I2, c) { [A → c·, d] [B → c·, e] } I7 GOTO(I3, B) { [S → bB·d, $] } I8 GOTO(I3, A) { [S → bA·e, $] } I9 GOTO(I3, c) { [B → c·, d] [A → c·, e] }再往后I10 GOTO(I4, d) { [S → aAd·, $] } I11 GOTO(I5, e) { [S → aBe·, $] } I12 GOTO(I7, d) { [S → bBd·, $] } I13 GOTO(I8, e) { [S → bAe·, $] }到这里没有新的可移进符号了项目集族封闭一共I0到I13共14 个状态。3.3 状态转移关系梳理把这 14 个状态的转移关系整理成一张表能一眼看清整个自动机的骨架填分析表的时候直接照着查就行状态移进/核心项目abcde$非终结符 GOTOI0S→·SI2I3S→I1I1S→S·accI2S→a·Ad / a·BeI6A→I4, B→I5I3S→b·Bd / b·AeI9B→I7, A→I8I4S→aA·dI10I5S→aB·eI11I6A→c·,d / B→c·,er5r6I7S→bB·dI12I8S→bA·eI13I9B→c·,d / A→c·,er6r5I10S→aAd·r1I11S→aBe·r3I12S→bBd·r2I13S→bAe·r4这张表里r1到r6分别对应第 1 到第 6 条产生式的归约acc是接受动作。你会看到 I6 和 I9 的核心项目完全一样都是{A → c·, B → c·}只是前瞻不同这就是 LR(1) 状态下能看到、但 LALR 会合并掉的“同心集”。4. 填 LR(1) 分析表ACTION 和 GOTO 到底怎么落格4.1 移进项对应 ACTION[s, a] sj分析表填起来其实比构造项目集简单得多规则就三条。第一条处理移进如果状态s里存在项目[A → α·aβ, b]其中a是终结符那么ACTION[s, a] sj这里的j就是GOTO(I_s, a)对应的状态编号。注意一个细节这里的判定条件只看圆点后面是不是终结符a跟项目自己的前瞻符号b没有任何关系。这是很多人会纠结的点——“既然每个项目都带前瞻移进是不是也要看前瞻”不用。前面讲过前瞻描述的是归约时的约束移进动作不受它影响。在I0里[S → ·aAd, $]和[S → ·aBe, $]圆点后都是a所以ACTION[I0, a] shift I2直接照做。4.2 归约项对应 ACTION[s, a] rja 为该项目的前瞻第二条规则处理归约这也是 LR(1) 区别于 SLR 的核心如果状态s里存在项目[A → α·, a]并且圆点已经到达产生式末尾那么只对前瞻符号a这一个符号填ACTION[s, a] rj其中j是产生式A → α的编号。对比一下 SLRSLR 是对FOLLOW(A)里的每一个符号都填归约。LR(1) 精确到单个前瞻符号往往只填一格。回到第 3 节的例子I6 {[A → c·, d], [B → c·, e]}。对[A → c·, d]只在ACTION[I6, d]填归约A → cr5对[B → c·, e]只在ACTION[I6, e]填归约B → cr6。I6这一行里d和e两格各归约一条不同的产生式互不干扰没有冲突。4.3 接受项与 GOTO 表第三条规则接受项目[S → S·, $]表示分析成功在ACTION[I1, $]填acc。GOTO 表则处理所有非终结符的转移对GOTO(I_s, A) I_j的情况在GOTO[s, A]填j。这部分 LR(1) 和 SLR、LALR 完全一样因为 GOTO 只跟核心项目有关不受前瞻影响。把完整的结果整理出来就是下面这张分析表s后数字是移进目标r后数字是归约产生式状态abcde$I0s2s3I1accI2s6I3s9I4s10I5s11I6r5r6I7s12I8s13I9r6r5I10r1I11r3I12r2I13r4你可以拿一个句子a c d走一遍验证I0 读a进 I2读c进 I6此时前瞻是d正好触发[A → c·, d]的归约r5把c归约成A回到 I2 并转到 I4读d进 I10遇到$触发 r1 (S → aAd)回到 I0 转到 I1遇到$接受。整个过程干干净净没有任何冲突。5. LALR(1)把同心项目集合并代价是什么5.1 同一个例子在 LALR 下暴露出的归约-归约冲突LR(1) 分析能力强但代价是状态数多。刚才那个小文法就有 14 个状态真实编程语言的文法动辄几百上千个状态分析表会膨胀得很难看。LALR(1) 出现的动机很简单把核心kernel相同、只有前瞻不同的状态合并这样状态数能砍掉一大截。定义一下“同心集”两个 LR(1) 状态如果把所有项目的前瞻符号都去掉之后得到的 LR(0) 项目集合完全相同就说它们有相同的核心same core。在我们的例子里I6 {[A → c·, d], [B → c·, e]}和I9 {[B → c·, d], [A → c·, e]}去掉前瞻后都是{A → c·, B → c·}核心一模一样于是 LALR 会把它们合并成I6 ∪ I9 { [A → c·, d] [A → c·, e] [B → c·, d] [B → c·, e] }问题就在合并后浮现了。现在这个合并状态里遇到前瞻d时[A → c·, d]说“归约成 A”[B → c·, d]说“归约成 B”两条归约项目的前瞻区间重叠了于是产生归约-归约冲突。遇到e时同理也是两条归约抢一个前瞻。这就说明这套文法在 LR(1) 下没有冲突但合并之后冲突冒了出来所以它不是 LALR(1) 文法。5.2 合并只动前瞻、不动核心这里要强调 LALR 合并的本质它只对前瞻符号求并集核心项目原封不动。I6里A → c·的前瞻是dI9里A → c·的前瞻是e合并后A → c·的前瞻就变成{d, e}B → c·同理也变成{d, e}。两边前瞻重叠冲突就来了。这也揭示了一个重要结论合并同心集是信息损失的过程。它把原本精确到每个状态的前瞻信息糊到了一起换来了更小的表和更少的状态代价是可能引入原本不存在的冲突。凡是“用空间换能力”或者“用能力换空间”的取舍本质上都是在做这种权衡。所以 LALR(1) 的表达能力严格弱于 LR(1)任何 LALR(1) 文法都是 LR(1) 文法反过来不成立我们这个例子就是反例。5.3 LR(1)、LALR(1)、SLR(1) 的能力与表规模对比把三者放一起对比逻辑会清楚很多维度SLR(1)LALR(1)LR(1)归约判定依据全局 FOLLOW 集合并后的项目前瞻每个项目自己的前瞻状态数量与 LR(0) 相同约等于 LR(0)最多可达 LALR 的数倍分析能力最弱中等最强冲突容忍度容易移进-归约、归约-归约冲突可能引入新的归约-归约冲突冲突最少实际应用教学与小型语法主流工具默认如 yacc/bison需要时手工构造我在实际写编译器前端的时候绝大多数场景用 LALR(1) 就够因为它的状态数和 LR(1) 比通常能省掉一半甚至更多而像I6/I9这种合并才崩溃的文法在真实语言里很少见。真正非用 LR(1) 不可的场景往往是文法里出现了大量需要精确前瞻才能区分归约的情况比如某些手写 DSL 或者精简过的表达式文法。6. 手推 LR(1) 时最常踩的几个坑6.1 闭包里漏掉“新产生的前瞻”这是第一号大坑。初学者算闭包时容易把新项目的瞻符号直接写成外层项目的前瞻而忘了要算FIRST(βa)。比如在[S → a·Ad, $]上有人会顺手把[A → ·c, ...]的前瞻也写成$但正确的应该是FIRST(d$) {d}。这个错误在简单例子里可能侥幸不出问题一旦β非空且能区分不同上下文表里就会冒出一堆莫名其妙的冲突。提示背下这句话——圆点后面非终结符B展开时新项目的前瞻是FIRST(βa)其中β是B在产生式里后面的那一串符号a是当前项目原本的前瞻。只有当β能推出空串时a才有机会出现在结果里。6.2 GOTO 时把前瞻抄错第二号坑是 GOTO 时前瞻处理。规则很明确圆点右移前瞻原样照抄。但我见过太多人在这一步“自作聪明”地重新算一遍 FIRST或者只保留部分前瞻导致同一个项目的不同来源被错误地混在一起。判断标准很简单GOTO(I, X)里的每个项目其前瞻必须和它在I里的来源项目一模一样。如果你在某一步发现前瞻变了那一定是算错了。6.3 用程序验证手推结果的土办法手推 14 个状态还好一旦状态上到几十个靠肉眼核对就成了灾难。我的习惯是写个小脚本跑一遍闭包运算跟手推的结果对拍。核心就是一个闭包函数大概长这样def first_of_seq(seq, first, nullable): result set() for sym in seq: result | first[sym] - {ε} if ε not in first[sym]: return result result.add($) # 序列整体可空时补上结束符 return result def closure(items, grammar, first, nullable): items set(items) changed True while changed: changed False for (lhs, rhs, la) in list(items): dot rhs.index(·) if dot 1 len(rhs): continue B rhs[dot 1] if B not in grammar: # 终结符跳过 continue beta rhs[dot 2:] las first_of_seq(beta [la], first, nullable) for prod in grammar[B]: for b in las: it (B, tuple([·] list(prod)), b) if it not in items: items.add(it) changed True return items拿这个函数对着手推的I0跑一遍如果两个集合相等基本可以放心。这招在做编译原理实验报告的时候特别省事因为报告里要求你给出项目集族用程序生成一遍再截图贴上去既准确又快。我当年就是靠这个小脚本把“手推三小时、全错一遍”的悲剧压缩成了“改几分钟、结果可信”。7. 考试和面试里 LR(1) 的几种典型问法7.1 选择题的常见陷阱编译原理考试的选择题里LR(1) 相关的干扰项翻来覆去就那么几类。一类是让你判断某个文法属于哪一级——SLR(1)、LALR(1)、LR(1) 之间的关系是逐级包含SLR ⊆ LALR ⊆ LR(1)所以“是 LALR(1) 则一定是 LR(1)”成立反过来不一定。另一类陷阱是问“LR(1) 项目的第二个分量是什么”正确答案是“归约时的前瞻符号”不是“当前读入的符号”也不是“移进时要看的符号”。还有一类喜欢拿状态数量做文章问 LR(1) 比 LALR(1) 状态多还是少——记住 LR(1) 只会更多合并同心集之后数量不增。7.2 构造大题的标准答题节奏构造 LR(1) 分析表这类大题答题节奏很重要我的固定套路是四步走。第一步先写增广文法把S → S加上并给所有产生式编号这一步千万别省编号后面填表要用。第二步从[S → ·S, $]出发逐个状态算闭包状态编号用I0、I1……标清楚每个状态的来源也在旁边注明方便检查。第三步把所有状态转移列成表把 GOTO 关系画清楚。第四步按前面讲的三条规则填 ACTION 和 GOTO。填完之后一定回头检查有没有一个格子被填了两次、有没有该填的格子空着。检查冲突是这道题拿分的关键很多人前面构造全对最后漏了冲突判断被扣分。7.3 面试最爱的对比题面试里问 LR(1) 通常不会让你手推状态而是考理解为什么需要 LR(1)LALR(1) 和 LR(1) 差在哪LALR(1) 会不会引入新的冲突这类问题的回答要点是抓住“前瞻信息的精确度”这条主线——SLR 用全局 FOLLOWLALR 用合并后的项目前瞻LR(1) 用每个项目独立的前瞻精确度依次提升能力依次增强表规模也依次变大。再补一句“LALR 合并同心集可能带来归约-归约冲突”基本就答到点子上了。我个人在实际学习和带新人做题的过程中最大的体会是LR(1) 的难点从来不在“规则多复杂”而在于“前瞻符号的传播链条一旦断了后面全错却很难一眼看出来”。手推的时候老老实实把每一个状态的前瞻写全、每一步都把FIRST(βa)算清楚比什么都强。如果时间允许把第 6 节那个闭包脚本挂着对拍基本可以做到手推零失误。这套东西啃下来之后再看 LALR(1)你会发现它根本不是什么新东西无非就是 LR(1) 做了一次“拿精确度换空间”的合并而已。