解析器 · 各路引擎、一门文法与编辑器要的那半边
解析（parsing）要解决的是同一个问题：输入是线性的字符流，而语言的含义是有层次的——1+2*3 里的 2*3 必须先成一个整体。把线性还原成层次的那套机制就是 parser，产物是语法树。本系列各页拆的是同一条流水线的不同位置：词法分析怎么把字符切成 token、语法分析怎么把 token 升维成树、fold 怎么把树折叠回值。
中段是解析方法的四个象限。按两个维度切：自顶向下（从起始符号猜产生式）还是自底向上（凑齐右部就归约），确定性（要求文法无冲突、换来线性时间）还是通用（接受任意上下文无关文法、含歧义）。Pratt 与算符优先占「表达式优先级」这一格，LL 与 LR 占确定性两格，Earley / CYK / GLR / GLL / Unger 占通用两格，PEG 与 parser combinator 则是带回溯的自顶向下。同一份文法喂进不同引擎，可直接对照它们各自付出与换取的东西。
末段是工程化的那半边，也是教科书讲得最少的一半：编辑器不接受 fail-fast，它要一次报出全部错误、要在有错时仍然产出可用的树、要能逐字节还原源码、要只重解析被编辑触及的那一小段。这几页对应 @vega/parsing 的 recovery / repair / diagnostics / cst / incremental / lazy-parse，设计分别对标 rustc、rust-analyzer 的 rowan 与 V8 的两层预解析策略。
前置知识只需读懂函数递归与基本的树形结构。正则与有限自动机不是前置：词法分析那部分只用到「最长匹配」这一条直觉，需要机器模型时请参阅 有限自动机系列与 regex 系列。
先把四段骨架走通一遍：同一个表达式在 lexer 手里是 token 串、在 parser 手里是树、在 fold 手里是一个数。
解析流水线：字符、token、树、值
解析器不是一个函数，它是一条四段流水线：词法分析把字符流切成 token 流，语法分析把 token 流升维成树，fold 把树折叠回值。以 @vega/parsing/calc 为载体三种形态并置，并说明位置信息为何须贯穿全程。
手写递归下降：一条产生式一个函数
把文法的每条产生式写成一个函数，相互递归即得 parser。以 @vega/parsing/json 的四条产生式为载体，单步展示调用栈的涨落；并说明这种写法为何本质上是手写的 LL(1)，以及左递归为何是它的硬边界。
缩进也是词法问题：off-side rule
Python、YAML 的块结构由缩进决定，lexer 于此要替语法层记住层级，在层级变化处补出源码里没有的 INDENT 与 DEDENT。载体是 @vega/parsing/offside，并证明词法阶段已超出正则。
算术表达式里运算符为操作数竞争，结合次序由优先级与结合性决定。Pratt 把它抽成一张表，算符优先抽成一张关系矩阵，combinator 抽成函数组合，PEG 再给组合加上记忆化。
Pratt parsing：优先级作为数据
分层文法把优先级编码进非终结符的层数，加一档就多一层函数。Pratt 把它变成一张 binding power 表，用单个带门槛的循环驱动全部层级；结合性只是右侧门槛的一次加减。
算符优先分析：优先级作为关系矩阵
Floyd 1963 的做法把优先级编成终结符两两之间的三种关系，由栈驱动自底向上归约。它与 Pratt 是同一想法的两种表示：矩阵与标量、自底向上与自顶向下。代价是只做识别、不重建语法树，且对文法形态有硬要求。
parser combinator：parser 就是函数
把 parser 定义成「读状态、产结果」的纯函数，文法就由 seq / alt / many 这些高阶函数拼出来。优先级靠层级嵌套、结合性靠 chainl1。代价是有序选择的回溯不带缓存，同一个位置会被反复求值。
PEG 与 packrat：把回溯压成线性
PEG 把文法从函数变回数据，由解释器驱动；packrat 在解释器与文法之间插一张「规则 @ 位置」的记忆表，使每格至多求值一次，指数回溯由此变成线性。代价是左递归无解，以及有序选择带来的语义陷阱。
把文法当数据看：nullable / FIRST / FOLLOW 是各表驱动方法共用的预处理，消左递归与左因子提取则是「改写文法而不改变语言」。
文法作为数据：FIRST 与 FOLLOW
表驱动的解析方法都建立在同一份文法预处理上：哪些非终结符能推出空串、每个非终结符可能以哪些终结符开头、又可能被哪些终结符跟随。三个集合由不动点迭代算出，LL 的预测表与 LR 的归约条件都从它们导出。
文法变换：改写形态而不改变语言
各解析方法对文法形态各有要求：LL 不能有左递归与共享前缀，CYK 要求 Chomsky 范式。四种变换把文法改写成所需形态且保持语言不变，但树形会变，这才是它们的真实代价。
要求文法无冲突，换来一遍扫描、线性时间、不回溯。冲突不是缺陷报告，而是这类方法的能力边界。
LL(1)：把 peek 派发做成一张表
手写递归下降的「看一个 token 选一条产生式」被提取成二维预测表，由通用驱动器查表运行。表格化的收益是冲突能被静态检出：每个格子多于一条候选即该文法不是 LL(1)，而这也是这类方法的能力边界。
LR：移进、归约与项集自动机
自底向上不猜产生式，而是把输入移进栈、凑齐右部就归约，反向重建最右推导。关键数据结构是项集自动机：它记住「当前可能在哪几条产生式的什么位置」，左递归因此无碍，且归约时知道用的是哪条规则。
lookahead 的四档精度
四个等级共用同一套移进-归约驱动，差别只在「归约的许可条件有多精确」。SLR(1) 用整个文法的 FOLLOW 集，LALR(1) 用该状态下真正可能的 lookahead，这一步之差决定了 yacc 一族为何选了 LALR(1)。
left-corner：先移进左角，再向上爬
一条产生式最左边的符号叫它的左角。left-corner 先自底向上识别左角，再自顶向下补齐剩余部分，然后把左角爬升为目标符号。左角是移进上来的而非预测出来的，因此它天然接受左递归。
放弃确定性要求，换来任意上下文无关文法都能解析、歧义输入产出多棵树。这一组的引擎从 chart、DP 表、多栈分叉三条路各自抵达同一目标。
歧义：一个串几棵树
歧义是文法的性质而非解析方法的缺陷：同一个串有多棵派生树。棵数随操作数个数按卡塔兰数增长，原理各异的各台通用引擎给出同一个数。而「一份文法是否歧义」本身不可判定。
Earley：chart 上的三类动作
Earley 不构表、不要求文法形态：每个输入位置维护一组「进行中的产生式」，用 predict、scan、complete 三类动作推进。左递归、歧义、空产生式一概照吃，代价是最坏 O(n³)，但对无歧义文法退化为线性。
CYK 与 Unger：记住与不记住
两台引擎做同一件事：枚举「这一段能不能由某个非终结符覆盖」。Unger 直接递归枚举切分点，CYK 把结果记进三角表并自底向上填。同一份文法上前者指数、后者 O(n³)，这就是动态规划的全部价值。
GLR 与 GLL：把冲突变成分岔口
确定性方法遇冲突即拒绝整份文法。GLR 与 GLL 保留冲突格的全部动作，在该处分叉并行推进：一个把 LR 通用化，一个把 LL 通用化。代价是栈从一条变成一张图，树从一棵变成一片森林。
同题横评：同一份文法喂给全部引擎
把同一份文法与同一个输入喂给全部引擎，四个维度并列：接受与否、树的棵数、工作量、以及被拒绝时的理由。通用引擎的棵数必须逐项相同，确定性引擎则以构表冲突的形式暴露各自的边界。
把散落各处的 fold 形式化：给产生式配综合属性与继承属性规则，在树上系统求值，且与产树的引擎解耦。
属性文法：把 fold 形式化
给每条产生式配语义规则，在树上系统求值：综合属性自底向上、继承属性自顶向下。求值器按「左部加子节点符号序列」匹配规则，与产树的引擎因此完全解耦：任何引擎产的树都能喂进同一套规则。
容错、修复、诊断渲染、无损语法树、增量与惰性——教科书不讲，但每一个语言服务器都靠它们活着。
容错解析：一次报出全部错误
编译器可以 fail-fast，编辑器不能，因为文档在编辑过程中大部分时间不合法。容错解析改用「收集而非抛出」：出错处放 error 占位节点，丢 token 到同步点重新对齐，一次报出全部错误且仍产出可用的树。
局部修复与 error production
panic-mode 遇错就丢弃到同步点，句内小笔误也会连累半句。phrase-level 修复改为在失配点做最小编辑，并把它记成一条可执行的 repair；整句无法起头时则用 error production 吸收。
把错误画成报告
本仓库各个 parser 都能产出带 span 的错误，但都止步于「有一个错误对象」。诊断渲染器补上最后一步：把（源码、span、消息）画成带行号边栏与下划线的报告，且不绑定任何语言。
无损语法树：红绿两层
AST 丢掉空白、注释与多余括号，编译器够用，但 formatter 与重构工具需要逐字节还原源码。红绿树把 trivia 也留在树里，并把「结构」与「位置」分成两层：不可变的绿树可被共享，惰性的红树负责定位。
增量解析：只重解析脏区
编辑器每次按键都全文重解析既慢又浪费。增量解析记住上一棵树，编辑后把文档拆成「脏区之前、相交部分、脏区之后」三段，首尾整块复用。绿子树不存绝对位置，位移因此不构成改动。
惰性解析：V8 的两层策略
V8 对暂不执行的函数体只做预解析：扫到结尾、查语法错误，但不建 AST，等被调用才回头完整解析。把这套策略套到 JSON 上：容器体先留占位，访问到才展开一层。省下的是节点分配，付出的是重扫成本。
这些方法各自落在哪些真实系统里
douglas crockford 的 JSLint 让它在 JS 圈流行。LALR(1)：yacc / bison / LALRPOP 的默认级别，Ruby 与 PHP 的官方语法沿用至今。PEG / packrat：Python 3.9 起的官方 parser（PEP 617）替掉了原先的 LL(1)，pest / peg.js 同属此列。GLR：Bison 的 %glr-parser、Elkhound 与 Tree-sitter 的冲突处理思路。Earley：自然语言处理与 nearley，以及各种「文法不受我控制」的场景。容错解析与无损语法树：rust-analyzer（rowan）、Roslyn、Tree-sitter 与所有 LSP 实现的地基；本系列末段那一组正是这条线。与相邻系列的边界
@vega/parsing/regex 的递归下降实现。有限自动机系列讲 regex → NFA → DFA 这条链，也就是词法分析器背后的机器模型。glob 系列是一门迷你模式语言从 AST 到转译的完整案例。HTML Parsing则是容错解析在现实标准里的极端形态：规范明文规定了错误恢复的每一步。本系列不重复这四条线，只在相应位置交叉引用。