中间代码生成

Baileys2022年5月13日

学校课程

学校课程
编译原理

大约 5 分钟...

简介

SDT

声明语句的翻译

类型表达式

基本类型是类型表达式。

integer
real
char
boolean
type_error
void

可以为类型表达式命名，类型名也是类型表达式。

将类型构造符(type constructor)作用于类型表达式可以构成新的类型表达式。

数组构造符 $array$ ，若 $T$ 是类型表达式，则 $array(I,T)$ 是类型表达式( $I$ 是一个整数)，例:
指针构造符 $pointer$
若T是类型表达式，则 $pointer(T)$ 是类型表达式，它表示一个指针类型。
笛卡尔乘积构造符 $\times$
若 $T_{1}$ 和 $T_{2}$ 是类型表达式，则笛卡尔乘积 $T_{1}{\times}T_{2}$ 是类型表达式
函数构造符 ${\rightarrow}$
若 $T_{1}$ 、 $T_{2}$ 、 $…$ 、 $T_{n}$ 和 $R$ 是类型表达式，则 $T_{1}{\times}T_{2}{\times}…{\times}T_{n}{\rightarrow}R$ 是类型表达式。
记录构造符 $record$
若有标识符 $N_{1}$ 、 $N_{2}$ 、 $...$ 、 $N_{n}$ 与类型表达式 $T_{1}$ 、 $T_{2}$ 、 $...$ 、 $T_{n}$ ，则 $record((N_{1}{\times}N_{2}){\times}(N_{2}{\times}T_{2}){\times}...{\times}(N_{n}{\times}T_{n}))$ 是一个类型表达式。

举例:
声明语句

局部变量的存储分配

对于声明语句，语义分析的主要任务就是收集标识符的类型等属性信息，并为每一个名字分配一个相对地址:

从类型表达式可以知道该类型在运行时刻所需的存储单元数量称为类型的宽度(width)
在编译时刻，可以使用类型的宽度为每一个名字分配一个相对地址

名字的类型和相对地址信息保存在相应的符号表记录中。

变量声明的SDT

声明语句

赋值语句的翻译

赋值语句的语法:

赋值语句翻译的主要任务:
生成对表达式求值的三地址码。
赋值语句的语法

赋值语句的SDT

code表示三地址码，E的addr表示表达式的存放地址。
赋值语句的语法

数组引用的翻译

赋值语句的文法

数组引用的语法

数组元素寻址

将数组引用翻译成三地址码时要解决的主要问题是确定数组元素的存放地址，也就是数组元素的寻址。

一维数组
假设每个数组元素的宽度是 $w$ ，则数组元素 $a[i]$ 的相对地址是: $base+i{\times}w$ ，其中， $base$ 是数组的基地址， $i{\times}w$ 是偏移地址。
二维数组
假设一行的宽度是 $w_{1}$ ，同一行中每个数组元素的宽度是 $w_{2}$ ，则数组元素 $a[i_{1}][i_{2}]$ 的相对地址是: $base+i_{1}{\times}w_{1}+i_{2}{\times}w_{2}$ 。
k维数组数组元素 $a[i_{1}][i_{2}]...[i_{k}]$ 的相对地址是: $base+i_{1}{\times}w_{1}+i_{2}{\times}w_{2}+...+i_{k}{\times}w_{k}$ 。其中， $w_{1}$ 是 $a[i_{1}]$ 的宽度( $a[i_{1}]$ 是一个 $k-1$ 维数组)， $w_{2}$ 是 $a[i_{1}][i_{2}]$ 的宽度，..., $w_{k}$ 是 $a[i_{1}][i_{2}]...[i_{k}]$ 的宽度。

例:
假设: $type(a)=array(3,array(5,array(8,int)))$ .
一个整形变量占用4个字节，则 $addr(a[i_{1}][i_{2}][i_{3}])=base+i_{1}{\times}w_{1}+i_{2}{\times}w_{2}+i_{3}{\times}w_{3}=base+i_{1}{\times}160+i_{2}{\times}32+i_{3}{\times}4$ ，其中 $a[i_{1}]$ 的宽度为160， $a[i_{1}][i_{2}]$ 的宽度为32， $a[i_{1}][i_{2}][i_{3}]$ 的宽度为4.

带有数组引用的赋值语句的翻译

例1: 假设 $type(a)=array(n,int)$
源程序片段: $c=a[i];$
三地址码: $t_{1}=i{\cdot}4$
$t_{2}=a[t_{1}]$
$c=t_{2}$

例2: 假设
$type(a)=array(3,array(5,int))$
源程序片段: $c=a[i_{1}][i_{2}];$
三地址码: $t_{1}=i_{1}{\cdot}20$
$t_{2}=i_{2}{\cdot}4$
$t_{3}=t_{1}+t_{2}$
$t_{4}=a[t_{3}]$
$c=t_{4}$