6.1 Overview of Intermediate Code Generation在线视频

各位同学大家好

这节课我们开始学习第7章

中间代码生成

我们先来看一下

编译器的整体结构

中间代码生成

处于前端的最后一个阶段

也就是我们在完成词法分析、

语法分析和语义分析之后

我们需要将我们得到的结果

翻译成中间代码

然后供编译器的后端来使用

中间代码

用来区分编译器的前端和后端

方便我们来针对新的机器

提出新的编译器

我们还可以针对中间代码

来设计更好的程序优化器

我们看到中间代码

这个部分

是连接前端和后端的重要组成部分

得到的结果是中间代码

使用中间代码的优点是

中间代码和机器无关

便于我们在不同的机器上进行移植

便于进行独立于机器的优化

有几种常用的中间表示

包括后缀表示、

图形表示

和三地址代码表示

我们要用语法制导的定义

和翻译方案

可以将源程序翻译成中间代码

我们首先来学习一下

后缀表示方法

后缀表示方法

相当于是我们有一个如下的递归定义

假设 E是一个变量或者参数

那么它的后缀表示就是它本身

也就是id这个表达式

它的后缀表示就是id

num这个表达式

它的后缀表示就是num

如果E是形式为E1 Op E2这样的表达式

那么E的后缀表示

就是E1'E2'Op

其中E1'是E的后缀表示

E2'是E2的后缀表示

如果是单目运算符uop E

那么它的后缀表示

就变成了E' uop

E'是E的后缀表示

如果E的表示形式是(E1)

那么E1的后缀表示就是E的表示

也就是说

(E)它的后缀表示形式就是E

也就是说后缀表示形式不需要带括号

我们再看一个表达式

(8-4)+2

那么(8-4)这个括号

在我们使用后缀表达式之后

就不再需要括号了

我们可以将它写为84-2+

后缀表示的最大优点

是方便计算机来处理

我们可以通过一个例子

来了解一下后缀表达式的优点

比如说

(8-4)+2这样的后缀表示是84-2+

它非常方便计算机来进行处理

我们看到

我们会在栈里边

将临时变量8写入到栈底

然后我们读取到第二个数字是4

4也放入到栈中

接下来计算机会读取到减号

我们就来计算8-4的结果

将4写入到栈中

下一步我们读取到数字2

我们将2写入到栈中

然后我们读取到加号

我们就把4和2相加的结果

写入到栈中

我们观察到这种后缀

表示非常方便计算机来进行处理

接下来我们来学习

第二种表达方法

图形表示

假设有一个表达式

a=(-b+c×d)+c×d

对于这样的一个表达式

我们可以将它化为语法树的形式加以表达

我们看到

对于这棵语法树来说

我们读取的时候

是从上到下开始进行读取

a=-b+c×d+c×d

这样的形式

还有一种表达方法

是有向无环图

它是语法树的一个简便的表达方式

我们注意到

刚才的表达式当中

c×d出现了两次

我们实际上不需要计算两次

而是需要在语法树当中

将加号的右结点

引入到c×d的父结点当中

也就是乘号上

这样我们就可以将c×d的结果

直接来进行使用

根据图形化的表示

我们可以来构造语法树对应的语法指导定义

我们来观察一下

针对如下的这些产生式它的语法规则

我们针对第一个产生式S→id := E

针对这个表达式

我们需要去构造一个新的结点

我们用了mknode这样的一个函数

来构造一个新的结点，assign这个结点

然后它的左边的叶子结点是id

右边的页子结点是E

第二个产生式 E→E1+E2

我们对应的语义规则是

E的指针

等于mknode('+', 左子树E1.nptr, 右子树E2.nptr)

那么我们观察到根结点是加号

左子树是E1，右子树是E2

对于第三条产生式 E→E1×E2

和加法的产生式类似的

只是乘号作为了当前的父结点

对于第4个产生式来说

E→-E

我们看到这是一个单目运算符

所以我们对应的语义规则是

构造单目运算符所对应的结点

然后它的子结点是E1

下一个产生式，E→(E)

那么我们知道

对于语法树来说

不需要有括号的存在

所以只需要把E1的指针赋给E即可

最后一个产生式E→id

那么我们需要为id构造一个子结点

也就是

最后一个语义规则

E的指针等于mkleaf

也就是我们当前构造了一个叶子结点

叶子结点的值是id

下面我们来学习

第三种表达方法

三地址代码

三地址代码的一般形式是x=y op z

也就是说

在一条语句当中

最多包含三个地址

假设有一个表达式x+y×z

它的三地址代码表示形式是

t1=y×z

t2=x+t1

其中t1和t2

我们把它称之为临时变量

临时变量需要在我们

栈中存储在局部数据的下边

我们可以根据语法树

或者是有向无环图

来写出它对应的三地址代码

我们来看一下这个例子

针对这棵语法树

我们可以将它的三地址代码

写为左侧的形式

t1=-b

t2=c×b

t3=t1+t2

t4=c×b

t5=t3+t4

a=t5

针对有向无环图

我们同样可以把它的三地址代码

写出来

t1=-b

t2=c×d

t3=t1+t2

t4=t3+t2

a=t4

下面我们给出一些

常用的三地址代码

一般的表示形式

对于赋值语句来说

x=y op z

里边只包含三个地址

直接就可以写为三地址代码

x=op y或者x=y

这都是满足三地址代码的形式

对一个无条件转移语句

我们将它写为goto L

也就是无条件跳转到L

对于条件转移语句

我们将它写为 if x relop y goto L的形式

也就是，如果x和y满足一定的条件

我们跳转到L

下一个是过程调用语句

首先是我们将n个参数写出来

param x1, param x2, 一直到param xn

然后我们来调用这n个参数

所对应的这个过程

也就是call p, n

n指出了参数的个数

下一个是给出过程的返回语句return y

我们将y返回

接下来是索引赋值语句x=y[i]

也就是我们从y这个地址出发

向下取i个存储单元之后

取出对应的值赋给x

对于x[i]=y来说

我们把y的值取出来

赋给x[i]对应的单元

也就是从x出发

向下寻找i个存储单元

将y的值存入其中

最后是地址和指针赋值语句

x=&y

我们取出y的地址赋给x

x=*y

我们取出y的指针赋给x

*x=y

我们将y的值取出来

赋给x所指的位置

最后还有一种表达方式

我们将它称为静态单赋值形式

我们看一下静态单赋值形式

同样是一种中间代码的表示形式

它可以用来方便某些代码

来进行进一步的优化

它和三地址代码的主要区别有两点

首先

所有的赋值指令

都是对不同名字的变量的赋值

在三地址代码当中

比如说

我们可以将它写为一个代码序列

p=a+b

q=p-c

p=q×d

我们发现在这一步我们重用了p

p=e-p

q=p+q

在这里我们多次重复了p和q

在静态单赋值形式当中

我们强调的是

每一个变量只有一次赋值

p1=a+b

q1=p1-c

p2=q1×d

也就是我们不可以对一个值

进行两次重复的赋值

p1只可以进行一次的赋值

p3=e-p2

q2=p3+q1

如果是这样的话

对于静态单赋值的形式

我们会碰到的另一个问题是

一个变量

如果在不同的路径上都有不同的定值

如何去解决这个问题呢？

比如说

if (flag) x=-1; else x=1

我们发现其实在不同的路径上

x的值是不同的

在后边y=x×a

对x进行引用的时候

我们究竟取哪个x的值呢？

那么在静态单赋值中

是这样解决这个问题的

我们将它改写成

if (flag) x1=-1; else x2=1

也就是在两个不同的路径上

我们使用了不同的变量名称去表示它

然后我们写成一个函数

x3=Φ(x1, x2)

这个函数是由flag值来决定的

由flag来决定

我们在此处

x3的值是取x1还是取x2

这一小节就到这

谢谢大家