1. 项目概述为什么我们要“手搓”一个编译器“编译器”这个词听起来总是带着一层神秘的面纱仿佛是高阶程序员的专属领域。每当看到GCC、Clang这些庞然大物或者听到LLVM、IR这些术语很多开发者都会下意识地觉得这玩意儿太底层、太复杂不是自己能碰的。但事实真的如此吗一个能处理int main() { return 123; }这样简单程序的微型编译器其核心骨架远比想象中清晰和迷你。这个项目的目标就是亲手揭开这层神秘的面纱从最原始的字节流开始一步步构建出一个能真正生成可执行代码的编译器前端。它不追求功能完备而是要让你透彻理解编译器工作的三个核心阶段词法分析Lexical Analysis、语法分析Syntax Analysis和代码生成Code Generation。你可能会问在拥有无数成熟编译工具的今天为什么还要从零开始造轮子这恰恰是关键所在。通过亲手实现你将不再把编译器看作一个黑盒。当你的程序出现语法错误时你能在脑海中清晰地映射出是词法分析器没能识别某个标识符还是语法分析器在解析表达式时遇到了意外的结构。当你学习一门新语言的特性时你会本能地去思考它的语法该如何定义它的语义该如何检查。这种从“使用者”到“创造者”视角的转变是阅读任何理论书籍或使用现成工具都无法替代的深刻理解。无论是为了深入理解编程语言原理还是为未来的领域特定语言DSL或代码转换工具打下基础这个“手搓”编译器的过程都是一次绝佳的思维训练。2. 核心思路与架构设计三阶段流水线一个典型的编译器尤其是教学用的简化编译器通常采用一种清晰的“流水线”架构。这种架构将复杂的翻译过程分解为多个职责单一的阶段每个阶段接收上一阶段的输出并产生下一阶段所需的输入。对于我们这个微型编译器我们采用最经典的三阶段模型。2.1 阶段划分与数据流整个编译过程就像一条工厂流水线源代码是原材料最终的可执行代码是成品。流水线由三个主要工站构成词法分析器Lexer这是第一道工序。它的任务非常“机械”读取源代码的原始字符流字节流忽略其中的空白、换行等无关紧要的“噪音”然后将字符组合成一个个有意义的“单词”在编译原理中称为词法单元Token。例如对于字符串“int main() { return 123; }”Lexer 会识别出int关键字、main标识符、(、)、{、return关键字、123整数常量、;、}。它的输出是一个 Token 序列或者叫 Token 流。语法分析器Parser这是第二道工序也是编译器“理解”程序结构的关键。它接收 Lexer 产生的 Token 流并根据预先定义好的语法规则Grammar检查这个 Token 序列是否构成一个合法的程序。如果合法Parser 会构建出一棵抽象语法树Abstract Syntax Tree, AST。这棵树以一种层次化的、去除了冗余细节如分号、括号等的结构精确地描述了程序的语法构成。例如它会知道123是return语句的返回值表达式而不是一个独立的语句。代码生成器Code Generator这是最后一道工序。它遍历 Parser 生成的 AST根据每个节点的语义生成等价的目标代码Target Code。在我们的例子中目标代码是 RISC-V 汇编语言。代码生成器需要了解目标平台的约定比如在 RISC-V 中函数的返回值通常存放在a0寄存器中ret指令用于从函数返回。这三个阶段之间的数据流非常明确源代码文本 - Lexer - Token流 - Parser - AST - CodeGen - 目标代码汇编。这种清晰的接口使得每个阶段可以独立开发、测试和优化。2.2 技术选型与工具考量对于这样一个教学项目技术选型的核心原则是简单、直观、易于理解避免被复杂的工业级工具分散注意力。实现语言我们选择Python。原因很简单Python 语法简洁表达力强能让我们专注于算法逻辑而非语言细节。它的字符串处理、数据结构列表、字典和面向对象特性非常适合快速实现 Lexer、Parser 和 AST 遍历。当然你用 C、Java 甚至 JavaScript 来实现也完全可行逻辑是相通的。词法/语法分析工具在工业界我们会使用 Lex/Flex词法分析器生成器和 Yacc/Bison语法分析器生成器或更现代的 ANTLR。但在这个“从零开始”的项目中我们决定手写一个简单的、确定有限自动机DFA驱动的 Lexer 和一个递归下降Recursive Descent的 Parser。这样做虽然功能有限但能让你彻底理解自动机如何识别单词以及递归函数如何对应语法规则进行推导这是理解编译原理基石的关键。目标平台我们选择RISC-V 汇编。RISC-V 指令集架构设计精简、规整非常适合教学。相比于复杂的 x86 汇编RISC-V 的指令更容易理解。我们只需要用到其中极少的几条指令如li,ret即可完成目标。生成汇编后我们可以使用 RISC-V 的工具链如gcc、as、qemu进行汇编、链接和运行验证。AST 的遍历我们将采用访问者模式Visitor Pattern。这是一种在编译器中非常流行的设计模式。它允许我们在不修改 AST 节点类结构的前提下定义新的操作比如生成代码、进行类型检查。简单来说我们为每种 AST 节点定义一个accept方法然后创建不同的“访问者”类如CodeGenVisitor来访问这些节点并执行相应操作。这比在 AST 节点类中直接嵌入代码生成逻辑要清晰和灵活得多。注意这个选择是教学导向的。真实的编译器在词法语法分析阶段几乎无一例外地使用生成器并且拥有复杂的中间表示IR和优化管道。但请记住所有复杂的工具都是为了自动化或优化我们即将要手动完成的这些核心步骤。3. 第一阶段词法分析器Lexer的构建词法分析是编译器的“眼睛”。它的任务是把杂乱无章的字符序列转换成有分类、有意义的单词序列。我们首先需要定义我们的“单词”有哪些种类。3.1 Token 的定义与分类在我们的迷你语言姑且叫它 MiniDecaf的第一步只需要支持非常少的 Token 种类。我们用一个 Python 类或字典来定义它们。# 定义 Token 的类型用枚举或字符串常量表示 class TokenType: KEYWORD KEYWORD # 如 int, return IDENTIFIER IDENTIFIER # 如 main INTEGER INTEGER # 如 123 LPAREN LPAREN # ( RPAREN RPAREN # ) LBRACE LBRACE # { RBRACE RBRACE # } SEMICOLON SEMICOLON # ; # 第一步我们暂时忽略空白符或者定义一个 SKIP 类型每个 Token 不仅要知道它的类型还要知道它对应的原始字符串lexeme以及在源代码中的位置行号、列号用于错误报告。因此我们定义一个Token类class Token: def __init__(self, type_: TokenType, lexeme: str, line: int, column: int): self.type type_ self.lexeme lexeme # 实际的字符串如 ‘int’ ‘123’ self.line line self.column column def __repr__(self): return fToken({self.type}, {self.lexeme}, line{self.line}, col{self.column})3.2 手写 DFA 实现 Lexer 核心逻辑Lexer 的核心是一个状态机。它逐个读取字符根据当前字符和状态决定下一步动作是继续累积字符构成一个单词还是结束当前单词并开始识别下一个。我们以识别整数和关键字为例勾勒一个简化的 DFA 逻辑初始状态读取一个字符。如果是数字‘0’-‘9’进入“识别整数”状态。继续读字符只要还是数字就累积。直到遇到非数字字符如空格、分号则生成一个INTEGERToken并回退一个字符让下一个 Token 从它开始识别。如果是字母‘a’-‘z’ ‘A’-‘Z’进入“识别标识符或关键字”状态。继续读字母或数字累积字符串。完成后检查累积的字符串是否是预定义的关键字如‘int’,‘return’。如果是生成KEYWORDToken否则生成IDENTIFIERToken。如果是特定符号如 ‘(‘, ‘)’, ‘{‘, ‘}’, ‘;’直接生成对应的单字符 Token。如果是空白符空格、制表符、换行直接跳过更新行号列号回到初始状态。下面是一个极度简化的 Lexer 核心循环伪代码class Lexer: def __init__(self, source: str): self.source source self.pos 0 # 当前读取位置 self.line 1 self.column 1 self.tokens [] def lex(self) - List[Token]: while self.pos len(self.source): ch self.source[self.pos] if ch.isdigit(): # 处理整数 start_pos self.pos while self.pos len(self.source) and self.source[self.pos].isdigit(): self.pos 1 num_str self.source[start_pos:self.pos] self.tokens.append(Token(TokenType.INTEGER, num_str, self.line, start_pos)) continue # 继续循环pos 已经在数字末尾 elif ch.isalpha(): # 处理标识符或关键字 start_pos self.pos while self.pos len(self.source) and (self.source[self.pos].isalnum() or self.source[self.pos] _): self.pos 1 word self.source[start_pos:self.pos] # 判断是否为关键字 if word in [int, return]: token_type TokenType.KEYWORD else: token_type TokenType.IDENTIFIER self.tokens.append(Token(token_type, word, self.line, start_pos)) continue elif ch (: self.tokens.append(Token(TokenType.LPAREN, ch, self.line, self.column)) elif ch ): # ... 类似处理其他符号 elif ch in [ , \t]: # 跳过空白只更新列号 pass elif ch \n: # 换行更新行号和列号 self.line 1 self.column 1 else: raise LexerError(fUnexpected character {ch} at line {self.line}, column {self.column}) # 对于大多数情况处理完当前字符后位置前进一位 self.pos 1 self.column 1 return self.tokens实操心得“回退”技巧在识别完一个整数或标识符后我们读取了第一个不属于它的字符比如分号。此时self.pos指向了这个字符。为了让下一个识别周期能正确处理这个字符我们使用了continue跳过了循环末尾的self.pos 1。另一种常见做法是主动将self.pos减 1效果相同。错误处理遇到无法识别的字符比如、$Lexer 应该立即报错并指出位置而不是静默忽略或产生混乱的 Token。这能帮助用户快速定位源代码中的拼写错误。关键字与标识符的区分关键字的识别是在标识符识别之后进行的。先按标识符规则收集字母数字串然后查表判断是否为关键字。这比在 DFA 中为每个关键字设计独立路径要简单得多。3.3 测试与验证编写一个简单的测试确保你的 Lexer 能正确工作source_code int main() { return 123; } lexer Lexer(source_code) tokens lexer.lex() for token in tokens: print(token)期望的输出应该类似于Token(KEYWORD, int, line1, col1) Token(IDENTIFIER, main, line1, col5) Token(LPAREN, (, line1, col9) Token(RPAREN, ), line1, col10) Token(LBRACE, {, line1, col12) Token(KEYWORD, return, line1, col14) Token(INTEGER, 123, line1, col21) Token(SEMICOLON, ;, line1, col24) Token(RBRACE, }, line1, col26)注意这里列号是示意实际计算需要考虑跳过空白符。看到这个清晰的 Token 流你就成功迈出了第一步。4. 第二阶段语法分析器Parser与抽象语法树AST拿到 Token 流后编译器需要理解它的结构。这就是语法分析器的任务验证结构是否符合语法并构建出抽象语法树。4.1 定义迷你语言的语法规则首先我们需要用形式化的方式定义我们语言的语法。我们使用上下文无关文法CFG来描述。对于第一步我们的语法非常简单program : function function : type identifier ( ) { statement } type : int statement : return expression ; expression : integer解释一下program是起始符号一个程序就是一个function。function由返回type、函数名identifier、一对圆括号、一对花括号和其中的statement组成。type目前只有‘int’一种。statement目前只有return语句后面跟着一个expression和分号。expression目前只有一个整数常量integer。这里的‘int’,‘return’,‘(‘等用引号括起来的是终结符对应 Lexer 产生的 Token。program,function等是非终结符它们由终结符和其他非终结符组合而成。4.2 实现递归下降语法分析器递归下降是一种直观的解析方法。我们为每个非终结符编写一个解析函数。这个函数会“消耗”掉匹配其规则的 Token并返回对应的 AST 节点。首先设计我们的 AST 节点类。AST 应该反映程序的逻辑结构而不是语法细节比如括号、分号。# AST 节点基类 class ASTNode: pass class Program(ASTNode): def __init__(self, function): self.function function class Function(ASTNode): def __init__(self, name, body): self.name name # 字符串 ‘main’ self.body body # 一个 Statement 节点 class ReturnStmt(ASTNode): def __init__(self, value): self.value value # 一个 Expression 节点 class IntegerLiteral(ASTNode): def __init__(self, value): self.value value # 整数值如 123现在实现 Parser。Parser 需要持有 Token 流和一个当前位置索引。class Parser: def __init__(self, tokens): self.tokens tokens self.pos 0 self.current_token self.tokens[self.pos] if tokens else None def eat(self, token_type): 消费当前 Token如果类型匹配则前进到下一个 Token if self.current_token and self.current_token.type token_type: old_token self.current_token self.pos 1 if self.pos len(self.tokens): self.current_token self.tokens[self.pos] else: self.current_token None return old_token else: # 报错期望的 Token 类型与实际不符 expected token_type actual self.current_token.type if self.current_token else EOF raise ParserError(fExpected {expected}, got {actual} at line {self.current_token.line}) def parse_program(self): program : function func self.parse_function() return Program(func) def parse_function(self): function : type identifier ( ) { statement } # 1. 解析类型 ‘int’ self.eat(TokenType.KEYWORD) # 消耗 ‘int’ # 2. 解析函数名 id_token self.eat(TokenType.IDENTIFIER) # 消耗 ‘main’并获取其字符串 func_name id_token.lexeme # 3. 解析 ‘(‘ ‘)’ self.eat(TokenType.LPAREN) self.eat(TokenType.RPAREN) # 4. 解析 ‘{‘ self.eat(TokenType.LBRACE) # 5. 解析语句 stmt self.parse_statement() # 6. 解析 ‘}’ self.eat(TokenType.RBRACE) return Function(func_name, stmt) def parse_statement(self): statement : return expression ; self.eat(TokenType.KEYWORD) # 消耗 ‘return’ expr self.parse_expression() # 解析表达式 self.eat(TokenType.SEMICOLON) # 消耗 ‘;’ return ReturnStmt(expr) def parse_expression(self): expression : integer int_token self.eat(TokenType.INTEGER) # 消耗整数 Token # 将字符串转换为整数这里可以加入范围检查语义检查 int_value int(int_token.lexeme) return IntegerLiteral(int_value) def parse(self): 入口函数 ast self.parse_program() # 解析完成后应该消耗完所有 Token if self.current_token is not None: raise ParserError(fUnexpected token {self.current_token} at end of parsing) return ast关键点解析eat方法这是递归下降解析器的核心驱动。它检查当前 Token 是否符合预期如果符合就“吃掉”它并前进如果不符合就抛出语法错误。这强制了语法规则必须被严格遵循。函数对应规则每个parse_xxx函数严格对应文法中的一个非终结符产生式。函数体中的调用顺序对应产生式右侧符号的顺序。错误恢复我们这个简单的 Parser 没有错误恢复能力遇到第一个错误就停止。更复杂的解析器会尝试跳过一些 Token 并继续解析以报告更多错误。前瞻Lookahead我们的文法非常简单只需要看当前一个 Token (self.current_token) 就能决定如何解析。这称为 LL(1) 文法。更复杂的文法可能需要前瞻多个 Token。4.3 构建与验证 AST运行 Parser并打印 AST 的结构tokens [...] # 从 Lexer 得到的 Token 列表 parser Parser(tokens) ast parser.parse() # 可以写一个简单的打印函数来可视化 AST def print_ast(node, indent0): prefix * indent print(f{prefix}{node.__class__.__name__}, end) if isinstance(node, IntegerLiteral): print(f({node.value})) elif isinstance(node, ReturnStmt): print() print_ast(node.value, indent1) elif isinstance(node, Function): print(f(name{node.name})) print_ast(node.body, indent1) elif isinstance(node, Program): print() print_ast(node.function, indent1) print_ast(ast)输出应该类似于Program Function(namemain) ReturnStmt IntegerLiteral(123)这棵树清晰地告诉我们这是一个程序包含一个名为main的函数函数体是一条返回语句返回整数值123。所有语法细节括号、分号、关键字都被抽象掉了只留下了逻辑结构。5. 第三阶段代码生成器与访问者模式现在我们有了内存中的 AST最后一步就是将它翻译成目标机器能执行的代码——RISC-V 汇编。5.1 理解目标平台RISC-V 汇编基础我们不需要成为汇编专家只需要了解极少的几条指令和约定li a0, imm将立即数imm加载到寄存器a0中。a0是 RISC-V 的通用寄存器之一按照调用约定它用于传递函数的第一个参数和存放整数返回值。ret从当前函数返回。它等价于jalr x0, ra, 0即跳转到返回地址ra寄存器指向的位置。.text汇编器指令表示后续的代码是程序代码段。.globl main声明main标签是一个全局符号这样链接器才能从外部找到它。所以对于int main() { return 123; }我们期望生成的汇编代码是.text .globl main main: li a0, 123 ret5.2 实现访问者模式进行代码生成为什么用访问者模式想象一下如果我们在每个 AST 节点类里都加一个generate_code()方法那么每增加一种新的操作比如类型检查、代码优化就需要修改所有节点类。访问者模式将“操作”与“数据结构”分离。我们定义一个新的“访问者”类来承载“生成代码”这个操作。首先修改 AST 节点基类增加一个接受访问者的方法。class ASTNode: def accept(self, visitor): # 这是一个双分派double dispatch的技巧 # 具体调用哪个 visit 方法由 visitor 和 node 的实际类型共同决定 method_name visit_ self.__class__.__name__ visitor_method getattr(visitor, method_name, visitor.generic_visit) return visitor_method(self) # 其他节点类保持不变但不需要再包含生成代码的逻辑。然后实现代码生成访问者CodeGenVisitorclass CodeGenVisitor: def __init__(self): self.code [] # 用于累积生成的汇编代码行 def generic_visit(self, node): raise Exception(fNo visit method for {node.__class__.__name__}) def visit_Program(self, node): # 生成程序头 self.code.append( .text) self.code.append( .globl main) # 访问函数节点 node.function.accept(self) return \n.join(self.code) def visit_Function(self, node): # 生成函数标签 self.code.append(f{node.name}:) # 访问函数体语句 node.body.accept(self) def visit_ReturnStmt(self, node): # 访问返回值表达式期望它生成将值加载到 a0 的代码 node.value.accept(self) # 生成返回指令 self.code.append( ret) def visit_IntegerLiteral(self, node): # 生成加载立即数到 a0 寄存器的指令 self.code.append(f li a0, {node.value})工作流程我们从根节点Program开始访问。Program的accept方法会调用visitor.visit_Program(self)。在visit_Program中我们生成汇编头然后让function节点接受访问。function节点接受访问时调用visitor.visit_Function生成函数标签再让body一个ReturnStmt接受访问。以此类推最终IntegerLiteral的访问会生成li a0, 123。整个过程就像一次深度优先遍历。5.3 集成与最终输出最后将三个阶段串联起来并加入简单的语义检查例如检查函数名是否为main整数是否在 32 位有符号范围内。def compile(source_code): # 1. 词法分析 lexer Lexer(source_code) tokens lexer.lex() print(Tokens:, tokens) # 2. 语法分析 parser Parser(tokens) ast parser.parse() print(\nAST Structure:) print_ast(ast) # 3. 简单的语义检查集成在遍历中或单独进行 # 例如在 visit_Function 中检查 node.name main # 在 visit_IntegerLiteral 中检查 node.value 的范围 # 4. 代码生成 visitor CodeGenVisitor() assembly_code ast.accept(visitor) # Program 节点接受访问 return assembly_code # 测试 source int main() { return 123; } asm compile(source) print(\nGenerated Assembly:) print(asm)运行这段代码你将得到最终的 RISC-V 汇编输出。你可以将这个汇编代码保存到.s文件使用 RISC-V 的工具链如riscv64-unknown-elf-gcc -static your_code.s -o output进行汇编和链接然后在 RISC-V 模拟器如qemu-riscv64中运行验证它是否正确返回123。6. 常见问题、调试技巧与扩展思考在“手搓”编译器的过程中你一定会遇到各种问题。下面是一些常见坑点和解决思路。6.1 词法分析阶段问题标识符识别错误把关键字也识别成了标识符。排查检查你的关键字判断逻辑。必须在完整读出一个由字母/数字组成的单词后再查表判断它是否是关键字。顺序不能错。问题整数识别时遇到123abc这样的输入Lexer 把整个串识别成了一个整数或标识符。排查这是词法错误。你的 DFA 规则需要明确数字序列后紧跟字母是不合法的。在识别数字的状态如果下一个字符是字母应该报错“无效的数字格式”而不是继续累积。问题忘记处理多行代码和注释。解决在初始状态增加对\n的处理以更新行号。对于注释如//或/* */你需要增加对应的状态来跳过这些字符直到注释结束。6.2 语法分析阶段问题Parser 报告语法错误但你觉得代码没错。排查首先打印出 Lexer 产生的 Token 流确认 Token 序列和你想象的一致。很多时候是 Lexer 漏掉了某个 Token 或者产生了错误的 Token 类型。其次在 Parser 的每个eat调用前打印当前 Token看解析流程在哪里偏离了预期。问题如何处理运算符优先级和结合性例如1 2 * 3解决我们当前的简单文法无法处理。需要引入更复杂的表达式文法并使用递归下降中的优先级爬升Pratt Parsing或为表达式专门设计子解析函数如parse_additive_expression,parse_multiplicative_expression来体现优先级。这是语法分析中的一个重要话题。问题错误恢复能力差一个错误导致整个解析崩溃。解决简单的错误恢复策略包括“恐慌模式”当遇到意外 Token 时跳过后续所有 Token直到遇到一个“同步点”如分号、右花括号然后尝试继续解析。这能让 Parser 报告更多独立错误。6.3 代码生成与集成阶段问题生成的汇编代码无法通过汇编器如as编译。排查这是最直接的问题。仔细对比你生成的汇编和手动编写的正确汇编的每一行。常见的错误有指令拼写错误li写成la、寄存器名错误、缺少必要的汇编器指令如.text、标签格式错误等。使用汇编器的错误输出信息来定位。问题程序编译链接成功但在模拟器中运行结果不对或崩溃。排查检查系统调用如果你的程序需要打印结果在 RISC-V 裸机环境下可能需要使用 ecall 进行系统调用。我们简单的return程序依赖宿主环境如qemu-user或操作系统来获取返回值。在 Linux 下用echo $?查看上一个程序的退出状态这对应main函数的返回值。检查调用约定确保返回值确实放在了a0寄存器。在更复杂的函数中还需要处理栈帧来保存寄存器。使用调试器用qemu-riscv64 -g 1234 ./program启动模拟器并等待 gdb 连接然后用riscv64-unknown-elf-gdb ./program连接、单步执行观察寄存器和内存的变化。这是定位运行时问题的终极武器。6.4 如何扩展你的迷你编译器完成这个基础版本后你可以沿着多个方向扩展它每一个方向都能加深你对编译技术的理解支持更多数据类型和运算添加-负号、,-,*,/等运算符。这需要扩展 Lexer识别新符号、Parser定义表达式语法处理优先级和 CodeGen生成对应的算术指令。引入变量支持局部变量声明如int a;和赋值a 5;。这涉及到符号表的管理和栈帧布局。你需要为每个变量在栈上分配空间如addi sp, sp, -16; sw a0, 8(sp)并在访问时计算正确的偏移地址。支持控制流添加if-else和while语句。这需要生成条件跳转指令如beq,bne,j和标签。你需要一个机制来生成唯一的标签名如L0,L1。增加中间表示IR在 AST 和汇编之间引入一层类似于 LLVM IR 的中间表示。这样可以将与目标机器无关的优化如常量折叠、死代码删除放在 IR 层进行让代码生成器更专注于目标机器相关的翻译。尝试不同的目标架构尝试为 x86-64 或 ARM 生成汇编。你会立即体会到不同指令集架构ISA的差异并理解抽象中间表示的价值。这个简单的编译器项目就像一把钥匙为你打开了编译原理和编程语言实现的大门。从识别一个数字到解析一个表达式再到生成一条正确的指令每一步的完成都会带来巨大的成就感。更重要的是这个过程强迫你去思考编程语言最本质的表示、转换与执行。当你下次再使用gcc -O2时你看到的将不再是一个魔法黑盒而是一个由无数个类似但远为复杂的模块精密组合而成的工程奇迹。而这正是“从零开始”的意义所在。