ExpDesc概念

在介绍表的读写之前，本节先引入ExpDesc这个语法分析的核心数据结构。

表构造的问题

上一节实现的表的构造存在一个性能问题。比如，对于通用式[ exp ] = exp，会依次把key和value对应的表达式通过load_exp()函数加载到栈顶，作为临时变量；然后再生成SetTable字节码，包含栈顶的两个临时变量的索引。代码如下：

    Token::SqurL => { // `[` exp `]` `=` exp
        nmap += 1;
        self.lex.next();

        self.load_exp(sp); // 加载key到栈顶
        self.lex.expect(Token::SqurR); // `]`
        self.lex.expect(Token::Assign); // `=`
        self.load_exp(sp + 1); // 加载value到栈顶

        self.byte_codes.push(ByteCode::SetTable(table, sp as u8, sp as u8 + 1));
    },

这就造成了浪费，因为某些表达式类型，比如局部变量、临时变量和常量，都可以直接引用，而无需加载到栈上。比如下面的Lua代码：

local k = 'kkk'
local v = 'vvv'
local t = { [k] = v }

按照现在的实现方式，运行时的栈和字节码序列如下：

    +---------+
  0 |  "kkk"  |---\[1] Move 3 0
    +---------+   |
  1 |  "vvv"  |---|-\[2] Move 4 1
    +---------+   | |
  2 |   { }   |<--|-|---------\
    +---------+   | |         |
  3 |  "kkk"  |<--/ |   --\   |
    +---------+     |      >--/[3] SetTable 2 3 4
  4 |  "vvv"  |<----/   --/
    +---------+
    |         |

而实际上这两个临时变量都不需要，而是只需要1条字节码即可：SetTable 2 0 1，其中的3个参数分别是表、key和value在栈上的索引。这也是Lua官方实现的方式，即尽量直接引用索引，而避免无谓的临时变量。运行时的栈和字节码序列如下：

    +---------+
  0 |  "kkk"  |---\
    +---------+    >--\[1] SetTable 2 0 1
  1 |  "vvv"  |---/   |
    +---------+       |
  2 |   { }   |<------/
    +---------+
    |         |

这两种方式（是否引入临时变量）对应虚拟机的两种类型，基于栈的和基于寄存器的。

基于栈和基于寄存器

先罗列一下上面例子中，现在实现方式的字节码：

Move 3 0  # 把k加载到3位置。此时3是栈顶
Move 4 1  # 把v加载到4位置。此时4是栈顶
SetTable 2 3 4

在现在的实现方式中，我们可以确定key和value是要加载到栈顶，所以两条Move字节码中的第一个参数（即目标地址）是可以省略的；另外我们也可以确定在设置表时，key和value一定在栈顶，所以SetTable字节码的后面两个参数也是可以省略的。所以字节码序列可以简化如下：

Push 0   # 把k加载到栈顶
Push 1   # 把v加载到栈顶
SetTable 2  # 把栈顶的两个值作为key和value，设置给2位置的表

这种通过栈顶来操作参数的方式，称为基于栈的虚拟机。很多脚本语言如Java、Python等的虚拟机都是基于栈的。而在字节码中直接索引参数的方式（比如SetTable 2 0 1），称为基于寄存器的虚拟机。这里的“寄存器”并不是计算机CPU中的寄存器，而是一个虚拟的概念，比如在我们的Lua解释器中，就是用栈和常量表来实现的寄存器。Lua是第一个（官方的虚拟机）基于寄存器的主流语言。

上面是通过表的写语句作为例子。下面再介绍一个更容易理解的例子，即加法语句（虽然我们现在还没有实现加法，但确实更容易理解）。对于如下Lua代码：

local r
local a = 1
local b = 2
r = a + b

基于栈的虚拟机生成的字节码可能如下：

Push 1  # 把a加载到栈顶
Push 2  # 把b加载到栈顶
Add     # 把栈顶的2个数弹出并相加，并把结果压到栈顶
Pop 0   # 把栈顶的结果弹出，并赋值给r

基于寄存器的虚拟机生成的字节码可能如下：

Add 0 1 2

可以直观地看到，基于寄存器虚拟机的字节码序列，条数少，但每条字节码更长。一般认为基于寄存器的字节码性能略优，但实现较复杂。这两种类型更详细的说明和比较已经超出本文讨论范围，并且我也没能力介绍。我之所以在这个项目里选择了基于寄存器，仅仅是因为Lua官方实现就是这么做的。我甚至是项目写了一部分后，才知道有这两种方式。接下来只要继续按照基于寄存器的方式即可，而不去纠结基于栈的方式。

需要说明的一点是，基于寄存器的方式，也只是尽量避免使用栈顶的临时变量。在必要的时候也是需要的。如何选择寄存器还是临时变量，这一点在后面会详细介绍。

中介ExpDesc

既然我们要按照基于寄存器方式，但为什么上一节表的构造里，要把key和value都加载到栈顶，使用基于栈的方式呢？是因为我们目前还无法实现基于寄存器的方式。现在load_exp()函数在遇到Token后，是直接生成字节码加载到栈的指定位置的。代码如下：

    fn load_exp(&mut self, dst: usize) {
        let code = match self.lex.next() {
            Token::Nil => ByteCode::LoadNil(dst as u8),
            Token::True => ByteCode::LoadBool(dst as u8, true),
            Token::False => ByteCode::LoadBool(dst as u8, false),
            Token::Float(f) => self.load_const(dst, f),
            Token::String(s) => self.load_const(dst, s),
            // 省略其他Token
        };
        self.byte_codes.push(code);
    }

所以在解析上面的表的通用式写语句时，遇到key和value的表达式时，就立即加载到栈顶了，就成为了基于栈的方式。

而如果要实现基于寄存器方式，生成SetTable 2 0 1这样的字节码，那在遇到key或value的表达式时，就不能立即生成字节码，而是需要暂时保存起来，等待时机成熟时，再按情况处理。还是用本节开头的Lua代码为例：

local k = 'kkk'
local v = 'vvv'
local t = { [k] = v }

第3行的表构造语句，解析过程如下：

  • [，确定为通用式；
  • k，作为Name，先确定是局部变量，索引是0，然后作为key保存起来；
  • ]和=，预期中；
  • v，作为Name，也确定是局部变量，索引是1，然后作为value保存起来；
  • 此时，一条初始化语句完成，之前保存的key和value的索引分别是0和1，于是就可以生成字节码SetTable 2 0 1。

这里的关键是“把key/value保存起来”。我们现在就要增加这种暂存的机制。一个解决方法是直接保存读到的Token。比如这个例子中，key和value分别保存为Token::Name("k")和Token::Name("v")。但这样做有几个问题：

  • 一个小问题是Name可能是局部变量或者全局变量，我们后续会看到对这两种变量的处理方式是不一样的，而用Token::Name无法区分这两个类型。
  • 稍大的问题是，有的表达式是更复杂的，不止包含一个Token，比如t.k、a+1、foo()等，这些不能用一个Token来代表。这一章支持表，就要支持t.k甚至t.k.x.y这种表达式语句。
  • 更大的问题是，表的读语句t.k至少还可以用基于栈的方式来实现，但表的写语句就不行了。比如t.k = 1，就是赋值语句的左边部分，在解析时，必须要先保存起来，然后再解析右值表达式，最后再执行赋值。要支持表的写语句，就必须先增加这种暂存的机制。这也是在接下来支持表的读写功能之前，必须要先插入这一节的原因。

所以，我们需要一种新类型来保存中间结果。为此我们引入ExpDesc（名字来自Lua官方实现代码）：

#[derive(Debug, PartialEq)]
enum ExpDesc {
    Nil,
    Boolean(bool),
    Integer(i64),
    Float(f64),
    String(Vec<u8>),
    Local(usize), // on stack, including local and temprary variables
    Global(usize), // global variable
}

现在看上去其类型，就是表达式目前支持的类型，只是把Token::Name拆成了Local和Global，为此引入这个类型有点小题大做。但在下一节支持表的读写时，以及后续的运算表达式、条件跳转等语句时，ExpDesc就会大显身手！

原来的解析过程是从Token直接生成字节码：

    Token::Integer  ->  ByteCode::LoadInt
    Token::String   ->  ByteCode::LoadConst
    Token::Name     ->  ByteCode::Move | ByteCode::GetGlobal
    ...

现在中间增加了ExpDesc这层，解析过程就变成：

    Token::Integer  ->  ExpDesc::Integer  ->  ByteCode::LoadInt
    Token::String   ->  ExpDesc::String   ->  ByteCode::LoadConst
    Token::Name     ->  ExpDesc::Local    ->  ByteCode::Move
    Token::Name     ->  ExpDesc::Global   ->  ByteCode::GetGlobal
    ...

语义分析和ExpDesc

ExpDesc是非常重要的，这里换个角度再介绍一次。

第1.1节基础的编译原理中介绍了通用的编译流程：

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

我们仍然用上面的加法代码来举例：

local r
local a = 1
local b = 2
r = a + b

按照上述通用编译流程，对于最后一行的加法语句，语法分析会得到语法树：

    |
    V
    +
   / \
  a   b

然后在语义分析时，先看到+，得知这是一条加法的语句，于是可以很直接地生成字节码：Add ? 1 2。其中?是加法的目标地址，由赋值语句处理，这里忽略；1和2分别是两个加数的栈索引。

但我们目前的做法，也是Lua官方实现的做法，是省略了“语义分析”这一步，从语法分析直接生成中间代码，边分析边生成代码。那么在语法分析时，就不能像上述语义分析那样有全局的视角。比如对于加法语句a+b，在读到a时，还不知道这是一条加法语句，只能先存起来。读到+时才确定是加法语句，然后再读第二个加数，然后生成字节码。我们为此引入了ExpDesc这个中间层。所以ExpDesc就相当于是通用流程中的“语法树”的作用。只不过语法树是全局的，而ExpDesc是局部的，而且是最小粒度的局部。

       词法分析               语法分析
字符流 --------> Token流 ----(ExpDesc)---> 中间代码 ...

可以直观地看到，Lua的这种方式省去了语义分析步骤，速度应该略快，但由于没有全局视角，所以实现相对复杂。这两种方式更详细的说明和对比已经超出了本文的讨论范围。我们选择按照Lua官方实现的方式，选择语法分析直接生成字节码的方式。

小结

本节引入了ExpDesc的概念，并介绍了其作用和角色。下一节，基于ExpDesc对现有代码做改造。