编译原理课件18.ppt

5 9说明语句的翻译 说明语句的作用是指明被说明的量的一些具体属性 如类型 种属 存储分配特点及其它属性等等 编译程序对说明语句进行处理的主要任务是把有关属性填入符号表相应登记项中 说明语句主要有变量定义 也称类型说明 语句 数组说明语句及类型定义语句等 5 9 1类型说明语句的翻译 类型说明语句的常见形式为其中 类型名可以是程序设计语言提供的简单数据类型名 如integer real boolean等 或是程序员自己定义的数据类型 如结构 联合类型等 的名字 变量名表是以逗号隔开的变量或数组名 为了叙述方便 我们假定简单类型名只有int real boolean三种 其它简单类型的处理与其类似 而自定义数据类型名的处理将在5 9 2节中讨论 我们假定数组名具有形式name l1 u1 l2 u2 ln un 其中 li ui i 1 2 n 为整型常数 且满足li ui 类型说明的属性翻译文法 为了区分一般变量与指针 我们在符号表中引入一个标志域IsPointer 当其为真 1 时表示该变量为指针 否则 0 为一般变量 另外 我们假定指针变量的定义形式与C语言相同 Varable iden Entry 1 变量在符号表中序号 VarList CAT SimVar 种属为简单变量 VarList IsPointer 0 指针标志 VarList ADDR NULL 尚未分配内存空间 下同 iden 指针 Entry 1 变量在符号表中序号 VarList CAT SimVar 种属为简单变量 VarList IsPointer 1 指针标志 VarList ADDR NULL ArrayVar 1 ArrayMSG iden number number Entry 1 VarList CAT Array 种属为数组 VarLIst IsPointer 0 VarList ADDR DIM 1 记录维数 下面为内情向量申请空间 并填入第一维下标信息 其中 前两个单元 下标为 0 和 1 用来存放a C之值 此时暂不填写 n值可由DIM保存 因此不必另存 VarList ADDR Vector malloc 5 sizeof int VarList ADDR Vector 2 3 第一维下界 VarList ADDR Vector 3 5 第一维上界 VarList ADDR Vector 4 5 3 1 第一维界差 iden number number 指针数组 Entry 1 VarList CAT Array 种属为数组 VarList IsPointer 1 VarList ADDR DIM 1 记录维数 下面的填写工作与上一产生式相同 注释略 VarList ADDR Vector malloc 5 sizeof int VarList ADDR Vector 2 4 第一维下界 VarList ADDR Vector 3 6 第一维上界 VarList ADDR Vector 4 6 4 1 第一维界差 ArrayMSG number number intdim VarList ADDR DIM 1 1 VarList ADDR DIM 维数加1 下面增加向量空间 记录新一维的信息 VarList ADDR Vector realloc VarList ADDR Vector 3 dim 2 sizeof int 下面记录当前维的下 上界及界差 VarList ADDR Vector 3 dim 1 3 VarList ADDR Vector 3 dim 5 VarList ADDR Vector 3 dim 1 5 3 1 ArrayVar ArrayMSG 传递数组名在表中序号 1 FillArrMSG C 计算并填写数组内情向量的C值 Type int Type INT real Type REAL boolean Type BOOL SelfDef Type 1 Type DefVarable TypeVarable FillVarType 2 1 Type Type 1 Type DefVarable Varable FillVarType 3 1 Type Type 1 Type 在上面的属性翻译文法中 我们引入了两个辅助函数voidFillVarType intNO intTYPE 和voidFillArrMSG C intNO 第一个函数完成将类型信息TYPE填写到符号表中的第NO项之类型 type 域的工作 第二个函数计算并填写符号表中第NO登记项ADDR所指示的内情向量中的C CONSTPART 值 非终结符SelfDef用于描述用户自定义数据类型 其文法定义将在5 9 2节中讨论 这里 我们只需知道它具有一个属性Type 用大于零的整型数表示 对于简单数据类型 如real int等 我们规定用负整数表示 为了便于阅读 这里使用了助记符 常量定义 另外 还利用符号表 VarList 的ADDR域作为指针 指向一个结构struct intDIM int Vector 其中 DIM用于描述数组的维数 Vector是一3 DIM 2个整型数组成的向量 用于存放除n 维数 外的内情向量信息 其中存放首地址a的单元暂为空 由于各个数组的维数可以不同 这里采用了动态申请 不断增大 空间的方法保存上述信息 另外 为保持一致性 当说明简单变量时 将其ADDR域赋值为NULL 在上面的文法中 我们假定数组各维的上下界均是常数 有些语言 ALGOL 允许上下界是可变的 在这种情况下 数组的内情向量信息就无法在编译时具体填入 此外 由于在编译时不能确定数组的体积 故也无法为其分配存储空间 可见 对于变界数组内情向量的填写工作 只能在运行时动态地进行 由于内情向量本身所占存储空间的大小一般仅依赖于数组的维数n 因此 尽管变界数组相应内情向量中的一些信息无法在编译时填入 但其内情向量所需要量的内存空间的大小 3 n 2 可在编译时确定 在编译时 为各变界数组分配内情向量区 并产生填写内情向量的目标代码 通常是调用一个填写内情向量的子程序 待目标程序运行时 再根据当时所算出的下标上下界 动态地为变界数组建立内情向量和分配存储空间 5 9 2数据类型定义语句的翻译 一般说来 常用的高级语言 如PASCAL C JAVA等 都支持复杂的数据类型 这些数据类型除了系统提供的常用类型外 还允许用户自定义复杂的数据类型 如PASCAL中的RECORD语句 C语言中的struct定义语句等等 要实现这类语句的翻译 首先应有合理的数据结构来存储复杂数据类型的各种信息 其次 由于复杂数据类型实际上是由多层次 复合使用简单数据类型定义和变量 分量 定义而建立的 所以 处理好数据类型分量定义与变量定义的关系 以及分量为复杂类型时的递归 嵌套问题是实现数据类型定义语句翻译的关键 由于处理上述问题的方法极其复杂 本节仅概要地介绍翻译这类语句的基本思想 有兴趣的读者可参阅有关文献 为了在系统内部表示复杂的数据结构 需设置两种信息表 结构 记录 名表和分量表 结构名表用于记录用户自定义的复杂数据类型的名称及一些相关信息 如第一分量在分量表中的序号 分量的个数等 分量表用于记录复杂数据结构的各个分量 并在表内将同一数据结构的各个分量拉成一条链 以便查询 分量表在结构上类似于符号 变量定义 表 主要数据域有 分量名FieldName 类型Type 下一分量NextField 数组信息ArrayMSG 指向内情向量的首地址 等等 其中 类型用整数表示 大于等于零时表示该分量是复杂类型 即表示该类型在结构表中的序号 小于零时表示简单数据类型 例如 我们可规定 INT REAL BOOL类型分别为 1 2 3等等 结构名表与分量表的数据结构typedefstruct charStructName MAXSTRING 结构名 intFirstMember 首分量地址 StructTableTag 结构名表字段定义 typedefstruct charFieldName MAXSTRING intType intNext intArrayMSG FieldTableTag typedefstruct intCount 结构名个数计数 StructTableTag StructTable 结构表 StructTag 结构名表的数据结构定义 typedefstruct intCount 分量个数计数 FieldTableTag FieldTable FieldTag 分量表的数据结构定义 StructTagStructList 结构表定义 FieldTagFieldList 分量表定义 为了简化说明 我们假定复杂数据结构只有形如PASCAL中的RECORD语句所定义的记录类型一种 由于分量说明语句与变量说明语句完全相同 为了能将其正确地填写到相应的表中 设置一全局变量IsInRecord 用于标识目前正在处理的 变量或分量 说明语句 所描述的是记录分量 大于0时 还是变量 等于0时 IsInRecord初值为0 为处理记录定义语句的嵌套 每进入一层RECORD语句就将其 遇到END时 在处理说明语句时 首先判断IsInRecord之值 以确定将信息填入变量表还是分量表 例如 DefVarable TypeVarable if IsInRecord 填写分量表 else填写变量表 在填写分量表时还要完成分量的拉链工作 为保证能正确地记下复杂数据结构的所有信息 DefVarable还应具有两个属性 First和Last 分别指向当前说明语句中所定义的第一个分量和最后一个分量 用于处理在同一结构说明中定义多个分量的情况 要求在处理过程中将其拉成一个小链 当IsInRecord 0时 First和Last二属性无用下面 我们以PASCAL语言中RECORD为例 给出其属性翻译文法 SelfDef RecordDef Type 1 No 其它数据结构定义 RecordDef FieldListend IsInRecord No 1 No FieldList FieldList DefVarable 利用 1 Last及 3 First合并链 链尾为 3 Last Last 3 Last No 1 No RecordDefVarable 将当前结构名表中的最后一登记项的FirstMember域指向DefVarable说明的第一分量 StructList StructTable StructList Count 1 FirstMember 2 First Last 2 Last 用于拉链 No 1 结构名表中序号 Record iden record i