前言

出于学习的目的，想通过从头实现Lua解释器的方式来对Lua有更深入的了解。正好学习Rust也有段时间了，于是找了份用Rust实现Lua的教程，动手实现一下。这个系列的文章将基本是学习这篇教程的课程笔记。

01-Hello, world!

这节的目标是实现一个简单的，只能解析print "Hello, world!"这样只有两个Token的简单语句的解释器。虽然简单，但是完整的包含了一个Lua解释器需要的词法分析生成Token流、语法分析生成字节码（没有生成抽象语法树的环节）、虚拟机执行字节码三个部分。

词法解析生成Token流

数据结构定义

• Token

  用来表示Lua的词法单元，在官方的C实现中，Token是一个结构体（见llex.h中定义的Token），包括一个表明token类型的int值和token语法信息的SemInfo。在Rust中，这个结构可以用TagedUnion，即SumType实现。教程里Token::Ident(String)叫做Token::Name(String)，从含义上感觉叫Ident更合适一点，也对应Rust宏里的片段类型ident。

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

• Lexer

  对应官方C实现中的LexState，但是考虑我们当前只需要实现一条简单的语句，所以不用太复杂，定义如下。包含一个类型别名type LexerBytes = Peekable<Bytes<File>>;，教程里，这里是一个std::fs::File类型的字段表示输入文件，此处做简单预处理，转成u8类型的迭代器。

  pub struct Lexer {
      bytes: LexerBytes
  }

  算法实现

  使用DFA（确定有限状态自动机），读取代码文件字节流，以字节为单位，逐个ASCII字符匹配Token。见Lexer的next方法。

  pub fn next(&mut self) -> Token {
    loop {
        let next_byte = self.bytes.next();
        match next_byte {
            Some(Ok(byte)) => {
                match byte as char {
                  // TLDR, DFA.
                }
            },
            Some(Err(e)) => panic!("Error reading token: {}", e),
            _ => break Token::Eos
        }
    }
  }

  或许这里可以返回一个Iterator<Item = Token>类型的迭代器?

语法分析生成字节码

数据结构定义

• ByteCode

  Lua官方的实现是用32位的无符号整数表示一个字节码，前7位是op类型，即最多128种字节码，后25位作为参数，按位划分成了5种格式。而LuaJit则使用了更简单的字节码格式，同样是使用32位无符号整数，以字节位最小的单位，划分了2种格式。在Rust里，我们用TagedUnion来表示字节码，和LuaJit一样，字节是最小的控制单位。代码如下，值得一提的是，当前只有3种字节码，ByteCode的大小为3字节即24位。

  #[derive(Debug)]
  pub enum Bytecode {
      GetGlobal(u8, u8),
      LoadConst(u8, u8),
      Call(u8, u8)
  }

• Value

  Lua是动态类型语言，类型与值绑定，也就意味着从底层看，Lua的每种值都是同一种类型。在C中，可以用union这种数据结构来表示（见lobject.h中定义的Value），在Rust中，同样可以用TagedUnion轻松的实现这一点（暴论：所有语言都应该有SumType）。定义如下，当前只包括三种值，或者说实现print "Hello, world!"只需要这三种值。

  #[derive(Clone)]
  pub enum Value {
      Nil,
      String(String),
      Function(fn (&mut ExeState) -> i32),
  }

• Parser

  负责语法分析，用Token流生成字节码，同时记录常量值等必要的语法信息。在官方实现中，可以从lua.c中的doREPL函数开始，逐层深入lparser.c中的statement和expr函数，东西很多，但这里我们只需要最简单的逻辑，毕竟我们的目标也很简单。定义中包括constants和bytecodes两个字段，分别存放从Token流中记录的常量和解析出的字节码。

  pub struct Parser {
      pub constants: Vec<Value>,
      pub bytecodes: Vec<Bytecode>
  }

  算法实现

  采用自顶向下的方法，因为这节要实现的逻辑很简单，不多赘述。见Parser的load方法。

  pub fn load(mut lexer: Lexer) -> Self {
    let mut constants = Vec::new();
    let mut bytecodes = Vec::new();
  
    loop {
        match lexer.next() {
            Token::Ident(ident) => {
                constants.push(Value::String(ident));
                bytecodes.push(Bytecode::GetGlobal(0, (constants.len(- 1) as u8));
  
                if let Token::String(s) = lexer.next() {
                    constants.push(Value::String(s));
                    bytecodes.push(Bytecode::LoadConst(1, (constantlen() - 1) as u8));
                    bytecodes.push(Bytecode::Call(0, 1));
                } else {
                    panic!("Expected string after ident.");
                }
            }
            Token::Eos => break,
            _ => panic!("Unexpected token.")
        }
    }
  
    Self { constants, bytecodes }
  }

虚拟机执行字节码

数据结构定义

• ExeState

  包含虚拟机的状态和执行逻辑，参考lstate.h中定义的lua_State，此处只包含两个字段globals和stack，分别用于保存全局变量和用作函数执行栈。

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

  算法实现

  逐字节码执行对应逻辑，实现简单的参数入栈函数调用逻辑。官方的完整实现在lvm.c的luaV_execute函数。当前实现见ExeState`execute`方法。

  pub fn execute(&mut self, proto: &Parser) {
    for bytecode in &proto.bytecodes {
        match *bytecode {
            Bytecode::GetGlobal(stack_dst, const_idx) => {
                match &proto.constants[const_idx as usize] {
                    Value::String(key) => {
                        let global_value = self.globals.get(key).unwrap_or(&Value::default()).clone();
                        self.set_stack(stack_dst, global_value);
                    },
                    unknown => panic!("Unexpected global key: {:?}", unknown)
                };
            },
            Bytecode::LoadConst(stack_dst, const_idx) => {
                let const_value = proto.constants[const_idx as usize].clone();
                self.set_stack(stack_dst, const_value);
            },
            Bytecode::Call(func, _) => {
                let func = &self.stack[func as usize];
                match func {
                    Value::Function(f) => {
                        f(self);
                    },
                    unknown => panic!("Expected function: {:?}", unknown)
                }
            }
        }
    }
  }

小结

本章搭建了一个简单但相对完整的，可以解释执行print "Hello, world!"的Lua解释器。内容简单明了，Lua的官方源码虽然不多，但是一次性全部掌握还是比较困难。后面跟着教程循序渐进，会逐渐深入Lua的实现细节。
本节代码：01-Hello,world!