使用散列表构建符号表

Question

我想使用散列表构建符号表。总体思路是：

int alpha; 
2 int beta; 
3 alpha = 0; // the alpha declared in line 1 
4 beta = 0; // the beta declared in line 2 
5 gamma = 0; // Error! gamma hasn't been declared. 
6 { 
7 int beta; // This beta shadows the one declared in line 2. 
8 int gamma; 
9 alpha = 0; // the alpha declared in line 1 
10 beta = 0; // the beta declared in line 7 
11 gamma = 0; // the gamma declared in line 8 
12 } 

等等。您只能使用矢量，列表，堆栈和队列库，并尝试尽可能快地完成它。 我的想法是在每个作用域上，我在列表中声明散列表并将所有信息保存到该表中，并且每当我有新的作用域时，我都会将新的散列表push_back到列表中。 但是，当程序正在寻找范围远远的项目时，这种方法似乎很慢，因为您必须查找每个范围才能找到该项目。

你们有什么想法来实现这个比这个更快的范围？它应该是更快的方式，因为我的实现速度比“他们提供的慢速版”慢

非常感谢！

Answer 1

这是一个好主意。在大多数语言中，范围很少嵌套得很深，可能平均有3或4个嵌套范围。所以我不会担心“远，远”的事情，因为这些会是病理性的情况。

Answer 2

只有一个哈希表的所有内容和一堆上下文对象。每当看到一个'{'时，在堆栈上推一个新对象。当你隐藏一个变量时，请记住上下文对象中的旧符号，并将其覆盖在散列表中。当你看到一个'}'并弹出上下文时，恢复你在那里记住的符号。

Answer 3

当我这样做时，我使用散列表符号，而不是实体。 对于每个符号，我都有一个实体列表。每个实体在两个 列表中，一个来自符号，另一个来自范围。来自符号的列表 像堆栈一样管理：当我访问符号时，范围内的 实体始终是列表中的第一个。当我离开示波器时，我走过它的实体列表，并从 符号列表中删除它们。这是前一段时间，在STL之前（甚至在C++之前）; I 手工实现了所有内容，并使用侵入式链接对 列表进行了设置，使得我可以从列表中删除元素 ，而不必知道列表本身的位置。 （这是 用手写双链表比较容易。）今天，用STL（并且具有访问的局部性的重要性），我可能简单地将 放在每个实体的列表头部。对于STL和 地方性的考虑，对于每个实体，我可能使用std::vector作为列表 （因此符号表是std::string到 std::vector的地图）。符号表查找，一旦找到条目，简单地 在向量上调用back()（在检查它不是空的，如果 当矢量变空时不清除条目）。在 中创建新实体时，在新范围内，您可以在矢量 上调用push_back，并将该矢量的地址保存在示波器的条目中（ std::stack的std::vector<std::vector<Entity>*>）;当离开 作用域时，您遍历堆栈顶部的向量，在其所有条目上调用 pop_back，然后将其从堆栈中弹出。 （和 显然，当进入一个新的范围时，你push一个新的空的矢量 范围堆栈。）

维护双列表意味着对于所有操作，您知道 究竟是哪个元素要访问，而不必遍历 任何东西;从来没有任何访问实体，看看它是否是你正在寻找的一个 。在我的日子里，这很简单，但代码很多，需要非常小心，而且我的实现可能不会那么快，因为地理位置不好。今天，使用STL的 ，您需要的代码少得多，并且通过对所有 列表使用std::vector，您会获得稍好的局部性;你仍然必须小心， ，这样你就不会最终保存会失效的迭代器。 （但是如上所述实现，您不需要;所有访问都始终是向量的最后一个元素，因此保存向量本身的地址是足够的。当然，前提是您的散列值 实现不会移动向量。）