lex → parse → fold

解析流水线：字符、token、树、值

解析要处理的输入是线性的：源码是一串字符，从头到尾没有层次。而语言的含义是分层的：1 + 2 * 3 里的 2 * 3 必须先结合成一个整体，否则算出的是 ${9}$ 而非 ${7}$ 。把线性输入还原成分层结构，是解析这件事的全部内容；这个分层结构就是语法树。

这条从字符到树的路很少一步走完。@vega/parsing 的各个格式模块共用同一副骨架，分四段：

text ──lex──▶ Token[] ──parse──▶ AST ──fold──▶ value

1 · 各段的判断依据

四段的输入输出类型两两相接，各段内部却是完全不同的判断依据。词法分析只看字符：数字由连续数位构成，<= 要作为一个整体而不是 < 与 =。语法分析只看符号种类：它不关心数字有几位，只关心该位置是一个 NUMBER。fold 只看结构：拿到一棵形状确定的树，按节点类型逐个折叠。

分段的直接好处是每段都能独立替换。calc 模块的同一份文法有三个并列的 parser 实现（手写 Pratt 循环、通用 Pratt 引擎、parser combinator），产出逐字段相同的 AST，下游的求值器一行都不用改。这条断言实测成立：1 + 2 * 3、(1+2)*3、右结合的 2^3^2、前缀负号与幂的 -2^2、以及大整数 9007199254740993，三个实现给出的树逐字段相同。

可替换的粒度却不是三份都一样。parser.ts 与 parser-pratt.ts 各导出两个入口，parse(string) 与 parseTokens(Token[])，后者接在词法阶段之后；parser-combinator.ts 只有 parse(string)，因为它没有独立的 token 流可接（§6 的 scannerless parsing）。所以第三份替换掉的是「词法加语法」这两段的合体，而不是单独的语法段。四段骨架描述的是这条流水线的逻辑分层，各段的接缝在实现里能不能真被切开，得看那份实现有没有把中间产物暴露成类型。

图 1-1 · 同一段输入的四种形态：字符流、token 流、语法树、值。产物均由 @vega/parsing/calc 的 tokenize / parse / evaluate 实时给出。hover 任一 token 或树节点，其覆盖的源码字符同时高亮；切换到语法错误的示例可见诊断落在哪个区间。

2 · 词法分析

token 是语言里的一个「词」：一个种类标记，加上它在源码中的原文与区间。1 + 2 * 3 切完是七个 token（含表示输入结束的 EOF），9007199254740993 无论有多少位都只是一个 NUMBER。

定义 2.1（token） 一个 token 是三元组 $\langle k, r, [s, e) \rangle$ ：种类 $k$ 取自有限集合（NUMBER、IDENT、OP、LPAREN……），原文 $r$ 是源码上的一段子串， $[s, e)$ 是该子串的半开区间。种类的有限性是关键：语法分析面对的于是是一个固定大小的字母表，而不是无穷多种字符串。

词法分析的规则大多一目了然，只有最长匹配（maximal munch）这一条需要交代：在当前位置尽量多吃字符。<= 由此切成一个 OP 而非两个，123 切成一个 NUMBER 而非三个。这条规则让词法分析成为一台纯粹的状态机：无须回溯、无须前瞻整个输入，逐字符推进即可，机器模型见有限自动机系列。

也正因为如此，词法与语法的分界并非天然存在。缩进敏感的语言就把这条界线搅乱了：off-side rule 一页会看到 lexer 不得不替语法层记住块层级，并合成出源码里并不存在的 INDENT 与 DEDENT 标记。

词法阶段还决定了一件容易被忽略的事：原文要不要留。9007199254740993 越过了 IEEE 754 双精度的整数安全区，解码成数值即丢精度，而原文没有。故 NUMBER token 同时携带两者，格式化器据此得以逐字节重放原数字，而 JSON.parse 与 JSON.stringify 往返做不到这件事。

3 · 语法分析

1 + 2 * 3 的七个 token 是一维的，而它表达的运算有嵌套。语法分析要在这条 token 流上恢复嵌套：哪一段先结合、谁是谁的操作数。产物之所以是树而不是别的结构，是因为「子表达式」这个关系天然满足树的两条性质：每个子表达式恰好属于一个父表达式，且不与兄弟交叉。

定义 3.1（抽象语法树） 抽象语法树（abstract syntax tree，AST）是只保留语义结构的树：每个节点记一种运算或一个字面量，不记源码里的空白、注释与多余的分组括号。(1 + 2) 与 1 + 2 产出同一棵 AST，因为括号的作用已经体现在树形里，不必再作为节点存在。

丢掉括号与空白是有代价的：formatter 与重构工具需要能逐字节还原源码。这一需求由无损语法树（concrete syntax tree）满足，无损语法树一页展开。

4 · fold

拿到树之后，「算出多少」是一次自底向上的折叠：叶子给出自身的值，内部节点把孩子的值按自己的运算合成。这个操作叫 fold，在代数上就是从树代数到目标代数的同态。

关键在于，一棵树可以有多种 fold，而它们互不干扰。json 模块的同一棵 AST 上挂着两个 fold：toValue 折成原生 JS 值，format 折成规范化的 JSON 文本。calc 的 evaluate 折成数字。如果求值逻辑写进了 parser 的递归函数里，这两件事就会互相纠缠。

建议 · 让 parser 只产结构、不产语义。判据很简单：同一份输入是否可能需要不止一种产物。需要高亮就得留 span，需要格式化就得留原文，需要类型检查就得留一棵完整的树，这些需求各自都是一次独立的 fold，而 parser 只需要产出它们共同的那棵树。属性文法（属性文法一页）把这种「树到值」的规则形式化成可与引擎解耦的独立层。

5 · 位置守恒

每个 token 与每个 AST 节点都带 [start, end) 区间，且这个区间从 token 一路透传到树的顶端：二元节点的区间覆盖左操作数起点到右操作数终点，调用节点从函数名覆盖到右括号。这条性质叫位置守恒，它支撑三件下游工作。

第一是错误定位：诊断不报「解析失败」，而报「第 5 个字符处期望操作数」，进而能渲染成带下划线的报告（见把错误画成报告一页）。第二是编辑器交互：从光标偏移反查 AST 节点，跳转定义、hover 提示、语法高亮都依赖它。第三是原文重放：区间加原文使 formatter 得以保留数字的精确写法。

位置守恒也是一条可测试的性质：任取一个节点，其区间必须包含全部子节点的区间，且首尾恰好落在自身首末 token 上。这类不变量比「输出是否等于期望字符串」更能守住 parser 的正确性。

6 · 分段的代价

四段骨架有代价。token 流是一个显式数组，对一份 $n$ 字节的输入要分配 $O(n)$ 的中间结构；树的每个节点又是一次分配。两处开销在追求吞吐或启动速度时都会被针对：simd-json 把词法阶段换成对字节的位并行扫描、只产出一串结构偏移；lazy-parse 复刻 V8 的策略，对暂时不需要的子结构只校验合法性而不建节点。这两页各自量化了省下多少。

另一条路是干脆不分段。PEG 与 parser combinator 可以直接在字符上写文法，不设独立的词法阶段，称为 scannerless parsing，代价是文法里要处处显式处理空白，收益是词法与语法可以互相嵌套（PEG 与 packrat 与 parser combinator 两页展开）。

7 · 参考文献

Aho, A. V., Lam, M. S., Sethi, R., & Ullman, J. D. (2006). Compilers: Principles, Techniques, and Tools (2nd ed.). Addison-Wesley. 第 3–4 章。
Grune, D., & Jacobs, C. J. H. (2008). Parsing Techniques: A Practical Guide (2nd ed.). Springer. 第 1–2 章。