# 探索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   ~~~ 整个的递归下降语法分析过程可以用下图表示。 ![](https://box.kancloud.cn/2016-01-15_56989af2ad7e3.png) 由于我们目前需要讲解的是表达式,这里为了讲解方便,这里省略了一些过程。接下来我们对这些步骤逐一进行解说。 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。 在后面的文章中,我将会按照分类对表达式进行详细的讲解。