1. 项目概述为什么我们要“手搓”一个编译器如果你是一名程序员每天敲着if、for、int这些关键字用着gcc或clang一键编译有没有那么一瞬间好奇过这行简单的文本代码究竟是怎么变成机器能执行的指令的编译器这个听起来高深莫测的“黑盒”其实是计算机科学皇冠上的明珠之一它连接了人类可读的高级语言和机器执行的底层指令。很多人觉得编译器是只有大神才能碰的领域但实际上它的核心思想非常直观甚至可以说自己动手实现一个简化版的编译器是理解编程语言本质、提升计算机系统认知的最佳路径之一。我最初接触编译原理时也被那些复杂的理论公式和龙书吓退过。直到后来我决定抛开大部头从一个最简单的“玩具语言”开始亲手实现它的词法分析、语法分析和代码生成。这个过程让我恍然大悟编译器不过是一个遵循固定规则、按部就班处理文本的程序。它没有魔法有的只是清晰的逻辑和严谨的步骤。这个项目就是带你一起从零开始构建一个能处理简单算术表达式比如1 2 * (3 - 4)并生成等价低级代码比如栈式虚拟机指令的微型编译器。我们不会涉及复杂的类型系统或优化目标是打通从源代码到目标代码的完整链路让你获得“哦原来编译器就是这么回事”的顿悟感。2. 编译器整体架构与核心流程拆解在动手写代码之前我们必须像建筑师一样先画出蓝图。一个典型的编译器无论大小其核心流程都可以抽象为一条清晰的流水线。我们的微型编译器将严格遵循这个经典的三阶段模型但会做最大程度的简化。2.1 核心三阶段源程序到目标代码的旅程想象一下你要把一篇中文文章翻译成英文。你不会拿起整篇文章就开始逐词替换那样会一团糟。正确的做法是先通读文章识别出一个个独立的词语词法分析然后分析句子的结构哪个是主语哪个是谓语它们之间是什么关系语法分析最后根据英文的语法规则把分析好的句子结构重新组织成地道的英文句子代码生成。编译器的工作流程与此惊人地相似。词法分析这是编译器的“眼睛”。它的任务是把源代码这个长长的字符串切割成一个个有意义的“单词”在编译原理中称为“词法单元”或“Token”。例如对于字符串“position initial rate * 60”词法分析器会识别出标识符position赋值符号标识符initial加号标识符rate乘号*数字60。它会忽略空格、换行这些无关紧要的空白字符。这一步的关键是定义好什么算一个“单词”以及每种“单词”的类型。语法分析这是编译器的“大脑”。它接收词法分析器产出的一串Token然后检查这串Token是否符合我们预先定义好的语法规则。这些规则定义了语言的结构比如“一个赋值语句应该是一个标识符后面跟着等号再后面跟着一个表达式”。语法分析器会构建出一棵“语法树”这棵树清晰地展示了代码的层次结构。例如对于表达式1 2 * 3正确的语法树应该把2 * 3作为一个整体再与1相加这反映了乘法的优先级高于加法。这一步的核心是定义语法规则通常用上下文无关文法和实现一个能根据规则构建树的解析器。代码生成这是编译器的“手”。它遍历语法分析器生成的语法树根据树的节点类型和结构生成等价的目标代码。我们的目标不是真实的x86或ARM汇编那样太复杂。为了保持项目的纯粹性和可理解性我们将生成一种“栈式虚拟机”的指令。这种虚拟机模拟一个操作数栈指令如PUSH 1将数字1压入栈、ADD弹出栈顶两个元素相加后结果压回栈顶等。生成这样的指令序列已经完整地体现了从高级结构到低级操作转换的核心思想。注意完整的工业级编译器在语法分析和代码生成之间通常还会有“语义分析”检查类型是否匹配等和“中间代码生成与优化”等阶段。但对于我们的教学性项目将语义检查的简单逻辑融入语法分析或代码生成阶段并跳过优化是保持项目简洁、主线清晰的关键策略。2.2 技术选型为什么用Python你可能会问C语言不是更贴近系统吗Java不是更严谨吗对于这个项目我强烈推荐使用Python。原因如下快速原型Python语法简洁能让我们把精力集中在算法和逻辑本身而不是内存管理、指针等底层细节上。我们可以用列表轻松模拟栈用字典实现符号表用递归下降法优雅地实现语法分析。表达力强Python的字符串处理、数据结构操作非常方便非常适合实现词法分析中的正则匹配和语法分析中的树形结构构建。零环境负担几乎任何系统都自带或可轻松安装Python避免了复杂的编译工具链配置让我们能专注于编译器本身。当然用C、Go、JavaScript等语言实现也完全可行原理是相通的。选择Python是为了最大限度地降低实现门槛让“构建编译器”这个目标变得触手可及。3. 第一阶段实战实现词法分析器词法分析器也叫扫描器是编译器流水线的第一个环节。它的输入是字符串输出是Token流。我们首先需要定义我们的“微型语言”有哪些词汇。3.1 定义Token类型我们的语言目前只支持整数、基本的算术运算符和括号。因此我们可以定义如下Token类型INTEGER: 整数如1,42,100。PLUS: 加号。MINUS: 减号-。MUL: 乘号*。DIV: 除号/。LPAREN: 左括号(。RPAREN: 右括号)。EOF: 表示文件结束这是一个特殊的Token用于告知语法分析器输入已耗尽。我们可以用一个简单的类或命名元组来表示一个Token它至少包含两个信息类型type和值value。对于运算符其值就是符号本身如‘’对于整数其值就是转换后的整型数字如42。3.2 构建Lexer类我们将创建一个Lexer类它内部维护着输入字符串和当前字符的索引位置。class Token: def __init__(self, type, value): self.type type self.value value def __repr__(self): return f‘Token({self.type}, {repr(self.value)})’ 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): 移动pos指针获取下一个字符。 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): 词法分析器的核心方法获取下一个Token。 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)实操心得在integer方法中我们通过循环拼接字符数字最后一次性转换成int。这里有个细节如果数字非常大超出了Python整型的范围怎么办在真正的编译器中词法分析器通常只负责识别数字的字面形式字符串将其作为“数字字面值”Token的值传递下去具体的数值转换和范围检查可能留到后续的语义分析阶段。我们的简化实现直接转换对于教学目的足够了。4. 第二阶段实战实现语法分析器语法分析器也叫解析器它接收Token流验证其结构是否符合语法并生成一颗抽象语法树。我们将采用“递归下降”的方法来实现这是最直观、最适合手写解析器的方法。4.1 定义语法规则与AST节点首先我们需要用“产生式”来定义我们表达式的语法。我们采用经典的运算符优先级处理方式加减法优先级最低且左结合。乘除法优先级较高且左结合。括号优先级最高可以改变默认优先级。用产生式可以这样描述expr是表达式的起始符号expr : term ((PLUS | MINUS) term)* term : factor ((MUL | DIV) factor)* factor : INTEGER | LPAREN expr RPAREN解释一下一个表达式expr由一个term开始后面可以跟零个或多个加减号 term的组合。一个term由一个factor开始后面可以跟零个或多个乘除号 factor的组合。一个factor可以是一个整数或者一个括号括起来的完整表达式。接下来定义AST节点。我们至少需要两种节点二元运算符节点BinOp和数字节点Num。class AST: pass class BinOp(AST): def __init__(self, left, op, right): self.left left self.op op # 一个Token对象如Token(‘PLUS’, ‘’) self.right right class Num(AST): def __init__(self, token): self.token token self.value token.value4.2 实现递归下降解析器我们创建一个Parser类它内部持有Lexer实例并有一个current_token属性指向当前正在处理的Token。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): “消耗”当前Token如果类型匹配则获取下一个Token。 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.expr() # 递归解析括号内的表达式 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 expr(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): 解析的入口点。 return self.expr()核心逻辑解读递归下降的精髓在于每个语法规则expr,term,factor对应一个函数。函数内部按照产生式的右部进行解析。factor函数处理最基本的单元数字或括号term函数处理乘除法它会先调用factor获取左操作数然后循环处理连续的乘除号expr函数处理加减法它会先调用term获取左操作数然后循环处理连续的加减号。这种结构天然地处理了运算符的优先级和结合性。注意事项eat方法是解析器的“驱动器”。它严格检查当前Token的类型是否符合预期符合则“吃掉”它并前进不符合则报语法错误。这是保证语法正确性的关键。递归下降法非常直观但当语法存在左递归时如A - A a会导致无限递归需要先对文法进行改造。我们的文法通过expr: term ((PLUS|MINUS) term)*这种形式避免了左递归。5. 第三阶段实战实现代码生成器现在我们有一颗结构清晰的AST。代码生成器的任务就是遍历这棵树为每个节点生成相应的指令。我们设计一个简单的栈式虚拟机它的指令集包括PUSH n: 将整数n压入栈顶。ADD,SUB,MUL,DIV: 弹出栈顶两个元素执行相应运算将结果压回栈顶。5.1 设计栈式虚拟机指令我们可以用一个列表来代表指令序列每条指令本身可以用一个元组表示例如(‘PUSH’, 5)或(‘ADD’,)。5.2 实现AST解释器/代码生成器我们将创建一个Interpreter类它通过一个后序遍历AST的方式来生成指令。后序遍历意味着先处理子节点再处理父节点这正好符合栈式运算的顺序先计算操作数压入栈再执行操作。class Interpreter: def __init__(self, parser): self.parser parser self.instructions [] # 存储生成的指令 def visit(self, node): 访问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(f‘No visit_{type(node).__name__} method’) def visit_Num(self, node): # 对于数字节点生成PUSH指令 self.instructions.append((‘PUSH’, node.value)) def visit_BinOp(self, node): # 对于二元操作节点先访问左子树再访问右子树最后生成操作指令 self.visit(node.left) self.visit(node.right) op_type node.op.type if op_type ‘PLUS’: self.instructions.append((‘ADD’,)) elif op_type ‘MINUS’: self.instructions.append((‘SUB’,)) elif op_type ‘MUL’: self.instructions.append((‘MUL’,)) elif op_type ‘DIV’: self.instructions.append((‘DIV’,)) else: raise Exception(‘Unsupported operator’) def generate_code(self): 代码生成的入口点。 ast self.parser.parse() self.visit(ast) return self.instructions代码生成逻辑visit_Num方法很简单遇到一个数字5就生成(‘PUSH’, 5)。visit_BinOp方法是关键对于表达式左 op 右它先递归生成左子树的指令这会导致左操作数的值被计算并压入栈再递归生成右子树的指令右操作数入栈此时栈顶两个元素就是左右操作数最后生成一条对应的运算指令如ADD该指令会弹出这两个数计算后将结果压栈。这个过程完美地利用了栈的“后进先出”特性。5.3 实现一个简单的虚拟机执行器生成了指令序列我们还需要一个执行器来运行它验证结果。class StackVM: def __init__(self): self.stack [] def run(self, instructions): for instr in instructions: op instr[0] if op ‘PUSH’: self.stack.append(instr[1]) elif op ‘ADD’: b self.stack.pop() a self.stack.pop() self.stack.append(a b) elif op ‘SUB’: 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) elif op ‘DIV’: b self.stack.pop() a self.stack.pop() self.stack.append(a // b) # 整数除法 else: raise Exception(‘Unknown instruction’) if len(self.stack) 1: return self.stack[0] else: raise Exception(‘Execution error’)6. 集成测试与问题排查现在让我们把所有的部件组装起来形成一个完整的编译-执行流程。def main(): while True: try: text input(‘calc ‘) except EOFError: break if not text: continue lexer Lexer(text) parser Parser(lexer) interpreter Interpreter(parser) code interpreter.generate_code() print(‘Generated Code:’, code) vm StackVM() result vm.run(code) print(‘Result:’, result) if __name__ ‘__main__’: main()运行这个程序输入3 5 * (10 - 4) / 2你会看到类似以下的输出calc 3 5 * (10 - 4) / 2 Generated Code: [(‘PUSH’, 3), (‘PUSH’, 5), (‘PUSH’, 10), (‘PUSH’, 4), (‘SUB’,), (‘MUL’,), (‘PUSH’, 2), (‘DIV’,), (‘ADD’,)] Result: 18生成的指令序列清晰地反映了运算顺序先计算10-4然后5*6然后30/2最后315。结果是正确的18。6.1 常见问题与调试技巧在实现过程中你几乎一定会遇到各种问题。下面是一些典型的坑和排查思路词法分析器无法识别多位数症状是输入12被识别为两个独立的INTEGER: 1和INTEGER: 2。检查integer()方法中的循环条件确保它在遇到非数字字符时才停止。一个常见的错误是advance()调用时机不对导致指针移动过头或不足。语法分析器报告“Invalid syntax”这是最常见的错误。首先在error()方法中打印出当前current_token的信息和位置这能帮你快速定位到源代码中出错的地方。其次仔细核对你的语法规则产生式和递归下降函数是否一一对应。例如expr函数里是否正确地调用了termterm的循环条件是否正确运算符优先级错误症状是1 2 * 3被计算成9而不是7。这几乎肯定是语法规则定义错误。确保你的文法层级是expr - term - factor并且乘除法的解析term在加减法expr的内部被调用。递归下降解析时函数调用链expr() - term() - factor()的嵌套关系决定了优先级。括号不起作用症状是(12)*3被计算成12*37。检查factor()函数当遇到LPAREN时是否正确地递归调用了expr()来解析括号内的整个表达式并在之后“吃掉”了RPAREN。一个常见的错误是递归调用后忘记消耗右括号。代码生成顺序错误导致计算结果不对对比你生成的指令序列和手动推导的序列。对于表达式a - b你的指令顺序应该是PUSH a,PUSH b,SUB。如果顺序反了变成PUSH b,PUSH a,SUB结果就是b - a。在visit_BinOp中务必保证self.visit(node.left)在self.visit(node.right)之前。调试建议在开发每个阶段Lexer, Parser, Interpreter时都编写独立的单元测试。例如给Lexer输入“2 3”手动检查它输出的Token流是否为[INT:2, PLUS:, INT:3, EOF]。给Parser输入这个Token流检查生成的AST结构是否正确。这种分阶段验证能极大降低整体调试的复杂度。7. 项目扩展与深入思考完成这个基础版本后你已经掌握了编译器的核心骨架。但这个玩具编译器距离实用还差得很远。以下是一些可以尝试的扩展方向每一个都能让你对编译技术的理解更深一层添加变量赋值与读取这需要引入“符号表”的概念。在词法分析阶段需要增加ID标识符类型的Token。在语法分析阶段需要增加赋值语句如x 1 2和表达式中的变量引用。在代码生成阶段需要维护一个变量名到内存地址或栈位置的映射。生成PUSH指令时如果是变量就需要生成LOAD [地址]这样的指令遇到赋值则需要生成STORE [地址]指令。支持更复杂的数据类型从整数扩展到浮点数、布尔值、字符串。这涉及到词法分析器如何区分不同的字面量例如3.14是FLOAT“hello”是STRING以及语法和代码生成阶段如何处理不同类型的运算整数加法和浮点数加法是不同的机器指令。实现控制流语句如if-else和while循环。这会给代码生成带来质的变化因为需要生成“跳转”指令。你需要引入标签Label的概念。例如对于if (cond) { A } else { B }生成的代码逻辑是计算条件cond的代码 - 条件跳转指令如果为假则跳到else标签- 语句块A的代码 - 无条件跳转指令跳到if语句结束后的标签- else标签 - 语句块B的代码 - 结束标签。生成真正的汇编代码将我们的栈式虚拟机指令替换为x86或RISC-V等真实架构的汇编代码。你需要学习目标平台的基本指令集如数据移动、算术运算、跳转、调用约定和汇编器语法。这会将你对“代码生成”的理解从抽象虚拟机拉到具体的硬件层面。实现一个简单的优化例如常量折叠。在语法分析或代码生成阶段如果发现表达式3 5可以直接计算出8并生成PUSH 8而不是PUSH 3, PUSH 5, ADD。再比如消除公共子表达式。这些优化能让你初步窥见工业级编译器复杂而精妙的设计。亲手实现一遍哪怕是最简单的版本你对编程语言的理解也会完全不同。下次当你再使用if、while或者调用一个函数时你脑海里可能会不自觉地浮现出它背后可能的AST结构和生成的低级指令。这种从上层应用到底层系统的贯通感正是这个项目带来的最大收获。编译器不是魔法它是一套精妙、系统且可以被理解和构建的工程艺术。从这个简单的起点出发你已经拿到了进入这扇大门的钥匙。
