符号表的实现

本文概述

• 实现符号表
• lookup()

符号表是在编译器中使用的重要数据结构。

符号表用于存储有关各种实体（例如对象, 类, 变量名, 接口, 函数名等）的出现的信息。在分析和合成阶段均使用该表。

符号表用于以下目的：

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

符号表可以是线性表或哈希表。使用以下格式, 它维护每个名称的条目。

<symbol name, type, attribute>

例如, 假设一个变量存储有关以下变量声明的信息：

static int salary

然后, 它以以下格式存储条目：

<salary, int, static>

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

实现符号表

如果使用编译器来处理少量数据, 则可以在无序列表中实现符号表。

可以使用以下技术之一来实现符号表：

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

符号表主要实现为哈希表。

运作方式

符号表提供以下操作：

插入 ()

• 当识别出令牌并将名称存储在表中时, 在分析阶段更频繁地使用Insert()操作。
• insert()操作用于将信息插入符号表中, 就像源代码中出现的唯一名称一样。
• 在源代码中, 符号的属性是与该符号关联的信息。该信息包含有关符号的状态, 值, 类型和范围。
• insert()函数采用符号形式的符号及其值。

例如：

int x;

编译器应按以下方式处理：

insert (x, int)

lookup()

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

• 表中存在符号。
• 使用符号之前的声明。
• 检查名称是否在范围中使用。
• 符号的初始化。
• 检查名称是否多次声明。

lookup()函数的基本格式如下：

lookup (symbol)

该格式根据编程语言而有所不同。