高阶函数 · 有序选择 · 无 lexer

parser combinator：parser 就是函数

前两页的引擎都有一个专门的驱动器：Pratt 有它的循环，算符优先有它的栈。第三种范式干脆不要驱动器：把 parser 本身定义成一个函数，然后用函数的组合来表达文法。

定义 1.1（parser combinator） 一个 parser 是纯函数 Parser<A> = (State) => Step<A>，其中 State 是「输入串加当前位置」，Step 是「成功并带值与新位置」或「失败并带位置与期望」。combinator 是接受 parser 返回 parser 的高阶函数：seq 顺序连接，alt 有序选择，many 重复，map 变换产物。

这个定义的全部内容就是上面那一行类型。文法不再是一份需要被解释的数据，也不再需要驱动循环，它就是代码。

1 · 层级嵌套与 chainl1

算术表达式的三档优先级写成三层函数，每层的操作数是下一层：

const number = lexeme(regex(/[0-9]+/, '数字'))
const atom   = alt(number, between(symbol('('), expr, symbol(')')))
const power  = chainr1(atom,  ops({ '^': pow }))   // 右结合
const term   = chainl1(power, ops({ '*': mul, '/': div }))
const expr   = chainl1(term,  ops({ '+': add, '-': sub }))

这与递归下降一页的分层文法同构，只是层与层的连接由 combinator 代替了手写的循环。chainl1 与 chainr1 把结合性收进两个组合子：前者把 many(seq(op, operand)) 的结果向左折叠，后者向右。左递归的问题由此被绕过：文法里没有一处直接左递归，重复由 many 表达。

把重复交给 many 之后，零宽度匹配成了新的失效点：若被重复的 parser 能在不消耗输入的情况下成功，循环就永不前进。combinator.ts 的 many 用位置比较挡住了它（if (r.next.pos === cur.pos) break），代价是那一次成功的值被丢弃而非收进结果。由此得到一处容易踩的不对称：many(succeed(1)) 在空输入上实测返回 []，而 many1(succeed(1)) 返回 [1]，因为 many1 先无条件跑一次再转交 many。同理 many(optional(p)) 永远不会在结果里留下代表「这一轮什么都没匹到」的那个 null。凡是靠元素个数反推轮数的语义动作，都要先确认被重复的 parser 不可能零宽成功。

图 1-1 · 组合式解析的单步轨迹。左侧调用栈的每一帧是一个 parser 函数与它的起始位置，右侧统计被重复求值的 (parser, 位置) 对。轨迹装饰器与被装饰者同类型，故跑的是 @vega/parsing/combinator 的真实实现。可切换两种文法写法，对照同一门语言在 chainl1 与有序选择下的求值次数与树形。

2 · 有序选择与它的重叠

alt 的语义是有序的：从同一位置依次尝试各分支，第一个成功者胜出。这与上下文无关文法里 | 的无序语义不同：后者是「这几条都是候选」，前者是「按这个顺序试」。

有序选择的代价是回溯：一个分支即便已经消费了半个句子才失败，也要整段回退，下一个分支从同一位置重新开始。代价的大小取决于候选之间有没有公共前缀。图 1-1 的两种写法把这件事分了开：

写法	`1 + 2 * 3` 的 parser 求值次数	其中重复
`chainl1(term, ops(…))`	12	0
`alt(seq(term, '+', expr), term)`	84	70

第二种写法是照 PEG 教科书的形状写的：先试带运算符的长候选，失败再退回短候选。两条候选共享前缀 term，长候选失败后，短候选要把这个前缀完整重解析一遍。三层文法各自如此，重叠便自乘三次，同一个 atom@4 被求值了 18 次。第一种写法把重复交给 many，各层之间没有公共前缀可回溯，求值次数就是节点数。

警示 · 两种写法还有一处语义差异：有序选择那版的递归出现在右侧，1-2-3 于是被解析成 1-(2-3)，与减法的实际结合性相反。chainl1 版给出 (1-2)-3。把左结合写成右递归再靠语义动作纠正，是这个范式里最常见的一类缺陷：它不报错，只是算错。

回溯的重叠在最坏情形会累积成指数：候选的公共前缀嵌套 $k$ 层即得 ${2}^k$ 量级的重复求值。解法是给 $(\text{规则}, \text{位置})$ 加一张记忆表，把每格压到至多一次，见 PEG 与 packrat 一页，那里用同一份有序选择文法量出了从指数到线性的差距。

3 · 空白与 scannerless parsing

上面的文法里没有 lexer。regex(/[0-9]+/) 直接作用在字符上，lexeme 负责吞掉词素后的空白。这种取消独立词法阶段的做法叫 scannerless parsing。

收益是词法与语法可以互相嵌套：字符串插值里嵌一段表达式、正则字面量与除号的歧义、Markdown 里嵌 HTML，这些「词法边界取决于语法上下文」的场合，两段式骨架要靠 lexer 的模式开关来应付，而 combinator 只是又一次函数调用。

代价是空白处理成为文法作者的责任，且必须处处一致。漏掉一个 lexeme 就会得到一个只在特定空白排布下失败的 parser，这类缺陷不易被例子覆盖。工程惯例是把「词素」这一概念显式化：所有终结符一律走 symbol 或 lexeme，绝不裸用 str 与 regex。

4 · 上下文相关文法与 andThen

有一个能力是上下文无关文法给不了的：用已经解析出的值决定接下来怎么解析。andThen 提供了它：它把前一个 parser 的成功值交给一个函数，由该函数返回下一个 parser。

这使得「先读一个长度前缀，再按这个长度读内容」这类格式可以直接表达（Netstring、某些二进制协议），而它们严格来说不是上下文无关的。同一个能力在 combinator 里只是一次函数调用，在文法驱动的引擎里则需要属性文法或语义谓词（见属性文法一页）。

5 · 错误报告：最远失败

回溯带来一个报错难题：某个分支在很深的位置失败后被整段回退，那个「最深的失败位置」往往才是真正的问题所在，而顶层看到的却只是「所有分支都失败于起点」。

本模块的对策是最远失败（farthest failure）策略：失败信息在合并时保留位置最靠后的那一条，并把该位置上「本应出现什么」的期望集合并起来。被吞掉的软失败（optional 与 many 终止时那一次、alt 落到后续分支前更靠前分支走到的最远处）也一路捎带到顶层，因此「解析成功但留有残余输入」时也能指向最深处而非残余起点。

注 · 最远失败是启发式的，不是最优解。它假设「走得越远的分支越接近作者本意」，这在多数情形成立，但当两个分支走到同样深度时就无从取舍。得到真正好的错误消息仍要靠人工标注：label 组合子用来给某一层起一个说得出口的名字，使期望集合里出现「表达式」而不是「数字或左括号」。

6 · 取舍

parser combinator 的位置在「文法不大、但需要嵌进宿主语言」的场合：配置格式、DSL、协议解析。它的可读性与可组合性最好：文法即代码，能被复用、被参数化、被单元测试。Haskell 的 Parsec、Rust 的 nom、JS 的 Parsimmon 都属此列，@vega/parsing/regex 模块也用它实现了一个与生产递归下降版本交叉验证的对照实现。

它的两处代价前文已述：回溯无缓存，最坏情形指数级，有序选择使文法不再是可分析的数据（无法自动检出歧义或不可达分支）。下一页的 PEG 保留有序选择的语义，但把文法从函数变回数据并加上记忆化，正好补上这两处。

7 · 参考文献

Hutton, G., & Meijer, E. (1998). Monadic parsing in Haskell. Journal of Functional Programming, 8(4), 437–444.
Leijen, D., & Meijer, E. (2001). Parsec: Direct style monadic parser combinators for the real world (Technical Report UU-CS-2001-27). Utrecht University.