如何管理符号表中的变量范围

Question

我正在编写一个玩具编译器，我使用ANTLR生成了一个工作的C++解析器。我做了一些研究，发现处理符号表中的作用域的最好方法是为每个作用域创建一个不同的表。我计划使用堆栈(进入作用域时推送，退出时弹出)来实现这一点，但我意识到，为了访问来自高校的变量，我需要能够访问不在堆栈顶部的作用域。这会变得有点混乱，因为(理论上)可以有数百个作用域，而弹出所有这些以找到变量将是无效的。是否有更好的方法来实现这一点？

Answer 1

实际上，对于一个程序来说，拥有“数百”嵌套作用域是非常罕见的。例如，C标准只需要编译器来处理“127个块嵌套级别”Note 1。

然而，在我的第一种玩具语言中，有一个非常简单的算法，它在半个多世纪前就已经使用过了；我怀疑我自己是否想到了它，但是很久以前，我想不出它的来源是什么。

其思想是使用单个关联数组(“哈希表”)，其解析中任意点的键是当前可见的标识符(“在范围内”)。每个作用域都是一个简单的名称线性数组，每个名称都与一些有关名称的信息相关联，例如定义变量Note 2的类型。关联数组中的值包含一个指针，指向当前定义关联名称的作用域，以及该定义的作用域数组中的索引。

还有一个下推堆栈，它包含由名称及其先前定义(即名称的范围和框架索引)组成的元组。每次遇到名称的定义时，在将名称输入符号表关联数组之前，名称及其先前的定义(或Null标记)被推入该堆栈。

最后，还有另一个范围的下推堆栈；每次输入范围时，都会将对定义下推堆栈当前顶部的引用推送到范围堆栈上，当作用域结束时，定义堆栈将弹出回范围条目所在的位置。当定义堆栈弹出时，关联数组中的每个名称条目将被保存在范围条目的定义堆栈上的数据替换。

这一切都很有效，所有的操作基本上都是恒定时间Note 3，我仍然认为它是一个相当不错的解决方案。但是有一种观点认为，哈希表的开销是不合理的，因为大多数名称引用接近于名称定义，因此在下推定义堆栈中进行线性搜索平均速度可能更快，因为它比哈希表查找要友好得多。不过，我没有费心去做基准测试。

请注意，许多真实语言的名称查找规则要复杂得多，您可能需要处理多个名称空间(结构成员、显式名称空间等)，它们具有不同的嵌套规则。(甚至还没有开始讨论在C++中查找名称的复杂性。)

备注

1. 如果您想获得技术，它甚至不要求编译器处理任何代码块嵌套深度不超过127个级别。它要求“实现至少能够翻译和执行至少一个包含127个嵌套级块的实例的程序”，这实际上是一个完全没有效力的限制，只是作为一个指南。但是，除了机器生成的代码之外，生产代码似乎不太可能达到这个限制。

1. 数组的开销比哈希表小得多，单个大型哈希表的开销比一堆小哈希表少得多。这里的想法是，除了将源代码中的名称与适当的定义相关联之外，不需要关联数组。在实际实现调用帧时，只需按顺序遍历已定义的变量即可；除了调试之外，它们的名称在这一点上可能无关紧要。

1. 作用域退出需要时间与该作用域中定义的名称数成线性关系，但是如果从摊销时间的角度来看它，您可以想到在作用域期间推送名称时在范围出口处弹出名称的成本，从中我们可以看到，维护定义和作用域堆栈的总成本基本上与程序中的声明数成线性关系，或者是每个定义的固定时间。