解析器组合子写到第九篇我决定把整套实现换成 CPSContinuation-Passing Style——也就是把“下一步做什么”当作回调函数一路传下去。这个决定不算突然前几篇的递归下降版本已经让我在长输入上吃了不少苦头而这一篇正好把控制流彻底翻了个底朝天。如果你也在自己做编译器或解释器的前端正被普通组合子的栈溢出、回溯和错误信息折磨这篇应该能给你一条新的实现思路。CPS 风格的解析器组合子本质上是用“续延”continuation替代“返回值”来控制解析流程。它不会让文法变简单但会让“解析到一半接下来干什么”这件事变得显式从而在错误恢复、长输入支持、尾调用优化这些环节获得更大的操作空间。下面我会从动机、类型设计、原语实现、表达式语法搭建、性能边界到踩坑经验把整套东西完整梳理一遍。1. 为什么这次改写没有把组合子留在普通函数式1.1 普通组合子隐藏的控制流和我的踩雷现场写解析器组合子最直观的版本是让每个解析器返回“成功值 剩余输入”。前八篇里我一直这么写它确实好理解type ParserT (input: Input) { ok: true; value: T; rest: Input } | { ok: false; message: string };每个组合子内部拿到前一个解析器的结果再决定下一步。听起来挺干净可实际上控制流被隐式地压进了调用栈里。某次我处理一个很长的模板文件——准确说是一个 10 万字符左右的文本里面还有不少嵌套括号。解析到两千多层嵌套时运行时直接爆出栈溢出。我当时第一反应是“递归深度太大”但真正让我不舒服的是即使把递归改成显式栈普通组合子那条“调用完再返回”的路也很难绕开函数调用帧的堆积。更麻烦的是错误信息。普通返回式组合子失败时通常只能带着一条字符串往上传没有人记得这一路失败路径上到底期望过哪些输入。于是想给用户提示“第 3 行附近期待数字或者右括号”只能在后期另写一层包装组合子内部完全无能为力。这让我动了重写控制流的念头CPS 就是在那个背景下试出来的。1.2 CPS 带来的三个直接收益CPS 的核心变化只有一句话解析器不再 “return”而是把结果交给成功续延或失败续延。这里的“续延”可以理解成“接下来要执行的代码块”在实现里就是一个函数。想象做菜的场景菜谱上写着“加盐然后加水然后关火”。普通写法是 addSalt 函数执行完返回调用方再执行 addWaterCPS 则是把 addWater 和 closeFire 打包成续延函数直接传给 addSalt让 addSalt 自己顺着续延把后面的流程串完。解析器组合子也一样每次匹配完一个字符立刻调用成功续延把剩余输入交给下一个阶段。这个改动给我带来三个实打实的好处控制流显式化每个分支点都明明白白写着“成功去哪”“失败去哪”不会再靠系统调用栈隐式维护。错误信息可以增量构建失败续延可以在不同解析器之间传递上下文把多个期望值合并成一条更自然的提示。尾调用友好只要运行环境支持尾调用或者自己加一个 trampoline很深的嵌套也能安全跑完。当然CPS 不是银弹。它解决的是控制流问题不是文法问题。左递归照样得靠文法改写或优先级爬升来处理。这个限制我在系列后面详细说这里先记住一个结论CPS 换来的不是“什么都能解析”而是“解析器在长输入和错误处理上更可控”。2. 一套可工作的 CPS 组合子骨架类型、原语与连接件2.1 核心类型解析器不再“返回”结果而是“续延”我实现 CPS 组合子用的是 TypeScript因为类型能帮我理清每一层续延的签名。最核心的几个类型是这样设计的type Pos { offset: number; line: number; column: number }; type Input { source: string; pos: Pos; }; type ParseResult | { status: success; value: unknown; rest: Input } | { status: failure; message: string; rest: Input }; type SuccessV (value: V, rest: Input) ParseResult; type Failure (message: string, rest: Input) ParseResult; type ParserV (ok: SuccessV, err: Failure) (input: Input) ParseResult;看到这个类型你可能第一反应ParserV怎么不是“输入到结果”的函数对它多了一对参数ok和err。一个解析器被调用时先收到“成功续延”和“失败续延”然后才收到输入。真正开始解析后它能选择调用ok(value, rest)或者调用err(message, rest)而不是返回给调用者。这里的ParseResult是给最外层驱动用的。你可以理解成每一个小解析器都不直接定义最终结果长什么样它只知道“如果成功了把值传给谁如果失败了把错误传给谁”。最后由runParser提供两个终结续延把结果包装成可观察的ParseResult。这种设计对比普通组合子最大的区别是普通组合子像“打电话问完情况再挂断”CPS 组合子像“开一个工单让工单沿着流程逐级传递最后到终审”。状态不再散落在调用栈里而是在每个续延闭包中显式流动。2.2 基础原语succeed、fail、satisfy有了类型原语实现就很直白了。succeed不回看输入直接触发成功续延const succeed V(value: V): ParserV (ok, _err) (input) ok(value, input);fail直接触发失败续延const fail V(message: string): ParserV (_ok, err) (input) err(message, input);真正干活的是satisfy它消费一个字符并做谓词判断。需要注意失败时不应该消费输入否则会破坏“失败不前进”的约定const advance (input: Input): Input { const ch input.source[input.pos.offset]; if (ch \n) { return { ...input, pos: { offset: input.pos.offset 1, line: input.pos.line 1, column: 1 } }; } return { ...input, pos: { offset: input.pos.offset 1, column: input.pos.column 1 } }; }; const satisfy (predicate: (ch: string) boolean, expected: string): Parserstring (ok, err) (input) { const ch input.source[input.pos.offset]; if (ch undefined) { return err(期望${expected}但已经到输入末尾, input); } if (predicate(ch)) { return ok(ch, advance(input)); } return err(期望${expected}实际遇到 ${JSON.stringify(ch)}, input); };这里有个很微妙的点失败续延的第二个参数传的是input也就是本轮尝试开始的位置而不是advance(input)。如果传成advance(input)外层组合子回溯时就会从错误的位置重新开始导致很多看似正常的输入也会解析失败。这个坑我后面专门再讲先记住CPS 的成功续延和失败续延都会携带输入但语义不同成功续延携带的是消费后的剩余输入失败续延携带的是本轮尝试的起点。2.3 三个关键连接件bind、choice、many解析器不能只有原语还需要把多个解析器组合起来。第一个连接件是bind它对应普通函数式里的flatMap作用是把前一个解析器的值喂给下一个解析器const bind A, B(p: ParserA, f: (a: A) ParserB): ParserB (ok, err) (input) p( (value, rest) f(value)(ok, err)(rest), err )(input);bind的关键在成功续延里p成功时不是把值直接上抛而是立刻把value交给f(value)然后继续用同一套ok和err跑后面的解析器。这条链就这样被续延串起来。第二个连接件是choice也就是普通组合子里的|。它的任务是“第一个失败时从原始输入重试第二个”const choice V(p: ParserV, q: ParserV): ParserV (ok, err) (input) p( ok, (_msg, _rest) q(ok, (msg, rest) err(msg, rest))(input) )(input);我特意把p的失败分支写成忽略_msg和_rest然后重新用input调q。这个input必须是choice开始时的输入而不是p失败时返回的输入否则一旦p消费了几列字符再失败q就会从错误位置继续解析。CPS 里这个回溯点非常显式少写一个参数就是另一种语义。第三个连接件是many。它要循环执行同一个解析器直到失败然后把结果累积成数组const many V(p: ParserV): ParserV[] (ok, err) { const loop (acc: V[]): ParserV[] (ok2, err2) (input) p( (value, rest) loop([...acc, value])(ok2, err2)(rest), (_msg, _rest) ok2(acc, input) )(input); return loop([])(ok, err); };注意many在p失败时调用的是ok2(acc, input)它不是一个错误而是“循环到此为止把已经收集到的列表作为成功结果返回”。这里又用到了“失败不消费”的约定因为p失败时位置还在本轮尝试起点所以把input还给成功续延是安全的。如果p违反了约定many的行为就会出问题。再补一个map和一个lazy后续表达式解析要用const map A, B(p: ParserA, f: (a: A) B): ParserB (ok, err) (input) p((value, rest) ok(f(value), rest), err)(input); const lazy V(thunk: () ParserV): ParserV (ok, err) (input) thunk()(ok, err)(input);最后给一个驱动函数把 CPS 解析器转成普通结果function runParserV(parser: ParserV, source: string): ParseResult { const start: Input { source, pos: { offset: 0, line: 1, column: 1 } }; return parser( (value, rest) ({ status: success, value, rest }), (message, rest) ({ status: failure, message, rest }) )(start); }到这一步骨架已经跑得通了。你可以用它解析一个字符、一串数字或者做简单的选择匹配。真正有意思的是用它搭出带运算符优先级的表达式语法。3. 用 CPS 组合子搭一个带优先级的算术解析器3.1 从词法单元到语法数字、空白和运算符先定义基本的词法单元。数字可以由多个digit组成空白由多个空格或换行组成const isDigit (ch: string) ch 0 ch 9; const digit satisfy(isDigit, 数字); const many1 V(p: ParserV): ParserV[] bind(p, first map(many(p), rest [first, ...rest])); const integer: Parsernumber map(many1(digit), ds parseInt(ds.join(), 10)); const spaces: Parserstring[] many(satisfy(ch ch || ch \n || ch \r, 空白));我想让 token 之间允许任意空白所以写了一个lexeme包装先解析目标 token再吞掉后面所有空白const lexeme V(p: ParserV): ParserV bind(p, v map(spaces, () v)); const symbol (s: string): Parserstring lexeme(satisfy(ch ch s, ${s}));注意symbol()解析完加号后会继续消费后面的空白这样在表达式解析时不需要每步手动处理空格。3.2 chainl1 如何用续延实现左结合算术表达式最麻烦的部分是左结合运算符。比如1 - 2 - 3在标准语义里是(1 - 2) - 3而不是1 - (2 - 3)。普通递归下降写法会把它转成一个循环用累加器实现左结合。CPS 版本也一样只是把“循环”写成了一串尾调用续延。我先给运算符定义解析器把运算符映射成二元函数const plus: Parser(a: number, b: number) number map(symbol(), () (a, b) a b); const times: Parser(a: number, b: number) number map(symbol(*), () (a, b) a * b);然后实现chainl1(term, op)。它的意思是先解析一个term然后反复尝试op只要op成功就再解析一个term把左值、运算符、右值组合成新左值继续向后看function chainl1V(term: ParserV, op: Parser(l: V, r: V) V): ParserV { return (ok, err) { const rest (left: V): ParserV (ok2, err2) (input) op( (fn, restAfterOp) term( (right, restAfterRight) rest(fn(left, right))(ok2, err2)(restAfterRight), err2 )(restAfterOp), (_msg, _restAtOp) ok2(left, input) )(input); return term( (first, restAfterFirst) rest(first)(ok, err)(restAfterFirst), err )(input); }; }这段代码值得多看两遍。rest(left)返回一个解析器它先尝试解析 op。如果 op 成功就把运算符函数fn和后续解析到的right组合成一个新左值然后继续调用rest(fn(left, right))。如果 op 失败说明没有更多运算符了就把当前左值作为最终结果返回并且把位置恢复到本轮尝试前的input。这里有个细节如果 op 成功但 term 失败了不应该回退。比如输入是1 * 2已经看到那后面的内容必须是一个 term此时*不是合法的 term应该报告错误而不是把结果退化成单独的1。所以在 op 成功续延里我传给 term 的失败续延是err2它会把错误继续向上抛。这个“成功后就不可反悔”的行为就是很多解析器中 commit 语义的基础。3.3 跟踪“123”的续延流转过程理论说再多不如手动跑一遍。看输入12*3的简化过程这里乘法优先级高于加法但我先用同一个 chainl1 演示机制。初始时expr调用chainl1(term, plus)。term会先解析1然后用成功续延进入rest(1)。rest(1)尝试解析plus成功得到fn (a,b)ab位置来到2*3之前。接着解析term也就是先解析2进入rest(2)。rest(2)尝试解析times如果成功会先把2*3组合成6再返回rest(6)。在这个简化文法中如果rest(6)发现没有更多加号就把值6作为term的结果返回给外层plus的成功续延。此时外层得到left1right6组合成7继续rest(7)最终7作为整个表达式返回。“续延流转”具体长什么样我用伪代码把关键调用对齐一下expr - term(1) - rest(1) - plus() - term(2) - rest(2) - times(*) - term(3) - rest(6) - plus 失败 - 返回 ok(6, 剩余输入) - plus 成功续延: fn(left1, right6) 7 - rest(7) - plus 失败 - 返回 ok(7, 剩余输入)你会注意到整个流程没有一个“返回后继续”的等待所有下一步动作都被写进了成功续延里。这也是 CPS 调试时最需要适应的地方调用栈看起来可能很扁但每一个闭包里都塞着“接下来的计算”。4. 输入变长后栈安全、性能和左递归的边界4.1 尾调用、trampoline 与栈安全的真实关系CPS 把解析器的控制流从“调用栈隐式管理”变成“续延显式传递”但它并没有凭空消灭函数调用。如果你在 JavaScript 里不加任何处理直接写一版很深的 chainl1照样可能栈溢出。原因不复杂虽然当前解析器在调用成功续延后没有更多动作但如果 JS 引擎不支持尾调用优化这个调用仍然会先在栈上留下一帧然后再进入下一个函数。所以“CPS 能解决栈溢出”这句话是有前提的要么目标运行环境支持尾调用优化要么你自己用 trampoline 把每次续延调用延后到循环里。我自己的实现里驱动层的思路大致是这样把每个“下一步调用”包装成无参函数由循环反复执行。简单的 trampoline 类似type StepT | { done: true; result: T } | { done: false; next: () StepT };真正实现起来需要对所有原语和连接件做一层改造不是加一个run()就能解决但核心思想是明确的别让ok(...)或err(...)在解析器内部直接递归而是返回一个“待执行的下一步”。在支持尾调用的环境里你其实可以不用 trampoline代码更简洁在不支持的环境里trampoline 是必须的。4.2 压力测试10 万字符输入下的行为对比我拿一个很长的表达式字符串做对比大概 5 万个1之后接一个1也就是总长接近 10 万字符的表达式。普通返回式递归组合子解析到几千层就会爆栈这是我在系列前几篇里的真实遭遇。CPS 版本配上 trampoline 后在 Node.js 里可以完整跑完解析时间大约几百毫秒内存会明显高一些因为每个续延闭包都持有上下文。这个结果并不意外。普通组合子的调用深度由输入嵌套深度决定一个 10 万字符的右结合链条就能让栈长到 10 万层CPS trampoline 把这种深度转换成堆上的闭包链堆比栈能扛的数量级大多了。代价是每次成功匹配都要创建几个续延闭包GC 压力比普通版大。如果对性能极端敏感可以在续延复用和数组收集上做优化。但这里我还是要泼一盆冷水CPS 只是换了一个控制流载体并没有改变文法的结构性缺陷。如果文法是左递归的CPS 也只能看着它无限递归。原因在于左递归式子expr :: expr term | term在展开时第一步还没消费任何输入就想再次调用expr这会让解析器进入死循环不管是普通组合子还是 CPS 都一样。所以在我的实现里所有运算符优先级都用优先级爬升改写比如加法用chainl1(term, plus)乘法用chainl1(factor, times)因子层再处理括号和数字。CPS 的价值不是绕开左递归而是让改写后的右递归或循环版本运行得更深、更稳。4.3 CPS 仍然绕不开的墙左递归与无消歧除了左递归还有一个更隐蔽的问题无消歧。CPS 把回溯点变得显式但它不会自动帮你在多个成功路径里选一条最优的。choice默认是“第一个成功就停止”这对应“优先选择第一个匹配项”的贪心策略。如果文法存在歧义比如a既可以是某个关键词又可以是标识符的开头那么choice(keyword, identifier)和choice(identifier, keyword)的结果可能完全不同。要消歧你需要额外机制最长匹配、前瞻、或者优先级表。CPS 的优势在于你可以在成功续延里访问“剩余输入”如果第一个分支得到的rest还有剩余字符你可以决定是否回退去尝试第二个分支。但这种逻辑一旦多了组合子就变得不那么“组合”。我的经验是能用文法分层解决的就用文法分层解决比如运算符优先级表不能分层的关键词冲突再去用前瞻或 commit 语义显式处理。5. 我在这个版本里踩过的坑和最终的代码组织5.1 三个典型 Bug 的完整排查过程CPS 组合子最反直觉的地方就是续延参数传递我连续踩了三个坑每一个都花了不少时间才定位。第一个坑在choice里。我最初写的p失败分支是这样q(ok, err)(_rest)直接用了p失败时传回来的输入。结果当一个解析器消费了几个字符后失败_rest已经前进了好几个位置在这个错误位置上再跑q自然什么也匹配不上最终把本来合法的输入判成语法错误。修复方式就是前面代码里的写法必须从choice开始时的原始input重试q。第二个坑在many里。我最初把p失败分支写成了err2(stop, _rest)结果解析空白时一遇到非空白字符就报错而不是优雅地返回已经收集的空白列表。这里要理解many的语义它内部解析器的失败不是整个解析的失败而是“循环结束信号”。正确的做法是调用ok2(acc, input)把已收集结果作为成功返回。第三个坑在chainl1的 op 失败恢复上。我一开始写了ok2(left, restAfterOp)错误地使用了op失败时传回的输入。但op失败时这个输入有可能是op尝试的起点也可能是前面已经消费后的位置。最终我用ok2(left, input)恢复到了本轮rest(left)开始的位置确保不会再吞掉一个多余的 token。这三个坑总结起来就一句话CPS 里失败续延携带的输入表示“回退到哪”成功续延携带的输入表示“继续到哪”两者绝对不能混用。5.2 调试 CPS 代码的小技巧CPS 调试比普通递归麻烦因为调用栈里几乎看不到清晰的“解析到哪个规则”的层级。我的做法是给关键组合子增加一个可选的label并在调试期打印日志。思路非常简单const debug V(name: string, parser: ParserV): ParserV (ok, err) (input) { const offset input.pos.offset; console.log(enter ${name} ${offset}); return parser( (value, rest) { console.log(ok ${name} ${offset} - ${JSON.stringify(value)}); return ok(value, rest); }, (message, rest) { console.log(fail ${name} ${offset} - ${message}); return err(message, rest); } )(input); };打印出来的日志会非常长但你能清楚地看到每次choice尝试了哪个分支、每次many在什么位置停止。调试完成后把这层包装去掉就行。另一个技巧是给续延编号每次调用ok或err时输出一个自增 id这样可以串起一条完整的续延链排查“谁在什么位置触发了下一步”。5.3 后续迭代路径错误聚合、cut 与运算符优先级表当前版本只保留了最朴素的错误消息真正想做编译器前端的话错误聚合是很自然的下一步。你可以在choice里收集所有失败分支的期望值最终输出“期待数字、加号或右括号”这样的一整句而不是只报最后一个失败分支。实现上只要让失败续延携带一个结构化错误对象而不是纯字符串即可。另一个值得扩展的是cut组合子。很多解析器库里的cut p表示“一旦进入这个分支后续失败就不允许回退到前面的分支”这能提升错误报告质量也能减少无意义的回溯。在 CPS 里实现 cut 非常自然只要在切点后把外层失败续延替换成一个“硬错误”续延就能阻断回溯。运算符优先级如果越来越多chainl1嵌套会变得很啰嗦。我后来直接把优先级表抽成了一个配置按级别从低到高依次构建chainl1层。CPS 组合子在这一层反而更灵活因为每一层解析器都是普通值可以放进数组循环里动态组装。这套 CPS 版本的解析器我保留了挺长时间后续系列里的 JSON 解析和模板语法解析都直接复用了它。每次遇到“这个错误怎么回溯”“长输入怎么不爆栈”的问题我都发现答案早就在续延的传递方式里写好了。如果你也在实现自己的编译器或解释器前端不妨在普通组合子能跑通之后再试着把它改成 CPS 风格——你会发现控制流一旦拿在手里很多之前不敢碰的问题都变得可以下手了。
解析器组合子写到第九篇我决定把整套实现换成 CPSContinuation-Passing Style——也就是把“下一步做什么”当作回调函数一路传下去。这个决定不算突然前几篇的递归下降版本已经让我在长输入上吃了不少苦头而这一篇正好把控制流彻底翻了个底朝天。如果你也在自己做编译器或解释器的前端正被普通组合子的栈溢出、回溯和错误信息折磨这篇应该能给你一条新的实现思路。CPS 风格的解析器组合子本质上是用“续延”continuation替代“返回值”来控制解析流程。它不会让文法变简单但会让“解析到一半接下来干什么”这件事变得显式从而在错误恢复、长输入支持、尾调用优化这些环节获得更大的操作空间。下面我会从动机、类型设计、原语实现、表达式语法搭建、性能边界到踩坑经验把整套东西完整梳理一遍。1. 为什么这次改写没有把组合子留在普通函数式1.1 普通组合子隐藏的控制流和我的踩雷现场写解析器组合子最直观的版本是让每个解析器返回“成功值 剩余输入”。前八篇里我一直这么写它确实好理解type ParserT (input: Input) { ok: true; value: T; rest: Input } | { ok: false; message: string };每个组合子内部拿到前一个解析器的结果再决定下一步。听起来挺干净可实际上控制流被隐式地压进了调用栈里。某次我处理一个很长的模板文件——准确说是一个 10 万字符左右的文本里面还有不少嵌套括号。解析到两千多层嵌套时运行时直接爆出栈溢出。我当时第一反应是“递归深度太大”但真正让我不舒服的是即使把递归改成显式栈普通组合子那条“调用完再返回”的路也很难绕开函数调用帧的堆积。更麻烦的是错误信息。普通返回式组合子失败时通常只能带着一条字符串往上传没有人记得这一路失败路径上到底期望过哪些输入。于是想给用户提示“第 3 行附近期待数字或者右括号”只能在后期另写一层包装组合子内部完全无能为力。这让我动了重写控制流的念头CPS 就是在那个背景下试出来的。1.2 CPS 带来的三个直接收益CPS 的核心变化只有一句话解析器不再 “return”而是把结果交给成功续延或失败续延。这里的“续延”可以理解成“接下来要执行的代码块”在实现里就是一个函数。想象做菜的场景菜谱上写着“加盐然后加水然后关火”。普通写法是 addSalt 函数执行完返回调用方再执行 addWaterCPS 则是把 addWater 和 closeFire 打包成续延函数直接传给 addSalt让 addSalt 自己顺着续延把后面的流程串完。解析器组合子也一样每次匹配完一个字符立刻调用成功续延把剩余输入交给下一个阶段。这个改动给我带来三个实打实的好处控制流显式化每个分支点都明明白白写着“成功去哪”“失败去哪”不会再靠系统调用栈隐式维护。错误信息可以增量构建失败续延可以在不同解析器之间传递上下文把多个期望值合并成一条更自然的提示。尾调用友好只要运行环境支持尾调用或者自己加一个 trampoline很深的嵌套也能安全跑完。当然CPS 不是银弹。它解决的是控制流问题不是文法问题。左递归照样得靠文法改写或优先级爬升来处理。这个限制我在系列后面详细说这里先记住一个结论CPS 换来的不是“什么都能解析”而是“解析器在长输入和错误处理上更可控”。2. 一套可工作的 CPS 组合子骨架类型、原语与连接件2.1 核心类型解析器不再“返回”结果而是“续延”我实现 CPS 组合子用的是 TypeScript因为类型能帮我理清每一层续延的签名。最核心的几个类型是这样设计的type Pos { offset: number; line: number; column: number }; type Input { source: string; pos: Pos; }; type ParseResult | { status: success; value: unknown; rest: Input } | { status: failure; message: string; rest: Input }; type SuccessV (value: V, rest: Input) ParseResult; type Failure (message: string, rest: Input) ParseResult; type ParserV (ok: SuccessV, err: Failure) (input: Input) ParseResult;看到这个类型你可能第一反应ParserV怎么不是“输入到结果”的函数对它多了一对参数ok和err。一个解析器被调用时先收到“成功续延”和“失败续延”然后才收到输入。真正开始解析后它能选择调用ok(value, rest)或者调用err(message, rest)而不是返回给调用者。这里的ParseResult是给最外层驱动用的。你可以理解成每一个小解析器都不直接定义最终结果长什么样它只知道“如果成功了把值传给谁如果失败了把错误传给谁”。最后由runParser提供两个终结续延把结果包装成可观察的ParseResult。这种设计对比普通组合子最大的区别是普通组合子像“打电话问完情况再挂断”CPS 组合子像“开一个工单让工单沿着流程逐级传递最后到终审”。状态不再散落在调用栈里而是在每个续延闭包中显式流动。2.2 基础原语succeed、fail、satisfy有了类型原语实现就很直白了。succeed不回看输入直接触发成功续延const succeed V(value: V): ParserV (ok, _err) (input) ok(value, input);fail直接触发失败续延const fail V(message: string): ParserV (_ok, err) (input) err(message, input);真正干活的是satisfy它消费一个字符并做谓词判断。需要注意失败时不应该消费输入否则会破坏“失败不前进”的约定const advance (input: Input): Input { const ch input.source[input.pos.offset]; if (ch \n) { return { ...input, pos: { offset: input.pos.offset 1, line: input.pos.line 1, column: 1 } }; } return { ...input, pos: { offset: input.pos.offset 1, column: input.pos.column 1 } }; }; const satisfy (predicate: (ch: string) boolean, expected: string): Parserstring (ok, err) (input) { const ch input.source[input.pos.offset]; if (ch undefined) { return err(期望${expected}但已经到输入末尾, input); } if (predicate(ch)) { return ok(ch, advance(input)); } return err(期望${expected}实际遇到 ${JSON.stringify(ch)}, input); };这里有个很微妙的点失败续延的第二个参数传的是input也就是本轮尝试开始的位置而不是advance(input)。如果传成advance(input)外层组合子回溯时就会从错误的位置重新开始导致很多看似正常的输入也会解析失败。这个坑我后面专门再讲先记住CPS 的成功续延和失败续延都会携带输入但语义不同成功续延携带的是消费后的剩余输入失败续延携带的是本轮尝试的起点。2.3 三个关键连接件bind、choice、many解析器不能只有原语还需要把多个解析器组合起来。第一个连接件是bind它对应普通函数式里的flatMap作用是把前一个解析器的值喂给下一个解析器const bind A, B(p: ParserA, f: (a: A) ParserB): ParserB (ok, err) (input) p( (value, rest) f(value)(ok, err)(rest), err )(input);bind的关键在成功续延里p成功时不是把值直接上抛而是立刻把value交给f(value)然后继续用同一套ok和err跑后面的解析器。这条链就这样被续延串起来。第二个连接件是choice也就是普通组合子里的|。它的任务是“第一个失败时从原始输入重试第二个”const choice V(p: ParserV, q: ParserV): ParserV (ok, err) (input) p( ok, (_msg, _rest) q(ok, (msg, rest) err(msg, rest))(input) )(input);我特意把p的失败分支写成忽略_msg和_rest然后重新用input调q。这个input必须是choice开始时的输入而不是p失败时返回的输入否则一旦p消费了几列字符再失败q就会从错误位置继续解析。CPS 里这个回溯点非常显式少写一个参数就是另一种语义。第三个连接件是many。它要循环执行同一个解析器直到失败然后把结果累积成数组const many V(p: ParserV): ParserV[] (ok, err) { const loop (acc: V[]): ParserV[] (ok2, err2) (input) p( (value, rest) loop([...acc, value])(ok2, err2)(rest), (_msg, _rest) ok2(acc, input) )(input); return loop([])(ok, err); };注意many在p失败时调用的是ok2(acc, input)它不是一个错误而是“循环到此为止把已经收集到的列表作为成功结果返回”。这里又用到了“失败不消费”的约定因为p失败时位置还在本轮尝试起点所以把input还给成功续延是安全的。如果p违反了约定many的行为就会出问题。再补一个map和一个lazy后续表达式解析要用const map A, B(p: ParserA, f: (a: A) B): ParserB (ok, err) (input) p((value, rest) ok(f(value), rest), err)(input); const lazy V(thunk: () ParserV): ParserV (ok, err) (input) thunk()(ok, err)(input);最后给一个驱动函数把 CPS 解析器转成普通结果function runParserV(parser: ParserV, source: string): ParseResult { const start: Input { source, pos: { offset: 0, line: 1, column: 1 } }; return parser( (value, rest) ({ status: success, value, rest }), (message, rest) ({ status: failure, message, rest }) )(start); }到这一步骨架已经跑得通了。你可以用它解析一个字符、一串数字或者做简单的选择匹配。真正有意思的是用它搭出带运算符优先级的表达式语法。3. 用 CPS 组合子搭一个带优先级的算术解析器3.1 从词法单元到语法数字、空白和运算符先定义基本的词法单元。数字可以由多个digit组成空白由多个空格或换行组成const isDigit (ch: string) ch 0 ch 9; const digit satisfy(isDigit, 数字); const many1 V(p: ParserV): ParserV[] bind(p, first map(many(p), rest [first, ...rest])); const integer: Parsernumber map(many1(digit), ds parseInt(ds.join(), 10)); const spaces: Parserstring[] many(satisfy(ch ch || ch \n || ch \r, 空白));我想让 token 之间允许任意空白所以写了一个lexeme包装先解析目标 token再吞掉后面所有空白const lexeme V(p: ParserV): ParserV bind(p, v map(spaces, () v)); const symbol (s: string): Parserstring lexeme(satisfy(ch ch s, ${s}));注意symbol()解析完加号后会继续消费后面的空白这样在表达式解析时不需要每步手动处理空格。3.2 chainl1 如何用续延实现左结合算术表达式最麻烦的部分是左结合运算符。比如1 - 2 - 3在标准语义里是(1 - 2) - 3而不是1 - (2 - 3)。普通递归下降写法会把它转成一个循环用累加器实现左结合。CPS 版本也一样只是把“循环”写成了一串尾调用续延。我先给运算符定义解析器把运算符映射成二元函数const plus: Parser(a: number, b: number) number map(symbol(), () (a, b) a b); const times: Parser(a: number, b: number) number map(symbol(*), () (a, b) a * b);然后实现chainl1(term, op)。它的意思是先解析一个term然后反复尝试op只要op成功就再解析一个term把左值、运算符、右值组合成新左值继续向后看function chainl1V(term: ParserV, op: Parser(l: V, r: V) V): ParserV { return (ok, err) { const rest (left: V): ParserV (ok2, err2) (input) op( (fn, restAfterOp) term( (right, restAfterRight) rest(fn(left, right))(ok2, err2)(restAfterRight), err2 )(restAfterOp), (_msg, _restAtOp) ok2(left, input) )(input); return term( (first, restAfterFirst) rest(first)(ok, err)(restAfterFirst), err )(input); }; }这段代码值得多看两遍。rest(left)返回一个解析器它先尝试解析 op。如果 op 成功就把运算符函数fn和后续解析到的right组合成一个新左值然后继续调用rest(fn(left, right))。如果 op 失败说明没有更多运算符了就把当前左值作为最终结果返回并且把位置恢复到本轮尝试前的input。这里有个细节如果 op 成功但 term 失败了不应该回退。比如输入是1 * 2已经看到那后面的内容必须是一个 term此时*不是合法的 term应该报告错误而不是把结果退化成单独的1。所以在 op 成功续延里我传给 term 的失败续延是err2它会把错误继续向上抛。这个“成功后就不可反悔”的行为就是很多解析器中 commit 语义的基础。3.3 跟踪“123”的续延流转过程理论说再多不如手动跑一遍。看输入12*3的简化过程这里乘法优先级高于加法但我先用同一个 chainl1 演示机制。初始时expr调用chainl1(term, plus)。term会先解析1然后用成功续延进入rest(1)。rest(1)尝试解析plus成功得到fn (a,b)ab位置来到2*3之前。接着解析term也就是先解析2进入rest(2)。rest(2)尝试解析times如果成功会先把2*3组合成6再返回rest(6)。在这个简化文法中如果rest(6)发现没有更多加号就把值6作为term的结果返回给外层plus的成功续延。此时外层得到left1right6组合成7继续rest(7)最终7作为整个表达式返回。“续延流转”具体长什么样我用伪代码把关键调用对齐一下expr - term(1) - rest(1) - plus() - term(2) - rest(2) - times(*) - term(3) - rest(6) - plus 失败 - 返回 ok(6, 剩余输入) - plus 成功续延: fn(left1, right6) 7 - rest(7) - plus 失败 - 返回 ok(7, 剩余输入)你会注意到整个流程没有一个“返回后继续”的等待所有下一步动作都被写进了成功续延里。这也是 CPS 调试时最需要适应的地方调用栈看起来可能很扁但每一个闭包里都塞着“接下来的计算”。4. 输入变长后栈安全、性能和左递归的边界4.1 尾调用、trampoline 与栈安全的真实关系CPS 把解析器的控制流从“调用栈隐式管理”变成“续延显式传递”但它并没有凭空消灭函数调用。如果你在 JavaScript 里不加任何处理直接写一版很深的 chainl1照样可能栈溢出。原因不复杂虽然当前解析器在调用成功续延后没有更多动作但如果 JS 引擎不支持尾调用优化这个调用仍然会先在栈上留下一帧然后再进入下一个函数。所以“CPS 能解决栈溢出”这句话是有前提的要么目标运行环境支持尾调用优化要么你自己用 trampoline 把每次续延调用延后到循环里。我自己的实现里驱动层的思路大致是这样把每个“下一步调用”包装成无参函数由循环反复执行。简单的 trampoline 类似type StepT | { done: true; result: T } | { done: false; next: () StepT };真正实现起来需要对所有原语和连接件做一层改造不是加一个run()就能解决但核心思想是明确的别让ok(...)或err(...)在解析器内部直接递归而是返回一个“待执行的下一步”。在支持尾调用的环境里你其实可以不用 trampoline代码更简洁在不支持的环境里trampoline 是必须的。4.2 压力测试10 万字符输入下的行为对比我拿一个很长的表达式字符串做对比大概 5 万个1之后接一个1也就是总长接近 10 万字符的表达式。普通返回式递归组合子解析到几千层就会爆栈这是我在系列前几篇里的真实遭遇。CPS 版本配上 trampoline 后在 Node.js 里可以完整跑完解析时间大约几百毫秒内存会明显高一些因为每个续延闭包都持有上下文。这个结果并不意外。普通组合子的调用深度由输入嵌套深度决定一个 10 万字符的右结合链条就能让栈长到 10 万层CPS trampoline 把这种深度转换成堆上的闭包链堆比栈能扛的数量级大多了。代价是每次成功匹配都要创建几个续延闭包GC 压力比普通版大。如果对性能极端敏感可以在续延复用和数组收集上做优化。但这里我还是要泼一盆冷水CPS 只是换了一个控制流载体并没有改变文法的结构性缺陷。如果文法是左递归的CPS 也只能看着它无限递归。原因在于左递归式子expr :: expr term | term在展开时第一步还没消费任何输入就想再次调用expr这会让解析器进入死循环不管是普通组合子还是 CPS 都一样。所以在我的实现里所有运算符优先级都用优先级爬升改写比如加法用chainl1(term, plus)乘法用chainl1(factor, times)因子层再处理括号和数字。CPS 的价值不是绕开左递归而是让改写后的右递归或循环版本运行得更深、更稳。4.3 CPS 仍然绕不开的墙左递归与无消歧除了左递归还有一个更隐蔽的问题无消歧。CPS 把回溯点变得显式但它不会自动帮你在多个成功路径里选一条最优的。choice默认是“第一个成功就停止”这对应“优先选择第一个匹配项”的贪心策略。如果文法存在歧义比如a既可以是某个关键词又可以是标识符的开头那么choice(keyword, identifier)和choice(identifier, keyword)的结果可能完全不同。要消歧你需要额外机制最长匹配、前瞻、或者优先级表。CPS 的优势在于你可以在成功续延里访问“剩余输入”如果第一个分支得到的rest还有剩余字符你可以决定是否回退去尝试第二个分支。但这种逻辑一旦多了组合子就变得不那么“组合”。我的经验是能用文法分层解决的就用文法分层解决比如运算符优先级表不能分层的关键词冲突再去用前瞻或 commit 语义显式处理。5. 我在这个版本里踩过的坑和最终的代码组织5.1 三个典型 Bug 的完整排查过程CPS 组合子最反直觉的地方就是续延参数传递我连续踩了三个坑每一个都花了不少时间才定位。第一个坑在choice里。我最初写的p失败分支是这样q(ok, err)(_rest)直接用了p失败时传回来的输入。结果当一个解析器消费了几个字符后失败_rest已经前进了好几个位置在这个错误位置上再跑q自然什么也匹配不上最终把本来合法的输入判成语法错误。修复方式就是前面代码里的写法必须从choice开始时的原始input重试q。第二个坑在many里。我最初把p失败分支写成了err2(stop, _rest)结果解析空白时一遇到非空白字符就报错而不是优雅地返回已经收集的空白列表。这里要理解many的语义它内部解析器的失败不是整个解析的失败而是“循环结束信号”。正确的做法是调用ok2(acc, input)把已收集结果作为成功返回。第三个坑在chainl1的 op 失败恢复上。我一开始写了ok2(left, restAfterOp)错误地使用了op失败时传回的输入。但op失败时这个输入有可能是op尝试的起点也可能是前面已经消费后的位置。最终我用ok2(left, input)恢复到了本轮rest(left)开始的位置确保不会再吞掉一个多余的 token。这三个坑总结起来就一句话CPS 里失败续延携带的输入表示“回退到哪”成功续延携带的输入表示“继续到哪”两者绝对不能混用。5.2 调试 CPS 代码的小技巧CPS 调试比普通递归麻烦因为调用栈里几乎看不到清晰的“解析到哪个规则”的层级。我的做法是给关键组合子增加一个可选的label并在调试期打印日志。思路非常简单const debug V(name: string, parser: ParserV): ParserV (ok, err) (input) { const offset input.pos.offset; console.log(enter ${name} ${offset}); return parser( (value, rest) { console.log(ok ${name} ${offset} - ${JSON.stringify(value)}); return ok(value, rest); }, (message, rest) { console.log(fail ${name} ${offset} - ${message}); return err(message, rest); } )(input); };打印出来的日志会非常长但你能清楚地看到每次choice尝试了哪个分支、每次many在什么位置停止。调试完成后把这层包装去掉就行。另一个技巧是给续延编号每次调用ok或err时输出一个自增 id这样可以串起一条完整的续延链排查“谁在什么位置触发了下一步”。5.3 后续迭代路径错误聚合、cut 与运算符优先级表当前版本只保留了最朴素的错误消息真正想做编译器前端的话错误聚合是很自然的下一步。你可以在choice里收集所有失败分支的期望值最终输出“期待数字、加号或右括号”这样的一整句而不是只报最后一个失败分支。实现上只要让失败续延携带一个结构化错误对象而不是纯字符串即可。另一个值得扩展的是cut组合子。很多解析器库里的cut p表示“一旦进入这个分支后续失败就不允许回退到前面的分支”这能提升错误报告质量也能减少无意义的回溯。在 CPS 里实现 cut 非常自然只要在切点后把外层失败续延替换成一个“硬错误”续延就能阻断回溯。运算符优先级如果越来越多chainl1嵌套会变得很啰嗦。我后来直接把优先级表抽成了一个配置按级别从低到高依次构建chainl1层。CPS 组合子在这一层反而更灵活因为每一层解析器都是普通值可以放进数组循环里动态组装。这套 CPS 版本的解析器我保留了挺长时间后续系列里的 JSON 解析和模板语法解析都直接复用了它。每次遇到“这个错误怎么回溯”“长输入怎么不爆栈”的问题我都发现答案早就在续延的传递方式里写好了。如果你也在实现自己的编译器或解释器前端不妨在普通组合子能跑通之后再试着把它改成 CPS 风格——你会发现控制流一旦拿在手里很多之前不敢碰的问题都变得可以下手了。
平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测)
