Sherfiter's wiki for fun

第 4 章 · 自底向上语法分析:LR

LR 是语法分析的重型武器:能力覆盖所有确定性的上下文无关文法(LL(1) 是它的真子集),不用改写左递归,而且解析器的生成器(yacc/bison)全基于它。代价是实现复杂:手工写 LR 几乎没人干,都是「文法进、分析表出」由工具生成。本章讲清 LR 的运行机制(移进-归约、状态栈)、构造思想(LR 项与项集族)、以及和 LL 的取舍,最后用 bison 实战一段。

4.1 移进-归约:从底部把树搭起来

LR 从左到右扫描(L),自右向左构造最右推导的反向(R)。运行时维护一个状态栈,两个动作:

  • 移进(shift):把当前 token 压栈;
  • 归约(reduce):栈顶的若干符号匹配某条产生式右部,弹出它们,压入左部非终结符(相当于「完成了一个子树」)。

用文法 S → E,E → E+E | NUM 解析 1+2+3:

栈               输入        动作
$                1+2+3 $     移进 NUM(1)
$ NUM            +2+3 $      E → NUM,归约
$ E              +2+3 $      移进 +
$ E +            2+3 $       移进 NUM(2)
$ E + E          +3 $        E → E+E,归约    ← 3 变成 5(如果带求值)
$ E              +3 $        移进 +,移进 NUM(3)
$ E + E          $           E → E+E,归约    ← 8
$ E              $           S → E,归约,接受!

观察归约顺序:1+2+3 先归约的是最右边的 2+3?不对,是最先能归约的(左边的 1+2 先归),配合栈的顺序恰好实现左结合——这是 LR 天然处理左递归的原因:左递归文法在 LL 里是死穴,在 LR 里只是普通的移进归约循环。

4.2 LR 项与项集族:表是怎么算出来的

「什么时候移进、什么时候归约」由一张分析表决定,表由 LR 项(item) 的自动机构造。项 = 「产生式加一个进度点」:E → E · + E 表示「已见 E,期待 +E」。

把所有项按「从初态可达」闭包成项集(状态),项集之间的转移构成 DFA(这一步的算法叫 LR(0) 构造,SLR/LR(1)/LALR 是在它的基础上加不同精度的「向前看」信息来消冲突):

状态 0:E → · E      状态 1:E → E ·      状态 2:E → · E+E ...
       E → · E+E            E → E·+E(遇 + 移进到状态 3)
       E → · NUM
遇 NUM → 状态 4

构造完成的 DFA 转成两张表:ACTION 表(状态 × 终结符 → 移进/归约/接受)和 GOTO 表(状态 × 非终结符 → 状态)。冲突发生在某格被填了两个动作:移进-归约冲突(比如悬空 else)和归约-归约冲突。消解手段按工具:yacc 默认「移进优先于归约」「早出现的产生式优先」,再给你优先级声明(%left +%right *)手动解决。表生成是纯机械过程,工具全包;你要懂的是冲突出现时怎么读 bison 的报错(yyconflicts、状态几号、哪两条产生式打架),这是工程上的真功夫。

4.3 三兄弟:SLR / LALR / LR(1)

变体向前看信息表大小能力
LR(0)不看最小太弱,教学用
SLR(1)用 FOLLOW 集小中等
LALR(1)合并同心项集与 SLR 相同yacc/bison 的选择,工业标配
LR(1)每项精确看 1大最强,Elr 等新工具用

LALR 的聪明处:LR(1) 的状态里有很多「只在向前看符号上不同」的项集,合并它们(丢弃向前看差异)表小了一个数量级,代价是可能引入少量归约-归约冲突。考试三兄弟的构造和比较是高频题;工程记 bison 就是 LALR(1)。

4.4 实战:bison 版计算器

.y 文件 = 文法 + 语义动作(第 5 章的语法制导翻译直接内置):

%{
#include <stdio.h>
int yylex(void);
void yyerror(const char *s);
%}
%define api.value.type {int}
%left '+' '-'
%left '*' '/'
%%
line:   /* 空 */
      | line expr '\n'   { printf("= %d\n", $2); }
      ;
expr:   NUM              { $$ = $1; }
      | expr '+' expr    { $$ = $1 + $3; }
      | expr '*' expr    { $$ = $1 * $3; }
      | '(' expr ')'     { $$ = $2; }
      ;
%%
void yyerror(const char *s) { fprintf(stderr, "error: %s\n", s); }
int main(void) { return yyparse(); }

%left 声明解决优先级与结合性(2、2、3 取栈上符号的语义值),词法部分配一个 flex 的 .l 文件(第 2 章),bison -d calc.y && flex calc.l && gcc 一套组合跑起来。这个 30 行的计算器是第 10 章迷你编译器的骨架:把语义动作从「求值」换成「生成 IR」,它就升级成编译器。

4.5 LR 与 LL 怎么选

LL(递归下降)LR(bison)
左递归必须改写直接支持
手写难度低(文法即代码)高(没人手写)
错误信息容易做好默认较烂(报 unexpected token)
工具链ANTLRyacc/bison
现代倾向手写递归下降成主流(clang、rustc、go)数据格式、老牌语言(gcc 旧版)

行业现实:新编译器倾向手写递归下降(错误信息、性能、可调试性都更好),LR 的天下在解析器生成器和 DSL。理解 LR 依然必要:面试、读老代码、以及理解「歧义检测」「冲突」这些概念的最佳教材。

常见错误

  • 手工推 LR(0) 项集漏了闭包。状态里必须加入「点后是非终结符 → 该非终结符的所有产生式加点」。
  • 归约时忘了弹栈数量。产生式右部有 k 个符号,归约弹 k 个压 1 个,数错了整棵树塌。
  • bison 冲突不管。yyconflicts 输出被忽略,解析结果「看起来对、偶尔错」;每次改文法都盯着 conflict 报告。
  • 语义值类型设错。api.value.type 是 int 就存不了字符串;要用 %union(多类型),代价是类型安全靠自觉。

练习

  1. 手算:对文法 E → E+T | T, T → T*F | F, F → (E) | id,手工构造 LR(0) 项集族(第 0、1、2 状态即可)和 SLR 分析表,再模拟解析 id*id+id 的移进归约全过程。
  2. 动手:跑通 4.4 的 bison 计算器(配 flex 词法),加入 -、/、一元负号(提示:一元负号是典型的移进-归约冲突现场,用优先级声明解决)。
  3. 动手:故意制造冲突:把文法里的 '*' 优先级声明删掉,看 bison 报几个 shift/reduce 冲突,推理 2+3*4 会算成什么。
  4. 思考:LR 的移进-归约栈和递归下降的调用栈,本质都在「记住未完成的上下文」。对比两者的栈内容(状态 vs 函数帧),想想为什么手写递归下降的错误信息更好做(栈上的信息是代码,可读),而表驱动 LR 的错误信息难做(栈上是数字)。
豫ICP备2026027944号