类型表达式
- 基本类型是类型表达式
- integer、real、char、boolean、type_error (出错类型)、void (无类型)
- 可以为类型表达式命名，类型名也是类型表达式
- 将类型构造符 (type constructor) 作用于类型表达式可以构成新的类型表达式
- 数组构造符 array
- 若 T 是类型表达式，则 array (I, T) 是一个表示数组类型的表达式，该数组包含 I 个元素，每个元素都是 T 类型
- 指针构造符 pointer
- 若 T 是类型表达式，则 pointer (T) 是一个表示指向类型 T 的指针类型的表达式
- 笛卡尔乘积构造符
- 若 T1 和 T2 是类型表达式，则笛卡尔乘积 T1 × T2 是类型表达式
- 函数构造符→
- 若 T1、T2、…、Tn 和 R 是类型表达式，则 T1 × T2 ×…× Tn→ R 是类型表达式 (T1,T2 表示函数参数类型，R 表示函数返回值类型)
- 记录构造符 record
- 若有标识符 N1 、N2 、…、Nan 与类型表达式 T1 、T2 、…、Tn ， 则 record (( N1 × T1) × ( N2 × T2 )× …× ( Nan × Tn )) 是一个类型表达式 (记录中有 n 个字段，每个字段名为 N1、N2、……，字段类型为 T1、T2、……)
- 数组构造符 array
声明语句翻译
- 对于声明语句，语义分析的主要任务就是收集标识符的类型等属性信息，并为每一个名字分配一个相对地址
- 从类型表达式可以知道该类型在运行时刻所需的存储单元数量称为类型的宽度 (width)
- 在编译时刻，可以使用类型的宽度为每一个名字分配一个相对地址
- 名字的类型和相对地址信息保存在相应的符号表记录中
【例 2-1】声明语句 (基本类型) 的语法制导翻译
- 该 SDT(语法制导翻译方案) 对应的是一个 L 属性定义，若该 L 属性定义的基础文法是 LL(1) 文法，则可以在自顶向下分析中实现该 SDT
- 验证该基础文法是否为 LL(1) 文法
- 判断具有相同左部的产生式，它们的可选集是否不相交
- 产生式 23 具有相同左部
- SELECT(2)=FIRST(T)=FIRST(B)={int,real,⬆}
- SELECT(3)=FOLLOW(D)={$}
- 产生式 45 具有相同左部
- SELECT(4)={int,real}
- SELECT(5)={⬆}
- 产生式 67 具有相同左部
- SELECT(6)={int}
- SELECT(7)={real}
- 产生式 89 具有相同左部
- SELECT(8)=FOLLOW(C)=FOLLOW(T)={id}
- SELECT(9)={ [ }
- 综上，该基础文法为 LL(1) 文法
- 初始时刻，输入指针指向 real
- 从文法开始符号 P 开始推导，根据产生式 1，将 P 替换 2 个符号
- 第一个符号是用来表示语义动作的动作符号，起名为 a，
- 第二个符号是非终结符 D
- 此时，动作符号 a 处于栈顶，执行它所对应的语义动作，即将 offset 置为 0，随后动作符号 a 出栈
- 此时，栈顶为非终结符 D，因为当前输入符号为 real，所以选择产生式 2，将 D 替换为 4 个符号
- 此时，栈顶为非终结符 T，因为当前输入符号为 real，所以选择产生式 4，将 T 替换为 4 个符号
- 此时，栈顶为非终结符 B，因为当前输入符号为 real，所以选择产生式 7，将 B 替换为 2 个符号
- 从文法开始符号 P 开始推导，根据产生式 1，将 P 替换 2 个符号
- 此时，栈顶为终结符 real，与输入符号匹配成功，real 出栈，输入指针指向下一个输入符号 x
- 此时，动作符号 a 处于栈顶，执行它所对应的语义动作，即将 B 的两个综合属性 type 和 width 分别置为 real 和 8
- ……
- ……
- enter 是一条记录
赋值语句翻译
简单赋值语句的翻译
- lookup(name)：查询符号表返回 name 对应的记录 (值)
- gen(code)：生成三地址指令 code
- newtemp( )：生成一个新的临时变量 t，返回 t 的地址
- code：表达式的值
- addr：表达式的值的存放地址
- ||：连接运算符
【例 3-1】增量翻译
- 在第四章中曾分析过，该 SDT 的基础文法可以采用 LR 分析技术，且所有的语义动作都位于产生式右部的末尾，因此，采用自底向上的方式来翻译
具体翻译过程用文字描述较为繁琐，可看视频讲解：传送门
数组引用的翻译
地址计算公式
【例 3-2】数组元素寻址
- a[i1]：二维数组，宽度为 5×8×4=160bit
- a[i1] [i2]：一维数组，宽度为 8×4=32bit
- a[i1] [i2] [i3]：一个整型变量，宽度为 4bit
【例 3-3】带有数组引用的赋值语句的翻译 (一维)
【例 3-4】带有数组引用的赋值语句的翻译 (二维)
【例 3-5】数组引用的 SDT
控制流语句
基本文法
代码结构
SDT
- newlabel( ): 生成一个用于存放标号的新的临时变量 L，返回变量地址
- label(L): 将下一条三地址指令的标号赋给 L
布尔表达式
基本文法
代码结构
SDT
- 对照上面的代码看
- 对照代码结构图看 SDT
控制流语句的翻译
【例】SDT 的通用翻译实现方法
- 该 SDT 的基础文法不是 LL(1) 文法，不能在自顶向下的语法分析中同时实现语义翻译
- 该 SDT 的产生式右部中又含有内嵌的语义动作，因此要想在自底向上的语法分析进行语义翻译，需要修改该文法，引入一些标记非终结符
- 任何 SDT 都可以通过下面的方法实现
- 首先建立一棵语法分析树，然后按照从左到右的深度优先顺序来执行这些动作
- 该 SDT 采用 LR 分析，为输入的语句构造语法分析树，后按照从左到右的深度优先顺序来执行这些该文法中的语义动作
【例】构造语法分析树
- 翻译给定的输入程序片段
- 分析树中各个节点对应的产生式如下
- 当 S3 分析完后，生成 goto 语句，跳转到 S.begin，也就是 L2，即下图的序号 10 指令
- L 是用来存放标号变量的地址，自己定义的，随着程序的执行，每遇到新标号就 + 1
- 右上角，数字 123…… 是自己定义的序号，表示指令，随着程序的执行，每遇到关系表达式或赋值语句，就生成跳转指令或三地址指令
- 最后，将标号 L 与地址对应，得到下图
- 右边是三地址指令对应的四元式形式
- 在为布尔表达式和控制流语句生成中间代码的过程中，最重要的是确定跳转指令的目标标号，但是在生成跳转指令的时候，目标标号还不能确定
为了解决这一问题，上面例题的解决方案，是将存放标号的地址作为继承属性，传递到跳转指令生成的地方，但是这样做，需要在最后将标号 L 与具体地址对应绑定起来
回填
为了解决在生成跳转指令的时候，目标标号还不能确定这一问题，可以采用回填技术
- 回填技术：把一个由跳转指令组成的列表以综合属性的形式进行传递
基本思想：
综合属性
- B.truelist：指向一个包含跳转指令的列表，这些指令最终获得的目标标号就是当 B 为真时控制流应该转向的指令的标号
- B.falselist：指向一个包含跳转指令的列表，这些指令最终获得的目标标号就是当 B 为假时控制流应该转向的指令的标号
为了处理跳转指令，构造三个函数
- makelist(i)
- 创建一个只包含 i 的列表，i 是跳转指令的标号，函数返回指向新创建的列表的指针
- merge(p1, p2)
- 将 p1 和 p2 指向的列表进行合并，返回指向合并后的列表的指针
- backpatch(p, i)
- 将 i 作为目标标号插入到 p 所指列表中的各指令中
- _：有待回填
- nextquad：下一条即将生成的指令的标号，在这里，也就是第一个 gen 中跳转指令的标号
- 从翻译示意图中可以看出
- B1 为真 ，B1 的 truelist 中所有指令直接跳转到 B 为真
- B1 为假，B1 的 falselist 中所有指令还需跳转到 B2 继续判断
- 在分析 B2 之前，需要用 B2 的第一条指令的标号回填 B1 的 falselist 中所有指令，也可以记录下 B2 的第一条指令的标号，在归约的时候回填
- 为了记录 B2 的第一条指令的标号，在非终结符 B 之前插入标记一个非终结符 M，与 M 关联的语义动作就是记录 B2 的第一条指令的标号
- M 的综合属性 quada 记录下一条指令的标号，因为 M 放在 B2 之前，所有 quada 属性记录 B2 的第一条指令的标号
- 调用 backpatch 函数，用 M.quad 回填 B1.falselist 中所有指令
- 调用 merge 函数，将 B1.truelist 和 B2.truelist 合并，B.truelist 指向合并后的指令列表
【例】布尔表达式的翻译
- 因为定义的都是综合属性，所以采用自底向上的分析，从左到右扫描字符串
- 将 a<b 归约为非终结符 B
- 假设下一条指令从 100 开始编写
- and 优先级高于 or
- 将 B and B 归约 B，并执行该产生式相关语义动作
- 用 M.quad=104 回填 B1.truelist={102}，也就是回填标号 102 的跳转指令
- B.truelist=B2.truelist={104}
- 将 B1.falselist 与 B2.falselist 合并后赋给 B.falselist，即 {103，105}
- 将 B or B 归约 B，并执行该产生式相关语义动作
- 用 M.quad 回填 B1.falselist
- 将 B1.truelist 与 B2.truelist 合并后赋给 B.truelist，即 {100，104}
- B.falselist=B2.falselist={103，105}
- 当 B 的真出口确定后，回填 B.truelist
-
控制流语句的回填
综合属性
- S.nextlist：指向一个包含跳转指令的列表，这些指令最终获得的目标标号就是按照运行顺序紧跟在 S 代码之后的指令的标号
- 由图可知
- 在 S1 执行完之后，要显式的生成一条跳转指令，跳转到 S 之后的第一条指令
- 要由 S1 的第一条指令的标号回填 B.truelist，S2 的第一条指令的标号回填 B.falselist
- 在 S1 之后设置一个标记非终结符 N，用来生成跳转指令
- 由翻译方案示意图可知
- 在 S1 执行完之后，要显式的生成一条跳转指令，跳转到 WHILE 语句的第一条指令
- 用 B 的第一条指令的标号回填 S1.nextlist 中的指令
- 用 S1 的第一条指令的标号回填 B.truelist 中的指令
- 用 M1 和 M2 分别记录 B 和 S1 的第一条指令的标号
- 赋值语句不需要跳转，所以为空
【例】控制流语句的翻译
输入的控制流语句对应的注释分析树构造过程，可看视频讲解，方法与之前的布尔表达式大同小异，不同的是控制流语句是自顶向下分析
switch 语句的翻译
从代码结构图可看出
- 将表达式 E 的值存到临时变量 t 中
- Ln-1 是 Sn.code 中第一条指令的标号
- 在生成每个 S 的代码之后，要生成一条跳转指令，next 是 Sn 的代码之后的第一条指令的标号，也就是整个 switch 语句之后的第一条指令的标号
- 根据代码结构图编写出 switch 语句的翻译方案
- 将分支测试指令集中在一起，提高代码执行效率
过程调用语句的翻译
- id 是过程名，Elist 是过程的参数表达式列表
- 由参数表达式的代码构成，每一个表达式的值存放在非终结符 Ei 的 address 属性中，在生成各个表达式的代码之后，各生成一条 param 指令，将这些表达式的值设置为实参
- 可以将各个 param 指令集中在一起
【例】过程调用语句的翻译
- 过程名是 f，有 4 个参数
若有收获，就点个赞吧
0 人点赞
