企业官网建设流程全解析

期末复习到语法分析这一块，十个人里有八个人会被 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 → ·E+T。如果读入 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) 里的每一个终结符 a，ACTION[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

先把文法拓广，加入新的开始产生式并编号：

求 FOLLOW 集，这个步骤在正式构造项目集之前先做完，后面填归约动作要直接查：

• FOLLOW(E') = {$}
• 由 E' → E，FOLLOW(E) 加 $；由 E → E+T，FOLLOW(E) 加 +。所以 FOLLOW(E) = {$, +}
• 由 E → T，FOLLOW(E) 传给 FOLLOW(T)；再由 E → E+T，FOLLOW(E) 传给 FOLLOW(T)。所以 FOLLOW(T) = {$, +}

这个结果是后续填表最重要的依据。每次算完 FOLLOW 集，我都习惯用一小行标记写在题目旁边，防止填表时回头重算。

3.2 手推I0到I5：活前缀DFA的完整演变

从初始项目集开始，一步一步闭包和 GOTO。

I0 = closure({E' → ·E})，里面会有：

I0: E' → ·E E → ·E+T E → ·T T → ·id

从 I0 出发，分别看 GOTO(I0, E)、GOTO(I0, T)、GOTO(I0, id)。

GOTO(I0, E) 得到 I1，把点号越过 E：

I1: E' → E· E → E·+T

GOTO(I0, T) 得到 I2：

I2: E → T·

GOTO(I0, id) 得到 I3：

I3: T → id·

接着看 I1 里有哪些转移。I1 里只有 + 是点号后的终结符，所以 GOTO(I1, +) = I4：

I4: E → E+·T T → ·id

注意 I4 里加入了 T → ·id，因为点号后面是非终结符 T，必须对它做闭包。

再看 I4 的转移：GOTO(I4, id) 会回到 I3；GOTO(I4, T) 得到 I5：

I5: E → E+T·

到这里没有新项目集了。整个 DFA 的转移关系可以整理成一张小表：

画 DFA 时要注意：I3 被 I0 和 I4 两条边同时指向，同一个状态只能出现一次，不能复制成两个 I3。这是个特别容易让整张表连锁出错的地方。

3.3 填表：把DFA翻译成ACTION/GOTO表

按照前面填表规则，逐行处理。

状态 0：id 移进到状态 3，即 s3；GOTO 表写 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。

状态 4：id 移进到 I3，即 s3；GOTO 表写 T → 5。

状态 5：项目是 E → E+T·，属于编号 1 的产生式。FOLLOW(E) = {$, +}，所以 $ 和 + 都填 r1。

最终表如下：

这张表同时也可以看作 LR(0) 分析表，因为状态 1 里的 acc 和 s4 恰好分属 $ 和 +，没有出现同一个格子里两种动作的冲突。很多复习题会要求你说明“该文法为什么是 LR(0) 或 SLR(1)”，在这个例子里两类说法都成立。

3.4 模拟分析：栈里到底发生了什么

填完表不能扔下不管，考试大题往往第二问就是“给出输入串 id+id+id 的分析过程”。模拟的时候，状态栈、符号栈、剩余输入、动作四列要同时维护。归约动作要注意：先弹出与产生式右部长度相同数量的状态和符号，露出栈顶状态，再查 GOTO 表压入左部非终结符对应的新状态。

稍微放慢一点看第 6 步到第 7 步。第 5 步结束后，状态栈是 0 1 4 3，符号栈是 # E+id。第 6 步按 T→id 归约，弹出状态 3 和符号 id；露出状态 4，查 GOTO[4, T] = 5，压入状态 5。所以状态栈变成 0 1 4 5，符号栈是 # E+T。

继续完整推完：

这个完整的分析过程，和 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 大题就会变成你最稳的拿分项。