动手实现

之前章节介绍了编译原理基础知识，并定义了两个最重要的概念字节码ByteCode和值Value。接下来就可以动手编码实现我们的解释器了！

这系列文章对应的代码全部使用Rust自带的Cargo来管理。目前采用二进制类型的项目，后续会改成库类型。

目前要实现的极简解释器是非常简单的，代码很少，我当初也是把代码都写在一个文件里。不过可以预见的是，这个项目的代码量会随着功能的增加而增加。所以为了避免后续再拆文件的改动，我们直接创建多个文件：

  • 程序入口：main.rs；
  • 三个组件：词法分析 lex.rs、语法分析 parse.rs、和虚拟机 vm.rs；
  • 两个概念：字节码 byte_code.rs、值value.rs。

后面的两个概念和其代码之前已经介绍了。下面介绍其他4个文件。先从程序入口开始。

程序入口

简单起见，我们的解释器只有一种工作方式，即接受一个参数作为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源文件。

中间几行通过use引用其他文件的模块。

然后看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的栈来传递。而我们目前没有类似的统一的状态数据结构，所以只能先分别调用解析和执行两部分的功能。

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

词法分析

虽然上面的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
    }
}

语法分析

上面main()函数中的解析结果proto是解析和执行两个过程的中间纽带。但是鉴于Rust强大的类型机制，在上述代码中proto并没有展示出具体的类型。现在来看其类型定义。在字节码一节中已经介绍过，解析结果需要包含2部分：字节码序列和常量表。于是可以定义解析结果的格式如下：

#[derive(Debug)]
pub struct ParseProto {
    pub constants: Vec::<Value>,
    pub byte_codes: Vec::<ByteCode>,
}

常量表constants是包含Value类型的Vec，字节码序列byte_codes是包含ByteCode类型的Vec。他们都是Vec结构，具有相同的功能，但包含类型不一样。在古老的C语言里要包含Value和ByteCode这两种类型，要么针对每种类型都编写一套代码，要么就要用到宏或函数指针等复杂特性。Rust语言中的泛型就可以针对不同类型抽象出同一套逻辑。后续代码中会用到泛型的更多特性。

在定义好ParseProto后，接下来看语法分析流程。我们目前只支持print "hello, world!"这一个类型的语句，也就是Name String的格式。首先从词法分析中读取Name，然后再读取字符串常量。如果不是这个格式则报错。具体代码如下：

pub fn load(input: File) -> ParseProto {
    let mut constants = Vec::new();
    let mut byte_codes = Vec::new();
    let mut lex = Lex::new(input);

    loop {
        match lex.next() {
            Token::Name(name) => { // `Name LiteralString` as function call
                constants.push(Value::String(name));
                byte_codes.push(ByteCode::GetGlobal(0, (constants.len()-1) as u8));

                if let Token::String(s) = lex.next() {
                    constants.push(Value::String(s));
                    byte_codes.push(ByteCode::LoadConst(1, (constants.len()-1) as u8));
                    byte_codes.push(ByteCode::Call(0, 1));
                } else {
                    panic!("expected string");
                }
            }
            Token::Eos => break,
            t => panic!("unexpected token: {t:?}"),
        }
    }

    dbg!(&constants);
    dbg!(&byte_codes);
    ParseProto { constants, byte_codes }
}

输入是源文件File，输出是刚才定义的ParseProto。

函数主体是个循环，通过在函数开头创建的词法分析器lex提供的next()函数，循环读取Token。我们目前只支持一种类型的语句，即Name LiteralString，并且语义是函数调用。所以分析逻辑也很简单：

  • 遇到Name，认为是语句开始：
    • 把Name作为全局变量，存入常量表中；
    • 生成GetGlobal字节码，把根据名字把全局变量加载到栈上。第1个参数是目标栈索引，由于我们目前只支持函数调用语言，栈只用来函数调用，所以函数一定是在0的位置；第2个参数是全局变量名在全局变量中的索引；
    • 读取下一个Token，并预期是字符串常量，否则panic；
    • 把字符串常量加入到常量表中；
    • 生成LoadConst字节码，把常量加载到栈上。第1个参数是目标栈索引，排在函数的后面，为1；第2个参数是常量在常量表中的索引；
    • 准备好了函数和参数，就可以生成Call字节码，调用函数。目前2个参数，分别是函数位置和参数个数，分别固定为0和1。
  • 遇到Eos，退出循环。
  • 遇到其他Token（目前只能是Token::String类型），则panic。

函数后面通过dbg!输出常量表和字节码序列，用于调试。可以跟luac的输出做对比。

最后返回ParseProto。

虚拟机执行

解析生成ParseProto后，就轮到虚拟机执行了。按照之前分析，虚拟机目前需求2个组件：栈和全局变量表。所以定义虚拟机状态如下：

pub struct ExeState {
    globals: HashMap<String, Value>,
    stack: Vec::<Value>,
}

创建虚拟机时，需要提前在全局变量表里添加print函数：

impl ExeState {
    pub fn new() -> Self {
        let mut globals = HashMap::new();
        globals.insert(String::from("print"), Value::Function(lib_print));

        ExeState {
            globals,
            stack: Vec::new(),
        }
    }

其中print函数的定义如下：

// "print" function in Lua's std-lib.
// It supports only 1 argument and assumes the argument is at index:1 on stack.
fn lib_print(state: &mut ExeState) -> i32 {
    println!("{:?}", state.stack[1]);
    0
}

目前print函数只支持一个参数，并假设这个参数在栈的1位置。函数功能就是打印这个参数。因为这个函数不需要向调用者返回数据，所以返回0。

完成初始化后，下面就是最核心的虚拟机执行功能，也就是字节码分发的大循环：依次读取字节码序列并执行对应的预定义功能。具体代码如下：

    pub fn execute(&mut self, proto: &ParseProto) {
        for code in proto.byte_codes.iter() {
            match *code {
                ByteCode::GetGlobal(dst, name) => {
                    let name = &proto.constants[name as usize];
                    if let Value::String(key) = name {
                        let v = self.globals.get(key).unwrap_or(&Value::Nil).clone();
                        self.set_stack(dst, v);
                    } else {
                        panic!("invalid global key: {name:?}");
                    }
                }
                ByteCode::LoadConst(dst, c) => {
                    let v = proto.constants[c as usize].clone();
                    self.set_stack(dst, v);
                }
                ByteCode::Call(func, _) => {
                    let func = &self.stack[func as usize];
                    if let Value::Function(f) = func {
                        f(self);
                    } else {
                        panic!("invalid function: {func:?}");
                    }
                }
            }
        }
    }

现在只支持3个字节码。每个功能都很明确，无须多言。

测试

至此，我们实现了一个完整流程的Lua解释器！看下运行效果：

$ cargo r -q -- test_lua/hello.lua
[src/parse.rs:39] &constants = [
    print,
    hello, world!,
]
[src/parse.rs:40] &byte_codes = [
    GetGlobal(
        0,
        0,
    ),
    LoadConst(
        1,
        1,
    ),
    Call(
        0,
    ),
]
hello, world!

输出分3部分。第1部分是常量表，包含2个字符串常量。第2部分是字节码，可以跟字节码一节里的luac的输出对比下。最后1行就是我们期待的结果：hello, world!

还有个额外的功能。语法分析部分并非只支持一条语句，而是一个循环。所以我们可以支持多条print语句，比如：

print "hello, world!"
print "hello, again..."

执行会发现有个小问题，就是在常量表里print出现了两次。这里可以优化为，每次向常量表里添加值时可以先判断是否已经存在。在下一章处理。

总结

本章的目的是实现一个完整流程的Lua解释器，以熟悉解释器结构。为此，我们首先介绍了编译原理基础知识，然后介绍了Lua的字节码和值这两个核心概念，最后编码实现！

我们一直在强调“完整流程”，是因为后续只需要基于这个框架上，加上亿点点细节，就能完成一个“完整功能”的Lua解释器。继续前行。