自制编程语言，六个令你迷惑的问题

自制编程语言和虚拟机，这是一个看似很深奥的课题，也涉及当今互联网流行的主题，许多技术人员对其心驰神往，但要领悟其精髓步履维艰。

《自制编程语言》循序渐进、由浅到深地讲解了丰富的基础知识，覆盖了常见的编译原理入门知识，更难能可贵的是，作者讲解的知识具有其独特的理解和视角，相信本书能让读者能够受益匪浅。

本文涉及一些编译原理基础，我担心没学过编译原理的读者会觉得吃力，因此顺带介绍了编译原理的基础知识。当然，不会编译原理也无法阻止你成功写出一门脚本语言。

因为原理太抽象了，而且为了严谨，理论总是把简单的描述成复杂的。在实践中你会发现，编译器的实现比理解编译器原理容易，你会发现——原来晦涩难懂的概念其实就是这么简单，以至于你是通过实践才懂得了编译原理。毕竟纸上得来终觉浅，绝知此事要躬行。今天我们来介绍一些自制编程语言可能令人迷惑的问题。

编译型程序和脚本程序的异同

两者最明显的区别就是看它们各是谁的“菜”。两者的共性是最终生成的指令都包含操作码和操作数两部分。

编译型程序所生成的指令是二进制形式的机器码和操作数，即二进制流。同样是数据，和文本文件相比，这里的数据是二进制形式，并不是文本字符串（如ASCII码或unicode等）形式。

如果二进制流按照有无格式来划分，无格式的便是纯粹的二进制流，程序的入口便是文件的开始。另外一种是按照某种协议（即格式）组织的二进制流，比如Lnux下elf格式的可执行文件。它是硬件CPU的直接输入，因此硬件CPU是“看得到”编译型程序所对应的指令的，CPU亲自执行它，即机器码是CPU的菜。

编译型语言编译出来的程序，运行时本身就是一个进程，它是由操作系统直接调用的，也就是由操作系统加载到内存后，操作系统将CS:IP寄存器（IA32体系架构的CPU）指向这个程序的入口，使它直接上CPU运行，这就是所说的CPU“看得到”它。总之调度器在就绪队列中能看到此进程。

脚本语言，也称为解释型语言，如JavaScript、Python、Perl、Php、Shell脚本等。它们本身是文本文件，是作为某个应用程序的输入，这个应用程序是脚本解释器。由于只是文本，这些脚本中的代码在脚本解释器看来和字符串无异。

也就是说，脚本中的代码从来没真正上过CPU去执行，CPU的CS：IP寄存器从来没指向过它们，在CPU眼里只看得到脚本解释器，而这些脚本中的代码，CPU从来就不知道有它们的存在，脚本程序却因硬件CPU而间接“运行”着。

这就像家长给孩子生活费，孩子用生活费养了只狗狗，家长只关心孩子的成长，从不知道狗狗的存在，但狗狗却间接地成长。这些脚本代码看似在按照开发人员的逻辑在执行，本质上是脚本解释器在时时分析这个脚本，动态根据关键字和语法来做出相应的行为。

解释器有两大类，一类是边解释边执行，另一类是分析完整个文件后再执行。如果是第一类，那么脚本中若有语法错误，先前正确的部分也会被正常执行，直到遇到错误才退出；如果是第二类，分析整个文件后才执行的目的是为了创建抽象语法树或者是用与之等价的遍历去生成指令，有了指令之后再运行这些指令以表示程序的执行，这一点和编译型程序是一致的。

脚本程序所生成的指令是文本形式的操作码和操作数，即数据以文本字符串的形式存在。其中的操作码称为opcode，通常opcode是自定义的，所以相应的操作数也要符合opcode的规则。为了提高效率，一个opcode的功能往往相当于几百上千条机器指令的组合。

如果虚拟机不是为了效率，多半是用于跨平台模拟程序运行。这种虚拟机所处理的opcode就是另一体系架构的机器码，比如在x86上模拟执行MIPS上的程序，运行在x86上的虚拟机所接收的opcode就是MIPS的机器码。

除跨平台模拟外，通常虚拟机的用途是提高执行效率，因此opcode很少按照实际机器码来定义，否则还不如直接生成机器指令交给硬件CPU执行更快呢。故此种自定义的指令是虚拟机的输入，即所谓虚拟机的菜。

虚拟机分为两大类，一类是模拟CPU，也就是用软件来模拟硬件CPU的行为，这种往往是给语言解释器用的，比如Python虚拟机。另一类是要虚拟一套完整的计算机硬件，比如用数组虚拟寄存器，用文件虚拟硬盘等，这种虚拟机往往是用来运行操作系统的，比如VMware，因为只有操作系统才会操作硬件。

脚本程序是文本字符流（即字符串），其以文本文件的形式存储在磁盘上。具体的文本格式由文本编译器决定，执行时由解释器将其读到内存后，逐行语句地分析并执行。

执行过程可能是先生成操作码，然后交给虚拟机逐句执行，此时虚拟机起到的就是CPU的作用，操作码便是虚拟机器的输入。

当然也可以不通过虚拟机而直接解析，因为解析源码的顺序就是按照程序的逻辑执行的顺序，也就是生成语法树的顺序，因此在解析过程中就可以同时执行了，比如解析到 2+3 时就可以直接输出 5 了。

但方便是有限的，实现复杂的功能就不容易了，因为计算过程中需要额外的数据结构，比较对于函数调用来说总该有个运行时栈来存储参数和局部变量以及函数运行过程中对栈的需求开销。因此对于复杂功能，多数情况下还是专门写个虚拟机来完成。

顺便猜想一下解释型语言是如何执行的。我们在执行一个PHP脚本时，其实就是启动一个C语言编写出来的解释器而已。这个解释器就是一个进程，和一般的进程是没有区别的，只是这个进程的输入则是这个PHP脚本。在PHP解释器中，这个脚本就是个长一些的字符串，根本不是什么指令代码之类。

只是这种解释器了解这种语法，按照语法规则来输出罢了。举个例子，假设下面是文件名为a.php的PHP代码。

php解释器分析文本文件a.php时，发现里面的echo关键字，将其后面的参数获取后就调用C语言中提供的输出函数，比如printf((echo的参数))。PHP解释器对于PHP脚本，就相当于浏览器对于JavaScript一样。

不过这个完全是我猜测的，我不知道PHP解释器里面的具体工作，以上只是为了说清楚我的想法，请大家辩证地看。

说到最后，也许你有疑问，如果CPU的操作数是字符串的话，那CPU就能直接执行脚本语言了，为什么CPU不直接支持字符串作为指令呢？后面会有分享。

脚本语言的分类

脚本语言大致可分为以下4类。

（1）基于命令的语言系统

在这种语言系统中，每一行的代码实际上就是命令和相应的参数，早期的汇编语言就是这种形式。此类语言系统编写的程序就是解决某一问题的一系列步骤，程序的执行过程就是解决问题的过程，就像做菜一样，步骤是提前写好在脑子里（或菜谱中）的。如以下炒菜脚本。

以上步骤中第1列都是命令，后面是命令的参数。其中把菜放进锅后不断地搅拌（示意而已，不用太严谨），由于命令式语言系统中没有循环语句，需要连续填入多个stir以实现连续多个相同的操作。会有一个解释器逐行分析此文件，执行相应命令的处理函数。以下是一个解释器示例。

（2）基于规则的语言系统

此类语言的执行是基于条件规则，当满足规则时便触发相应的动作。其语言结构是谓词逻辑→动作，如图1-1所示。

图1-1

因此此类语言常称为逻辑语言，常用于自然语言处理及人工智能方面，典型的代表有Prolog。

（3）面向过程的语言系统

面向过程的语言系统我们都比较熟悉，批处理脚本和shell脚本，perl、lua等属于此类，和基于命令的语言系统相比，它可以把一系列命令封装成一个代码块供反复调用。此代码块便是借用了数学中函数的概念，一个x对应一个y，即给一个输入便有一个输出，于是这个代码块便称为函数。

（4）面向对象的语言系统

现代脚本语言基本上都是面向对象，大伙儿用的都挺多的，比如python。很多读者误以为只要语言中含有关键字class，那么该语言就是面向对象的语言，这就不严谨了。因为在perl语言中也可以通过关键字class定义一个类，但其内部实现上并不是完全面向对象，其本质是面向过程的语言。世界上第一款血统纯正的面向对象语言是smalltalk，它在实现上就是一切皆对象，具有完全面向对象的基因。

为什么CPU要用数字作为指令

在之前小节“编译型程序和脚本程序的异同”的结束处我们讨论过，为什么CPU不直接支持字符串作为指令。我估计有的读者会误以为CPU将直接执行汇编代码，这是不对的，因为汇编代码是机器码的符号化表示，几乎是与机器码一一对应，但汇编代码绝对不是机器语言。

你想，如果汇编代码是机器指令的话，那么CPU看到的输入便是字符串，比如以下汇编代码用于计算1+10-2。

汇编语言其实是汇编器的输入，对于汇编器来说，汇编代码文件也是文本，因此其中mov指令也是字符串。如果让CPU直接读取汇编文件逐行分析各种字符串以判断指令，这效率必然非常低下。

毕竟要比较的字符数太多，比较的次数多了效率当然就低了，因此把指令编号为数字，这样比较数字多省事。而且最主要的是，CPU更擅长处理数字，它本身的基因就是数字电路，数字计算是建立在数值处理的基础上，这就是本质上二进制数据比文本ASCII码更快更紧凑的原因。

为什么脚本语言比编译型语言慢

而脚本语言的编译有两类，一类是边解释边执行，不产生指令，这个解释过程最占时间的部分就是字符串的比较过程，字符串比较的时间复杂度是O(n)，也就是在比较n次之后解释器才确定了操作码是什么，然后再去获取操作码的操作数，你看能不慢吗？而编译型语言编译后是机器码，是二进制数字，因此可直接上CPU运行，而CPU擅长处理数字，比较一次数字便可确定操作码。

另一类脚本语言是先编译，再生成操作码，最后交给虚拟机执行，这样多了一个生成操作码的过程，似乎“显得”更慢了。其实这都不是主要的。

你看，程序“执行”速度的快慢是比较出来的，编译型语言在执行时已经是二进制语言了，而大多数脚本语言在执行时还是文本，必然要先有个编译过程。

这里面全是字符串处理，整个脚本的源码对于编译器来说就是一个长长的字符串，都要完整地进行各种比较，因此多了一个冗长的步骤，必然要慢。有些脚本系统为减少编译的过程，第一次编译后将编译结果缓存为文件，如Python会将.py文件编译后存储为.pyc文件，下次无须编译直接运行便可。

但是，这样无须二次编译的脚本语言就能和编译型程序媲美吗？不见得磁盘IO是整个系统最慢的部分，解释器读取缓存文件难道不需要时间吗？等等，有读者说了，编译型的程序被操作系统加载时也要从磁盘上读取啊，这不一样吗？

当然不一样，别忘了，脚本程序在执行时先要加载解释器，解释器也是位于硬盘上的文件，只是二进制可执行文件而已，依然需要读取硬盘，然后解释器再去从硬盘上读取脚本语言文件并编译脚本文件。

你看，编译型程序在执行时只有1个IO，而脚本程序在执行时有两个，比前者多了1个低速的IO操作，因此，脚本语言更慢一些是注定的。

既然脚本语言比较慢，为什么大家还要用

这里的语言是指语言的编译器或解释器，以下简称为语言。

语言慢并不影响整个系统，影响整个系统速度的短板并不是语言本身，目前来说系统的瓶颈普遍是在IO部分。语言再慢也比IO快一个数量级，并不是语言执行速度快10倍后整个系统就快10倍，语言慢了，整个系统依然不受影响，这要看瓶颈是哪块儿。

这就像动物园运送动物的船超载了，人们不会埋怨某些人太胖了，而是清楚地知道占分量的主要是船上的大象，人的体重和大象根本就不是一个量级。

再说，即使是语言提速后，由于IO这块跟不上，依然会被阻塞（由于是脚本语言，这里阻塞的是脚本解释器），而且由于语言太慢而显得阻塞时间更漫长。

为什么会阻塞呢？这种阻塞往往是由于程序后续的指令需要从IO设备读取到的数据，也就是说程序后面的步骤依赖这些数据，没这些数据程序运行没意义。比如说Web服务器先要读取硬盘上的数据然后通过网卡发送给用户，必须获得硬盘数据后，web服务器进程中那部分操作网卡发送数据的指令才能上CPU上执行。

由于语言的解释器是由CPU处理的，CPU速率肯定比IO设备快太多，因此在等待IO设备响应的过程中啥也干不了。操作系统为了让宝贵的CPU资源得到最大的利用，肯定会把进程（二进制可执行程序或脚本语言的解释器）加入阻塞队列，让其他可直接运行的、不需要阻塞的进程使用CPU（阻塞指的是并不会上CPU运行，也就是将该进程从操作系统调度器的就绪队列中去掉）。

而语言（脚本语言解释器）再慢也比IO设备快，因此依然会因为更慢的IO而难逃阻塞的命运。也就是说，拖慢整个系统后腿的一定是系统中最慢的部分，而无论脚本语言多慢，IO设备总是会比语言更慢，因此“影响系统性能”这个黑锅，脚本语言不能背。

另一方面大伙儿喜欢用脚本语言的原因是开发效率高，这也是脚本语言被发明的初衷，很多在C中需要多个步骤才能实现的功能在脚本语言中一句话就搞定，当然更受开发人员欢迎了。

什么是中间代码

很多编译器会将源语言先编译为中间代码，最后再编译为目标代码，但中间语言并不是必需的。中间代码简称IR，是介于源程序和机器语言之间的语言，有N元式（如三元式、四元式）、逆波兰、树等形式。

目标代码是指运行在目标机器上的代码，与目标机器的体系架构直接相关，编译器干吗不直接生成目标代码，多这一道程序有什么好处呢？

（1）可以跨平台

由于中间代码并不是目标代码，因此可以作为所有平台的公共语言，从而可通过中间代码实现前后端分离。比如在多平台、多语言的环境下开发可提高开发效率，只要在某一平台上编译出中间代码后，中间代码到目标代码的剩余工作可以由目标平台的编译器继续完成。

（2）便于优化

中间代码更接近于源代码，对于优化来说更直接有效。而且可以在一种平台上优化好中间代码，再发送到其他平台编译为目标机器，提高优化效率。

什么是编译器的前端、后端

编译器的前后端是由中间代码来划分的，如图1-2所示。

图1-2

前端主要负责读取源码，对源码进行预处理，通过词法分析把单词变成Token流，然后进行语法分析，语义分析，将源码转换为中间代码。

后端负责把中间代码优化后转换为目标代码。

词法分析、语法分析、语义分析和生成代码并不是串行执行

很多教材上会把编译阶段分为几个独立的部分：

（1）词法分析；

（2）语法分析；

（3）语义分析；

（4）生成中间代码；

（5）优化中间代码；

（6）生成目标代码。

这容易给人造成“这几个步骤是串行执行”的错觉，即“从源码到目标代码必须要顺序地执行这6个步骤”，其实不是这样子的，至少一个高效的编译器绝不会这样做。

这只是在功能逻辑上的步骤，就拿前4步来说，它们是以语法分析为主线，以并行的、穿插的方式在一起执行的，即这4个步骤是随语法分析同时开始，同时结束。

每个步骤的功能实现由其实际的模块完成，负责词法分析的模块称为词法分析器，负责生成代码的模块称为代码生成器，负责语法分析的模块称为语法分析器。

我们所说的编译器就是由词法分析器、语法分析器和代码生成器组成的（如果有目标代码优化的话还包括优化模块）。

编译工作的入口是语法分析，因此编译是以调用语法分析器为开始的，语法分析器会把词法分析器和代码生成器视为两个子例程去调用。换句话说，词法分析器和代码生成器只会被语法分析器调用，如果没有语法分析器，它们就没有“露脸儿”的机会。

因此说编译是以语法分析器为主线，由语法分析器穿插调用词法分析器和代码生成器并行完成的。

语法分析和语义分析尽管是两个功能，但这其实可以合并为一个。因为在语法分析过后便知道了其语义。这个很好理解，毕竟语法就是语义的规则，规则是由编译器（的设计者）制定的，那么编译器（的设计者）分析了自己设定的规则后当然就明白了语义（不可能不明白自己所制定规则的意义）。

比如读英文句子，尤其是复杂的长句，先找到句子谓语动词，以谓语动词为分界线把句子拆分主谓两大部分，在前一部分中找主语，后一部分中找宾语等，在分析完语法后句子的意思就搞清楚了。

也就是说，语法分析和语义分析是同时，又是前后脚的事儿，因此合并到一起并不奇怪。你看，语法分析和语义分析确实是并行。

为了语法分析的效率，词法分析器往往是作为一个子例程被语法分析器调用，即每次语法分析器需要一个单词的token时就调用词法分析器。你看，语法分析和词法分析确实也是并行。

最后说生成代码。目前生成代码的方式叫语法制导，什么是语法制导呢？就是在分析语法的“同时”生成目标代码或中间代码，实际上就是以语法分析为导向，语法分析器在了解源码语义后立即调用代码生成器生成目标代码或中间代码，因此这也是和语法分析器并行。

提醒一下，并不是在语法分析器分析完整个源码后，再一次性地生成整个源码对应的目标代码或中间代码，而是分析一部分源码后就立即生成该部分源码对应的目标代码或中间代码，这样做比较高效且更容易实现。

举个例子，比如源码文件中有10行代码，语法分析器不断调用词法分析器，每次获得一个单词的token，把前3行源码都读完后确定了源码的语义，立即生成与这3行源码同等意义的目标代码或中间代码。

然后语法分析器继续调用词法分析器读取第4行之后的源码，重复分析语法、生成代码的过程。总之是以语法分析为主线，语法分析把源码按照语法来拆分成多个小部分，每次生成这一小部分的目标代码或中间代码。

总结，为了使编译更加高效，词法分析、语法分析、语义分析和生成代码是以语法分析为中心并行执行的，词法分析和生成代码都是被语法分析器调用的子例程。

什么是符号表

把符号表列出来是因为这个词听上去“挺唬”人的，由于看不见摸不着，很多初学者都以为它是个非常神秘的东西。其实符号表就是存储符号的表，就是这么简单。

你想，源码中的那些符号总该存储在某个地方，这样在引用的时候才能找得到，因此符号表的用途就是记录文件中的符号。符号包括字符串、方法名、变量名、变量值等。符号放在表中的另一个重要原因是便于生成指令，使指令格式统一。

编译器会把符号在符号表中的索引作为指令的操作数，如果不用索引的话，指令就会很乱，比如若直接用函数名或字符串作为操作数，指令就冗长了。“表”在计算机中并不专指“表格”，“表”是个笼统的概念，用以表示一切可供增、删、改、查的数据结构，因此符号表可以用任何结构来实现，比如链表、散列表、数组等。

《自制编程语言》

郑钢著

本书全面从脚本语言和虚拟机介绍开始，讲解了词法分析的实现、一些底层数据结构的实现、符号表及类的结构符号表，常量存储，局部变量，模块变量，方法存储、虚拟机原理、运行时栈实现、编译的实现、语法分析和语法制导自顶向下算符优先构造规则、调试、查看指令流、查看运行时栈、给类添加更多的方法、垃圾回收实现、添加命令行支持命令行接口。