编译原理以及"hello world!"实现

编译原理

编译型和解释型

无论什么编程语言，源代码在交给计算机执行之前，必然需要一个翻译的过程，以把源代码翻译成计算机可执行的语言。按照这个翻译的时机，编程语言大致可以分为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流 --------> 字节码
                                    ^
                                    |
                                  虚拟机

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

字节码

作为一个小白，要实现一个解释器，开始自然是一头雾水，无从下手。

好在上一节最后介绍了字节码，把整个解释器流程分为解析和执行两个阶段。那么我们就可以从字节码入手：

• 先确定字节码，
• 然后让解析过程（词法分析和语法分析）努力生成这套字节码，
• 再让执行过程（虚拟机）努力执行这套字节码。

          生成             执行
    解析 -------> 字节码 <------- 虚拟机

但字节码长什么样？如何定义？有什么类型？可以先参考Lua的官方实现。

luac的输出

为方便叙述，这里再次列出目标代码：

print "hello, world!"

Lua官方实现自带一个非常好用的工具，luac，即Lua Compiler，把源代码翻译为字节码并输出。是我们这个项目的最得力助手。看下其对"hello, world!"程序的输出：

$ luac -l hello_world.lua

main <hello_world.lua:0,0> (5 instructions at 0x600000d78080)
0+ params, 2 slots, 1 upvalue, 0 locals, 2 constants, 0 functions
    1	[1]	VARARGPREP	0
    2	[1]	GETTABUP 	0 0 0	; _ENV "print"
    3	[1]	LOADK    	1 1	; "hello, world!"
    4	[1]	CALL     	0 2 1	; 1 in 0 out
    5	[1]	RETURN   	0 1 1	; 0 out

动手实现

程序入口main.rs

简单起见，我们的解释器只有一种工作方式，即接受一个参数作为Lua源码文件，然后解析并执行。代码如下：

use std::env;
use std::fs::File;

mod value;
mod bytecode;
mod lex;
mod parse;
mod vm;

fn main() {
    let args: Vec<String> = env::args().collect();
    if args.len() != 2 {
        println!("Usage: {} script", args[0]);
        return;
    }
    let file = File::open(&args[1]).unwrap();

    let proto = parse::load(file);
    vm::ExeState::new().execute(&proto);
}

开头2行引用了两个标准库。env用于获取命令行参数。fs::File用来打开Lua源文件。

然后看main()函数。前面几行是读取参数并打开源文件。在打开源文件时使用了unwrap()，如果打开失败则终止程序。简单起见，接下来几章对所有错误的处理方式都是直接终止程序，之后再统一引入规范的错误处理。

最后2行是核心功能：

• 首先语法分析模块parse（内部调用词法分析lex）解析文件，并返回解析结果proto；
• 然后创建一个虚拟机，并执行proto。

这个流程跟Lua官方实现的API调用方式不一样。Lua官方实现的主要流程如下（完整示例）：

lua_State *L = lua_open();   // 创建lua_State
luaL_loadfile(L, filename);  // 解析，并把解析结果放在栈顶
lua_pcall(L, 0, 0, 0);       // 执行栈顶

这是因为Lua官方实现是“库”，API对外只暴露lua_State这一个数据结构，负责解析和执行两部分的功能，所以要先创建lua_State，再以其为基础去调用解析和执行，解析结果也是通过Lua_state的栈来传递。而我们目前没有类似的统一的状态数据结构，所以只能先分别调用解析和执行两部分的功能。

下面分别看解析和执行过程。

词法分析lex.rs

虽然上面的main()函数里是直接调用的语法分析parse模块，但语法分析内部是调用了词法分析lex模块。先看词法分析。

词法分析的输出是Token流。对于"hello, world!"程序，只需用到“标识print”和“字符串"hello, world!"”这两个Token，简单起见我们也暂时只支持这两个。另外我们还定义一个Eos用于表示文件结束：

#[derive(Debug)]
pub enum Token {
    Name(String),
    String(String),
    Eos,
}

我们并没有一次性把输入文件解析完毕，返回一个Token数组，而是提供一个类似迭代器的功能，以便让语法分析模块按需调用。为此先定义一个词法分析器：

#[derive(Debug)]
pub struct Lex {
    input: File,
}

现在暂时只包含一个成员，即输入文件。

对外提供2个API：new()基于输入文件创建语法分析器；next()返回下一个Token。

impl Lex {
    pub fn new(input: File) -> Self ;
    pub fn next(&mut self) -> Token ;
}

具体的解析过程就是单纯的字符串处理了，代码略过。

按照Rust的惯例，这里的next()函数的返回值应该是Option<Token>类型，Some<Token>表示读到新Token，None表示文件结束。但是既然Token本身就是一个enum了，直接在里面加入一个Eos似乎更方便些。而且如果改成Option<Token>类型，那么在下一次语法分析调用的地方，也会需要多一层判断，如下代码。所以还是选择了新增Eos类型。

loop {
    if let Some(token) = lex.next() {  // extra check
        match token {
            ... // parse
        }
    } else {
        break
    }
}