用于以解释语言存储变量的数据结构

Question

我正在设计自己的实验性脚本语言,以便将其嵌入到我更大的应用程序中.

我想做的几乎所有事情都是顺利编程的,但在内存中存储变量的"简单"行为似乎是最困难的部分.我不知道如何存储它们以允许所有类型检查,全局变量和特殊标志.首先看一下示例代码:

a = 1
b = 2

someFunction()
  print(a)   --> This should read the global variable and print `1`
  a = 3      --> Now `a` should become a local variable of this function
                 and the global `a` remain unchanged
  x = 4      --> `x` should always be local of this function
end

我将变量的"局部性"称为levels,因此嵌套块中的变量具有更高的级别.在上面的代码,a并且b是1级的变量.someFunction的局部变量将具有2级.函数的第一行应该读取全局变量a(级别1),但是第二行应该创建一个再次调用的变量,a但是级别2会a从该点开始影响全局变量.第三行应该创建x级别为2 的变量.如何在内存中存储和跟踪所有这些变量？

到目前为止我尝试了什么:

方法1:存储variable=>value级别数组的映射:

variables
{
    level=1 //global variables
    {
        a => 1,
        b => 2
    },
    level=2 //function variables
    {
        a => 3,
        x => 4
    }
}

但这会使变量查找真的很慢,因为必须搜索给定变量的所有级别.

方法2:将(变量,级别)对存储为映射的键:

variables
{
    (a, 1) => 1, //global
    (b, 1) => 2, //global
    (a, 2) => 3, //function
    (x, 2) => 3  //function
}

这与以前有同样的问题,因为我们必须尝试具有给定变量的所有可能级别的对(变量,级别).

我应该使用什么方法来优化内存使用和最快的访问时间？

补充说明:

我知道如何在堆栈和堆上管理变量在其他"真实"语言上,但我发现在解释语言上执行此操作很棘手."这绝不是Lua和Python那样做的,"我一直认为.如我错了请纠正我.我正在尝试将变量存储在地图和内部C++结构中.

最后,这就是我代表变量的方式.你认为它很大,可以有更多的内存效率表示吗？(我也尝试将"Level"作为成员在这里,但它也有与其他问题相同的问题.)

struct Member
{
    uchar type;  //0=num, 1=str, 2=function, 3=array, etc
    uchar flags; //0x80 = read-only, 0x40 = write-only, etc
    union {
        long double value_num;
        char* value_str;
        int value_func;
        //etc
    };
};

Answer 1

与数组类似,一件容易的事就是维护一堆地图.每个映射都包含该范围的绑定.要绑定变量,请将其添加到顶部地图; 查找变量,从堆栈顶部开始,到达包含该变量绑定的映射时停止.搜索需要一点点,但从顶部/结尾开始,您只需搜索直到找到它 - 在大多数情况下,此搜索不会很长.

您还可以通过将此逻辑封装在Environment具有本地绑定的类和用于解析未知变量的继承环境中来隐式堆栈.需要进入一个新的范围？创建一个以当前环境为基础的新环境,使用它,然后在范围完成时将其丢弃.根/全局环境可以只具有null继承环境.这是我可能会做的.