探索Lua5.2內(nèi)部實(shí)現(xiàn):編譯系統(tǒng)(1) 概述

目錄(?)[+]

原文

Lua是一個(gè)輕量級(jí)高效率的語言。這種輕量級(jí)和高效率不僅體現(xiàn)在它本身虛擬機(jī)的運(yùn)行效率上，而且也體現(xiàn)在他整個(gè)的編譯系統(tǒng)的實(shí)現(xiàn)上。因?yàn)榻^大多數(shù)的lua腳本需要運(yùn)行期動(dòng)態(tài)的加載編譯，如果編譯過程本身非常耗時(shí)，或者占用很多的內(nèi)存，也同樣會(huì)影響到整體的運(yùn)行效率，使你感覺這個(gè)語言不夠“動(dòng)態(tài)”。正是因?yàn)榫幾g系統(tǒng)實(shí)現(xiàn)的非常出色，我們?cè)趯?shí)際使用lua時(shí)基本感覺不到這個(gè)過程的存在。

要實(shí)現(xiàn)一個(gè)Lua的編譯系統(tǒng)可能不是很困難，但要高效的實(shí)現(xiàn)，還是有一定挑戰(zhàn)的。這需要一些精妙的設(shè)計(jì)和實(shí)現(xiàn)技巧，也值得我們花一些時(shí)間去一探究竟。

輸入與輸出

編譯系統(tǒng)的工作就是將符合語法規(guī)則的chunk轉(zhuǎn)換成可運(yùn)行的closure。要了解編譯系統(tǒng)，首先要了解作為輸入的chunk和最為輸出的closure以及他們的對(duì)應(yīng)關(guān)系。

說到closure，就不能不先說一下proto。closure對(duì)象是lua運(yùn)行期一個(gè)函數(shù)的實(shí)例對(duì)象，我們?cè)谶\(yùn)行期調(diào)用的都是一個(gè)closure。而proto對(duì)象是lua內(nèi)部代表一個(gè)closure原型的對(duì)象，有關(guān)函數(shù)的大部分信息都保存在這里。這些信息包括：

• 指令列表：包含了函數(shù)編譯后生成的虛擬機(jī)指令。
• 常量表：這個(gè)函數(shù)運(yùn)行期需要的所有常量，在指令中，常量使用常量表id進(jìn)行索引。
• 子proto表：所有內(nèi)嵌于這個(gè)函數(shù)的proto列表，在OP_CLOSURE指令中的proto id就是索引的這個(gè)表。
• 局部變量描述：這個(gè)函數(shù)使用到的所有局部變量名稱，以及生命期。由于所有的局部變量運(yùn)行期都被轉(zhuǎn)化成了寄存器id，所以這些信息只是debug使用。
• Upvalue描述：設(shè)個(gè)函數(shù)所使用到的Upvalue的描述，用來在創(chuàng)建closure時(shí)初始化Upvalue。

每個(gè)closure都對(duì)應(yīng)著自己的proto，而運(yùn)行期一個(gè)proto可以產(chǎn)生多個(gè)closure來代表這個(gè)函數(shù)實(shí)例。

由此可見，closure是運(yùn)行期的對(duì)象，與運(yùn)行期關(guān)系更大；而與編譯期相關(guān)的其實(shí)是proto對(duì)象，他才是編譯過程真正需要生成的目標(biāo)對(duì)象。

Chunk代表一段符合Lua的語法的代碼。我們可以調(diào)用lua_load api，將一個(gè)chunk進(jìn)行編譯。lua_load根據(jù)當(dāng)前chunk生成一個(gè)mainfunc proto，然后為這個(gè)proto創(chuàng)建一個(gè)closure放到當(dāng)前的棧頂，等待接下來的執(zhí)行。Chunk內(nèi)部的每個(gè)function statement也都會(huì)生成一個(gè)對(duì)應(yīng)的proto，保存在外層函數(shù)的子函數(shù)列表中。所有最外層的function statement的proto會(huì)被保存到mainfunc proto的子函數(shù)列表中。所以，整個(gè)編譯過程會(huì)生成一個(gè)以mainfunc為根節(jié)點(diǎn)的proto樹。

簡(jiǎn)介

按照功能劃分，整個(gè)編譯系統(tǒng)被劃分成以下3個(gè)模塊：

Lua并沒有使用llex和yacc，而是使用完全手寫的詞法和語法分析器。使用手寫分析器的原因首先是考慮到效率。并且yacc/bison本身生成的代碼在可移植性上有一些問題，無發(fā)達(dá)到Lua高可移植性的設(shè)計(jì)目標(biāo)。還有就是手寫分析器可以在C stack上面分配編譯過程中需要的數(shù)據(jù)對(duì)象，這個(gè)我們后面會(huì)講到。對(duì)于一個(gè)chunk，Lua在對(duì)其分析的過程中直接生成最終的指令，沒有多余的對(duì)源代碼或語法結(jié)構(gòu)的遍歷。也就是說Lua對(duì)源代碼進(jìn)行一次遍歷就生成最終結(jié)果。

詞法分析

LexState結(jié)構(gòu)體的用途其實(shí)與其名稱不是很貼切。LexState不僅用于保存當(dāng)前的詞法分析狀態(tài)信息，而且也保存了整個(gè)編譯系統(tǒng)的全局狀態(tài)，這個(gè)我們?cè)诤竺鏁?huì)講到。

語法分析和指令生成

從宏觀上講，整個(gè)編譯過程就是生成proto tree的過程。語法分析器從mainfunc出發(fā)，開始分析和生成mainfunc的proto。在生成一個(gè)proto的過程中，生成的指令直接保存到proto的指令列表中。當(dāng)遇到function statement或者local function statement時(shí)，首先生成子函數(shù)的proto，然后回來繼續(xù)。通過這樣的遍歷方式，最終構(gòu)建出一個(gè)proto tree。

在編譯過程中，使用FuncState結(jié)構(gòu)體來保存一個(gè)函數(shù)編譯的狀態(tài)數(shù)據(jù)。每個(gè)FuncState都有一個(gè)prev變量用來引用外圍函數(shù)的FuncState，使當(dāng)前所有沒有分析完成的FuncState形成一個(gè)棧結(jié)構(gòu)。棧底是mainfunc的FuncState，棧頂是當(dāng)前正在分析的FuncState。每當(dāng)開始分析一個(gè)新的函數(shù)時(shí)，會(huì)創(chuàng)建一個(gè)新的FuncState與之對(duì)應(yīng)，將當(dāng)前的FuncState保存在新的FuncState的prev中，并將當(dāng)前的FuncState指向新的FuncState，這相當(dāng)于壓棧(open_func)。等待這個(gè)新函數(shù)分析完成后，當(dāng)前的FuncState就沒用了，將當(dāng)前的FuncState恢復(fù)成原來的FuncState，這相當(dāng)于彈棧(close_func)。

Dyndata是一個(gè)全局?jǐn)?shù)據(jù)，他本身也是一個(gè)棧。對(duì)應(yīng)上面的FuncState棧，Dyndata保存了每個(gè)FuncState對(duì)應(yīng)的局部變量描述列表，goto列表和label列表。這些數(shù)據(jù)會(huì)跟著當(dāng)前FuncState進(jìn)行壓棧和彈棧。

前面說過，整個(gè)編譯系統(tǒng)的全局狀態(tài)都保存在LexState中。LexState中與全局狀態(tài)相關(guān)的主要是兩個(gè)變量。fs指向當(dāng)前正在編譯的函數(shù)的FuncState。而dyd則指向全局的Dyndata數(shù)據(jù)。

FuncState本身通過f保存對(duì)于Proto的引用。所有過程中生成的指令都直接保存到Proto的指令列表中。FuncState還通過h引用到一個(gè)table，用于在編譯過程中生成proto的常量表。這個(gè)table使用常量值作為key，常量的id作為value。當(dāng)編譯過程中發(fā)現(xiàn)一個(gè)常量時(shí)，會(huì)首先使用這個(gè)常量值在這個(gè)表中查找。如果找到，說明前面已經(jīng)將這個(gè)常量加入到常量表了，直接使用其id。否者，向常量表中添加一個(gè)常量，并相應(yīng)的添加到這個(gè)表中。

對(duì)于一個(gè)FuncState本身的分析也是有層次關(guān)系的。一個(gè)函數(shù)本身使用block來控制局部變量的有效范圍。函數(shù)本身就是一個(gè)block，里面的想while statement，for statement等等，還會(huì)形成子block。函數(shù)內(nèi)的這些block會(huì)形成一個(gè)以函數(shù)本身block為根節(jié)點(diǎn)的block tree。Lua使用BlockCnt來保存一個(gè)block的數(shù)據(jù)。與FuncState的分析方法類似，BlockCnt使用一個(gè)previous變量保存外圍block的引用，形成一個(gè)棧結(jié)構(gòu)。enterblock和leaveblock函數(shù)負(fù)責(zé)壓棧和彈棧。在FuncState中，bl用來指向當(dāng)前的block。

縱觀整個(gè)語法分析過程，Lua其實(shí)就是按照深度優(yōu)先的順序，遍歷了FuncState tree，以及子結(jié)構(gòu)BlockCnt tree。在遍歷的過程中，所有的編譯狀態(tài)(FuncState,BlockCnt)都是在C stack中保存，這就表示只保存當(dāng)前正在處理的編譯狀態(tài)，而那些已經(jīng)處理完成的在彈棧時(shí)被丟棄。在分析具體的語法結(jié)構(gòu)時(shí)也是如此，Lua并被有完整的構(gòu)建一個(gè)語法樹對(duì)象，而是將過程中的語法結(jié)構(gòu)保存在函數(shù)棧中，分析完立刻丟棄。所以就算用Lua來分析一個(gè)很大的程序，也不會(huì)占用過多的內(nèi)存。不過，這也為指令生成帶來了很多麻煩。比如向后跳轉(zhuǎn)，在分析過程中還無法知道具體的跳轉(zhuǎn)地址。如果構(gòu)建了完整的語法樹，就可以在最后去解決這些未決的地址。Lua使用了一些技巧來解決這些問題，我會(huì)在后面的文章中詳細(xì)講述。