自制脚本语言（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