1. 项目概述为什么我们要“手搓”一个编译器如果你是一名程序员每天敲下的代码最终都要通过一个“翻译官”变成机器能懂的语言这个翻译官就是编译器。我们用的GCC、Clang、MSVC它们强大而复杂像一座座精密的工厂。但你是否好奇过这座工厂内部的生产线是如何运作的代码从文本变成可执行文件究竟经历了什么这就是“从零开始构建一个简单的编译器”这个项目的全部意义——它不是要你造一个能投入生产的工业级工具而是要你亲手搭建一条微缩的、功能完整的“玩具”生产线从而彻底理解编译技术最核心的三个环节词法分析、语法分析和代码生成。这个过程业内戏称为“手搓编译器”。它绝不是学院派的纸上谈兵而是一次极具实践价值的深度探索。当你自己实现过一个编译器哪怕是只能处理加减乘除的你对编程语言的理解会跃升一个维度。你会明白为什么代码要这么写语法错误是怎么被检测出来的甚至能洞悉某些语言特性的设计优劣。这对于想要深入理解计算机系统、从事底层开发、或是对新型编程语言如各种DSL领域特定语言设计感兴趣的朋友来说是一次不可多得的“练内功”的机会。它让你从被动的语言使用者转变为主动的语言理解者和塑造者。2. 核心思路与整体架构设计2.1 目标语言定义从“计算器”开始在动手之前我们必须先明确要编译的“目标语言”是什么。一个好高骛远的开始往往是失败的根源。因此我强烈建议从一门极简的语言开始我称之为“MiniCalc”。它的功能可以简单到只支持整数、加减乘除、括号和变量赋值。例如它可以处理这样的语句x 10 y x 5 * (2 - 3)这个语言虽然简单但已经包含了编译器需要处理的所有核心概念标识符变量名、数字字面量、运算符、括号改变优先级和赋值语句。从这样一个微小的内核开始我们能集中精力攻克编译流程本身而不是被复杂的语言特性淹没。后续我们可以很容易地为它添加功能比如支持浮点数、比较语句、if-else控制流等这正是一个优秀学习项目的扩展路径。2.2 编译器工作流程总览一个典型的编译器工作流程可以看作一个多阶段的管道Pipeline。我们的简易编译器将实现其中最经典、最核心的三个阶段词法分析器Lexer这是编译器的“眼睛”。它的任务是将源代码字符串这个“字符流”切割成一个个有意义的“单词”在编译原理中称为“词法单元”或“Token”。例如对于输入x 10 yLexer会产出类似[Identifier(“x”), Assign, Number(10), Plus, Identifier(“y”)]的Token序列。它负责识别并忽略空格、换行等无关字符。语法分析器Parser这是编译器的“大脑”。它接收Token序列并根据预先定义好的“语法规则”Grammar检查这些Token的排列组合是否符合语言规范并同时构建出一棵“抽象语法树”。AST是源代码结构化的内存表示它抛弃了具体的字符细节如空格、分号只保留程序的逻辑骨架。例如对于10 5 * 2一个正确的AST会确保乘法节点*是加法节点的子节点体现了乘法的更高优先级。代码生成器Code Generator这是编译器的“手”。它遍历AST根据每个节点的类型生成等价的“目标代码”。对我们这个学习项目而言最直观的目标是生成一种“中间表示”比如三地址码或者直接生成x86汇编的某个子集。我们甚至可以生成另一种高级语言如C的代码然后借用成熟的编译器如GCC来完成最后的编译。这能大大降低我们项目的复杂度。整个架构是单向流动的源代码-Lexer-Token流-Parser-AST-CodeGen-目标代码。每个阶段职责单一通过定义清晰的接口Token, AST节点进行通信。3. 第一阶段词法分析器的实现细节词法分析说白了就是“拆词”。我们写一个循环逐个读取源程序字符根据字符的特征将其归并到不同的Token类别中。3.1 Token的设计与分类首先我们需要定义Token有哪些类型。这由我们的MiniCalc语言决定。我们可以用一个枚举Enum来定义from enum import Enum class TokenType(Enum): # 字面量 NUMBER NUMBER # 整数如 123 IDENTIFIER IDENTIFIER # 变量名如 x, total # 运算符 PLUS PLUS # MINUS MINUS # - MUL MUL # * DIV DIV # / ASSIGN ASSIGN # # 括号 LPAREN LPAREN # ( RPAREN RPAREN # ) # 特殊标记 EOF EOF # 文件结束每个Token对象除了类型最好还能携带具体的值lexeme。例如对于数字123Token类型是NUMBER值是整数123对于标识符foo类型是IDENTIFIER值是字符串foo。3.2 核心扫描逻辑与状态机词法分析器的核心是一个状态机。我们维护一个指针pos指向当前处理的字符一个变量current_char存储该字符。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 advance(self): 移动指针读取下一个字符 self.pos 1 if self.pos len(self.text): self.current_char None else: self.current_char self.text[self.pos] 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 Token(TokenType.NUMBER, self.number()) # 识别标识符变量名和关键字 if self.current_char.isalpha() or self.current_char _: return self.identifier() # 识别单字符运算符 if self.current_char : self.advance() return Token(TokenType.PLUS, ) if self.current_char -: self.advance() return Token(TokenType.MINUS, -) if self.current_char *: self.advance() return Token(TokenType.MUL, *) if self.current_char /: self.advance() return Token(TokenType.DIV, /) if self.current_char : self.advance() return Token(TokenType.ASSIGN, ) if self.current_char (: self.advance() return Token(TokenType.LPAREN, () if self.current_char ): self.advance() return Token(TokenType.RPAREN, )) # 如果遇到无法识别的字符报错 raise Exception(fInvalid character: {self.current_char}) # 所有字符处理完毕返回EOF Token return Token(TokenType.EOF, None) def number(self): 提取连续的数字字符转换为整数 result while self.current_char is not None and self.current_char.isdigit(): result self.current_char self.advance() return int(result) def identifier(self): 提取标识符变量名 result while self.current_char is not None and (self.current_char.isalnum() or self.current_char _): result self.current_char self.advance() # 这里可以检查result是否是关键字如if, while我们当前语言没有所以直接返回标识符 return Token(TokenType.IDENTIFIER, result) def skip_whitespace(self): while self.current_char is not None and self.current_char.isspace(): self.advance()实操心得在实现number()函数时一个常见的坑是只处理了十进制整数。如果你想支持浮点数需要在遇到第一个小数点.后进入另一个状态继续收集数字。同时要小心处理像123.这样的输入它可能是一个错误也可能是一个合法的浮点数取决于语言定义。在初期保持简单只处理整数能避免很多麻烦。4. 第二阶段语法分析器与抽象语法树构建词法分析器给了我们一堆单词现在需要检查这些单词能否组成合乎语法的句子并构建出AST。4.1 为MiniCalc定义文法我们需要用形式化的方法描述MiniCalc的语法通常使用“上下文无关文法”。这里我们采用一种易于理解和递归下降解析的写法program : statement statement : assignment | expression assignment : IDENTIFIER expression expression : term (( | -) term)* term : factor ((* | /) factor)* factor : NUMBER | IDENTIFIER | ( expression )解释一下program程序由至少一条statement语句组成。statement可以是assignment赋值语句或expression表达式语句。assignment是一个标识符后面跟着等号和表达式。expression表达式由term项通过加减号连接而成。*表示前面的部分可以重复零次或多次所以1 2 - 3是合法的。term项由factor因子通过乘除号连接而成体现了乘除比加减更高的优先级。factor因子是构成表达式的基本单元可以是数字、标识符变量或者用括号括起来的表达式这实现了通过括号改变优先级。这种文法的设计是递归下降解析成功的关键。每个非终结符如expression,term,factor都对应解析器中的一个函数。4.2 递归下降解析算法实现递归下降解析器就是一组相互递归调用的函数每个函数负责匹配文法中的一个非终结符。它从program函数开始像一棵树一样向下递归解析。首先我们定义AST节点。一个简单的设计如下class ASTNode: pass class BinOp(ASTNode): 二元操作节点如 左表达式 运算符 右表达式 def __init__(self, left, op, right): self.left left self.op op # Token类型如 PLUS, MUL self.right right class Num(ASTNode): 数字字面量节点 def __init__(self, token): self.token token self.value token.value class Var(ASTNode): 变量节点 def __init__(self, token): self.token token self.name token.value class Assign(ASTNode): 赋值语句节点 def __init__(self, left, right): self.left left # Var节点 self.right right # 表达式节点接着实现解析器。解析器内部封装一个词法分析器实例用于获取Token。class Parser: def __init__(self, lexer): self.lexer lexer self.current_token self.lexer.get_next_token() def eat(self, token_type): “消费”当前Token如果类型匹配则获取下一个Token否则报错 if self.current_token.type token_type: self.current_token self.lexer.get_next_token() else: raise Exception(fSyntax error, expected {token_type}, got {self.current_token.type}) def factor(self): 解析因子: NUMBER | IDENTIFIER | ( expression ) token self.current_token if token.type TokenType.NUMBER: self.eat(TokenType.NUMBER) return Num(token) elif token.type TokenType.IDENTIFIER: self.eat(TokenType.IDENTIFIER) return Var(token) elif token.type TokenType.LPAREN: self.eat(TokenType.LPAREN) node self.expression() # 递归解析括号内的表达式 self.eat(TokenType.RPAREN) return node else: raise Exception(Syntax error in factor) def term(self): 解析项: factor ((* | /) factor)* node self.factor() # 解析第一个因子 # 循环处理连续的 * 或 / while self.current_token.type in (TokenType.MUL, TokenType.DIV): op_token self.current_token if op_token.type TokenType.MUL: self.eat(TokenType.MUL) elif op_token.type TokenType.DIV: self.eat(TokenType.DIV) # 构建新的二元操作节点左子树是之前的node右子树是新解析的factor node BinOp(leftnode, opop_token.type, rightself.factor()) return node def expression(self): 解析表达式: term (( | -) term)* node self.term() # 解析第一个项 # 循环处理连续的 或 - while self.current_token.type in (TokenType.PLUS, TokenType.MINUS): op_token self.current_token if op_token.type TokenType.PLUS: self.eat(TokenType.PLUS) elif op_token.type TokenType.MINUS: self.eat(TokenType.MINUS) node BinOp(leftnode, opop_token.type, rightself.term()) return node def assignment(self): 解析赋值语句: IDENTIFIER expression # 当前Token应该是一个标识符 left Var(self.current_token) self.eat(TokenType.IDENTIFIER) self.eat(TokenType.ASSIGN) # 消费掉 ‘’ right self.expression() # 解析等号右边的表达式 return Assign(left, right) def statement(self): 解析语句: assignment | expression # 预读下一个Token判断是赋值还是表达式 # 简单策略如果下一个Token是IDENTIFIER且再下一个是ASSIGN则是赋值 # 更健壮的做法需要更复杂的预读这里简化处理 if self.current_token.type TokenType.IDENTIFIER: # 偷看下一个Token # 注意这里需要小心地“偷看”不能消费Token。我们可以复制lexer状态或使用更正式的方法。 # 为了简化我们假设如果遇到标识符就尝试按赋值解析失败则回退按表达式解析。 # 实际上一个更简单初期的实现是只支持表达式或者只支持赋值。我们先实现表达式。 # 我们先实现一个只支持表达式的解析器作为示例。 pass # 我们暂时只实现表达式解析 return self.expression() def program(self): 解析整个程序: statement statements [] while self.current_token.type ! TokenType.EOF: statements.append(self.statement()) # 这里我们缺少语句分隔符如分号所以默认一个语句接一个语句。 # 在实际语言中需要处理分号或换行作为分隔符。 return statements # 返回AST根节点列表注意事项上面的statement和program函数是一个简化版本没有处理赋值和多个语句。一个完整的实现需要引入语句分隔符如分号;或换行并在statement中根据预读的Token决定是调用assignment()还是expression()。递归下降解析器对文法的要求很严格需要避免“左递归”如expression: expression ‘’ term我们的文法通过改写已经避免了这一点。这是实现递归下降解析器的关键技巧。5. 第三阶段代码生成与目标输出有了AST这棵结构清晰的树代码生成就变成了对树的一次遍历。我们为每种AST节点类型编写一个处理函数。5.1 遍历AST生成三地址码三地址码是一种非常简单的中间表示形式每条指令最多涉及三个“地址”可以是变量名、常量或编译器生成的临时变量。它非常接近最终的汇编指令但又保持了平台无关性。例如对于表达式x a b * c可能生成的三地址码序列是t1 b * c t2 a t1 x t2我们来编写一个访问AST并生成三地址码列表的类class TACGenerator: def __init__(self): self.temp_counter 0 # 用于生成唯一的临时变量名如 t0, t1, t2... self.code [] # 存储生成的三地址码指令 self.symbol_table {} # 简单的符号表记录变量名可选用于后续优化或检查 def new_temp(self): 生成一个新的临时变量名 temp_name ft{self.temp_counter} self.temp_counter 1 return temp_name def visit(self, node): 根据节点类型分发到具体的处理方法 method_name visit_ type(node).__name__ visitor getattr(self, method_name, self.generic_visit) return visitor(node) def generic_visit(self, node): raise Exception(fNo visit_{type(node).__name__} method) def visit_Num(self, node): 处理数字节点数字本身就是值可以作为一个“地址”直接使用 # 返回这个数字的字面值作为“地址” return str(node.value) def visit_Var(self, node): 处理变量节点返回变量名作为“地址” # 这里可以检查符号表看变量是否已定义 return node.name def visit_BinOp(self, node): 处理二元操作节点生成计算指令并返回一个临时变量名存放结果 # 递归访问左子树和右子树获取它们计算结果的“地址” left_addr self.visit(node.left) right_addr self.visit(node.right) # 为本次运算结果生成一个临时变量 result_temp self.new_temp() # 根据操作符生成对应的三地址码指令 op_map { TokenType.PLUS: ADD, TokenType.MINUS: SUB, TokenType.MUL: MUL, TokenType.DIV: DIV } op_code op_map.get(node.op) if not op_code: raise Exception(fUnsupported operator: {node.op}) # 生成指令结果临时变量 左地址 操作符 右地址 self.code.append(f{result_temp} {left_addr} {op_code} {right_addr}) # 返回这个临时变量名供上层表达式使用 return result_temp def visit_Assign(self, node): 处理赋值节点生成赋值指令 # 访问等号右边的表达式获取其计算结果的“地址” right_addr self.visit(node.right) # 获取等号左边的变量名 left_name node.left.name # 生成赋值指令变量名 右地址 self.code.append(f{left_name} {right_addr}) # 赋值语句本身不产生值返回None或变量名均可 return left_name def generate(self, ast_root): 入口函数遍历AST可能是语句列表并生成代码 if isinstance(ast_root, list): for stmt in ast_root: self.visit(stmt) else: self.visit(ast_root) return self.code现在如果我们有一个AST例如表示x a b * c调用生成器的generate方法就能得到类似[t0 b MUL c, t1 a ADD t0, x t1]的三地址码序列。5.2 从三地址码到真实汇编以x86为例三地址码是平台无关的但最终我们需要让机器执行。我们可以再写一个后端将三地址码翻译成特定CPU的汇编指令。以x86-64汇编Intel语法为例这是一个极度简化的转换假设我们有一个无限的寄存器集合用rax, rbx, rcx...模拟实际需要寄存器分配这是一个复杂问题初期我们可以简单地将每个临时变量和用户变量映射到内存栈帧上的一个位置。更简单的策略我们生成“栈机”代码所有操作都在一个操作数栈上进行。这更容易实现也是很多解释器如Java虚拟机早期和简单编译器的选择。这里我们展示一个概念性的、极其简化的x86生成思路不处理寄存器分配假设所有值都在内存中class X86AssemblyGenerator: def __init__(self, tac_code): self.tac tac_code self.asm [] # 一个简单的内存地址映射表 self.var_map {} def allocate_var(self, var_name): 为变量分配一个内存位置例如基于栈的偏移量 if var_name not in self.var_map: # 假设每个变量占8字节64位整数从rbp-8, rbp-16...开始分配 offset (len(self.var_map) 1) * 8 self.var_map[var_name] f[rbp-{offset}] return self.var_map[var_name] def generate(self): self.asm.append(section .text) self.asm.append(global main) self.asm.append(main:) self.asm.append( push rbp) self.asm.append( mov rbp, rsp) self.asm.append( sub rsp, 64 ; 为局部变量预留栈空间简化处理) for instr in self.tac: # 解析三地址码指令例如 t1 a ADD t0 parts instr.split() if len(parts) 5: # 形如: dest src1 op src2 dest, _, src1, op, src2 parts dest_addr self.allocate_var(dest) src1_addr self.allocate_var(src1) if src1 in self.var_map else src1 # 可能是常数 src2_addr self.allocate_var(src2) if src2 in self.var_map else src2 # 生成汇编将src1加载到rax if src1.isdigit(): self.asm.append(f mov rax, {src1} ; 加载常数{src1}) else: self.asm.append(f mov rax, {src1_addr} ; 加载变量{src1}) # 根据操作符生成运算指令 if op ADD: if src2.isdigit(): self.asm.append(f add rax, {src2}) else: self.asm.append(f add rax, {src2_addr}) elif op SUB: # ... 类似处理SUB pass elif op MUL: # x86的mul指令隐含使用rax和rdx需要特殊处理 self.asm.append(f mov rbx, {src2_addr if not src2.isdigit() else src2}) self.asm.append( imul rbx) # rax rax * rbx elif op DIV: # ... 类似处理DIV更复杂 pass # 将结果存回dest地址 self.asm.append(f mov {dest_addr}, rax) elif len(parts) 3 and parts[1] : # 形如: x t1 (简单赋值) dest, _, src parts dest_addr self.allocate_var(dest) src_addr self.allocate_var(src) if src in self.var_map else src if src.isdigit(): self.asm.append(f mov rax, {src}) else: self.asm.append(f mov rax, {src_addr}) self.asm.append(f mov {dest_addr}, rax) # 函数尾声 self.asm.append( mov rax, 60 ; sys_exit) self.asm.append( xor rdi, rdi ; exit code 0) self.asm.append( syscall) return \n.join(self.asm)重要提示上面的汇编生成代码是高度简化的概念演示不能直接运行。真实的x86汇编生成需要处理调用约定、寄存器分配、内存对齐、系统调用等诸多复杂问题。对于学习项目生成三地址码或一种更简单的虚拟机字节码如栈机指令是更可行、更有成就感的目标。你可以为你的三地址码写一个简单的解释器来执行它这同样能完整地走通整个编译流程。6. 项目集成、测试与调试实录6.1 将三个阶段串联起来现在我们把词法分析、语法分析和代码生成三个阶段串联起来形成一个完整的编译流程。我们可以写一个主函数def compile_source(source_code): # 1. 词法分析 lexer Lexer(source_code) # 2. 语法分析 parser Parser(lexer) ast parser.program() # 获取AST根节点列表 # 3. 中间代码生成 tac_gen TACGenerator() tac_code tac_gen.generate(ast) return tac_code # 测试 source x 10 y x 5 * 2 tac compile_source(source) for instr in tac: print(instr)预期输出可能类似于t0 5 MUL 2 t1 x ADD t0 y t1注意第一句x 10的赋值需要你的解析器支持赋值语句并生成类似x 10的三地址码。6.2 常见问题与调试技巧在“手搓编译器”的过程中你会遇到各种各样的bug。以下是一些典型问题及其排查思路词法分析器无法识别多字符运算符如,问题扫描到第一个时就直接返回了ASSIGNToken导致被错误地拆成两个Token。解决在识别单字符后需要“向前看”一个字符peek。例如当当前字符是时检查下一个字符是不是也是如果是则生成EQToken并消费两个字符。语法分析器陷入无限递归或报告不期望的Token问题这通常是由于文法存在左递归或者递归下降函数之间的调用关系与文法不匹配。调试在eat()方法和每个递归函数的入口处打印当前Token观察解析过程在哪里卡住或跑偏。确保你的文法已经消除了左递归我们的expression: term ((|-) term)*就是一种消除左递归的写法。运算符优先级处理错误问题1 2 * 3被错误地解析为(1 2) * 3。解决检查你的文法层级。乘除term必须在加减expression的下一层被调用。在expression函数中它应该先调用term()来解析高优先级的乘除部分。生成的代码效率低下或冗余问题对于表达式a 1 2可能生成t0 a ADD 1; t1 t0 ADD 2这是正确的但非最优。解决这是优化器的工作。在编译器设计中优化是一个独立的、庞大的阶段。学习初期我们只追求正确性可以暂时忽略优化。一个简单的“常量折叠”优化可以在语法分析或代码生成时进行例如直接将1 2计算为3。如何处理错误恢复问题当遇到一个语法错误如缺少右括号时编译器直接崩溃无法报告后续的错误。解决工业级编译器有复杂的错误恢复机制。在我们的学习项目中可以在eat()函数中尝试同步到下一个“同步点”如分号、行尾然后继续解析从而报告多个错误。但这会显著增加复杂度初期在遇到第一个错误时直接停止并给出清晰错误信息即可。给初学者的终极建议从一个极其微小的、可运行的核心开始然后一点点添加功能。例如先让词法分析器能识别数字和加减号语法分析器能解析12-3这样的表达式代码生成器能打印出对应的三地址码。测试通过。添加乘除法测试优先级。添加括号支持。添加变量标识符和支持赋值的语句。添加更多的语句类型如打印语句。每完成一步都进行充分的测试。使用小而具体的输入用例并手动推算预期的AST和三地址码与程序输出对比。这个过程虽然缓慢但能帮你建立坚实的信心和对每个环节的深刻理解。当你看到自己编写的程序能够将一段文本逐步转换成可执行的指令时那种穿透抽象、直达本质的成就感是学习编程语言理论无法比拟的。