# Pratt Parsing 工程实现：摒弃分离式词法分析，直接在 Token 级别处理优先级 > 解析器实现新思路：使用 Pratt Parsing（自顶向下优先级解析）在 Token 级别直接处理运算符优先级，抛弃传统 lexer 与 parser 分离模式，提供可落地的 nud/led 表驱动实现方案。 ## 元数据 - 路径: /posts/2026/04/01/pratt-parsing-token-level-precedence/ - 发布时间: 2026-04-01T18:50:35+08:00 - 分类: [compilers](/categories/compilers/) - 站点: https://blog.hotdry.top ## 正文 在表达式解析领域，传统做法通常将词法分析（Lexing）与语法分析（Parsing）严格分离：先由 Lexer 将输入字符流切分为 Token 序列，再由 Parser 根据预定义的优先级规则构建抽象语法树。这种模式虽然经典，但在处理动态优先级、用户自定义运算符或混合语法时，往往需要额外的优先级表或复杂的语法描述文件。Pratt Parsing（又称 Top-Down Operator Precedence，TDOP）提供了一种截然不同的工程化路径：直接在每个 Token 上绑定其前缀（nud）与中缀（led）处理逻辑，以数值化的 Binding Power（绑定强度）取代传统优先级规则，从而实现代码即语法的极简解析器架构。 ## 核心概念：nud 与 led 的职责划分 Pratt Parsing 的精髓在于将表达式的解析逻辑拆解为两类基本操作：Null Denotation（nud）与 Left Denotation（led）。这两个概念源自 Vaughan Pratt 在 1973 年的研究，其核心思想是每个 Token 都可以独立声明自己作为表达式起始点（前缀）或表达式中缀（中缀）时的处理方式。 **nud（空标记记号）**负责处理那些可以独立作为表达式开头的 Token。典型的 nud 处理对象包括：字面量（数字、字符串）、标识符、 grouping 括号（左圆括号）、以及一元前缀运算符（如负号、逻辑非）。nud 函数不接受左侧上下文，只负责将当前 Token 转化为对应的语法树节点。例如，数字 Token 的 nud 直接返回一个 Literal 节点；左括号的 nud 则递归调用表达式解析器，直到匹配到右括号为止。 **led（左侧标记记号）**则处理那些必须出现在某个表达式左侧之后的 Token，本质上对应二元运算符与后缀运算符。led 函数接收左侧已构建完成的语法树节点作为第一个参数，负责消费右侧的表达式并返回组合后的新节点。二元加法的 led 会读取右侧表达式（通常通过递归调用 parseExpression 并传入当前运算符的右侧绑定强度），然后将左右两侧节点封装为一个 BinaryExpr 节点。 这种设计将优先级信息直接嵌入每个 Token 的 led 定义中，无需维护全局优先级表。当 Parser 决定是否继续消费右侧运算符时，只需比较当前运算符的左侧绑定强度（lbp）与已传递进来的右侧绑定强度（rbp）：如果下一个运算符的 lbp 大于当前 rbp，说明该运算符的优先级更高，应当先于当前运算符完成结合。 ## 绑定强度的数值化设计 绑定强度（Binding Power）是 Pratt Parsing 取代传统优先级规则的核心机制。工程师为每个运算符分配两个数值：左侧绑定强度（lbp）与右侧绑定强度（rbp），分别决定该运算符向左与向右结合的能力。在实际工程中，许多实现采用简化的单值方案，仅使用 lbp，通过巧妙设置 rbp 为 lbp 或 lbp-1 来控制结合性。 典型的数值分配策略遵循“乘除先于加减”的直觉：加法与减法的绑定强度设为 20，乘法与除法设为 40，幂运算因右结合特性设为 60（或令其 rbp 为 59 以实现右结合）。赋值运算符通常分配较低的强度（如 10），而成员访问与函数调用则需要较高的强度（如 80 或 100）以确保正确结合。括号本身不构成运算符，而是通过提升解析上下文的 rbp 来强制提高内部表达式的优先级。 以表达式 `1 + 2 * 3` 为例解析流程如下：首先 parseExpression(0) 被调用，nud 处理数字 1 得到左侧 Literal 节点；随后发现下一个 Token 加号的 lbp（20）大于当前 rbp（0），遂调用加号的 led；led 内部以 rbp = 20 递归调用 parseExpression(20) 解析右侧；在右侧解析中，数字 2 被 nud 处理为 Literal，而后的乘号 lbp（40）大于当前 rbp（20），触发乘号的 led；以 rbp = 40 继续解析得到数字 3，最终返回 2 * 3 的子树，最终组合为 1 + (2 * 3) 的完整结构。 ## 表驱动的解析器架构 工程实现上，Pratt Parser 通常采用表驱动模式：建立一个从 Token 类型到 nud/led 处理函数的映射表（Parselet Table），以及每个运算符对应的绑定强度值。这种设计的优势在于添加新运算符无需修改解析核心逻辑，只需在表中注册新的处理函数即可。 最小化实现通常包含以下组件：简易分词器（将输入字符流转换为带类型信息的 Token 流）、Token 类型枚举（Number、Identifier、Plus、Minus、Star、Slash、LeftParen、RightParen、EOF 等）、nud 表（Token 类型到 nud 函数的映射）、led 表（Token 类型到 led 函数与 lbp 数值的映射）、以及 parseExpression 核心函数。 具体实现时，nud 表存储各 Token 类型的前缀处理逻辑：Number 直接返回字面量节点，Identifier 返回标识符节点，左括号触发括号内表达式的递归解析，一元负号在 nud 中以较高 rbp（如 100）递归解析右侧以实现正确的右结合行为。led 表则存储各运算符的中缀处理逻辑：二元运算符以自身 lbp 为参数递归调用 parseExpression 解析右侧，然后将左右子树封装为二元表达式节点返回。 ## 与传统递归下降 parser 的本质差异 传统递归下降 Parser 通常需要为每个非终结符编写独立的递归函数（如 parseExpression、parseTerm、parseFactor），每个函数对应一个优先级层级。这种方式虽然直观，但当需要支持用户自定义优先级或动态修改优先级时，修改成本较高。Pratt Parsing 则将优先级压缩到单一入口函数 parseExpression 中，通过比较绑定强度动态决定解析路径。 另一个关键差异体现在结合性处理上。传统方法需要在语法层面显式处理左递归或右递归，而 Pratt Parsing 通过 rbp 参数巧妙实现：对于左结合运算符，led 内部递归调用 parseExpression 时传入当前 lbp 值；对于右结合运算符（如幂运算），传入 lbp - 1 或更小的值，使得右侧可以继续结合同类运算符。这种设计在同一套解析框架下自然支持了不同的结合性需求。 ## 可落地的工程参数与实现阈值 在生产级实现中，以下参数值可作为参考基准：字面量与标识符的默认绑定强度为 0，确保它们不会意外绑定到相邻运算符；加减法的 lbp/rbp 设为 20/20 实现左结合；乘除法的 lbp/rbp 设为 40/40；幂运算符 lbp 设为 60，rbp 设为 59 以实现右结合；函数调用与成员访问的 lbp 设为 80 以获得最高优先级；赋值运算符根据语言设计可设为 10 或 15。 对于需要支持一元运算符的语言，负号的 nud 处理应当以 100 或更高值作为 rbp 参数递归解析右侧，确保在表达式 ` -3^2` 中正确解析为 `-(3^2)` 而非 `(-3)^2`。括号的 nud 处理则通过创建一个临时的解析上下文，将 rbp 设为一个足够高的值（如 0），确保括号内的表达式能够独立完成完整解析。 监控与调试方面，建议在 parseExpression 循环中记录每次迭代的当前 Token、rbp 值与决策结果，便于追踪复杂的优先级判断路径。对于错误恢复，当遇到既无 nud 又无 led 处理的 Token 时，应抛出具有位置信息的语法错误，而非静默跳过。 Pratt Parsing 的核心价值在于将“优先级”这一抽象概念转化为可执行的数值比较，并将语法定义从代码层级降维到数据层级。对于需要频繁扩展运算符集合的领域特定语言、游戏脚本引擎或教学型解释器，这种表驱动的解析架构能够显著降低维护成本，同时保持解析器代码的简洁与可读性。 资料来源：Eli The Green Place - Top-Down Operator Precedence Parsing；Bob Nystrom - Pratt Parsers: Expression Parsing Made Easy；matklad - Simple but Powerful Pratt Parsing ## 同分类近期文章 ### [C# 15 联合类型：穷尽性模式匹配与密封层次设计](/posts/2026/04/08/csharp-15-union-types-exhaustive-pattern-matching/) - 日期: 2026-04-08T21:26:12+08:00 - 分类: [compilers](/categories/compilers/) - 摘要: 深入分析 C# 15 联合类型的语法设计、穷尽性匹配保证及其与密封类层次结构的工程权衡。 ### [LLVM JSIR 设计解析：面向 JavaScript 的高层 IR 与 SSA 构造策略](/posts/2026/04/08/jsir-javascript-high-level-ir/) - 日期: 2026-04-08T16:51:07+08:00 - 分类: [compilers](/categories/compilers/) - 摘要: 深度解析 LLVM JSIR 的设计动因、SSA 构造策略以及在 JavaScript 编译器工具链中的集成路径，为前端工具链开发者提供可落地的工程参数。 ### [JSIR：面向 JavaScript 的高级 IR 与碎片化解决之道](/posts/2026/04/08/jsir-high-level-javascript-ir/) - 日期: 2026-04-08T15:51:15+08:00 - 分类: [compilers](/categories/compilers/) - 摘要: 解析 LLVM 社区推进的 JSIR 如何通过 MLIR 实现无源码丢失的往返转换，并终结 JavaScript 工具链碎片化困境。 ### [JSIR：面向 JavaScript 的高层中间表示设计实践](/posts/2026/04/08/jsir-high-level-ir-for-javascript/) - 日期: 2026-04-08T10:49:18+08:00 - 分类: [compilers](/categories/compilers/) - 摘要: 深入解析 Google 推出的 JSIR 如何利用 MLIR 框架实现 JavaScript 源码的高保真往返，并探讨其在反编译与去混淆场景的工程实践。 ### [沙箱JIT编译执行安全：内存隔离机制与性能权衡实战](/posts/2026/04/07/sandboxed-jit-compiler-execution-safety/) - 日期: 2026-04-07T12:25:13+08:00 - 分类: [compilers](/categories/compilers/) - 摘要: 深入解析受控沙箱中JIT代码的内存安全隔离机制，提供工程化落地的参数配置清单与性能优化建议。