parser combinator vs 递归下降:同一个文法,两种写法

combinator(组合子)= 一个「吃 parser、吐 parser」的高阶函数,自己不含解析逻辑,只负责把小 parser 拼成大 parser (seq 顺序、alt 选择、many 重复…)。文法用「拼数据」声明出来。 递归下降 (recursive descent) 则相反:每条文法规则手写成一个函数,控制流(while/if/递归)自己写。两条路殊途同归——产出同一棵 AST。下面这两个 toy 解析器都真在跑,改 pattern 看两边树是否一字不差。

玩具子集:为了让两边源码都短到能一眼读完,这页只解析 字面量 · . · | · 量词 * + ?(含惰性 *?)· 分组 ( ) / 非捕获 (?:)。没有字符类 / 锚点 / 转义 / 反向引用——那些本仓库的生产解析器(走的正是右边这种递归下降)都有,见「解析引擎」那页。

pattern

parser combinator声明式 · 拼出来

递归下降命令式 · 手写控制流

AST 节点形状两边完全一致:Char / AnyChar / Concat / Alt / Repeat{quant,greedy} / Group{capturing,#index}。捕获组编号 #1 #2… 由两边共用的一个 left-to-right 后处理 pass 按左括号顺序填(对齐 JS)。绿条 = 逐字段 deep-equal 通过。

两边的解析器长什么样

注意区别只在「怎么描述文法」:左边把 seq/alt/many 拼成数据,右边把同样的结构写成 while/if 与函数递归。

parser combinator (单子式 · 节选,完整版即本页脚本)声明式

递归下降 (节选,完整版即本页脚本)命令式

为什么 regex 没必要为它专门重写? combinator 只换「描述文法」的方式,不增加任何能力——同一棵 AST、同样线性、同样无回溯 (combinator 实现同样可以是 LL(1),而递归下降本就是手写的 LL 解析器)。本仓库 @vega/parsing/regex 的生产解析器选了右边的递归下降 (优先级分层、\1 反向引用的前向回填、精确错误位置都更顺手);而 combinator 这种写法,仓库里 action-grammar 已经有完整示范。