从零构建编译器：词法分析、语法树与代码生成实践

1. 为什么我们要亲手“造轮子”理解编译器构建的底层价值在编程的世界里我们每天都在使用编译器。无论是写一行print(Hello, World)还是构建一个复杂的分布式系统最终都需要编译器这个“翻译官”将我们人类可读的代码转换成机器能执行的指令。大多数时候我们把它当作一个黑盒工具输入代码点击运行得到结果。但你是否想过这个黑盒内部是如何工作的当你在调试一个诡异的语法错误或者试图理解某个语言特性背后的行为时那种隔靴搔痒的感觉往往源于对编译过程底层逻辑的陌生。亲手构建一个编译器哪怕是最简单的版本其价值远超“完成一个作业”或“掌握一个知识点”。这更像是一次对计算机科学核心思想的深度解剖。你会直观地理解为什么编程语言要设计成现在这个样子——那些看似繁琐的语法规则、作用域、类型系统背后都是为了解决信息如何被无歧义地组织、分析和转换的问题。这个过程会彻底改变你阅读代码的视角。从此你看到的将不再是一行行孤立的指令而是一棵结构化的语法树一串被精确分类的符号流以及从高级抽象到低级指令的映射路径。这对于提升调试能力、理解语言设计哲学、乃至进行高性能优化都有着不可替代的作用。很多人觉得编译器是“屠龙之技”只有开发新编程语言才用得上。这是一个巨大的误解。现代软件开发中编译技术的思想无处不在构建工具如Webpack、Vite对模块依赖的分析、代码格式化工具如Prettier对代码结构的重排、静态代码检查工具如ESLint对潜在问题的侦测甚至是一些低代码平台的可视化逻辑到代码的转换其核心都是编译原理中词法分析、语法分析和代码生成的变体。理解这些能让你在遇到复杂工程问题时拥有更底层的工具箱和更清晰的解决思路。2. 我们的“微型语言”设计与目标设定在开始敲代码之前我们必须先明确我们要编译什么。为了聚焦核心流程避免被复杂的语言特性分散精力我们需要设计一门极简的“玩具语言”。这门语言的目标不是实用而是教学它必须能清晰地展示编译的每一个阶段。我设计了一个名为TinyCalc的语言。它只做一件事计算四则运算表达式并支持整数变量。它的语法规则我们称之为“文法”如下程序Program由一系列“语句”组成。语句Statement有两种形式变量名 表达式;赋值语句print(表达式);打印语句表达式Expression可以是一个数字、一个变量或者由,-,*,/连接的两个表达式并用括号()改变优先级。终结符数字如42、变量名如x 以字母开头可包含字母和数字、运算符,-,*,/、括号和分号。一个合法的 TinyCalc 程序示例如下x 10; y 20; z (x y) * 2; print(z);我们的编译器目标是将这样一段 TinyCalc 代码最终转换成一种可以“执行”的形式。为了简化我们不直接生成机器码而是生成一种非常简单的“中间指令”我们可以用 Python 或 JavaScript 写一个解释器来执行这些指令。这种指令集我们称为TinyVM指令它可能包括PUSH 5 将数字5压入栈。LOAD x 将变量x的值压入栈。ADD 弹出栈顶两个值相加后结果压回栈。STORE y 弹出栈顶值存入变量y。PRINT 弹出栈顶值并打印。这样我们的编译目标就非常明确了将 TinyCalc 源码翻译成 TinyVM 指令序列。整个过程将清晰地分为三个核心阶段接下来我们就逐一拆解。3. 第一阶段词法分析——将字符流转化为有意义的单词词法分析器也叫扫描器是编译器的“眼睛”。它的任务极其纯粹读入源代码的字符流一个长长的字符串忽略空格、制表符、换行这些无关紧要的空白字符然后将其切割成一系列不可再分的基本单元我们称之为词法单元。每个词法单元通常是一个二元组(类型, 值)。例如对于代码position initial rate * 60;词法分析器不会把它看成一堆字符而是识别为[(标识符, position), (赋值符, ), (标识符, initial), (加号, ), (标识符, rate), (乘号, *), (数字, 60), (分号, ;)]3.1 如何实现一个简单的词法分析器我们不需要一上来就研究复杂的自动机理论。一个直观且足够用于 TinyCalc 的方法是手动编写一个状态机。我们可以用一个指针从头到尾扫描源代码字符串根据当前字符决定进入什么状态并收集字符形成词素。核心状态初始状态 遇到字母进入“标识符”状态遇到数字进入“数字”状态遇到运算符或分号直接生成对应词法单元遇到空格/换行直接跳过。标识符状态 持续读取字母或数字直到遇到非字母数字的字符如运算符、空格此时将收集到的字符串作为标识符的词素生成(标识符, 词素)单元并回退一个字符因为当前字符不属于这个标识符回到初始状态。数字状态 持续读取数字直到遇到非数字字符生成(数字, 词素)单元并回退一个字符。实操心得与避坑指南回退操作是关键 在标识符或数字状态结束时我们读到的那个“终止字符”如或空格是属于下一个词法单元的。必须将扫描指针回退一位否则这个字符就被“吃掉”了。这是手动实现时最容易出错的地方。提前识别关键字 像print这样的词虽然看起来像标识符但它是语言的关键字。一种常见的做法是先统一按标识符规则收集生成词法单元后在一个“关键字表”里查找这个词素。如果找到则将其类型从“标识符”改为“关键字”。这样设计比在扫描时做特殊判断更清晰。处理多字符运算符 虽然 TinyCalc 没有但很多语言有,,这样的运算符。在扫描到第一个字符如时需要“向前看”一个字符判断是否能组成双字符运算符。这要求词法分析器具备有限的“预读”能力。下面是一个极度简化的 TinyCalc 词法分析器 Python 伪代码片段展示了核心逻辑class Lexer: def __init__(self, text): self.text text self.pos 0 self.current_char self.text[self.pos] if self.pos len(self.text) else None def advance(self): self.pos 1 self.current_char self.text[self.pos] if self.pos len(self.text) else None 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() # 检查是否为关键字 if result print: return Token(PRINT, result) return Token(ID, 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.isalpha(): return self.identifier() # 处理单字符符号 if self.current_char : self.advance() return Token(ASSIGN, ) if self.current_char ;: self.advance() return Token(SEMI, ;) if self.current_char : self.advance() return Token(PLUS, ) # ... 处理 -, *, /, (, ) self.error() return Token(EOF, None)词法分析器的输出是一个有序的词法单元列表。这个列表将作为下一个阶段——语法分析器的输入。词法分析的成功意味着编译器已经正确理解了源代码中每一个“单词”是什么为理解整个“句子”的结构打下了基础。4. 第二阶段语法分析——从单词到结构树如果说词法分析是认单词那么语法分析就是理解句子的语法结构。它接收词法单元流并依据我们预先定义好的“文法”规则检查这些单词的排列组合是否符合语言的语法规范同时构建出一棵能够反映代码层次结构的树——抽象语法树。AST 是编译器前端最核心的数据结构。它抛弃了源代码中的一些细节如分号、括号但这些信息已隐含在树结构中只保留对后续生成代码有意义的逻辑结构。对于表达式x 10 y * 2其 AST 可能如下图所示文本表示(赋值) / \ (变量x) (加号) / \ (数字10) (乘号) / \ (变量y) (数字2)4.1 两种主流的语法分析方法语法分析有两大流派自顶向下和自底向上。对于 TinyCalc 这样的简单语言自顶向下的递归下降分析法是最直观、最适合手工实现的方法。递归下降分析 我们为文法中的每一条规则如“语句”、“表达式”编写一个对应的函数。这个函数的任务就是“吃掉”符合该规则的词法单元序列并在过程中递归调用其他规则函数最终构建出 AST 节点。它就像是一个严格的语法导游按照既定路线文法检查游客词法单元的参观顺序。自底向上分析 更强大能处理更复杂的文法如 LR 文法但原理和实现都复杂得多通常需要工具如 Yacc, Bison来生成分析器。我们暂时不涉及。4.2 实现递归下降分析器我们的 TinyCalc 文法是精心设计的它避免了“左递归”形如Expr - Expr Term的规则这是递归下降分析的大敌会导致函数无限递归。我们的表达式规则可以这样设计Expr - Term ((PLUS|MINUS) Term)* Term - Factor ((MUL|DIV) Factor)* Factor - INTEGER | ID | LPAREN Expr RPAREN*表示0次或多次重复。这保证了乘除法Term比加减法Expr有更高的优先级括号Factor有最高的优先级。对应的递归下降函数伪代码如下class Parser: def __init__(self, lexer): self.lexer lexer self.current_token self.lexer.get_next_token() 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): Factor : INTEGER | ID | LPAREN Expr RPAREN token self.current_token if token.type INTEGER: self.eat(INTEGER) return NumNode(token.value) elif token.type ID: self.eat(ID) return VarNode(token.value) elif token.type LPAREN: self.eat(LPAREN) node self.expr() # 递归解析括号内的表达式 self.eat(RPAREN) return node def term(self): Term : Factor ((MUL | DIV) Factor)* node self.factor() while self.current_token.type in (MUL, DIV): op_token self.current_token self.eat(op_token.type) node BinOpNode(leftnode, opop_token.value, rightself.factor()) return node def expr(self): Expr : Term ((PLUS | MINUS) Term)* node self.term() while self.current_token.type in (PLUS, MINUS): op_token self.current_token self.eat(op_token.type) node BinOpNode(leftnode, opop_token.value, rightself.term()) return node def statement(self): Statement : ID ASSIGN Expr SEMI | PRINT LPAREN Expr RPAREN SEMI if self.current_token.type ID: var_name self.current_token.value self.eat(ID) self.eat(ASSIGN) expr_node self.expr() self.eat(SEMI) return AssignNode(var_name, expr_node) elif self.current_token.type PRINT: self.eat(PRINT) self.eat(LPAREN) expr_node self.expr() self.eat(RPAREN) self.eat(SEMI) return PrintNode(expr_node) def program(self): Program : Statement statements [] while self.current_token.type ! EOF: statements.append(self.statement()) return ProgramNode(statements)4.3 语法分析中的常见陷阱与调试错误恢复 一个健壮的编译器不应该在遇到第一个语法错误时就崩溃。我们需要在分析器中加入错误恢复机制。例如在statement函数中如果遇到意外的词法单元可以跳过一些 token直到遇到分号;然后尝试继续解析下一条语句。这能帮助用户一次发现多个错误。左递归问题 这是递归下降的经典陷阱。如果你写的文法规则是Expr - Expr Term那么expr()函数会直接调用expr()导致无限递归。必须将文法改写为等价的右递归或迭代形式如我们上面用的Expr - Term ((PLUS|MINUS) Term)*。优先级与结合性 乘除优先于加减是通过expr - term和term - factor的层级嵌套实现的。左结合性如a - b - c理解为(a - b) - c是通过在while循环中不断用当前节点作为新节点的左子树来实现的。右结合性如赋值a b c则需要不同的处理方式。语法分析器成功运行后我们就得到了一棵完整的 AST。这棵树精确地描述了源代码的语义结构是进行语义检查如下一节和代码生成的基础。此时编译器已经“理解”了程序要做什么。5. 第三阶段语义分析与中间表示——为代码生成铺路在得到 AST 之后直接生成目标代码是鲁莽的。我们还需要进行语义分析以确保程序在逻辑上是正确的。对于 TinyCalc语义分析相对简单主要包括变量声明检查 TinyCalc 是动态类型变量无需声明即可使用。但我们需要一个符号表来记录每个变量当前的值或类型。当遇到x 10;时我们在符号表中记录或更新x。当在表达式中使用y时我们需要检查符号表中是否存在y即y是否已被赋值过。对于我们的简单实现可以在运行时检查也可以在编译时进行“使用前定义”的简单检查。类型检查 TinyCalc 只有整数类型所以类型检查很简单确保运算符两边的表达式结果都是整数。在更复杂的语言中这是语义分析最繁重的部分之一。语义分析的过程通常伴随着对 AST 的遍历。我们可能会进行多次遍历一次用于构建符号表一次用于类型检查一次用于为代码生成收集信息。5.1 引入中间表示直接遍历 AST 生成最终的目标代码如 TinyVM 指令是可行的但通常不是最优选择。AST 的树形结构非常利于分析和转换但不利于生成线性的指令序列。因此编译器常常引入一种更接近目标代码的线性表示——中间表示。IR 是介于源代码和目标代码之间的一种表示形式。它既保留了高级语言的语义如变量、操作又具有低级语言的线性特征如基本块、跳转。三地址码是一种常见的 IR它的每条指令最多包含三个“地址”可以是变量、常量或临时变量。例如t1 y * 2和t2 x t1就是三地址码。将 AST 转换为 IR 是一个标准化的 lowering lowering过程。这个过程会消除语法糖 将复杂的语法结构分解为简单的操作。引入临时变量 保存中间计算结果。规范化控制流 将各种循环、条件语句转换为带标签和跳转指令的线性序列。对于 TinyCalc我们可以定义一个非常简单的 IR它其实就是 TinyVM 指令的另一种形式但更结构化。例如将x 10 y * 2的 AST 转换为以下指令序列t1 MUL y, 2 t2 ADD 10, t1 x ASSIGN t2这个转换过程可以通过对 AST 进行后序遍历来实现先处理子节点再处理父节点。每个表达式节点如BinOpNode被访问时会递归生成其左右子表达式的代码然后生成一条将自己左右结果合并的指令并将结果存入一个新的临时变量该临时变量名作为该节点的“值”返回给父节点。5.2 符号表的设计与实现符号表是语义分析的基石。对于 TinyCalc一个简单的符号表可以就是一个字典Python或对象JavaScript键是变量名值可以是变量的类型信息目前只有int或者为了代码生成所需的其他属性如分配的虚拟寄存器编号或栈帧偏移量。class SymbolTable: def __init__(self): self.symbols {} def define(self, name, type_int): if name in self.symbols: raise Exception(f变量 {name} 重复定义) self.symbols[name] {type: type_} def lookup(self, name): if name not in self.symbols: # 简单实现允许未声明使用但可以给出警告 # 更严格的实现抛出异常 “变量未定义” self.symbols[name] {type: int} # 隐式声明 return self.symbols[name]在遍历 AST 进行语义分析时我们携带这个SymbolTable实例。遇到赋值语句的左值变量名时调用define或更新遇到表达式中使用变量时调用lookup检查。虽然 TinyCalc 简单但这个模式是任何编译器符号管理的基础。6. 第四阶段代码生成与“虚拟机”实现这是将前端成果转化为可执行结果的最后一步。我们有了 IR或直接基于 AST也有了符号表现在要为 TinyCalc 程序生成 TinyVM 指令。6.1 从 IR 到目标代码代码生成器本质上是一个 IR或 AST的翻译器。它遍历 IR 指令序列为每一条 IR 指令生成一条或多条目标机器这里是 TinyVM指令。这个过程需要考虑指令选择 对于ADD操作直接生成ADD指令。寄存器分配 这是真实编译器中最复杂的环节之一决定哪些值放在有限的 CPU 寄存器中哪些需要溢出到内存。对于我们的栈式 TinyVM这个问题被简化了——所有计算都通过一个操作数栈进行。指令调度 调整指令顺序以利用目标机器的特性如流水线。对于 TinyVM我们忽略。我们的 TinyVM 设计为栈式虚拟机这是实现起来最简单的一种。它有一个操作数栈和一个存储变量的内存区。PUSH和LOAD指令向栈顶压入值ADD、MUL等指令从栈顶弹出所需数量的操作数进行计算再将结果压回栈顶。STORE从栈顶弹出一个值存入变量空间。生成代码的算法非常直接。我们之前将x 10 y * 2转换成了三地址码 IR。现在为每条 IR 生成 TinyVM 代码t1 MUL y, 2-LOAD y,PUSH 2,MUL(执行后栈顶是t1的值)t2 ADD 10, t1-PUSH 10,ADD(栈顶现在是t1 执行ADD需要两个操作数所以需要调整顺序。更稳妥的方式是所有的二元运算都先计算右操作数再计算左操作数或者使用临时变量存储。为了简单我们可以规定 IR 是逆波兰表达式形式或者生成代码时注意顺序。) 一个更系统的做法是在生成 IR 时就确保每个操作的结果都保存在一个临时变量中然后代码生成器为每个临时变量分配一个栈位置或直接生成计算它的指令序列。6.2 实现 TinyVM 解释器生成 TinyVM 指令后我们需要一个解释器来执行它以验证编译器的正确性。这个解释器本身就是一个简单的循环读取并执行每一条指令。class TinyVM: def __init__(self): self.stack [] self.vars {} def run(self, instructions): ip 0 # 指令指针 while ip len(instructions): instr instructions[ip] op instr[0] if op PUSH: self.stack.append(instr[1]) elif op LOAD: var_name instr[1] self.stack.append(self.vars.get(var_name, 0)) # 未定义变量默认为0 elif op ADD: 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 STORE: value self.stack.pop() var_name instr[1] self.vars[var_name] value elif op PRINT: value self.stack.pop() print(value) else: raise Exception(f未知指令: {op}) ip 1 # 示例指令序列 instructions [ (PUSH, 10), (STORE, x), (PUSH, 20), (STORE, y), (LOAD, x), (LOAD, y), (ADD,), (PUSH, 2), (MUL,), (STORE, z), (LOAD, z), (PRINT,) ] vm TinyVM() vm.run(instructions) # 输出: 606.3 整合与测试最后我们将所有阶段串联起来源代码 - 词法分析器 - 语法分析器生成 AST- 语义分析/IR 生成器 - 代码生成器 - TinyVM 指令 - 虚拟机执行。编写测试用例至关重要。从简单的单个表达式开始逐步测试变量赋值、运算符优先级、括号、多条语句、print语句等。这个过程会暴露出你在前面各阶段未曾考虑到的边界情况比如空格处理、错误输入、除零错误可以在运行时检查等。7. 超越玩具从 TinyCalc 到真实编译器的鸿沟与桥梁完成 TinyCalc 编译器你已经走完了现代编译器核心流水线的简化版。但要理解真实编译器如 GCC, Clang的复杂性我们需要知道 TinyCalc 省略了什么丰富的类型系统 支持浮点数、字符串、数组、结构体、指针等。每种类型都需要特定的操作指令和存储布局。复杂的控制流if-else条件分支、while/for循环、switch语句、函数调用/返回。这需要引入标签、条件跳转和无条件跳转指令并管理好执行路径。函数与作用域 这是质的飞跃。需要管理调用栈、参数传递、返回值、局部变量和全局变量的寻址。符号表会变成层次结构作用域链。优化 真实编译器花费大量时间在优化上例如常量折叠、公共子表达式消除、死代码删除、循环优化等。这些都是在 IR 上进行的复杂变换。目标代码生成 生成真实的机器码x86, ARM或成熟的字节码JVM, .NET IL需要处理复杂的指令集、寄存器分配算法和内存对齐。如何从 TinyCalc 出发继续深入学习扩展语言特性 尝试为 TinyCalc 添加if语句和while循环。这会迫使你设计条件跳转指令并理解控制流图的构建。学习经典工具 使用Lex(或 Flex) 和Yacc(或 Bison)。它们是生成词法分析器和语法分析器的工具。你只需要用特定的语法描述词法规则和文法规则它们就能自动生成 C 代码。这能让你专注于语言设计本身而不是手写分析器。研究真实项目 看看LLVM教程。LLVM 提供了一个模块化、可重用的编译器基础设施。你可以用它的前端工具Clang生成 LLVM IR然后学习如何为这个 IR 写一个简单的后端或者用 LLVM 的 JIT 引擎直接执行。这会让你立刻站上巨人的肩膀。阅读《编译原理》 龙书紫龙书是经典。虽然理论性强但结合了 TinyCalc 的实践后再去读你会对自动机、文法、语法制导翻译等概念有恍然大悟的感觉。亲手实现 TinyCalc 的过程就像第一次拆开钟表看到了里面的齿轮。它不会让你立刻成为钟表匠但让你明白了时间是如何被具象化驱动的。下次当你再使用gcc或javac时你听到的不再是黑盒的轰鸣而是词法分析器在贪婪地扫描语法分析器在递归地下降代码生成器在忙碌地发射指令——那是一首由逻辑与数据构成的交响乐而你现在至少能听懂它的主旋律了。