想象你同时扮演两个角色：一位话剧导演和一位乐高拼装师。 导演的工作是拿着完整剧本，从第一幕开始，根据演员念出的每一句台词，判断剧情该往哪里走——这叫“自顶向下”的 LL 解析，导演就是 LL 解析器。乐高拼装师则完全不同，他不需要说明书，只凭手里积木的形状，看到几块能拼成标准组件就顺手拼好，组件越来越大，最后拼出整个模型——这叫“自底向上”的 LR 解析。 编译器把高级语言翻译成机器码，也像一场精密排练。在“语法分析”环节，程序员的代码（token 流）是演员的台词，而编程语言的语法规则（文法）就是剧本。LL 与 LR 正是两大流派解析器的代表。这篇文章带你从零理解这两种解析器的工作原理、分析表构建、冲突处理，以及各自的强项。学完你会发现：原来编译器的“阅读理解”，就是一门导演与拼装师的统筹艺术。

岗位关联

对 AI 从业者而言，语法分析是理解语言模型“结构理解”、构建结构化数据解析系统的基石。掌握 LL/LR 原理，等于拿到了阅读解析器源码、驾驭 Yacc/Bison/ANTLR 等工具的钥匙。

目录
  1. 可视化演示
  2. 语法分析概览：解析器的“剧本与积木”
  3. LL自顶向下：导演按剧本排戏
  4. FIRST与FOLLOW：导演的场记表
  5. LR自底向上：拼装师的魔力
  6. LR分析表构建：状态机的幕后图纸
  7. 冲突处理：岔路口的选择题
  8. 表达力对比：两种手艺的较量
  9. 工具与实践：选择你的工具包
  10. AI 应用场景
  11. Python 演示
  12. 常见误区
  13. 面试题

可视化演示

对比LL自顶向下预测分析与LR自底向上移进归约两种语法解析范式，展示解析树构建方向、栈操作流程及分析表结构差异。

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

解析过程对比 LL解析器从起始符号S出发，自顶向下展开解析树，通过FIRST集预测下一个产生式 LR解析器从输入串出发，自底向上移进归约，通过ACTION/GOTO表驱动栈操作 LL: S→AB | LR: ab→A→S LL(1)简单但表达力弱，LR(1)强大但实现复杂。

语法分析概览：解析器的“剧本与积木”

不管是导演还是拼装师，开工前都要有一份“总纲”。导演拿的是剧本——每一幕每一场怎么演写得明明白白；拼装师拿的是说明书——每个模型由哪些标准组件组成。在编译世界里，这份总纲就叫文法（Grammar）。

编译器读入源代码，先做词法分析，把字符流切成一个个 token，就像把一整篇文章切成带词性的单词；紧接着就是语法分析，负责按文法把这些“单词”组装成有结构的句子——语法树。这一层是编译器的“阅读理解”环节，语法树生成得对不对，直接决定后续语义分析和代码生成的质量。

文法由一条条产生式组成，比如下面的规则描述了一个最简表达式：一个表达式可以是一个表达式加一个项，也可以直接是一个项。

所以，无论导演方式还是拼装方式，大家都服务于同一份“剧本”（文法）；差别只在于——谁从头念到尾，谁从碎片拼到顶。理解这一点，你就握住了两大解析流派的共同根基。

E→E+T∣TE \to E + T \mid T
这条产生式说：“表达式（E）有两种写法：要么写成'表达式加项'，要么直接写成一个项（T）。”竖线 | 表示“或者”，是给导演和拼装师看的剧本选项。
  1. 符号 E代表“表达式”这个语法范畴，属于非终结符——它还要继续展开，不能直接出现在最终串中。
    EE
  2. 推导箭头表示“可以展开为”，是产生式的核心关系，左边是左部，右边是右部。
    →\to
  3. 右部 E+T表示递归地将 E 展开成“一个 E、一个加号、一个 T”，这是处理二元运算的经典写法。
    E+TE + T
  4. 竖线分隔表示文法为 E 提供了两种可选展开方式，解析器需要在两者间做选择，而“怎么选”正是 LL 与 LR 的分水岭。
    ∣\mid

LL自顶向下：导演按剧本排戏

导演拿到剧本后，从第一幕（开始符号）开始读。比如剧情是“一个表达式”，剧本写着 E → T+E，导演就布置三场戏：先演 T，再演 +，最后演 E。每场戏继续按各自的剧本展开，直到所有台词（终结符）与观众听到的完全一致。

这个“边念台词、边定下一步”的过程就是 LL 预测分析。LL 中第一个 L（Left-to-right）表示从左向右读输入，第二个 L 表示产生最左推导；括号里的 1 表示每次只需看一眼当前 token 就能决定下一步动作。导演因此自信满满：台词一出口，我立刻知道剧本翻到哪一页。

递归下降是 LL 家族最直观的实现——为每个非终结符写一个函数，函数内部按产生式逐个“调用”其他函数，代码几乎就是文法的一对一翻译。但导演对剧本有硬性要求：剧本不能“循环套娃”。像 E → E+T 这种左递归规则，会让导演永远往下钻、无法停止，必须先改写为等价的右递归形式。

LL 导演的秘诀是：剧本必须“一眼可断”——任何时刻看到一句台词，就能唯一确定下一步排哪场戏。如果一份文法能让导演随时做到这一点，它就被称为 LL(1) 文法。

E⇒T+E⇒F+E⇒id+EE \Rightarrow T + E \Rightarrow F + E \Rightarrow id + E
这一串箭头表示“推导”：表达式一步步被展开，从抽象的非终结符，最终落到具体的单词 id。每走一步，导演就看一眼剧本、布置一场更细的戏。
  1. 推导记号表示“一步推导”，即把当前串中的某个非终结符按产生式替换成右部。
    ⇒\Rightarrow
  2. 第一步展开把 E 按 E→T+E 展开，得到 T+E，导演先排“T 这场戏”。
    E⇒T+EE \Rightarrow T + E
  3. 展开 T 为 F继续把 T 按 T→F 展开，演出计划变成"F+E"。
    T⇒FT \Rightarrow F
  4. 落到终结符F 最终展开为 id（标识符），推导完成，台词与输入对齐。
    F⇒idF \Rightarrow id

FIRST与FOLLOW：导演的场记表

导演怎么做到“一眼可断”？他需要两本场记表。FIRST 表记录：“这场戏的第一句台词可能是什么”；FOLLOW 表记录：“这场戏演完后，观众接下来可能听到哪句台词”。两张表一配合，导演查表即可决策。

FIRST 集的计算是递归的：终结符的 FIRST 集就是它自己；非终结符的 FIRST 集，是其所有产生式右部首符号的 FIRST 集的并集；若某个右部能推导出空串 ε，还要继续看下一个符号。FOLLOW 集的计算则从开始符号出发，沿产生式右部“往后看”，收集可能紧跟其后的终结符。

有了这两张表，就能构建预测分析表：表的行是非终结符，列是终结符，格子里填“该用哪条产生式展开”。只要每个格子里至多有一个产生式，LL(1) 分析就畅通无阻；否则导演就会在岔路口迷茫。

LL(1) 中的"1"就建立在这两张表上：任何时刻查表都必须恰好有一格有值。场记表越精确，导演就越镇定；表上一旦出现空格或有重复，戏就排不下去了。

FIRST(α)={a∣α⇒∗aβ, a∈VT}\mathrm{FIRST}(\alpha) = \{ a \mid \alpha \Rightarrow^* a\beta,\ a \in V_T \}
这个公式说：FIRST(α) 是所有“从 α 出发、经过零步或多步推导后，得到的串的首个终结符”的集合。通俗讲，就是“这场戏可能以哪句台词开场”的完整清单。
  1. FIRST(α)求符号串 α 的首终结符集合，它是预测分析表的核心索引。
    FIRST(α)\mathrm{FIRST}(\alpha)
  2. 集合构造式用一个条件来定义集合中的元素，竖线前是元素形式，竖线后是条件。
    {a∣… }\{ a \mid \dots \}
  3. 多步推导表明 α 可以经过零步或任意有限步推导，变成以终结符 a 开头的串。
    ⇒∗aβ\Rightarrow^{*} a\beta
  4. 终结符集合a 必须属于终结符集合 V_T，即最终要落在具体的单词上。
    a∈VTa \in V_T

LR自底向上：拼装师的魔力

镜头切到拼装师。他不需要剧本，只需要把零件一个个拿起来——这个动作叫“移进”。手里攒了几个零件，发现它们的形状正好能拼成一个“项”（T），就啪嗒一声拼起来——这个动作叫“归约”。拼好的部件继续参与下一轮拼装，直到最后拼出完整的表达式模型。

移进-归约分析的流程很机械但很强大：分析器维护一个栈，每次把当前输入 token 压入栈顶（移进）；一旦栈顶的若干符号恰好匹配某条产生式的右部（称为句柄），就用产生式左部替换它们（归约）。整个过程其实就是“最右推导的逆过程”——拼装师每归约一次，就是在逆着推导方向走一步。

LR 的含义：L 仍表示从左向右读输入，R 表示“最右推导的逆”。括号里的 1 表示归约时向前看一个符号。LR 分析器本质上是一个精密的自动机，所有“移进还是归约”的动作都预先写在分析表里，运行时只需机械查表。

拼装师的厉害之处在于：他不需要预先知道全貌，只凭局部形状判断“拼还是不拼”，照样能完成最复杂的拼装——这正是 LR 表达力强于 LL 的深层原因：决策永远基于已经看到的局部事实，而不是全局预测。

E+id⇐E+T⇐EE + id \Leftarrow E + T \Leftarrow E
这个反向箭头链表示归约的逆过程：从"E + id“出发，把 id 归约为 T，再把整个”E + T"归约为 E。拼装师每一步都在把散件拼成更大的组件。
  1. 当前局面栈中已经积累了 E + id，输入中还剩后续符号，拼装师盯着手里的零件。
    E+idE + id
  2. 第一次归约id 是 T→id 的右部，把 id 替换为 T，栈变成 E + T。
    E+id⇐E+TE + id \Leftarrow E + T
  3. 第二次归约E+T 恰好是 E→E+T 的右部，整个替换为 E，拼出模型顶部。
    E+T⇐EE + T \Leftarrow E
  4. 逆推导方向所有箭头都是可逆的；LR 做的是从右往左读推导，LL 是从左往右推导。
    ⇐\Leftarrow

LR分析表构建：状态机的幕后图纸

拼装师怎么知道“何时该拿、何时该拼”？他手上有一张精密的状态图。图中的每个状态用 LR(0) 项目描述，比如 E→E·+T，圆点表示“我已经看到了 E，正在等待一个 +”。

把所有可能的状态以及状态之间的转移连起来，就得到项目集规范族——本质是一个确定有限自动机（DFA）。每个状态记录“拼到一半”的所有可能情况，遇到不同输入符号就跳转到下一个状态。SLR 分析法在归约时用 FOLLOW 集过滤掉不可能的归约；LR(1) 则让每个项目额外携带一个向前看符号，决策更精细；LALR(1) 将“核心相同”的状态合并，在表大小与表达能力之间取得平衡。

Yacc/Bison 这类工具就是自动完成这套构建流程：输入文法，工具内部生成项目集规范族，再输出一张驱动解析器的分析表。你不需要手工画状态图，但理解这张图，才能看懂工具打印的冲突警告。

项目集规范族是 LR 家族共同的“幕后图纸”：SLR、LR(1)、LALR 的区别，只在于给这些状态补充了多少“向前看”的侦察信息。侦察越细致，决策越准，但状态也越多。

E→E⋅+TE \to E \cdot + T
这个 LR(0) 项目表示分析器正处于“已经看到 E，圆点停在加号前”的状态。圆点是进度标记：前面是已读入的符号，后面是期待中的符号。
  1. 项目左部E 是归约目标的非终结符，表示拼到一半的组件类型。
    E→E⋅+TE \to E \cdot + T
  2. 圆点位置圆点前的 E 已出现在栈顶，说明本状态关心的是“如何继续拼成更大的 E”。
    ⋅\cdot
  3. 圆点后的符号加号 + 是当前正在等待的终结符，看到它才能继续前进。
    +T+ T
  4. 状态转移语义每个圆点位置不同，对应 DFA 中一个不同的状态；圆点跨过符号的过程就是状态转移。
    E⋅+TE \cdot + T

冲突处理：岔路口的选择题

无论导演还是拼装师，都会遇到岔路口。拼装师手里状态显示：既可以“继续拿起下一个零件”，又可以“把现有零件拼起来”——这就是移进-归约冲突；另一种情况是同一撮零件既能拼成 A 又能拼成 B——这就是归约-归约冲突。

绝大多数编程语言文法的冲突，可以用优先级与结合性化解。就像生活中“先乘除后加减”一样，Yacc 里一句 %left '+'、%left '*' 就能告诉解析器：乘号优先级更高，遇到冲突时先归约。结合性则处理连写问题：a-b-c 是 (a-b)-c 还是 a-(b-c)？左结合就选前者。

如果冲突无法用优先级解决，就需要动手改造文法：提取公共因子、改写递归结构、引入新的非终结符分层。这就像把“一团乱麻”的岔路口改造成“立交桥”——每一层只走一个方向，自然不冲突。

冲突处理是解析器工程中最“接地气”的部分。导演的剧本和拼装师的手感都难免遇到模棱两可，好在有优先级、结合性和文法改造这三件法宝——把岔路口改造成红绿灯井然的十字路口，解析才能一路畅通。

FIRST(α)∩FIRST(β)=∅\mathrm{FIRST}(\alpha) \cap \mathrm{FIRST}(\beta) = \varnothing
这个公式是 LL(1) 无冲突的必要条件：同一个非终结符的两条产生式，其右部的 FIRST 集必须不相交；否则导演看到同一句台词时会不知道翻哪一页剧本。
  1. 两个候选右部α 和 β 是同一非终结符的两条不同产生式的右部，代表两个可选方向。
    FIRST(α)\mathrm{FIRST}(\alpha)
  2. 集合交集∩ 表示两个集合共同拥有的元素；交集非空说明存在一个 token 同时是两个方向的开头。
    ∩\cap
  3. 空集条件交集等于空集，才保证任意时刻至多一个产生式可选，预测表才无冲突。
    ∅\varnothing

表达力对比：两种手艺的较量

拼装师的能力上限比导演更高。形式语言理论给出了清晰的包含链：LL(1) 文法类 ⊂ LALR(1) 文法类 ⊂ LR(1) 文法类。也就是说，凡是 LL 能处理的文法，LR 几乎都能处理；但反过来，很多 LR 可解析的文法（比如包含左递归的文法），LL 需要先改写才能用。

但导演有导演的优势。LL 自顶向下推进，一旦第一个 token 不符合预期，立刻就能报错——错误定位靠前、提示直观，非常适合交互式场景；而 LR 要等栈里攒够信息才做归约，发现错误时往往已经读了很远，错误定位相对滞后。LL 的预测表也小得多，逻辑直观，手写实现、断点调试都更轻松。

实际工程中，编程语言的语法通常比较复杂，包含大量左递归规则；若交给工具自动生成，LALR 是性价比之王（Yacc 默认）；若团队想要友好错误提示和灵活扩展，手写递归下降的 LL 风格反而更受青睐。

两种手艺没有绝对的优劣，只有匹配的场景。导演适合“边演边看、随时纠错”的舞台，拼装师适合“默默堆叠、最后成型”的流水线。理解了表达力差异，你就知道在何种场景该请哪位出场。

LL(1)⊊LALR(1)⊊LR(1)\mathrm{LL}(1) \subsetneq \mathrm{LALR}(1) \subsetneq \mathrm{LR}(1)
这个包含链表示三种文法类的表达能力关系：LL(1) 最“挑剧本”，LALR(1) 居中，LR(1) 能力最强。一枚硬币的两面——能力越强，表越大、构建越复杂。
  1. LL(1)最左侧，要求最严格、表最小，适合手写。
    LL(1)\mathrm{LL}(1)
  2. 严格包含⊊ 表示“真子集”，左边集合严格包含于右边，且不等于右边。
    ⊊\subsetneq
  3. LALR(1)位于中间，Yacc 的默认选择，兼顾表大小与文法适用范围。
    LALR(1)\mathrm{LALR}(1)
  4. LR(1)最右侧，能力最强，状态数也最多，常用于理论研究与小规模文法。
    LR(1)\mathrm{LR}(1)

工具与实践：选择你的工具包

导演和拼装师都有成熟的工具链。导演系代表是 ANTLR，也有大量手写递归下降解析器；拼装师系则以 Yacc 与 Bison 为旗帜——只要提供文法，它们自动完成项目集构建、冲突检测并生成 C 代码解析器。

现实世界的选型往往是工程权衡。MySQL 使用 Bison（LALR）处理复杂 SQL 文法；Go 语言的编译器则完全手写递归下降，换取友好的错误信息和流畅的增量编译体验；Rust、Zig 等新语言也偏爱手写 LL 风格解析器，以便给出“这里缺了个分号”这类贴心提示。选择依据很简单：你的语言文法有多复杂？你需要多友好的错误提示？你的团队能不能维护一个自动生成的巨大分析表？

下面是一段 Bison 风格文法的骨架示意，它背后的形式文法就是本节关注的核心。

从文法理论到工具落地，是一条成熟的链路：你只需描述“剧本该怎么演”，Bison 或手写解析器负责把剧本变成可执行的分析逻辑。理解了 LL 与 LR 的原理对比，你就能在这条链路的源头做出理性选择，而不是被工具的默认行为牵着走。

expr→expr+term∣termexpr \to expr + term \mid term
这是 Yacc 规则 expr: expr '+' term | term; 背后的文法形式。工具拿到这条规则，就为拼装师准备了一条“看到 E+T 就归约为 E”的组装指令。
  1. expr语法树的根概念——表达式，对应 Yacc 规则左部。
    exprexpr
  2. 递归右部expr+term 是递归形式，允许无限长的加法链，如 a+b+c。
    expr+termexpr + term
  3. 终结符加号Yacc 中用单引号包裹的字面量就是终结符 token。
    ′+′' + '
  4. 终止选项 term提供递归出口，表达式最终落到无法再拆的项上。
    ∣term\mid term

AI 应用场景

编译器前端开发：用 Bison 搭建新语言解析器

阶段：语法分析（Compiler Frontend）

解决的问题：设计一门新的 DSL（领域专用语言）时，手写解析器不仅耗时且易出错。传统做法是人工维护递归下降代码，文法一变就要大改函数逻辑；用 Bison 只需维护文法文件，工具自动生成 LALR 解析器 C 代码，文法调整后重新生成即可，把“导演的即兴发挥”变成“拼装师的流水线作业”。

具体案例：某团队设计配置语言，文法包含嵌套块与运算符优先级。用 Bison 声明 %left '+'、%left '*' 后，冲突自动消解，生成的分析器在 500 万行配置上解析零歧义。

IDE 语法高亮与代码补全：递归下降的友好错误

阶段：增量解析（Incremental Parsing）

解决的问题：IDE 需要在用户敲代码的瞬间给出反馈，错误信息必须精确到“第几行缺了什么”。LR 分析器错误定位滞后，LL 风格的手写递归下降则能边读边报，天然适合增量重解析——用户改了一个 token，只需重解析受影响的子树。

具体案例：Go 语言的 gopls 语言服务器使用手写递归下降解析器，在用户未输完的代码上也能生成不完整语法树，实现自动补全与括号匹配。

SQL 解析与查询优化：LALR 在数据库中的应用

阶段：查询编译（Query Compilation）

解决的问题：数据库系统每秒要解析大量 SQL，解析器既要快又要稳。SQL 文法含有大量左递归规则，LR 家族天然支持，无需改写；用 Bison 生成 LALR 解析器，语法树直接喂给查询优化器，效率与可维护性兼得。

具体案例：MySQL 的 sql_yacc.yy 文法文件包含上千条产生式，经 Bison 生成解析器后，一条复杂的联表查询在微秒级完成解析并进入优化环节。

Python 演示

python61 行
# -*- coding: utf-8 -*-# LL(1) 预测分析器演示：解析 id + id * id# 文法（已消除左递归）:#   E  -> T E'#   E' -> + T E' | ε#   T  -> F T'#   T' -> * F T' | ε#   F  -> ( E ) | id FIRST = {    'E': {'id', '('},    "E'": {'+', 'ε'},    'T': {'id', '('},    "T'": {'*', 'ε'},    'F': {'id', '('},} FOLLOW = {    'E': {')', '$'},    "E'": {')', '$'},    'T': {'+', ')', '$'},    "T'": {'+', ')', '$'},    'F': {'*', '+', ')', '$'},} TABLE = {    'E': {'id': ['T', "E'"], '(': ['T', "E'"]},    "E'": {'+': ['+', 'T', "E'"], ')': ['ε'], '$': ['ε']},    'T': {'id': ['F', "T'"], '(': ['F', "T'"]},    "T'": {'*': ['*', 'F', "T'"], '+': ['ε'], ')': ['ε'], '$': ['ε']},    'F': {'id': ['id'], '(': ['(', 'E', ')']},} def ll1_parse(tokens):    """用预测分析表检查 token 串是否被文法接受"""    tokens = list(tokens) + ['$']    stack = ['$', 'E']    print('栈'.ljust(16), '输入'.ljust(16), '动作')    print('-' * 54)    while stack:        top = stack[-1]        lookahead = tokens[0]        print(str(stack).ljust(16), str(tokens).ljust(16), end=' ')        if top == lookahead:            stack.pop()            tokens.pop(0)            print('匹配 ' + lookahead)        elif top in TABLE and lookahead in TABLE[top]:            stack.pop()            rule = TABLE[top][lookahead]            if rule != ['ε']:                stack.extend(reversed(rule))            print('展开 ' + top + ' -> ' + ' '.join(rule))        else:            print('语法错误！')            return False    print('分析成功！')    return True if __name__ == '__main__':    ll1_parse(['id', '+', 'id', '*', 'id'])
目的：完整演示 LL(1) 预测分析器的运行过程——给定 token 串，用预测分析表驱动栈，逐步输出“匹配”与“展开”动作。
  1. TABLE = {...}预测分析表是 LL(1) 的“剧本索引”：行是非终结符，列是终结符，格子里存放要展开的产生式。
  2. stack = ['$', 'E']分析栈初始装有“结束标记 + 开始符号”，模仿导演手里最初的剧本页。
  3. top = stack[-1]每次只看栈顶符号，这是 LL 分析的“一眼可断”决策点。
  4. if top == lookahead栈顶与当前 token 相同，说明台词与剧本一致，弹出并推进输入。
  5. rule = TABLE[top][lookahead]栈顶是非终结符时查表，找到唯一正确的展开方式。
  6. stack.extend(reversed(rule))把产生式右部逆序压栈，保证左端符号在栈顶先被处理。
  7. if rule != ['ε']ε 产生式代表“空戏”，只弹出非终结符，不压入任何新符号。
  8. print('展开 ' + top + ' -> ' + ...)输出推导过程，让你看清导演每一步翻的剧本页。

常见误区

误区很多人以为 LL 是“预测式”的，LR 是“回溯式”的，所以 LL 更快，是更先进的技术。实际刚好相反，LR 在编译原理课程里通常是更“高级”的内容。

正解两类分析器的时间复杂度都是 O(n)，严格线性扫描输入，性能差异微乎其微。就像导演和拼装师都能在相同时间内完成任务，区别不在速度，而在谁能处理更复杂的剧本。LR 表达力更强，能处理含左递归的自然文法；LL 需要改写文法，但错误定位更早。选型依据是表达力、错误提示和维护成本，而不是“快慢”。

为何常见：人们常把“自顶向下”与“递归”联想为简单直接，把复杂机制误判为慢速；且教学上常先讲 LL 后讲 LR，容易形成“后者更高级”的错误印象。

误区听说“左递归会导致死循环”，就以为 E→E+T 这种规则在任何解析器里都不可用，必须统统改写。

正解只有自顶向下的 LL 系解析器害怕左递归——导演按剧本推导，遇到 E→E+T 会无限钻下去。而 LR 系解析器天然支持左递归：拼装师是从输入往上游走，E+T 出现在栈顶时直接归约，毫无压力。所以 Yacc 里写 expr: expr '+' term 完全合法，这也是现实中 LR 更省心的原因之一。

为何常见：多数入门课程以 LL 开篇，递归下降的无限递归问题被反复强调，导致学 LR 时仍带着“左递归=万恶”的惯性思维。

误区以为只要按照算法算出 FIRST 集和 FOLLOW 集，预测分析表就自动完美，解析一定顺利。

正解FIRST/FOLLOW 只是构建表的原料。表建好后还必须逐格检查：同一格出现两个产生式说明有冲突；有些文法无论如何计算都不满足 LL(1) 条件，需要改造文法。好比场记表写得再全，剧本本身“一场戏两种演法”，导演照样卡壳。

为何常见：教材例题大多精心挑选了满足条件的文法，给人“按步骤算完就万事大吉”的错觉；实际工程中的文法几乎都要迭代调整。

误区看到 Bison 输出"shift/reduce conflict"警告就紧张，以为文法写错了，必须改到零警告为止。

正解Yacc 对冲突有默认策略——冲突时优先移进、按声明优先级处理，很多场景下默认行为正是你想要的。比如悬空 else 问题，Yacc 默认移进就实现了“就近匹配”语义。冲突警告是提醒你“这里存在多种解读”，需要确认默认选择是否符合语言设计意图，而不是一律视为错误。

为何常见：教学强调“冲突=LL(1) 失败”，但工程工具把冲突变成了可配置的语义选择，两种语境的目标不同，初学容易混淆。

面试题

Q1. LL 解析器属于哪一类语法分析方法？

单选题 · easy

  • A.自顶向下预测分析← 正确答案
  • B.自底向上移进归约
  • C.算符优先分析
  • D.通用 Chart 分析

答案：A。LL 从开始符号出发，按产生式逐步向下展开，直到匹配输入 token，本质是“导演照剧本排戏”，属于自顶向下预测分析。LR 才是自底向上移进归约。

Q2. LR 分析中的“移进”动作具体指什么？

单选题 · easy

  • A.把当前输入 token 压入分析栈← 正确答案
  • B.用产生式左部替换栈顶右部
  • C.展开栈顶的非终结符
  • D.从头重新扫描输入

答案：A。移进就是拼装师“拿起一个零件”——把输入符号压入栈中；归约才是“把零件拼成组件”，即用产生式左部替换右部。混淆两者是最常见的入门错误。

Q3. FIRST 集的定义是？

单选题 · mid

  • A.从某符号出发可能推导出的所有串的集合
  • B.从某符号出发可能推导出的串的首个终结符的集合← 正确答案
  • C.可能出现在某非终结符之后的终结符集合
  • D.所有产生式右部的符号集合

答案：B。FIRST 回答“这场戏第一句台词可能是什么”，即推导结果的首个终结符集合；FOLLOW 才回答“之后可能听到什么”。选项 A 范围太大，C 是 FOLLOW 的定义。

Q4. 文法 S → aS | b 是 LL(1) 文法吗？

单选题 · easy

  • A.是← 正确答案
  • B.否，因为含左递归
  • C.否，因为 FIRST 集相交
  • D.否，因为存在二义性

答案：A。这是右递归文法，两条产生式开头分别是 a 和 b，FIRST 集不相交，无左递归、无冲突，满足 LL(1) 条件。左递归才需要改写，右递归对 LL 完全友好。

Q5. LR 分析中“句柄”指的是？

单选题 · mid

  • A.当前输入串的最右终结符
  • B.栈顶能与某产生式右部匹配、且归约后形成规范句型的符号串← 正确答案
  • C.栈中任意一段符号串
  • D.语法树最左侧的叶子节点

答案：B。句柄是拼装师“认出的那一撮能拼成组件的零件”——它必须匹配某条产生式右部，并且归约方向符合最右推导的逆过程。任意符号串不算，最右终结符也不算。

Q6. Yacc 遇到移进-归约冲突时的默认处理策略是？

单选题 · mid

  • A.优先归约
  • B.优先移进← 正确答案
  • C.立即报错终止
  • D.随机选择一条路径

答案：B。Yacc 的默认策略是“移进优先”，这正好实现了悬空 else 的“就近匹配”语义。理解这个默认行为，才能正确解读 Bison 的冲突警告。

Q7. 下列哪些情况会导致 LL(1) 预测分析表出现冲突？

多选题 · mid

  • A.文法中存在左递归← 正确答案
  • B.同一非终结符的两条产生式 FIRST 集相交← 正确答案
  • C.某非终结符可推导出 ε，且其 FOLLOW 集与该产生式 FIRST 集有交集← 正确答案
  • D.产生式右部长度超过 10 个符号

答案：ABC。左递归会让 FIRST 集自相交；两条产生式右部以同一终结符开头，查表时同一格会有两个候选；ε 产生式则要求“FIRST 与 FOLLOW 不相交”，否则导演不知道是该展开还是该跳过。右部长度与冲突无关。

Q8. 关于 SLR 与 LR(1) 的关系，下列说法正确的是？

多选题 · hard

  • A.SLR 使用 FOLLOW 集来决定归约动作← 正确答案
  • B.LR(1) 通过向前看符号区分不同归约上下文← 正确答案
  • C.LALR(1) 合并了 LR(1) 中核心相同的项目集← 正确答案
  • D.LALR(1) 能解析所有 LR(1) 文法

答案：ABC。SLR 在归约时检查当前 token 是否在左部的 FOLLOW 集中；LR(1) 为每个项目携带更精确的向前看符号；LALR 合并同心项目集以压缩状态数。但合并会丢失部分上下文，故 LALR(1) 是 LR(1) 的真子集，D 错误。

Q9. 关于 LL 与 LR 表达能力的对比，正确的说法是？

多选题 · mid

  • A.LL(1) 文法集合包含于 LR(1) 文法集合← 正确答案
  • B.LR 解析器能直接处理左递归文法，LL 需要先改写← 正确答案
  • C.LL 解析器通常比 LR 更早发现语法错误← 正确答案
  • D.LR(1) 分析表通常比 LL(1) 预测表更小

答案：ABC。LL(1) ⊂ LALR(1) ⊂ LR(1)，A 正确；左递归对 LR 天然友好，B 正确；LL 边读边预测，遇到不匹配立即报错，C 正确；LR 表因状态多通常比 LL 预测表大得多，D 恰好相反。

Q10. LALR(1) 合并同心项目集时，会引入哪种新的冲突？

单选题 · extreme

  • A.移进-归约冲突
  • B.归约-归约冲突← 正确答案
  • C.同时引入两类冲突
  • D.不会引入任何冲突

答案：B。合并同心项目集后，不同上下文的归约项目可能聚到一起，若它们面对同一向前看符号却对应不同产生式，就产生归约-归约冲突；而移进-归约冲突在合并中不会出现，这是 LALR 的关键性质，也是它比 LR(1) 弱的原因。