假设你经营一家米其林后厨，自动传送带上源源不断送来食材——西红柿、鸡蛋、盐、糖。三位新厨师要在备菜台上，按同一本菜谱把这些食材拼成一道道半成品菜。他们需要回答的问题是：传送带上的这串食材，按菜谱能不能做出东西来？如果能，先拼哪一步、再拼哪一步？ 这其实就是编译器里语法分析器（Parser）每天做的事。源代码字符流就像传送带上的食材，文法（Grammar）就是菜谱，而三位厨师分别叫 SLR、LALR、LR(1)。他们基本功几乎一样，唯一的差别藏在“向前看”这三个字里——处理到备菜台中间某一步时，要不要提前瞥一眼传送带上的下一件食材？看多少？看多细？正是这个微小的差别，决定了三位厨师谁更容易做错菜、谁更费神、谁又快又稳。本文就带你走进这间厨房，从备菜台的每一张进度便签讲起，看清三位厨师的分工与高下。

岗位关联

对 AI 从业者而言，理解 SLR / LALR / LR(1) 的差异，是吃透编译原理语法分析的关键一环，能帮你从容调试 Yacc/Bison 中的文法冲突，也能为设计编程语言、编写解析器选型提供坚实底气。

目录
  1. 可视化演示
  2. 谱系总览：三位厨师的厨房
  3. 共同地基：LR(0) 项目集
  4. SLR 前瞻：只看食材大类的粗心厨师
  5. LR(1) 精确制导：看得见盘中餐的厨师
  6. LALR 高明合并：会做笔记的聪明厨师
  7. 冲突对比：谁家的菜谱更广
  8. 实战选型：Yacc 的厨房为何选 LALR
  9. AI 应用场景
  10. Python 演示
  11. 常见误区
  12. 面试题

可视化演示

SLR、LALR与LR(1)是LR分析家族的三种代表，状态数与表达能力依次递增。本文对比三者的LR(0)项目集... 切换模式查看不同维度。

本节配有交互动效（进入视口后自动加载，约 3KB）。

LR分析器家：核心原理 动态展示关键流程与数据流动 交互控件调节参数实时渲染 f(x) = transform(x) 核心概念的可视化呈现

谱系总览：三位厨师的厨房

后厨里有三位厨师，名字分别叫 SLR、LALR 和 LR(1)。他们都毕业于同一所厨师学校，抄着同一本菜谱（文法），操作着同一张备菜台（分析栈）。唯一不同的是他们“向前看”的习惯：SLR 厨师习惯只看传送带上食材的“大类”——比如“这是蔬菜类”，不管具体是西红柿还是青椒；LR(1) 厨师则会眯起眼睛看清具体是哪一颗西红柿；而 LALR 厨师最精明，他既想看得精确，又不想因此多准备几百张便签。

这个“向前看”的习惯差异，最终体现为两个指标：状态数（厨师要准备多少张进度便签）和表达能力（能驾驭多复杂的菜谱）。三者共用同一个 LR(0) 自动机作为地基，却因为前瞻策略不同，走上了三条路。LALR 的状态数与 SLR 一样多，但能力直逼 LR(1)——这正是它日后成为 Yacc 默认人选的伏笔。

打个比方，SLR 和 LALR 厨师都只需要一本 100 页的菜谱手账，而 LR(1) 厨师为了把每种食材语境都记清楚，手账可能膨胀到 300 页。后厨空间有限，手账越厚，翻起来越慢，这就是 LR(1) 的代价。但话又说回来，手账厚也有厚的好处——某些 SLR 会做错的菜，只有 LR(1) 看得穿，LALR 则恰好站在两者中间。

∣QSLR∣=∣QLALR∣≤∣QLR(1)∣\displaystyle |Q_{\text{SLR}}| = |Q_{\text{LALR}}| \le |Q_{\text{LR(1)}}|
这条公式是说：SLR 和 LALR 准备的“进度便签”张数一样多，而 LR(1) 因为便签上多写了一行“前瞻符号”，通常需要更多张便签。
  1. 状态集符号 QQ 代表解析器的状态集合，也就是厨师脑中“备菜进度”的所有快照。
    Q={state0,state1,…}Q = \{ \text{state}_0, \text{state}_1, \ldots \}
  2. 竖线表示取个数|Q| 表示状态总数，即厨师为处理所有可能进度而备好的便签张数。
    ∣Q∣=状态的数目|Q| = \text{状态的数目}
  3. 等号的含义SLR 与 LALR 都建立在同一个 LR(0) 状态机之上，所以两者的状态数完全一致。
    ∣QSLR∣=∣QLALR∣|Q_{\text{SLR}}| = |Q_{\text{LALR}}|
  4. 不等号的含义LR(1) 的状态里额外携带前瞻符号，一个状态被拆成多个，所以总状态数往往更多。
    ∣QLR(1)∣≥∣QSLR∣|Q_{\text{LR(1)}}| \ge |Q_{\text{SLR}}|

共同地基：LR(0) 项目集

三位厨师虽然风格不同，但都从同一堂课毕业——先学会在菜谱上贴“进度便签”。菜谱上每一行规则，比如 拼盘 → 肉类 + 蔬菜，厨师会在某个食材后面点一个点，写成 拼盘 → 肉类 · 蔬菜，意思是“肉类已经备好，正在等蔬菜”。这张带点的便签，在编译原理里就叫 LR(0) 项目。

单张便签只能描述一种可能，但传送带还没走完，厨师并不知道最终会走哪条分支，于是他把所有眼下可能成立的便签全部贴在墙上，形成一张“可能进度集合”。关键在于：如果某张便签点号后面是一个半成品（非终结符），比如 拼盘 → 肉类 · 半成品B，那么半成品 B 的所有做法便签也必须补进墙里。这个不断补全的过程叫做项目集闭包。把墙上所有可能状态连起来，就得到一台状态机——确定性有限状态自动机（DFA），它正是三位厨师共用的“行动地图”。

闭包运算看似不起眼，却是所有解析器共同的“地基工程”。SLR、LALR、LR(1) 在项目集构造这一步动作完全一致，谁也不会偷懒。真正分道扬镳的地方，是下一步——当墙上某张便签提示“可以归约了”，三位厨师各凭本事决定：眼前这个局势，到底该不该动手？

CLOSURE(I)=I∪{[A→α⋅Bβ] | [B→⋅γ] 是产生式}\displaystyle \text{CLOSURE}(I) = I \cup \left\{ [A \to \alpha \cdot B \beta] \ \middle|\ [B \to \cdot \gamma] \text{ 是产生式} \right\}
闭包运算就像整理冰箱：先把已有的便签留下，再看每张便签上“还没做的半成品”有哪些做法，把所有相关做法便签一并贴到墙上。
  1. 左边 CLOSURE(I)闭包运算，从一份便签集合出发，把相关的便签全部补全。
    CLOSURE(I)\text{CLOSURE}(I)
  2. 右边的 I先把已有的全部便签原样保留，这是闭包的起点。
    II
  3. 点号后是非终结符 B某张便签上点号后面站着半成品 B，说明下一步可能要做 B。
    [A→α⋅Bβ][A \to \alpha \cdot B \beta]
  4. B 的全部做法入列把 B 的每一条产生式 B → γ 都写成新便签，加入集合。
    [B→⋅γ][B \to \cdot \gamma]

SLR 前瞻：只看食材大类的粗心厨师

现在到了 SLR 厨师的主场。他的习惯是：每当便签提示可以归约，他并不仔细看传送带上那件具体食材，而是先在心里翻一本“食材大类手册”。这本手册对于每个半成品，记录着“凡是可能出现在它后面的食材大类”，这个大类集合在编译原理里叫 FOLLOW 集。SLR 的规则只有一条：只要下一件食材属于这个半成品的大类集合，就毫不犹豫地归约。

听起来很省事，问题恰恰出在“大类”上。FOLLOW 集合的构造方式是全局收集：只要在文法的任何地方、任何语境里，半成品 R 后面出现过符号 a，a 就会被记进 FOLLOW(R)。它完全不关心当下这个状态里 R 到底处在哪条菜谱的哪个位置。于是 FOLLOW 集合往往偏大——它把“别处可能出现的食材”也算进了“此处可能出现的食材”。

龙书里有个经典例子：文法 S → L = R | R，L → * R | id，R → L。SLR 构造到某个状态时，便签同时提示“可以移进 = ”和“可以按 R → L 归约”。SLR 厨师一翻大类手册，发现 FOLLOW(R) 里居然包含 =（因为在别的语境中 R 后面确实跟过 =），于是判定两者冲突，当场懵住。而实际上，在当下这个具体状态里，= 根本不可能合法地跟在归约后的 R 后面——是“大类”骗了他。这就是 SLR 看得太粗的代价。

FOLLOW(A)={a | S⇒∗αAaβ}\displaystyle \text{FOLLOW}(A) = \left\{ a \ \middle|\ S \Rightarrow^* \alpha A a \beta \right\}
通俗说，FOLLOW(A) 是“半成品 A 完成后，全局所有语境下可能跟在后面的终结符的并集”。它宽而不精，正是 SLR 容易误判的根源。
  1. 左边 FOLLOW(A)收集“半成品 A 完成后，所有可能跟在后面的终结符”。
    FOLLOW(A)\text{FOLLOW}(A)
  2. 中间的推导关系S ⇒\* αAaβ 表示从开始符号 S 出发，经过任意多步推导，A 后面真的出现过终结符 a。
    S⇒∗αAaβS \Rightarrow^* \alpha A a \beta
  3. 花括号中的 a所有满足条件的不同终结符 a 都放进这个集合，无论语境是否一致。
    a∈FOLLOW(A)a \in \text{FOLLOW}(A)
  4. 关键缺陷无视上下文：FOLLOW 不管 A 究竟在哪条产生式、哪个位置出现，只要全局可能就收进来——这是 SLR 粗糙的根源。
    FOLLOW(A)=⋃所有语境{a}\text{FOLLOW}(A) = \bigcup_{\text{所有语境}} \{a\}

LR(1) 精确制导：看得见盘中餐的厨师

LR(1) 厨师看不惯 SLR 的“大类辩证法”，他的做法简单粗暴：在每一张便签末尾，额外写一个精确前瞻符号。便签从 [R → L ·] 升级为 [R → L ·, $]，意思是“只有当下一个输入符号恰好是 $ 时，才允许按 R → L 归约”。这个带前瞻的便签就叫 LR(1) 项目。归约不再看全局大类手册，而是看眼前具体食材——精确、可靠，绝不误判。

当然，精确是有代价的。每张便签都要附带前瞻符号，而同一个 LR(0) 项目在不同语境下的合法前瞻可能不同，于是墙上的一张便签被拆成多张，状态数随之暴涨。在龙书例子中，LR(1) 的状态数往往比 SLR/LALR 多出一大截，最坏情况甚至可能指数级膨胀。这就是传说中的状态爆炸：为了看一眼具体食材，厨师需要随身携带一只塞满便签的行李箱。

回到厨房：SLR 厨师看到传送带上的“甜椒”就敢归约，因为他查的大类手册说“甜椒可能出现在这之后”；LR(1) 厨师却要等看清是“甜椒”还是“朝天椒”才动手。这个“等看清”的动作，让他避开了几乎所有误判——但也让他的备菜手账厚到要在厨房单独加一张操作台来堆放。

[A→α⋅β, a]\displaystyle [A \to \alpha \cdot \beta, \ a]
这条公式就是 LR(1) 项目的完整形态：一条产生式进度 + 一个精确前瞻符号。它把“何时能归约”从大类级细化到单品级。
  1. 方括号是合成便签一条 LR(1) 项由“产生式进度”和“前瞻符号”两部分拼成。
    [ , ][ \ , \ ]
  2. 点号左侧是 αα 是已经确认备好的部分，点号表示进度走到了这里。
    α⋅\alpha \cdot
  3. 点号右侧是 ββ 是还差的部分，期望在后续输入中凑齐。
    ⋅β\cdot \beta
  4. 逗号后的 a 是精确前提只有当下一个输入符号正好是 a 时，才允许按这条产生式归约。
    [A→α⋅β, a][A \to \alpha \cdot \beta, \ a]

LALR 高明合并：会做笔记的聪明厨师

LALR 厨师看完两位师兄的表现，想出了一个折中方案：合并笔记。他注意到一个现象——LR(1) 的许多状态，去掉前瞻符号之后，剩下的 LR(0) 项目竟然一模一样。比如状态 I₁ 里写着 [R → L ·, $]，状态 I₂ 里写着 [R → L ·, =]，它们的内核（Core）完全相同，只是前瞻符号不同。LALR 厨师果断把这两张便签合并成一张：[R → L ·, {$, =}]。

这种内核相同的状态对，被叫做同心项目。合并之后，前瞻符号取并集，动作表的大小瞬间缩回 SLR 的水平。更妙的是，这种合并非常“安全”：因为每个状态原本的归约前瞻符号都和自己状态内的移进符号不相交，合并后的并集依然不会与移进符号产生新的交集——所以合并不会引入新的移进-归约冲突。唯一的隐患是，两个不同归约的前瞻集合合并后可能发生重叠，从而引入新的归约-归约冲突，不过这种情况在实践中相当少见。

LALR 厨师的高明之处在于：他既没有像 SLR 那样看大类而误判，也没有像 LR(1) 那样背着一箱便签。他把相近的笔记合并归类，用与 SLR 完全相同的便签数量，拿到了几乎与 LR(1) 持平的归约精度。这个“用合并换效率”的思路，在工程上简直是教科书级的优雅——后来的 Yacc 工具一眼就相中了他。

LA(Iij)=LA(Ii)∪LA(Ij),当 Core(Ii)=Core(Ij)\displaystyle \text{LA}(I_{ij}) = \text{LA}(I_i) \cup \text{LA}(I_j), \quad \text{当 } \text{Core}(I_i) = \text{Core}(I_j)
合并规则就一句话：两张便签的内核相同，就把它们贴在一起，前瞻符号并成一行。状态数减半，归约精度几乎不变。
  1. Core 相同是前提两个 LR(1) 状态去掉前瞻符号后，LR(0) 项目完全一致，才允许合并。
    Core(Ii)=Core(Ij)\text{Core}(I_i) = \text{Core}(I_j)
  2. LA 表示前瞻集合一个状态里所有前瞻符号 a 的集合。
    LA(I)={a∣[A→α⋅β,a]∈I}\text{LA}(I) = \{a \mid [A \to \alpha \cdot \beta, a] \in I\}
  3. 合并后取并集把两个状态的前瞻符号简单拼在一起，形成新的状态 I_ij。
    LA(Iij)=LA(Ii)∪LA(Ij)\text{LA}(I_{ij}) = \text{LA}(I_i) \cup \text{LA}(I_j)

冲突对比：谁家的菜谱更广

衡量三位厨师水平的最直接指标，是各自能驾驭的菜谱范围。在编译理论里，我们把“能被某类解析器无冲突处理的文法”称为一个文法类。SLR 处理不了的文法，LALR 可能处理得了；LALR 处理不了的，LR(1) 可能处理得了。三者构成一条严格递进的包含链。

为什么 LALR 能比 SLR 处理更多文法？因为 SLR 的冲突来自“大类很宽”的误判，而 LALR 用精确前瞻把这些误判全部消解掉了。那 LR(1) 又多出什么？答案在前文埋下的伏笔：LALR 合并同心项目时，偶尔会引入归约-归约冲突，而 LR(1) 从不合并，自然没有这个隐患。于是，存在一小撮文法，LALR 会报冲突、LR(1) 却安然无恙——这就是两者能力差距的全部来源。

这场“菜谱宽度”对比，结论非常治愈：LALR 与 LR(1) 的差距远小于 SLR 与 LALR 的差距。对绝大多数真实编程语言的文法来说，LALR 已经绰绰有余。工程界因此形成共识——与其一上来就抱着最重的 LR(1) 不放，不如先用 LALR 试试水，遇到真正“非 LR(1) 不可”的文法再升级。

SLR⊊LALR⊊LR(1)\displaystyle \text{SLR} \subsetneq \text{LALR} \subsetneq \text{LR}(1)
这条链说的是文法类的包含关系：SLR 的菜谱最小，LALR 居中，LR(1) 最大。最外层多出来的菜，几乎都是“归约-归约冲突”那类难题。
  1. SLR 严格小于 LALR存在文法能被 LALR 处理而 SLR 不能，例如龙书的 S→L=R | R 例子。
    SLR⊊LALR\text{SLR} \subsetneq \text{LALR}
  2. LALR 严格小于 LR(1)存在文法能被 LR(1) 处理而 LALR 不能，多由合并引入的归约-归约冲突导致。
    LALR⊊LR(1)\text{LALR} \subsetneq \text{LR}(1)
  3. 符号 ⊊ 表示真子集A ⊊ B 意味着 A 完全包含于 B 且两者不相等。
    A⊊B  ⟺  (A⊆B∧A≠B)A \subsetneq B \iff (A \subseteq B \land A \neq B)

实战选型：Yacc 的厨房为何选 LALR

20 世纪 70 年代，Yacc（Yet Another Compiler-Compiler）这间大型厨房要定一位“默认主厨”。候选人有三位：SLR 虽然手账薄，但误判太多；LR(1) 能力最强，可状态爆炸让内存捉襟见肘；LALR 手账和 SLR 一样薄，能力却接近 LR(1)。Yacc 毫不犹豫地选了 LALR——这个决定影响深远，直到今天，Yacc 的继承者 Bison 依然默认使用 LALR(1)。

要理解这个选择，就得算一笔内存账。解析器的动作表（ACTION 表和 GOTO 表）大小约等于状态数 × 终结符数。LALR 的状态数与 SLR 相同，比 LR(1) 小一个量级，动作表自然紧凑许多。在上世纪内存以 KB 计的时代，这是生死攸关的优势；即便在今天，紧凑的动作表也意味着更快的查表速度和更小的缓存压力。工程权衡的智慧在于：用 5% 的能力损失，换取 50% 甚至更多的内存节省，这笔买卖太划算了。

如今虽然内存不再昂贵，但 LALR 的霸主地位依然稳固。Bison、SableCC、CUP 等工具都把 LALR 作为默认；只有当文法确实触发 LALR 的归约-归约冲突时，工程师才会转向 Menhir 等支持 LR(1) 甚至 LR(1) 变体的工具。选型要诀一句话：默认 LALR，冲突时先用优先级声明化解，实在不行再上 LR(1)。这既是工具链的现实，也是工程上“够用就好”的智慧。

M=∣Q∣×∣T∣\displaystyle M = |Q| \times |T|
动作表的大小 M 约等于状态数 |Q| 乘以终结符数 |T|。LALR 之所以省内存，正是因为它的状态数 |Q| 比 LR(1) 小得多。
  1. M 是动作表规模解析器需要为每个状态 × 每个终结符准备一个动作槽位。
    M=∣Q∣×∣T∣M = |Q| \times |T|
  2. |T| 是终结符个数终结符就是代码里的关键字、标识符、运算符等“基础食材”。
    ∣T∣=∣Σ∣|T| = |\Sigma|
  3. |Q| 是状态数LALR 的状态数与 SLR 相同，通常远小于 LR(1)。
    ∣QLALR∣=∣QSLR∣≪∣QLR(1)∣|Q_{\text{LALR}}| = |Q_{\text{SLR}}| \ll |Q_{\text{LR(1)}}|

AI 应用场景

编译器和解释器前端开发

阶段：编译器前端语法分析环节

解决的问题：在用 Yacc/Bison 编写编程语言解析器时，语法文件常常报出 “shift/reduce conflict“ 或 ”reduce/reduce conflict”。新手往往一头雾水，不知道冲突从哪里来；理解 SLR 的 FOLLOW 集误判、LALR 的同心合并机制后，就能快速定位冲突来自哪条规则、哪个前瞻符号，并用优先级(%prec)或重写文法来化解。

具体案例：某团队用 Bison 为内部 DSL 编写解析器，语法文件出现 3 处 "conflicts: 3 shift/reduce"。工程师借助 LALR 的合并逻辑，逐条检查冲突状态中的 LR(1) 项目，发现是赋值语句的右值文法过宽导致 FOLLOW 集重叠，通过拆分产生式将冲突清零。

现代解析器生成器的选型评估

阶段：解析方案架构选型

解决的问题：Rust 生态的 LALRPOP、Go 生态的 goyacc、Java 生态的 CUP 都基于 LALR(1)；而 Menhir、LRSTAR 等支持完整 LR(1)。选型时需要判断：文法是否超出 LALR 能力边界？如果超出，是改写文法迁就 LALR，还是直接上 LR(1) 工具？

具体案例：某数据库团队要设计一套类 SQL 的查询语言，文法中嵌套 JOIN 的 on 子句与子查询边界极其微妙，LALR 出现归约-归约冲突且难以改写。团队最终选择 Menhir 的 LR(1) 模式，用更大的动作表换来了文法的自然表达。

静态分析工具中的表达式解析

阶段：源代码解析与 AST 构建

解决的问题：代码检查工具需要处理各种语言里复杂的运算符优先级与结合性。SLR 的 FOLLOW 集过宽容易在表达式文法上产生冲突；理解三者的能力差异后，工程师可以放心使用 LALR 配合优先级声明来处理绝大多数表达式文法，而不必担忧状态爆炸。

具体案例：某 Python 静态分析工具使用 LALR(1) 解析器解析 f-string 中嵌套的表达式，利用 %prec 声明化解了 lambda 表达式与条件表达式的移进-归约歧义，最终在保持解析速度的同时实现 99.9% 的语法覆盖率。

Python 演示

python110 行
#!/usr/bin/env python3# -*- coding: utf-8 -*-"""SLR vs LALR vs LR(1) 前瞻决策对比演示。使用龙书经典文法:    S -> L = R | R    L -> * R | id    R -> L该文法不是 SLR(1), 但属于 LR(1), 且 LALR(1) 也能处理。本程序计算出 FOLLOW 集合, 并在关键状态 I2 上对比三种决策。"""from collections import defaultdict grammar = {    'S': [['L', '=', 'R'], ['R']],    'L': [['*', 'R'], ['id']],    'R': [['L']],}terminals = {'*', '=', 'id', '$'}nonterms = set(grammar)EPS = 'eps'  def compute_first():    first = defaultdict(set)    for t in terminals:        first[t].add(t)    changed = True    while changed:        changed = False        for A in grammar:            for body in grammar[A]:                before = len(first[A])                for X in body:                    if X in terminals:                        first[A].add(X)                        break                    first[A] |= first[X] - {EPS}                    if EPS not in first[X]:                        break                else:                    first[A].add(EPS)                if len(first[A]) != before:                    changed = True    return first  def compute_follow(first):    follow = defaultdict(set)    follow['S'].add('$')    changed = True    while changed:        changed = False        for A in grammar:            for body in grammar[A]:                trailer = follow[A]                for i in range(len(body) - 1, -1, -1):                    B = body[i]                    if B in nonterms:                        before = len(follow[B])                        follow[B] |= trailer                        if EPS in first[B]:                            trailer = trailer | (first[B] - {EPS})                        else:                            trailer = first[B]                        if len(follow[B]) != before:                            changed = True                    else:                        trailer = {B}    return follow  def main():    first = compute_first()    follow = compute_follow()    print('FIRST 集合:')    for A in sorted(grammar):        print('  FIRST(%s) = %s' % (A, sorted(first[A] - {EPS})))    print('FOLLOW 集合:')    for A in sorted(grammar):        print('  FOLLOW(%s) = %s' % (A, sorted(follow[A])))     print()    print('关键状态 I2 = { S -> L . = R, R -> L . }')    print('当前栈顶可以按 R -> L 归约, 而栈外下一个符号是 =')    print()     print('[SLR] 判断依据: FOLLOW(R)')    print('  FOLLOW(R) = %s' % sorted(follow['R']))    print('  归约动作覆盖: FOLLOW(R) 中全部符号')    print('  移进动作需要: =')    overlap = set(follow['R']) & {'='}    print('  两者交集: %s' % sorted(overlap))    if overlap:        print('  结论: 发生 shift/reduce 冲突, SLR 无法处理!')    else:        print('  结论: 无冲突')     print()    print('[LR(1)] 判断依据: 精确前瞻符号')    print('  项目 [R -> L . , {$}] 只在遇到 $ 时归约')    print('  项目 [S -> L . = R, {$}] 只在遇到 = 时移进')    print('  归约集 {$} 与移进集 {=} 不相交 -> 无冲突, LR(1) 可以处理!')     print()    print('[LALR(1)] 合并同心项目集后')    print('  状态数与 SLR 相同, 但本状态的动作与 LR(1) 一致 -> 同样可以处理!')  if __name__ == '__main__':    main()
目的：通过计算 FIRST/FOLLOW 集合并在关键状态上模拟决策，直观展示“SLR 因 FOLLOW 集过宽而冲突、LR(1) 与 LALR 因精确前瞻而通过”的完整过程。
  1. from collections import defaultdict引入默认字典，方便给每个非终结符动态追加 FIRST/FOLLOW 集合。
  2. first[t].add(t)每个终结符的 FIRST 集合就是它自己，这是固定点迭代的初始条件。
  3. first[A] |= first[X] - {EPS}把产生式右部第一个符号 X 的 FIRST 集合传播给左部 A，EPS 本身除外。
  4. if EPS not in first[X]: break一旦 X 不能推出空串，就不再看右部后续符号，立即停止传播。
  5. else: first[A].add(EPS)右部所有符号都能推出空串时，左部 A 才能把空串加进 FIRST。
  6. trailer = follow[A]从右往左扫描产生式时，先把左部 A 的 FOLLOW 集作为初始“后继者”。
  7. follow[B] |= trailer把后继者并入非终结符 B 的 FOLLOW 集合，完成一次传播。
  8. print(' 交集: %s' % sorted(overlap))打印 SLR 的归约符号集与移进符号的交集，揭示冲突来源。
  9. set(follow['R']) & {'='}判断 FOLLOW(R) 与移进符号是否重合，是 SLR 冲突检测的核心逻辑。
  10. if __name__ == '__main__': main()可执行入口，保证脚本可被直接运行，也便于被其他模块导入。

常见误区

误区我听说 SLR 和 LALR 的状态数相同，那它们处理文法、解决冲突的能力应该也完全一样吧？反正状态数都一样多，LALR 不就是 SLR 换了个名字吗？

正解状态数相同不等于能力相同。SLR 与 LALR 共用同一个 LR(0) 状态机，但归约决策的依据截然不同：SLR 查全局 FOLLOW 集（食材大类），LALR 用合并后的精确前瞻（具体食材）。就像两个厨师都只有 100 张便签，一个靠猜大类做事，另一个靠精确菜单做事，出错率当然不一样。龙书中的 S→L=R|R 文法，SLR 会报冲突，LALR 却顺利通过——这就是状态数相同、能力不同的铁证。

为何常见：初学者看到状态数这一最直观的指标相同，就误以为其他属性也一致，忽略了“前瞻精度”这一真正决定能力的隐藏维度。

误区LALR 是从 LR(1) 合并来的，简化版总该继承完整版的全部能力吧？既然 LR(1) 能处理某文法，LALR 肯定也能处理。

正解合并操作会带来微小但真实的能力损失。LR(1) 从不合并状态，因此绝不会出现“两个不同归约的前瞻符号被并到一起”的情况；而 LALR 合并同心项目后，前瞻取并集，可能让两个原本互不干扰的归约动作撞车，产生新的归约-归约冲突。这类文法虽然稀少，但在真实语言里确实存在。换句话说：LALR 是 LR(1) 的“近似”，而不是“子集套壳”。

为何常见：人们天然认为“简化 = 丢弃冗余、保留核心”，却忽略合并操作可能把原本隔离的信息混在一起，产生新问题。

误区我用 Bison 写语法文件时看到 "shift/reduce conflict" 的警告，第一反应是：这文法是不是不适合 LR 分析？要不要换成别的解析方法？

正解冲突只是“某一类”解析器处理不了，不代表所有 LR 家族都不行。SLR 报冲突的文法，LALR 可能无冲突；LALR 报冲突的文法，LR(1) 可能无冲突。更常见的是，冲突其实可以用优先级声明来化解——比如经典的四则运算表达式文法，在加"+ 的优先级声明后，LALR 就能无冲突处理。遇到冲突先看类型、定位状态，再判断是改文法、加优先级还是升级解析器，而不是直接否定整个 LR 路线。

为何常见：新手常把“一种解析器的失败”放大为“整个解析方案的失败”，忽略了分析家族内部的层次结构与优先级声明这套成熟化解手段。

误区LR(1) 的"1"是不是表示解析器要提前读入 1 个完整字符？那 LR(2) 是不是要读 2 个字符？向前看越多，能力一定越强。

正解LR(1) 的“1“指向前看一个”输入符号“（token），比如标识符、关键字、运算符，而不是一个字符。而且它的含义不是”预留并消耗掉这个符号“，而是”在归约决策时查询当前输入符号是否在允许集合里“，符号本身仍留在输入流中。能力变强的本质是归约决策获得了上下文信息，而非”多读了几位字符”。

为何常见：从词法分析的“读字符”直觉迁移到语法分析的“读 token”，又混淆了“查看”与“消费”两个完全不同的操作，才产生这个偏差。

面试题

Q1. 关于 SLR、LALR、LR(1) 三种解析器的状态数，下列哪项正确？

单选题 · easy

  • A.SLR 状态数少于 LALR
  • B.SLR 与 LALR 状态数相同，LR(1) 通常更多← 正确答案
  • C.三者状态数完全相同
  • D.LR(1) 与 LALR 状态数相同，SLR 更少

答案：B。SLR 与 LALR 都建立在同一个 LR(0) 状态机上，因此状态数相等；LR(1) 因为状态内携带前瞻符号、划分更细，状态数一般更多。这就像 SLR 和 LALR 两位厨师手账都是 100 页，而 LR(1) 的后厨手账更厚。故选 B。

Q2. 自底向上语法分析中，“把栈顶若干符号按照产生式替换为左部非终结符”的动作叫作？

单选题 · easy

  • A.移进
  • B.归约← 正确答案
  • C.接受
  • D.推导

答案：B。移进是把输入符号压入栈顶；归约是用产生式的左部替换掉栈顶能匹配右部的一串符号；接受是分析成功结束；推导是自上而下的概念。归约正如厨师把台上几件食材拼成一道半成品菜，故选 B。

Q3. SLR(1) 解析器的归约动作主要依据什么来判定？

单选题 · mid

  • A.产生式左部非终结符的 FIRST 集
  • B.当前状态下精确的前瞻符号
  • C.产生式左部非终结符的 FOLLOW 集← 正确答案
  • D.输入串中所有符号的集合

答案：C。SLR 用 FOLLOW 集作前瞻，只要当前输入符号属于左部非终结符的 FOLLOW 集就允许归约。FOLLOW 集是全局大类的近似，不够精确。FIRST 集用于预测推导而非归约决策；精确前瞻是 LR(1) 的特征。故选 C。

Q4. 关于 LALR(1) 解析器，下列说法正确的有？

多选题 · mid

  • A.状态数与 SLR(1) 相同← 正确答案
  • B.由 LR(1) 状态合并同心项目集而来← 正确答案
  • C.合并后不会产生新的移进-归约冲突← 正确答案
  • D.合并后不会产生新的归约-归约冲突

答案：ABC。LALR 由 LR(1) 合并“内核相同”的同心项目而来，合并前后状态数与 SLR 相同；合并只把前瞻取并集，不会新增移进-归约冲突（各状态前瞻原本就与移进符号不相交，并集亦然）；但两个不同归约的前瞻集合可能因合并而重叠，从而可能引入新的归约-归约冲突。因此 D 错误，选 ABC。

Q5. 龙书经典文法 S → L = R | R、L → * R | id、R → L，为什么 SLR(1) 无法处理？

单选题 · hard

  • A.FIRST(S) 为空集
  • B.FOLLOW(R) 包含 '='，在状态 S→L·=R 与 R→L· 处引发移进-归约冲突← 正确答案
  • C.文法存在左递归导致栈无限增长
  • D.FOLLOW(L) 包含 '$' 导致归约冲突

答案：B。SLR 在状态 {S→L·=R, R→L·} 中，面对输入 '=' 时，既需要移进（因为 S→L·=R），又因为 = 属于 FOLLOW(R) 而想按 R→L 归约，形成冲突。左递归本身不导致此问题，LR(1) 能精确判断该状态下 '=' 不应触发归约。故选 B。

Q6. 在 LR(1) 项目 [A → α·β, a] 中，前瞻符号 a 的作用是什么？

多选题 · mid

  • A.指示只有当下一个输入符号为 a 时才允许按此产生式归约← 正确答案
  • B.指示必须读入 a 才能执行移进动作
  • C.让归约决策携带上下文信息，提高精度← 正确答案
  • D.用于计算产生式右部的 FIRST 集

答案：AC。前瞻符号 a 是归约动作的“许可证”：下一个输入符号恰为 a 时才能归约，从而把决策从全局 FOLLOW 细化到具体语境。它不影响移进动作，也跟 FIRST 集计算无关。就像 LR(1) 厨师看清具体食材才动手，故选 AC。

Q7. Yacc 和 Bison 默认采用哪种解析器？

单选题 · easy

  • A.SLR(1)
  • B.LL(1)
  • C.LALR(1)← 正确答案
  • D.LR(1)

答案：C。Yacc 与 Bison 的默认解析器是 LALR(1)。它状态数与 SLR 相同、内存紧凑，能力又接近 LR(1)，是工程上的最佳折中。LL(1) 是自顶向下家族的产物。故选 C。

Q8. 将两个 LR(1) 状态合并为 LALR 状态时，“同心”指的是什么？

单选题 · hard

  • A.两个状态的前瞻符号完全相同
  • B.去掉前瞻符号后，LR(0) 项目完全相同← 正确答案
  • C.两个状态在状态机中的编号相邻
  • D.两个状态的动作表完全相同

答案：B。同心项目 = 内核相同，即去掉方括号中逗号后的前瞻符号后，LR(0) 项目一模一样。正因为内核相同，合并后不会改变状态机的跳转骨架，才能安全地把前瞻取并集。动作表完全相同与否不是合并的前提。故选 B。

Q9. 关于 SLR(1) 的局限性，下列说法正确的有？

多选题 · mid

  • A.FOLLOW 集可能包含实际不会出现的符号← 正确答案
  • B.过宽的前瞻集可能引发移进-归约冲突← 正确答案
  • C.SLR 状态数与 LALR 相同← 正确答案
  • D.SLR 比 LR(1) 的表达能力更强

答案：ABC。FOLLOW 集是全局收集的，可能把别的语境中的符号也算进来，导致归约面过宽、引发伪冲突；SLR 与 LALR 共用 LR(0) 状态机，状态数一致；但表达能力上 SLR 是三者中最弱的，D 明显错误。故选 ABC。

Q10. 关于 LR(1) 自动机状态数相对 LALR 的最坏情况，下列哪项正确？

单选题 · extreme

  • A.两者完全相同
  • B.最多多一个状态
  • C.理论上可能呈指数级膨胀← 正确答案
  • D.一定比 LALR 少

答案：C。LR(1) 把每个 LR(0) 状态按前瞻符号细分，最坏情况下状态数可以按输入符号组合数指数级增长，这就是“状态爆炸”现象。LALR 通过合并同心项目恰好规避了这一点。因此 C 正确，其余选项不成立。