自制腳本語言（6） 解釋器

摘要：在前文提到的編譯器的基礎上，設計解釋器來解釋運作腳本語言。

代碼位址：https://github.com/nklofy/Compiler

也可以在我的上傳資源中下載下傳

  解釋執行是對中間代碼的一種執行方式，因為并沒有編譯成二進制碼在CPU直接執行，而是通過解釋器模拟執行。優點是容易實作，語義清晰，缺點是效率低、記憶體占用高。不過對于這個個人作品，我的計劃是先用解釋器直接解釋執行確定正确性以後再找機會實作為更底層的方式。

  前面的編譯器把腳本編譯為樹型中間代碼，這個解釋器直接周遊文法樹來執行。我設計為通路者模式。為什麼是通路者模式？這裡面有幾個考慮。第一是盡量讓interpreter對文法樹内部保持隔離。文法樹屬于parser子產品，和interpreter子產品應該是充分隔離的，互相之間盡量暴露少的接口。第二，通路者模式有利于實作control flow。用額外的control flow flag來控制interpreter的行為，如break、continue、return ，甚至還有函數式程式設計常見的call with current continuation。

  解釋執行時，需要有運作時環境。通常來說，需要有一個上下文環境，儲存類型資訊、變量表；而針對函數調用，需要棧幀。每次調用函數就建立一個新的棧幀，棧幀包含了一個新的環境，放置局部變量和類型；棧幀有調用鍊，指向調用這個函數的代碼所在的棧幀；棧幀包含一個傳回值，是函數調用結束後傳回的值；棧幀還應該有一個通路鍊，指向其他的環境來查找變量。這裡設計的棧幀沒有為寄存器保留位置，因為隻是模拟解釋，而不是二進制碼運作在CPU上。

  Interpreter包内，有Interpreter類、RT_Env類、RT_Frame類、RT_CtrFlow類。Interpreter類負責周遊文法樹，依序解釋執行，主要有interpret()接口。RT_Env類表示目前上下文環境，設定和讀取目前棧幀的變量表、類型表、函數表。RT_Frame類表示目前棧幀，主要是設定和讀取目前環境、函數的傳回變量、傳回棧幀，通路鍊暫時沒有加進去。RT_CtrFlow類主要是讀寫一個控制流的标記，來控制interpreter的行為。比如break狀态下，就會跳出循環體而不執行體内剩餘代碼，continue狀态則會跳出并重新開始執行。簡要的類型設計如下所示：

class Interpreter{
	interpret()	//與AST之間的解釋執行的接口
}
class RT_Env{
	Map<String,Obj>	//變量表
	Map<String,Set<Func>>	//函數表
	Map<String,Type>	//類型表
	get/addObj()	//環境中存取變量的值
	get/addFunc()	//環境中存取函數
	get/addType()	//環境中存取類型
}
class RT_Frame{
	get/setCtrEnv()	//讀寫目前環境
	get/setRtnObj()	//讀寫傳回變量
	get/setRtnFrm()	//讀寫傳回棧幀
}
class RT_CtrFlow{
	get/setFlowState()	//讀寫控制流狀态
}
           

  在AST下的具體文法樹類中，都實作了eval()接口。這個接口被interpreter所通路。而eval()函數内部，定義了interpreter對本類型内部屬性的通路順序和方法，也就是控制了interpreter通路本樹結點的子結點。這就是一個典型的通路者模式。與此同時，解釋AST_Var類型結點時，需要獲得Interpreter的環境，在其中儲存或通路變量。解釋AST_apply結點時，需要從環境中查找函數，先由函數名獲得一組函數，然後對應形參和實參的類型獲得唯一函數，interpreter中建立一個新RT_Frame棧幀，棧幀中建立新RT_Env環境，将形參名和實參值存入環境，然後解釋函數體的AST_StmtList。遇到解釋return語句時，将return calc_exp計算的結果放入棧幀的傳回變量值。被調用函數Callee結束時，取出傳回值，interpreter退回到上面一層棧幀，也就是傳回了調用函數caller的程式位置，繼續執行caller剩餘的代碼。

  下面是一個eval()的簡化例子（僅僅用來舉例，與真實代碼完全不同）：

class AST_AddExp{
	AST_AddExp add1;
	AST_MulExp add2;
	eval(Interpreter interpreter){
		Value v1=interpreter.interpret(add1);
		Value v2=interpreter.interpret(add2);
		return v1 + v2;
	}
}
class Interpreter{
	interpret(AST_AddExp add){
		if(getCtrFlow.isGo){
			add.eval(this);
		}else if(getCrtFlow.isSomeThing){
			do SomeThing;
		}...
	}
}
           

  這樣，在interpreter通路完整個AST抽象文法樹之後，就完成了整個腳本的解釋執行。

https://github.com/nklofy/Compiler