1 LR解析概述

LR解析（LR Parsing）是一类用于语法分析器构造的系统化方法，常见于编译器前端。其基本任务是：将给定的上下文无关文法（CFG）与输入串配合，通过一个由自动机状态和分析表共同驱动的“动作序列”，决定输入串在语法上的结构，并最终得到可用于后续阶段的表示（例如语法树）。

LR解析的典型工作方式可以概括为：从左到右读取输入符号，同时在分析过程中不断执行移进（shift）或归约（reduce）操作；其中“归约”的方向与推导思想相对应，整体可被理解为对最右推导的逆过程。该机制让解析过程具有可判定性：只要分析表与当前状态、当前看见的输入符号确定，就能唯一选择动作（若选择唯一）。

1.1 基本思想：从左到右与“最右归约”

LR解析通过维护一个“状态栈”和“符号栈”（或等价结构），把已处理的前缀对应到某个自动机状态。每一步都查看当前状态与前瞻输入符号（lookahead）来决定动作：

  • 移进（shift）：把当前输入符号移到符号栈，并相应推进状态。
  • 归约（reduce）：根据文法产生式，用产生式右部长度从栈中弹出相应符号，再把产生式左部压回栈，同时根据“归约后状态转移”推进。

“最右归约”的直观来源在于：归约实际上是在把先前移入并形成的右部片段，反向解释为某个非终结符的归约结果，从而逐步重建整体语法结构。

1.2 与其它语法分析方法的关系

LR解析与自顶向下分析（如递归下降、LL解析）一样，都是把文法“转译”为可执行的解析策略。差异主要体现在能力与约束条件上：

  • 自顶向下方法通常依赖前瞻符来预测产生式选择，若文法难以预测则会遇到冲突。
  • LR解析以“状态机 + 分析表”为核心，允许通过更精确的栈信息与前瞻符组合，决定移进或归约，从而覆盖更广的文法类。

与自底向上的思想（shift-reduce）也存在直接关联：LR解析本质上就是一种可构造、可判定的 shift-reduce 解析框架。

1.3 适用的语法类型与边界（上下文无关文法）

LR解析主要面向上下文无关文法（CFG）解析问题。其分类（如LR(0)、SLR、LR(1)、LALR(1)）通过限制与增强分析表构造时的判断精度，来控制：

  • 可处理的文法范围（能否找到无冲突的分析表）。
  • 解析表规模与构造成本（项目集越细致，表越大）。
  • 冲突能否被消解或避免。

若文法本身不满足某一变体所要求的无冲突条件，就可能需要更强的变体，或对文法进行等价改写（例如消除左递归、提取公共前缀等）。

2 文法与形式化基础

为了讨论LR解析的构造与运行，需要先统一CFG、推导、产生式与语法树等基本概念。LR解析的核心对象是产生式及其在解析过程中对应的归约模式，因此形式化边界越清晰，后续的项目集与分析表构造越不易混乱。

2.1 上下文无关文法（CFG）回顾

CFG由一组终结符、非终结符、产生式集合以及开始符号构成。产生式的形式通常为：

CFG的关键性质是：替换发生在句型的局部，但替换规则的适用性与上下文无关（即只依赖当前要替换的非终结符）。

2.2 推导、句型与语法树

  • 推导（derivation）：从开始符号出发，反复应用产生式得到新的句型，直到得到只含终结符的串。
  • 句型（sentential form）：在推导过程中出现的符号串，可能含非终结符。
  • 语法树（parse tree）：推导结果的一种结构化表示，体现每次产生式选择及其嵌套关系。

LR解析的归约动作，实质上就是在构造语法树的片段：当某个栈顶符号序列匹配某个产生式右部时，就把它归约成右部对应的非终结符。

2.3 终结符、非终结符与产生式表示

终结符是最终出现在输入串中的符号（或词法分析后得到的token种类），非终结符用于描述语法结构。产生式可以看作“语法的构造模板”，例如：

  • E → E + T
  • E → T

在LR项目与分析表中，产生式右部长度决定归约时从栈弹出的符号数量；产生式左部决定归约后压入的非终结符，从而驱动后续的goto转移。

2.4 可接受输入与接受条件

LR解析通过“接受（accept）”动作来判定解析成功。典型机制是：当分析栈处于某个表示开始符整体推导完成的状态，且当前输入符号达到结束标记时，ACTION表触发接受动作。若解析过程中表要求某类动作但文法与输入导致冲突或找不到动作，则属于语法错误或需要进入错误恢复流程。

3 LR项目（Items）与项目集

LR项目（items）是把“产生式 + 圆点位置（dot）+（可选）展望符”组合起来的形式单元。项目的意义在于描述：在某个状态下，解析器已经识别了产生式右部的前缀，并且接下来要识别的位置在哪里。项目集则是多个项目的集合，用于刻画自动机的状态内容。

3.1 LR(0)项目的定义

LR(0)项目通常写作：

  • A → α · β

其中：

  • A → αβ 是产生式；
  • · 表示“已识别部分”和“待识别部分”的分界；
  • α是已经匹配到的右部前缀，β是尚未完成的剩余部分。

LR(0)项目不引入展望符，意味着在进行归约决策时信息更少，因而更容易出现冲突或需要更强限制才能保持无冲突。

3.2 带展望符的LR(1)项目

LR(1)项目在LR(0)项目基础上增加一个展望符（lookahead）a，写作：

  • [A → α · β, a]

展望符a表示：当某个项目处于可归约位置时，归约所依赖的当前输入符号类型应该是a。由于归约条件更精确，LR(1)通常比LR(0)/SLR更能避免不必要的归约，从而提高可解析范围。

3.3 closure（闭包）与 goto（转移）

  • closure（闭包）：给定一个项目集I，把所有因“圆点后出现非终结符”而必然需要考虑的项目补全进去。直观上，它表示：在当前状态下，解析器可能马上要展开那些非终结符的产生式。
  • goto（转移）：对项目集I和符号X，计算在圆点前进到X之后得到的新项目集，记作goto(I, X)。

这两步共同构成LR自动机的状态扩展逻辑。项目集的精确定义使得构造过程可机械化：状态之间的迁移由goto决定，而状态内部通过closure补齐。

3.4 项目集规范族（canonical collection）

对初始项目集进行closure，再不断应用goto扩展所有可达状态，就得到自动机的“规范族”（canonical collection）。每个项目集对应一个状态，状态之间由goto带来的迁移边连接。

规范族通常用于构造分析表：ACTION表与GOTO表中的各项由状态的项目结构及其展望符（若存在）决定。

4 分析自动机与分析表

LR解析器在运行时不直接“重新计算项目集”，而是依赖预先构造好的分析表。分析表把自动机状态与动作规则映射起来，使得解析过程可以在时间上保持线性级别的输入扫描（在典型实现条件下）。

4.1 状态含义与转移构造

每个状态对应一个项目集，项目集刻画了“在该状态下，解析器已识别到哪些产生式右部位置”。当输入符号推进时，解析器根据当前状态与符号查表，决定是：

  • 进入某个新状态（移进或goto）
  • 执行归约并重新查表
  • 或宣布接受

因此，状态的意义不仅是编号，更是项目集合所蕴含的上下文信息。

4.2 ACTION表：移进、归约与接受

ACTION表的行是状态，列是终结符（或结束符号），单元格存放动作，常见动作包括：

  • shift s：把当前输入符号移入并转到状态s
  • reduce A → γ：当栈顶与γ对应且展望符匹配时执行归约
  • accept：当遇到结束标记且满足开始符整体完成条件

ACTION表中“归约使用哪条产生式、归约在何时触发”由项目集内的项目以及展望符规则决定。

4.3 GOTO表：非终结符转移

GOTO表同样以状态为行，但列是非终结符。它用于归约之后：当把产生式左部A压回栈后，需要根据当前状态与A确定下一状态。这样，归约不会只停留在语义层面，而是能继续推动自动机沿正确路径前进。

4.4 分析栈与符号栈的协作机制

典型实现维护两类结构：

  • 符号栈：保存已归约/已移入的语法符号序列。
  • 状态栈：保存对应符号栈各前缀的自动机状态编号。

归约时先根据产生式右部长度弹出相应数量的符号与状态；然后将左部符号压栈，并根据弹出后栈顶状态查询GOTO表得到新状态，再压入状态栈。该协作保证了每一步决策都能由“局部表查询”完成。

4.5 冲突：移进-归约与归约-归约

在分析表构造过程中，可能出现同一状态同一输入条件下存在多种动作要求，即“冲突”。两类常见冲突：

  • 移进-归约冲突：对某个终结符既要求shift又要求reduce。
  • 归约-归约冲突：同一条件下需要执行两条不同的reduce。

不同LR变体通过更细粒度的展望符或状态合并策略，降低冲突或提高消解能力，但无法保证所有CFG都能变成某一变体的无冲突形式。

5 LR变体：能力与代价

LR解析的分类本质上是：在构造项目集与确定归约触发条件时，采用不同的精确度与压缩策略。精确度越高，通常可解析的文法范围越大，但项目集规模与分析表成本也越高。

5.1 SLR：用FOLLOW集合消解部分冲突

SLR（Simple LR）使用LR(0)项目作为基础结构，但归约决策依赖FOLLOW集合（对非终结符的合法后继终结符集合）。直观上，它把归约触发条件从“精确展望符”简化为“可能跟在该非终结符后面的符号范围”，因此成本较低，但精确度不足会导致某些本可区分的场景仍产生冲突。

5.2 LR(1)：精确展望符，语法能力更强

LR(1)为归约保留精确的展望符信息。由于归约只在项目所指向的特定展望符出现时才发生，冲突减少的往往更多，从而使得LR(1)能够覆盖比SLR更广的文法类。不过，其项目集规模通常也更大，构造和表的规模代价更高。

5.3 LALR(1)：合并LR(1)状态以压缩规模

LALR(1)可以视为一种折中：先以LR(1)的思想构造较精细的信息，再通过合并具有相同核心结构（常称为core）的状态来压缩项目集规模。合并会带来潜在新冲突的风险，因此LALR(1)可解析范围通常介于SLR与LR(1)之间，但在工程上更常见。

5.4 LR(0)：概念简洁但表达能力有限

LR(0)不使用展望符信息，也就是说归约触发不区分“当前该看哪类后继符号”。这让实现概念更简单，但冲突更容易出现，因而适用的文法范围有限。在某些情况下，只有对文法进行改写才能落到无冲突的LR(0)形式。

5.5 变体比较：表规模、可解析范围与冲突概率

总体趋势可概括为：

  • 表规模：LR(0)与SLR通常较小，LR(1)最大，LALR(1)在两者之间。
  • 可解析范围：LR(1)通常最强，其次LALR(1)，再到SLR，LR(0)通常最弱。
  • 冲突概率：展望符越精确，冲突越少；但即使更强变体仍可能遇到文法固有冲突结构。

在工程选择上，常按“性能预算与文法来源可靠性”来取舍：手写小文法偏简单时可用较轻量变体；复杂语言语法通常选择更强或经过改写后的文法配套方案。

6 分析过程（运行时行为）

运行时的LR解析可以被看作：在输入流上进行一次“以表为准绳”的驱动式过程。解析的每一步都由ACTION表与GOTO表决定，不依赖回溯式重试。

6.1 初始化与输入指针管理

初始化通常包括：

  • 状态栈压入初始状态（对应项目集规范族的起点）。
  • 符号栈为空或按约定预置。
  • 输入指针指向当前要处理的符号。
  • 输入末尾使用结束标记（常称$）以触发接受条件。

每一步操作可能移动输入指针（shift）或不移动（reduce/accept），从而保证整体仍能向前推进。

6.2 移进（shift）动作细节

当ACTION表给出shift s时，解析器把当前输入符号压入符号栈，并把状态s压入状态栈，然后把输入指针向前推进到下一个符号。由于移进不会引入归约歧义，它承担了“读入并建立局部结构”的职责。

6.3 归约（reduce）动作与产生式应用

当ACTION表要求reduce A → γ时，解析器会：

  1. 从符号栈弹出与γ右部长度相同的符号。
  2. （在需要构造语法树时）将这些符号作为孩子挂到新节点A下。
  3. 把A压回符号栈。
  4. 由于归约后状态取决于栈顶历史信息，通过GOTO表确定下一状态并压栈。

归约不推进输入指针，因此可以在同一输入符号前进行多次归约，直到ACTION表给出shift或accept为止。

6.4 归约后的栈更新与goto跳转

归约后需要重新确定自动机状态：具体做法是查“当前状态栈栈顶状态 + 归约得到的非终结符A”的GOTO表入口，将其作为新状态压入栈。这个步骤把“语法构造完成的局部结果”与“更大范围的上下文”连接起来。

6.5 接受（accept）与错误处理框架

accept通常在ACTION表触发时发生：此时开始符整体完成且输入结束标记已匹配。若出现ACTION表中不存在所需动作，解析器通常判定为语法错误。

错误恢复的具体策略因实现而异，例如基于同步符号的跳过、局部插入/删除的代价估计等。就概念而言，错误恢复需要在不中断整体解析框架的前提下，引导状态机重新找到“可继续”的位置。

7 构造分析表的算法要点

构造分析表的过程可以抽象为：从文法生成项目集规范族，然后根据项目集内容填充ACTION与GOTO表；若出现冲突则进行记录或判定文法不满足该变体条件。以下按关键步骤概括其要点。

7.1 生成项目集并确定状态编号

构造流程通常从初始项目集开始：

  • 将开始产生式扩展成带新开始符的形式（并引入结束标记相关条件）。
  • 对初始项目集执行closure得到起始状态。
  • 对每个已发现状态，考虑所有可能的符号X，计算goto并得到新项目集；若该项目集未出现过则新增状态编号。
  • 重复直到所有可达状态都生成。

状态编号服务于表格填充与运行时查询。

7.2 计算展望符与FOLLOW（适用于SLR）

在SLR中，归约动作触发条件由FOLLOW集合提供。构造时对每个归约项目（圆点在产生式右部末尾），把对应reduce动作写入ACTION表中所有与FOLLOW相关的终结符列。这样就能把“可能的后继符号”统一用FOLLOW集合覆盖。

7.3 LR(1)的展望符传播思路（概念层面）

LR(1)的展望符更精细：在closure展开时，需要根据语法结构与既有展望符组合，计算新生成项目的展望符。概念上可理解为：展望符来自于“圆点后符号能够推导出哪些终结符，并且这些终结符与当前项目展望的关联方式”。该传播使得每条归约规则带着更明确的触发条件，从而减少错误归约。

7.4 冲突检测与记录机制

当填充ACTION表时，如果同一单元格试图写入两种不同动作（例如已有shift又要写reduce），就标记为冲突。工程实现通常会：

  • 立即判定该变体下文法不可构造无冲突表。
  • 或记录冲突来源状态与涉及产生式，便于后续分析与改写文法。

在开发中，对冲突的可视化非常重要，因为它往往与文法的歧义或结构难以区分有关。

7.5 无冲突条件与文法性质的判定

无冲突的判断依赖具体变体的构造规则。若对所有状态、所有输入符号都能保证ACTION表唯一，就称该文法在该变体下可被解析（即存在LR分析表）。若出现冲突，则该文法不满足该变体所需的性质，通常需要：

  • 换用更强的变体（如从SLR升级到LR(1)或LALR(1)）
  • 或对CFG进行等价改写，使其更适合shift-reduce解析。

8 实际应用与实现建议

LR解析主要用于编译器中语法分析阶段。尽管理论部分复杂，但落到工程实现时有较成熟的流程：文法输入、表构造、表优化、解析执行与诊断反馈。

8.1 编译器前端中的语法分析角色

在典型编译器流水线中，词法分析把原始文本转换成token流；语法分析器把token流与CFG匹配，形成语法结构，供后续语义分析与中间代码生成使用。LR解析作为一种自底向上的分析框架，常被用在希望避免回溯、并获得较强语法覆盖的场景。

8.2 与词法分析（tokenization）的接口

LR解析器通常只关心token种类及其属性（如标识符名称或数值）。因此接口层需要：

  • 提供当前token的类别映射到终结符符号。
  • 提供结束标记token以触发accept或错误处理。
  • 在需要时将语义值（语义动作对应的数据）随符号栈一起传递，以支持语法树或中间表示的构建。

8.3 构建与生成表的工程流程

常见工程流程：

  1. 定义或读取CFG（包含产生式列表）。
  2. 选择LR变体并执行项目集构造。
  3. 生成ACTION与GOTO表。
  4. 可选：对表进行压缩（如稀疏表存储、合并相同行等）。
  5. 在编译时或构建阶段生成可执行用的数据结构，运行时仅加载并驱动解析。

对于大型语言语法，提前生成并持久化表是常见做法。

8.4 性能考量：表压缩与缓存

LR解析运行时查询主要是“查表 + 栈操作”，整体性能良好。但表过大时会导致缓存不友好。常用优化包括：

  • 使用稀疏表示减少空单元格存储。
  • 对ACTION/GOTO表按状态连续布局以提升局部性。
  • 合并或压缩表项（例如采用紧凑编码存动作）。

选择LALR(1)往往也正是出于在可解析能力与表规模之间取得平衡。

8.5 诊断与错误恢复策略（概念性讨论）

当解析失败时，诊断信息常依赖“当前状态、期望的终结符集合、以及出错位置附近的token”。错误恢复一般要尽可能保持解析继续进行，以便一次输出多处错误。概念上常用做法是利用同步符号集合，在错误出现后跳过部分输入或进行局部调整，直到状态机能继续接受。

9 常见问题与“梗”式理解

LR解析常被初学者“卡住”的原因并不是数学困难，而是直觉与符号系统之间的断层。下面以更直觉、带一点梗味的方式解释常见疑惑，同时保持概念正确。

9.1 为什么会有冲突：直觉版解释

把每个状态想成一个“裁判”。裁判看当前栈的状态信息，又看当前输入符号，然后宣布“该移进还是该归约”。冲突就像裁判同时收到了两条不同判决：同一时刻它既想把符号读进来（shift），又想把栈顶结构拼回去（reduce）。更强的LR变体通过更精细的展望符，让裁判不再“看错时间”。

9.2 “归约时机”为什么重要

归约发生在圆点落到产生式右部末尾的情形。归约时机决定了语法树结构的边界：归约早了可能把本应属于更大结构的部分“提前封装”；归约晚了则可能导致需要的组合无法在当前状态中完成。换句话说，归约时机是“结构拼图装盒的时刻”，早一步或晚一步，拼图就可能对不上。

9.3 移进/归约的性格冲突：把它当成状态机争吵

在运行时，shift更像“把证据记进本子”，reduce更像“把证据归类总结”。当分析表里同一格出现争吵，说明文法结构让“证据归类与证据补齐”难以在当前信息粒度下区分。你可以把它理解为：状态机在当前场景下拿到的信息不够，导致两种操作都显得合理。

9.4 调试分析表：看懂状态与项目（实操提示）

调试时通常从以下路径入手：

  • 找到冲突发生的状态编号，查看该状态对应的项目集。
  • 对比涉及冲突的终结符列：ACTION表为什么同时出现shift与reduce（或两个reduce）。
  • 检查涉及的产生式与圆点位置：判断哪些右部片段被视为“可归约”。
  • 若使用SLR，重点检查FOLLOW是否过宽导致误归约；若用LR(1)/LALR(1)，检查展望符传播或状态合并带来的影响。

通过“项目集—动作—冲突单元格”的链路定位，通常能把问题从“看不懂表”转为“看懂为什么会争吵”。