1. 项目概述为什么我们要“手搓”一个编译器“从零开始构建一个简单的编译器”这个标题听起来像是一个计算机科学专业学生的课程大作业或者是一个资深工程师为了深入理解底层原理而进行的“硬核”挑战。确实对于绝大多数应用开发者而言编译器是一个黑盒——我们写好代码点击“运行”或“构建”然后等待输出。GCC、Clang、MSVC、Javac这些名字我们耳熟能详但很少有人真正关心它们内部是如何将我们写的if-else和for循环变成机器可以执行的指令的。然而理解编译器的工作机制尤其是亲手实现一个哪怕是最简陋的版本其价值远超完成一个作业。这就像学开车你当然可以只学操作但如果你了解发动机、变速箱和底盘的基本原理你就能更好地应对突发故障甚至能进行一些简单的改装和性能调优。对于开发者而言理解编译器能让你写出更“友好”的代码你知道编译器是如何看待你的代码的就能避免写出那些让编译器“困惑”或低效的语法结构。深入理解编程语言特性闭包、泛型、异步/协程这些高级特性在编译器层面是如何实现的自己实现一遍比看十篇理论文章都管用。掌握强大的元编程和领域特定语言DSL能力当你需要为特定场景设计一套简化的配置语言或流程引擎时编译器的前端技术词法、语法分析就是你的核心工具。奠定性能优化和底层开发的基石无论是进行Android/iOS的NDK开发还是从事数据库、游戏引擎等基础软件研发对程序从源码到二进制产物的完整生命周期有清晰认知是解决复杂问题的关键。我们这个项目的目标就是剥开编译器这个黑盒用最直接的方式构建一个能处理简单算术表达式和赋值语句的编译器。它将完成经典的三段式流水线词法分析 - 语法分析 - 代码生成。我们不会涉及复杂的优化而是聚焦于让这个流程完整地跑通。你将看到一个编译器最核心的骨架其思想之优美与逻辑之严密足以让你对编程有全新的认识。2. 编译器核心流程与我们的设计蓝图一个完整的工业级编译器流程极其复杂包括预处理、编译、汇编、链接等多个阶段编译阶段本身又可能包含多次中间表示转换和优化。但万变不离其宗其最核心的“编译”动作可以抽象为下图所示的三个关键阶段这也是我们本次实践的核心源代码字符串 - [词法分析器] - 令牌流 - [语法分析器] - 抽象语法树 - [代码生成器] - 目标代码我们的设计将围绕这三个模块展开并为它们定义一个极简的“教学语言”我们称之为MiniLang。它的语法规则如下程序Program由一系列语句Statement组成。语句Statement赋值语句标识符 表达式;输出语句print(表达式);表达式Expression可以是数字如42、标识符变量名如x。可以是二元运算表达式 运算符 表达式运算符支持,-,*,/。可以用括号()改变优先级。例如下面就是一个合法的 MiniLang 程序x 10; y x 5 * 2; print(y);我们的编译器任务就是读取这样的文本最终生成一段可以执行的代码比如 x86 汇编或者另一种高级语言如 C。为了最大化可理解性和可移植性我们选择生成C 语言代码作为目标。因为 C 编译器无处不在生成 C 代码后我们可以用 GCC 或 Clang 轻松编译成可执行文件直观地看到我们编译器的成果。设计思路选择为什么不直接生成汇编汇编与硬件架构强相关x86, ARM引入大量细节会分散我们对核心流程的注意力。生成 C 代码是一个完美的折中C 本身足够底层能清晰反映我们的意图变量、运算、函数调用同时又屏蔽了寄存器分配、调用约定等复杂问题。这让我们能专注于前端分析部分。3. 第一阶段词法分析——从字符流到令牌流词法分析也叫扫描Scanning是编译器的“眼睛”。它的任务极其直观读入源代码的原始字符流就是一堆字符忽略掉空格、制表符、换行这些无关紧要的“空白字符”然后将剩下的字符组合成一个个有意义的单词在编译原理中称为令牌Token。3.1 令牌设计与分类我们需要为 MiniLang 定义所有可能的令牌类型。这就像为一种语言编写字典。我们使用一个枚举Enum来定义from enum import Enum class TokenType(Enum): # 关键字 PRINT PRINT # 标识符 (变量名) IDENTIFIER IDENTIFIER # 字面量 NUMBER NUMBER # 运算符 PLUS PLUS # MINUS MINUS # - MULTIPLY MULTIPLY # * DIVIDE DIVIDE # / ASSIGN ASSIGN # # 分隔符 LPAREN LPAREN # ( RPAREN RPAREN # ) SEMICOLON SEMICOLON # ; # 文件结束 EOF EOF每个令牌不仅仅是一个类型它还需要携带具体的值。例如对于令牌NUMBER它的值可能是字符串10或3.14对于IDENTIFIER它的值可能是x或count。因此我们用一个简单的类来封装class Token: def __init__(self, type: TokenType, value: str None): self.type type self.value value # 对于关键字、运算符、分隔符value通常为None或符号本身 def __repr__(self): return fToken({self.type}, {repr(self.value)})3.2 实现词法分析器词法分析器的核心是一个状态机。它逐个读取字符根据当前字符决定下一个状态并累积字符形成令牌。我们实现一个简单的Lexer类class Lexer: def __init__(self, text: str): self.text text self.pos 0 # 当前字符索引 self.current_char self.text[self.pos] if self.text else None def error(self): raise Exception(fInvalid character at position {self.pos}: {self.current_char}) 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 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() return Token(TokenType.NUMBER, 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() # 检查是否是关键字 if result print: return Token(TokenType.PRINT) else: return Token(TokenType.IDENTIFIER, result) def get_next_token(self): 获取下一个令牌这是词法分析器的核心接口 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.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.MULTIPLY) if self.current_char /: self.advance() return Token(TokenType.DIVIDE) 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) if self.current_char ;: self.advance() return Token(TokenType.SEMICOLON) self.error() return Token(TokenType.EOF)实操心得与避坑指南前瞻字符Lookahead我们的实现是“一个字符前瞻”即根据current_char决定动作。更复杂的语言可能需要前瞻多个字符例如区分和。这时可以维护一个缓冲区或使用peek()方法查看下一个字符而不消耗它。错误恢复上面的error()方法直接抛出异常在简单编译器中可以接受。工业级编译器会尝试从错误中恢复例如跳过非法字符继续分析并收集多个错误一次性报告。数字与标识符的边界注意number()和identifier()函数中的循环条件。isalnum()判断字母或数字这确保了x123能被正确识别为一个完整的标识符而不是x和123。关键字处理关键字如print是标识符的子集。我们是在识别出一个完整的标识符字符串后再检查它是否是关键字。这是一种简单有效的策略。让我们测试一下词法分析器code x 10 y; lexer Lexer(code) tokens [] while True: token lexer.get_next_token() tokens.append(token) if token.type TokenType.EOF: break print(tokens) # 输出: [Token(IDENTIFIER, x), Token(ASSIGN, None), Token(NUMBER, 10), Token(PLUS, None), Token(IDENTIFIER, y), Token(SEMICOLON, None), Token(EOF, None)]成功源代码字符串被转换成了一个有结构的令牌流。4. 第二阶段语法分析——从令牌流到抽象语法树词法分析告诉我们“有什么单词”语法分析则要告诉我们“这些单词按照什么规则组成了句子”。它依据的是我们前面定义的语法Grammar。语法分析的结果通常是一棵抽象语法树Abstract Syntax Tree, AST。AST 忽略了分隔符等细节只保留程序结构的核心逻辑。4.1 定义抽象语法树节点首先我们需要定义 AST 的节点类型。每种语法结构对应一种节点。class ASTNode: 所有AST节点的基类 pass class Program(ASTNode): def __init__(self, statements): self.statements statements # Statement列表 class AssignStmt(ASTNode): 赋值语句: identifier expression; def __init__(self, identifier, expression): self.identifier identifier # 一个字符串变量名 self.expression expression # 一个Expr节点 class PrintStmt(ASTNode): 输出语句: print(expression); def __init__(self, expression): self.expression expression # 一个Expr节点 class BinOp(ASTNode): 二元运算: left op right def __init__(self, left, op, right): self.left left # 左表达式节点 self.op op # 运算符令牌类型如 TokenType.PLUS self.right right # 右表达式节点 class Num(ASTNode): 数字字面量 def __init__(self, value): self.value value # 数字的字符串或整数表示 class Var(ASTNode): 变量引用 def __init__(self, name): self.name name # 变量名的字符串4.2 实现递归下降语法分析器我们将采用递归下降分析法Recursive Descent Parsing。这是一种直观的自顶向下分析方法为语法中的每个非终结符如program,statement,expression编写一个解析函数。我们的语法是 LL(1) 的即只需要看下一个令牌Lookahead(1)就能决定使用哪条语法规则。class Parser: def __init__(self, lexer: Lexer): self.lexer lexer self.current_token self.lexer.get_next_token() # 初始化当前令牌 def error(self, msg): raise Exception(fSyntax error at token {self.current_token}. {msg}) def eat(self, token_type: TokenType): “消耗”当前令牌如果类型匹配则获取下一个令牌 if self.current_token.type token_type: self.current_token self.lexer.get_next_token() else: self.error(fExpected {token_type}, got {self.current_token.type}) # 解析因子数字或标识符或括号表达式 def factor(self): token self.current_token if token.type TokenType.NUMBER: self.eat(TokenType.NUMBER) return Num(int(token.value)) # 将字符串转为整数 elif token.type TokenType.IDENTIFIER: self.eat(TokenType.IDENTIFIER) return Var(token.value) elif token.type TokenType.LPAREN: self.eat(TokenType.LPAREN) node self.expr() # 递归解析括号内的表达式 self.eat(TokenType.RPAREN) return node else: self.error(Expected NUMBER, IDENTIFIER, or LPAREN) # 解析项处理 * 和 / def term(self): node self.factor() while self.current_token.type in (TokenType.MULTIPLY, TokenType.DIVIDE): op self.current_token.type self.eat(op) node BinOp(leftnode, opop, rightself.factor()) return node # 解析表达式处理 和 - def expr(self): node self.term() while self.current_token.type in (TokenType.PLUS, TokenType.MINUS): op self.current_token.type self.eat(op) node BinOp(leftnode, opop, rightself.term()) return node # 解析语句 def statement(self): token self.current_token if token.type TokenType.PRINT: self.eat(TokenType.PRINT) self.eat(TokenType.LPAREN) expr_node self.expr() self.eat(TokenType.RPAREN) self.eat(TokenType.SEMICOLON) return PrintStmt(expr_node) elif token.type TokenType.IDENTIFIER: identifier_name token.value self.eat(TokenType.IDENTIFIER) self.eat(TokenType.ASSIGN) expr_node self.expr() self.eat(TokenType.SEMICOLON) return AssignStmt(identifier_name, expr_node) else: self.error(Expected PRINT or IDENTIFIER at start of statement) # 解析程序由多个语句组成 def program(self): statements [] while self.current_token.type ! TokenType.EOF: stmt self.statement() statements.append(stmt) return Program(statements) def parse(self): 解析入口返回整个程序的AST return self.program()关键点解析与实操心得运算符优先级与结合性优先级是通过调用顺序实现的。expr(处理,-) 调用term(处理*,/)term又调用factor(处理原子项)。这确保了*和/比和-绑定得更紧。结合性左结合是通过while循环实现的例如在term中1 * 2 * 3会被解析为((1 * 2) * 3)。递归下降的“递归”注意factor函数中当遇到左括号时它会递归调用expr。这正是处理嵌套表达式(1 2) * 3的关键。递归下降能很自然地处理语法的递归定义。eat方法的作用这是语法分析中的“消费”动作。它检查当前令牌是否符合预期符合则“吃掉”它并获取下一个令牌不符合则报语法错误。这是保证解析过程与语法规则同步的核心机制。错误处理目前的错误处理很初级。更好的做法是记录错误位置、期望的令牌类型并尝试同步到下一个语句的起始点如分号以便报告多个错误。让我们测试语法分析器code x 10; y x 5 * 2; print(y); lexer Lexer(code) parser Parser(lexer) ast parser.parse() # 此时ast是一个Program节点包含三个语句。 # 第二个赋值语句的表达式AST大致为 # AssignStmt(y, BinOp(Var(x), PLUS, BinOp(Num(5), MULTIPLY, Num(2))))我们成功地将令牌流转换为了结构化的 AST。这棵树清晰地表达了运算的优先级和嵌套关系。5. 第三阶段代码生成——从抽象语法树到目标代码现在我们手握程序的完整结构描述AST最后一步就是“翻译”。我们将遍历这棵 AST为每种节点类型生成对应的 C 语言代码片段。5.1 设计代码生成器代码生成器本质上是一个树遍历器。我们采用访问者模式Visitor Pattern的思想为每种 AST 节点编写一个生成方法。class CodeGenerator: def __init__(self): self.code_lines [] # 存储生成的C代码行 self.variables set() # 记录所有已声明的变量 def generate(self, node: ASTNode): 分发生成函数 if isinstance(node, Program): return self.generate_program(node) elif isinstance(node, AssignStmt): return self.generate_assign(node) elif isinstance(node, PrintStmt): return self.generate_print(node) elif isinstance(node, BinOp): return self.generate_binop(node) elif isinstance(node, Num): return self.generate_num(node) elif isinstance(node, Var): return self.generate_var(node) else: raise Exception(fUnknown AST node type: {type(node)}) def generate_program(self, node: Program): 生成完整的C程序框架 # 1. 生成C程序头部 self.code_lines.append(#include stdio.h) self.code_lines.append(int main() {) # 2. 为所有变量生成声明C语言需要先声明后使用 # 注意我们这里假设所有变量都是int类型。更复杂的编译器需要类型系统。 for var_name in sorted(self.variables): self.code_lines.append(f int {var_name};) # 3. 生成所有语句的代码 for stmt in node.statements: stmt_code self.generate(stmt) if stmt_code: # 赋值语句生成的是表达式需要加上分号 if not stmt_code.strip().endswith(;): stmt_code ; self.code_lines.append( stmt_code) # 4. 生成程序尾部 self.code_lines.append( return 0;) self.code_lines.append(}) return \n.join(self.code_lines) def generate_assign(self, node: AssignStmt): 生成赋值语句代码: identifier expression; self.variables.add(node.identifier) # 记录变量 expr_code self.generate(node.expression) return f{node.identifier} {expr_code} def generate_print(self, node: PrintStmt): 生成printf语句代码 expr_code self.generate(node.expression) return fprintf(%d\\n, {expr_code}) # 假设表达式结果是整数 def generate_binop(self, node: BinOp): 生成二元运算代码需要处理运算符映射 left_code self.generate(node.left) right_code self.generate(node.right) op_map { TokenType.PLUS: , TokenType.MINUS: -, TokenType.MULTIPLY: *, TokenType.DIVIDE: /, } c_op op_map.get(node.op) if not c_op: raise Exception(fUnsupported operator: {node.op}) # 为运算加上括号以确保优先级正确虽然AST已保证但生成时加括号更安全 return f({left_code} {c_op} {right_code}) def generate_num(self, node: Num): return str(node.value) def generate_var(self, node: Var): return node.name5.2 整合与测试完整流程现在让我们把词法分析、语法分析和代码生成三个模块串联起来形成一个完整的编译器前端。def compile_minilang(source_code: str) - str: MiniLang编译器主函数 # 1. 词法分析 lexer Lexer(source_code) # 2. 语法分析 parser Parser(lexer) ast parser.parse() # 3. 代码生成 generator CodeGenerator() c_code generator.generate(ast) return c_code # 测试我们的编译器 mini_program x 10; y x 5 * 2; print(y); try: generated_c compile_minilang(mini_program) print(生成的C代码) print(generated_c) except Exception as e: print(f编译错误: {e})运行上述代码你将得到如下输出#include stdio.h int main() { int x; int y; x 10; y (x (5 * 2)); printf(%d\n, y); return 0; }代码生成阶段的注意事项变量声明C语言要求变量先声明后使用。我们在generate_program中遍历所有收集到的变量名在generate_assign时收集统一在main函数开头声明。这是一个简单的策略。更复杂的做法是在语法分析阶段构建符号表Symbol Table。运算符映射需要将我们自定义的令牌运算符映射到目标语言C的运算符。这是一个简单的查表过程。表达式括号我们在生成二元运算时为左右操作数都加上了括号。虽然 AST 已经确保了优先级但无脑加括号是最安全的做法能避免因生成逻辑复杂导致的优先级错误。在优化阶段可以移除冗余的括号。类型系统我们的 MiniLang 只有整数类型。一个真正的编译器必须有类型系统在语法分析或语义分析阶段检查类型是否匹配例如不能将字符串赋值给整型变量并在代码生成时根据类型决定如何生成目标代码如整数运算和浮点数运算的指令不同。6. 功能扩展与常见问题排查一个基础的编译器已经完成。但它是脆弱的只能处理完美的输入。接下来我们探讨如何让它更健壮并处理一些常见的扩展需求。6.1 添加对浮点数的支持目前我们的词法分析器只识别整数数字节点也只存储整数。要支持浮点数如3.14需要修改词法分析器number方法def number(self): result while self.current_char is not None and self.current_char.isdigit(): result self.current_char self.advance() # 处理小数点 if self.current_char .: result . self.advance() while self.current_char is not None and self.current_char.isdigit(): result self.current_char self.advance() # 返回时可以标记为浮点数字面量或者统一为数字 # 我们需要扩展TokenType或用一个字段标记 return Token(TokenType.NUMBER, result) # 现在value可能是3.14修改语法分析器在factor中创建Num节点时需要判断字符串是否包含小数点以决定存储为int还是float。修改代码生成器C语言中整数和浮点数类型不同。我们需要引入简单的类型推导或类型声明。一个简单策略是如果数字包含小数点或运算涉及浮点数则使用double类型。这需要扩展 AST 节点以携带类型信息并在代码生成时生成double类型的变量和printf(%f\\n, ...)。6.2 添加注释支持注释在词法分析阶段就应该被忽略。添加对单行注释//和多行注释/* */的支持class Lexer: # ... 其他代码不变 ... def skip_comment(self): 跳过注释 if self.current_char / and self.pos 1 len(self.text): next_char self.text[self.pos 1] # 单行注释 if next_char /: self.advance() # 消耗第一个 / self.advance() # 消耗第二个 / while self.current_char is not None and self.current_char ! \n: self.advance() # 多行注释 elif next_char *: self.advance() # 消耗 / self.advance() # 消耗 * while self.current_char is not None: if self.current_char * and self.pos 1 len(self.text) and self.text[self.pos 1] /: self.advance() # 消耗 * self.advance() # 消耗 / break self.advance() else: self.error(Unterminated multi-line comment) # 否则就是一个除法运算符不处理 # 如果不是注释开始则什么也不做 def get_next_token(self): while self.current_char is not None: # ... 跳过空白字符 ... # 在识别数字、标识符等之前检查是否是注释 if self.current_char /: # 先 peek 一下看是不是注释 start_pos self.pos self.skip_comment() # 如果跳过了注释pos会前进current_char会改变 if self.pos start_pos: continue # 重新开始循环获取下一个有效令牌 # 如果不是注释则继续往下被识别为 DIVIDE 运算符 # ... 其他令牌识别逻辑 ...6.3 常见编译错误与排查在开发编译器过程中你会遇到各种错误。下面是一个速查表错误现象可能原因排查方向KeyError或AttributeError在代码生成时AST 节点类型未在CodeGenerator.generate中处理检查是否新增了 AST 节点类型但未添加对应的generate_xxx方法和分发逻辑。生成的 C 代码编译失败语法错误代码生成逻辑错误如缺少分号、括号不匹配、变量未声明1. 打印出生成的 C 代码用肉眼或 C 编译器检查。2. 检查generate_program中变量声明部分是否包含了所有使用的变量。3. 检查每个语句生成后是否正确添加了分号。语法分析器报错“Expected X, got Y”1. 源代码不符合语法。2. 词法分析器错误地将字符分组如将识别为两个。3. 语法分析器规则有误未能覆盖所有合法情况。1. 确认输入程序是否符合 MiniLang 语法。2. 在语法分析器报错的位置打印出之前的令牌流看词法分析输出是否正确。3. 使用简单的输入如单个语句逐步调试语法分析器的各个函数。词法分析器将标识符和数字连在一起number()或identifier()函数边界判断逻辑有误确保循环条件正确。例如identifier()在遇到数字后是否应该停止对于var123应该是允许的。检查isalnum()的使用。运算符优先级错误语法分析器中expr,term,factor的调用关系错误回顾语法定义。乘除应在加减之前被组合。确保expr调用termterm调用factor。使用1 2 * 3这样的用例测试。递归深度过大递归错误语法存在左递归且递归下降解析器未消除左递归。递归下降解析器不能处理直接的左递归文法如A - A B。需要改写文法为等价的右递归形式如A - B A A - B A6.4 迈向更真实的编译器下一步是什么这个简单的编译器只是一个起点。如果你想继续深入可以考虑以下方向语义分析在语法分析和代码生成之间加入语义分析阶段。构建符号表检查变量是否先声明后使用我们目前是隐式声明、类型是否匹配、函数调用参数是否正确等。支持控制流添加if-else、while循环语句。这需要扩展 AST 节点IfStmt,WhileStmt并在代码生成中生成对应的 C 控制流语句if,while。同时可能需要引入布尔表达式和比较运算符,!,,。生成真正的汇编或字节码将目标从 C 代码改为 x86 汇编或 JVM 字节码、Python 字节码等。这将涉及寄存器分配、栈管理、调用约定等更底层的知识挑战巨大但收获也巨大。优化在 AST 层面或生成中间表示IR后进行优化例如常量折叠将2 * 3直接计算为6、公共子表达式消除等。错误恢复与友好报错实现能报告多个错误并尽可能继续分析的编译器给出清晰的错误信息和位置行号、列号。构建这个简易编译器的过程就像亲手搭建了一个模型它揭示了那些庞大工业编译器如 GCC、LLVM最核心、最本质的工作原理。下次当你使用-O2优化选项或者遇到一个晦涩的编译错误时你脑海中对这个流程的认知或许能帮你更快地理解到底发生了什么。编程语言不再是魔法而是你手中可以剖析和塑造的工具。