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

Question

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

int myFunc1()
{
  // some functionality
}

int main()
{

}

void myFunf2()
{
  // some functionality
}

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

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

范围符号表的最简单实现是能够同时存储符号和范围标记的可搜索堆栈。操作简单：

• Enter scope：Push a scope marker.
• Declare a变量：Push声明，在验证声明变量不是本地的declared.
• Exit作用域：弹出堆栈，直到范围标记为removed.
• Find当前绑定到名称：搜索堆栈(即从最新条目开始)，直到找到该名称的声明为止。

如果您稍后决定允许本地阴影声明(如C)，也可以使用该数据结构。

存储在堆栈上的声明对象中的内容高度依赖于编译器的性质。在最简单的情况下，局部变量只需要与当前堆栈帧中的类型和偏移量相关联。由于作用域也有效地分隔了变量的生存期，所以可以使用范围标记将当前偏移量保留在堆栈框架中，允许您在退出范围时恢复偏移量。

全局变量需要进行不同的处理，部分原因是函数名可以存储在全局符号表中，部分原因是全局变量存储的分配遵循不同的规则。因此，将全局数据保存在不同的容器中可能很方便，可能使用类似哈希表的方法，如果在符号堆栈中找不到名称，则搜索这个容器。

顺便说一句，我知道，建议对名字进行线性搜索总是会引起人们的注意。实际上，就执行时间而言，这并不是最优的。然而，在您的项目的这个阶段，更重要的是集中精力工作；您以后总是可以添加一个更有效的查找过程。(请确保您的符号表提供了一个简单且文档良好的编程接口。这将使以后修改实现变得更加容易。)不管怎样，这真的不是什么大问题。经验表明，绝大多数可见名称在任何一点都是全局的(对应于库函数，其中许多名称实际上从未被给定的源文本使用)。本地名称通常在其声明附近使用。因此，花在线性查找上的时间不会是一个交易的破坏者。如果这让您感到担忧，那么在花费大量精力进行优化之前，请对编译器进行分析，看看它是否具有重要意义。

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

所有这些假设您的语言中没有嵌套函数声明。C没有这些，所以这似乎是一个安全的假设。(将闭包转换为C++将是一个额外的挑战，我认为这超出了本文的范围。)