上一节:
下一节:

  编译器设计 - 符号表

  • 简述

    符号表是编译器创建和维护的重要数据结构，用于存储变量名、函数名、对象、类、接口等各种实体出现的信息。符号表用于分析和综合编译器的一部分。
    根据手头的语言，符号表可以用于以下目的：
    • 以结构化形式将所有实体的名称存储在一个位置。
    • 验证是否已声明变量。
    • 要实现类型检查，通过验证源代码中的赋值和表达式在语义上是否正确。
    • 确定名称的范围（范围解析）。
    符号表只是一个可以是线性表或哈希表的表。它以下列格式为每个名称维护一个条目： 
    
<symbol name,  type,  attribute>
    例如，如果符号表必须存储有关以下变量声明的信息： 
    
static int interest;
    那么它应该存储以下条目： 
    
<interest, int, static>
    属性子句包含与名称相关的条目。

  • 执行

    如果编译器要处理少量数据，那么符号表可以实现为无序列表，这样容易编码，但只适用于小表。符号表可以通过以下方式之一实现：
    • 线性（排序或未排序）列表
    • 二叉搜索树
    • 哈希表
    其中，符号表大多以哈希表的形式实现，其中源代码符号本身被视为哈希函数的键，返回值是符号的相关信息。

  • 运营

    一个符号表，无论是线性的还是散列的，都应该提供以下操作。

    插入（）

    此操作更常用于分析阶段，即编译器的前半部分，其中标识了标记并将名称存储在表中。此操作用于在符号表中添加有关源代码中出现的唯一名称的信息。存储名称的格式或结构取决于手头的编译器。
    源代码中符号的属性是与该符号相关的信息。此信息包含有关符号的值、状态、范围和类型。insert() 函数将符号及其属性作为参数，并将信息存储在符号表中。
    例如： 
    
int a;
    应该由编译器处理为： 
    
insert(a, int);

    抬头（）

    lookup() 操作用于在符号表中搜索名称以确定：
    • 如果符号存在于表中。
    • 如果它是在使用之前声明的。
    • 如果名称在范围内使用。
    • 如果符号已初始化。
    • 如果符号多次声明。
    lookup() 函数的格式因编程语言而异。基本格式应符合以下条件： 
    
lookup(symbol)
    如果符号表中不存在该符号，则此方法返回 0（零）。如果符号存在于符号表中，则返回其存储在表中的属性。

  • 范围管理

    编译器维护两种类型的符号表：global symbol table所有程序都可以访问它，并且scope symbol tables为程序中的每个范围创建的。
    为了确定名称的范围，符号表按层次结构排列，如下例所示： 
    
. . . 
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 值）的名称和两个过程名称，这些名称应该可用于上面显示的所有子节点。pro_one 符号表（及其所有子表）中提到的名称不适用于 pro_two 符号及其子表。
    此符号表数据结构层次结构存储在语义分析器中，每当需要在符号表中搜索名称时，都会使用以下算法进行搜索：
    • 首先将在当前范围内搜索一个符号，即当前符号表。
    • 如果找到名称，则搜索完成，否则将在父符号表中搜索，直到，
    • 找到该名称或已在全局符号表中搜索该名称。
上一节:
下一节: