消左递归 · 左因子 · CNF

文法变换：改写形态而不改变语言

上一页的三个集合能判断一份文法适不适合某种方法。判断为不适合时有两条路：换方法，或者改文法。这一页讲后者。

四种变换共同的性质是保语言不变：改写前后的文法接受完全相同的串集合。这条性质可以被验证：把同一批输入分别喂给两份文法，接受与否必须逐项一致。本仓库的 transform 模块就用 earley 当 oracle 做这件事，因为 Earley 接受任意上下文无关文法，能作为语言层面的判据而不受形态限制。

1 · 消左递归

$A \to A\,\alpha \mid \beta$ 这种形态使自顶向下方法无限递归。Paull 的变换把它改成右递归：

A \to \beta\,A' \qquad A' \to \alpha\,A' \mid \varepsilon

直觉是：原文法说「 $A$ 是一个 $\beta$ 后面跟任意多个 $\alpha$ 」，改写后把「任意多个 $\alpha$ 」显式地交给一个新的非终结符。间接左递归（ $A$ 推出以 $B$ 开头、 $B$ 又推出以 $A$ 开头）先按非终结符的某个固定顺序做代入，化为直接形态，再逐个消除。

图 1-1 · 四种变换的前后对照。变换由 @vega/parsing/transform 与 cyk 的 toCNF 给出；下表把同一批输入分别喂两份文法、用 earley 识别，逐项核对语言是否不变。读数条同时给出变换前后是否仍含左递归。

警示 · 消左递归保语言，但不保树形。原文法的左递归结构对应左结合的归约次序，变换后重复被挪到右侧，得到的树是右倾的。若语义动作依赖树形（算术减法、赋值链），改写后必须重写语义动作，否则 1-2-3 会算成 ${1}-(2-3)$ 。这与 parser combinator 一页里 chainl1 与右递归写法的差异是同一件事。

2 · 左因子提取

$S \to a\,b \mid a\,c$ 的两条候选 FIRST 相交，一个 lookahead 分不开。把公共前缀提出来：

S \to a\,S' \qquad S' \to b \mid c

决策由此被推迟到公共前缀消费完之后，那时 $b$ 与 $c$ 已经能区分。这条变换处理的是「需要更多 lookahead」这类问题，不处理歧义：上一页说过，两者是不同的事。

3 · 去无用符号

两类符号可以直接删掉：推不出任何终结符串的（不可产生），以及从起始符号出发到不了的（不可达）。

删除次序要紧：先删不可产生的，再删不可达的。反过来做可能留下垃圾：删掉不可产生的符号后，某些原本可达的符号会因为引用它们的产生式被移除而变得不可达。

这条变换不改变任何解析方法的能力，纯粹是规模优化：文法小一圈，构表就快一圈，冲突报告也更干净。

4 · Chomsky 范式

CYK 算法要求每条产生式形如 $A \to B\,C$ 或 $A \to a$ ，这个形态称为 Chomsky 范式（CNF）。转换分四步：新起始符号、抽出长产生式里的终结符、消除 $\varepsilon$ 产生式、消除单元产生式，最后把长度大于二的右部拆成一串二元产生式。

代价是规模。图 1-1 里分层算术文法的 6 条产生式转出 20 条，非终结符从 3 个涨到 11 个；歧义文法 $E \to E + E \mid n$ 的 2 条转出 6 条，非终结符从 1 个涨到 4 个。这个膨胀就是 CYK 的 $O(n^3 |G|)$ 复杂度里 $|G|$ 那一项的来源。

注 · 「保语言不变」这条性质在四种变换里都成立，但可保的东西不止语言这一层。更强的性质是保持歧义度（同一个串的树的棵数不变），CNF 转换在消除单元产生式时可能改变它；再强一层是保持树形，四种变换都做不到。选择变换时要先问清楚下游依赖的是哪一层。

歧义度这一层在本仓库的实现上实测是保住了的。把原文法与 toCNF 的产物分别交给 Earley 数棵数，上面两份文法逐项一致：分层算术在 $n$ 到 $n{+}n{+}n{+}n$ 这几个输入上都是 1 棵，歧义文法在 n+n+n 上都是 2 棵、n+n+n+n 上都是 5 棵。这也是歧义一页六台引擎棵数能对齐的前提，那张表里的 cyk 走的正是 CNF 转换后的文法。理论上的风险仍在，注记里那句「可能改变」不因这两个用例通过而失效；能说的只是这份实现在这些用例上没有触发它，而棵数对照本身就是发现它的手段。

5 · 变换与换方法的取舍

改文法的代价是累积的：每次变换都引入辅助非终结符、加深树、并可能要求重写语义动作。真实项目里若发现文法需要三四次变换才能过 LL(1)，通常说明该换方法而非继续改文法。

反过来，有两类场合改文法是正解。一是文法本身写得不好：共享前缀往往是重构的信号，提取公共前缀后的文法常常也更好读。二是目标引擎的形态要求无法回避，CNF 就属于这类：想用 CYK 就必须转，没有折中。

6 · 参考文献

Paull, M. C. (1968). Algorithm design: A recursion transformation framework. Wiley-Interscience.
Aho, A. V., Lam, M. S., Sethi, R., & Ullman, J. D. (2006). Compilers: Principles, Techniques, and Tools (2nd ed.). Addison-Wesley. §4.3（文法变换）。
Hopcroft, J. E., Motwani, R., & Ullman, J. D. (2006). Introduction to Automata Theory, Languages, and Computation (3rd ed.). Addison-Wesley. §7.1（Chomsky 范式）。