编译器设计 - 符号表

符号表是编译器创建和维护的重要数据结构，用于存储有关各种实体（如变量名、函数名、对象、类、接口等）出现的信息。符号表由编译器的分析和综合部分使用。

符号表可能用于以下目的，具体取决于所使用的语言：

将所有实体的名称以结构化形式存储在一个位置。
验证变量是否已声明。
通过验证源代码中的赋值和表达式在语义上是否正确来实现类型检查。
确定名称的范围（范围解析）。

符号表只是一个表，可以是线性的，也可以是哈希表。它为每个名称维护一个条目，格式如下：

<symbol name,  type,  attribute>

例如，如果符号表必须存储有关以下变量声明的信息：

static int interest;

那么它应该存储如下条目：

<interest, int, static>

属性子句包含与名称相关的条目。

实现

如果编译器要处理少量数据，那么符号表可以实现为无序列表，这很容易编码，但它只适用于小型表。符号表可以通过以下方式之一实现：

线性（排序或未排序）列表
二叉搜索树
哈希表

其中，符号表大多以哈希表的形式实现，其中源代码符号本身被视为哈希函数的键，返回值是有关符号的信息。

操作

符号表（无论是线性还是哈希）都应提供以下操作。

insert()

此操作在分析阶段更常用，即编译器的前半部分，在此阶段识别标记并将名称存储在表中。此操作用于在符号表中添加有关源代码中出现的唯一名称的信息。名称的存储格式或结构取决于手头的编译器。

源代码中符号的属性是与该符号相关的信息。此信息包含符号的值、状态、范围和类型。insert() 函数将符号及其属性作为参数，并将信息存储在符号表中。

例如：

int a;

should be processed by the compiler as:

insert(a, int);

lookup()

lookup() 操作用于在符号表中搜索名称以确定：

符号是否存在于表中。
符号是否在使用前已声明。
名称是否在范围内使用。
符号是否已初始化。
符号是否已多次声明。

lookup() 函数的格式因编程语言而异。基本格式应符合以下要求：

lookup(symbol)

如果符号不存在于符号表中，则此方法返回 0（零）。如果符号存在于符号表中，它将返回存储在表中的符号属性。

范围管理

编译器维护两种类型的符号表：全局符号表，可由所有过程访问；范围符号表，为程序中的每个范围创建。

为了确定名称的范围，符号表按层次结构排列，如下例所示：

. . . 
int value=10;

void pro_one()
   {
   int one_1;
   int one_2;
   
      {              \
      int one_3;      |_  inner scope 1 
      int one_4;      | 
      }              /
      
   int one_5; 
   
      {              \   
      int one_6;      |_  inner scope 2
      int one_7;      |
      }              /
   }
   
void pro_two()
   {
   int two_1;
   int two_2;
   
      {              \
      int two_3;      |_  inner scope 3
      int two_4;      |
      }              /
      
   int two_5;
   }
. . .

上述程序可以用符号表的层次结构来表示：