parser · 两种写法与同一棵树

parser combinator 与递归下降

自研引擎的解析器走的是递归下降。本页把它与另一条路并排：parser combinator 是一个吃 parser、吐 parser 的高阶函数，自己不含解析逻辑，只负责把小 parser 拼成大的——seq 管顺序、alt 管选择、many 管重复，文法由「拼数据」声明出来。递归下降则相反，每条文法规则手写成一个函数，while、if 与递归都自己写。两条路殊途同归，产出同一棵 AST。

1 · 两条路径的产物

下面两个 toy 解析器都真在跑，逐字段比对两边的产物。为了让两边源码都短到能一眼读完，玩具子集只解析字面量、.、|、量词 * + ?（含惰性写法）与分组 ( )、(?:)。捕获组编号由两条路径共用的一个后处理 pass 完成，按左括号出现顺序编号，与 JS 对齐。

图 1-1 · 同一条 pattern 分别经组合子与递归下降解析出的 AST，顶部徽标给出 deep-equal 结论。可改 pattern 或点预设。

2 · 两种写法的形状

组合子这一路，文法读起来就是它自己的定义：

// Parser<T> = (s, i) => [value, next] | null   —— 一个 parser 就是个函数
const lit = (c) => (s, i) => s[i] === c ? [c, i + 1] : null;
const sat = (f) => (s, i) => i < s.length && f(s[i]) ? [s[i], i + 1] : null;

// combinator: 吃 parser、吐 parser, 自己不含解析逻辑
const map  = (p, f)  => (s, i) => { const r = p(s, i); return r ? [f(r[0]), r[1]] : null; };
const seq  = (...ps) => (s, i) => { /* 依次跑, 全成功才成功 */ };
const alt  = (...ps) => (s, i) => { /* 第一个成功的赢 */ };
const many = (p)     => (s, i) => { /* p 重复 0+ 次 */ };
const lazy = (f)     => (s, i) => f()(s, i);   // 解开自引用递归

// 文法 = 用 combinator 把零件「拼」出来 (声明式)
const atomP   = alt(groupP, dotP, charP);
const repeatP = map(seq(atomP, opt(quantP)),
                    ([node, q]) => q ? { kind: 'Repeat', ...q, node } : node);
const concatP = map(many(repeatP), foldConcat);
const altP    = map(seq(concatP, many(seq(lit('|'), concatP))),
                    ([head, tail]) => foldAlt(head, tail));

递归下降这一路，控制流全在眼前：

// 递归下降: 每条文法规则 = 一个函数, 控制流自己手写 (命令式)
function parseAlt() {
  const options = [parseConcat()];
  while (peek() === '|') { pos++; options.push(parseConcat()); }   // 自己写 while
  return foldAlt(...);
}
function parseConcat() {
  const parts = [];
  while (!eof() && peek() !== '|' && peek() !== ')') parts.push(parseRepeat());
  return foldConcat(parts);
}
function parseRepeat() {
  let node = parseAtom();
  const c = peek();
  if (c === '*' || c === '+' || c === '?') {        // 手写量词判定
    pos++; let greedy = true;
    if (peek() === '?') { pos++; greedy = false; }
    node = { kind: 'Repeat', quant: QUANT[c], greedy, node };
  }
  return node;
}
function parseAtom() {
  if (peek() === '(') { /* 读分组, 递归 parseAlt, 吃掉 ')' */ }
  if (peek() === '.') { pos++; return { kind: 'AnyChar' }; }
  return { kind: 'Char', ch: src[pos++] };
}

注 · 组合子只是换一种描述文法的方式，不增加任何能力：同一个文法，两边产出的 AST 一字不差。差别在工程性质上——组合子容易拼装与复用，错误信息与性能调优则要额外费心；递归下降控制流直白、报错位置好拿捏，代价是每条规则都得手写。本仓库的引擎选了后者，@vega/parsing 的解析器即是。

3 · 参考文献

Hutton, G., & Meijer, E. (1996). Monadic Parser Combinators. Technical report NOTTCS-TR-96-4, Department of Computer Science, University of Nottingham. 组合子解析的经典论述，seq / alt / many 这套零件的来历。people.cs.nott.ac.uk
Nystrom. Crafting Interpreters: Parsing Expressions. 递归下降的标准写法与优先级处理，本页右侧那一路的教科书版本。craftinginterpreters.com
Ecma International. ECMA-262: Patterns. 正则文法的规范定义，玩具子集之外的完整规则。tc39.es