探索Lua5.2内部实现:编译系统(3) 表达式
最后更新于：2022-04-01 07:09:59
# 探索Lua5.2内部实现:编译系统(3) 表达式
表达式(expression)在编程语言中代表一个可以返回值的语法单位，比如常量表达式，变量表达式，函数调用表达式，算术、关系和逻辑表达式等等。对于函数式编程语言来说，几乎所有的语句都是表达式，可以被估值。而对于命令式语言，一般会将语句分成表达式和陈述语句(statement)。表达式可以被估值，而普通的陈述语句用来执行命令。根据具体的语法，这两种类型不一定会有明确的界限。比如在C中，a = b既是一个用来赋值的陈述语句，又是一个表达式，而作为表达式的结果是最终的a值。所以，像c = a = b这样的语句是成立的，意思是将a = b作为表达式，并将值赋给c。
而在Lua中，表达式的描述要明确的多。a = b属于一个赋值statement，而不属于表达式，所以c = a = b会产生语法错误。唯一即可以当作expression又可以当作statement使用的就是call。call本身会调用函数，返回函数的返回值，而作为statement时，返回值被忽略。
根据Lua5.2完整的[BNF](http://www.lua.org/manual/5.2/manual.html#9)，我们可以看到Lua中仅有以下地方需要使用表达式：
* 变量赋值，等号左边必须是一个变量表达式，右边是一个任意表达式
* 局部变量的初始化，等号右边是任意表达式
* if statement的条件表达式和循环的条件表达式
在需要表达式的地方，通过调用expr函数，并传入一个expdesc结构体对象，对表达式进行解析。表达式的解析是一个递归下降的过程。下降分析将高层的表达式分解成底层表达式或表达式的组合，而递归则发生在expr函数的递归调用上，也就是说在解析过程中还会用表达式本身来描述高层表达式。当解析到BNF的终结符时，会返回上一层处理，然后再一层层的处理后返回。expr函数最终会填充传入的expdesc结构体，作为最高层的根表达式，交给更高层的语义，也就是上面需要表达式的地方进行处理。
Lua关于递归下降分析的每个函数的注释中都有代表这个函数的BNF范式，我们可以很容易的浏览这些代码，不需要过多的解释。真正需要理解的是表达式与指令生成相关的部分，这也是整个Lua编译系统里面比较晦涩的地方。我们可以首先通过一个简单的例子，在宏观上了解一下语法分析和指令生成的全过程。
对于下面的chunk
` c = a.b + 1 `
我们最终可以生成如下指令
~~~
main (5 instructions at 0x80048eb8)
0+ params, 2 slots, 1 upvalue, 0 locals, 4 constants, 0 functions
1 [1] GETTABUP 0 0 -2 ; _ENV "a"
2 [1] GETTABLE 0 0 -3 ; "b"
3 [1] ADD 0 0 -4 ; - 1
4 [1] SETTABUP 0 -1 0 ; _ENV "c"
5 [1] RETURN 0 1
constants (4) for 0x80048eb8:
1 "c"
2 "a"
3 "b"
4 1
locals (0) for 0x80048eb8:
upvalues (1) for 0x80048eb8:
0 _ENV 1 0
~~~
整个的递归下降语法分析过程可以用下图表示。
由于我们目前需要讲解的是表达式，这里为了讲解方便，这里省略了一些过程。接下来我们对这些步骤逐一进行解说。
1. exprstat函数调用suffixedexp函数，对赋值语句的左边的后缀表达式进行分析。
2. 这里没有展开suffixedexp函数，我们目前只需要知道它会返回一个VINDEXED表达式。
3. exprstat调用expr函数，对赋值右面的表达式进行分析。如上所述，expr函数是解析表达式的总入口，他接受一个expdesc结构体，开始分析。
4. expr调用subexpr
5. subexpr函数首先调用simpleexp，来分析“+”号左边的表达式。
6. simpleexp调用suffixedexp函数，将这个表达式当成后缀表达式开始分析。
7. suffixedexp函数首先调用primaryexp函数，分析主表达式，也就是a。
8. primaryexp调用singlevar函数，将a当作一个变量进行分析。
9. singlevar没有找到名字为"a"的局部变量或upvalue，将"a"当作全局变量处理，也就是将"a"变成“_ENV.a"来处理。这里已经到了递归下降分析的最低端，最终创建一个VINDEXED的表达式给上层，table为upvalue "_ENV"，key为常量”a“。
10. 继续返回VINDEXED表达式给上层。
11. suffixedexp将这个VINDEXED表达式传给fieldsel，对后缀进行分析。
12. fieldsel首先根据这个VINDEXED表达式的table和key生成指令1，这个指令的目标寄存器为临时分配的寄存器0。然后以寄存器0为table，”b“为key，生成一个新的VINDEXED表达式返回给上层。
13. 继续返回VINDEXED表达式给上层。
14. 继续返回VINDEXED表达式给上层。
15. subexp调用subexp本身，开始对”+“号右边的表达式进行分析。
16. subexp调用simpleexp，分析这个”1“。
17. simpleexp为这个"1"生成一个VKNUM表达式，返回给上层。
18. 继续返回VKNUM表达式给上层。
19. subexp首先根据+号左边的VINDEXED表达式的table和key生成指令2，这个指令的目标寄存器为临时分配的寄存器0。然后生成指令3的加法运算，操作数为寄存器0和VNUM表达式对应的常量id。指令3的目标寄存器还不能确定，所以创建一个VRELOCABLE表达式返回给上层。
20. 这时整个表达式已经解析完毕，返回VRELOCABLE表达式给上层，等待进一步的处理。
21. 将VRELOCABLE表达式对应的指令3的目标寄存器回填成临时分配的寄存器0，然后将寄存器0的内容赋值给左边的VINDEXED表达式，也就是生成指令4。
通过上面的分析过程我们可以看到，Lua整体的语法分析过程就是对语法树的一次性的先续遍历的过程。对于表达式的分析，首先要分析子表达式，并为其生成指令来获取表达式的值，存入临时寄存器，然后父表达式再使用子表达式的分析结果和临时寄存器作为参数，来生成获取值的指令。所有在过程中使用的子表达式的expdesc结构体对象全部在函数的调用栈上分配，待分析完成返回后，就被丢弃掉了。由于Lua本身的指令是基于寄存器的，一条指令所能完成的任务相对比较复杂，所以有些情况下在子表达式分析过程中不能完全获得所需要的信息。这是就需要将表达式分析所得的信息返回给上一层父表达式，也就是子表达式的使用者，由上一层做最终的指令生成。或者先生成子表达式指令，然后在上一层分析中进行指令的回填修改。我们在上例中就可以清晰地看到这种情况。
在《[虚拟机指令](http://blog.csdn.net/yuanlin2008/article/details/8423951)》中我们提到过，Lua使用的是register based vm，所以相对于stack based vm来说，整个编译和指令生成过程要更复杂。寄存器在Lua中的第一个用处就是存储局部变量的值，所有局部变量在编译后，都不再使用名称，而是寄存器id进行访问。而另一个用处就是存储表达式估值过程中的临时值。当对一个表达式进行估值时，可能先要对其子表达式进行估值，将估值结果存储到一个临时的寄存器，然后使用这个结果再进行下一步的估值计算。寄存器为一个id从0开始的数组。在编译过程中，Lua使用FuncState中的freereg变量记录当前空闲寄存器的起始id。在开始编译一个FuncState时，freereg被设置成0，表示所有寄存器都可以被分配。当遇到一个局部变量或者临时值时，就分配出一个id为当前freereg的寄存器，然后将freereg++。局部变量会在语法域内一直占用这个寄存器，而临时值会在使用完其值后立即被释放，也就是freereg--。由于临时值会在表达式估值完成后全部释放掉，所以局部变量被分配的寄存器肯定是从0开始并且是连续的，中间不会被临时值占用。
总的来说，局部变量与临时值没有什么本质区别，都是用来存放函数计算过程中表达式的值得，唯一区别就在于临时值不占用寄存器，而局部变量会一直占用寄存器，并且可以被程序访问。
上面的例子中，12，19和21步中都需要临时寄存器的分配。我们看到在需要临时寄存器的指令生成之后，临时寄存器就被被释放掉了，所以每次分配时都会将寄存器0分配给临时值使用，而不会一直占用寄存器0。
在后面的文章中，我将会按照分类对表达式进行详细的讲解。