如何管理符号 table 中的变量范围
How to manage variable scopes in symbol table
我正在编写一个玩具编译器，并使用 ANTLR 生成了一个可用的 C++ 解析器。我做了一些研究，发现处理符号 table 范围的最佳方法是为每个范围创建不同的 table。我计划使用堆栈来实现这一点（进入范围时压入，退出时弹出）但我意识到要访问高中的变量，我需要能够访问不在堆栈顶部的范围.这会变得有点混乱，因为（理论上）可能有数百个范围，并且弹出所有这些范围以查找变量将是低效的。有没有更好的方法来实现这个？
一个程序拥有“数百个”嵌套作用域实际上并不常见。例如，C 标准仅要求编译器处理“127 层嵌套块”[注 1]。
但是，我在我的第一门玩具语言中使用了一个非常简单的算法，那已经是半个多世纪以前的事了；我怀疑这是否是我自己想出来的，但回想起来源可能已经太久远了。
想法是使用单个关联数组（“hash table”），其在解析中任何一点的键都是当前可见的标识符（“在范围内”）。每个范围都是一个简单的名称线性数组，每个名称都与一些有关名称的信息相关联，例如定义变量的类型 [注 2]。关联数组中的值包含指向当前定义关联名称的范围的指针，以及该定义的范围数组中的索引。
还有一个下推堆栈，其中包含由名称及其先前定义（即名称的范围和帧索引）组成的元组。每次遇到名称的定义时，在将名称输入符号 table 关联数组之前，名称及其先前的定义（或 Null 标记）被推入该堆栈。
最后，还有一个作用域的下推栈；每次进入范围时，都会将对定义下推堆栈当前顶部的引用推送到范围堆栈中，并且当范围结束时，定义堆栈会弹出回到范围入口处的位置。当弹出定义堆栈时，关联数组中的每个名称条目将替换为在作用域条目处保存在定义堆栈中的数据。
这一切都非常有效；所有的操作基本上都是常数时间[注3]，我仍然认为这是一个相当不错的解决方案。但是有一个论点认为散列的开销 table 是不合理的，因为大多数名称引用都接近名称定义，因此在定义的下推堆栈中进行线性搜索可能更快 平均而言，因为它比哈希-table 查找对缓存更友好。不过，我没有费心去进行基准测试。
请注意，许多真实语言的名称查找规则要复杂得多，您可能需要使用不同的嵌套规则处理多个名称空间（结构成员、显式名称空间等）。 （甚至没有开始讨论 C++ 中名称查找的复杂性。）
备注
如果您想获得技术知识，甚至不需要编译器处理嵌套深度不超过 127 层的块的任何程序。它要求“一个实现应该能够翻译和执行至少一个包含至少一个 [127 层嵌套块] 实例的程序”，这实际上是一个完全没有牙齿的限制，仅作为指导。但是除了机器生成的代码，生产代码似乎不太可能接近这个限制。
一个数组的开销比散列小得多table，单个大散列table比一堆小散列table的开销小得多秒。这里的想法是，除了将源代码中的名称与适当的定义相关联之外，不需要关联数组。真正实现调用框架时，只需要按顺序循环遍历定义的变量即可；除了调试之外，那时他们的名字可能无关紧要。
作用域退出所花费的时间与该作用域中定义的名称数量呈线性关系，但是如果从摊销时间的角度来看，您可以想到在作用域中弹出名称的成本exit 在范围内推送名称的那一刻被考虑在内，从中我们可以看到维护定义和范围堆栈的总成本基本上与程序中的声明数量或每个定义的恒定时间成线性关系。
我正在编写一个玩具编译器，并使用 ANTLR 生成了一个可用的 C++ 解析器。我做了一些研究，发现处理符号 table 范围的最佳方法是为每个范围创建不同的 table。我计划使用堆栈来实现这一点（进入范围时压入，退出时弹出）但我意识到要访问高中的变量，我需要能够访问不在堆栈顶部的范围.这会变得有点混乱，因为（理论上）可能有数百个范围，并且弹出所有这些范围以查找变量将是低效的。有没有更好的方法来实现这个？
一个程序拥有“数百个”嵌套作用域实际上并不常见。例如，C 标准仅要求编译器处理“127 层嵌套块”[注 1]。
但是，我在我的第一门玩具语言中使用了一个非常简单的算法，那已经是半个多世纪以前的事了；我怀疑这是否是我自己想出来的，但回想起来源可能已经太久远了。
想法是使用单个关联数组（“hash table”），其在解析中任何一点的键都是当前可见的标识符（“在范围内”）。每个范围都是一个简单的名称线性数组，每个名称都与一些有关名称的信息相关联，例如定义变量的类型 [注 2]。关联数组中的值包含指向当前定义关联名称的范围的指针，以及该定义的范围数组中的索引。
还有一个下推堆栈，其中包含由名称及其先前定义（即名称的范围和帧索引）组成的元组。每次遇到名称的定义时，在将名称输入符号 table 关联数组之前，名称及其先前的定义（或 Null 标记）被推入该堆栈。
最后，还有一个作用域的下推栈；每次进入范围时，都会将对定义下推堆栈当前顶部的引用推送到范围堆栈中，并且当范围结束时，定义堆栈会弹出回到范围入口处的位置。当弹出定义堆栈时，关联数组中的每个名称条目将替换为在作用域条目处保存在定义堆栈中的数据。
这一切都非常有效；所有的操作基本上都是常数时间[注3]，我仍然认为这是一个相当不错的解决方案。但是有一个论点认为散列的开销 table 是不合理的，因为大多数名称引用都接近名称定义，因此在定义的下推堆栈中进行线性搜索可能更快 平均而言，因为它比哈希-table 查找对缓存更友好。不过，我没有费心去进行基准测试。
请注意，许多真实语言的名称查找规则要复杂得多，您可能需要使用不同的嵌套规则处理多个名称空间（结构成员、显式名称空间等）。 （甚至没有开始讨论 C++ 中名称查找的复杂性。）
备注
如果您想获得技术知识，甚至不需要编译器处理嵌套深度不超过 127 层的块的任何程序。它要求“一个实现应该能够翻译和执行至少一个包含至少一个 [127 层嵌套块] 实例的程序”，这实际上是一个完全没有牙齿的限制，仅作为指导。但是除了机器生成的代码，生产代码似乎不太可能接近这个限制。
一个数组的开销比散列小得多table，单个大散列table比一堆小散列table的开销小得多秒。这里的想法是，除了将源代码中的名称与适当的定义相关联之外，不需要关联数组。真正实现调用框架时，只需要按顺序循环遍历定义的变量即可；除了调试之外，那时他们的名字可能无关紧要。
作用域退出所花费的时间与该作用域中定义的名称数量呈线性关系，但是如果从摊销时间的角度来看，您可以想到在作用域中弹出名称的成本exit 在范围内推送名称的那一刻被考虑在内，从中我们可以看到维护定义和范围堆栈的总成本基本上与程序中的声明数量或每个定义的恒定时间成线性关系。