可以用符号表实现解释器吗？

Question

我常常听说使用符号表可以优化编程语言中的符号查找.目前,我的语言仅作为解释器实现,而不是作为编译器实现.我还不想分配时间来构建编译器,所以我试图优化解释器.该语言大部分基于Scheme语义和语法,并且是静态范围的.我使用AST在运行时执行代码(在我的解释器中,实现为有区别的联合,就像在AST中一样)Write Yourself a Scheme in 48 Hours.

不幸的是,由于使用F#Map按名称包含和查找符号,因此我的解释器中的符号查找速度很慢.(嗯,实际上,它使用的是Trie,但性能同样存在问题).我想改为使用符号树来实现更快的符号查找.但是,我不知道是否或如何在解释器中实现符号表.我只在编译器的上下文中听到它们.

这可能吗？如果实现策略或性能与编译器中的符号表不同,您能描述一下这些差异吗？最后,在我可能会看到的解释器中是否存在符号树的现有参考实现？

谢谢!

Answer 1

符号表将一些信息与每个符号相关联.在解释器中,您可能会将值与符号相关联.Map是一种特别适用于功能性解释器的实现.

如果要优化解释器,请在运行时删除对符号表的需求.一个方法是De Bruijn idexing.

还有一些很好的文献可以从功能解释器中机械地推导出优化的解释器,虚拟机和编译器,例如:

http://www.brics.dk/RS/03/14/BRICS-RS-03-14.pdf

举一个简单的例子,考虑具有用De Bruijn指数编码的常数的lambda演算.请注意,求值程序没有符号表,因为它可以使用整数进行查找.

type exp =
    | App of exp * exp
    | Const of int
    | Fn of exp
    | Var of int

type value =
    | Closure of exp * env
    | Number of int

and env = value []

let lookup env i = Array.get env i
let extend value env = Array.append [| value |] env
let empty () : env = Array.empty

let eval exp =
    let rec eval env exp =
        match exp with
        | App (f, x) ->
            match eval env f with
            | Closure (bodyF, envF) ->
                let vx = eval env x
                eval (extend vx envF) bodyF
            | _ -> failwith "?"
        | Const x -> Number x
        | Fn e -> Closure (e, env)
        | Var x -> lookup env x
    eval (empty ()) exp