一門語(yǔ)言的作用域和函數(shù)調(diào)用是如何實(shí)現(xiàn)的

作者：crossoverJie 2022-08-17 08:10:34

Visitor? 模式正好和 Listener 相反，這是由我們自行控制需要訪問(wèn)哪個(gè) AST 節(jié)點(diǎn)，同時(shí)需要在每次訪問(wèn)之后返回?cái)?shù)據(jù)，這點(diǎn)非常適合來(lái)做程序運(yùn)行期。

前言

上次利用 Antlr 重構(gòu)一版??用 Antlr 重構(gòu)腳本解釋器??之后便著手新增其他功能，也就是現(xiàn)在看到的支持了作用域以及函數(shù)調(diào)用。

int b= 10;
int foo(int age){
 for(int i=0;i<10;i++){
  age++;
 }
 return b+age;
}
int add(int a,int b) {
 int e = foo(10);
 e = e+10;
 return a+b+3+e;
}
add(2,20);
// Output:65

整個(gè)語(yǔ)法規(guī)則大部分參考了 Java，現(xiàn)階段支持了：

函數(shù)聲明與調(diào)用。
函數(shù)調(diào)用的入棧和出棧，保證了函數(shù)局部變量在函數(shù)退出時(shí)銷毀。
作用域支持，內(nèi)部作用域可以訪問(wèn)外部作用域的變量。
基本的表達(dá)式語(yǔ)句，如i++, !=,==

這次實(shí)現(xiàn)的重點(diǎn)與難點(diǎn)則是作用域與函數(shù)調(diào)用，實(shí)現(xiàn)之后也算是滿足了我的好奇心，不過(guò)在講作用域與函數(shù)調(diào)用之前先來(lái)看看一個(gè)簡(jiǎn)單的變量聲明與訪問(wèn)語(yǔ)句是如何實(shí)現(xiàn)的，這樣后續(xù)的理解會(huì)更加容易。

變量聲明

int a=10;
a;

由于還沒(méi)有實(shí)現(xiàn)內(nèi)置函數(shù)，比如控制臺(tái)輸出函數(shù) print()，所以這里就直接訪問(wèn)變量也能拿到數(shù)據(jù)

運(yùn)行后結(jié)果如下：

首先看看變量聲明語(yǔ)句的語(yǔ)法：

variableDeclarators
    : typeType variableDeclarator (',' variableDeclarator)*
    ;

variableDeclarator
    : variableDeclaratorId ('=' variableInitializer)?
    ;
typeList
    : typeType (',' typeType)*
    ;
typeType
    : (functionType | primitiveType) ('[' ']')*
    ;
primitiveType
    : INT
    | STRING
    | FLOAT
    | BOOLEAN
    ;

只看語(yǔ)法不太直觀，直接看下生成的 AST 樹(shù)就明白了：

編譯期左邊這棵 ?BlockVardeclar? 樹(shù)對(duì)應(yīng)的就是 int a=10;?，右邊的 blockStm? 對(duì)應(yīng)的就是變量訪問(wèn) a。

整個(gè)程序的運(yùn)行過(guò)程分為編譯期和運(yùn)行期，對(duì)應(yīng)的流程：

遍歷 AST 樹(shù)，做語(yǔ)義分析，生成對(duì)應(yīng)的符號(hào)表、類型表、引用消解、還有一些語(yǔ)法校驗(yàn)，比如變量名、函數(shù)名是否重復(fù)、是否能訪問(wèn)私有變量等。

運(yùn)行期：從編譯期中生成的符號(hào)表、類型表中獲取數(shù)據(jù)，執(zhí)行具體的代碼邏輯。

訪問(wèn) AST

對(duì)于剛才提到的編譯期和運(yùn)行期其實(shí)分別對(duì)應(yīng)兩種訪問(wèn) AST? 的方式，這也是 Antlr 所提供兩種方式。

Listener 模式

第一種是 Listener 模式，就這名字也能猜到是如何運(yùn)行的；我們需要實(shí)現(xiàn) Antlr 所提供的接口，這些接口分別對(duì)應(yīng) AST 樹(shù)中的不同節(jié)點(diǎn)。

接著 Antlr 會(huì)自動(dòng)遍歷這棵樹(shù)，當(dāng)訪問(wèn)和退出某個(gè)節(jié)點(diǎn)時(shí)變會(huì)回調(diào)我們自定義的方法，這些接口都是沒(méi)有返回值的，所以我們需要將遍歷過(guò)程中的數(shù)據(jù)自行存放起來(lái)。

這點(diǎn)非常適合上文提到的編譯期，遍歷過(guò)程中產(chǎn)生的數(shù)據(jù)自然就會(huì)存放到符號(hào)表、類型表這些容器中。

以這段代碼為例，我們實(shí)現(xiàn)了程序根節(jié)點(diǎn)、for循環(huán)節(jié)點(diǎn)的進(jìn)入和退出 Listener，當(dāng) Antlr 運(yùn)行到這些節(jié)點(diǎn)時(shí)便會(huì)執(zhí)行其中的邏輯。

https://github.com/crossoverJie/gscript/blob/main/resolver/type_scope_resolver.go

Visitor 模式

配合在編譯期中存放的數(shù)據(jù)，便可以實(shí)現(xiàn)各種特性了。

以上圖為例，在訪問(wèn) Prog 節(jié)點(diǎn)時(shí)便可以從編譯期中拿到當(dāng)前節(jié)點(diǎn)所對(duì)應(yīng)的作用域 scope?，同時(shí)我們可以自行控制訪問(wèn)下一個(gè)節(jié)點(diǎn) VisitBlockStms，訪問(wèn)其他節(jié)點(diǎn)當(dāng)然也是可以的，不過(guò)通常我們還是按照語(yǔ)法中定義的結(jié)構(gòu)進(jìn)行訪問(wèn)。

作用域

即便是同一個(gè)語(yǔ)法生成的 AST 是相同的，但我們?cè)诒闅v AST 時(shí)實(shí)現(xiàn)不同也就會(huì)導(dǎo)致不同的語(yǔ)義，這就是各個(gè)語(yǔ)言語(yǔ)義分析的不同之處。

比如 Java 不允許在子作用域中聲明和父作用域中相同的變量，但 JavaScript 卻是可以的。

有了上面的基礎(chǔ)下面我們來(lái)看看作用域是如何實(shí)現(xiàn)的。

int a=10;
a;

還是以這段代碼為例：

這里我簡(jiǎn)單畫了下流程：

在編譯期間會(huì)會(huì)為當(dāng)前節(jié)點(diǎn)寫入一個(gè) scope?，以及在 scope? 中寫入變量 “a”。

這里的寫入 scope 和寫入變量是分為兩次 Listener 進(jìn)行的，具體代碼實(shí)現(xiàn)在下面查看源碼。

第一次：https://github.com/crossoverJie/gscript/blob/main/resolver/type_scope_resolver.go#L21

第二次：https://github.com/crossoverJie/gscript/blob/main/resolver/type_resolver.go#L59

接著是運(yùn)行期，從編譯期中生成的數(shù)據(jù)拿到 scope? 以及其中的變量，獲取變量時(shí)有一個(gè)細(xì)節(jié)：當(dāng)前 scope 中如果獲取不到需要嘗試從父級(jí) scope 中獲取，比如如下情況：

int b= 10;
int foo(){
 return b;
}

這里的 b 在當(dāng)前函數(shù)作用域中是獲取不到的，只能在父級(jí) scope 中獲取。

父級(jí) scope 的關(guān)系是在創(chuàng)建 scope 的時(shí)候維護(hù)進(jìn)去的，默認(rèn)當(dāng)前 scope 就是寫入時(shí) scope 的父級(jí)。

關(guān)鍵代碼試下如下圖：

第四步獲取變量的值也是需要訪問(wèn)到 AST 中的字面量節(jié)點(diǎn)獲取值即可，核心代碼如下：

函數(shù)

函數(shù)的調(diào)用最核心的就是在運(yùn)行時(shí)需要把當(dāng)前函數(shù)中的所有數(shù)據(jù)入棧，訪問(wèn)完畢后出棧，這樣才能實(shí)現(xiàn)函數(shù)退出后自動(dòng)釋放函數(shù)體類的數(shù)據(jù)。

核心代碼如下：

int b= 10;
int foo(){
 return b;
}
int func(int a,int b) {
 int e = foo();
 return a+b+3+e;
}
func(2,20);

即便是有上面這類函數(shù)類調(diào)其他函數(shù)情況也不必?fù)?dān)心，無(wú)非就是在執(zhí)行函數(shù)體的時(shí)候再往棧中寫入數(shù)據(jù)而已，函數(shù)退出后會(huì)依次退出棧幀。

有點(diǎn)類似于匹配括號(hào)的算法 {[()]}，本質(zhì)上就是遞歸調(diào)用。

總結(jié)

限于篇幅其中的許多細(xì)節(jié)沒(méi)有仔細(xì)討論，感興趣的朋友可以直接跑跑單測(cè)，debug 試試。

https://github.com/crossoverJie/gscript/blob/main/compiler_test.go

目前的版本還比較初級(jí)，比如基本類型還只有 int，也沒(méi)有一些常用的內(nèi)置函數(shù)。

后續(xù)會(huì)逐步完善，比如新增：

函數(shù)多返回值。
自定義類型
閉包

等特性，這個(gè)坑會(huì)一直填下去，希望在年底可以用 gscript? 寫一個(gè) web 服務(wù)端那就算是里程碑完成了。

現(xiàn)階段也實(shí)現(xiàn)了一個(gè)簡(jiǎn)易的 REPL? 工具，大家可以安裝試用：

源碼地址：https://github.com/crossoverJie/gscript

責(zé)任編輯：武曉燕來(lái)源： crossoverJie