RezeのBlog
← 返回文章列表

一行代码怎么变成能跑的程序

2020.10.19技术4481 字参考 3

编译原理这门课,睡过去的人不止一个。老师在黑板上推导 LL(1) 文法、讲什么“移进-归约”,我全程在想中午吃什么。当时我觉得这玩意儿离我太远了——我又不去写编译器,学它干嘛。

编译器把源码翻译成可执行程序的典型流程
编译器把源码翻译成可执行程序的典型流程

后来自己写 Java,有次报了个错,堆栈里全是看不懂的字节码行号,我对着 `at com.xxx.Foo.bar(Foo.java:42)` 下面那一串 `invokevirtual`、`aload_0` 发愣。搜了半天才在一个博客里看到答案:“这是 JVM 字节码,编译器把 Java 编成这个再跑的。”我“哦”了一声,心里其实是虚的。再后来我好奇,自己动手写了个几十行的迷你解释器,才算把“代码怎么变成能跑的东西”这条路走通了一遍。走完我才明白,编译原理根本不是给写编译器的人准备的,它是理解“你敲的那几行字,机器凭什么能执行”的底层地图。

先破除一个幻觉:你写的 `.java`、`.py`、`.js`,对 CPU 来说就是一串字符,跟一篇小说没有本质区别。CPU 不认识 `if`,不认识 `for`,它只认识一条条机器指令——加减、跳转、读写内存。所以中间必须有个翻译官,把“人话”翻成“机器话”。这个翻译官就是编译器(或者解释器)。编译原理研究的,就是这个翻译过程怎么做得高效、正确。

整个过程,粗略分五步:词法分析、语法分析、语义分析、中间代码生成与优化、目标代码生成。我一步步说。编译器拿到的是一整串字符:`let x = 1 + 2;`。它先干一件很朴素的事——把这串字符切成一个个有意义的“词”,术语叫 token。`let` 是一个关键字 token,`x` 是一个标识符 token,`=`、`+`、`;` 各是一个符号 token,`1`、`2` 是数字 token。空格通常直接扔掉。这一步看着简单,其实有坑。比如 `1.0` 是一个数字,但 `1.foo` 里的 `1` 和 `.` 就得分开;字符串里的 `“let”` 不能当成关键字;注释要整个跳过。词法分析器(lexer)就是按规则一个个地认。

我写那个迷你解释器的时候,第一步就是手写了个 tokenizer,几十行,用正则或者状态机都行。写完之后我突然理解了一个以前没想过的事:为什么有些语言里“关键字不能当变量名”——因为词法阶段它就被认成关键字了,根本没机会当标识符。

第二步:语法分析,把词拼成树

有了 token 列表,下一步是搞清楚“这些词怎么组合成有意义的句子”。这一步叫语法分析(parsing),产物是一棵抽象语法树(AST)。`let x = 1 + 2;` 会被拼成一棵树:一个“变量声明”节点,左边是 `x`,右边是一个“加法”节点,加法的左孩子是 `1`,右孩子是 `2`。AST 是后面所有工作的基础。它把“文本的线性顺序”变成了“结构的层次关系”。有了这棵树,编译器才知道“这个加法的两个操作数分别是啥”“这个 if 的条件和分支在哪”。

这一步也是报错大户。你写了个 `if (x > 1 {`,少个右括号,语法分析器走到那儿就懵了,只能跟你说“语法错误,期望 `)` 但遇到了 `{`”。那些让人抓狂的“unexpected token”,基本都是这一步吐出来的。我写解释器时,语法分析用的是最土的办法——递归下降,一个函数对应一种语法结构。写完之后我对“为什么报错信息经常指向一个八竿子打不着的行”有了切身体会:因为解析器是往下递归的,它真正发现问题的地方,往往比出错的地方晚了几步。语法过了,只说明“这句话符合语法”,不代表“这句话有意义”。`let x = “hello” + 1;` 语法上没问题,但类型对不上。

语义分析就是干这个:建符号表(记录每个变量叫什么、什么类型、作用域在哪),做类型检查,检查变量有没有声明、函数调用参数对不对。这一步过不了,就是你熟悉的那些类型错误:`Type 'string' is not assignable to type 'number'`。顺带一提,很多“编译期能发现的问题”都在这一步被拦下。这也是静态类型语言的一大价值——把错误提前到运行之前。我写 TypeScript 写多了,再回去写裸 JS,那种“运行到一半才炸”的感觉特别没安全感,就是因为少了一层语义检查。

第四步:中间表示和优化

真正体现编译器“聪明”的地方,是优化。直接拿 AST 生成机器码也能跑,但生成的代码会很蠢。所以编译器通常先把 AST 转成一种中间表示(IR),在 IR 上做各种优化,再生成目标代码。GCC 和 LLVM 的核心,就是这套 IR 加优化 pass。优化的招数很多,我挑几个好懂的:常量折叠:`1 + 2` 这种编译时就能算出 `3` 的,编译器直接替你算好,运行时不做了。死代码消除:`if (false) { ... }` 里面的代码永远执行不到,直接删掉;一个变量算出来从来没用过,也删掉。内联:一个小函数被到处调用,编译器干脆把函数体“贴”到调用处,省掉函数调用的开销。Java 的 JIT 特别爱干这个。

循环优化:把循环里每次都要算的、但其实不随循环变量变的表达式提到循环外;或者把循环展开,减少跳转次数。这些优化有个共同点:它们不改变程序的语义,只是让它跑得更快。我写那个迷你解释器时当然没做这些,所以它慢得感人。写完再去看专业的编译器做的优化,才知道“快”这件事,有多少是编译器在背后替你扛的。最后一步,把优化后的 IR 变成目标平台能跑的东西。这里分两条路。一条是 AOT(提前编译),直接生成机器码,比如 C/C++、Rust、Go 编出来的可执行文件。程序启动就能跑,性能稳定。另一条是生成字节码,交给虚拟机去跑,比如 Java 编成 `.class` 字节码,交给 JVM;C# 编成 IL,交给 .NET。字节码不是机器码,它是一种“更接近机器、但还保留跨平台性”的中间指令。JVM 在运行时再把字节码翻译成机器码,这一步叫 JIT(即时编译)。

JIT 到底在干嘛,为什么 JS 也能跑这么快

JIT 这块我特别想讲,因为它是很多人对“解释型语言”的最大误解来源。很多人以为 JS 是“解释执行”的,所以慢。这话在很久以前对,现在完全不对了。以 V8 为例,它的大致流程是:先把 JS 源码解析成 AST,再编译成字节码,由解释器(Ignition)先跑起来。跑的过程中,它会盯着那些“反复执行的热点代码”,把这些热点用优化编译器(TurboFan)编译成高度优化的机器码。如果后来发现假设错了(比如一个函数之前一直传数字,突然传了字符串),它就“去优化”,退回字节码重新跑。

所以现代 JS 引擎是“解释 + 编译”的混合体,它会根据运行时的实际情况动态决定怎么优化。这就是为什么同样的代码,跑热了之后会突然变快,也是为什么有些写法(比如让变量的类型变来变去)会让它优化失效、反而变慢。Java 的 HotSpot 也是这个思路,C1 做快速编译,C2 做深度优化,运行时根据热度切换。你看,Java 和 JS 在“运行时要编译”这件事上,其实是同一套哲学。

解释器和编译器,到底差在哪

很多人把这两个词混着用,其实它们的区别很朴素:编译器是“先全部翻译好,再拿去跑”;解释器是“边翻译边跑”。我用 Python 写那个迷你解释器的时候,走的是“树遍历”的路子:拿到 AST 之后,直接从根节点开始递归地“求值”——遇到加法节点,就算两个孩子的值加起来;遇到变量节点,就去符号表里查。整棵树走完,结果就出来了。这种方式的优点是直观、好实现,改一行代码立刻生效,不用等编译。缺点是慢,因为每次执行都要重新遍历一遍 AST,没有提前优化,也没有提前把“文本结构”变成机器能直接跑的指令。编译器则相反:它把整个程序一次性翻译成机器码(或字节码),生成一个文件,之后再执行就不用再翻译了。所以它启动慢一点(要编译),但跑起来快。

有意思的是,现在这条线已经模糊了。JS 引擎是“先解释字节码,热的再 JIT 编译”;Python 也有 PyPy 这种带 JIT 的实现。所以“解释型语言”和“编译型语言”这种分类,越来越不准确。更准确的说法是:这个语言的实现,是编译执行、解释执行,还是两者混合。我那个迷你解释器最后慢到什么程度?算个斐波那契 30,得等好几秒,同样的东西编译成机器码是毫秒级。那一刻我对“编译”这两个字的敬畏,是实打实的。

链接器:源代码之外,还有一关

还有一个经常被忽略的环节:链接(linking)。你写 C 或 Rust,代码里会调用别的文件、别的库里的函数。编译器一次只处理一个源文件,把它编成一个“目标文件”(.o),里面还有一堆“这个函数我不知道在哪”的占位。把所有目标文件、加上用到的库,拼成一个最终可执行文件,把那些占位填上真实地址——这个活儿是链接器干的。链接分两种。静态链接,是把用到的库代码整个拷进你的可执行文件里,好处是拷到哪都能跑,坏处是文件大、多个程序各拷一份浪费空间。动态链接,是运行时再去加载共享库(.so / .dll),好处是省空间、库更新了程序不用重编,坏处是“换个环境少个库就跑不起来”,也就是你熟悉的 `error while loading shared libraries`。

我第一次遇到“编译明明过了,运行却说找不到某个 .so”,整个人是懵的——编译器都点头了,怎么还跑不了?后来才明白,编译器只管“语法和类型对不对”,链接器管“东西找不找得到”,运行时的动态加载又是另一回事。这三关,各管各的。

现在回头看那串看不懂的字节码

回到开头那个堆栈。我现在再看 `aload_0`、`invokevirtual`,大概能猜出它在干嘛了:`aload_0` 是把第 0 个局部变量(通常是 `this`)压到操作数栈上,`invokevirtual` 是调用一个虚方法。这些指令,就是 javac 把 Java 源码编译成的“字节码”,JVM 再把它翻译成机器指令。

我以前觉得编译原理没用,是因为我以为它只服务于“写编译器的人”。现在我觉得,只要你写代码,懂一点它就有好处:你知道为什么有的写法快、有的慢,知道报错为什么长那样,知道 TypeScript 的类型检查、V8 的 JIT、Java 的字节码,背后其实是同一套“把文本翻译成可执行结构”的逻辑。那次我花了一个周末写那个迷你解释器,最后它只能算四则运算,慢得像蜗牛。但它让我第一次完整地看到:一行文本,怎么经过切词、拼树、检查、优化,最后变成机器能执行的指令。那种“原来如此”的感觉,比我在课上背一百遍 LL(1) 都值。有些知识,你不需要用它谋生,但懂了之后,你脚下那块地会变得结实一点。

参考与延伸