程序设计语言语义的分类

静态语义

在编译阶段可以检查的语义。

标识符未声明，类型不匹配。

动态语义

目标程序运行时才能检查的语义。

除零，溢出错误。

主要任务

根据声明部分建立符号表。

符号表：是一种供编译器，用于保存有关源程序的各种信息的数据结构。符号表的每个条目中包含与一个标识符相关的信息，这些信息全面的反映改名字的属性以及他们在编译过程中的特征。

• 储存标识符的属性
• 检查语义错误
• 代码生成阶段作为地址分配的依据

在整个程序范围内检查常见的的语义错误

• 声明和使用相关的错误 建表就能发现
• 类型相关的语义 中间代码生成阶段

语义错误检查

常见语义错误

• 未声明就使用
  • 每个使用性标识符是否都有声明
  • 标号是否有声明
• 重复声明
  • 在同层内有无标识符被声明多次
  • 标号有无重复声明和重复定位错误，有无非法转入错误
• 如何检查
  • 声明填表
  • 使用查表
• 每当遇到新声明的标识符，查符号表
  • 如果当前有效的所有标识符中有重复名字的，是重复声明错误。
  • 否则生成它的属性信息，保存到符号表中。
• 每当遇到标识符的使用，查符号表
  • 如果没有找到，说明该标识符没有声明
  • 如果找到，则可获取该标识符的属性，进行进一步分析
• 类型相关的语义错误
  • if条件句传入是不是布尔类型
  • 运算符的分量类型是否相容
  • 赋值语句的左右部是否相容
  • 形参和实参的类型是否相容
  • 下标类型是否为所允许的类型

语义分析的实现

不作为独立的一遍

• 类型语义错误检查：可以安排在中间代码生成时进行
• 一般的语义检查：与语法分析相结合

独立一遍的语义分析

另一种语法树

都是由终极符组成。

语义分析处理后的结果

标识符在程序中的出现

• 声明性出现
• 使用性出现

标识符的种类

标识符的属性

• 名字
• 种类信息，常量，变量，函数
• 类型信息，整形，实形，字符型（语义分析，内存空间分配）
• 对不同类型的独特信息

类型的语义表示

• 类型的语义检查
• 分配空间的大小
• 类型可以分为下面几大类
  • 标准的类型
  • 自定义的数据类型
  • 结构数据类型：数组，记录
  • 指针类型
• 类型存储占用大小size属性：
  • 为了方便起见，规定RealSize取2，IntSize,BoolSize,CharSize取1
• 标准类型：大小种类

• 子界类型：定义在有序数据上

• 枚举类型

• 数组类型

• 结构体和联合体

• 指针类型

• 常量标识符

• 类型标识符

• 变量标识符

• 过程/函数标识符的内部表示

抽象地址

地址分配原则

• 静态分配：编译时，在编译时间即为所有数据对象分配固定的地址单元，且这些地址在运行时间始终保持不变。是一种直观的方法，但不适用于动态申请空间。
• 动态分配：运行时，程序中变量分配的地址不是具体的地址，而是一个抽象地址，当程序运行时，根据抽象地址二分配的具体的物理地址。

抽象地址的结构

抽象地址的形式是一个二元组，由层数和偏移组成。

• 层数主要针对嵌套式语言，表示的是某个函数所处的嵌套定义层数。
• 偏移是针对过程活动记录的一个相对偏移量
• 首地址+偏移=真实地址

层数的定义

• 嵌套式语言中：
  • 主程序为0层
  • 主程序直接定义的函数和过程为1层
  • 若某函数为L层，则该函数定义的函数为L+1层
• 并列式语言中：
  • 全局变量定义为0层，函数中的变量定义为1层

过程活动记录

• 数据区记录数据
• 管理信息保存从哪来到哪去

• 每次函数被调用时都会给函数分配一片空间，用以存储如图信息，把这片存储空间称作过程活动记录
• 偏移是针对过程活动记录的，通过起始位置+偏移量就可以找到对应的物理位置
• 过程活动记录中存储的顺序实际上是处理的先后顺序

空间分配原则

• 临时变量分配一个单元
• 局部变量类型按大小分
• 形参
  • 地址引用形参：分一个单元
  • 值引用形参：按类型大小分
  • 过/函形参：分两个单元：（入口地址，display表信息）
    • 入口地址：目标代码的地址
    • display表：记录变量访问环境，可以使用哪些数据

符号表简述

• 在语义分析中，符号表所登记的内容将用于语义检查（如检查一个名字的使用和原先声明是否一致
• 在产生中间代码中，用于类型检查及转换
• 在目标代码生成阶段，当对名字进行地址分配时，符号表是地址分配的依据

在编译程序工作的过程中，需要对符号表进行频繁的访问

组织符号表主要解决的问题

数据结构的内容

符号表的总体组织

符号表表项的排列

核心作用域的记录

符号表的局部化

符号表的总体组织

• 符号表存储的是标识符的语义信息
  • 标识符的名字
  • 语义字
• 不同类别的标识符所包含的信息是不同的
• 符号表的总体组织既可以使用多表结构，也可以使用单表结构，也可以两种折中。

多表结构

• 将属性完全相同的符号存放在一张符号表中，从而有常量表，类型表，变量表等。
• 多表结构的优点：每个符号表的属性个数和结构完全相同，各个表项都是等长的，并且表项中每个属性都是有效的，管理起来方便一致，空间效率高。
• 多表结构的缺点：编译程序时将同时管理若干个符号表，增加了总体管理工作的复杂度。并且对各类标识符的共同属性如类型的管理必须设置重复的运行机制。

单表结构

• 将所有符号都组织在一张符号表中。
• 单表结构的优点：总体管理集中单一，且不同种类符号的共同属性可以一致地管理和处理。
• 单表结构的缺点：由于符号属性的不同，为完整表达各类符号的全部属性必将出现不等长的表项，一句表项中属性位置交错重叠的复杂情况，极大增加了符号表管理的复杂度。
• 可行的解决方法：把所有符号可能属性作为符号表表项属性。
  • 优点：有助于降低符号表管理的复杂度。
  • 缺点：对于某些具体符号可能增加无用的属性空间，从而增加空间开销

折中方式

• 根据符号属性相似程度组织成若干张表，每张表中记录的符号都有比较多的相同属性。

• 符号表的建立是一次性的，符号表的查找是重复性的，因此查表的方法更为重要，对于查表的效率要求决定了建表的方法。

符号表项的排列

线性组织

• 录入方式：规定符号表中表项按符号被扫描到的先后顺序录入。
• 线性组织的优点：没有空白项，存储空间效率高
• 线性组织的缺点：运行效率低，特别当表项数模较大后效率就非常低。对于符号的个数无法确定的情况下，无法确定符号表的总长度。但当事先能确定符号个数的情况下，使用线性组织非常合适

排列组织

• 排列组织的符号表，就是在符号表中的表项，按其符号的字符代码串的值的大小排列的。
• 排序表的表项建立及符号查找，通常采用“二分法”

散列组织

• 一个符号在散列表中的位置，由对该符号代码值进行某种函数操作所得到函数值来确定的。
• 对符号代码进行哈希，计算哈希值，放入哈希表中
• 优缺点：效率最高，但是实现复杂而且消耗额外的存储扣扣你赶紧啊。

符号表的局部化处理

源程序的局部化单位

程序中允许有声明的部分，称为一个局部化单位，通常是一个子程序（函数、过程）或分程序。

主程序也可以被看作一个局部化单位。

标识符的作用域

• 一个局部化单位所建立的所有符号表项称为该局部化单位的符号表。
• 一个局部化单位的符号表的有效范围是该局部化单位。
• 在程序的点P处，对他有效的符号表是包含P的那些嵌套外层的局部化单位的符号表。
• 在P处遇使用性出现的标识符查符号表时，只能按着内层到外层的次序查在此处有效的那些局部化单位的符号表，而不访问在此无效的符号表，使其能够在程序的每点判断出哪些局部化单位的符号表使有效的。

局部化区的语义错误检查

• 变量的重复声明
  • 在一个程序的局部化区内，同一个标识不能被声明两次。
• 标识符的使用有无声明
  • 强类型语言规定标识符必须先声明后使用，弱类型语言无要求。

标识符的处理原则

• 遇到声明性标识符时，首先查找当前局部化单位的符号表中有无与此同名者，若有，则报告重复定义的语义错误，若无，则将该标识符的名字，及其属性填入符号表
• 遇到使用性出现，按由内到外的次序，一次查其嵌套外层的局部化单位的符号表，若有，则根据查得的属性判断对其使用是否合法，若无，则报告有使用而无声明的语义错误。

符号表的组织

突出标识符的作用域

全局式符号表

把整个程序的符号表作为一个表，即加标和查表单位是整个符号表。

如何屏蔽无效部分

• 每进入一个局部化，记住初始地址
• 遇到声明，若有则错，若无则加
• 遇到使用，由内向外，若有则用，若无则错

• 每当结束一个局部化区，“删除”

  • 直接删除

  • 驻留法（添加特殊表项）

    • 增加一个标识位，有效为1，失效为0

  • 转跳法

用一个Scope栈来实现标识符的嵌套作用域

• Scope[k]指向第k层符号表的表始地址。
  • 并列式语义：k指个数（都在一层）
  • 嵌套式语义：k指层数
• 真删除法：当退出一个局部化单位时，删除掉该局部化单位的符号表。
  • k表示层数计数器，s表示符号表的最后一项的地址，则删除式的局部化算法如下
  • 让表尾指针指向第k层地址的前一项，层数减一
• 驻留法：不用删除表，但使用一定措施不去查那些已经无效的符号表部分。
  • 符号表内容后面还可能用，所以多采用驻留法
  • 当退出一个局部化区时，将一个跳转表项加入结尾
    • $(#,Scope(k)-1)$

局部式符号表

把每个局部化单位的符号表作为一个独立的表来处理，即把每个局部符号表作为建表和查表单位。

如何找到外层有效符号

局部式线性组织的符号表的局部化处理思想

一个局部化区域一个表

只有真删除法

• 在不同时刻，不是所有的局部符号表都有效。用一个附属数据结构Scope栈，栈便于体现标识符的嵌套作用域的原则。
• 每当进入一个新的局部化区，就把表始地址存入栈中，当退出时，把栈顶元素弹出。
• 驻留表是居于全局表的结构，而对局部表只有删除法。

符号表管理