大四的课表慢慢空了下来。在广州商学院这几年的软件工程学习里,我写过不少应用层的代码,做过各种管理系统和小程序。为了维持专业第一的绩点,也为了那两次国家奖学金的答辩,我习惯了去钻研框架的源码和底层实现。但直到真正坐在屏幕前,开始写编译原理的大作业时,我才感觉到一种触及计算机科学本质的平静。
编译原理是计算机专业最硬核的课之一,这几乎是所有CS学生的共识。厚厚的“龙书”里堆满了形式化语言和自动机理论,很容易让人在第一章就失去耐心。这次的大作业要求并不算苛刻,目标是实现一个简单语言的编译器前端。不需要去生成晦涩的汇编代码,只要能把一段文本转化为计算机能理解的结构化数据就可以。
整个实现范围被我拆解成了三个明确的阶段。首先是词法分析器(Lexer),负责把毫无规律的源代码字符串切割成有意义的 Token 序列;其次是语法分析器(Parser),根据我们预先定义好的文法规则,把这些 Token 组装成抽象语法树(AST);最后是语义分析,在树的结构上进行类型检查和作用域的解析。
开发的第一步是从词法分析开始的。面对一段代码,人类的眼睛会自动识别出关键字、变量名和数字,但计算机看到的只是一个漫长的字符数组。词法分析器的任务,就是充当一个极其耐心的阅读者,逐个字符地扫描,然后把它们归类。
function tokenize(source) {
const tokens = []
let pos = 0
while (pos < source.length) {
if (/\d/.test(source[pos])) {
let num = ''
while (pos < source.length && /\d/.test(source[pos]))
num += source[pos++]
tokens.push({ type: 'NUMBER', value: Number(num) })
}
// ... 更多 token 类型
}
return tokens
}
这段代码看起来并不复杂,本质上就是一个带状态的指针在字符串上慢慢向前移动。但在实际编写的时候,细节里的坑并不少。比如处理数字时,不仅要考虑连续的整数,还要考虑小数点,甚至科学计数法。处理字符串字面量时,遇到转义字符需要做特殊的跳跃。还有一个容易绊倒人的地方是标识符和关键字的区分。当我们扫描到一个单词,比如 if,我们需要先去关键字表里查一下,如果存在,它就是一个 KEYWORD,否则它只是一个普通的变量名 IDENTIFIER。看着原本杂乱无章的文本变成一个整齐的 Token 数组输出在控制台时,会有一种把房间打扫干净的秩序感。
词法分析只是热身,真正的挑战在语法分析。拿到 Token 数组后,我们需要把它变成一棵树。这里我用的是递归下降解析(Recursive Descent Parsing)的方法。这种方法很直观,每一种语法规则对应一个函数。比如解析一个代码块,就写一个 parseBlock 函数,解析一个表达式,就写一个 parseExpression 函数。
踩坑最深的地方是处理运算符的优先级。比如 1 + 2 * 3,词法分析器给出的只是一条平坦的序列,但语法分析器必须知道 * 的优先级高于 +,从而把 2 * 3 包装成一个整体作为 + 的右子节点。刚开始写的时候,我没有处理好左递归的问题,导致解析器在遇到连续的加法操作时陷入了无限循环,直接把调用栈撑爆了。后来停下来重新翻书,引入了优先级表,通过比较当前运算符和下一个运算符的权重,才让这棵抽象语法树按预期的形状生长出来。当程序第一次成功打印出带有层级缩进的 AST 节点时,我盯着屏幕看了很久,那种感觉就像是亲手拆解并重新组装了一台精密的钟表。
树建好之后,代码的骨架就有了,但它还没有灵魂。语义分析要做的,就是赋予这棵树逻辑上的合理性。最核心的工作是维护一个符号表(Symbol Table)。在代码执行前,编译器需要知道每一个变量是在哪里声明的,它的类型是什么,以及当前的作用域能不能访问到它。
我用了一个栈来模拟作用域的嵌套。每当遍历到 AST 中的块级节点(比如进入一个 if 语句或者函数体),就往栈里压入一个新的 Map;当离开这个节点时,再把 Map 弹出。遇到变量声明时,就在当前的 Map 里记录下变量名和类型;遇到变量调用时,就从栈顶开始往下查找。如果找遍了整个栈都没有,就可以抛出一个 ReferenceError。在这个过程中,我也顺便实现了简单的类型检查。如果尝试把一个字符串赋值给一个声明为数字类型的变量,编译器就会在遍历到赋值表达式节点时报错。写到这里的时候,我突然明白了平时用 TypeScript 写代码时,编辑器里那些红色的波浪线到底是怎么产生的。它们不再是IDE变魔术,而是一次次静默的树遍历和查表。
整个项目断断续续写了半个月。提交代码的那天下午,广州刚好下了一场很大的阵雨。我坐在宿舍里,看着测试用例一个个跑通,绿色的勾在终端里依次亮起。
写编译器让我对日常使用的编程语言有了完全不同的理解。以前写代码,语言就像是一个黑盒,我只管按照文档输入,它负责输出结果。但现在,每次在编辑器里敲下 const x = 1 + 2 的时候,我脑海里都会自动浮现出这行代码经历的漫长旅程:它先是被拆解成五个 Token,然后被组装成一棵以 = 为根节点、左边是变量声明、右边是二元表达式的语法树,接着符号表里多了一个不可变的记录,最后才被转化为机器能执行的指令。
大学四年快结束了,GPA和奖学金是对过去学习态度的记录,但这个编译器前端,是我给自己写的一个总结。它让我确信,无论上层的技术框架怎么更迭,计算机科学最底层的逻辑始终是安静且坚固的。
这个大作业的完整代码我已经整理好了,放在了 GitHub 上,项目在 compile。如果以后有时间,也许我会继续给它写一个代码生成器,让它成为一个真正意义上的编译器。