编译原理这四个字在很多人的学习清单里排位都挺尴尬——知道它重要知道面试偶尔会问也知道看懂了能“开天眼”但真翻开书前面几页的字母表、符号串、闭包就把人劝退了。我自己第一次接触编译原理也是这个状态啃了两章文法合上书只记得几个希腊字母。后来真正在做项目时被迫写了一个小型的表达式解析器才算把书本上那些抽象符号和真实代码对上号。这篇入门介绍就是写给当时那个自己的不堆数学证明不急着推自动机先把“编译器到底在干什么”“整条流水线怎么串起来”“新手第一段代码该写什么”讲清楚。这篇适合谁看零基础但想搞明白原理的在校同学、写了几年业务代码想往底层走一步的开发者、需要给项目写配置解析或者规则引擎的工程师还有那些纯粹被“编译原理”这四个字吓退过、想找个不那么吓人的入口的人。关键词就三个编译原理、编译器工作流程、递归下降。读完之后你至少能做到两件事说清楚源代码从字符到机器指令经历了哪几步、每一步输入输出是什么以及自己动手写出一个能算加减乘除带括号的小型“编译器”先把流程跑通。1. 先搞清楚编译器到底在干什么1.1 一个翻译官的类比比任何定义都好用把编译器想象成一位翻译官这个类比虽然老套但真的有效。你写的高级语言代码相当于一封用中文写的信CPU 只认识机器指令相当于只懂某种外语的收信人。翻译官的工作不是逐字替换而是先读懂整封信的意思再按照对方的语言习惯重新组织句子最后才落笔。如果只是逐字查词典替换结果一定是语法不通的这就是为什么“简单替换”做不出编译器。这个类比里藏着两个关键判断第一编译是分阶段的读信、理解、组织、落笔是不同工序每道工序的产出物不一样第二编译是保语义的翻译完的信必须和原信意思一致否则翻译就是错的。后一点经常被新手忽略——很多人写解析器时只管“能跑通”结果23*4算出来是 20 而不是 14语法全对、语义全错这种 bug 恰恰是编译器最不该犯的。按业界的通俗定义编译器是把一种语言源语言写成的程序整体转换成另一种语言目标语言写成的程序。注意“整体”两个字这正是它和解释器的分水岭。编译器拿到完整的源文件后才开工产出的是一个新的产物目标文件、字节码、另一段代码解释器则是边读边执行读一行做一行不产生独立产物。两者的差异直接决定了错误发现时机、执行性能和调试体验下一节展开说。还有一类经常被混为一谈的东西预处理器、转换器、编译器前端库。预处理器只做文本级替换不理解语法#define那种宏展开就是典型转换器是把一种高级语言变成另一种高级语言比如把某个新语法编译成老版本语法产出仍是源代码而编译器前端库只负责“读懂”把源码变成结构化表示接不接后端由你决定。搞清自己要做的是哪一类选型才不会跑偏。1.2 编译器、解释器、混合模式三条路线怎么选新手最常见的困惑是既然解释器能直接跑为什么还要费劲编译答案在于代价的分配位置不同。编译把开销前置一次翻译、多次执行适合反复运行的场景解释把开销后置改一行立刻能跑适合迭代频繁的调试场景。这不是技术优劣是工程权衡。维度编译器解释器混合模式先编译成字节码再解释/JIT产出物目标机器码或字节码文件无独立产物直接执行中间表示字节码启动速度慢需要先编译快边读边跑中等需先生成中间表示执行速度快可做深度优化慢每次都要解析快热点代码可优化错误发现编译期集中报错运行到哪错到哪编译期报语法错运行时报类型错调试体验源码与目标码有映射需调试信息直接对应源码需要映射表典型适用交付部署、嵌入式、性能敏感脚本、配置、一次性任务通用语言运行时、大型应用我个人的经验是学习阶段优先做编译器不要做解释器。原因很实在——编译器有明确的产物你可以把中间结果打印出来对照检查词法分析完了看 token 列表语法分析完了看语法树每一步都能验证对错解释器边读边跑出错时你很难判断是解析错了还是执行错了。等流程跑通了再把“执行”这一步接上去它就是一个解释器了成本极低。至于混合模式值得多说一句。它本质上是把“编译”这一步的目标语言选成了自己设计的字节码而不是真实 CPU 指令于是获得了可移植性执行时再用一个虚拟机去解释这些字节码或者把热点部分即时编译成机器码。这条路线的复杂度在于虚拟机的设计与优化策略新手阶段完全不必碰但要知道它存在理解“编译目标不一定是机器码”这一点对后面理解中间表示非常有帮助。1.3 为什么新手也该啃这块硬骨头先说功利的部分。你日常用的构建工具、模板引擎、正则引擎、ORM 的查询构造、前端框架的模板编译、IDE 的语法高亮与跳转、Lint 规则的实现背后全是编译原理的东西。搞懂了词法分析和语法分析你再去读那些“看起来像黑魔法”的库会突然发现它们的骨架很朴素切词、建树、遍历、输出。这种“祛魅”的体验是其他知识很难给的。再说思维层面。编译原理训练的是分层抽象的能力把一个大问题拆成若干阶段每个阶段只做一件事阶段之间用明确的数据结构通信。这个套路不只用于编译器。你写一个数据导入模块天然就是“读取→解析→校验→转换→落库”五段式你做一个规则引擎天然就是“切词→建条件树→求值”。我带过几个刚工作的同学明显感觉到系统学过编译原理的人写这类转换逻辑时结构更清晰因为他们下意识就在做阶段划分。最后说长期价值。抽象语法树、中间表示、静态类型检查这些概念在数据库SQL 解析与优化、硬件设计综合工具、AI 领域计算图编译、算子融合里全都出现了类似的结构。你今天花在理解 AST 上的时间会在未来某个完全不相干的场景里回报你。顺手提一句新手最容易走的弯路一上来就抱着龙书死磕形式语言与自动机理论。理论当然要学但它和“动手写一个能跑的东西”之间有个巨大的鸿沟先跨过去再回头补理论效率高得多。这是我踩过的坑——第一遍学的时候把大量时间花在证明 NFA 到 DFA 的等价性上结果连一个 token 流都没切出来过挫败感极强。2. 把编译流程拆成一条流水线2.1 词法分析把字符流切成有意义的“单词”词法分析是整个流水线的第一道工序任务简单但极其关键把一串字符12*(3-4)切成一个个有类型的记号token并且丢掉空格、换行这类无意义字符。输出通常是一个 token 列表每个 token 带上类型、原始文本、以及它在源码里的位置行号、列号、起止偏移。位置信息千万别省后面报错全靠它。为什么要有这一步因为后续的语法分析关心的是“加法符号”这个抽象概念而不是 ASCII 码里那个 43 号字符。词法分析把字符级的细节收敛成类型化的记号让语法分析可以在更高层次上工作。这就是分层的价值——每一层都隐藏下一层的复杂度。具体怎么切最常用的做法是正则匹配 最长匹配 关键字优先。你为每种 token 定义一个正则模式然后从左到右扫描每次尝试匹配选最长的那个成功匹配。这条“最长匹配”规则很重要遇到时绝不能先匹配到就收手否则后面那个会变成一个孤立的记号语法分析直接崩。同理遇到if这种关键字它同时也符合“标识符”的模式所以必须先判断关键字集合再走标识符规则。注意很多正则引擎默认行为是贪婪匹配但这和“词法规则的最长匹配”不完全是一回事。手写扫描器时规则的书写顺序决定了匹配优先级一定要把更具体、更长的规则排在前面把通用规则标识符、数字排在后面。这里有个隐性的坑值得提前说绝大多数教材用正则表达式来定义 token但正则文法处理不了嵌套结构比如括号配对、块注释/* ... /* ... */ ... */。所以凡是涉及嵌套的部分必须在词法层用状态机手工处理别硬塞进正则里。我见过有人为了匹配嵌套注释写了一百多字符的正则最后既跑不动也改不动。2.2 语法分析检查句子结构是否成立拿到 token 流之后语法分析的任务是判断这串记号能不能按语法规则组合成合法结构并且把这种结构显式地表达出来——这个表达就是抽象语法树AST。注意是“抽象”语法树不是“具体”语法树具体树里会保留括号、分号这些分隔符节点抽象树里把它们去掉只留下真正承载语义的结构。语法规则怎么描述业界通用的是巴科斯范式BNF及其变体。举个最简的例子四则运算的规则可以写成expr : term (( | -) term)* term : factor ((* | /) factor)* factor : NUMBER | ( expr ) | - factor这三行规则信息量很大。它把“加减”和“乘除”拆成两个层级天然表达了乘除优先级高于加减它把括号写成“一个 factor 可以是括号包起来的 expr”这是递归的体现也是上下文无关文法能描述嵌套结构的根本原因它用*表示“重复零次或多次”避免了直接写左递归。说到左递归这是新手必踩的坑。教科书写expr : expr term看起来很自然但如果你用递归下降的方式实现函数parse_expr第一件事就是调用parse_expr直接栈溢出。解决办法是把它改写成等价的右递归或者循环形式也就是上面那种term (( | -) term)*的写法。递归下降天然适合处理右递归处理左递归要靠消除或改写成循环记住这条能省下好几个小时的调试。语法分析的实现路线大致分三派手写递归下降、表驱动的自底向上分析LR 系列、以及用生成器自动产出。新手阶段强烈建议手写递归下降理由很直接——它和文法规则几乎一一对应你看着 BNF 就能写出代码出错时也容易定位到具体规则上。等到规则规模大到几十上百条再考虑上生成器。2.3 语义分析语法对了不代表讲得通“ colorless green ideas sleep furiously ”这句话语法完全正确但语义荒诞。编译器也一样a b结构没问题但如果a是个整数、b是个字符串这就讲不通了。语义分析要干的就是这类活维护符号表、检查类型、检查作用域、检查变量是否声明、函数调用参数个数是否匹配。符号表是这一阶段的核心数据结构本质是一个从名字到信息的映射信息包括类型、作用域层级、存储位置、是否已初始化等。麻烦的是作用域是嵌套的所以常见的实现是“栈式符号表”或者“链式作用域”进入一个块就压一层离开就弹一层查找时从内向外逐层找。你要是只用一个扁平字典遇到同名变量遮蔽的场景必然出错。检查项典型错误示例发现阶段处理方式变量未声明使用x但从未定义语义分析报错并标注位置类型不匹配整数与字符串相加语义分析报错或按规则隐式转换重复定义同一作用域内两次定义同名变量语义分析报错调用参数不符函数声明两个参数调用传了三个语义分析报错控制流缺失返回非 void 函数某分支没有 return语义分析警告或报错不可达代码return 之后还有语句语义分析或优化警告优化阶段删除我个人的体会是语义分析这一层最容易被新手跳过因为它不像词法和语法那样“能画图”但它恰恰是决定你的实现是“玩具”还是“能用”的分界线。一个只做语法检查的解析器遇到用户写错变量名时只能干瞪眼加上符号表之后报错信息立刻从“语法错误”变成“第 12 行变量count未声明是否想用counter”体验差一个量级。2.4 中间代码、优化与目标代码从“能跑”到“跑得快”语义检查通过之后很多教材会直接跳到目标代码生成这是不对的。中间代码这一步不能省原因是它把“语言相关的部分”和“机器相关的部分”彻底解耦。前端词法、语法、语义负责理解源语言后端优化、代码生成负责适配目标机器中间代码是两者之间的契约。有了这层契约一个前端可以接多个后端多平台支持一个后端也可以接多个前端多语言支持这是现实中主流编译器架构的基本形态。最经典的中间表示是三地址码每条指令最多包含一个运算符、两个源操作数、一个目标操作数形如t1 a b。它的好处是结构规整、容易分析和变换控制流可以表示成基本块加跳转数据流分析也能直接在它上面做。往上还有更抽象的形式比如带类型的树形表示、往下还有更接近机器的形式比如带虚拟寄存器的线性表示新手从三地址码入手最合适因为它既能手写生成、又能肉眼验证。优化就建立在中间表示之上。常见的入门级优化有几类常量折叠编译期能算出来的就提前算2 * 3直接变成6。常量传播把已知的常量值传播到使用点配合折叠效果更好。公共子表达式消除同一个表达式算了两遍第二遍直接复用结果。死代码消除算了但没人用的结果、永远走不到的分支删掉。强度削弱把昂贵的运算换成便宜的比如乘以 2 的幂换成移位。注意优化的第一原则是不能改变程序的可观测行为。新手最容易在这里翻车——把带副作用的表达式当纯表达式折叠了或者重排了有依赖的读写顺序。每次写完一个优化必须拿一批用例回归尤其是带边界值、带副作用、带异常的用例。目标代码生成是最后一公里把中间表示翻译成目标机器的指令同时解决寄存器分配这个老大难问题。寄存器数量有限变量一大堆谁进寄存器、谁溢出到内存需要一套分配算法图着色是经典方案。这部分对新手来说可以先简化假设寄存器无限多先把指令生成跑通等真需要性能了再回来处理分配。我在第一次实现时死磕寄存器分配结果卡了两周毫无进展后来退回去用“无限寄存器 后处理溢出”的方案一天就跑通了这个取舍非常值。把六个阶段串起来整条流水线的输入输出关系可以这样记阶段输入输出新手常见错误词法分析字符流token 列表不处理最长匹配、丢失位置信息语法分析token 列表抽象语法树左递归导致栈溢出、优先级层次搞错语义分析语法树 符号表带类型标注的语法树作用域扁平化、不做类型检查中间代码生成标注后的语法树三地址码 / 中间表示临时变量命名冲突、求值顺序错乱优化中间表示优化后的中间表示破坏语义、忽略副作用目标代码生成优化后的中间表示汇编或机器码寄存器冲突、调用约定不匹配3. 动手写一个最小可用的表达式编译器3.1 先把边界定死支持什么、不支持什么动手之前一定要先划范围这是我踩坑最多的地方。第一次写的时候雄心勃勃想支持变量、函数、循环、字符串结果写到一半发现符号表设计撑不住推倒重来。后来学乖了第一版只做四则运算加括号加一元负号输入是一个字符串输出是三地址码列表。功能极窄但流程完整从切词到生成代码一步不缺。第一版的能力边界支持整数和浮点数常量浮点只是为了演示实际项目中我会用定点或直接报错。支持 - * /四则运算-既可以做二元减号也可以做一元负号。支持圆括号改变优先级。不支持变量、不支持函数调用、不支持赋值。遇到任何非法输入抛出带位置信息的异常。这个范围小到一天能写完但它逼着你把词法、语法、代码生成三个环节全部走一遍而且每一步的中间结果都能打印出来肉眼核对。先用最小闭环跑通再逐步加特性这个方法论适用于几乎所有工程问题在编译器上尤其明显因为它的阶段耦合度很高一步错后面全错。3.2 词法分析器四十行代码的核心逻辑下面这个实现用正则规则表驱动扫描核心是“按顺序尝试、取第一个成功匹配、跳过空白”。这个写法不够高效每次都切片重建字符串但足够清晰适合新手理解。import re # 规则顺序很重要更具体的规则必须排在通用规则前面 TOKEN_RULES [ (NUMBER, r\d(?:\.\d)?, ), # 整数或小数 (PLUS, r\), (MINUS, r-), (STAR, r\*), (SLASH, r/), (LPAREN, r\(), (RPAREN, r\)), (SPACE, r[ \t\r\n]), ] COMPILED [(kind, re.compile(pat)) for kind, pat, in [(k, p) for k, p in TOKEN_RULES]] def tokenize(src: str): pos 0 line, col 1, 1 tokens [] while pos len(src): for kind, pattern in COMPILED: m pattern.match(src, pos) if not m: continue text m.group(0) start_line, start_col line, col # 更新行列号按换行符切分统计 newlines text.count(\n) if newlines: line newlines col len(text) - text.rfind(\n) else: col len(text) pos m.end() if kind ! SPACE: tokens.append({ kind: kind, text: text, line: start_line, col: start_col, }) break else: raise SyntaxError( f第 {line} 行第 {col} 列出现无法识别的字符 {src[pos]!r} ) tokens.append({kind: EOF, text: , line: line, col: col}) return tokens几个值得说的细节。第一我用pattern.match(src, pos)而不是对切片做匹配这样避免了每次创建新字符串同时也让m.end()直接给出新位置代码更干净。第二行号列号的更新必须精确text.rfind(\n)那个写法是为了处理“一段文本里有多个换行”的情况col应该重置到最后一个换行之后。第三末尾补一个EOF记号这是为了让语法分析器不用到处判断“是不是到头了”统一处理会省很多边界代码。注意src.rfind那段在多换行时有个细节——len(text) - text.rfind(\n)得到的是最后一行的字符数但它从 1 开始计数所以列号是准的。这类“差一”错误极其常见写完务必用手工构造的用例验证一遍比如1 \n 2确认第二行的2列号是 3 而不是 2。再加一句关于浮点的提醒上面用了float纯粹是为了 demo 简洁。真做语言实现浮点数会牵扯精度、舍入、NaN、比较语义一大堆问题我建议第一版要么只支持整数要么把数值类型做成显式的结构体别偷懒用float。3.3 递归下降解析器看着文法写代码有了 token 流接下来按文法写三个函数一层管一个优先级。这个结构的好处是函数与文法规则一一对应改动文法时改哪个函数非常明确。class Parser: def __init__(self, tokens): self.tokens tokens self.pos 0 def peek(self): return self.tokens[self.pos] def advance(self): tok self.tokens[self.pos] self.pos 1 return tok def expect(self, kind): tok self.peek() if tok[kind] ! kind: raise SyntaxError( f第 {tok[line]} 行第 {tok[col]} 列 f期望 {kind}实际遇到 {tok[kind]}({tok[text]!r}) ) return self.advance() # expr : term (( | -) term)* def parse_expr(self): node self.parse_term() while self.peek()[kind] in (PLUS, MINUS): op self.advance()[kind] right self.parse_term() node {type: binop, op: op, left: node, right: right} return node # term : factor ((* | /) factor)* def parse_term(self): node self.parse_factor() while self.peek()[kind] in (STAR, SLASH): op self.advance()[kind] right self.parse_factor() node {type: binop, op: op, left: node, right: right} return node # factor : NUMBER | ( expr ) | - factor def parse_factor(self): tok self.peek() if tok[kind] NUMBER: self.advance() return {type: num, value: tok[text]} if tok[kind] LPAREN: self.advance() node self.parse_expr() self.expect(RPAREN) return node if tok[kind] MINUS: self.advance() return {type: neg, operand: self.parse_factor()} raise SyntaxError( f第 {tok[line]} 行第 {tok[col]} 列 f无法作为表达式开头{tok[kind]}({tok[text]!r}) ) def parse(self): node self.parse_expr() self.expect(EOF) return node注意while循环那段它替代了左递归。文法写的是expr : expr term代码写成“先解析一个 term然后只要看到加号就继续吃”这本质上是把左递归改造成了迭代。这个转换是机械的记住模板就行A : A op B | B等价于A : B (op B)*代码里就是一个前置调用加一个循环。再看parse_factor里对括号的处理——它调用parse_expr而不是parse_term这是必须的因为括号里的内容可以是完整的加减表达式。如果这里写成parse_term(12)*3就会解析失败。同理一元负号的处理放在factor层意味着-2*3会被解析成(-2)*3而不是-(2*3)这在数值上恰好等价但在引入函数调用或更复杂的前缀运算符时优先级归属就必须仔细推敲了。3.4 从直接求值到生成三地址码最省事的做法是解析完直接在树上递归求值二十行搞定def evaluate(node): t node[type] if t num: return float(node[value]) if t neg: return -evaluate(node[operand]) left, right evaluate(node[left]), evaluate(node[right]) op node[op] if op PLUS: return left right if op MINUS: return left - right if op STAR: return left * right if op SLASH: if right 0: raise ZeroDivisionError(除数为零) return left / right raise ValueError(f未知运算符 {op})但求值这一步掩盖了大量信息你没法看到“编译器怎么把一棵树变成线性指令”。所以第二步我强烈建议补上三地址码生成这段代码是整个流程里最有“编译器味道”的部分class CodeGen: OP_MAP {PLUS: , MINUS: -, STAR: *, SLASH: /} def __init__(self): self.counter 0 self.insns [] def new_temp(self): self.counter 1 return ft{self.counter} def gen(self, node): t node[type] if t num: return node[value] # 常量可以直接当操作数用 if t neg: val self.gen(node[operand]) tmp self.new_temp() self.insns.append(f{tmp} -{val}) return tmp # 二元运算先递归生成左右子树再发一条加法类指令 left self.gen(node[left]) right self.gen(node[right]) tmp self.new_temp() op self.OP_MAP[node[op]] self.insns.append(f{tmp} {left} {op} {right}) return tmp def compile(self, ast): result self.gen(ast) return self.insns, result跑一下1 2 * (3 - 4)src 1 2 * (3 - 4) tokens tokenize(src) ast Parser(tokens).parse() insns, result CodeGen().compile(ast) print(\n.join(insns)) print(结果寄存器:, result)输出大致是这样t1 3 - 4 t2 2 * t1 t3 1 t2 结果寄存器: t3到这儿你已经完整走过了“字符→记号→树→线性指令”的路径虽然产物还不能真的在 CPU 上跑但编译器的骨架已经立起来了。接下来所有扩展都是在这个骨架上加东西加变量就扩符号表加控制流就在生成阶段插标号和跳转加函数就在调用点处理参数传递和返回约定。这条路径我走过好几遍比看任何章节都管用。顺手加一个小实验在new_temp里加上可选的复用逻辑或者写一个“常量折叠”的 pass遍历 AST 时发现左右子树都是数字就直接算出来你会发现这个“优化”用十几行代码就实现了而且效果肉眼可见。这种即时正反馈对坚持学下去特别重要。4. 工具选型别一上来就硬搓4.1 手写、生成器、现成框架怎么选“自己写还是用工具”这个问题没有标准答案取决于你处在什么阶段、要解决什么问题。我把常见的三条路线列出来附上各自的代价。路线代表做法上手成本灵活度适合场景纯手写自己实现扫描器 递归下降低但规则多了容易乱极高学习、语法简单的 DSL、嵌入式小解析器词法/语法生成器写文法文件工具生成分析器代码中需要学工具的语法和调试方式中受工具约束语法规则多、需要稳定错误恢复解析框架/组合子用库提供的组合子函数拼装规则低中高快速原型、规则不复杂的配置解析完整编译器基础设施使用成熟的中间表示加后端高高真正要做一门语言、需要优化和跨平台对新手我的建议很明确第一遍手写第二遍用生成器。手写是为了理解机制你知道每一层怎么来的报错时能定位到根上用生成器是为了理解工具的价值边界知道哪些活可以交出去、哪些必须自己控。只走第一条路容易变成“什么都自己造”只走第二条路容易变成“出了错完全不知道从哪查”。选生成器时有个坑要提醒文法文件的调试体验通常比手写代码差很多冲突报告往往只给你一个状态编号和一个移进/归约冲突的提示新手看了一头雾水。这时候的排查顺序是先确认文法是否真的有二义性大概率有再检查优先级声明是否写全最后才怀疑工具配置。我见过太多人卡在“表达式优先级”上其实加三行优先级声明就解决了。还有一类工具值得单独提语法分析框架里的“解析表达式文法”那一族。它特别适合表达式密集的场景写一条规则就能自动处理左递归和优先级缺点是对复杂语句结构的表达不如传统文法直观。如果你只是要解析配置、公式、查询条件这类工具能省一大半时间。4.2 学习路径上的几个关键节点我把新手到能用的路径分成四个阶段每个阶段给自己定一个可验收的产出验收不过就不要往下走否则一定是空中楼阁。第一阶段能跑通。产出就是上面那个表达式编译器能处理加减乘除括号负数能生成三地址码。验收标准是准备二十条手工用例包括各种边界空输入、只有括号、连续负号、除零全部通过。第二阶段能报错。加上精确的错误位置和可读的错误信息。验收标准是拿一段故意写错的输入报错必须指出行号、列号、期望什么、实际遇到什么。这一步看似简单实际上会把你的架构问题暴露得很彻底——如果你的 token 不带位置这里就得大改。第三阶段有结构。加变量、赋值、语句块、条件分支让符号表真正发挥作用。验收标准是能写出一个带 if-else 的小程序并且正确求值。这个阶段会第一次遇到“控制流怎么翻译成跳转”的问题也是从表达式解析迈进真正编译的门槛。第四阶段有优化。加两三个简单的 pass比如常量折叠、死代码消除。验收标准是同一个程序在优化前后的执行结果完全一致且中间代码条数明显减少。这个阶段最重要的是建立“回归测试”的习惯因为优化是唯一会悄悄改变语义的环节。我特别想强调第三阶段的价值。很多教程止步于表达式求值导致学完之后不知道“真正的语言”长什么样。其实从表达式到语句跨越的核心就一个控制流的线性化。if (cond) A else B翻译成“条件跳转 标号 跳转 标号”while翻译成“标号 条件跳转 循环体 回跳”。这两条翻译规则一旦掌握你就具备了编译任意结构化控制流的能力。5. 新手最容易踩的坑与排查实录5.1 词法与语法的边界之争新手最常问的一个问题-号到底该归词法还是语法答案是看它的语义角色。当它出现在两个操作数之间它是二元减号由语法分析按规则处理当它出现在表达式开头或者左括号之后它是一元负号也由语法分析处理。词法层只负责识别出“这是一个减号记号”不负责判断它扮演什么角色。这个分工如果搞混你会看到有人试图在词法分析里根据前一个记号来决定输出什么——那会立刻陷入上下文敏感的泥潭。同理和的切分是纯词法问题靠最长匹配解决而a b是否合法是语法问题a和b类型是否可比较是语义问题。这三层职责划清楚90% 的“这个该放哪里”的困惑会自动消失。我自己的判断口诀是看字符本身就能决定的放词法看记号关系才能决定的放语法看名字和类型才能决定的放语义。还有一类边界情况值得单独说换行敏感的语言。有些语言里换行有语义比如语句结束有些语言里没有完全靠分号。如果你在做一个换行敏感的语言词法分析器就必须输出“换行”记号并且语法分析要小心处理“行末是否允许续行”的规则。这件事没有通用答案完全取决于你要模仿的语言风格务必先想清楚再动手。5.2 左递归、优先级与结合性三个问题经常一起出现我把它们放在一起讲因为它们的根都是“文法怎么设计”。左递归的症状是解析器一进函数就无限递归、栈溢出。诊断方法很直接看你的parse_expr第一行是不是又调用了自己。修复方法是改写成A : B (op B)*的形式代码里变成一个前置调用加 while 循环。优先级的症状是23*4算出 20。诊断方法是把语法树打印出来看乘号是不是比加号更靠近叶子节点。修复方法是分层——每一层只处理一组同优先级的运算符低优先级在高层、高优先级在低层从expr往下依次是term、factor。结合性的症状是10-3-2算出 9左结合正确而不是 5右结合错误或者幂运算2^3^2算成 64右结合正确而不是 512。诊断方法是把嵌套结构打印出来看左子树还是右子树更深。修复方法是循环解析的方向——左结合用while往后吃右结合用递归往后吃。把这三个问题的现象、诊断、修复整理成一张表方便排查时对照现象最可能的原因诊断手段修复方式栈溢出、无限递归文法存在左递归打印调用栈看循环点改写成迭代或右递归23*4得 20优先级未分层打印 AST 看结构按优先级拆成多层规则10-3-2得 9 或 5 异常结合性方向错打印 AST 看嵌套方向调整循环/递归方向(12)*3解析失败括号内调用了低层规则检查 factor 内的调用括号内应调用最高层规则报错位置偏移一位列号从 0 开始或未处理换行用多行用例验证统一行列起始与更新逻辑提示调试语法问题最有效的手段不是打断点而是打印缩进形式的语法树。一个能把 AST 打印成缩进文本的十行函数价值超过任何调试器因为你能一眼看出结构是否符合预期。5.3 常见问题速查表与排查顺序把经常遇到的问题摊开说这部分是我从无数次踩坑中攒下来的。问题排查思路常见根因报错指向的位置不对检查 token 是否记录了绝对偏移行列更新是否在跳过空白时也执行了只对非空白 token 更新位置导致空白被跳过时位置不同步表达式算出来全错但语法通过打印 AST检查运算符与左右子树的对应关系递归时把左右参数传反了小数运算出现奇怪尾数确认中间表示里常量的类型直接用了二进制浮点未做精度处理大数字被截断检查数值解析是否有限制用了固定宽度整数未做溢出检查输入包含中文或特殊符号时崩溃检查扫描器对未知字符的处理没有兜底的“非法字符”分支嵌套很深的表达式栈溢出检查递归深度考虑改成显式栈递归下降的固有局限错误信息只有“语法错误”四个字检查异常是否带上下文没有把 token 位置和期望集合带进异常排查顺序我建议固定成一条线避免乱试先看 token 流再看语法树再看中间代码最后看执行结果。原因是流水线是单向的上游错了一定导致下游错但下游错了不代表上游有问题。很多人一上来就盯着生成的三地址码看其实问题在词法阶段漏掉了一个记号。还有一个经验值得分享给每一层写一个“可视化打印”函数。token 列表打印成表格AST 打印成缩进文本中间代码就是有序列表。这三个函数加起来不超过五十行但它们是你调试时的眼睛。我在带新人的时候第一件事就是要求他把这三个函数写出来然后才允许写业务逻辑——事实证明没有这三双眼睛的人调 bug 的时间是有的三倍以上。再提一个容易被忽略的点测试用例的组织。不要用随机数字测要用有设计意图的用例。我会分四组正常路径各种优先级组合、边界路径空输入、单数字、纯括号、深层嵌套、错误路径缺右括号、连续运算符、非法字符、以及一组“回归用例”之前修过的 bug 对应的输入。这四组跑通基本能保证重构时不翻车。最后说一个我自己的教训。第一次实现时我把所有错误都抛同一个异常不加任何信息结果测试时看到“SyntaxError”完全不知道哪错了只能一行行打印调试。后来改成携带位置、期望集合、实际记号三个字段调试效率立刻提升一个档。错误信息不是给用户看的装饰品它是你调试时最重要的信息来源在编译器这种阶段多、链路长的系统里这条尤其成立。下一步如果继续往下走自然的延伸方向是加变量和语句块让符号表真正跑起来然后是控制流的线性化再往后才是类型系统和优化。这条路我走了挺久走走停停但每次回头看那些当初觉得抽象的符号和公式都能对上号了——它们不是凭空造出来的理论而是对“怎么把一门语言忠实地翻译过去”这件事的精确描述。 
长河君 · 2026/10/26 19:14:15 · 阅读 1.2k 编译原理入门：编译器工作流程与递归下降解析实践
编译原理这四个字在很多人的学习清单里排位都挺尴尬——知道它重要知道面试偶尔会问也知道看懂了能“开天眼”但真翻开书前面几页的字母表、符号串、闭包就把人劝退了。我自己第一次接触编译原理也是这个状态啃了两章文法合上书只记得几个希腊字母。后来真正在做项目时被迫写了一个小型的表达式解析器才算把书本上那些抽象符号和真实代码对上号。这篇入门介绍就是写给当时那个自己的不堆数学证明不急着推自动机先把“编译器到底在干什么”“整条流水线怎么串起来”“新手第一段代码该写什么”讲清楚。这篇适合谁看零基础但想搞明白原理的在校同学、写了几年业务代码想往底层走一步的开发者、需要给项目写配置解析或者规则引擎的工程师还有那些纯粹被“编译原理”这四个字吓退过、想找个不那么吓人的入口的人。关键词就三个编译原理、编译器工作流程、递归下降。读完之后你至少能做到两件事说清楚源代码从字符到机器指令经历了哪几步、每一步输入输出是什么以及自己动手写出一个能算加减乘除带括号的小型“编译器”先把流程跑通。1. 先搞清楚编译器到底在干什么1.1 一个翻译官的类比比任何定义都好用把编译器想象成一位翻译官这个类比虽然老套但真的有效。你写的高级语言代码相当于一封用中文写的信CPU 只认识机器指令相当于只懂某种外语的收信人。翻译官的工作不是逐字替换而是先读懂整封信的意思再按照对方的语言习惯重新组织句子最后才落笔。如果只是逐字查词典替换结果一定是语法不通的这就是为什么“简单替换”做不出编译器。这个类比里藏着两个关键判断第一编译是分阶段的读信、理解、组织、落笔是不同工序每道工序的产出物不一样第二编译是保语义的翻译完的信必须和原信意思一致否则翻译就是错的。后一点经常被新手忽略——很多人写解析器时只管“能跑通”结果23*4算出来是 20 而不是 14语法全对、语义全错这种 bug 恰恰是编译器最不该犯的。按业界的通俗定义编译器是把一种语言源语言写成的程序整体转换成另一种语言目标语言写成的程序。注意“整体”两个字这正是它和解释器的分水岭。编译器拿到完整的源文件后才开工产出的是一个新的产物目标文件、字节码、另一段代码解释器则是边读边执行读一行做一行不产生独立产物。两者的差异直接决定了错误发现时机、执行性能和调试体验下一节展开说。还有一类经常被混为一谈的东西预处理器、转换器、编译器前端库。预处理器只做文本级替换不理解语法#define那种宏展开就是典型转换器是把一种高级语言变成另一种高级语言比如把某个新语法编译成老版本语法产出仍是源代码而编译器前端库只负责“读懂”把源码变成结构化表示接不接后端由你决定。搞清自己要做的是哪一类选型才不会跑偏。1.2 编译器、解释器、混合模式三条路线怎么选新手最常见的困惑是既然解释器能直接跑为什么还要费劲编译答案在于代价的分配位置不同。编译把开销前置一次翻译、多次执行适合反复运行的场景解释把开销后置改一行立刻能跑适合迭代频繁的调试场景。这不是技术优劣是工程权衡。维度编译器解释器混合模式先编译成字节码再解释/JIT产出物目标机器码或字节码文件无独立产物直接执行中间表示字节码启动速度慢需要先编译快边读边跑中等需先生成中间表示执行速度快可做深度优化慢每次都要解析快热点代码可优化错误发现编译期集中报错运行到哪错到哪编译期报语法错运行时报类型错调试体验源码与目标码有映射需调试信息直接对应源码需要映射表典型适用交付部署、嵌入式、性能敏感脚本、配置、一次性任务通用语言运行时、大型应用我个人的经验是学习阶段优先做编译器不要做解释器。原因很实在——编译器有明确的产物你可以把中间结果打印出来对照检查词法分析完了看 token 列表语法分析完了看语法树每一步都能验证对错解释器边读边跑出错时你很难判断是解析错了还是执行错了。等流程跑通了再把“执行”这一步接上去它就是一个解释器了成本极低。至于混合模式值得多说一句。它本质上是把“编译”这一步的目标语言选成了自己设计的字节码而不是真实 CPU 指令于是获得了可移植性执行时再用一个虚拟机去解释这些字节码或者把热点部分即时编译成机器码。这条路线的复杂度在于虚拟机的设计与优化策略新手阶段完全不必碰但要知道它存在理解“编译目标不一定是机器码”这一点对后面理解中间表示非常有帮助。1.3 为什么新手也该啃这块硬骨头先说功利的部分。你日常用的构建工具、模板引擎、正则引擎、ORM 的查询构造、前端框架的模板编译、IDE 的语法高亮与跳转、Lint 规则的实现背后全是编译原理的东西。搞懂了词法分析和语法分析你再去读那些“看起来像黑魔法”的库会突然发现它们的骨架很朴素切词、建树、遍历、输出。这种“祛魅”的体验是其他知识很难给的。再说思维层面。编译原理训练的是分层抽象的能力把一个大问题拆成若干阶段每个阶段只做一件事阶段之间用明确的数据结构通信。这个套路不只用于编译器。你写一个数据导入模块天然就是“读取→解析→校验→转换→落库”五段式你做一个规则引擎天然就是“切词→建条件树→求值”。我带过几个刚工作的同学明显感觉到系统学过编译原理的人写这类转换逻辑时结构更清晰因为他们下意识就在做阶段划分。最后说长期价值。抽象语法树、中间表示、静态类型检查这些概念在数据库SQL 解析与优化、硬件设计综合工具、AI 领域计算图编译、算子融合里全都出现了类似的结构。你今天花在理解 AST 上的时间会在未来某个完全不相干的场景里回报你。顺手提一句新手最容易走的弯路一上来就抱着龙书死磕形式语言与自动机理论。理论当然要学但它和“动手写一个能跑的东西”之间有个巨大的鸿沟先跨过去再回头补理论效率高得多。这是我踩过的坑——第一遍学的时候把大量时间花在证明 NFA 到 DFA 的等价性上结果连一个 token 流都没切出来过挫败感极强。2. 把编译流程拆成一条流水线2.1 词法分析把字符流切成有意义的“单词”词法分析是整个流水线的第一道工序任务简单但极其关键把一串字符12*(3-4)切成一个个有类型的记号token并且丢掉空格、换行这类无意义字符。输出通常是一个 token 列表每个 token 带上类型、原始文本、以及它在源码里的位置行号、列号、起止偏移。位置信息千万别省后面报错全靠它。为什么要有这一步因为后续的语法分析关心的是“加法符号”这个抽象概念而不是 ASCII 码里那个 43 号字符。词法分析把字符级的细节收敛成类型化的记号让语法分析可以在更高层次上工作。这就是分层的价值——每一层都隐藏下一层的复杂度。具体怎么切最常用的做法是正则匹配 最长匹配 关键字优先。你为每种 token 定义一个正则模式然后从左到右扫描每次尝试匹配选最长的那个成功匹配。这条“最长匹配”规则很重要遇到时绝不能先匹配到就收手否则后面那个会变成一个孤立的记号语法分析直接崩。同理遇到if这种关键字它同时也符合“标识符”的模式所以必须先判断关键字集合再走标识符规则。注意很多正则引擎默认行为是贪婪匹配但这和“词法规则的最长匹配”不完全是一回事。手写扫描器时规则的书写顺序决定了匹配优先级一定要把更具体、更长的规则排在前面把通用规则标识符、数字排在后面。这里有个隐性的坑值得提前说绝大多数教材用正则表达式来定义 token但正则文法处理不了嵌套结构比如括号配对、块注释/* ... /* ... */ ... */。所以凡是涉及嵌套的部分必须在词法层用状态机手工处理别硬塞进正则里。我见过有人为了匹配嵌套注释写了一百多字符的正则最后既跑不动也改不动。2.2 语法分析检查句子结构是否成立拿到 token 流之后语法分析的任务是判断这串记号能不能按语法规则组合成合法结构并且把这种结构显式地表达出来——这个表达就是抽象语法树AST。注意是“抽象”语法树不是“具体”语法树具体树里会保留括号、分号这些分隔符节点抽象树里把它们去掉只留下真正承载语义的结构。语法规则怎么描述业界通用的是巴科斯范式BNF及其变体。举个最简的例子四则运算的规则可以写成expr : term (( | -) term)* term : factor ((* | /) factor)* factor : NUMBER | ( expr ) | - factor这三行规则信息量很大。它把“加减”和“乘除”拆成两个层级天然表达了乘除优先级高于加减它把括号写成“一个 factor 可以是括号包起来的 expr”这是递归的体现也是上下文无关文法能描述嵌套结构的根本原因它用*表示“重复零次或多次”避免了直接写左递归。说到左递归这是新手必踩的坑。教科书写expr : expr term看起来很自然但如果你用递归下降的方式实现函数parse_expr第一件事就是调用parse_expr直接栈溢出。解决办法是把它改写成等价的右递归或者循环形式也就是上面那种term (( | -) term)*的写法。递归下降天然适合处理右递归处理左递归要靠消除或改写成循环记住这条能省下好几个小时的调试。语法分析的实现路线大致分三派手写递归下降、表驱动的自底向上分析LR 系列、以及用生成器自动产出。新手阶段强烈建议手写递归下降理由很直接——它和文法规则几乎一一对应你看着 BNF 就能写出代码出错时也容易定位到具体规则上。等到规则规模大到几十上百条再考虑上生成器。2.3 语义分析语法对了不代表讲得通“ colorless green ideas sleep furiously ”这句话语法完全正确但语义荒诞。编译器也一样a b结构没问题但如果a是个整数、b是个字符串这就讲不通了。语义分析要干的就是这类活维护符号表、检查类型、检查作用域、检查变量是否声明、函数调用参数个数是否匹配。符号表是这一阶段的核心数据结构本质是一个从名字到信息的映射信息包括类型、作用域层级、存储位置、是否已初始化等。麻烦的是作用域是嵌套的所以常见的实现是“栈式符号表”或者“链式作用域”进入一个块就压一层离开就弹一层查找时从内向外逐层找。你要是只用一个扁平字典遇到同名变量遮蔽的场景必然出错。检查项典型错误示例发现阶段处理方式变量未声明使用x但从未定义语义分析报错并标注位置类型不匹配整数与字符串相加语义分析报错或按规则隐式转换重复定义同一作用域内两次定义同名变量语义分析报错调用参数不符函数声明两个参数调用传了三个语义分析报错控制流缺失返回非 void 函数某分支没有 return语义分析警告或报错不可达代码return 之后还有语句语义分析或优化警告优化阶段删除我个人的体会是语义分析这一层最容易被新手跳过因为它不像词法和语法那样“能画图”但它恰恰是决定你的实现是“玩具”还是“能用”的分界线。一个只做语法检查的解析器遇到用户写错变量名时只能干瞪眼加上符号表之后报错信息立刻从“语法错误”变成“第 12 行变量count未声明是否想用counter”体验差一个量级。2.4 中间代码、优化与目标代码从“能跑”到“跑得快”语义检查通过之后很多教材会直接跳到目标代码生成这是不对的。中间代码这一步不能省原因是它把“语言相关的部分”和“机器相关的部分”彻底解耦。前端词法、语法、语义负责理解源语言后端优化、代码生成负责适配目标机器中间代码是两者之间的契约。有了这层契约一个前端可以接多个后端多平台支持一个后端也可以接多个前端多语言支持这是现实中主流编译器架构的基本形态。最经典的中间表示是三地址码每条指令最多包含一个运算符、两个源操作数、一个目标操作数形如t1 a b。它的好处是结构规整、容易分析和变换控制流可以表示成基本块加跳转数据流分析也能直接在它上面做。往上还有更抽象的形式比如带类型的树形表示、往下还有更接近机器的形式比如带虚拟寄存器的线性表示新手从三地址码入手最合适因为它既能手写生成、又能肉眼验证。优化就建立在中间表示之上。常见的入门级优化有几类常量折叠编译期能算出来的就提前算2 * 3直接变成6。常量传播把已知的常量值传播到使用点配合折叠效果更好。公共子表达式消除同一个表达式算了两遍第二遍直接复用结果。死代码消除算了但没人用的结果、永远走不到的分支删掉。强度削弱把昂贵的运算换成便宜的比如乘以 2 的幂换成移位。注意优化的第一原则是不能改变程序的可观测行为。新手最容易在这里翻车——把带副作用的表达式当纯表达式折叠了或者重排了有依赖的读写顺序。每次写完一个优化必须拿一批用例回归尤其是带边界值、带副作用、带异常的用例。目标代码生成是最后一公里把中间表示翻译成目标机器的指令同时解决寄存器分配这个老大难问题。寄存器数量有限变量一大堆谁进寄存器、谁溢出到内存需要一套分配算法图着色是经典方案。这部分对新手来说可以先简化假设寄存器无限多先把指令生成跑通等真需要性能了再回来处理分配。我在第一次实现时死磕寄存器分配结果卡了两周毫无进展后来退回去用“无限寄存器 后处理溢出”的方案一天就跑通了这个取舍非常值。把六个阶段串起来整条流水线的输入输出关系可以这样记阶段输入输出新手常见错误词法分析字符流token 列表不处理最长匹配、丢失位置信息语法分析token 列表抽象语法树左递归导致栈溢出、优先级层次搞错语义分析语法树 符号表带类型标注的语法树作用域扁平化、不做类型检查中间代码生成标注后的语法树三地址码 / 中间表示临时变量命名冲突、求值顺序错乱优化中间表示优化后的中间表示破坏语义、忽略副作用目标代码生成优化后的中间表示汇编或机器码寄存器冲突、调用约定不匹配3. 动手写一个最小可用的表达式编译器3.1 先把边界定死支持什么、不支持什么动手之前一定要先划范围这是我踩坑最多的地方。第一次写的时候雄心勃勃想支持变量、函数、循环、字符串结果写到一半发现符号表设计撑不住推倒重来。后来学乖了第一版只做四则运算加括号加一元负号输入是一个字符串输出是三地址码列表。功能极窄但流程完整从切词到生成代码一步不缺。第一版的能力边界支持整数和浮点数常量浮点只是为了演示实际项目中我会用定点或直接报错。支持 - * /四则运算-既可以做二元减号也可以做一元负号。支持圆括号改变优先级。不支持变量、不支持函数调用、不支持赋值。遇到任何非法输入抛出带位置信息的异常。这个范围小到一天能写完但它逼着你把词法、语法、代码生成三个环节全部走一遍而且每一步的中间结果都能打印出来肉眼核对。先用最小闭环跑通再逐步加特性这个方法论适用于几乎所有工程问题在编译器上尤其明显因为它的阶段耦合度很高一步错后面全错。3.2 词法分析器四十行代码的核心逻辑下面这个实现用正则规则表驱动扫描核心是“按顺序尝试、取第一个成功匹配、跳过空白”。这个写法不够高效每次都切片重建字符串但足够清晰适合新手理解。import re # 规则顺序很重要更具体的规则必须排在通用规则前面 TOKEN_RULES [ (NUMBER, r\d(?:\.\d)?, ), # 整数或小数 (PLUS, r\), (MINUS, r-), (STAR, r\*), (SLASH, r/), (LPAREN, r\(), (RPAREN, r\)), (SPACE, r[ \t\r\n]), ] COMPILED [(kind, re.compile(pat)) for kind, pat, in [(k, p) for k, p in TOKEN_RULES]] def tokenize(src: str): pos 0 line, col 1, 1 tokens [] while pos len(src): for kind, pattern in COMPILED: m pattern.match(src, pos) if not m: continue text m.group(0) start_line, start_col line, col # 更新行列号按换行符切分统计 newlines text.count(\n) if newlines: line newlines col len(text) - text.rfind(\n) else: col len(text) pos m.end() if kind ! SPACE: tokens.append({ kind: kind, text: text, line: start_line, col: start_col, }) break else: raise SyntaxError( f第 {line} 行第 {col} 列出现无法识别的字符 {src[pos]!r} ) tokens.append({kind: EOF, text: , line: line, col: col}) return tokens几个值得说的细节。第一我用pattern.match(src, pos)而不是对切片做匹配这样避免了每次创建新字符串同时也让m.end()直接给出新位置代码更干净。第二行号列号的更新必须精确text.rfind(\n)那个写法是为了处理“一段文本里有多个换行”的情况col应该重置到最后一个换行之后。第三末尾补一个EOF记号这是为了让语法分析器不用到处判断“是不是到头了”统一处理会省很多边界代码。注意src.rfind那段在多换行时有个细节——len(text) - text.rfind(\n)得到的是最后一行的字符数但它从 1 开始计数所以列号是准的。这类“差一”错误极其常见写完务必用手工构造的用例验证一遍比如1 \n 2确认第二行的2列号是 3 而不是 2。再加一句关于浮点的提醒上面用了float纯粹是为了 demo 简洁。真做语言实现浮点数会牵扯精度、舍入、NaN、比较语义一大堆问题我建议第一版要么只支持整数要么把数值类型做成显式的结构体别偷懒用float。3.3 递归下降解析器看着文法写代码有了 token 流接下来按文法写三个函数一层管一个优先级。这个结构的好处是函数与文法规则一一对应改动文法时改哪个函数非常明确。class Parser: def __init__(self, tokens): self.tokens tokens self.pos 0 def peek(self): return self.tokens[self.pos] def advance(self): tok self.tokens[self.pos] self.pos 1 return tok def expect(self, kind): tok self.peek() if tok[kind] ! kind: raise SyntaxError( f第 {tok[line]} 行第 {tok[col]} 列 f期望 {kind}实际遇到 {tok[kind]}({tok[text]!r}) ) return self.advance() # expr : term (( | -) term)* def parse_expr(self): node self.parse_term() while self.peek()[kind] in (PLUS, MINUS): op self.advance()[kind] right self.parse_term() node {type: binop, op: op, left: node, right: right} return node # term : factor ((* | /) factor)* def parse_term(self): node self.parse_factor() while self.peek()[kind] in (STAR, SLASH): op self.advance()[kind] right self.parse_factor() node {type: binop, op: op, left: node, right: right} return node # factor : NUMBER | ( expr ) | - factor def parse_factor(self): tok self.peek() if tok[kind] NUMBER: self.advance() return {type: num, value: tok[text]} if tok[kind] LPAREN: self.advance() node self.parse_expr() self.expect(RPAREN) return node if tok[kind] MINUS: self.advance() return {type: neg, operand: self.parse_factor()} raise SyntaxError( f第 {tok[line]} 行第 {tok[col]} 列 f无法作为表达式开头{tok[kind]}({tok[text]!r}) ) def parse(self): node self.parse_expr() self.expect(EOF) return node注意while循环那段它替代了左递归。文法写的是expr : expr term代码写成“先解析一个 term然后只要看到加号就继续吃”这本质上是把左递归改造成了迭代。这个转换是机械的记住模板就行A : A op B | B等价于A : B (op B)*代码里就是一个前置调用加一个循环。再看parse_factor里对括号的处理——它调用parse_expr而不是parse_term这是必须的因为括号里的内容可以是完整的加减表达式。如果这里写成parse_term(12)*3就会解析失败。同理一元负号的处理放在factor层意味着-2*3会被解析成(-2)*3而不是-(2*3)这在数值上恰好等价但在引入函数调用或更复杂的前缀运算符时优先级归属就必须仔细推敲了。3.4 从直接求值到生成三地址码最省事的做法是解析完直接在树上递归求值二十行搞定def evaluate(node): t node[type] if t num: return float(node[value]) if t neg: return -evaluate(node[operand]) left, right evaluate(node[left]), evaluate(node[right]) op node[op] if op PLUS: return left right if op MINUS: return left - right if op STAR: return left * right if op SLASH: if right 0: raise ZeroDivisionError(除数为零) return left / right raise ValueError(f未知运算符 {op})但求值这一步掩盖了大量信息你没法看到“编译器怎么把一棵树变成线性指令”。所以第二步我强烈建议补上三地址码生成这段代码是整个流程里最有“编译器味道”的部分class CodeGen: OP_MAP {PLUS: , MINUS: -, STAR: *, SLASH: /} def __init__(self): self.counter 0 self.insns [] def new_temp(self): self.counter 1 return ft{self.counter} def gen(self, node): t node[type] if t num: return node[value] # 常量可以直接当操作数用 if t neg: val self.gen(node[operand]) tmp self.new_temp() self.insns.append(f{tmp} -{val}) return tmp # 二元运算先递归生成左右子树再发一条加法类指令 left self.gen(node[left]) right self.gen(node[right]) tmp self.new_temp() op self.OP_MAP[node[op]] self.insns.append(f{tmp} {left} {op} {right}) return tmp def compile(self, ast): result self.gen(ast) return self.insns, result跑一下1 2 * (3 - 4)src 1 2 * (3 - 4) tokens tokenize(src) ast Parser(tokens).parse() insns, result CodeGen().compile(ast) print(\n.join(insns)) print(结果寄存器:, result)输出大致是这样t1 3 - 4 t2 2 * t1 t3 1 t2 结果寄存器: t3到这儿你已经完整走过了“字符→记号→树→线性指令”的路径虽然产物还不能真的在 CPU 上跑但编译器的骨架已经立起来了。接下来所有扩展都是在这个骨架上加东西加变量就扩符号表加控制流就在生成阶段插标号和跳转加函数就在调用点处理参数传递和返回约定。这条路径我走过好几遍比看任何章节都管用。顺手加一个小实验在new_temp里加上可选的复用逻辑或者写一个“常量折叠”的 pass遍历 AST 时发现左右子树都是数字就直接算出来你会发现这个“优化”用十几行代码就实现了而且效果肉眼可见。这种即时正反馈对坚持学下去特别重要。4. 工具选型别一上来就硬搓4.1 手写、生成器、现成框架怎么选“自己写还是用工具”这个问题没有标准答案取决于你处在什么阶段、要解决什么问题。我把常见的三条路线列出来附上各自的代价。路线代表做法上手成本灵活度适合场景纯手写自己实现扫描器 递归下降低但规则多了容易乱极高学习、语法简单的 DSL、嵌入式小解析器词法/语法生成器写文法文件工具生成分析器代码中需要学工具的语法和调试方式中受工具约束语法规则多、需要稳定错误恢复解析框架/组合子用库提供的组合子函数拼装规则低中高快速原型、规则不复杂的配置解析完整编译器基础设施使用成熟的中间表示加后端高高真正要做一门语言、需要优化和跨平台对新手我的建议很明确第一遍手写第二遍用生成器。手写是为了理解机制你知道每一层怎么来的报错时能定位到根上用生成器是为了理解工具的价值边界知道哪些活可以交出去、哪些必须自己控。只走第一条路容易变成“什么都自己造”只走第二条路容易变成“出了错完全不知道从哪查”。选生成器时有个坑要提醒文法文件的调试体验通常比手写代码差很多冲突报告往往只给你一个状态编号和一个移进/归约冲突的提示新手看了一头雾水。这时候的排查顺序是先确认文法是否真的有二义性大概率有再检查优先级声明是否写全最后才怀疑工具配置。我见过太多人卡在“表达式优先级”上其实加三行优先级声明就解决了。还有一类工具值得单独提语法分析框架里的“解析表达式文法”那一族。它特别适合表达式密集的场景写一条规则就能自动处理左递归和优先级缺点是对复杂语句结构的表达不如传统文法直观。如果你只是要解析配置、公式、查询条件这类工具能省一大半时间。4.2 学习路径上的几个关键节点我把新手到能用的路径分成四个阶段每个阶段给自己定一个可验收的产出验收不过就不要往下走否则一定是空中楼阁。第一阶段能跑通。产出就是上面那个表达式编译器能处理加减乘除括号负数能生成三地址码。验收标准是准备二十条手工用例包括各种边界空输入、只有括号、连续负号、除零全部通过。第二阶段能报错。加上精确的错误位置和可读的错误信息。验收标准是拿一段故意写错的输入报错必须指出行号、列号、期望什么、实际遇到什么。这一步看似简单实际上会把你的架构问题暴露得很彻底——如果你的 token 不带位置这里就得大改。第三阶段有结构。加变量、赋值、语句块、条件分支让符号表真正发挥作用。验收标准是能写出一个带 if-else 的小程序并且正确求值。这个阶段会第一次遇到“控制流怎么翻译成跳转”的问题也是从表达式解析迈进真正编译的门槛。第四阶段有优化。加两三个简单的 pass比如常量折叠、死代码消除。验收标准是同一个程序在优化前后的执行结果完全一致且中间代码条数明显减少。这个阶段最重要的是建立“回归测试”的习惯因为优化是唯一会悄悄改变语义的环节。我特别想强调第三阶段的价值。很多教程止步于表达式求值导致学完之后不知道“真正的语言”长什么样。其实从表达式到语句跨越的核心就一个控制流的线性化。if (cond) A else B翻译成“条件跳转 标号 跳转 标号”while翻译成“标号 条件跳转 循环体 回跳”。这两条翻译规则一旦掌握你就具备了编译任意结构化控制流的能力。5. 新手最容易踩的坑与排查实录5.1 词法与语法的边界之争新手最常问的一个问题-号到底该归词法还是语法答案是看它的语义角色。当它出现在两个操作数之间它是二元减号由语法分析按规则处理当它出现在表达式开头或者左括号之后它是一元负号也由语法分析处理。词法层只负责识别出“这是一个减号记号”不负责判断它扮演什么角色。这个分工如果搞混你会看到有人试图在词法分析里根据前一个记号来决定输出什么——那会立刻陷入上下文敏感的泥潭。同理和的切分是纯词法问题靠最长匹配解决而a b是否合法是语法问题a和b类型是否可比较是语义问题。这三层职责划清楚90% 的“这个该放哪里”的困惑会自动消失。我自己的判断口诀是看字符本身就能决定的放词法看记号关系才能决定的放语法看名字和类型才能决定的放语义。还有一类边界情况值得单独说换行敏感的语言。有些语言里换行有语义比如语句结束有些语言里没有完全靠分号。如果你在做一个换行敏感的语言词法分析器就必须输出“换行”记号并且语法分析要小心处理“行末是否允许续行”的规则。这件事没有通用答案完全取决于你要模仿的语言风格务必先想清楚再动手。5.2 左递归、优先级与结合性三个问题经常一起出现我把它们放在一起讲因为它们的根都是“文法怎么设计”。左递归的症状是解析器一进函数就无限递归、栈溢出。诊断方法很直接看你的parse_expr第一行是不是又调用了自己。修复方法是改写成A : B (op B)*的形式代码里变成一个前置调用加 while 循环。优先级的症状是23*4算出 20。诊断方法是把语法树打印出来看乘号是不是比加号更靠近叶子节点。修复方法是分层——每一层只处理一组同优先级的运算符低优先级在高层、高优先级在低层从expr往下依次是term、factor。结合性的症状是10-3-2算出 9左结合正确而不是 5右结合错误或者幂运算2^3^2算成 64右结合正确而不是 512。诊断方法是把嵌套结构打印出来看左子树还是右子树更深。修复方法是循环解析的方向——左结合用while往后吃右结合用递归往后吃。把这三个问题的现象、诊断、修复整理成一张表方便排查时对照现象最可能的原因诊断手段修复方式栈溢出、无限递归文法存在左递归打印调用栈看循环点改写成迭代或右递归23*4得 20优先级未分层打印 AST 看结构按优先级拆成多层规则10-3-2得 9 或 5 异常结合性方向错打印 AST 看嵌套方向调整循环/递归方向(12)*3解析失败括号内调用了低层规则检查 factor 内的调用括号内应调用最高层规则报错位置偏移一位列号从 0 开始或未处理换行用多行用例验证统一行列起始与更新逻辑提示调试语法问题最有效的手段不是打断点而是打印缩进形式的语法树。一个能把 AST 打印成缩进文本的十行函数价值超过任何调试器因为你能一眼看出结构是否符合预期。5.3 常见问题速查表与排查顺序把经常遇到的问题摊开说这部分是我从无数次踩坑中攒下来的。问题排查思路常见根因报错指向的位置不对检查 token 是否记录了绝对偏移行列更新是否在跳过空白时也执行了只对非空白 token 更新位置导致空白被跳过时位置不同步表达式算出来全错但语法通过打印 AST检查运算符与左右子树的对应关系递归时把左右参数传反了小数运算出现奇怪尾数确认中间表示里常量的类型直接用了二进制浮点未做精度处理大数字被截断检查数值解析是否有限制用了固定宽度整数未做溢出检查输入包含中文或特殊符号时崩溃检查扫描器对未知字符的处理没有兜底的“非法字符”分支嵌套很深的表达式栈溢出检查递归深度考虑改成显式栈递归下降的固有局限错误信息只有“语法错误”四个字检查异常是否带上下文没有把 token 位置和期望集合带进异常排查顺序我建议固定成一条线避免乱试先看 token 流再看语法树再看中间代码最后看执行结果。原因是流水线是单向的上游错了一定导致下游错但下游错了不代表上游有问题。很多人一上来就盯着生成的三地址码看其实问题在词法阶段漏掉了一个记号。还有一个经验值得分享给每一层写一个“可视化打印”函数。token 列表打印成表格AST 打印成缩进文本中间代码就是有序列表。这三个函数加起来不超过五十行但它们是你调试时的眼睛。我在带新人的时候第一件事就是要求他把这三个函数写出来然后才允许写业务逻辑——事实证明没有这三双眼睛的人调 bug 的时间是有的三倍以上。再提一个容易被忽略的点测试用例的组织。不要用随机数字测要用有设计意图的用例。我会分四组正常路径各种优先级组合、边界路径空输入、单数字、纯括号、深层嵌套、错误路径缺右括号、连续运算符、非法字符、以及一组“回归用例”之前修过的 bug 对应的输入。这四组跑通基本能保证重构时不翻车。最后说一个我自己的教训。第一次实现时我把所有错误都抛同一个异常不加任何信息结果测试时看到“SyntaxError”完全不知道哪错了只能一行行打印调试。后来改成携带位置、期望集合、实际记号三个字段调试效率立刻提升一个档。错误信息不是给用户看的装饰品它是你调试时最重要的信息来源在编译器这种阶段多、链路长的系统里这条尤其成立。下一步如果继续往下走自然的延伸方向是加变量和语句块让符号表真正跑起来然后是控制流的线性化再往后才是类型系统和优化。这条路我走了挺久走走停停但每次回头看那些当初觉得抽象的符号和公式都能对上号了——它们不是凭空造出来的理论而是对“怎么把一门语言忠实地翻译过去”这件事的精确描述。