← 解析器 · 各路引擎、一门文法与编辑器要的那半边 / 手写递归下降：一条产生式一个函数 待审核 2 / 25
LL(1) · peek 派发 · fail-fast

手写递归下降：一条产生式一个函数

上下文无关文法的产生式和函数之间存在一个机械的对应：非终结符对应函数，右部的终结符对应「消耗一个 token」，右部的非终结符对应「调用对应的函数」。照这个对应逐条翻译，就得到一个可以工作的 parser。这种写法叫递归下降（recursive descent）：下降指自顶向下、从起始符号往输入走，递归指这组函数相互调用。

它是手写 parser 的默认形态，也是 @vega/parsing 里 json / regex / glob 等模块实际采用的写法。

1 · 产生式与函数的一一对应

RFC 8259 的 JSON 文法核心只有四条：

value  := object | array | string | number | 'true' | 'false' | 'null'
object := '{' ( member ( ',' member )* )? '}'
member := string ':' value
array  := '[' ( value ( ',' value )* )? ']'

翻译规则逐项对应：| 变成入口处的一次分支，( … )* 变成循环，( … )? 变成一次条件判断，右部里出现的非终结符变成函数调用。递归结构直接由文法的递归结构继承，value 能间接调回自身，对应 JSON 值可以任意嵌套。

图 1-1 · 递归下降的单步轨迹。左侧是调用栈（栈底在下，每帧记录该产生式起于哪个 token、已归约出几个子构件），右侧是 @vega/parsing/json 真实 parse 产出的 AST。切换到出错示例可见 fail-fast 停在哪一帧。

2 · 单 token 判定

value 的入口要在七条候选之间选一条，而它只看了下一个 token 就做了决定：{ 走 object，[ 走 array，字面量类的 token 走对应叶子。既不试探，也不回退。

定义 2.1（LL(1)） 一个文法是 LL(1) 的，若对每个非终结符的任意两条候选产生式，其可能的首个终结符集合互不相交（且在可推出空串时还须与后继集合不相交）。此时只看一个 lookahead 即可唯一确定用哪条产生式。两个 L 分别指从左到右扫描输入、以及构造最左推导。

JSON 文法满足这个条件，因为七条候选的首 token 集合两两不交。这不是巧合，是 JSON 设计上刻意为之：它要让最朴素的解析方法就足以处理。上一段的四个函数就构成一个手写的 LL(1) 解析器：把「看一个 token 选一条产生式」的判断从代码里提出来做成一张二维表，就得到 LL(1) 一页的表驱动版本。表驱动的好处是能自动检测出这个条件何时不成立；手写的代价是冲突只会表现为「某个分支永远走不到」，静默且难查。

3 · 左递归的硬边界

自顶向下方法有一个无法回避的失效条件。考虑算术表达式的自然写法：

E := E '+' T | T

翻译成函数，E() 的第一件事是调用 E()，且此前未消耗任何 token，于是无限递归、栈溢出。这类产生式称为左递归（left recursion），间接形式（AA 推出以 BB 开头、BB 又推出以 AA 开头）同样致命。

警示 · 左递归不是写法瑕疵，而是自顶向下这一族方法的共同边界。三条出路各有代价：改写文法（文法变换 一页的消左递归变换，语言不变但树形改变，且引入辅助非终结符）、把递归换成循环（Pratt parsing 与 算符优先分析 两页，专治表达式的优先级与结合性）、或换用能吃左递归的方法（lr 的自底向上、earley 的 chart、lc 的 left-corner）。纯 packrat 的 PEG 同样栽在左递归上，PEG 与 packrat 一页会看到引擎主动检测并报错，而不是让它栈溢出。

JSON 文法没有左递归，所以递归下降对它够用；表达式语言几乎必然带左递归，所以真实编译器普遍在语句层用递归下降、在表达式层换成 Pratt。

4 · fail-fast 与错误位置

上面的 parser 一旦失配就立即抛出，只报第一处错，且不产出树。这种策略叫 fail-fast，对编译器前端是合理的默认：错误位置越靠前，后续报告越可能是级联噪声。

错误的位置取自当前 token 的起点。这一点比错误消息本身更重要：有了位置才能渲染成带下划线的报告（把错误画成报告 一页），也才能驱动编辑器的波浪线。

而编辑器要的正好相反：文档在编辑过程中大部分时间是不合法的，它需要一次拿到全部错误、并且要一棵仍然可用的树。这条相反的要求由容错解析满足，见 容错解析 与 局部修复 两页。

5 · 递归深度与嵌套深度

递归下降的调用栈深度与输入的嵌套深度成正比。这条性质使它对深嵌套输入天然脆弱：[[[[…]]]] 嵌套上万层就会耗尽调用栈，而这类输入在解析不受信任的 JSON 时是现实威胁。

生产实现的应对是显式设置深度上限并转成普通错误。V8 的 JSON.parse 在遇到过深嵌套时抛 RangeError，各语言的标准库大多有一个可配置的深度阈值。另一条路是把递归改成显式栈的迭代形式，深度上限从此由堆而非调用栈决定。

本页载体的这份实现两条都没做。formats/json/parser.ts 里没有任何深度计数，[ 嵌套到六千层仍正常，七千层则每次都栽（parseValue 与 parseArray 交替占栈，一层嵌套吃两个栈帧）。同一份输入交给 V8 的 JSON.parse，两万层仍能解析完。更要紧的是失败的形态：栈溢出抛的是 RangeError，它绕过了模块统一的 ParseResult 契约，调用方按 if (!r.ok) 那套写法根本接不住，必须另加 try。

警示 · 溢出阈值不是一个可依赖的常数。同一深度在不同调用点、不同 JIT 状态下结论会变：二分查找这个阈值时，6936 层报溢出而 6937 层通过，因为二分过程自身的栈占用参与了结果；固定在 7000 层重复 20 次则 20 次全溢出。凡是拿「能解析多深」当兼容性承诺的地方，都需要显式的深度计数器来兜底。

注 · 深度与输入长度是两个独立的维度。递归下降对长度是线性的（每个 token 恰好被消耗一次），对深度才是线性栈占用。惰性解析 一页的策略正是抓住这一点：容器体先不下潜，只在真正被访问时才展开一层，深嵌套文档的峰值栈深因此与访问路径有关，而与文档整体嵌套无关。

6 · 手写的理由

表驱动的方法能自动检查文法、能由工具生成，但真实编译器前端仍普遍手写：rustc、Clang、TypeScript、Go 的 gc 都是手写递归下降加一个 Pratt 表达式层。原因不在性能，而在可插手性。

自然语言般的错误消息需要在失配处知道上下文；TypeScript 里 < 既可能是小于号也可能是泛型实参列表的开头，判断依赖回溯与试探性解析；增量重解析要能从任意语法结构处重新开始。这些需求都要求对控制流有完全掌握，而生成器给出的是一张表和一个通用驱动循环。表驱动方法的位置更多在「文法本身需要被验证」的场合：语言设计阶段、DSL、以及文法由第三方给定的场合。

7 · 参考文献

  1. Aho, A. V., Lam, M. S., Sethi, R., & Ullman, J. D. (2006). Compilers: Principles, Techniques, and Tools (2nd ed.). Addison-Wesley. §4.4（递归下降与 LL(1)）。
  2. Bray, T. (Ed.). (2017). The JavaScript Object Notation (JSON) Data Interchange Format (RFC 8259). IETF.