探索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

c = a.b + 1
           

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

main <test.lua:0,0> (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本身的指令是基于寄存器的，一條指令所能完成的任務相對比較複雜，是以有些情況下在子表達式分析過程中不能完全獲得所需要的資訊。這是就需要将表達式分析所得的資訊傳回給上一層父表達式，也就是子表達式的使用者，由上一層做最終的指令生成。或者先生成子表達式指令，然後在上一層分析中進行指令的回填修改。我們在上例中就可以清晰地看到這種情況。

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

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