『compiler-4』symbol table

符号表管理技术

一、语义分析

• 语义分析任务：对识别出的各种语法成分进行语义分析，产生相应的中间代码

  • 上下文相关分析：标识符的作用域
  • 类型的一致性检查
  • 语义处理：主要处理声明语句 + 执行语句

  注意：上下文无关语法只能描述语法结构，而不能描述其语义，故只能把上下文相关分析交给语义分析
  通过语义分析的程序未必是“正确的程序”

---

二、符号表

• 符号表的概念：编译过程中用于记录源程序中的各种名字及其特性信息

  • 名字：存放标识符（如变量、函数等）的符号串

  • 特性：表示标识符的有关信息，有关信息包括：

    

• 符号表的组织方式：

  • 统一符号表：将任何符号都填入统一格式的符号表中；符号表的属性数量需兼顾信息量最大的符号

  • 分类符号表：对于不同种类的名字分别建立符号表

    注意：统一符号表查表简便、但浪费空间；分类符号表节省空间、但填查表不方便

  • 折中符号表：将所有符号的大部分信息组成统一格式的符号表，特殊信息另外附设表，两表用指针连接

• 非分程序的符号表：

  • 非分程序结构语言：每个可独立编译的程序单元不包含子模块

  • 标识符作用域：分为全局作用域 + 局部作用域

    • 具有全局作用域：子程序名 + 函数名 + 公共区名
    • 具有局部作用域：程序单元内部声明的变量（即局部变量）

  • 符号表管理：分为全局符号表 + 局部符号表

    1. 子程序名 + 函数名 + 公共区名填入全局符号表（具有全局作用域）
    2. 在子程序的声明部分读到标识符，先查本单元的表：
       • 若该符号已经存在，说明重复声明，报错
       • 若该符号不存在，则直接填表
    3. 在可执行语句部分读到标识符，先查本单元的表：
       • 若该符号已经存在，说明已被正确声明
       • 若该符号不存在，转去查全局符号表；若仍不存在说明未声明，报错
    4. 程序单元编译结束：释放该单元的局部符号表
    5. 整个程序编译完成：将全部符号表都释放掉

  • 符号表组织方式：

    • 无序符号表：仅按扫描顺序建立表，查表需要线性查找

    • 有序符号表：符号表按照变量名进行字典式排序，可使用折半查找，但插入开销大

      注意：平均查找长度：线性查表（ n + 1 / 2）；折半查表（\(\log\)n - 1）

    • 散列符号表：符号表地址 = Hash (标识符名称)

  ---

• 分程序的符号表：

  • 分程序结构语言：模块内部可以嵌套子模块
  • 作用域：标识符的作用域为定义该标识符的子程序
    • 函数内定义的标识符：作用域为函数体本身
    • 循环语句中定义的标识符：作用域为该循环语句
  • 符号表管理：
    1. 在声明部分读到标识符，先查本单元的表：
       • 若该符号已经存在，说明重复生命，报错
       • 若该符号不存在，则直接查表
    2. 在可执行语句部分读到标识符，先查本单元的表：
       • 若该符号已经存在，说明该符号已被正确声明
       • 若该符号不存在，逐层向外查直接外层的符号表；若在最外层表中仍未查到，报错
    3. 语言预先定义的标准标识符，用户不必声明即可使用，一般放于最外层表
    4. 编译中识别出是分程序开始时，执行定位操作；分程序结束时执行重定位操作

• 定位与重定位：

  • 定位：编译进入新的分程序时，为新声明的标识符建立一个子表

  • 重定位：编译离开当前分程序时，将符号表恢复为进入该分程序前的状态

---

• 栈式符号表：分程序结构语言最简单的符号表组织形式

  • 符号表管理：

    • 遇到标识符声明：考虑插入符号表
    • 分程序结尾：将当前分程序对应的符号表弹栈

  • 插入符号：先查找考虑栈顶（当前编译步骤）符号表的符号信息，若未重复声明则将其插入

  • 查表符号：从栈顶表到栈底表进行线性搜索，确保最内层定义的变量最先被找到

  • 定位与重定位：

    • 定位：在分程序索引表顶端创建新的分区索引，并将索引值填为当前TOP值（开辟新表）
    • 重定位：TOP下移至当前分区索引表顶端的元素值（移除顶表）

    

  • 带有哈希表的栈式符号表：hash(ident) = ident 符号在栈式符号表中的位置