探索Lua5.2內部實現:編譯系統(3) 表達式

原文地址:http://blog.csdn.net/yuanlin2008/article/details/8516325

表達式(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，我們可以看到Lua中僅有以下地方需要使用表達式：

• 變量賦值，等號左邊必須是一個變量表達式，右邊是一個任意表達式
• 局部變量的初始化，等號右邊是任意表達式
• if statement的條件表達式和循環的條件表達式

在需要表達式的地方，通過調用expr函數，並傳入一個expdesc結構體對象，對錶達式進行解析。表達式的解析是一個遞歸下降的過程。下降分析將高層的表達式分解成底層表達式或表達式的組合，而遞歸則發生在expr函數的遞歸調用上，也就是說在解析過程中還會用表達式本身來描述高層表達式。當解析到BNF的終結符時，會返回上一層處理，然後再一層層的處理後返回。expr函數最終會填充傳入的expdesc結構體，作為最高層的根表達式，交給更高層的語義，也就是上面需要表達式的地方進行處理。

Lua關於遞歸下降分析的每個函數的註釋中都有代表這個函數的BNF範式，我們可以很容易的瀏覽這些代碼，不需要過多的解釋。真正需要理解的是表達式與指令生成相關的部分，這也是整個Lua編譯系統裡面比較晦澀的地方。我們可以首先通過一個簡單的例子，在宏觀上了解一下語法分析和指令生成的全過程。

對於下面的chunk

[plain] view plain copy print ?

1. c = ab + 1  

我們最終可以生成如下指令

[plain] view plain copy print ?

1. main <test.lua:0,0> (5 instructions at 0x80048eb8)  
2. 0+ params, 2 slots, 1 upvalue, 0 locals, 4 constants, 0 functions  
3.         1 [1] GETTABUP 0 0 -2 ; _ENV "a"  
4.         2 [1] GETTABLE 0 0 -3 ; "b"  
5.         3 [1] ADD 0 0 -4 ; - 1  
6.         4 [1] SETTABUP 0 -1 0 ; _ENV "c"  
7.         5 [1] RETURN 0 1  
8. constants (4) for 0x80048eb8:  
9.         1 "c"  
10.         2 "a"  
11.         3 "b"  
12.         4 1  
13. locals (0) for 0x80048eb8:  
14. upvalues​​ (1) for 0x80048eb8:  
15.         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本身的指令是基於寄存器的，一條指令所能​​完成的任務相對比較複雜，所以有些情況下在子表達式分析過程中不能完全獲得所需要的信息。這是就需要將表達式分析所得的信息返回給上一層父表達式，也就是子表達式的使用者，由上一層做最終的指令生成。或者先生成子表達式指令，然後在上一層分析中進行指令的回填修改。我們在上例中就可以清晰地看到這種情況。

在《虛擬機指令》中我們提到過，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。

在後面的文章中，我將會按照分類對錶達式進行詳細的講解。