期末复习到语法分析这一块十个人里有八个人会被 LR 分析弄得坐立不安。LR 分析在编译原理里不是最抽象的内容但一定是最讲究“手底功夫”的内容它既考概念又考计算还要求你能独立完成“从文法到分析表再到句子分析”的完整链条。某高校这几年的编译原理复习题里LR 分析相关题型的出现频率非常高基本稳定在语法分析部分的大题位置。这篇内容就是围绕 LR 分析复习题来写的既适合考前突击也适合第一次接触 LR 分析的同学把整个思路捋顺。我把话放在前面LR 分析不需要你背表需要的是你会“造表”。考试真正拉开差距的地方永远是项目集规范族算得够不够细、两个集合FIRST/FOLLOW求没求对、分析表填得有没有漏格子。下面按复习题的常见考法把这块硬骨头从原理到题型拆开讲透。1. 读懂LR为什么复习题总爱考它1.1 用移进-归约一句话建立LR的直觉LR 分析属于自底向上分析方向恰好和递归下降相反。递归下降是从开始符号出发一路推导到输入串LR 是从输入串出发不断找到可以归约的子串把它替换成左部非终结符直到最后只剩下开始符号。整个过程里只有三个动作移进shift、归约reduce、接受accept。我给学生举过一个乐高类比把输入串看成散落的积木块LR 分析器一边从左往右读积木一边看栈顶的积木形状只要发现某一段“正好等于某块大积木的零件”就把这一小段拼成一块大积木。拼到只剩一块起始积木而且输入也刚好读完就说明这个句子符合文法。拼的过程中把零件拿进栈里叫移进把一小段零件合成大积木叫归约。其中“某一段正好等于零件集合”里的“某一段”就是句柄。LR 分析每一次归约的时机都必须落在句柄结束的位置上早一步、晚一步都算错。考试里经常考“为什么 LR 是正确的”——核心原理就是它通过分析栈中的活前缀永远能把句柄准确地找出来。1.2 LR家族图谱期末最常考LR(0)和SLR(1)LR 不是一个算法而是一个家族按“向前看”的符号数量和判断粒度分为四档LR(0)、SLR(1)、LR(1)、LALR(1)。LR(0) 最朴实它构造分析表时不看当前输入符号看着栈顶状态就决定动作SLR(1) 在 LR(0) 基础上引入了 FOLLOW 集归约前先检查“当前输入符号是否在左部非终结符的 FOLLOW 集里”LR(1) 则把向前看信息细化到每个项目上能力更强但状态数暴增LALR(1) 是对 LR(1) 的压缩常出现在考研和工程编译器里。期末复习题和大多数教材讲考重点其实是 LR(0) 和 SLR(1) 两兄弟。很多学校把两者合在一道大题里考先构造 LR(0) 项目集再尝试用 SLR(1) 填表如果遇到冲突再判断能不能被 FOLLOW 集消解。把这套流程练熟了等于抓住了出题人的常见思路。一个容易混淆的点LR 是表驱动分析器和 LL(1) 的递归下降预测分析不是一回事。LL 是自顶向下按产生式“推导”每步要选择用哪条产生式展开LR 是自底向上按句柄“归约”每步根据分析表决定动作。考题判断正误时特别喜欢在这点上设陷阱。1.3 前置技能FIRST集和FOLLOW集必须求对SLR(1) 之所以叫“Simple LR(1)”就是因为它只用 FOLLOW 集来决定归约。求 FOLLOW 集这一步错了后面填表必然错。FIRST、FOLLOW 两套规则我习惯用一句话概括FIRST 是“我能以什么开头”FOLLOW 是“谁可能合法地站在我后面”。求 FIRST(A) 时看所有 A 的产生式右部右部第一个符号是终结符就把该终结符放进去第一个符号是非终结符就把它自己的 FIRST 放进去如果它能推出 ε还要继续往后看下一个符号。求 FOLLOW(A) 时规则更细开始符号的 FOLLOW 里一定要有 $。找所有产生式右部出现的 A如果 A 后面紧跟着符号 β就把 FIRST(β) 去掉 ε 后加进来。如果 β 是空的、或者 β 能推出 ε那么产生式左部非终结符的 FOLLOW 也要传给 A。我见过太多同学在“β 能为空要继承左部 FOLLOW”这条上翻车尤其是遇到 A → αBε 这种形式。这里有个检查技巧KEEP 一个 FOLLOW 速查卡每次填归约动作之前先在草稿纸上列出所有归约项目的左部 FOLLOW 集再对着查不要凭印象写。2. LR分析表从哪儿来项目集规范族是命根子2.1 项目的本质一条产生式上的“进度条”项目item是 LR 分析最基础的单位本质就是“一条产生式的某个位置打了一个点”。比如产生式 A → αβ可以写出 A → ·αβ、A → α·β、A → αβ· 三种项目。点在哪个位置代表“这一条产生式已经识别到了哪一步”。这就像一个游戏进度的存档点点号左边是已经见过、可以放心的内容点号右边是接下来还要等待的内容。如果点号在最右端说明这条产生式的右部已经全部识别完毕可以进行归约。如果点号后面跟的是终结符下一步大概率是移进这个终结符如果点号后面跟的是非终结符这说明还要先等待这个非终结符的自己展开所以就要去做闭包运算。考试里有一个高频细节A → ε 这样的空产生式它的项目就只有一个形式 A → ·点号在位置上其实就已经是“右部空”不能再说它后面还有符号。2.2 闭包运算怎么算才不会漏项目闭包运算解决的是“当前状态里到底有哪些项目在等着”。一看到项目 A → α·Bβ就要意识到 B 马上要被读到了所以所有 B 的产生式 B → ·γ 都必须放进当前状态。闭包过程的完整规则是closure(I) J ← I repeat for 每个 形如 A → α·Bβ 的项目 in J for 每一条产生式 B → γ if B → ·γ 不在 J 中 把 B → ·γ 加入 J until J 不再增大 return J闭包运算的典型错误是“漏展開”。比如状态里已经加了 B → ·γ而 γ 右部第一个符号又是非终结符 C那 C → ·δ 也必须继续加不能中途停下。操作时我习惯用笔在“点号后的非终结符”上画个小圈每加入一个新项目就围绕它重新扫一遍直到一轮下来没有任何新增项为止。这种反复检查和 ε 闭包很像理解这一点闭包就不难了。2.3 GOTO运算其实就是看箭头往哪走GOTO(I, X) 的含义是从项目集 I 出发读入一个文法符号 X终结符或非终结符都行之后到达的下一个项目集。计算方式也很机械先把 I 中“点号后面紧跟着 X”的项目找出来让点号越过 X得到新项目然后对这批新项目做一次闭包运算。举例说明假设当前项目集里有 E → ·E 和 E → ·ET。如果读入 E那就变成 E → E·和 E → E·T再对这些项目求闭包就得到新状态。GOTO 这个操作本身就是 DFA 的转移函数项目集就是状态文法符号就是转移边。整个 LR 分析表的核心就是一张“识别活前缀的 DFA”。活前缀可以简单理解成分析过程中栈里已经累积出来的、还没有完全归约掉的前缀部分。LR 分析器的每个状态本质上都对应一个或多个活前缀的识别状态。这也是为什么项目集规范族又叫“LR(0)自动机”它是整张表的地基。2.4 把DFA变成ACTION/GOTO表的填表规则当项目集规范族全部构造出来后填表就是套流程如果项目 A → α·aβa 是终结符在状态 Ii 中并且 GOTO(Ii, a) Ij那么 ACTION[i, a] sj意思是“移进 a 并压入状态 j”。如果项目 A → α· 在状态 Ii 中且 A 不是拓广开始符号那么对 FOLLOW(A) 里的每一个终结符 aACTION[i, a] rj其中 j 是产生式 A → α 的编号。如果项目 S → S· 在状态 Ii 中ACTION[i, $] acc。剩下的空白格子全是报错说明输入串不属于该文法。GOTO 表则是对非终结符 X若 GOTO(Ii, X) Ij则 GOTO[i, X] j。这里最关键的差别就是 SLR(1) 与 LR(0) 的不同。LR(0) 分析表看到状态里有归约项目就对所有输入符号都填归约SLR(1) 只对 FOLLOW 集里的符号填归约这样能在一定程度上化解冲突。举个考研真题里常见的微缩例子文法S → a A | a A → b项目集状态之一会同时出现 S → a· 和 A → ·b。LR(0) 会把这里的 b 同时填成“归约”和“移进”直接冲突。但求 FOLLOW(S) {$}b 不在 FOLLOW(S) 里所以 SLR(1) 的做法是遇到 b 就移进遇到 $ 才归约冲突成功化解。这个小例子我每次复习都默写一遍因为它是理解 SLR 精髓最短的路径。3. 一道完整的LR(0)/SLR(1)例题演出3.1 拓广文法与FOLLOW集用一道复习题中非常经典的文法来完整推一遍E → E T | T T → id先把文法拓广加入新的开始产生式并编号编号产生式0E → E1E → E T2E → T3T → id求 FOLLOW 集这个步骤在正式构造项目集之前先做完后面填归约动作要直接查FOLLOW(E) {$}由 E → EFOLLOW(E) 加 $由 E → ETFOLLOW(E) 加 。所以 FOLLOW(E) {$, }由 E → TFOLLOW(E) 传给 FOLLOW(T)再由 E → ETFOLLOW(E) 传给 FOLLOW(T)。所以 FOLLOW(T) {$, }这个结果是后续填表最重要的依据。每次算完 FOLLOW 集我都习惯用一小行标记写在题目旁边防止填表时回头重算。3.2 手推I0到I5活前缀DFA的完整演变从初始项目集开始一步一步闭包和 GOTO。I0 closure({E → ·E})里面会有I0: E → ·E E → ·ET E → ·T T → ·id从 I0 出发分别看 GOTO(I0, E)、GOTO(I0, T)、GOTO(I0, id)。GOTO(I0, E) 得到 I1把点号越过 EI1: E → E· E → E·TGOTO(I0, T) 得到 I2I2: E → T·GOTO(I0, id) 得到 I3I3: T → id·接着看 I1 里有哪些转移。I1 里只有 是点号后的终结符所以 GOTO(I1, ) I4I4: E → E·T T → ·id注意 I4 里加入了 T → ·id因为点号后面是非终结符 T必须对它做闭包。再看 I4 的转移GOTO(I4, id) 会回到 I3GOTO(I4, T) 得到 I5I5: E → ET·到这里没有新项目集了。整个 DFA 的转移关系可以整理成一张小表状态转移I0E → I1T → I2id → I3I1 → I4I2无转移I3无转移I4T → I5id → I3I5无转移画 DFA 时要注意I3 被 I0 和 I4 两条边同时指向同一个状态只能出现一次不能复制成两个 I3。这是个特别容易让整张表连锁出错的地方。3.3 填表把DFA翻译成ACTION/GOTO表按照前面填表规则逐行处理。状态 0id 移进到状态 3即 s3GOTO 表写 E → 1、T → 2。状态 1对于 E → E·填 acc对于 E → E·T填 移进到 4即 s4。因为这两个动作不在同一个输入符号上所以没有冲突。状态 2项目是 E → T·属于编号 2 的产生式。FOLLOW(E) {$, }所以 $ 和 都填 r2。状态 3项目是 T → id·属于编号 3 的产生式。FOLLOW(T) {$, }所以 $ 和 都填 r3。状态 4id 移进到 I3即 s3GOTO 表写 T → 5。状态 5项目是 E → ET·属于编号 1 的产生式。FOLLOW(E) {$, }所以 $ 和 都填 r1。最终表如下状态ACTIONidACTIONACTION$GOTOEGOTOT0s3121s4acc2r2r23r3r34s355r1r1这张表同时也可以看作 LR(0) 分析表因为状态 1 里的 acc 和 s4 恰好分属 $ 和 没有出现同一个格子里两种动作的冲突。很多复习题会要求你说明“该文法为什么是 LR(0) 或 SLR(1)”在这个例子里两类说法都成立。3.4 模拟分析栈里到底发生了什么填完表不能扔下不管考试大题往往第二问就是“给出输入串 ididid 的分析过程”。模拟的时候状态栈、符号栈、剩余输入、动作四列要同时维护。归约动作要注意先弹出与产生式右部长度相同数量的状态和符号露出栈顶状态再查 GOTO 表压入左部非终结符对应的新状态。步骤状态栈栈顶在右符号栈栈顶在右剩余输入动作00#ididid#初始10 3# ididid#ACTION[0,id]s3移进20 2# Tidid#ACTION[3,]r3按 T→id 归约30 1# Eidid#ACTION[2,]r2按 E→T 归约40 1 4# E idid#ACTION[1,]s4移进50 1 4 3# E idid#ACTION[4,id]s3移进60 1 4 2# E Tid#ACTION[3,]r3按 T→id 归约70 1 5# E Tid#等等这里状态应该是 0 1 4 5符号栈是 # ET80 1# Eid#按 E→ET 归约稍微放慢一点看第 6 步到第 7 步。第 5 步结束后状态栈是 0 1 4 3符号栈是 # Eid。第 6 步按 T→id 归约弹出状态 3 和符号 id露出状态 4查 GOTO[4, T] 5压入状态 5。所以状态栈变成 0 1 4 5符号栈是 # ET。继续完整推完步骤状态栈符号栈剩余输入动作00#ididid#初始10 3# ididid#移进20 2# Tidid#按 T→id 归约30 1# Eidid#按 E→T 归约40 1 4# E idid#移进50 1 4 3# E idid#移进60 1 4 2# E Tid#按 T→id 归约70 1 4 5# E Tid#按 E→ET 归约80 1# Eid#按 E→ET 归约90 1 4# E id#移进100 1 4 3# E id#移进110 1 4 2# E T#按 T→id 归约120 1 4 5# E T#按 E→ET 归约130 1# E#接受这个完整的分析过程和 LL(1) 的预测分析过程完全不同。LR 的归约动作不是“推导”而是“最右推导的逆过程”所以每一步归约的顺序反着看就是在做规范归约。考试如果要求写出“最右推导”也可以从这张表逆推出来。4. 复习题里那些“故意挖的坑”4.1 判断题最喜欢藏的四个概念坑第一坑把 LR 说成自顶向下分析。这是最基础的反向设置LR 是自底向上的。第二坑混淆“归约”和“推导”方向。LR 的归约过程是规范规约是最右推导的逆过程。说“LR 是构造最左推导”一定错。第三坑把活前缀理解成普通字符串前缀。活前缀的限制在于不能越过句柄右端不是随便截一段前缀都行。第四坑认为“一个 LR(0) 文法一定是 LL(1) 文法”。两类分析能力不构成这种包含关系甚至很多 LL(1) 无法处理的左递归文法LR(0) 都能处理反过来也成立。遇到这种互推的选项直接判断为错。4.2 构造过程中的4个计算硬伤我批改复习卷时反复看到这几类错误漏闭包。状态里引入新非终结符后没有继续把该非终结符的产生式加进去。这是最常见的失分点。FOLLOW 集求错。最容易漏“β 可空时要把左部 FOLLOW 传下去”。另外开始符号的 $ 也常被忘。归约编号写错。拓广产生式编号从 0 开始1 号就是原文法的第一条产生式。归约动作写 r2代表用第 2 条产生式归约不是用第 2 个状态。弹栈数量算错。归约时弹出的符号数量等于产生式右部的长度状态栈也要弹出同样数量然后查 GOTO、压新状态。有人只改符号栈不改状态栈后面全乱。另外ACTION 表只会出现终结符和 $GOTO 表只会出现非终结符。如果看到有人往 ACTION 表里填非终结符转移那说明填表规则没吃透。4.3 冲突不可怕先看能否用FOLLOW集化解复习题里出现“判断该文法是否为 SLR(1)”时思路要固定成三步第一步把项目集规范族完整写出来找到同时存在“移进项目”和“归约项目”或者多个“归约项目”的状态。第二步对状态里的每一个归约项目查出左部非终结符的 FOLLOW 集。第三步检查有没有一个输入符号既满足某个移进项目的移进条件又落在某个归约项目的 FOLLOW 集里或者同时落在两个不同归约项目的 FOLLOW 交集里。有就是冲突没有SLR(1) 分析表就能成立。这里要特别注意LR(0) 冲突不代表文法有问题也不代表 SLR(1) 就不能用。SLR 存在的意义就是通过“只看 FOLLOW 集里的符号才归约”来缓解冲突。只有当 FOLLOW 集无法错开时才需要升级到 LR(1)。遇到这种题别一看到冲突就直接写“不是 SLR(1)”先把 FOLLOW 集算出来再下结论。4.4 做题的优先级与时间分配期末复习不建议按题目顺序从头刷到尾更高效的是按题型分配精力。我把 LR 常见题分成三类概念选择/判断类占 20%主要靠理解不花太多时间。构造类占 50%给文法求项目集、画 DFA、填 ACTION/GOTO 表。这类题最值得投入时间练的是完整流程。分析类占 30%给出现成分析表和输入串模拟移进归约过程。这类题熟练速度很快考前两三天每天练一题保持手感就够。冲刺时优先保证构造类能独立完成。因为构造题一错往往连环错项目集错一个后续 DFA 错分析表跟着错。反过来只要流程熟练分析类几乎是送分题。5. 考场外最后要记住的三件事5.1 考前把五步法默写一遍我考前习惯在草稿纸上把 LR 的完整流程默写一遍拓广文法并编号求 FIRST 和 FOLLOW求项目集规范族画 DFA 并编号按规则填 ACTION/GOTO 表。五步默写完心里就踏实了大半。这个方法帮我稳定过很多次考试比临时翻书有用得多。5.2 尽量用表格而不是文字描述项目集草稿纸上推项目集时建议用清晰的分状态表格而不是一段一段写文字。每个状态写成一个独立的集合块旁边标好转移方向。这样既方便检查也方便后续填表。考场时间紧张表格比长篇文字更不容易漏状态。5.3 用FOLLOW集提前预判冲突的小技巧最后一个实用技巧拿到拓广文法后先花一分钟把所有非终结符的 FOLLOW 集列成速查表然后每推到一个归约项目就顺手对照速查表判断它能在哪些输入符号上归约。不要等整张 DFA 画完再去查那样容易在填表时手忙脚乱。这个习惯能帮你提前发现冲突也能防止填表时把归约动作漏填到不该填的格子里。LR 分析最终考的是仔细程度不是智商。我见过太多同学明明理解了原理却在项目集编号和 FOLLOW 集上丢分。考前至少完整推演三遍类似上面的例题把每一步写得清清楚楚真正坐到考场上时LR 大题就会变成你最稳的拿分项。
