我应该提供什么样的数据结构来处理我的编译器中的范围？

Question

我正在 ubuntu 中使用 flex 和 bisonc++ 开发一个“玩具”编译器，它将类似 C 的输入语言编译成优化的 C++。在输入语言中包含一个main函数（必须有）并且可以在main之外有optionals函数，例如：

int myFunc1()
{
  // some functionality
}

int main()
{

}

void myFunf2()
{
  // some functionality
}

在语义分析部分我遇到了麻烦，我不知道如何处理范围，我现在不知道，我应该提供什么样的符号 table 结构或者我应该提供什么样的数据结构针对这个问题创建。我的问题有一个复杂的案例（语义分析部分）：

int Name() // here "Name" is a function name
{
  int Name = 0; // Here Name is a variable name
  return Name // the function returns with the variable
}

int main()
{
  int Name = 5; // Here name is a variable name, it is not the same variable which is in the Name() 
                   function, it is a **different** **variable**
  if ()
  {
    // int Name = 6; <- Name variable cannot be redeclared in this inner if block
    // A variable can be declared once in a function it cannot be redeclared in an if, while, etc. block
  }
}

void Name2()
{
  int Name = 55; // here Name is also a different variable from the others
}

Answer 1

范围符号的最简单实现 table 是一个可搜索的堆栈，能够存储符号和范围标记。操作简单：

进入作用域: 推送一个作用域标记。
声明一个变量: 推送声明，在确认声明的变量没有在本地声明后。
退出作用域：弹出堆栈直到作用域标记被移除。
查找名称的当前绑定：向下搜索堆栈（即从最新条目开始）直到找到该名称的声明。

如果您以后决定像 C 那样允许本地隐藏声明，也可以使用该数据结构。

您在堆栈上的声明对象中存储的内容在很大程度上取决于您的编译器的性质。在最简单的情况下，局部变量只需要与当前堆栈帧中的类型和偏移量相关联。由于范围也有效地界定了变量的生命周期，您可以使用范围标记将当前偏移量保留在堆栈帧中，从而允许您在退出范围时恢复偏移量。

全局变量需要不同的处理方式，部分原因是函数名可以存储在全局符号 table 中，部分原因是全局变量的存储分配遵循不同的规则。因此，将全局变量保存在不同的容器中可能很方便，可能使用类似散列的东西 table，如果在符号堆栈中找不到名称，则搜索此容器。

顺便说一句，我知道建议对名称进行线性搜索总是会引起注意。事实上，它在执行时间方面并不是最优的。但是，在您项目的这个阶段，更重要的是专注于让事情正常进行；您以后总是可以添加更有效的查找过程。（确保你的符号 table 提供了一个简单且文档完善的编程接口。这将使以后修改实现变得容易得多。）无论如何，这真的不是什么大问题。经验表明，绝大多数可见名称在任何时候都是全局的（对应于库函数，其中许多从未被给定的源文本实际使用过）。本地名称通常在其声明附近使用。因此，花在线性查找上的时间不会成为交易破坏者。如果您担心，请分析您的编译器以查看它是否显示出重要意义，然后再花费大量精力进行优化。

如果可以在范围内声明全局变量（就像在 C 中一样，使用 extern 关键字），则会出现额外的复杂情况。（这可能不适用于您的语言；听起来您并没有考虑将程序分布在多个源文件上。但您可能有一天会想添加它。）要正确实现链接，您需要清楚两者之间的区别作用域名称和外部链接对象的名称。它们是相同的名称，但它们有不同的规则：局部范围的名称仅在声明它的范围内可见，而外部链接对象的名称将对链接器可见，因此需要将其添加到另一个符号不通过名称查找搜索的存储库。此外，可以在多个范围内声明相同的外部对象。

所有这些都假定您没有使用您的语言的嵌套函数声明。 C 没有这些，所以这似乎是一个安全的假设。（将闭包翻译成 C++ 将是一个额外的挑战，我认为这超出了本 post 的范围。）

我应该提供什么样的数据结构来处理我的编译器中的范围？

What kind of data structure should I provide to handle scopes in my compiler?

c++

bison

semantic-analysis

symbol-table

bisonc++