# 10 月 30 日左递归审查问题：修复与兼容目标

本页介绍源码分支的左递归支持；已发布的 0.3.0 不包含这些改进。

## 原因与修复

此前递归下降求解器要求规则展开前有输入进展，因此 compile 明确拒绝直接、间接及可空前缀左递归。这个限制属于实现选择，不是 ABNF 文法合法性要求；通用解析器需要覆盖这类合法文法。单纯删除拒绝检查会导致循环/深度预算耗尽，并不能实现支持。

当前实现在检测到左递归时使用有限输入上的单调最小不动点：缓存 `(规则, 起点) → 终点集合`，反复加入新终点，直到稳定。引用只读取已有事实，不递归调用自身。仅遍历入口可达规则。输入树为每个终点保存一个有限见证；新节点只引用已经建立的节点，可空循环不会构成循环输出树。非左递归文法继续使用原路径。

已补直接左递归、间接左递归、可空前缀、空串循环、歧义串及树结构/确定性测试。所有解析均受工作量、状态数和输入长度约束；不动点状态包含空 chart 项，也计入状态预算。达到预算返回 BudgetExceeded（未判定），不能当 NoMatch。

## 兼容目标与边界

目标是按 RFC 5234/RFC 7405 的 ABNF 语义解析调用方给出的闭合文法（Bytes或显式scalar应用域），而不是要求调用方手工消除左递归。当前实现已支持有有限终结推导的直接/间接左递归与可空左递归的识别和单一派生树。

仍明确区分文法语法解析与可执行编译：

- 原 `parse` 保留prose-val，原 `compile` 仍返回prose-unsupported；新增 `compile_with_prose` / `compile_scalar` 接受精确命名的有限词表/单符号范围绑定，不执行自然语言或任意回调。
- 没有有限终结推导的闭合规则现在作为空语言接受编译：入口返回 NoMatch，引用该规则贡献空终点集合；0 次重复仍可导出空串。已覆盖直接/间接空循环、消耗字节但无基例的递归、未引用空规则和有效/空分支混合。生产性分析仅用于确定空语言，不再将此类规则判作文法非法。
- 原Bytes域保留；新增 `parse_numeric` 支持0..Int32最大值AST，`compile_scalar`明确选择Unicode scalar应用域并使用独立树类型。不能称任意外部编码或无限整数支持。详见 SCALAR_PROSE_EXTENSION_20261030.md。
- 左递归无匹配时，现有“局部最远期望”解释算法尚未接入不动点路径；返回 generalized-explanation-unavailable 和 failure=None，不伪造错误位置。recognize/parse_input 的判定独立有效。
- 按所选入口选择路径：编译阶段先通过可空前缀图识别左递归环，再通过所有可执行引用反向传播。只有能引用到左递归环的入口使用不动点求解；前缀已消耗输入的引用仍计入，重复上限为 0 的子表达式不计入。不相关的左递归规则不再改变普通入口的匹配预算、输入树或局部诊断。整个调用保持同一种求解模式，不在单个引用处混用递归与 chart。该分析是保守的静态引用分析，不按具体输入消除永远走不到的分支；分析工作仍受编译预算限制。
- 不枚举所有歧义树，不做错误修复或流式识别；一个确定有限见证满足当前输入树接口。大输入或高度歧义可能耗尽预算。

因此不能宣称已完成所有 ABNF 标准兼容，也不能将测试数量代替标准条款/范围证明。

来源：[RFC 5234](https://www.rfc-editor.org/rfc/rfc5234.html) 第 2–4 节与 Appendix B；[RFC 7405](https://www.rfc-editor.org/rfc/rfc7405.html) 第 2 节。两者定义文法规则/操作符与字符匹配，不规定必须采用无左递归的递归下降实现。