1. 项目概述为什么我们要“手搓”一个编译器在编程的世界里编译器就像一个无所不能的翻译官。我们写的那些人类可读的代码比如int a 10;或者if (x 5) { ... }对它来说就是一门需要翻译的外语。它的核心工作就是把这些高级语言如C、Java、Python的源代码精准无误地转换成计算机CPU能直接理解和执行的机器码。你每天用的各种软件背后都离不开编译器的默默工作。但编译器本身对大多数开发者来说却像一个黑盒——我们知道输入和输出却很少关心中间那复杂精妙的转换过程。这就是我决定动手“从零开始构建一个简单的编译器”的原因。不是为了造一个能替代GCC或LLVM的工业级工具那工程量太大了。我的目标很纯粹亲手拆解这个黑盒把“翻译”的过程一步步具象化。通过实现最核心的三个阶段——词法分析、语法分析和代码生成——来彻底理解一段我们随手写下的字符究竟是如何变成让芯片“动起来”的指令的。这个过程能极大地加深你对编程语言本质的理解让你在调试一些诡异语法错误时能立刻想到背后是哪一步分析出了岔子也能让你在接触各种新语言的语法糖时一眼看穿它的实现原理。这个项目适合所有对编程有好奇心的人。无论你是刚学完数据结构、想找个综合项目练手的学生还是已经工作、想深入理解工具链的开发者甚至是好奇AI代码生成如GitHub Copilot背后原理的探索者跟着走一遍这个流程都会有豁然开朗的感觉。我们选择的实现语言是Python因为它语法简洁能让我们专注于编译器逻辑本身而不是内存管理之类的细节。最终我们会实现一个能编译简单算术表达式和赋值语句的微型编译器比如把a 3 5 * 2这样的字符串转换成类似汇编的中间代码或直接求值。麻雀虽小五脏俱全核心思想与大型编译器一脉相承。2. 编译器整体架构与核心流程拆解一个典型的编译器其工作流程是一条清晰的“流水线”。我们的简易编译器将遵循经典的三阶段模型这也是理解所有复杂编译器的基石。2.1 核心三阶段模型详解我们的编译器管线主要分为三个阶段数据像流水一样依次经过它们形态不断发生变化词法分析器也称为扫描器。它的任务最简单直接就是读入源代码字符串把它切分成一个个有意义的“单词”专业术语叫“词法单元”或“Token”。例如对于字符串“sum 123 abc”扫描器会识别出sum- 标识符TokenType: IDENTIFIER, Value: “sum”- 赋值运算符TokenType: ASSIGN_OP123- 整数常量TokenType: INTEGER, Value: 123- 加法运算符TokenType: PLUS_OPabc- 标识符TokenType: IDENTIFIER, Value: “abc” 它会忽略空格、换行、注释这些无关紧要的字符。你可以把它想象成阅读文章时的“分词”过程。语法分析器也称为解析器。这是编译器的“大脑”。它接收词法分析器产出的Token流然后根据预定义的语法规则检查这些Token的排列组合是否符合规矩并同时构建出一种树形的数据结构——抽象语法树。语法规则就像句子的主谓宾结构。例如它规定一个“赋值语句”必须由“标识符 等号 表达式”构成。解析器会检查Token流是否符合这条规则如果符合就生成一棵以“赋值”为根节点左子树是标识符“sum”右子树是表达式“123 abc”的AST。如果遇到123 sum这种乱序它就会报语法错误。代码生成器这是最终的“翻译官”。它遍历上一步生成的AST根据每个节点的类型和含义生成等价的目标代码。对于我们的简易编译器目标代码可以是另一种更简单的中间表示比如三地址码也可以是直接对AST进行求值。例如遍历“123 abc”这棵子树时代码生成器会生成类似t1 123; t2 abc; t3 t1 t2;的指令序列最后生成sum t3。注意工业级编译器在这三个阶段前后还有更多环节如语义分析类型检查、优化、链接等。但词法、语法、代码生成是其中最核心、最不可或缺的骨架。先吃透骨架再理解血肉就简单多了。2.2 技术选型与实现语言考量为什么用Python在这样一个教学性质的项目中选择Python有几点压倒性优势开发效率高丰富的内置数据结构列表、字典和字符串处理能力能让我们快速实现状态机、树形结构无需纠缠于底层细节。表达力强代码清晰接近伪代码重点突出算法逻辑本身。生态支持好有graphviz等库可以轻松可视化AST调试直观。当然这并不意味着编译器必须用Python写。像GCC、LLVM这样的生产级编译器多用C/C编写追求极致的性能。Java有ANTLRRust有nom这些语言在实现编译器时各有其生态和范式。但Python是我们快速理解概念、验证想法的最佳“脚手架”。3. 第一阶段词法分析器的深度实现词法分析是编译器的“第一印象”。它必须准确、无歧义地将字符流转化为Token流。3.1 定义Token类型与状态机设计首先我们要定义我们的微型语言包含哪些类型的“单词”。我们创建一个TokenType枚举在Python中可以用类或字符串常量和Token类。class TokenType: # 关键字 (我们的微型语言可能先不定义关键字或只定义少数几个) # KEYWORD_IF IF # KEYWORD_THEN THEN # 标识符和字面量 IDENTIFIER IDENTIFIER # 变量名如 sum, count INTEGER INTEGER # 整数如 123 # 运算符 ASSIGN_OP # 赋值 PLUS_OP # 加 MINUS_OP - # 减 MULTIPLY_OP * # 乘 DIVIDE_OP / # 除 # 分隔符 LPAREN ( # 左括号 RPAREN ) # 右括号 SEMICOLON ; # 分号语句结束 # 特殊Token EOF EOF # 文件结束标志 class Token: def __init__(self, type_: TokenType, value: str None, lineno: int None, column: int None): self.type type_ self.value value # 对于INTEGERvalue是数字字符串对于IDENTIFIER是变量名字符串 self.lineno lineno self.column column def __repr__(self): return fToken({self.type}, {repr(self.value)})词法分析器的核心是一个有限状态自动机。它逐个读取字符根据当前字符和状态决定是继续累积当前Token的字符还是结束当前Token并开始下一个。例如初始状态读到一个字母进入“识别标识符”状态。“识别标识符”状态继续读字母或数字直到遇到非字母数字的字符如运算符、空格则生成一个IDENTIFIER Token并回退一个字符回到初始状态。初始状态读到一个数字进入“识别整数”状态。“识别整数”状态继续读数字直到遇到非数字字符生成INTEGER Token回退。3.2 核心扫描逻辑与字符处理下面是一个高度简化的扫描器核心循环代码框架展示了状态机的思想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 self.lineno 1 self.column 1 def advance(self): 向前移动一个字符更新行列号 if self.current_char \n: self.lineno 1 self.column 1 else: self.column 1 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 integer(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() return 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(): start_col self.column value self.integer() return Token(TokenType.INTEGER, value, self.lineno, start_col) # 识别标识符以字母或下划线开头 if self.current_char.isalpha() or self.current_char _: start_col self.column value self.identifier() # 这里可以加入关键字判断例如 if value if: return Token(TokenType.KEYWORD_IF) return Token(TokenType.IDENTIFIER, value, self.lineno, start_col) # 识别单字符运算符 start_col self.column char self.current_char if char : self.advance(); return Token(TokenType.PLUS_OP, char, self.lineno, start_col) if char -: self.advance(); return Token(TokenType.MINUS_OP, char, self.lineno, start_col) if char *: self.advance(); return Token(TokenType.MULTIPLY_OP, char, self.lineno, start_col) if char /: self.advance(); return Token(TokenType.DIVIDE_OP, char, self.lineno, start_col) if char : self.advance(); return Token(TokenType.ASSIGN_OP, char, self.lineno, start_col) if char (: self.advance(); return Token(TokenType.LPAREN, char, self.lineno, start_col) if char ): self.advance(); return Token(TokenType.RPAREN, char, self.lineno, start_col) if char ;: self.advance(); return Token(TokenType.SEMICOLON, char, self.lineno, start_col) # 遇到无法识别的字符抛出错误 raise Exception(fLexer error at line {self.lineno}, column {self.column}: Unexpected character {self.current_char}) # 源代码已读完返回EOF Token return Token(TokenType.EOF, None, self.lineno, self.column)3.3 词法分析中的常见陷阱与调试技巧陷阱一忘记处理空白字符。如果不在主循环开始时跳过空白那么空格本身也会被当作一个未知字符导致解析错误。skip_whitespace()必须在识别任何Token之前调用。陷阱二数字解析的边界。上面的integer()函数只处理了十进制整数。如果需要支持浮点数、十六进制0x开头状态机会更复杂。务必在识别到第一个数字后根据后续字符如 ‘.’, ‘x’切换到不同的子状态。陷阱三标识符与关键字的冲突。像if,while这样的字符串既是关键字也是合法的标识符格式。通常的解决方法是先统一按标识符规则解析出来然后在一个“关键字表”里查找。如果查到了就返回关键字Token否则返回标识符Token。这个查表操作应该在identifier()返回后立即进行。调试技巧在开发初期单独测试词法分析器非常有效。写一个简单的测试程序输入“a 42 (b * 3);”然后循环调用get_next_token()并打印直到遇到EOF。确保输出的Token序列完全符合你的预期。给Token加上行列号信息在报错时能精准定位到源代码位置这是专业编译器的基本素养。4. 第二阶段语法分析器与抽象语法树构建语法分析是编译器的核心智慧所在。它不仅要检查语法是否正确更要构建出程序的层次化结构模型——AST。4.1 文法定义与递归下降解析法首先我们需要用形式化的方式定义我们微型语言的语法规则这称为“文法”。我们使用巴科斯范式的一种变体来描述program : statement statement : assignment_statement | expression_statement assignment_statement : IDENTIFIER expression ; expression_statement : expression ; expression : term (( | -) term)* term : factor ((* | /) factor)* factor : INTEGER | IDENTIFIER | ( expression )解释一下program程序由一条或多条statement语句组成。statement可以是赋值语句或表达式语句。assignment_statement赋值语句的模式是标识符、等号、一个表达式、分号。expression表达式被定义为一个term后面可以跟零个或多个加减号 term的组合。这确保了加减法是左结合的并且优先级低于乘除。term项被定义为一个factor后面可以跟零个或多个乘除号 factor的组合。这赋予了乘除法更高的优先级。factor因子是表达式的最小单元可以是整数、标识符变量或者用括号括起来的另一个表达式。括号在这里提供了显式的优先级控制。我们采用递归下降分析法来实现这个解析器。它的思想非常直观为文法中的每一条规则program,statement,expression,term,factor编写一个对应的函数。这个函数负责“吃掉”并检查当前Token流中属于它这部分规则的所有Token并返回构建好的AST节点。4.2 AST节点设计与树形结构生成在写解析函数前先定义AST的节点类型。AST节点是带标签的树节点每个标签对应一种语法结构。class ASTNode: 抽象语法树节点的基类 pass class BinOpNode(ASTNode): 二元操作节点如 a b, c * d def __init__(self, left: ASTNode, op: Token, right: ASTNode): self.left left self.op op # 操作符Token如 PLUS_OP self.right right def __repr__(self): return fBinOp({self.left}, {self.op.type}, {self.right}) class NumNode(ASTNode): 数字字面量节点 def __init__(self, token: Token): self.token token self.value token.value def __repr__(self): return fNum({self.value}) class VarNode(ASTNode): 变量节点 def __init__(self, token: Token): self.token token self.name token.value def __repr__(self): return fVar({self.name}) class AssignNode(ASTNode): 赋值语句节点 def __init__(self, left: VarNode, op: Token, right: ASTNode): self.left left # 一定是一个变量节点 self.op op # 赋值操作符Token self.right right # 一个表达式节点 def __repr__(self): return fAssign({self.left}, {self.right})4.3 递归下降解析器的核心实现解析器类将持有词法分析器实例并提供一个“当前Token”的视图。class Parser: def __init__(self, lexer: Lexer): self.lexer lexer self.current_token self.lexer.get_next_token() # 初始化获取第一个Token def eat(self, token_type: TokenType): “消耗”当前Token并获取下一个Token。如果当前Token类型不匹配则报错。 if self.current_token.type token_type: self.current_token self.lexer.get_next_token() else: raise Exception(fSyntax error at line {self.current_token.lineno}: Expected {token_type}, got {self.current_token.type}) def factor(self): 解析因子整数 | 标识符 | ( expression ) token self.current_token if token.type TokenType.INTEGER: self.eat(TokenType.INTEGER) return NumNode(token) elif token.type TokenType.IDENTIFIER: self.eat(TokenType.IDENTIFIER) return VarNode(token) elif token.type TokenType.LPAREN: self.eat(TokenType.LPAREN) node self.expression() # 递归解析括号内的表达式 self.eat(TokenType.RPAREN) return node else: raise Exception(fSyntax error at line {token.lineno}: Unexpected factor {token}) def term(self): 解析项factor ((* | /) factor)* node self.factor() # 解析第一个因子 # 循环处理所有连续的乘除因子 while self.current_token.type in (TokenType.MULTIPLY_OP, TokenType.DIVIDE_OP): op_token self.current_token if op_token.type TokenType.MULTIPLY_OP: self.eat(TokenType.MULTIPLY_OP) else: self.eat(TokenType.DIVIDE_OP) right_node self.factor() node BinOpNode(leftnode, opop_token, rightright_node) return node def expression(self): 解析表达式term (( | -) term)* node self.term() # 解析第一个项 # 循环处理所有连续的加减项 while self.current_token.type in (TokenType.PLUS_OP, TokenType.MINUS_OP): op_token self.current_token if op_token.type TokenType.PLUS_OP: self.eat(TokenType.PLUS_OP) else: self.eat(TokenType.MINUS_OP) right_node self.term() node BinOpNode(leftnode, opop_token, rightright_node) return node def assignment_statement(self): 解析赋值语句IDENTIFIER expression ; # 左值必须是一个变量 left_token self.current_token self.eat(TokenType.IDENTIFIER) left_node VarNode(left_token) # 等号 op_token self.current_token self.eat(TokenType.ASSIGN_OP) # 右值是一个表达式 right_node self.expression() # 分号 self.eat(TokenType.SEMICOLON) return AssignNode(leftleft_node, opop_token, rightright_node) def statement(self): 解析语句尝试按赋值语句解析否则按表达式语句解析 # 这里做一个简单的预读如果下一个Token是标识符且再下一个是等号则是赋值 # 更健壮的做法需要更复杂的预读这里简化处理 if self.current_token.type TokenType.IDENTIFIER: # 偷看下一个Token # 注意在实际中我们需要一个“peek”方法这里为了简化先按赋值解析出错再回退会复杂。 # 我们假设我们的语法里语句开头是标识符就只有赋值这一种可能。 return self.assignment_statement() else: # 否则是表达式语句 node self.expression() self.eat(TokenType.SEMICOLON) return node def program(self): 解析整个程序statement statements [] while self.current_token.type ! TokenType.EOF: stmt_node self.statement() statements.append(stmt_node) return statements # 返回一个语句节点的列表4.4 语法分析中的优先级、结合性与错误恢复优先级在我们的文法中乘除法term比加减法expression优先级高是通过文法规则的分层实现的。expression由term组成而term由factor组成。解析器会先调用最深层的factor然后组合成term最后组合成expression自然实现了“先乘除后加减”。结合性加减乘除都是左结合的即a - b - c等价于(a - b) - c。这在term和expression函数的while循环中实现node BinOpNode(leftnode, opop_token, rightright_node)每次都将新的操作符和右节点与之前已经构建好的左节点结合形成新的左节点从而保证了左结合。错误恢复上面的简易解析器在遇到错误时直接抛出异常这对于学习是清晰的但对用户不友好。一个成熟的编译器应尝试从错误中恢复继续解析后续代码以便报告更多错误。简单的错误恢复策略包括恐慌模式跳过Token直到遇到一个同步点如分号、短语层恢复等。这涉及到更复杂的eat()函数实现。5. 第三阶段代码生成与解释执行有了AST这棵结构清晰的树最后一步就是“执行”它。对于我们的教学编译器最简单的“代码生成”就是直接解释执行这棵树。5.1 遍历AST与解释器设计我们将实现一个树遍历解释器。它深度优先遍历AST对于不同类型的节点执行相应的操作。class Interpreter: def __init__(self): self.variable_table {} # 符号表存储变量名和值的映射 def visit(self, node: ASTNode): 访问AST节点的分发方法 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_NumNode(self, node: NumNode): 访问数字节点直接返回值 return node.value def visit_VarNode(self, node: VarNode): 访问变量节点从符号表中查找值如果未定义则报错 var_name node.name if var_name in self.variable_table: return self.variable_table[var_name] else: raise Exception(fRuntime error: Variable {var_name} is not defined.) def visit_BinOpNode(self, node: BinOpNode): 访问二元操作节点递归计算左右子树然后执行运算 left_val self.visit(node.left) right_val self.visit(node.right) if node.op.type TokenType.PLUS_OP: return left_val right_val elif node.op.type TokenType.MINUS_OP: return left_val - right_val elif node.op.type TokenType.MULTIPLY_OP: return left_val * right_val elif node.op.type TokenType.DIVIDE_OP: # 简单处理除零错误 if right_val 0: raise Exception(Runtime error: Division by zero.) return left_val // right_val # 使用整数除法 else: raise Exception(fRuntime error: Unknown operator {node.op.type}) def visit_AssignNode(self, node: AssignNode): 访问赋值节点计算右值表达式存入符号表 var_name node.left.name value self.visit(node.right) self.variable_table[var_name] value return value # 赋值表达式本身也有值这里返回被赋予的值 def interpret(self, ast_list): 解释执行整个AST语句列表 result None for node in ast_list: result self.visit(node) # 可以打印每个语句的执行结果对于赋值语句就是被赋的值 # print(fStatement result: {result}) return result # 返回最后一个语句的结果5.2 从解释执行到真实代码生成上面的解释器是“边遍历边计算”。真正的代码生成器则是“边遍历边输出指令”。例如对于表达式a 3 5 * 2一个简单的代码生成器可能输出如下的三地址码t1 5 * 2 # 计算乘法 t2 3 t1 # 计算加法 a t2 # 赋值要实现这个我们需要修改访问者模式让每个visit_方法不再返回值而是返回一个“位置”比如临时变量名t1,t2或者最终变量名a并生成对应的指令字符串添加到一个指令列表中。这更接近传统编译器的后端工作。5.3 集成测试与效果验证让我们把三个阶段串联起来进行一次完整的测试。def main(): # 1. 源代码 source_code a 3 5 * 2; b (a 1) / 2; # 2. 词法分析 print( 词法分析 ) lexer Lexer(source_code) token lexer.get_next_token() while token.type ! TokenType.EOF: print(token) token lexer.get_next_token() print(Token(TokenType.EOF)) # 打印EOF # 重置词法分析器 lexer Lexer(source_code) # 3. 语法分析 print(\n 语法分析 AST ) parser Parser(lexer) ast_list parser.program() for i, stmt in enumerate(ast_list): print(fStatement {i}: {stmt}) # 4. 解释执行 print(\n 解释执行 ) interpreter Interpreter() final_result interpreter.interpret(ast_list) print(f执行完毕。最终结果最后一个表达式的值: {final_result}) print(f符号表内容: {interpreter.variable_table}) if __name__ __main__: main()运行这段代码你将看到词法分析器将源代码拆分成一个个Token。语法分析器构建出两棵AST分别对应两条赋值语句。解释器执行后符号表中a的值为13(3 5*2)b的值为7((131)/2 的整数除法结果)。6. 常见问题、扩展方向与实战心得在亲手实现这个简易编译器的过程中你一定会遇到各种问题。下面是我总结的一些常见坑点和进阶思路。6.1 开发与调试中的典型问题问题现象可能原因排查思路与解决方案词法分析器将123abc识别为一个Token标识符规则没有正确区分数字开头的情况。在get_next_token的主循环中数字识别 (isdigit()) 的检查必须放在字母识别 (isalpha())之前。因为1既是数字也是字母判断为真顺序错了就会进入标识符解析路径。解析a 5 ;时不报错或者报错位置不对语法错误处理太弱eat()函数可能消耗了不该消耗的Token或者错误恢复机制缺失。在factor(),term()等函数中在else分支抛出异常时要携带当前Token的行列信息。考虑实现一个peek()方法预读下一个Token帮助做出更准确的解析决策。表达式10 / 3结果为3不是3.333...解释器在visit_BinOpNode中使用了整数除法//。根据语言设计意图选择。如果想支持浮点数词法分析需要增加对浮点字面量如3.14的支持并且解释器应使用浮点除法/。同时需要引入类型系统来区分整数和浮点数。复杂的表达式如a b 5解析失败当前文法不支持连续赋值。赋值语句的右部只能是表达式不能是另一个赋值。修改文法使expression可以包含赋值操作。这需要调整文法优先级通常赋值运算符的优先级是最低的。对应的解析函数也需要重构。6.2 项目功能扩展与深化思路这个基础框架有巨大的扩展空间每深入一步你对编译器的理解就加深一层增加更多语法特性控制流实现if-else语句和while循环。这需要在AST中增加IfNode和WhileNode并在解释器中实现条件判断和跳转逻辑。函数定义与调用增加def和return关键字以及函数调用func()。这需要引入作用域管理、参数传递、栈帧等概念是质的飞跃。复合数据类型支持数组、简单的结构体。这涉及到内存布局和地址计算。构建真正的代码生成器生成三地址码如前所述修改访问者使其输出一种简单的中间表示。这种IR更容易进行后续优化。生成汇编代码以x86或ARM汇编为例学习如何将高级操作映射到有限的CPU指令集如何管理寄存器、栈帧。这是理解计算机体系结构的绝佳实践。对接LLVM IR一个更高级的玩法是让你的编译器前端生成LLVM中间表示然后利用强大的LLVM后端去优化和生成机器码。这样你就能快速得到一个功能相当强大的编译器。实现语义分析类型检查在语法分析之后代码生成之前增加一个“语义分析”阶段。遍历AST检查运算类型是否匹配如不能将字符串与数字相加、变量是否在使用前已声明等。符号表管理建立一个结构化的符号表记录每个标识符的类型、作用域等信息。6.3 从“玩具”到“工具”的实战心得测试驱动编译器项目非常适合测试驱动开发。为词法分析器、语法分析器、解释器分别编写单元测试。从最简单的用例如单个数字开始逐步增加复杂度如带括号的表达式、嵌套语句。这能极大提升开发效率和代码质量。可视化调试在开发语法分析器时将生成的AST用graphviz等工具可视化出来非常直观。一眼就能看出你的解析是否正确优先级和结合性是否处理得当。阅读经典当你卡在某个设计问题时去阅读经典教材如《编译原理》龙书或著名教学编译器如lcc,tcc,chibicc的源代码往往会茅塞顿开。不要怕代码量小我们这个项目已经涵盖了最核心的思想。理解比实现更重要这个项目的价值不在于你写出了多少行代码而在于你通过动手把那些抽象的概念有限状态机、递归下降、AST、访问者模式变成了肌肉记忆。下次当你再使用任何编程语言时你看到的将不再是一行行字符而是一棵棵流动的语法树。这种视角的转变是成为一名更深层次开发者的开始。最后别忘了享受这个过程。亲手让一堆字符串按照你定义的规则“活”起来变成可执行的动作这种创造和控制的乐趣正是编程最原始的吸引力之一。你的微型编译器就是这份乐趣的一个完美注脚。
从零构建编译器：Python实现词法分析、语法分析与代码生成
1. 项目概述为什么我们要“手搓”一个编译器在编程的世界里编译器就像一个无所不能的翻译官。我们写的那些人类可读的代码比如int a 10;或者if (x 5) { ... }对它来说就是一门需要翻译的外语。它的核心工作就是把这些高级语言如C、Java、Python的源代码精准无误地转换成计算机CPU能直接理解和执行的机器码。你每天用的各种软件背后都离不开编译器的默默工作。但编译器本身对大多数开发者来说却像一个黑盒——我们知道输入和输出却很少关心中间那复杂精妙的转换过程。这就是我决定动手“从零开始构建一个简单的编译器”的原因。不是为了造一个能替代GCC或LLVM的工业级工具那工程量太大了。我的目标很纯粹亲手拆解这个黑盒把“翻译”的过程一步步具象化。通过实现最核心的三个阶段——词法分析、语法分析和代码生成——来彻底理解一段我们随手写下的字符究竟是如何变成让芯片“动起来”的指令的。这个过程能极大地加深你对编程语言本质的理解让你在调试一些诡异语法错误时能立刻想到背后是哪一步分析出了岔子也能让你在接触各种新语言的语法糖时一眼看穿它的实现原理。这个项目适合所有对编程有好奇心的人。无论你是刚学完数据结构、想找个综合项目练手的学生还是已经工作、想深入理解工具链的开发者甚至是好奇AI代码生成如GitHub Copilot背后原理的探索者跟着走一遍这个流程都会有豁然开朗的感觉。我们选择的实现语言是Python因为它语法简洁能让我们专注于编译器逻辑本身而不是内存管理之类的细节。最终我们会实现一个能编译简单算术表达式和赋值语句的微型编译器比如把a 3 5 * 2这样的字符串转换成类似汇编的中间代码或直接求值。麻雀虽小五脏俱全核心思想与大型编译器一脉相承。2. 编译器整体架构与核心流程拆解一个典型的编译器其工作流程是一条清晰的“流水线”。我们的简易编译器将遵循经典的三阶段模型这也是理解所有复杂编译器的基石。2.1 核心三阶段模型详解我们的编译器管线主要分为三个阶段数据像流水一样依次经过它们形态不断发生变化词法分析器也称为扫描器。它的任务最简单直接就是读入源代码字符串把它切分成一个个有意义的“单词”专业术语叫“词法单元”或“Token”。例如对于字符串“sum 123 abc”扫描器会识别出sum- 标识符TokenType: IDENTIFIER, Value: “sum”- 赋值运算符TokenType: ASSIGN_OP123- 整数常量TokenType: INTEGER, Value: 123- 加法运算符TokenType: PLUS_OPabc- 标识符TokenType: IDENTIFIER, Value: “abc” 它会忽略空格、换行、注释这些无关紧要的字符。你可以把它想象成阅读文章时的“分词”过程。语法分析器也称为解析器。这是编译器的“大脑”。它接收词法分析器产出的Token流然后根据预定义的语法规则检查这些Token的排列组合是否符合规矩并同时构建出一种树形的数据结构——抽象语法树。语法规则就像句子的主谓宾结构。例如它规定一个“赋值语句”必须由“标识符 等号 表达式”构成。解析器会检查Token流是否符合这条规则如果符合就生成一棵以“赋值”为根节点左子树是标识符“sum”右子树是表达式“123 abc”的AST。如果遇到123 sum这种乱序它就会报语法错误。代码生成器这是最终的“翻译官”。它遍历上一步生成的AST根据每个节点的类型和含义生成等价的目标代码。对于我们的简易编译器目标代码可以是另一种更简单的中间表示比如三地址码也可以是直接对AST进行求值。例如遍历“123 abc”这棵子树时代码生成器会生成类似t1 123; t2 abc; t3 t1 t2;的指令序列最后生成sum t3。注意工业级编译器在这三个阶段前后还有更多环节如语义分析类型检查、优化、链接等。但词法、语法、代码生成是其中最核心、最不可或缺的骨架。先吃透骨架再理解血肉就简单多了。2.2 技术选型与实现语言考量为什么用Python在这样一个教学性质的项目中选择Python有几点压倒性优势开发效率高丰富的内置数据结构列表、字典和字符串处理能力能让我们快速实现状态机、树形结构无需纠缠于底层细节。表达力强代码清晰接近伪代码重点突出算法逻辑本身。生态支持好有graphviz等库可以轻松可视化AST调试直观。当然这并不意味着编译器必须用Python写。像GCC、LLVM这样的生产级编译器多用C/C编写追求极致的性能。Java有ANTLRRust有nom这些语言在实现编译器时各有其生态和范式。但Python是我们快速理解概念、验证想法的最佳“脚手架”。3. 第一阶段词法分析器的深度实现词法分析是编译器的“第一印象”。它必须准确、无歧义地将字符流转化为Token流。3.1 定义Token类型与状态机设计首先我们要定义我们的微型语言包含哪些类型的“单词”。我们创建一个TokenType枚举在Python中可以用类或字符串常量和Token类。class TokenType: # 关键字 (我们的微型语言可能先不定义关键字或只定义少数几个) # KEYWORD_IF IF # KEYWORD_THEN THEN # 标识符和字面量 IDENTIFIER IDENTIFIER # 变量名如 sum, count INTEGER INTEGER # 整数如 123 # 运算符 ASSIGN_OP # 赋值 PLUS_OP # 加 MINUS_OP - # 减 MULTIPLY_OP * # 乘 DIVIDE_OP / # 除 # 分隔符 LPAREN ( # 左括号 RPAREN ) # 右括号 SEMICOLON ; # 分号语句结束 # 特殊Token EOF EOF # 文件结束标志 class Token: def __init__(self, type_: TokenType, value: str None, lineno: int None, column: int None): self.type type_ self.value value # 对于INTEGERvalue是数字字符串对于IDENTIFIER是变量名字符串 self.lineno lineno self.column column def __repr__(self): return fToken({self.type}, {repr(self.value)})词法分析器的核心是一个有限状态自动机。它逐个读取字符根据当前字符和状态决定是继续累积当前Token的字符还是结束当前Token并开始下一个。例如初始状态读到一个字母进入“识别标识符”状态。“识别标识符”状态继续读字母或数字直到遇到非字母数字的字符如运算符、空格则生成一个IDENTIFIER Token并回退一个字符回到初始状态。初始状态读到一个数字进入“识别整数”状态。“识别整数”状态继续读数字直到遇到非数字字符生成INTEGER Token回退。3.2 核心扫描逻辑与字符处理下面是一个高度简化的扫描器核心循环代码框架展示了状态机的思想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 self.lineno 1 self.column 1 def advance(self): 向前移动一个字符更新行列号 if self.current_char \n: self.lineno 1 self.column 1 else: self.column 1 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 integer(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() return 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(): start_col self.column value self.integer() return Token(TokenType.INTEGER, value, self.lineno, start_col) # 识别标识符以字母或下划线开头 if self.current_char.isalpha() or self.current_char _: start_col self.column value self.identifier() # 这里可以加入关键字判断例如 if value if: return Token(TokenType.KEYWORD_IF) return Token(TokenType.IDENTIFIER, value, self.lineno, start_col) # 识别单字符运算符 start_col self.column char self.current_char if char : self.advance(); return Token(TokenType.PLUS_OP, char, self.lineno, start_col) if char -: self.advance(); return Token(TokenType.MINUS_OP, char, self.lineno, start_col) if char *: self.advance(); return Token(TokenType.MULTIPLY_OP, char, self.lineno, start_col) if char /: self.advance(); return Token(TokenType.DIVIDE_OP, char, self.lineno, start_col) if char : self.advance(); return Token(TokenType.ASSIGN_OP, char, self.lineno, start_col) if char (: self.advance(); return Token(TokenType.LPAREN, char, self.lineno, start_col) if char ): self.advance(); return Token(TokenType.RPAREN, char, self.lineno, start_col) if char ;: self.advance(); return Token(TokenType.SEMICOLON, char, self.lineno, start_col) # 遇到无法识别的字符抛出错误 raise Exception(fLexer error at line {self.lineno}, column {self.column}: Unexpected character {self.current_char}) # 源代码已读完返回EOF Token return Token(TokenType.EOF, None, self.lineno, self.column)3.3 词法分析中的常见陷阱与调试技巧陷阱一忘记处理空白字符。如果不在主循环开始时跳过空白那么空格本身也会被当作一个未知字符导致解析错误。skip_whitespace()必须在识别任何Token之前调用。陷阱二数字解析的边界。上面的integer()函数只处理了十进制整数。如果需要支持浮点数、十六进制0x开头状态机会更复杂。务必在识别到第一个数字后根据后续字符如 ‘.’, ‘x’切换到不同的子状态。陷阱三标识符与关键字的冲突。像if,while这样的字符串既是关键字也是合法的标识符格式。通常的解决方法是先统一按标识符规则解析出来然后在一个“关键字表”里查找。如果查到了就返回关键字Token否则返回标识符Token。这个查表操作应该在identifier()返回后立即进行。调试技巧在开发初期单独测试词法分析器非常有效。写一个简单的测试程序输入“a 42 (b * 3);”然后循环调用get_next_token()并打印直到遇到EOF。确保输出的Token序列完全符合你的预期。给Token加上行列号信息在报错时能精准定位到源代码位置这是专业编译器的基本素养。4. 第二阶段语法分析器与抽象语法树构建语法分析是编译器的核心智慧所在。它不仅要检查语法是否正确更要构建出程序的层次化结构模型——AST。4.1 文法定义与递归下降解析法首先我们需要用形式化的方式定义我们微型语言的语法规则这称为“文法”。我们使用巴科斯范式的一种变体来描述program : statement statement : assignment_statement | expression_statement assignment_statement : IDENTIFIER expression ; expression_statement : expression ; expression : term (( | -) term)* term : factor ((* | /) factor)* factor : INTEGER | IDENTIFIER | ( expression )解释一下program程序由一条或多条statement语句组成。statement可以是赋值语句或表达式语句。assignment_statement赋值语句的模式是标识符、等号、一个表达式、分号。expression表达式被定义为一个term后面可以跟零个或多个加减号 term的组合。这确保了加减法是左结合的并且优先级低于乘除。term项被定义为一个factor后面可以跟零个或多个乘除号 factor的组合。这赋予了乘除法更高的优先级。factor因子是表达式的最小单元可以是整数、标识符变量或者用括号括起来的另一个表达式。括号在这里提供了显式的优先级控制。我们采用递归下降分析法来实现这个解析器。它的思想非常直观为文法中的每一条规则program,statement,expression,term,factor编写一个对应的函数。这个函数负责“吃掉”并检查当前Token流中属于它这部分规则的所有Token并返回构建好的AST节点。4.2 AST节点设计与树形结构生成在写解析函数前先定义AST的节点类型。AST节点是带标签的树节点每个标签对应一种语法结构。class ASTNode: 抽象语法树节点的基类 pass class BinOpNode(ASTNode): 二元操作节点如 a b, c * d def __init__(self, left: ASTNode, op: Token, right: ASTNode): self.left left self.op op # 操作符Token如 PLUS_OP self.right right def __repr__(self): return fBinOp({self.left}, {self.op.type}, {self.right}) class NumNode(ASTNode): 数字字面量节点 def __init__(self, token: Token): self.token token self.value token.value def __repr__(self): return fNum({self.value}) class VarNode(ASTNode): 变量节点 def __init__(self, token: Token): self.token token self.name token.value def __repr__(self): return fVar({self.name}) class AssignNode(ASTNode): 赋值语句节点 def __init__(self, left: VarNode, op: Token, right: ASTNode): self.left left # 一定是一个变量节点 self.op op # 赋值操作符Token self.right right # 一个表达式节点 def __repr__(self): return fAssign({self.left}, {self.right})4.3 递归下降解析器的核心实现解析器类将持有词法分析器实例并提供一个“当前Token”的视图。class Parser: def __init__(self, lexer: Lexer): self.lexer lexer self.current_token self.lexer.get_next_token() # 初始化获取第一个Token def eat(self, token_type: TokenType): “消耗”当前Token并获取下一个Token。如果当前Token类型不匹配则报错。 if self.current_token.type token_type: self.current_token self.lexer.get_next_token() else: raise Exception(fSyntax error at line {self.current_token.lineno}: Expected {token_type}, got {self.current_token.type}) def factor(self): 解析因子整数 | 标识符 | ( expression ) token self.current_token if token.type TokenType.INTEGER: self.eat(TokenType.INTEGER) return NumNode(token) elif token.type TokenType.IDENTIFIER: self.eat(TokenType.IDENTIFIER) return VarNode(token) elif token.type TokenType.LPAREN: self.eat(TokenType.LPAREN) node self.expression() # 递归解析括号内的表达式 self.eat(TokenType.RPAREN) return node else: raise Exception(fSyntax error at line {token.lineno}: Unexpected factor {token}) def term(self): 解析项factor ((* | /) factor)* node self.factor() # 解析第一个因子 # 循环处理所有连续的乘除因子 while self.current_token.type in (TokenType.MULTIPLY_OP, TokenType.DIVIDE_OP): op_token self.current_token if op_token.type TokenType.MULTIPLY_OP: self.eat(TokenType.MULTIPLY_OP) else: self.eat(TokenType.DIVIDE_OP) right_node self.factor() node BinOpNode(leftnode, opop_token, rightright_node) return node def expression(self): 解析表达式term (( | -) term)* node self.term() # 解析第一个项 # 循环处理所有连续的加减项 while self.current_token.type in (TokenType.PLUS_OP, TokenType.MINUS_OP): op_token self.current_token if op_token.type TokenType.PLUS_OP: self.eat(TokenType.PLUS_OP) else: self.eat(TokenType.MINUS_OP) right_node self.term() node BinOpNode(leftnode, opop_token, rightright_node) return node def assignment_statement(self): 解析赋值语句IDENTIFIER expression ; # 左值必须是一个变量 left_token self.current_token self.eat(TokenType.IDENTIFIER) left_node VarNode(left_token) # 等号 op_token self.current_token self.eat(TokenType.ASSIGN_OP) # 右值是一个表达式 right_node self.expression() # 分号 self.eat(TokenType.SEMICOLON) return AssignNode(leftleft_node, opop_token, rightright_node) def statement(self): 解析语句尝试按赋值语句解析否则按表达式语句解析 # 这里做一个简单的预读如果下一个Token是标识符且再下一个是等号则是赋值 # 更健壮的做法需要更复杂的预读这里简化处理 if self.current_token.type TokenType.IDENTIFIER: # 偷看下一个Token # 注意在实际中我们需要一个“peek”方法这里为了简化先按赋值解析出错再回退会复杂。 # 我们假设我们的语法里语句开头是标识符就只有赋值这一种可能。 return self.assignment_statement() else: # 否则是表达式语句 node self.expression() self.eat(TokenType.SEMICOLON) return node def program(self): 解析整个程序statement statements [] while self.current_token.type ! TokenType.EOF: stmt_node self.statement() statements.append(stmt_node) return statements # 返回一个语句节点的列表4.4 语法分析中的优先级、结合性与错误恢复优先级在我们的文法中乘除法term比加减法expression优先级高是通过文法规则的分层实现的。expression由term组成而term由factor组成。解析器会先调用最深层的factor然后组合成term最后组合成expression自然实现了“先乘除后加减”。结合性加减乘除都是左结合的即a - b - c等价于(a - b) - c。这在term和expression函数的while循环中实现node BinOpNode(leftnode, opop_token, rightright_node)每次都将新的操作符和右节点与之前已经构建好的左节点结合形成新的左节点从而保证了左结合。错误恢复上面的简易解析器在遇到错误时直接抛出异常这对于学习是清晰的但对用户不友好。一个成熟的编译器应尝试从错误中恢复继续解析后续代码以便报告更多错误。简单的错误恢复策略包括恐慌模式跳过Token直到遇到一个同步点如分号、短语层恢复等。这涉及到更复杂的eat()函数实现。5. 第三阶段代码生成与解释执行有了AST这棵结构清晰的树最后一步就是“执行”它。对于我们的教学编译器最简单的“代码生成”就是直接解释执行这棵树。5.1 遍历AST与解释器设计我们将实现一个树遍历解释器。它深度优先遍历AST对于不同类型的节点执行相应的操作。class Interpreter: def __init__(self): self.variable_table {} # 符号表存储变量名和值的映射 def visit(self, node: ASTNode): 访问AST节点的分发方法 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_NumNode(self, node: NumNode): 访问数字节点直接返回值 return node.value def visit_VarNode(self, node: VarNode): 访问变量节点从符号表中查找值如果未定义则报错 var_name node.name if var_name in self.variable_table: return self.variable_table[var_name] else: raise Exception(fRuntime error: Variable {var_name} is not defined.) def visit_BinOpNode(self, node: BinOpNode): 访问二元操作节点递归计算左右子树然后执行运算 left_val self.visit(node.left) right_val self.visit(node.right) if node.op.type TokenType.PLUS_OP: return left_val right_val elif node.op.type TokenType.MINUS_OP: return left_val - right_val elif node.op.type TokenType.MULTIPLY_OP: return left_val * right_val elif node.op.type TokenType.DIVIDE_OP: # 简单处理除零错误 if right_val 0: raise Exception(Runtime error: Division by zero.) return left_val // right_val # 使用整数除法 else: raise Exception(fRuntime error: Unknown operator {node.op.type}) def visit_AssignNode(self, node: AssignNode): 访问赋值节点计算右值表达式存入符号表 var_name node.left.name value self.visit(node.right) self.variable_table[var_name] value return value # 赋值表达式本身也有值这里返回被赋予的值 def interpret(self, ast_list): 解释执行整个AST语句列表 result None for node in ast_list: result self.visit(node) # 可以打印每个语句的执行结果对于赋值语句就是被赋的值 # print(fStatement result: {result}) return result # 返回最后一个语句的结果5.2 从解释执行到真实代码生成上面的解释器是“边遍历边计算”。真正的代码生成器则是“边遍历边输出指令”。例如对于表达式a 3 5 * 2一个简单的代码生成器可能输出如下的三地址码t1 5 * 2 # 计算乘法 t2 3 t1 # 计算加法 a t2 # 赋值要实现这个我们需要修改访问者模式让每个visit_方法不再返回值而是返回一个“位置”比如临时变量名t1,t2或者最终变量名a并生成对应的指令字符串添加到一个指令列表中。这更接近传统编译器的后端工作。5.3 集成测试与效果验证让我们把三个阶段串联起来进行一次完整的测试。def main(): # 1. 源代码 source_code a 3 5 * 2; b (a 1) / 2; # 2. 词法分析 print( 词法分析 ) lexer Lexer(source_code) token lexer.get_next_token() while token.type ! TokenType.EOF: print(token) token lexer.get_next_token() print(Token(TokenType.EOF)) # 打印EOF # 重置词法分析器 lexer Lexer(source_code) # 3. 语法分析 print(\n 语法分析 AST ) parser Parser(lexer) ast_list parser.program() for i, stmt in enumerate(ast_list): print(fStatement {i}: {stmt}) # 4. 解释执行 print(\n 解释执行 ) interpreter Interpreter() final_result interpreter.interpret(ast_list) print(f执行完毕。最终结果最后一个表达式的值: {final_result}) print(f符号表内容: {interpreter.variable_table}) if __name__ __main__: main()运行这段代码你将看到词法分析器将源代码拆分成一个个Token。语法分析器构建出两棵AST分别对应两条赋值语句。解释器执行后符号表中a的值为13(3 5*2)b的值为7((131)/2 的整数除法结果)。6. 常见问题、扩展方向与实战心得在亲手实现这个简易编译器的过程中你一定会遇到各种问题。下面是我总结的一些常见坑点和进阶思路。6.1 开发与调试中的典型问题问题现象可能原因排查思路与解决方案词法分析器将123abc识别为一个Token标识符规则没有正确区分数字开头的情况。在get_next_token的主循环中数字识别 (isdigit()) 的检查必须放在字母识别 (isalpha())之前。因为1既是数字也是字母判断为真顺序错了就会进入标识符解析路径。解析a 5 ;时不报错或者报错位置不对语法错误处理太弱eat()函数可能消耗了不该消耗的Token或者错误恢复机制缺失。在factor(),term()等函数中在else分支抛出异常时要携带当前Token的行列信息。考虑实现一个peek()方法预读下一个Token帮助做出更准确的解析决策。表达式10 / 3结果为3不是3.333...解释器在visit_BinOpNode中使用了整数除法//。根据语言设计意图选择。如果想支持浮点数词法分析需要增加对浮点字面量如3.14的支持并且解释器应使用浮点除法/。同时需要引入类型系统来区分整数和浮点数。复杂的表达式如a b 5解析失败当前文法不支持连续赋值。赋值语句的右部只能是表达式不能是另一个赋值。修改文法使expression可以包含赋值操作。这需要调整文法优先级通常赋值运算符的优先级是最低的。对应的解析函数也需要重构。6.2 项目功能扩展与深化思路这个基础框架有巨大的扩展空间每深入一步你对编译器的理解就加深一层增加更多语法特性控制流实现if-else语句和while循环。这需要在AST中增加IfNode和WhileNode并在解释器中实现条件判断和跳转逻辑。函数定义与调用增加def和return关键字以及函数调用func()。这需要引入作用域管理、参数传递、栈帧等概念是质的飞跃。复合数据类型支持数组、简单的结构体。这涉及到内存布局和地址计算。构建真正的代码生成器生成三地址码如前所述修改访问者使其输出一种简单的中间表示。这种IR更容易进行后续优化。生成汇编代码以x86或ARM汇编为例学习如何将高级操作映射到有限的CPU指令集如何管理寄存器、栈帧。这是理解计算机体系结构的绝佳实践。对接LLVM IR一个更高级的玩法是让你的编译器前端生成LLVM中间表示然后利用强大的LLVM后端去优化和生成机器码。这样你就能快速得到一个功能相当强大的编译器。实现语义分析类型检查在语法分析之后代码生成之前增加一个“语义分析”阶段。遍历AST检查运算类型是否匹配如不能将字符串与数字相加、变量是否在使用前已声明等。符号表管理建立一个结构化的符号表记录每个标识符的类型、作用域等信息。6.3 从“玩具”到“工具”的实战心得测试驱动编译器项目非常适合测试驱动开发。为词法分析器、语法分析器、解释器分别编写单元测试。从最简单的用例如单个数字开始逐步增加复杂度如带括号的表达式、嵌套语句。这能极大提升开发效率和代码质量。可视化调试在开发语法分析器时将生成的AST用graphviz等工具可视化出来非常直观。一眼就能看出你的解析是否正确优先级和结合性是否处理得当。阅读经典当你卡在某个设计问题时去阅读经典教材如《编译原理》龙书或著名教学编译器如lcc,tcc,chibicc的源代码往往会茅塞顿开。不要怕代码量小我们这个项目已经涵盖了最核心的思想。理解比实现更重要这个项目的价值不在于你写出了多少行代码而在于你通过动手把那些抽象的概念有限状态机、递归下降、AST、访问者模式变成了肌肉记忆。下次当你再使用任何编程语言时你看到的将不再是一行行字符而是一棵棵流动的语法树。这种视角的转变是成为一名更深层次开发者的开始。最后别忘了享受这个过程。亲手让一堆字符串按照你定义的规则“活”起来变成可执行的动作这种创造和控制的乐趣正是编程最原始的吸引力之一。你的微型编译器就是这份乐趣的一个完美注脚。
