左角闭包 · climb · 混合方向

left-corner：先移进左角，再向上爬

前面几页把自顶向下与自底向上摆成了对立面：LL 死于左递归，LR 天然支持；LL 的表小，LR 的表大。但这两个方向并非只能二选一：left-corner 把它们缝在一起。

1 · 左角

定义 1.1（左角） 产生式 $A \to X\,\beta$ 的最左符号 $X$ 称为该产生式的左角（left corner）。符号 $Y$ 的左角闭包 $\text{lc}^*(Y)$ 是从 $Y$ 出发、沿各产生式最左符号可达的符号集合，即 $Y$ 能以「最左下降」的方式开头的全部符号。

LC 的解析过程分三步循环：

在当前位置移进一个终结符，它必然是目标符号的某个左角终结符；
爬升（climb）：已识别出符号 $X$ 时，找一条产生式 $A \to X\,\beta$ 且 $A \in \text{lc}^*(\text{goal})$ ，自顶向下识别剩余部分 $\beta$ （其中的非终结符递归解析），完成后得到 $A$ ；
对 $A$ 继续爬升，直到抵达目标符号。

每一层都是「一半自底向上、一半自顶向下」：左角靠移进得到， $\beta$ 靠预测得到。

图 1-1 · 左角闭包与各台引擎的同文法对照。闭包按定义 1.1 从文法算出；各行结论分别来自 @vega/parsing/ll 的 buildTable、@vega/parsing/lr 的 buildTable 与 @vega/parsing/lc 的 parse。默认的左递归算术在 LL(1) 那里是构表冲突，LC 直接解析。

2 · 为什么左递归不再是问题

$E \to E + T$ 的左角是 $E$ 自身。LL 在此无限展开，因为它要先「预测出一个 $E$ 」才能继续；LC 不预测左角，它等着移进：先移进一个终结符，识别出某个符号，再看「能不能把它爬升成 $E$ 」。

换句话说，左递归对 LL 是「向下的无底洞」，对 LC 只是「向上多爬一层」。爬升方向天然是有限的，因为每次爬升都要消耗一条产生式且目标固定。这与 LR 的处理方式同源：LR 的 $E \to E \cdot + T$ 也是「栈上已有一个 $E$ 」而非「预测一个 $E$ 」。

3 · 左角闭包作为剪枝

爬升时可选的产生式可能很多， $\text{lc}^*(\text{goal})$ 用来排除注定失败的方向：只有左部落在闭包里的产生式才值得爬。这条剪枝是 LC 相对朴素自底向上枚举的关键收益，作用与 Earley 的 predict 步骤类似，两者都在用「目标符号能以什么开头」来限制搜索。

图 1-1 里两份等价文法的闭包相同，都是 $\{E, T, F, \texttt{(}, \texttt{n}\}$ 。消左递归改写了递归的方向，却没有改变「什么可以出现在最左」。这说明左角闭包刻画的是语言层面的性质，而非文法的书写形态；同一批输入前缀在两份文法下都必须被同样地开头。差别体现在别处：左递归版 LC 用 32 步，消左递归版用 48 步，因为后者多了一层辅助非终结符要爬。

4 · 它在图谱里的位置

LC 的语言类严格介于 LL 与 LR 之间：确定性的 LC(k) 能接受的文法比 LL(k) 多（左递归即例），比 LR(k) 少。这个中间位置使它在两处有实际价值。

一是自然语言处理。左角解析在心理语言学里被反复讨论，因为它对人类的增量理解有较好的建模能力：人听句子时既不是纯自底向上（要有预期）也不是纯自顶向下（要受词面驱动）。Roark 与 Johnson 的增量句法分析器即基于左角变换。

二是文法变换。「左角变换」（left-corner transform）是一种把任意文法改写成无左递归形式的手段，与文法变换一页的 Paull 变换不同，它保留更多结构信息，代价是文法规模更大。

注 · 本仓库的实现是回溯式的非确定 LC，没有构造 LC(1) 预测表，它因此接受歧义文法并枚举出多棵树（图 1-1 切到歧义算术可见）。这使它在能力上更接近 earley，而非严格的确定性方法。把它放在确定性这一组是按方法的分类位置而非本实现的能力边界——LC 的经典形态是确定性表驱动的。回溯枚举带来一个读数上的口径：parse 默认 maxTrees 为 64， $E \to E + E \mid n$ 上实测 3 至 6 项的树数为 2、5、14、42（卡塔兰数），7 项起报 64 并置 stats.truncated，真值 132 已被截断。要与歧义一页的棵数对齐须显式调高该上限。

5 · 参考文献

Rosenkrantz, D. J., & Lewis, P. M. (1970). Deterministic left corner parsing. In Proceedings of the 11th Annual Symposium on Switching and Automata Theory (pp. 139–152).
Roark, B., & Johnson, M. (1999). Efficient probabilistic top-down and left-corner parsing. In Proceedings of the 37th Annual Meeting of the ACL (pp. 421–428).
Grune, D., & Jacobs, C. J. H. (2008). Parsing Techniques: A Practical Guide (2nd ed.). Springer. §10.1（left-corner parsing）。