1. 项目概述与核心价值如果你写过代码一定对“编译”这个按钮不陌生。点击它你写的那些英文单词和符号就变成了电脑能直接运行的玩意儿。但这个过程具体是怎么发生的编译器内部是不是一个深不可测的黑盒今天我们就来亲手把这个黑盒撬开一条缝看看里面到底装着什么。我们将从零开始构建一个能处理简单算术表达式的微型编译器。别被“编译器”这个词吓到我们不做GCC、Clang那样的工业级巨兽而是做一个麻雀虽小、五脏俱全的教学级项目。通过它你会透彻理解词法分析如何把字符串切成有意义的“单词”语法分析如何检查这些“单词”是否符合语法规则并构建出程序的结构树抽象语法树AST以及代码生成如何把这棵树翻译成另一种形式比如另一种简单语言或指令。为什么值得花时间做这个首先它能极大加深你对所用编程语言的理解。当你知道了a b * c是如何被解析和求值的你就能写出更高效、更不易出错的代码。其次调试能力会直线上升。面对一个语法错误你不再只是看着编译器报错行号发呆而是能大致推断出解析器在哪个环节“卡壳”了。最后这是计算机科学核心思想的绝佳实践涉及状态机、递归、树遍历等基础且重要的概念。无论你是想深入语言虚拟机如JVM、CPython、开发领域特定语言DSL还是单纯想挑战一下智力这个项目都是一个完美的起点。我们最终的目标是输入一个像“3 5 * (10 - 4)”这样的字符串我们的编译器能正确识别出数字、运算符和括号理解乘法的优先级高于加法并最终“计算”出结果或者生成一份等价的、步骤清晰的中间代码。我们将使用Python来实现因为它语法清晰能让我们专注于逻辑而非底层细节。当然其中的原理是语言无关的。2. 编译器前端核心流程拆解在动手写代码之前我们必须把编译器的“流水线”搞清楚。传统的编译器将整个翻译过程分为前端和后端。前端负责理解源代码后端负责生成目标代码。我们的微型编译器主要实现前端的核心部分并稍作延伸至简单的代码生成。2.1 阶段一词法分析——从字符流到单词流想象一下你在读英文句子。你不是一个字母一个字母地读而是自动地将字母组合成单词比如“I”、“have”、“an”、“apple”。词法分析器Lexer或Scanner干的就是这个活儿。它的输入是源代码字符串一堆字符输出是一连串的词法单元。什么是词法单元它是一个有类型的“单词”。对于我们的算术表达式编译器我们需要定义几种类型整数像3,42,100这样的数字序列。类型可以叫INTEGER。运算符加、减-、乘*、除/。类型可以叫PLUS,MINUS,MUL,DIV。括号左括号(和右括号)。类型叫LPAREN,RPAREN。结束符表示输入结束。类型叫EOF。所以对于输入“35”词法分析器应该输出[INTEGER:3, PLUS:, INTEGER:5, EOF]。注意它不关心35在数学上是否合理比如中间没空格它只负责识别并分类。核心实现思路词法分析器本质上是一个有限状态机。它逐个读取字符根据当前字符和状态决定下一个状态和输出。例如读到一个数字字符就进入“读取整数”的状态持续读取直到遇到非数字字符然后生成一个INTEGER词法单元。实操心得在实现时一个常见的“坑”是如何高效地处理空白字符空格、制表符、换行。它们通常被直接忽略不生成任何词法单元但它们是分隔符的关键。我的做法是在读取字符的主循环中一旦遇到空白字符就继续读下一个直到遇到非空白字符再开始真正的词法分析。这能避免很多无谓的状态判断。2.2 阶段二语法分析——从单词流到结构树现在我们有了一堆单词但它们是杂乱无章的。语法分析器Parser的任务是检查这些单词的排列顺序是否符合预定义的语法规则并依据这些规则构建出一棵抽象语法树。什么是语法规则我们可以用类似巴科斯-诺尔范式BNF的形式来定义我们微型语言的语法expression : term ((PLUS | MINUS) term)* term : factor ((MUL | DIV) factor)* factor : INTEGER | LPAREN expression RPAREN这段规则定义了运算的优先级factor是最基本的单元可以是一个整数或者一个括号包裹的完整表达式。term是由factor通过乘除运算符连接而成的。expression是由term通过加减运算符连接而成的。这种定义确保了*和/的优先级高于和-并且括号可以改变优先级。语法分析器的工作就是根据这组规则去“匹配”词法单元流。抽象语法树是程序结构的树形表示。树的叶子节点通常是操作数如整数内部节点是运算符。对于3 5 * 2正确的AST应该是 / \ 3 * / \ 5 2这棵树明确表示了乘法节点*是加法节点的右子节点因此乘法先计算。核心实现思路我们将采用递归下降分析法。这是一种直观的、手工编写语法分析器的常用方法。我们为语法规则中的每个非终结符如expression,term,factor编写一个对应的函数。这些函数会递归地调用彼此同时“消费”词法单元流最终构建出AST。注意事项递归下降分析器对文法的要求比较严格通常要求是LL(1)文法即通过向前看一个词法单元就能决定使用哪条规则。我们的算术表达式文法经过上述改写后是满足LL(1)条件的。在实现factor函数时需要处理两种可能当前词法单元是INTEGER则直接构造一个叶子节点如果是LPAREN则消费掉它递归调用expression函数来解析括号内的表达式并期望下一个是RPAREN然后消费掉右括号。这个“匹配并消费”的过程是递归下降分析器的核心动作。2.3 阶段三语义分析与代码生成——遍历结构树并行动有了AST我们就掌握了程序的完整结构。接下来的步骤可以有很多方向我们这里实现一个简单的解释执行或生成中间代码。解释执行写一个解释器函数递归地遍历AST。遇到整数节点返回其值遇到运算符节点先递归计算左右子树的值然后执行对应的运算加、减、乘、除。这相当于直接“执行”了这棵语法树。生成中间代码我们生成一种非常简单的、基于栈的指令序列比如PUSH 3将数字3压入栈。PUSH 5PUSH 2MUL弹出栈顶两个元素5和2计算乘积10将结果压回栈。ADD弹出栈顶两个元素3和10计算和13将结果压回栈。 这种指令集很容易被后续的虚拟机执行。生成过程同样通过递归遍历AST完成遍历左子树生成代码遍历右子树生成代码最后生成当前节点的操作指令。我们选择生成中间代码作为目标因为它更贴近传统编译器的后端流程且生成的代码是一种清晰的、与具体机器无关的表示。常见问题在生成代码时一个关键点是求值顺序。对于表达式3 - 5 - 2正确的AST应该是左结合的(3-5)-2而不是右结合的3-(5-2)。我们的文法expression : term ((PLUS | MINUS) term)*通过循环处理同一优先级的多个运算符天然实现了左结合性。在代码生成时必须严格按照后序遍历左子树-右子树-根节点或类似顺序来生成指令才能保证运算顺序正确。3. 分步实现构建我们的微型编译器理论铺垫完毕现在开始动手。我们将创建三个主要的Python类Lexer,Parser,CodeGenerator以及一些辅助的类如Token,ASTNode。3.1 步骤一定义词法单元与AST节点这是我们的数据结构基础。# token.py class Token: def __init__(self, type, value): self.type type # 类型如 INTEGER, PLUS, EOF self.value value # 对应的值如 123, , None def __repr__(self): return fToken({self.type}, {repr(self.value)}) # ast.py class ASTNode: 抽象语法树节点的基类 pass class BinOp(ASTNode): 二元运算符节点如 , -, *, / def __init__(self, left, op, right): self.left left # 左子节点 (ASTNode) self.op op # 运算符Token (Token) self.right right # 右子节点 (ASTNode) def __repr__(self): return fBinOp({self.left}, {self.op}, {self.right}) class Num(ASTNode): 数字叶子节点 def __init__(self, token): self.token token self.value token.value def __repr__(self): return fNum({self.value})3.2 步骤二实现词法分析器Lexer类将负责驱动整个词法分析过程。# lexer.py 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): 移动到下一个字符如果到达末尾则设为None self.pos 1 if self.pos len(self.text) - 1: 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 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 Token(INTEGER, self.integer()) if self.current_char : self.advance() return Token(PLUS, ) if self.current_char -: self.advance() return Token(MINUS, -) if self.current_char *: self.advance() return Token(MUL, *) if self.current_char /: self.advance() return Token(DIV, /) if self.current_char (: self.advance() return Token(LPAREN, () if self.current_char ): self.advance() return Token(RPAREN, )) self.error() return Token(EOF, None)关键点解析advance()方法是指针推进器。skip_whitespace()确保了空白字符不会干扰词法识别。integer()方法通过循环累积数字字符直到遇到非数字字符然后一次性转换为整数。这比逐个字符处理更高效。get_next_token()是主循环通过一系列的if判断来识别不同的词法单元类型。这是一个典型的手写词法分析器结构。3.3 步骤三实现递归下降语法分析器Parser类将使用Lexer提供的词法单元流来构建AST。# parser.py class Parser: def __init__(self, lexer): self.lexer lexer self.current_token self.lexer.get_next_token() # 初始化当前词法单元 def error(self): raise Exception(Invalid syntax) def eat(self, token_type): 消费当前词法单元。如果类型匹配则获取下一个词法单元否则报错。 if self.current_token.type token_type: self.current_token self.lexer.get_next_token() else: self.error() def factor(self): 解析因子整数或括号表达式 token self.current_token if token.type INTEGER: self.eat(INTEGER) return Num(token) elif token.type LPAREN: self.eat(LPAREN) node self.expression() # 递归解析括号内的表达式 self.eat(RPAREN) return node else: self.error() def term(self): 解析项因子之间的乘除运算 node self.factor() # 解析第一个因子 # 循环处理连续的乘除运算符 while self.current_token.type in (MUL, DIV): token self.current_token if token.type MUL: self.eat(MUL) elif token.type DIV: self.eat(DIV) node BinOp(leftnode, optoken, rightself.factor()) return node def expression(self): 解析表达式项之间的加减运算 node self.term() # 解析第一个项 # 循环处理连续的加减运算符 while self.current_token.type in (PLUS, MINUS): token self.current_token if token.type PLUS: self.eat(PLUS) elif token.type MINUS: self.eat(MINUS) node BinOp(leftnode, optoken, rightself.term()) return node def parse(self): 解析的入口点返回整个表达式的AST根节点 return self.expression()递归下降的精髓每个函数expression,term,factor对应文法中的一个非终结符。函数内部通过调用其他函数来实现递归。eat()方法是推进词法单元流的“齿轮”它确保了语法分析器与词法单元流的同步。term()和expression()函数中的while循环优雅地处理了相同优先级运算符的左结合性。例如对于1 - 2 3expression()会先构造(1-2)节点然后在循环的下一次迭代中将这个节点作为左子节点与3构造出新的根节点最终得到((1-2)3)的AST。3.4 步骤四实现代码生成器我们将实现一个简单的基于栈的代码生成器。它遍历AST生成类似“PUSH”、“ADD”这样的指令。# codegen.py class CodeGenerator: def __init__(self): self.instructions [] # 存储生成的指令 def generate(self, node): 根据AST节点生成代码 if isinstance(node, Num): # 数字节点生成PUSH指令 self.instructions.append((PUSH, node.value)) elif isinstance(node, BinOp): # 二元运算符节点先处理左子树再处理右子树最后生成运算指令 self.generate(node.left) self.generate(node.right) op_map {PLUS: ADD, MINUS: SUB, MUL: MUL, DIV: DIV} self.instructions.append((op_map[node.op.type],)) else: raise Exception(fUnknown AST node type: {type(node)}) def get_code(self): 返回生成的指令列表 return self.instructions生成逻辑这是一个典型的后序遍历。对于表达式3 5其AST为BinOp(Num(3), PLUS, Num(5))。生成过程是遍历左子节点Num(3)- 生成PUSH 3遍历右子节点Num(5)- 生成PUSH 5访问根节点BinOp- 根据PLUS生成ADD最终指令序列为[(PUSH, 3), (PUSH, 5), (ADD,)]。这个序列的含义是先把3和5压入栈然后执行ADD它会弹出栈顶的两个元素5和3相加得到8再把8压回栈顶。3.5 步骤五组装与测试最后我们写一个主程序把所有这些组件串联起来。# main.py from lexer import Lexer from parser import Parser from codegen import CodeGenerator def main(): while True: try: text input(calc ) # 模拟一个简单的计算器提示符 except EOFError: break if not text: continue # 1. 词法分析 lexer Lexer(text) # 2. 语法分析 parser Parser(lexer) ast parser.parse() print(fAST: {ast}) # 3. 代码生成 codegen CodeGenerator() codegen.generate(ast) code codegen.get_code() print(fGenerated Code: {code}) # (可选) 4. 执行生成的代码 stack [] for instr in code: if instr[0] PUSH: stack.append(instr[1]) elif instr[0] ADD: b stack.pop() a stack.pop() stack.append(a b) elif instr[0] SUB: b stack.pop() a stack.pop() stack.append(a - b) elif instr[0] MUL: b stack.pop() a stack.pop() stack.append(a * b) elif instr[0] DIV: b stack.pop() a stack.pop() stack.append(a / b) if stack: print(fResult: {stack[-1]}) print() if __name__ __main__: main()运行这个程序输入3 5 * (10 - 4)你会看到类似以下的输出calc 3 5 * (10 - 4) AST: BinOp(Num(3), PLUS, BinOp(Num(5), MUL, BinOp(Num(10), MINUS, Num(4)))) Generated Code: [(PUSH, 3), (PUSH, 5), (PUSH, 10), (PUSH, 4), (SUB,), (MUL,), (ADD,)] Result: 33.0AST清晰地展示了运算结构生成的代码顺序也完全符合我们预期的运算顺序先计算括号内的10-4再计算5*6最后计算330。一个微型编译器就完成了4. 深入探讨与扩展方向我们的微型编译器虽然功能简单但已经包含了经典编译器前端的所有核心概念。在此基础上你可以进行多方面的扩展和深化使其更强大、更实用。4.1 增强词法分析器目前的词法分析器只能处理整数和几个运算符。可以轻松扩展浮点数在integer()方法基础上增加对小数点.的识别。变量标识符增加对字母开头的词法单元识别类型为ID用于支持变量如x,total。更多运算符如取模%、幂运算**、比较运算符,等。注释增加跳过单行//或多行/* */注释的逻辑。实现浮点数的关键点读取数字时需要区分整数部分和小数部分。一个简单的状态机是先读取整数部分如果遇到小数点则标记进入小数部分继续读取数字。最后将整数部分和小数部分组合成浮点数。要注意处理像.5或10.这样的边界情况。4.2 增强语法与语义支持赋值语句扩展文法加入assignment : ID expression。这需要在AST中新增Assign节点并在代码生成或解释执行时维护一个符号表来存储变量名和值的映射。支持语句序列实现一个compound_statement节点包含多个语句如多个赋值或表达式。这通常需要一个statements规则用分号或换行分隔。支持控制流这是更大的挑战。可以尝试实现if条件语句和while循环语句。这需要引入布尔表达式、跳转指令JUMP_IF_FALSE,JUMP和标签LABEL的概念到你的中间代码中。添加赋值语句的示例在词法分析器中增加对标识符的识别。在文法中添加规则statement : assignment | expression和assignment : ID expression。在AST中创建Assign节点包含变量名和表达式节点。在代码生成器中为Assign节点生成代码先生成表达式求值的代码结果留在栈顶然后生成一条STORE指令将栈顶值存入符号表对应的变量位置。在解释执行时需要维护一个字典作为符号表。4.3 错误处理与恢复目前的编译器在遇到错误如非法字符、语法不匹配时直接抛出异常并终止。一个健壮的编译器应该能报告友好的错误信息如错误位置、预期内容并尝试从某些错误中恢复继续解析后续代码以便一次性报告所有错误。基础错误恢复策略在语法分析器的error()方法中不要直接退出而是可以尝试同步恢复。例如在expression解析中遇到意外词法单元可以一直丢弃词法单元直到遇到一个“同步词法单元”如分号、右括号或一个语句的开始关键字然后尝试继续解析。同时需要收集所有错误信息最后一并输出。4.4 从解释到真实编译我们生成的是“中间代码”并由一个简单的栈虚拟机执行。你可以将此作为跳板生成更低级代码将栈式指令转换为三地址码如t1 5 * 2t2 3 t1这是一种更接近真实机器码的中间表示。生成汇编代码为你的中间代码设计一个到x86或ARM汇编的映射。例如PUSH对应push指令算术运算对应add,sub,imul等指令。你需要处理寄存器分配、栈帧管理等复杂问题这是一个完整的后端挑战。集成现有工具了解工业级编译器如何使用Lex/Yacc或Flex/Bison、ANTLR等工具。这些工具能根据你定义的词法规则和文法规则自动生成词法分析器和语法分析器代码极大地提高了开发效率。手动实现一遍后再学习这些工具你会对它们的原理和局限性有更深刻的理解。5. 常见问题与调试技巧实录在实现这个编译器的过程中你几乎一定会遇到下面这些问题。这里记录了我的踩坑实录和解决思路。5.1 问题一运算符优先级错误症状输入3 5 * 2结果输出13正确应为13但AST显示为(35)*2的结构导致解释或生成代码后得到错误结果16。根因这是初学者最容易犯的错误。在递归下降分析器中优先级是通过函数调用层次来体现的。如果文法设计不当比如只有一个expression函数来处理所有运算符并且没有区分优先级就会导致错误。正确的做法是让低优先级的运算符如加减调用高优先级运算符如乘除的函数。在我们的设计中expression处理加减调用term处理乘除term调用factor处理基本单元这就自然实现了优先级。检查清单你的文法是否明确区分了不同优先级的层次如expr - term (|-) termterm - factor (*|/) factor你的递归下降函数调用关系是否与文法一致expression()中是否调用了term()而不是直接调用factor()5.2 问题二左结合性错误症状输入10 - 5 - 2结果输出7正确应为3。AST可能显示为10 - (5 - 2)。根因文法或解析函数没有正确处理同一运算符的连续出现。对于左结合的运算符需要循环构造AST。看我们的expression函数node self.term() while self.current_token.type in (PLUS, MINUS): token self.current_token self.eat(token.type) node BinOp(leftnode, optoken, rightself.term()) return node关键在node BinOp(leftnode, optoken, rightself.term())。第一次循环node是第一个term比如10构造出(10 - 5)节点并赋给node。第二次循环node变成了(10-5)节点作为新的左子节点与下一个term2构造出((10-5)-2)节点。这就实现了左结合。解决方案确保在处理同级运算符的递归下降函数中使用while循环而非if判断并且在循环体内将当前结果节点作为新节点的左子节点。5.3 问题三括号无法改变优先级症状输入(3 5) * 2结果被计算为3 (5 * 2) 13而不是(35)*216。根因factor函数的实现有误。在解析到左括号时它必须递归调用能解析最低优先级表达式的函数通常是expression并且必须消费掉匹配的右括号。正确的factor函数逻辑def factor(self): token self.current_token if token.type INTEGER: self.eat(INTEGER) return Num(token) elif token.type LPAREN: self.eat(LPAREN) node self.expression() # 关键调用 expression 而非 term 或 factor self.eat(RPAREN) # 必须消费右括号 return node else: self.error()括号的力量就在于它让内部的内容作为一个独立的、完整的表达式被解析其优先级最高在factor层面。解析完括号内的内容后必须显式地消费eat右括号否则解析器状态会错乱。5.4 问题四代码生成顺序错误导致计算错误症状AST看起来正确但生成的指令执行后结果不对。例如对于3 - 5生成的指令可能是PUSH 5,PUSH 3,SUB执行后得到-25-3而非-23-5等等这里需要仔细想。对于栈计算机SUB指令通常是a - b其中a是次栈顶元素b是栈顶元素。所以指令PUSH 3; PUSH 5; SUB的结果是3 - 5 -2。如果你的指令顺序反了结果就会反。根因在BinOp节点的代码生成中遍历子节点的顺序必须是左子树 - 右子树。因为栈是后进先出最后生成的指令对应栈顶。我们要先让左操作数在栈底先入栈右操作数在栈顶后入栈这样执行二元运算指令时顺序才对。调试技巧打印AST首先确保AST绝对正确。可视化AST可以帮助你理解结构。单步跟踪代码生成在generate函数中打印当前正在处理的节点和已生成的指令。对照AST看遍历顺序是否符合后序左-右-根。手动模拟栈执行对于生成的简短指令序列用纸笔模拟栈的变化这是验证指令逻辑最直接的方法。5.5 进阶挑战如何处理一元负号问题描述如何让我们的编译器支持像-5或3 * -x这样的表达式解决方案这需要在文法中引入一元运算符。通常我们在factor规则中处理它。修改文法factor : (PLUS|MINUS) factor | INTEGER | LPAREN expression RPAREN。这里(PLUS|MINUS) factor表示一个正号或负号后面跟着一个因子。修改factor函数在函数开始时检查当前词法单元是否是PLUS或MINUS。如果是消费掉它然后获取后面的因子节点并构造一个一元运算符节点例如UnaryOp。AST和代码生成需要新增UnaryOpAST节点。在代码生成时对于一元负号生成计算因子的代码然后生成一条取负指令如NEG。这个过程很好地展示了如何通过扩展文法规则和递归下降函数来为语言添加新特性。手动实现这个功能会让你对语法分析有更牢固的掌握。构建这个微型编译器的旅程就像在显微镜下观察一个生命体。你亲手实现了将杂乱字符转化为有序指令的每一个环节。当你第一次看到自己写的程序正确解析并计算出一个复杂表达式时那种成就感是无与伦比的。这不仅仅是实现了一个计算器而是打通了对编程语言如何工作的“任督二脉”。下次当你再使用if、while或调用一个函数时你脑海里可能会不自觉地浮现出它被解析成AST再被翻译成指令的样子。这种深度的理解是阅读多少理论书籍都难以替代的。