编译原理

编译原理是一门很精深也很成熟的学科，这里没必要也没能力做完整或准确的介绍，只是按照后续实现的流程做些简单的概念介绍。

编译型和解释型

无论什么编程语言，源代码在交给计算机执行之前，必然需要一个翻译的过程，以把源代码翻译成计算机可执行的语言。按照这个翻译的时机，编程语言大致可以分为2种：

• 编译型，即编译器先将源代码编译成计算机语言，并生成可执行文件。后续由计算机直接执行此文件。比如在Linux下，用编译器gcc把C语言源码编译为可执行文件。
• 解释型，则需要一个解释器，实时地加载并解析源程序，然后将解析的结果对应到预先编译的功能并执行。这个解释器一般是由上面的编译型语言实现。

  +-------+  编译   +----------+           +---------+  解析并执行   +----------+
  | 源代码 | -----> | 可执行文件 |           |  源代码  | ----------> | Lua解释器 |
  | bar.c |        |  bar.exe |           | bar.lua |             |  lua.exe |
  +-------+        +----------+           +---------+             +----------+
                        ^                                               ^
                        |执行机器指令                                     |执行机器指令
                        |                                               |
                  +-------------+                                 +-------------+
                  |    计算机    |                                 |    计算机    |
                  +-------------+                                 +-------------+

                编译型                                    解释型

上图大致展示了两种类型的翻译和执行过程。Lua属于解释型语言，我们的目标也是要实现Lua解释器，所以下面只介绍这个类型。在此之前先明确几个名词的含义：

• 编译（compile），这个名词的含义有点乱。广义上可以指任何将程序从一种计算机程序语言转换到另一种语言计算机语言的过程，比如“编译原理”这个词中的编译，再比如把Lua的源码转换为字节码的过程也可以认为是编译。狭义上特指上述的第一种类型，跟“解释型”相对。再狭义些，特指上述编译型过程的某个阶段，跟预处理、链接等过程并列。本文后续尽量避免使用这个名词。
• 解释（interpret），特指上述的第二种编译类型，跟“编译型”相对。
• 解析，是个笼统的概念，而非编译原理的专有名词。可指任何形式的转换，比如理解源码的语义，再比如把字符串解析为数字等。
• 翻译，对应编译的最广义的概念。
• 分析，这个词本身是个笼统的概念，但“词法分析”和“语法分析”是编译原理中的专有名词。

解析和执行

一般编译原理教程上介绍的编译过程如下：

       词法分析           语法分析         语义分析
字符流 --------> Token流 --------> 语法树 --------> 中间代码 ...

• 其中字符流对应源代码，即把源代码作为字符流来处理。
• 词法分析，把字符流拆为语言支持的Token。比如上述Lua代码就拆为“标识print”和“字符串"hello, world!"”两个Token。Lua是忽略空白字符的。
• 语法分析，把Token流按照语法规则，解析为语法树。比如刚才的2个Token被识别为一条函数调用语句，其中“标识print”是函数名，“字符串"hello, world!"”是参数。
• 语义分析，把这条函数调用的语句生成对应的中间代码，这些代码指示从哪里查找函数体，把参数加载到什么位置等具体功能。

生成中间代码之后，编译型和解释型语言就分道扬镳。编译型继续前进，最终生成可以直接执行的机器码，并包装为可执行文件。而对于解释型语言到此就告一段落，生成的中间代码（一般称为字节码）就是编译的结果；而字节码的执行就是虚拟机的任务了。

虚拟机把字节码转换为对应的一系列预先编译好的功能，然后执行这些功能。比如执行上述生成的字节码，虚拟机会首先找到对应的函数，即print，是Lua标准库里的函数；然后加载参数，即"hello, world"；最后调用print函数。这个函数也是预先编译好的，其功能是打印参数。这就最终完成了输出"hello, world!"的功能。

上述只是一般流程。具体到每个语言或者每个解释器流程可能有所不同。比如有的解释器可能不生成字节码，而是让虚拟机直接执行语法树。而Lua的官方实现则是省略了语法树，由语法分析直接生成字节码。这些选择各有优劣，但已超出我们的主题范围，这里不做讨论。我们的解释器在主流程上是完全参考的Lua官方实现，所以最终的流程如下：

       词法分析           语法分析
字符流 --------> Token流 --------> 字节码
                                    ^
                                    |
                                  虚拟机

由此可以明确我们的解释器的主要功能组件：词法分析、语法分析和虚拟机。可以把词法分析和语法分析合并称为“解析”过程，而虚拟机是“执行”的过程，那么字节码就是连接这两个过程的纽带。解析和执行两个过程相对独立。接下来我们就以字节码作为突破口，开始实现我们的解释器。