编程语言解释器编译器语言运行时教程【免费下载链接】craftinginterpretersRepository for the book Crafting Interpreters项目地址https://gitcode.com/gh_mirrors/cr/craftinginterpreters点击查看免费下载本文基于《Crafting Interpreters》第 17 章Compiling Expressions的课后习题解答笔记结合本仓库中 clox 的 C 源码c/compiler.c深入剖析 clox 单遍编译器如何用 Vaughan Pratt 的自顶向下运算符优先级解析Top-Down Operator Precedence简称 Pratt parsing完成表达式解析与字节码生成。读完本文你将掌握parsePrecedence()的递归调用细节、-等前后缀双角色 Token 的解析规则以及如何把 C 语言?:这样的 mixfix混合位置运算符接入运算符优先级表格。背景clox 的单遍编译管线与 Pratt 解析在动手解读三个练习题之前先建立共同语境。正如书中第 17 章开篇所述这一章补全了 VM 执行管线的最后一块拼图用户源码从扫描器scanner流向编译器compiler再由编译器填充字节码块chunk最终交给虚拟机VM执行。与 jlox 先构建 AST、再遍历 AST 生成代码的两遍式做法不同clox 采取的是单遍编译Single-Pass Compilation解析与代码生成合并为一遍。这种方式对语言设计要求较高——编译器只有窥视孔般的局部视野好在小型、动态类型的 Lox 恰好适合这种设计见 book/compiling-expressions.md。而表达式解析的引擎就是 Pratt 解析。它的优雅之处在于每个 Token 在表格中登记一个前缀prefix解析函数、一个中缀infix解析函数和一个优先级解析器只需一个统一的parsePrecedence()循环即可处理前缀、中缀、后缀乃至 mixfix 运算符无需为每种运算符手写递归下降代码。核心数据结构Precedence 枚举与 ParseRule 表格先看 clox 源码中定义的两块基石。首先是优先级枚举位于 c/compiler.ctypedef enum { PREC_NONE, PREC_ASSIGNMENT, // PREC_OR, // or PREC_AND, // and PREC_EQUALITY, // ! PREC_COMPARISON, // PREC_TERM, // - PREC_FACTOR, // * / PREC_UNARY, // ! - PREC_CALL, // . () PREC_PRIMARY } Precedence;该枚举按优先级从低到高排列PREC_NONE为最低无法作为操作数PREC_PRIMARY为最高主表达式。然后是ParseRule结构体与解析规则表c/compiler.c、c/compiler.ctypedef struct { ParseFn prefix; ParseFn infix; Precedence precedence; } ParseRule;规则表为每个 Token 类型登记三项信息。以算术运算符为例TokenprefixinfixprecedenceTOKEN_MINUSunarybinaryPREC_TERMTOKEN_PLUSNULLbinaryPREC_TERMTOKEN_SLASHNULLbinaryPREC_FACTORTOKEN_STARNULLbinaryPREC_FACTORTOKEN_MINUS一行同时登记了unary和binary——这正是练习 2 讨论的双角色 Token。而TOKEN_PLUS的 prefix 为NULL意味着只能作为中缀减法使用不能用于前缀位置。parsePrecedence()是 Pratt 解析的核心c/compiler.cstatic void parsePrecedence(Precedence precedence) { advance(); ParseFn prefixRule getRule(parser.previous.type)-prefix; if (prefixRule NULL) { error(Expect expression.); return; } bool canAssign precedence PREC_ASSIGNMENT; prefixRule(canAssign); while (precedence getRule(parser.current.type)-precedence) { advance(); ParseFn infixRule getRule(parser.previous.type)-infix; infixRule(canAssign); } if (canAssign match(TOKEN_EQUAL)) { error(Invalid assignment target.); } }流程为消费一个 Token → 调用其前缀函数 → 只要后续 Token 的优先级不低于当前界限就持续调用中缀函数。binary()c/compiler.c在编译完右操作数后按运算符类型发出对应字节码OP_ADD、OP_SUBTRACT、OP_MULTIPLY、OP_DIVIDE等unary()c/compiler.c则以parsePrecedence(PREC_UNARY)递归编译操作数并发出OP_NEGATE/OP_NOT。练习 1追踪(-1 2) * 3 - -4的解析调用轨迹原笔记给出了这道题的答案——一个按调用顺序展开的嵌套轨迹图。表达式(-1 2) * 3 - -4看似古怪实则每一层都对应parsePrecedence()与规则表函数的递归调用。将笔记中的轨迹整理成更易读的调用树缩进表示嵌套调用箭头表示返回值expression() ← parsePrecedence(PREC_ASSIGNMENT) └── parsePrecedence(PREC_ASSIGNMENT) ├── ( 前缀函数 grouping() │ └── expression() │ └── parsePrecedence(PREC_ASSIGNMENT) │ ├── - 前缀函数 unary() │ │ └── parsePrecedence(PREC_UNARY) │ │ └── number() // 字面量 1 │ ├── 中缀函数 binary() │ │ └── parsePrecedence(PREC_TERM 1) PREC_FACTOR │ │ └── number() // 字面量 2 │ └── ) 结束分组 ├── * 中缀函数 binary() │ └── parsePrecedence(PREC_FACTOR 1) PREC_UNARY │ └── number() // 字面量 3 └── - 中缀函数 binary() └── parsePrecedence(PREC_FACTOR) // 即 PREC_TERM 1 └── - 前缀函数 unary() └── parsePrecedence(PREC_UNARY) └── number() // 字面量 4对照源码逐一印证每一步expression()的入口expression()就是parsePrecedence(PREC_ASSIGNMENT)c/compiler.c这是整棵调用树的总入口。左括号的分组grouping()c/compiler.c消费(后调用expression()并consume右括号因为(在规则表中的中缀优先级为PREC_CALLc/compiler.c高于后续运算符所以括号内的表达式会被完整吞掉。内层-1-的前缀函数unary()用parsePrecedence(PREC_UNARY)编译操作数c/compiler.cPREC_UNARY高于加减乘除因此1之后紧跟的不会进入该层-1被完整解析。1 2的中缀加法binary()用parsePrecedence(rule-precedence 1)编译右操作数c/compiler.c的优先级是PREC_TERM加一后变成PREC_FACTOR右操作数2立即完成不向左结合更多项。* 3*的规则是{NULL, binary, PREC_FACTOR}binary()以PREC_FACTOR 1 PREC_UNARY编译3保证乘法右操作数不会被加减法抢走。最外层- -4外层-是中缀减法右操作数以PREC_TERM 1 PREC_FACTOR编译-4中前缀-的unary()再以PREC_UNARY编译4。这里的关键是中缀-的右操作数允许出现前缀-这正是笔记中注释PREC_FACTOR // PREC_TERM 1的含义。值得一提的细节binary()中右操作数的优先级是运算符自身优先级 1这是 Pratt 解析处理左结合的标准手法——同一优先级的后续运算符不会进入右操作数从而保证a - b - c解析为(a - b) - c。练习 2哪些 Token 既作前缀又作中缀原笔记的答案分三层展开Lox 语言中唯一的前缀/中缀双角色 Token 是左括号(前缀位置用于分组grouping中缀位置用于函数调用callc/compiler.c。这直接体现在规则表中TOKEN_LEFT_PAREN {grouping, call, PREC_CALL}c/compiler.c——grouping和call同时挂在同一个 Token 上。call解析参数列表argumentList()后发出OP_CALL指令。其他语言中常见的双角色 Token笔记列举一元加号若干语言允许像-一样作前缀一元运算符正号同时当然也用作中缀加法。有趣的是clox 的规则表中TOKEN_PLUS {NULL, binary, PREC_TERM}即 clox不支持一元正号这正是 Lox 与这些语言的差异点。方括号[不少语言用方括号表示列表/数组字面量前缀又用作下标访问运算符中缀。C 语言的*与*前缀为指针解引用、中缀为乘法前缀为取地址、中缀为按位与。Ruby 的*与它们不能作为前缀表达式但可以出现在实参列表的前缀位置如块参数展开*args。对照 clox 规则表可以佐证一个规律同一 Token 的 prefix 与 infix 可以是完全无关的两个函数表格把符号外形与解析语义解耦这是 Pratt 解析表达力的关键来源。练习 3将 C 风格三元运算符?:接入编译器原笔记给出的方案是在PREC_ASSIGNclox 中实际命名为PREC_ASSIGNMENT与PREC_OR之间新增一个优先级层级PREC_CONDITIONAL然后在?的规则表行中登记一个中缀函数conditional()static void conditional() { // Compile the then branch. parsePrecedence(compiler, PREC_CONDITIONAL); consume(compiler, TOKEN_COLON, Expect : after then branch of conditional operator.); // Compile the else branch. parsePrecedence(compiler, PREC_ASSIGNMENT); }注原笔记中的代码是为书中早期签名编写的完整 clox 最终版中解析函数统一带bool canAssign参数接入时应写作static void conditional(bool canAssign)与 c/compiler.c 的ParseFn类型保持一致。笔记同时点出了两个关键洞察?的操作数优先级是非对称的then 分支以PREC_CONDITIONAL比条件表达式自身低一级编译而 else 分支以PREC_ASSIGNMENT更低编译。也就是说最后一个操作数的优先级低于条件表达式本身。这看似反常但正是 C 的行为方式——a ? b : c ? d : e会右结合且整个条件表达式几乎可以作为任何更大表达式的一个操作数出现。这只是一个编译操作数的骨架完整实现还需要真正生成条件跳转字节码如 clox 后续章节中and_()/or_()那样通过emitJump()/patchJump()实现短路求值但该函数已经保证了三个操作数在正确的优先级下被解析。以 clox 的优先级枚举为参照接入点应当是typedef enum { PREC_NONE, PREC_ASSIGNMENT, // PREC_CONDITIONAL, // ?: PREC_OR, // or ... } Precedence;同时需要在rules表中为TOKEN_QUESTION增加一行{NULL, conditional, PREC_CONDITIONAL}。注意当前 clox 的扫描器与 Token 枚举中并未定义TOKEN_QUESTION与TOKEN_COLON在 c/scanner.h 与 c/token.h 中搜索无结果因此完整接入还需先在词法层补上这两个 Token 类型这也是原笔记明确跳过的一步。结合测试与运行验证本仓库的 test/ 目录提供了大量可运行验证材料。与本文主题最直接相关的有test/expressions/evaluate.lox 与 test/expressions/parse.lox覆盖表达式求值与解析的基础路径test/operator/ 下的negate.lox、add.lox、multiply.lox、divide.lox等逐一验证unary/binary产生的字节码在 VM 上的运行结果test/precedence.lox直接验证运算符优先级的整体行为。编译运行 clox 后你可以直接输入(-1 2) * 3 - -4观察解析结果(1) * 3 - (-4)求值为7。若想观察字节码可借助调试模块disassembleChunk()c/debug.c输出指令序列直观看到OP_NEGATE、OP_ADD、OP_MULTIPLY、OP_SUBTRACT的生成顺序与调用轨迹完全一致。小结三个练习题从三个角度覆盖了 Pratt 解析器的核心机制调用轨迹揭示了parsePrecedence()如何用前缀函数 中缀循环 优先级1统一处理嵌套表达式左结合、括号分组与一元运算符全部由同一套递归规则自然涌现双角色 Token展示了规则表一 Token 两函数的设计如何让同一个符号在不同位置获得不同语义同时指出了 Lox(与其他语言、[、*、的差异三元运算符示范了扩展语法时如何加一级优先级、加一行规则、写一个解析函数并强调了条件表达式右操作数优先级更低这一反直觉但符合 C 语义的设计。掌握这三个要点你就已经抓住了 clox 前端最核心的算法骨架——后续章节的赋值、变量、逻辑与短路运算符都是在这张规则表和parsePrecedence()之上逐步叠加的。赞分享编程语言解释器编译器语言运行时教程【免费下载链接】craftinginterpretersRepository for the book Crafting Interpreters项目地址https://gitcode.com/gh_mirrors/cr/craftinginterpreters点击查看免费下载相关推荐Velero Node-agent 配置指南通过 ConfigMap 精细调优 Data Mover 数据移动 PodVelero Node agent 配置指南通过 ConfigMap 精细调优 Data Mover 数据移动 Pod 导读 Velero node agen编程语言解释器编译器语言运行时教程深入解析DoctorWkt/acwj项目编译器开发中的运算符扩展与优化深入解析DoctorWkt/acwj项目编译器开发中的运算符扩展与优化 引言编译器开发中的运算符挑战 在编译器开发过程中运算符的处理是一个既基础又复杂的关编译器示例工程教程编程语言Impeller 入门实战用 HAL 与着色器编译管线绘制你的第一个三角形Impeller 入门实战用 HAL 与着色器编译管线绘制你的第一个三角形 导读 本文基于 Flutter 引擎中 Impeller 渲染器的官方教程文档跨平台移动开发前端图形学上一篇iPhone激活锁免费绕过applera1n保姆级教程动手前先过四道自检下一篇Visual C 运行库完整指南老系统软件闪退、DLL 缺失的一键修复方案创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考