1. 项目概述为什么我们要“手搓”一个编译器如果你是一名程序员每天敲着if、for、int这些关键字看着代码在屏幕上运行有没有那么一刻好奇过你写的这些文本机器到底是怎么“看懂”并执行的呢编译器就是这个将人类可读的“高级语言”翻译成机器可执行的“低级语言”的神秘黑盒。网上总有人讨论“手搓编译器”听起来高深莫测仿佛是大神们的专属领域。但今天我想告诉你从零构建一个能处理简单算术表达式的编译器其核心思想远比想象中直观。这不仅是计算机科学的一次深刻实践更是理解编程语言本质、提升代码抽象能力的绝佳路径。无论你是想夯实基础的学生还是希望深入理解工具链的开发者这个项目都能让你对“代码如何变成程序”有一个清晰、透彻的认识。我们这次的目标很明确不依赖任何庞大的编译器框架如LLVM、GCC纯粹用你熟悉的编程语言比如Python、Java或C实现一个能处理类似(3 5) * 2这样表达式的微型编译器。最终它能将这段文本转换成某种形式的低级代码比如汇编指令或虚拟机字节码。整个过程我们将拆解为三个经典阶段词法分析、语法分析和代码生成。别被术语吓到接下来我会用最“说人话”的方式带你一步步走完这个奇妙的旅程。2. 核心思路与整体设计编译器的“流水线”模型一个典型的编译器工作流程很像一条工厂流水线。原材料源代码文本从一端进入经过多个车间的加工最终成品目标代码从另一端出来。我们的微型编译器将模拟这条流水线的核心部分。2.1 编译器核心阶段拆解词法分析Lexical Analysis这是流水线的第一个车间任务是把一长串字符流“切碎”成有意义的单词Token。想象一下读英文句子你会自然地把“I love programming”分成“I”、“love”、“programming”三个单词。编译器也一样它会把(35)*2切分成左括号、数字3、加号、数字5、右括号、乘号、数字2。每个“单词”都会被打上标签比如NUMBER、PLUS、MULTIPLY、LPAREN等。这个阶段不关心单词之间的关系只负责识别和分类。语法分析Syntax Analysis第二个车间接收来自词法分析的一串Token然后检查它们是否符合预定的语法规则并构建出一棵“语法树”。这就像检查“I programming love”是否符合英语的语法结构。对于表达式(35)*2语法分析器会识别出这是一个乘法运算乘法的左操作数是一个括号内的加法表达式(35)右操作数是数字2。最终形成的树状结构抽象语法树AST清晰地表达了运算的优先级和结合性。代码生成Code Generation最后一个车间遍历语法树为每一个树节点生成对应的低级指令。比如遇到加法节点就生成一条加法指令遇到乘法节点就生成一条乘法指令。同时它还需要处理运算顺序、临时变量的分配等问题。最终输出可能是一段简单的汇编代码或者是一种自定义的栈式虚拟机指令。2.2 我们的技术选型与设计考量为什么选择实现一个算术表达式编译器作为起点目标聚焦算术表达式涵盖了编译器处理的核心问题运算符优先级乘除高于加减、结合性左结合、括号改变优先级。解决了它就理解了编译器处理复杂结构的基础。闭环验证输入是字符串输出是可计算的结果或低级代码整个流程可以形成一个完整的、可验证的闭环成就感强。易于扩展在此框架上后续可以相对容易地加入变量赋值、控制流if/while、函数调用等特性。关于实现语言的选择我推荐使用Python。原因如下开发效率高Python强大的字符串处理能力和清晰的数据结构列表、字典、类能让快速原型开发。聚焦算法逻辑无需过多关注内存管理等底层细节可以把精力完全集中在编译原理的核心算法上。可视化调试方便可以轻松打印和查看Token流、语法树的结构便于理解和调试。当然你用C或Java来实现也完全可以这能让你对性能和控制有更深体会。但首次实践我强烈建议用Python来降低入门门槛先跑通整个流程建立信心。注意这个项目的目的不是打造一个产品级的编译器而是教学和深刻理解。我们会刻意简化很多工业级编译器需要考虑的复杂问题如类型系统、优化、错误恢复等直击最核心的骨架。3. 第一阶段实战词法分析器Lexer的实现词法分析器我们常亲切地称之为“分词器”。它的任务就是读入源代码字符串输出一个标记Token序列。3.1 Token的设计与定义首先我们需要定义我们的“单词”有哪些类型。对于算术表达式我们至少需要以下几种# 定义Token类型 TT_INT INT # 整数如 3, 42 TT_FLOAT FLOAT # 浮点数如 3.14 (我们本次简化只处理整数) TT_PLUS PLUS # 加号 TT_MINUS MINUS # 减号 - TT_MUL MUL # 乘号 * TT_DIV DIV # 除号 / TT_LPAREN LPAREN # 左括号 ( TT_RPAREN RPAREN # 右括号 ) TT_EOF EOF # 文件结束符表示输入已处理完毕 class Token: def __init__(self, type_, valueNone): self.type type_ # Token类型如 TT_INT self.value value # Token的值如对于数字Tokenvalue就是具体的数字3 def __repr__(self): return fToken({self.type}, {self.value}) if self.value else fToken({self.type})3.2 构建Lexer逐字符扫描的艺术Lexer的核心是一个指针pos它从头到尾扫描输入字符串根据当前字符决定生成什么Token。class Lexer: def __init__(self, text): self.text text # 源代码字符串 self.pos 0 # 当前字符索引位置 self.current_char self.text[self.pos] if self.text else None # 当前字符 def error(self): raise Exception(Invalid character) def advance(self): 移动指针到下一个字符 self.pos 1 if self.pos len(self.text): self.current_char self.text[self.pos] else: self.current_char None def skip_whitespace(self): 跳过所有空白字符空格、制表符、换行 while self.current_char is not None and self.current_char.isspace(): self.advance() def number(self): 提取一个完整的数字多位数 result while self.current_char is not None and self.current_char.isdigit(): result self.current_char self.advance() # 目前只处理整数返回TT_INT类型的Token return Token(TT_INT, int(result)) def get_next_token(self): 词法分析的核心方法每次调用返回下一个Token while self.current_char is not None: # 跳过空白 if self.current_char.isspace(): self.skip_whitespace() continue # 识别数字 if self.current_char.isdigit(): return self.number() # 识别运算符和括号 if self.current_char : self.advance() return Token(TT_PLUS) if self.current_char -: self.advance() return Token(TT_MINUS) if self.current_char *: self.advance() return Token(TT_MUL) if self.current_char /: self.advance() return Token(TT_DIV) if self.current_char (: self.advance() return Token(TT_LPAREN) if self.current_char ): self.advance() return Token(TT_RPAREN) # 如果遇到无法识别的字符报错 self.error() # 所有字符处理完毕返回EOF Token return Token(TT_EOF)实操心得与避坑指南指针管理是关键advance()方法一定要在适当的时候调用确保current_char始终指向待处理的字符。忘记advance()是新手最常见的导致死循环的原因。空白字符处理必须在主循环开始时就处理空白否则会遇到 字符无法识别而报错。数字的贪婪匹配number()方法要用while循环收集连续的数字字符直到遇到非数字为止。这确保了123被识别为一个TokenINT(123)而不是三个独立的INT(1),INT(2),INT(3)。EOF必不可少EOFToken 是语法分析器知道输入何时结束的信号没有它语法分析器可能会试图读取不存在的Token而导致错误。你可以写个简单的测试来验证你的Lexerdef test_lexer(): lexer Lexer((3 5) * 2) tokens [] while True: token lexer.get_next_token() tokens.append(token) if token.type TT_EOF: break print(tokens) # 期望输出: [Token(LPAREN, None), Token(INT, 3), Token(PLUS, None), Token(INT, 5), Token(RPAREN, None), Token(MUL, None), Token(INT, 2), Token(EOF, None)]4. 第二阶段实战语法分析器Parser与抽象语法树AST拿到Token流后语法分析器要判断它是否符合我们定义的语法规则并构建出树形结构。我们采用递归下降的解析方法这是最直观、最适合手写解析器的方法。4.1 定义语法与AST节点首先我们用巴科斯范式BNF描述一下简单表达式的语法expr : term ((PLUS | MINUS) term)* term : factor ((MUL | DIV) factor)* factor : INT | LPAREN expr RPARENexpr表达式由term项和可选的加减运算组成。term项由factor因子和可选的乘除运算组成。factor因子可以是一个整数或者一个括号括起来的expr。 这种分层定义天然地赋予了乘除比加减更高的优先级。对应的我们需要定义AST的节点类class BinOpNode: 二元操作节点如 3 4, 5 * 2 def __init__(self, left_node, op_token, right_node): self.left_node left_node self.op_token op_token # 操作符Token如 PLUS, MUL self.right_node right_node class NumNode: 数字节点 def __init__(self, token): self.token token self.value token.value4.2 实现递归下降语法分析器Parser会持有Lexer实例并按照语法规则递归地调用对应的方法。class Parser: def __init__(self, lexer): self.lexer lexer self.current_token self.lexer.get_next_token() # 初始化当前Token def error(self): raise Exception(Invalid syntax) def eat(self, token_type): “消耗”当前Token如果类型匹配则获取下一个Token if self.current_token.type token_type: self.current_token self.lexer.get_next_token() else: self.error() def factor(self): 解析因子: INT 或 ( expr ) token self.current_token if token.type TT_INT: self.eat(TT_INT) return NumNode(token) elif token.type TT_LPAREN: self.eat(TT_LPAREN) node self.expr() # 递归解析括号内的表达式 self.eat(TT_RPAREN) return node else: self.error() def term(self): 解析项: factor ((MUL | DIV) factor)* node self.factor() # 先解析第一个因子 # 循环处理连续的乘除 while self.current_token.type in (TT_MUL, TT_DIV): op_token self.current_token if op_token.type TT_MUL: self.eat(TT_MUL) elif op_token.type TT_DIV: self.eat(TT_DIV) right_node self.factor() # 解析右边的因子 node BinOpNode(left_nodenode, op_tokenop_token, right_noderight_node) return node def expr(self): 解析表达式: term ((PLUS | MINUS) term)* node self.term() # 先解析第一个项 # 循环处理连续的加减 while self.current_token.type in (TT_PLUS, TT_MINUS): op_token self.current_token if op_token.type TT_PLUS: self.eat(TT_PLUS) elif op_token.type TT_MINUS: self.eat(TT_MINUS) right_node self.term() # 解析右边的项 node BinOpNode(left_nodenode, op_tokenop_token, right_noderight_node) return node def parse(self): 解析的入口返回整个表达式的AST根节点 return self.expr()核心逻辑解析与避坑点递归下降的精髓每个语法规则expr,term,factor对应一个函数。函数内部按照规则调用其他函数或处理Token。factor中遇到括号时递归调用expr完美体现了“递归”和“下降”从高层规则向底层规则解析。优先级处理注意expr调用termterm调用factor。这意味着在解析3 5 * 2时expr()先调用term()去解析5 * 2得到一个乘法节点然后再用这个节点作为右节点与左边的3组成加法节点。乘法在更深的调用层级中被解析从而获得了更高的优先级。左结合性的实现while循环是关键。node BinOpNode(left_nodenode, ...)这行代码将当前运算结果不断作为新运算的左节点实现了左结合。对于10 - 2 - 1它会生成((10 - 2) - 1)的AST而不是(10 - (2 - 1))。eat()方法的重要性它不仅是消耗Token更是语法检查。如果当前Token不符合预期直接报错比如在期望数字的地方遇到了加号。测试一下Parser和ASTdef test_parser(): lexer Lexer((3 5) * 2) parser Parser(lexer) ast parser.parse() # 可以写一个简单的打印函数来可视化AST print_ast(ast) # 期望的AST结构大致是 # MUL # / \ # PLUS 2 # / \ # 3 55. 第三阶段实战代码生成器Code Generator有了结构清晰的AST代码生成就变成了按特定顺序遍历这棵树并为每个节点“做点事情”。我们将生成一种非常简单的、基于栈的指令集模拟一个微型虚拟机的执行过程。5.1 设计我们的“汇编指令”为了简单我们设计三条指令PUSH将一个整数压入栈顶。ADD弹出栈顶两个元素相加结果压回栈顶。MUL弹出栈顶两个元素相乘结果压回栈顶。那么表达式(3 5) * 2对应的指令序列应该是PUSH 3 PUSH 5 ADD # 执行后栈顶为 8 PUSH 2 MUL # 执行后栈顶为 16执行完毕后栈顶的值就是计算结果。5.2 遍历AST生成指令我们采用后序遍历左子树 - 右子树 - 根节点的方式来生成代码。这是因为对于二元运算你需要先计算左操作数和右操作数的值它们各自可能又是复杂的表达式然后再进行运算。class CodeGenerator: def __init__(self): self.instructions [] # 存储生成的指令列表 def generate(self, node): 根据AST节点生成代码 if isinstance(node, NumNode): # 数字节点生成PUSH指令 self.instructions.append(fPUSH {node.value}) elif isinstance(node, BinOpNode): # 二元操作节点先递归生成左、右子树的代码再生成操作指令 self.generate(node.left_node) self.generate(node.right_node) # 根据操作符类型生成对应指令 if node.op_token.type TT_PLUS: self.instructions.append(ADD) elif node.op_token.type TT_MINUS: self.instructions.append(SUB) # 假设我们也实现了SUB指令 elif node.op_token.type TT_MUL: self.instructions.append(MUL) elif node.op_token.type TT_DIV: self.instructions.append(DIV) # 假设我们也实现了DIV指令 else: raise Exception(Invalid operator) else: raise Exception(Invalid AST node) def get_code(self): 返回生成的指令列表 return self.instructions5.3 实现一个简单的解释器来执行指令生成指令后我们还需要一个能执行这些指令的“虚拟机”。class Interpreter: def __init__(self, instructions): self.instructions instructions self.stack [] def run(self): for instr in self.instructions: parts instr.split() op parts[0] if op PUSH: value int(parts[1]) self.stack.append(value) elif op ADD: b self.stack.pop() a self.stack.pop() self.stack.append(a b) elif op MUL: b self.stack.pop() a self.stack.pop() self.stack.append(a * b) # 可以类似地实现 SUB, DIV # 执行完毕后栈顶应只剩下结果 if len(self.stack) 1: return self.stack[0] else: raise Exception(Execution error, stack is not clean.)代码生成的关键细节与经验遍历顺序决定一切后序遍历保证了操作数在操作符之前被计算和压栈这是栈式计算的核心。如果你用前序或中序遍历生成的指令顺序将是错误的。指令集的设计我们这里用了非常简单的零地址指令操作隐含从栈中取。在实际编译器中可能会生成x86、ARM等真实汇编或者LLVM IR、JVM字节码等中间表示原理相通但细节复杂得多。临时结果的处理栈机自动处理了中间结果。在更复杂的场景或生成真实寄存器代码时你需要一个“寄存器分配器”来管理有限的硬件寄存器这又是一个深水区。现在让我们把三个阶段串联起来完成整个编译流程def compile_and_run(source_code): # 1. 词法分析 lexer Lexer(source_code) # 2. 语法分析 parser Parser(lexer) ast parser.parse() # 3. 代码生成 generator CodeGenerator() generator.generate(ast) code generator.get_code() print(f生成的指令: {code}) # 4. 解释执行 interpreter Interpreter(code) result interpreter.run() print(f计算结果: {result}) return result # 测试 compile_and_run((3 5) * 2) # 输出生成的指令: [PUSH 3, PUSH 5, ADD, PUSH 2, MUL] 计算结果: 16 compile_and_run(10 - 2 - 1) # 需要扩展支持减法6. 常见问题、扩展方向与深度思考走到这一步一个微型编译器已经在你手中运行起来了。但真实的编译器远比这复杂。下面是一些你可能会遇到的问题和可以继续探索的方向。6.1 开发与调试中的常见陷阱无限递归或栈溢出原因语法规则定义存在左递归例如expr: expr PLUS term在递归下降解析器中会无限调用自身。解决必须将文法改写为等价的非左递归形式如我们使用的expr: term ((PLUS | MINUS) term)*。这是手写递归下降解析器必须掌握的第一步。优先级错乱现象3 5 * 2被计算成16而不是13。检查回顾你的语法规则层级。确保乘除term在加减expr的下一层被调用。expr - term - factor这个调用链是优先级正确的保证。结合性错误现象10 - 2 - 1被计算成9(即10 - (2 - 1)) 而不是7。解决确保在expr()和term()函数中用while循环和node BinOpNode(left_nodenode, ...)这种模式来构造AST这天然实现了左结合。错误处理过于简陋现状我们的error()方法直接抛出异常然后程序崩溃。改进工业级编译器会收集错误、尝试恢复并继续解析以报告更多错误。你可以尝试实现一个错误列表在遇到未知字符或语法错误时记录错误信息跳过当前Token或进行一些“应急”处理然后继续解析。6.2 如何扩展这个微型编译器这个项目是一个完美的起点你可以像搭积木一样为它添加新功能支持变量词法分析增加识别标识符字母开头的字符串的Token类型TT_ID。语法分析在factor中增加对标识符的解析。增加赋值语句的规则如assignment : ID EQUALS expr。代码生成需要维护一个“符号表”来记录变量名和它的值或存储位置。生成LOAD和STORE指令。支持控制流if/while词法分析增加关键字Token如IF,ELSE,WHILE,TRUE,FALSE以及比较运算符,,等。语法分析增加条件表达式和语句块的规则。控制流的核心是跳转指令。代码生成需要生成条件跳转JMP_IF_FALSE和无条件跳转JMP指令。生成代码时需要解决“回填”问题——即跳转的目标地址在生成跳转指令时可能还不知道。支持函数这是质的飞跃。需要处理参数传递、调用栈、返回地址、返回值。你会深入理解栈帧、活动记录等概念。生成真实汇编将我们的栈式指令替换为x86或RISC-V汇编。你需要学习目标平台的指令集和调用约定。例如PUSH变成mov和push指令的组合运算在寄存器中进行。6.3 从“玩具”到“工具”的思考完成这个项目后你再去看GCC、Clang这些工业编译器或者解释型语言的解释器如Python的CPython就会有一种豁然开朗的感觉。它们庞大的代码库无非是在我们这个小骨架的基础上填充了无数细节前端更复杂的词法语法分析处理整个C/Rust语言、语义分析类型检查、作用域分析。中端多种中间表示IR、大量的优化遍Pass如常量传播、死代码消除、循环优化。后端指令选择、指令调度、寄存器分配、窥孔优化针对不同CPU架构x86, ARM, RISC-V生成最优代码。“手搓编译器”的过程强迫你去思考语言设计的本质理解代码从抽象到具体的完整映射。这种系统性的思维训练对你设计复杂软件、调试深层Bug、理解任何新语言或框架都有着不可估量的价值。下次当你再遇到编译错误或神秘的运行时问题时你看到的将不再是一行冰冷的报错信息而是一整套正在运转的翻译和执行机制中的某个具体环节。这就是知其所以然的力量。