编译之桥

词法分析器（Dragon Ch3）的任务：字符流→Token 流，同时剥离注释与空白、记录行列号供报错定位。Token 是二元组（种别码, 属性值）：种别码区分关键字/标识符/常量/运算符/界符，属性值携带具体信息（标识符在符号表中的入口指针）。台上 a+++b 的两种切法实锤了「最长匹配 / 最大 munch」规则：C 标准（C99 6.4¶4）规定词法元素取可能的最长字符序列，a+++b 因此切成 a ++ + b 而非 a + ++ b——切分发生在语法分析之前，语法器永远看不到另一种切法。S1 亲手烧出的信息丢失清单：注释不进 Token 流、空白全丢、格式信息归零——这正是「编译器不看缩进」的机制根源，而 Python 反其道行之，把缩进升级为 INDENT/DEDENT Token，词法层不丢反用。词法为何独立成阶段：①Token 结构平坦，正则语言足够表达（K18-03）；②一遍只做一件事，让编译器结构可控；③正则→DFA 有全自动构造算法，Lex/Flex 把这层完全机械化（K18-04）。反例也真实：C 里 typedef 名与普通标识符同形，分词要查符号表才能判定——词法与语义并非严格隔离，这是 C 编译器实现中最著名的脏角落，也提醒你：分层是工程纲领，不是物理定律。

正则表达式的数学地位（Dragon Ch3）：它与 NFA、DFA 三者等价。正则→NFA 走 Thompson 构造（Thompson 1968，CACM）：每个基本正则一个小 NFA 片段，连接/并/星用 ε 转移缝合——台上标识符 [a-zA-Z_][a-zA-Z0-9_]* 造出的 q0..q6，首字符并集分叉、星号部分 ε 进环、ε 出环，正是教科书原样。NFA→DFA 走子集构造：DFA 的一个状态 = NFA 的一个状态集合（ε-闭包），台上 {q1,q2} 经 ε-闭包坍缩成 {q1,q2,q3,q4,q6}（含接受态——所以单字符标识符 x 也接受），再读字符到 {q4,q5,q6} 自环到底。代价账：子集构造最坏指数爆炸——n 状态 NFA 理论上可产生 2ⁿ 个 DFA 状态，但词法模式的工程实例很少触发；DFA 换来的线性性值这个价：匹配时间只与输入长度有关，与模式复杂度无关，这是词法扫描能扛百万行源码的底座。天花板由泵引理（pumping lemma）钉死：正则语言无法计数——匹配任意深度嵌套括号需要「记住已见过几个左括号」，有限状态机的状态有限，数到某个深度必然循环复用；嵌套之墙撞的就是这堵墙。这条线同时划出了词法与语法的分工：Token 结构平坦归正则，程序结构嵌套归 CFG——工具的边界，定义了阶段的分工。

Lex（Lesk & Schmidt 1975，贝尔实验室 CSTR 39；Flex 是其开源重写）把词法分析器从手工代码变成声明式规格：写「正则模式 + 动作」对，工具自动完成 Thompson 构造＋子集构造＋DFA 表压缩，生成 yylex()。台上生成的那段就是 Flex 源码骨架：IDENTIFIER/NUMBER/运算符模式列 + return Token 动作列 + 空白/注释 skip。三个工程细节：①最长匹配在工具层实现——多条模式都命中时取最长者，等长时取声明序在前者，C 里 a+++b 的切法出处就在这里；②Flex 把全部模式合成一个 DFA（不是每模式一个），单遍扫描同时试所有模式，达到理论线性的实用形态；③yymore()/REJECT 等逃生舱提供规则之外的补丁接口——表达力不够时的最后手段。血亲谱系：Java 的 JFlex、Python 的 re（运行时把模式编译成内部自动机并缓存）、grep 系工具。生产率账：词法规格从「周级手写」缩到「小时级声明」——生成器模式的第一次胜利；代价是你必须用它的语言思考：正则之外的表达力，一寸都没有（嵌套之墙在 Flex 里同样撞得到），这正是下一层要交给语法分析器的东西。

语法分析器（Dragon Ch4）以 Token 流为输入、语法树为输出，依据是上下文无关文法。语法树 vs AST：语法树保留全部非终结符节点（E→T→F→id 的单链全在），AST 折叠单链只留运算符与操作数——台上 S2 那棵树标了「单链已折叠」，就是两者的分界演示；现代编译器（clang/LLVM、rustc）从词法后直接构 AST，纯语法树只活在教科书与考卷里。分析的两条路线：自顶向下（从 E 开始按产生式展开，分叉处向前看 1 个 Token 决策——递归下降/LL(1)）与自底向上（从 id 开始归约成 F、T、E——LR）。复杂度账：通用 CFG 分析 O(n³)（CYK/Earley），而 LL(1)/LR(1) 都是线性 O(n)——代价是只接受文法的一个可判定子集。工程现实：手写递归下降在 GCC/Clang/V8 里全面回归，赢在错误恢复可控、可为表达式优先级写直觉代码；生成器路线（Bison）在语法稳定的领域（SQL、配置语言）仍是标配。左递归是自顶向下的死穴：E→E+T 让递归下降无限展开——S2 左递归按钮的「栈溢出」警告是真的；标准消左递归变换 E→T E'、E'→+TE'|ε 能解，但树形随之改变——文法改写本身也是一次语义形状的变换，这层代价台上「树形也改了」那行字替你记下了。

CFG 四元组 G=(终结符集 V_T, 非终结符集 V_N, 产生式集 P, 开始符号 S)；推导即从 S 反复应用产生式，最左/最右推导对应自顶向下/自底向上两个分析方向。二义性定义：存在一个句子拥有两棵不同语法树（等价地：两个不同的最左推导）。台上 dangling-else——if(a) if(b) x=1; else x=2; 的 else 挂外层还是内层，两棵树都合法。C 标准的裁决是「else 属于最近的尚未配对的 if」——不是语义推理，是标准文本里的约定条款；你写的缩进在词法层已被吞掉（S1 的丢失清单），编译器根本没见过。三条消歧路线：①改文法——引入 matched/unmatched 语句非终结符，把「配对 if」与「悬空 if」拆成两类产生式（Dragon Ch4.3 的正规做法）；②优先级/结合性声明——给冲突双方声明优先级与结合性（Yacc 的 %left/%right/%nonassoc，同法可给 if/else 显式声明以消解悬空 else）；③默认移进——Bison 对 shift/reduce 冲突默认移进，恰好等价于最近匹配。根本坏消息：二义性不可判定——不存在算法判定任意 CFG 是否二义（Chomsky 层次里的经典不可判定结果），所以工程只能「事前限制文法类」或「事后消解冲突」。顺带拆解台上表达式文法的形状密码：E→E+T|T、T→T*F|F 用分层产生式天然编码优先级（* 在更深的层先结合），用左递归编码左结合——文法的形状，就是语义的形状。

递归下降：每个非终结符一个函数，函数体按产生式右部依次处理——E() 先调 T()，再视下一 Token 决定是否进入 E' 循环。它是手写编译器的默认选择（Clang 的 Parser、V8、rustc 都是），可读性与错误恢复能力无人能敌。LL(1) 的含义：从左到右扫描、最左推导、向前看 1 个符号；可行性由 FIRST/FOLLOW 集判定——FIRST(X)=X 能推出的首个终结符集合，FOLLOW(X)=X 之后可能紧跟的终结符集合；文法是 LL(1) 的当且仅当分叉处各候选的 FIRST 互不相交，且候选可推 ε 时其 FIRST 与 FOLLOW 也不相交。台上消左递归后的表达式文法恰好满足：E 行在 id/( 两列都填 E→TE'，T' 在 +/)/$ 三列填 T'→ε、* 列填 T'→*FT'——预测分析表无多重定义格，这正是「每格至多一条」的机器可验证形态。两张死穴：左递归（FIRST 循环依赖，台上「LL(1) 冲突」按钮打出的就是这张牌）与公共前缀（if 语句两个分支都以 'if' 开头，需提左公因子 if-stmt→if ( E ) stmt matched-tail）。能力上限：LL(1) 是 LL(k) 家族最小的一个，LL(2) 多看一个符号可解部分冲突但表指数膨胀——工程上宁可改文法也不升 k。递归下降＋回溯＝朴素自顶向下，最坏指数时间；「永不回头」才是 LL 线性的前提，也是它与 LR 各领半壁的资本。

LR 分析：从左到右扫描、构造最右推导的逆；核心数据结构是 LR 项（带 · 的产生式）与项集自动机。规范 LR(0) 构造：closure＋goto 迭代到不动点——台上表达式文法（E→E+T|T; T→T*F|F; F→(E)|id）造出 I0..I11 共 12 个状态，Dragon Ch4 的经典数字。冲突两型：shift/reduce（I2 与 I9：T→T·*F 要移进 *，E→T·/E→E+T· 要归约）与 reduce/reduce。三档消解：①SLR(1)（DeRemer 1971）：仅当下一 Token ∈ FOLLOW(产生式左部) 才归约——本 LR 文法 FOLLOW(E)={+,$,)}，* ∉ FOLLOW(E)，I2 冲突消解；②LALR(1)：规范 LR(1) 项给每个项配前瞻符，同芯（相同 LR(0) 项目集）状态合并——状态数退回与 LR(0)/SLR(1) 相同（12 个），能力介于两者之间；③规范 LR(1)：每个「项×前瞻符」独立成状态，最强（覆盖几乎所有无二义 CFG）但状态数可能剧烈膨胀。能力排序 LR(1)>LALR(1)>SLR(1)>LR(0)，状态数同向增长——这是表达力与状态数的单向阶梯。LR 为什么赢：左递归天然友好（无需改文法，且左递归恰好对应左结合语义），实用语言文法几乎全部落在其射程内；Yacc/Bison、PostgreSQL 的 SQL 前端内核至今是 LALR(1) 变体。

Yacc（Yet Another Compiler-Compiler，Johnson 1975，贝尔实验室 CSTR 32；Bison 为 GNU 重写）与 Lex 配成经典工具链：lex 产 yylex()，yacc 产 yyparse()，约定 yylex() 返回 Token 种别码、yylval 携带属性。Yacc 读入文法→构造 LALR(1) 自动机→冲突按声明裁决：%left/%right/%nonassoc 声明结合性与优先级（后声明者优先级高——%left '+' 写在 %left '*' 之前，即 * 优先）；%prec 手动指定某产生式优先级；shift/reduce 冲突默认移进——「else 绑定最近 if」的出处就在这条默认规则。台上生成骨架里「默认移进 = else 绑定最近的 if」那行注释正是 dangling-else 的消解现场。工程地雷三枚：①冲突静默——Bison 默认只打 warning 照常生成，规范项目必须用 %expect 精确声明冲突数（GCC 的语法文件就这么干）；②错误恢复——error 伪 Token 让分析器在语法错误后跳到同步点继续，这是编译器「一次报多个错」的机制；③路线分野——生成器赢在文法即文档、改动即重生成（PostgreSQL 至今用 Bison），手写递归下降赢在错误信息质量与可调试性（Clang），GLR 模式（并行探索所有冲突分支）则留给歧义文法与自然语言场景。「else 绑定最近 if」不是语义决定，是你在 Yacc 声明段里写出来的约定——这句台上顿悟的工程注脚。