制作玩具语言解释器、AST 变量和作用域
Making a toy language interpreter, AST variables and scopes
如标题所示，我最近开始与朋友一起用 c++ 开发 parser/interpreter，稍后将集成到一个更大的项目中（如果可行的话）；我们决定开始制作我们将用于抽象语法树的 类 ，稍后我们将在适当的解析器端工作。
我们从范围和变量的概念开始。通过一些搜索，我们发现了一个示例，其中每个作用域都有一个符号 table 和一个 link 到前一个作用域的符号，因此如果在当前作用域中找不到变量，它将在上一个作用域中查找等等。
我必须从这个例子中指出的第一件事是，试图访问一个在堆栈中有很多作用域甚至不存在的变量会产生很高的成本（最坏的情况与堆栈深度一样高）。我当时想……不，我们可以做得更好。
我们思考的结果如下：
程序根部的单个符号 table，由字符串映射到变量堆栈
map<string, stack<variable>> table;
然后每个作用域将包含一组字符串，这些字符串将是在该作用域中分配的字符串
set<string> allocated;
分配变量 "a" 时，其名称的字符串被添加到该作用域本地集合中，然后一个新变量被推入 e table (table["a"].push()).
访问该变量以进行编辑或阅读将完成阅读同一位置的顶部 (table["a"].top())
最后，范围析构函数将循环遍历分配的所有元素，并从映射中的堆栈中弹出。
for(variable_name in allocated)
{
table[variable_name].pop();
}
这种方式无论如何都是分配，读写O(1)。
这是我的 2 个问题：
1) 必须为 table 和作用域中的每个变量保存字符串，并且必须在作用域的末尾循环遍历所有变量，与 many-tables-system 哪个只需要删除一个数组？
2) 我发现的这个例子是 not-so-efficient 故意作为一个非常初学者教程的东西，或者我缺少一些东西让它比我和我的朋友提出的想法更有价值？
这里没有绝对的答案；这取决于您的语言范围的精确性质以及您的编程风格。我的建议是先让它工作，然后看看它是否需要改进。无论您选择作为符号 table 实现的什么，请确保将实现细节隐藏在 ADT 原型后面，这将定义符号 table 的行为。然后，如果需要，您可以轻松地换成不同的实现。
无论如何，这里有几个数据点：
范围嵌套通常不是很深。事实上，对于大多数语言来说，深度嵌套的范围被认为是糟糕的风格。
您的提案涉及为每个范围创建一个散列 table。那不是真的必要；您可以使用单个散列 table 来完成所有查找，并使用堆栈来标记范围边界。符号 table 是 unordered_map<name, definition>，作用域堆栈是 stack<pair<name, definition>>。 （我假设是 C++。在这里，name 可能只是 std::string 的别名，但请参见下文。definition 包含您需要为每个符号存储的元数据。没有必要保留它们像那样分开；您可以使用单一类型，然后使用 set 而不是 map。）作用域堆栈中的 definition 是来自某个外部作用域的定义或指示在外部范围内，变量是未定义的。还需要有一个标记值（用于名称或定义），它指示范围的开始。
当你进入一个作用域时，你将哨兵压入作用域堆栈。然后每次定义一个变量时，它以前的定义被压入作用域栈，新的定义被存储到符号 table 中。当您离开作用域时，您会将作用域堆栈弹出回到最后一个哨兵，并在您离开时用其先前的定义替换每个变量。
典型语言中有许多不同种类的作用域。这里有几个例子：
闭包作用域。如果允许在函数内部定义函数，那么一些外部作用域实际上就是闭包。这些需要与同一函数中外部块中的范围不同的处理，尽管符号 table 处理除了正确跟踪元数据之外并没有真正的不同。
全局范围and/or模块范围。
复合对象 ("class") 成员名称范围。它们不像块范围那样嵌套，但根据您的语言的名称查找算法，它们可能仍然是链式名称搜索的一部分。
创建名称 std::string 对象显然更简单，但您最终会创建大量重复的字符串，与其他字符串相比，这些字符串需要是字符串。现代计算机的速度足够快，none 很重要，但您可能仍要考虑对其进行优化。我更喜欢 "intern" 字符串，方法是将它们放入 std::set<std::string> （或等效的），然后使用元素指针而不是字符串本身。这有两个好处：
每个字符串只存储和分配一次，节省了分配开销。现代分配库非常快，但保留同一个字符串的无数个副本仍然没有意义，每次在程序中使用一个名称。将名称保留在实习生 table 中可能会增加它们的生命周期，但实际上这不是什么大问题，特别是因为许多程序员在不同的范围内回收名称。
可以通过指针比较来比较名称，而不是逐字符比较。这要快一点，因为它不需要循环。同样，现代硬件使这一点变得不必要，但它仍然是一个优点。如果您随后使用指针而不是字符串作为符号 table 键，则可以节省每次查找时计算键的哈希值的开销。这是另一个可衡量但不是革命性的改进。
如标题所示，我最近开始与朋友一起用 c++ 开发 parser/interpreter，稍后将集成到一个更大的项目中（如果可行的话）；我们决定开始制作我们将用于抽象语法树的 类 ，稍后我们将在适当的解析器端工作。 我们从范围和变量的概念开始。通过一些搜索，我们发现了一个示例，其中每个作用域都有一个符号 table 和一个 link 到前一个作用域的符号，因此如果在当前作用域中找不到变量，它将在上一个作用域中查找等等。 我必须从这个例子中指出的第一件事是，试图访问一个在堆栈中有很多作用域甚至不存在的变量会产生很高的成本（最坏的情况与堆栈深度一样高）。我当时想……不，我们可以做得更好。
我们思考的结果如下： 程序根部的单个符号 table，由字符串映射到变量堆栈
map<string, stack<variable>> table;
然后每个作用域将包含一组字符串，这些字符串将是在该作用域中分配的字符串
set<string> allocated;
分配变量 "a" 时，其名称的字符串被添加到该作用域本地集合中，然后一个新变量被推入 e table (table["a"].push()). 访问该变量以进行编辑或阅读将完成阅读同一位置的顶部 (table["a"].top()) 最后，范围析构函数将循环遍历分配的所有元素，并从映射中的堆栈中弹出。
for(variable_name in allocated)
{
table[variable_name].pop();
}
这种方式无论如何都是分配，读写O(1)。 这是我的 2 个问题：
1) 必须为 table 和作用域中的每个变量保存字符串，并且必须在作用域的末尾循环遍历所有变量，与 many-tables-system 哪个只需要删除一个数组？
2) 我发现的这个例子是 not-so-efficient 故意作为一个非常初学者教程的东西，或者我缺少一些东西让它比我和我的朋友提出的想法更有价值？
这里没有绝对的答案；这取决于您的语言范围的精确性质以及您的编程风格。我的建议是先让它工作，然后看看它是否需要改进。无论您选择作为符号 table 实现的什么，请确保将实现细节隐藏在 ADT 原型后面，这将定义符号 table 的行为。然后，如果需要，您可以轻松地换成不同的实现。
无论如何，这里有几个数据点：
范围嵌套通常不是很深。事实上，对于大多数语言来说，深度嵌套的范围被认为是糟糕的风格。
您的提案涉及为每个范围创建一个散列 table。那不是真的必要；您可以使用单个散列 table 来完成所有查找，并使用堆栈来标记范围边界。符号 table 是
unordered_map<name, definition>，作用域堆栈是stack<pair<name, definition>>。 （我假设是 C++。在这里，name可能只是std::string的别名，但请参见下文。definition包含您需要为每个符号存储的元数据。没有必要保留它们像那样分开；您可以使用单一类型，然后使用set而不是map。）作用域堆栈中的definition是来自某个外部作用域的定义或指示在外部范围内，变量是未定义的。还需要有一个标记值（用于名称或定义），它指示范围的开始。当你进入一个作用域时，你将哨兵压入作用域堆栈。然后每次定义一个变量时，它以前的定义被压入作用域栈，新的定义被存储到符号 table 中。当您离开作用域时，您会将作用域堆栈弹出回到最后一个哨兵，并在您离开时用其先前的定义替换每个变量。
典型语言中有许多不同种类的作用域。这里有几个例子：
闭包作用域。如果允许在函数内部定义函数，那么一些外部作用域实际上就是闭包。这些需要与同一函数中外部块中的范围不同的处理，尽管符号 table 处理除了正确跟踪元数据之外并没有真正的不同。
全局范围and/or模块范围。
复合对象 ("class") 成员名称范围。它们不像块范围那样嵌套，但根据您的语言的名称查找算法，它们可能仍然是链式名称搜索的一部分。
创建名称
std::string对象显然更简单，但您最终会创建大量重复的字符串，与其他字符串相比，这些字符串需要是字符串。现代计算机的速度足够快，none 很重要，但您可能仍要考虑对其进行优化。我更喜欢 "intern" 字符串，方法是将它们放入std::set<std::string>（或等效的），然后使用元素指针而不是字符串本身。这有两个好处：每个字符串只存储和分配一次，节省了分配开销。现代分配库非常快，但保留同一个字符串的无数个副本仍然没有意义，每次在程序中使用一个名称。将名称保留在实习生 table 中可能会增加它们的生命周期，但实际上这不是什么大问题，特别是因为许多程序员在不同的范围内回收名称。
可以通过指针比较来比较名称，而不是逐字符比较。这要快一点，因为它不需要循环。同样，现代硬件使这一点变得不必要，但它仍然是一个优点。如果您随后使用指针而不是字符串作为符号 table 键，则可以节省每次查找时计算键的哈希值的开销。这是另一个可衡量但不是革命性的改进。