AST 解释执行

优质

小牛编辑

137浏览

2023-12-01

语法和语义分析的结果是抽象语法树AST，再往后编译原理还有代码生成及优化的很大一部分，但如果只是做一个执行器，到AST为止就可以解释执行了，当然就算不生成AST，解析执行也可以，只是基于之前说过的原因，极少采用解析执行的方式

目前的大多数解释执行的语言，都是在虚拟机解释字节码执行，这个后面再说，它只是把AST的解释串行化了而已，事实上ruby在1.9版本之前是解释AST执行的，到1.9整合了YARV才改成了解释字节码

抽象地看，一个高级语言的AST就是一个stmt_list，语法分析过程只是把人能看懂的语言转成方便解释器看懂的罢了，具体的执行过程和人阅读代码没什么差别，就是一个个stmt执行过去，前面讲过stmt的接口类的样子：

class Stmt   
{   
    RetType execute();   
}

这个RetType后面再细说，形式上可以认为一个解释器的架构就是：

RetType execute_stmt_list(StmtList stmt_list)   
{   
    for stmt in stmt_list //就是遍历，这里用伪代码   
    {   
        RetType ret = stmt.execute();   
        //处理RetType，后面讲   
    }   
}

因此，核心部分在于实现各个stmt的execute部分，为简单起见，我们讨论动态类型语言，所有变量类型都是用Object，这里还需要一个expr的接口：

class Expr   
{   
    Object compute();   
}

静态类型的情况虽然会复杂点，但也不难想到

于是很容易写出前面StmtPrint的execute方法（方便起见代码主要用类似java形式，不过不一定和java语法契合）：

Object a = this.e.compute();   
System.out.println(a);   
return RET_TYPE_NORMAL;

然后考虑StmtWhile的execute方法：

while (this.condition.compute().as_bool()) //因为是动态类型，as_bool将Object转为布尔型，和宿主语言契合   
{   
    RetType ret = execute_stmt_list(this.stmt_list);   
    //...   
}

在这里，出现了嵌套语句列表，相应地递归调用execute_stmt_list解释执行，这里需要解释下RetType的含义，根据具体的语法，一个语句块返回一般有以下几种情况：运行结束，break，continue，return，异常。而RetType则对应这几种，那么显然上面//...的内容差不多是这样：

switch (ret)   
{   
    case RET_TYPE_NORMAL:   
    case RET_TYPE_CONTINUE:   
        continue;   
    case RET_TYPE_BREAK:   
        break; //这里的意思是跳出while循环，不是switch   
    case RET_TYPE_RETURN:   
        return RET_TYPE_RETURN;   
    case RET_TYPE_EXCEPTION:   
        return RET_TYPE_EXCEPTION;   
}

return和异常直接往上面一层返回，因为while本身是在一个函数或try中，让上层来处理即可，另外，return的返回值和异常的内容应该已经存在某个地方了，不过这个在上面的伪代码里面没有体现，它属于运行时环境的范畴，后面再说

expr的compute方法的实现，差不多都是类似的，先计算各个操作数，然后最后做当前对象的运算，比如加法：

class ExprAdd   
{   
    Expr a;   
    Expr b;   
    Object compute()   
    {   
        return a.compute().add(b.compute());   
    }   
}

递归调用元素的compute，当然这个递归不会无限下去，最后都会停止于一个load操作：

class ExprLoad   
{   
    LoadArg a;   
    Object compute()   
    {   
        return env.get(a);   
    }   
}

其中env是运行时环境的一个抽象，简单说就是根据a的内容返回对应的对象即可，这个load操作一般会根据名字空间细化为几种，比如LoadLocal，LoadGlobal，LoadConst，表示从局部变量区，全局区，常量区

特殊点的，函数调用expr：

class ExprCallFunc   
{   
    Func f;   
    ExprList arg_list;   
    Object compute()   
    {   
        frm = f.init_frame(compute_expr_list(arg_list)); //初始化函数调用栈   
        RetType ret = execute_stmt_list_with_frm(f.stmt_list, frm);   
        assert ret == RET_TYPE_RETURN;   
        return frm.ret_value;   
    }   
}

这个实现稍微丑陋了点，其实可以改成f.execute(...)更直观些，另外这里的execute_stmt_list_with_frm以及ret_value存在栈帧里面只是表个意思，实际不一定这么实现