Lua是一個輕量級高效率的語言。這種輕量級和高效率不僅體現在它本身虛擬機的運行效率上，而且也體現在他整個的編譯系統的實現上。因為絕大多數的lua腳本需要運行期動態的加載編譯，如果編譯過程本身非常耗時，或者佔用很多的內存，也同樣會影響到整體的運行效率，使你感覺這個語言不夠“動態”。正是因為編譯系統實現的非常出色，我們在實際使用lua時基本感覺不到這個過程的存在。
要實現一個Lua的編譯系統可能不是很困難，但要高效的實現，還是有一定挑戰的。這需要一些精妙的設計和實現技巧，也值得我們花一些時間去一探究竟。
輸入與輸出
編譯系統的工作就是將符合語法規則的chunk轉換成可運行的closure。要了解編譯系統，首先要了解作為輸入的chunk和最為輸出的closure以及他們的對應關係。
說到closure，就不能不先說一下proto。closure對像是lua運行期一個函數的實例對象，我們在運行期調用的都是一個closure。而proto對像是lua內部代表一個closure原型的對象，有關函數的大部分信息都保存在這裡。這些信息包括：
- 指令列表：包含了函數編譯後生成的虛擬機指令。
- 常量表：這個函數運行期需要的所有常量，在指令中，常量使用常量表id進行索引。
- 子proto表：所有內嵌於這個函數的proto列表，在OP_CLOSURE指令中的proto id就是索引的這個表。
- 局部變量描述：這個函數使用到的所有局部變量名稱，以及生命期。由於所有的局部變量運行期都被轉化成了寄存器id，所以這些信息只是debug使用。
- Upvalue描述：設個函數所使用到的Upvalue的描述，用來在創建closure時初始化Upvalue。
每個closure都對應著自己的proto，而運行期一個proto可以產生多個closure來代表這個函數實例。
由此可見，closure是運行期的對象，與運行期關係更大；而與編譯期相關的其實是proto對象，他才是編譯過程真正需要生成的目標對象。
Chunk代表一段符合Lua的語法的代碼。我們可以調用lua_load api，將一個chunk進行編譯。lua_load根據當前chunk生成一個mainfunc proto，然後為這個proto創建一個closure放到當前的棧頂，等待接下來的執行。Chunk內部的每個function statement也都會生成一個對應的proto，保存在外層函數的子函數列表中。所有最外層的function statement的proto會被保存到mainfunc proto的子函數列表中。所以，整個編譯過程會生成一個以mainfunc為根節點的proto樹。
簡介
按照功能劃分，整個編譯系統被劃分成以下3個模塊：
- 詞法分析模塊llex.h .c
- 語法分析模塊lparser.h .c
- 指令生成模塊lcode.h .c
Lua並沒有使用llex和yacc，而是使用完全手寫的詞法和語法分析器。使用手寫分析器的原因首先是考慮到效率。並且yacc/bison本身生成的代碼在可移植性上有一些問題，無發達到Lua高可移植性的設計目標。還有就是手寫分析器可以在C stack上面分配編譯過程中需要的數據對象，這個我們後面會講到。對於一個chunk，Lua在對其分析的過程中直接生成最終的指令，沒有多餘的對源代碼或語法結構的遍歷。也就是說Lua對源代碼進行一次遍歷就生成最終結果。
詞法分析
Lua的詞法分析模塊比較簡單而且獨立，就是將源代碼拆分成一個個token，提供給語法分析使用。語法分析程序會調用luaX_next來獲取下一個單詞，然後進行語法分析。
- typedef union {
- lua_Number r;
- TString *ts;
- } SemInfo; /* semantics information */
- typedef struct Token {
- int token;
- SemInfo seminfo;
- } Token;
Token用來表示一個單詞，它包括類型token和語義seminfo。類型使用一個int來表示，既可以是一個字符，也可以是一個enum RESERVED。enum RESERVED從257開始，就是為了留給字符使用。如果類型是一個TK_NUMBER，seminfo.r就用來表示這個數字；如果是TK_NAME或者TK_STRING，seminfo.ts就表示對應的字符串。
LexState結構體的用途其實與其名稱不是很貼切。LexState不僅用於保存當前的詞法分析狀態信息，而且也保存了整個編譯系統的全局狀態，這個我們在後面會講到。
語法分析和指令生成
語法分析器是整個編譯過程的驅動器。通過對luaY_parser函數的調用，啟動整個編譯過程。語法分析採用“遞歸下降”的方法，從詞法分析器中讀取下一個token，然後根據這個token和lua的語法規則，將高層的語法規則分解成底層的語法規則，進一步進行分析。根據語法，“遞歸”在lua語法中只出現在兩個地方，一個是statement函數，一個是subexpr函數。這也就是在這兩個函數中調用enterlevel和leaveleavel，對當前調用深度進行檢測的原因。如果遞歸太深，編譯會報錯。在分析的過程中，詞法分析器會調用指令生成器，直接生成最終的指令。
從宏觀上講，整個編譯過程就是生成proto tree的過程。語法分析器從mainfunc出發，開始分析和生成mainfunc的proto。在生成一個proto的過程中，生成的指令直接保存到proto的指令列表中。當遇到function statement或者local function statement時，首先生成子函數的proto，然後回來繼續。通過這樣的遍歷方式，最終構建出一個proto tree。
在編譯過程中，使用FuncState結構體來保存一個函數編譯的狀態數據。每個FuncState都有一個prev變量用來引用外圍函數的FuncState，使當前所有沒有分析完成的FuncState形成一個棧結構。棧底是mainfunc的FuncState，棧頂是當前正在分析的FuncState。每當開始分析一個新的函數時，會創建一個新的FuncState與之對應，將當前的FuncState保存在新的FuncState的prev中，並將當前的FuncState指向新的FuncState，這相當於壓棧(open_func )。等待這個新函數分析完成後，當前的FuncState就沒用了，將當前的FuncState恢復成原來的FuncState，這相當於彈棧(close_func)。
Dyndata是一個全局數據，他本身也是一個棧。對應上面的FuncState棧，Dyndata保存了每個FuncState對應的局部變量描述列表，goto列表和label列表。這些數據會跟著當前FuncState進行壓棧和彈棧。
前面說過，整個編譯系統的全局狀態都保存在LexState中。LexState中與全局狀態相關的主要是兩個變量。fs指向當前正在編譯的函數的FuncState。而dyd則指向全局的Dyndata數據。
FuncState本身通過f保存對於Proto的引用。所有過程中生成的指令都直接保存到Proto的指令列表中。FuncState還通過h引用到一個table，用於在編譯過程中生成proto的常量表。這個table使用常量值作為key，常量的id作為value。當編譯過程中發現一個常量時，會首先使用這個常量值在這個表中查找。如果找到，說明前面已經將這個常量加入到常量表了，直接使用其id。否者，向常量表中添加一個常量，並相應的添加到這個表中。
對於一個FuncState本身的分析也是有層次關係的。一個函數本身使用block來控制局部變量的有效範圍。函數本身就是一個block，裡面的想while statement，for statement等等，還會形成子block。函數內的這些block會形成一個以函數本身block為根節點的block tree。Lua使用BlockCnt來保存一個block的數據。與FuncState的分析方法類似，BlockCnt使用一個previous變量保存外圍block的引用，形成一個棧結構。enterblock和leaveblock函數負責壓棧和彈棧。在FuncState中，bl用來指向當前的block。
縱觀整個語法分析過程，Lua其實就是按照深度優先的順序，遍歷了FuncState tree，以及子結構BlockCnt tree。在遍歷的過程中，所有的編譯狀態(FuncState,BlockCnt)都是在C stack中保存，這就表示只保存當前正在處理的編譯狀態，而那些已經處理完成的在彈棧時被丟棄。在分析具體的語法結構時也是如此，Lua並被有完整的構建一個語法樹對象，而是將過程中的語法結構保存在函數棧中，分析完立刻丟棄。所以就算用Lua來分析一個很大的程序，也不會佔用過多的內存。不過，這也為指令生成帶來了很多麻煩。比如向後跳轉，在分析過程中還無法知道具體的跳轉地址。如果構建了完整的語法樹，就可以在最後去解決這些未決的地址。Lua使用了一些技巧來解決這些問題，我會在後面的文章中詳細講述。
在C stack中保存編譯狀態數據還有一個原因，是和編譯系統的報錯機制相關。編譯系統整體的報錯機制採用與虛擬機運行期一致的異常處理機制，也就是longjump。當出錯時，直接跳出到最外層進行處理，此時所有當前的編譯狀態數據要能自動銷毀掉。
No comments:
Post a Comment