如何在解释器中跟踪变量的索引

Question

我正在创建一个解释器（字节码解释器，也是一个编译器），我发现了一个我无法解决的问题。我需要把变量存储在某个地方。将它们存储在字典中并在运行时查找它们可能会很慢，所以我希望将它们存储在寄存器中，并使用它们的索引而不是名称。

所以在编译时，我给每个变量一个索引，并创建一个寄存器数组。这对于单一范围的语言来说很好。但是我正在为其创建解释器的语言具有嵌套范围（和函数调用）。所以另一种方法可能是我有一组全局寄存器和一堆用于函数调用的寄存器列表。所以我的虚拟机会有这样的东西：

Register globalRegisters[NUMBER_OF_GLOBALS];
Stack<Register[]> callstack;

但还有一件事。我的语言允许函数中包含函数。示例：

var x = 1;
function foo() {
    y = 2;
    function bar() {
        z = 3;
        y = y - 1;
    }
}

Function bar（）引用属于foo（）的变量。因此，这意味着虚拟机必须查看堆栈顶部的寄存器列表。但如果bar（）是递归的呢？如果递归的数量是由用户输入定义的呢？然后，虚拟机就不知道要找到包含y值的寄存器集，需要多少堆栈元素。

这个问题的有效解决方案是什么？这是我第一次处理寄存器，计算发生在值堆栈上。

Answer 1

我认为这里的基本问题与你写的问题非常不同，所以我写了一个解释，解释为什么我认为这个问题格式不正确，并回答了我认为基本问题是什么。如果我错了，我道歉，但请宽容一点：-）

我正在创建一个解释器（字节码解释器，也是编译器）

解释器不是编译器，即使它是针对低级语言的，除非您的程序将某种语言编译为某种字节码解释，然后再对其进行解释。在任何情况下，除非您正在jitting代码，否则实际运行的程序就是解释器。

将它们存储在字典中并在运行时查找它们可能会很慢，所以我希望将它们存储在寄存器中，并使用它们的索引而不是名称。

在解释器中，将目标语言变量强制放入寄存器对我来说并不合适。例如，假设您有一种解释使用变量的特定语句的方法。您可以快速提取变量，因为您可以将它们强制放入寄存器中，但是寄存器太少，无法在您自己的方法中高效地运行操作。而且，说“是的，我只把它们存储在寄存器中”让我怀疑你高估了可用寄存器的数量。

我猜这里的“寄存器”是一个错误，您只关心在存在嵌套作用域和递归的情况下存储和访问局部变量的一些有效方法。因此，我认为您的问题可以用“我想要一些存储局部变量的数据结构，在存在嵌套作用域和递归函数的情况下如何做到这一点？”如果我错了，我很抱歉，但如果不是：

要回答“我想要一些存储局部变量的数据结构，如何在嵌套范围和递归函数存在的情况下做到这一点？”，我认为最好首先在局部变量的上下文中澄清范围和框架之间的区别。

范围是标识符到局部变量的一些映射。在范围内，您知道x标识符的所有实例都指的是同样的东西（大致）。范围是您在解析输入语言时关心的东西——它是您用来理解代码语义的东西（“哦，编码器正在递增的x与2行前的x相同”）。

帧是调用函数时分配的内存（通常在堆栈上）。每个局部通常在帧上获得一个保留位置来存储其值。

当您解析代码并处理作用域时，您并不关心递归（因为您没有运行任何东西，只是解析）。您确实关心嵌套的作用域，但这些作用域永远不会解除绑定，因为代码本身（不是它的执行，只是代码）总是有限的。解析时处理作用域中的局部变量的标准方法是保留字典堆栈。打开作用域时创建并推送新词典，关闭时弹出新词典。每当访问x时，请在堆栈中最顶层的字典中查找它-如果没有，请继续查找下一个字典，依此类推。

然后，您生成的代码（或在解释器中直接执行的代码）将准确地知道x的每个实例所指的位置。这些内存位置将在创建帧时分配。这样，您就不必关心递归了——您已经将变量映射到当前帧中的位置，无论从何处调用该帧，这都是有效的。

在我现在能回忆起的所有语言中，闭包都是通过在定义时捕获封闭变量来工作的。例如，在Java中，在属于外部类的内部类中访问的每个局部在创建时都会传递给内部类，可以将其视为内部类构造的另一个参数。C更明确地说明了它捕获哪些变量，但在其他方面，它的工作原理是相同的——lambda对象只是在创建时将这些变量（通过值或通过引用，取决于指令）传递给它。在任何情况下，捕获的对象都与捕获后的原始对象不同（它们可能都是指向同一位置的指针，但这并不意味着它们是同一个对象），因此应该不难解析。

Answer 2

表示闭包的通常方法是创建一个包含函数指针本身及其环境的结构。表示环境的最简单方法是作为指向外部函数堆栈框架的指针。然后，内部函数可以在访问外部函数的变量时简单地取消引用该指针（当然是给定变量的偏移量）。

但是，您必须考虑另一个问题：如果foo返回bar，然后在foo已经返回后调用bar怎么办？在这种情况下，指向foo的堆栈帧的指针将无效，因为该堆栈帧此时将不再存在。因此，如果您想允许这种情况（而不是简单地使返回函数非法），您需要另一种解决方案。

一种常见的解决方案是将所有局部变量表示为指向堆分配值的指针，并将所有这些指针的副本存储在函数的结构中。

另一种解决方案是限制闭包，这样外部函数的变量只有在从未重新分配的情况下才能被内部函数访问。这就是Java8中的闭包所做的。然后结构可以简单地包含变量的副本而不是指针。