编译器设计 - 符号表

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

根据手头的语言，符号表可以服务于以下目的

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

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

<symbol name,  type,  attribute>

例如，如果符号表需要存储以下变量声明的信息：

static int interest;

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

<interest, int, static>

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

实现

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

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

在所有方法中，符号表大多实现为哈希表，其中源代码符号本身被视为哈希函数的键，返回值是关于该符号的信息。

操作

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

插入（insert()）

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

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

例如：

int a;

应由编译器处理为：

insert(a, int);

查找（lookup()）

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

符号是否存在于表中。
在使用之前是否已声明。
名称是否在作用域中使用。
符号是否已初始化。
符号是否声明多次。

lookup() 函数的格式根据编程语言而有所不同。基本格式应与以下格式匹配：

lookup(symbol)

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

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

作用域管理

编译器维护两种类型的符号表：一个全局符号表，所有过程都可以访问它；以及为程序中的每个作用域创建的作用域符号表。

为了确定名称的作用域，符号表以分层结构排列，如下例所示：

. . . 
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;
   }
. . .

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

全局符号表包含一个全局变量（int value）和两个过程名称的名称，这些名称应可供上面显示的所有子节点使用。pro_one 符号表（及其所有子表）中提到的名称不适用于 pro_two 符号及其子表。

此符号表数据结构层次结构存储在语义分析器中，并且每当需要在符号表中搜索名称时，它都会使用以下算法进行搜索：

首先将在当前作用域（即当前符号表）中搜索符号。
如果找到名称，则搜索完成，否则将在父符号表中搜索，直到：
找到名称或已在全局符号表中搜索过该名称。

打印页面