4.3 文法变换、左递归与左因子

最适合表达语言定义的文法，不一定能被某种语法分析器直接消费。因此编译器工程中经常使用文法变换：在保持语言、预期树结构或两者的前提下，重写产生式。

这不是纯粹的排版工作。粗心的改写可能改变结合性，意外加入或移除空串，让错误消息变差，或者把语义动作放到错误的位置。每次变换都应该当成一个证明义务：先写清楚哪些语言行为必须保留，再用代表性输入做回归测试。

在预测式、自顶向下分析中，有两种特别常见的变换：

• 消除左递归。

• 提取左因子。

它们帮助语法分析器（parser）利用有限向前看（lookahead）做决定，但不会自动把任意 CFG 变成 LL(1)，也不是所有语法分析器架构都必须采用的做法。

直接左递归与间接左递归

如果一个非终结符能立刻推导出一个以自身开头的句型，就叫直接左递归：

E -> E + T | T

对于递归下降函数，E -> E + T 会让 parseE() 在尚未消费词法单元（token）时再次调用 parseE()：

parseE()
  -> parseE()
      -> parseE()
          -> ...

标准的直接左递归消除模式为：

A -> A α1 | A α2 | ... | β1 | β2 | ...

其中每个 β 都不以 A 开头。变换后：

A  -> β1 A' | β2 A' | ...
A' -> α1 A' | α2 A' | ... | ε

对于加法：

E -> E + T | T

可改写为：

E  -> T E'
E' -> + T E' | ε

新文法先识别一个 T，再重复零次或多次 + T 尾部。它仍然描述“一项后面接任意多个加项”的同一种字符串形状。

别在变换时丢失结合性

变换后的 E' 看上去是右递归的。如果 AST 构造写得天真，就可能把：

a - b - c

构造成：

a - (b - c)

但语言可能要求：

(a - b) - c

因此语法分析器实现通常在读取第一个操作数后用循环折叠尾部：

left = parseTerm()
while next token is "+":
  consume "+"
  right = parseTerm()
  left = Add(left, right)
return left

文法负责识别词法单元结构；AST 构造策略负责保留语义上的结合方向。两者必须一起测试。

间接左递归不那么显眼：

A -> B α
B -> A β | γ

因为 A => B α => A β α，所以 A 仍然可以经过多步回到以自身开头。通用算法会按顺序处理非终结符，把较早的产生式代入较晚的产生式，再消除形成的直接左递归。该过程可能显著膨胀文法，因此必须搭配测试、错误恢复策略和 AST 设计谨慎使用。

左因子把决定推迟到向前看真正有用时

考虑：

Stmt -> if Expr then Stmt else Stmt
      | if Expr then Stmt
      | while Expr do Stmt

语法分析器在语句开始读到 if 时，还无法区分前两条产生式，因为它们有相同前缀。左因子提取把公共前缀抽出来：

Stmt     -> if Expr then Stmt StmtTail
          | while Expr do Stmt
StmtTail -> else Stmt | ε

现在语法分析器先把公共前缀读完，只有在嵌套语句结束后，才根据是否看到 else 决定尾部。这正是一个词法单元向前看开始有信息量的时刻。

一般形式：

A -> α β1 | α β2

可改写为：

A  -> α A'
A' -> β1 | β2

如果原来的某个候选项刚好等于公共前缀，那么对应的尾部就是 ε。变换会改变解析树的形状，因此实现时可能需要在 AST 构造阶段重新合成更自然的节点结构。

变换规则也要保持源语言含义

把 E -> E + T | T 变成 E -> T E'、E' -> + T E' | ε 后，左递归消失，但结合性不能变化。AST 构造器应把连续 + T 从左折叠；若把尾部递归建在右边，就会误把 a-b-c 变成右结合。

左因子提取也只是延迟决定。对 IDENT = Expr 与 IDENT ( Args )，应等下一个 = 或 ( 提供区分信息。用空、最短、重复、嵌套输入测试变换后文法，防止可选尾部引入新二义性。

为实际使用的语法分析器变换文法

左递归对于 LR 语法分析器很自然，也常常清楚表达左结合性。如果使用 LR 体系，只因为“左递归看起来麻烦”就消除它，反而可能降低文法可读性。相反，手写递归下降语法分析器通常必须消除左递归，或把它改为循环、Pratt parser 等实现。

左因子也有类似取舍。它可以让 LL 风格预测更清楚，但过度提取会引入很多辅助非终结符，掩盖用户面对的真实语法。某些语法分析器生成器还提供优先级声明或冲突解决机制，未必需要手工做所有因子化。

变换前请问：

• 当前语法分析器策略究竟是什么？

• 变换是否保留语言，尤其是否正确处理 ε？

• 优先级与结合性是否仍符合语言规范？

• AST 构造器是否还可生成有用的源码范围和诊断？

• 回归用例是否覆盖普通输入与边界输入？

目标不是得到一份“看上去变换过”的文法，而是得到一组能可靠识别语言、正确构建树、并给用户好错误消息的文法和语法分析器。