企业官网建设流程全解析

期末前一周，老师发下来一批“编译原理复习题（LR分析练习题）”，看着满屏带点的产生式和状态转移，宿舍里直接安静了几秒。背模板应付词法分析和LL(1)还行，到了LR分析这里，题目是真要你动手画自动机、填分析表、正面对抗移进-归约冲突的。我花了两天半把这类题目彻底啃了一遍，这篇文章就是完整的复盘，从为什么LR分析容易“看了答案也写不出来”，到项目集规范族怎么构造、SLR(1)分析表怎么填、LR(1)和LALR到底在什么场合登场，最后一并给出我自己的刷题顺序和自检清单。准备期末、准备考研复试、甚至打算补考重修的同学，都可以直接照着这套方法论走。

1. LR分析为什么最容易“看了答案也写不出来”

1.1 从一道练习题说起

网上流传的LR分析复习题，题干通常很短，但解题量非常大。常见的有这么几个层次：

1. 将文法转换为增广文法，并对产生式编号；
2. 写出文法的所有LR(0)项目；
3. 构造LR(0)项目集规范族；
4. 画出识别活前缀的DFA；
5. 计算FIRST集和FOLLOW集；
6. 构造SLR(1)分析表；
7. 判断该文法是否为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+，等待T；
• E → E + T ·：右部全部看到，说明句柄已经形成，可以归约。

如果圆点在最后一个符号后面，这个项目就叫归约项目；如果圆点后面是终结符，叫移进项目；如果圆点后面是非终结符，叫待约项目。还有一种是S' → S ·，叫接受项目。这样分类不是考试为了考定义，而是你后面填ACTION表时，看到什么类型就知道该写什么动作。

项目集闭包的计算方法，一句话就能说清：从一个状态的核心项目出发，不停地看圆点后面的符号，如果是非终结符B，就把B的所有产生式写成B → · γ 加进这个状态，直到没有新项目为止。可以把它理解为“分析器已经到达这个位置时，所有可能接下来要匹配的产生式都提前列出来”。用生活类比，就是你在排队时不知道队伍前面具体哪个窗口会开，于是把所有可能窗口的业务都提前准备好。

2.3 把LR(0)自动机完整画一遍：极简文法示范

概念说太多没用，用一个极小文法把DFA画一遍。文法G：

S → 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--> I1
• I0 --a--> I2
• I0 --b--> I3
• I2 --S--> I4
• I2 --a--> I2
• I2 --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 * F，F位于右部末尾，所以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 · + T

I1的状态比较特殊，E' → E · 是接受项目，E → E · + T 又允许继续移进+，这就是一个随时可能触发“接受还是继续归约”的状态节点。这里是靠输入符号来区分的：只有当前符号是$时才接受，遇到+就移进。

从I0看T，得到I2：

I2: E → T · T → T · * F

这里出现了移进-归约冲突候选：E → T · 想归约成E，T → 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) ·

状态转移表如下：

写项目集规范族时，最容易漏的是“同一个目标状态被多个来源复用”。比如I2既从I0看T得到，也从I4看T得到；I3既从I0看F得到，也从I4看F得到。做题时宁可多花时间把每个状态的来源标出来，后面检查时能省很多事。

3.3 填ACTION/GOTO表：FOLLOW集在这里派上用场

有了DFA和FOLLOW集，填表就是机械工作。ACTION表看当前状态和输入终结符，GOTO表看归约后得到非终结符时的跳转。完整的ACTION表如下：

GOTO表为：

观察状态2的动作，id和(列是空的，因为状态2下这两个符号不可能出现；遇到+、)、$时归约E → T，遇到时移进。这就是2.1里FOLLOW集发挥作用的地方。再看状态9，遇到+、)、$归约E → E + T，遇到移进；状态10则统一归约T → T * F，因为FOLLOW(T)里包含了所有可能到达这里的终结符。

这里有个易错点：归约动作的符号集合，不是“这个状态里所有可能看到的终结符”，而是“这个状态里归约项目的左部FOLLOW集”。两个集合在有些状态下确实重合，但绝不能混为一谈。

3.4 拿输入串验证：id+id*id一步步走完

填完表必须验证。我用id+id*id完整走一遍，状态栈只写编号，符号栈也不省略：

每一步的归约动作都要先弹出右部长度个状态，再查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 → L，FOLLOW(R)要放入FOLLOW(L)；由L → * R，FOLLOW(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 = R，L后面直接跟着=，所以是=；R的项目来自S → R，R后面是$，所以是$。从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 阅卷老师最喜欢扣分的六个细节

结合我做题和改卷的经验，下面这六个细节出现的频率最高，每一项都值得考前专门检查：

我自己的经验是，步骤越机械化越容易因为“手滑”丢分。每次写完闭包，先数一遍项目数，再数一遍转移边数，两个数对不上，基本就是漏闭包了。

5.3 我的考前自检清单

答题字符串写作模板化之后，我每次交卷前会按下面的清单快速过一遍：

• 产生式编号从0开始了吗，增广产生式编号是0吗？
• 每个项目集的闭包里，是否遗漏了“点后非终结符”的新增产生式？
• DFA的每条边上，转移符号是否都是项目里圆点后面的那个符号？
• GOTO表里，归约后要压入的状态是否按“弹出右部长度个状态后再查表”得到？
• SLR判断冲突时，归约条件用的是左部FOLLOW集，还是当前状态下所有符号？
• LR(1)项目的lookahead，是否逐项目计算过FIRST(βa)，而不是直接复制上一层的集合？
• 如果做了LALR合并，合并后的状态是否存在两个归约项目共用同一个lookahead？

这套清单看着简单，但真能拦住绝大多数低级错误。我刷完一份复习题后，隔一天再拿清单复盘，每次都能抓到至少一个当初没发现的笔误。这也是我把这类题目从“会做”变成“稳做”的关键一步。

最后再分享一个小技巧。做题时我会把每个项目集的“核”先圈出来，也就是最初从上一个状态转移过来的那些项目，闭包新增的项目不作特殊标记，只是排在后面对齐。这样返工检查时，只看每组的核是否对得上转移边就够，不用把整页闭包重算一遍。复习本身也是同样的道理：先把框架核对清楚，再去抠细节，LR分析的所有练习，到最后拼的就是这种有条不紊的工序感。