Arya

第六章 中间代码生成 note
[+] 不想出门第六章 中间代码生成 note类型表达式(Type Express)基本类型是类型表达式integ...
扫描右侧二维码阅读全文
03
2019/02

第六章 中间代码生成 note

[+] 不想出门

第六章 中间代码生成 note

类型表达式(Type Express)

  • 基本类型是类型表达式
    integer
    real
    char
    boolean
    type_erroe(出错类型)
    viod(无类型
  • 可以为类型表达式命名,类型名也是类型表达式
  • 将类型构造符(type constructor)最用于类型表达式可以构成新的类型表达式

例如:

数组类型构造符array
若T是类型表达式,则array(I,T)是一个类型表达式(I是一个整数)

类型类型表达式
int[3]array(3,int)
int2array(a,array(3,int))

指针构造符pointer
若T是类型表达式,则pointer(T)是类型表达式,它表示一个指针类型

笛卡尔乘积构造符×
若T1和T2是类型表达式,则笛卡尔乘积T1×T2也是类型表达式

函数构造符→
若T1、T2、……Tn和R是类型表达式,则T1×T2×……×Tn→R是类型表达式

记录构造符record
若有标识符N1、N2、…、Nn 与类型表达式T1 、T2、…、Tn, 则record((N1×T1)×(N2×T2)×…×(Nn×Tn)) 是一个类型表达式

举一个例子:
假设有一个C语言片段

struct stype
{ char[8] name; 
int score; 
}; 
stype[50] table; 
stype* p; 

stype绑定的类型表达式

record((name×array(8,char))×(score×integer))

table绑定的类型表达式

array(50,stypr)

p绑定的类型表达式

point(stype)

声明语句的翻译

局部变量的存储分配

  • 对于声明语句,语义分析的主要任务就是收集标识符的类型等属性信息,并为每一个名字分配一个相对地址
    从类型表达式可以知道该类型在运行时刻所需的存储单元数量称为类型的宽度(width)
    编译时刻,可以使用类型的宽度为每一个名字分配一个相对地址
  • 名字的类型相对地址信息保存在相应的符号表记录中

接下来举了一个变量声明语句的SDT

Image6-3.png

其中非终结符B用来生成基本类型关键字,取Basic的首字母,用来生成int或者realC用来生成数组下标表达序列,T用来表示标识符的类型,D用来生成一个声明序列,一个声明序列对应一个P

如果我们需要翻译一个变量声明序列

real x;int i;

我们首先需要判定上面定义的文法是不是LL(1)文法,如果是,我们就可以在自顶向下的分析中来实现SDT

判定的方法具有相同左部的可选集是否不相交
②和③两个产生式有相同的左部D,那么我们先分析②。由②可知,DSELECT集也就是TFIRST集,而TFIRST集取决于BFIRST集,那么BFIRST集里有intreal,且指针关键字也在TFIRST集中,所以SELECT(D)={指针关键字,int,real}

在③中,可以看出③的SELECT集是FOLLOW(D),而FOLLOW(D)={$},所以二者不相交

再来看④和⑤产生式
在产生式④中,SELECT(T)取决于FRIST(B)FIRST(B)={int,real},而在产生式⑤中SELECT(T)={指针关键字},所以不相交

由上分析得知产生式⑥和⑦的SELECT(B)互不相交

最后看产生式⑧和⑨
在产生式⑧中,SELECT(C)取决于FOLLOW(C),由产生式④可得,FOLLOW(C)={$},所以SELECT(C)={$};而在产生式⑨中,SELECT(C)={[},所以也互不相交

所以基础文法就是一个LL(1)文法

那么在自顶向下的语法分析过程中实现这个SDT,初始时刻输入指针指向real,根据第一个产生式将P替换成{a}D,分别是用来表示语义动作的动作符号和非终结符,此时的offset=0,我们将D替换成Tid;{a}D,此时栈顶是T,我们根据产生式④,将T替换为B{a}C{a},现在的栈顶是B,那么我们根据产生式⑦将B替换为real{a},此时的栈顶是非终结符real,与当前的输入符号匹配成功,将real出栈,并且指针后移指向x

现在栈顶的为{a},执行{a}中的语义动作

B.type = real; B.width = 8; 

B出栈,栈顶为{a},执行{a}中的语义动作……

之后依次类推得到最终结果

Image6-4.png

不难,大概就是解释了一下如何翻译这句话

接下来翻译一个数组类型表达式

int[2][4]

因为当前输入符号是int所以选择产生式④,将T替换为B{a}C{a},接下来方法同上

Image6-5.png

简单赋值语句的翻译

首先来看一下一个赋值语句的基本文法

①S→id=E;
②E→E1+E2
③E→E1*E2
④E→-E1
⑤E→(E1)
⑥E→id

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

例如,源程序片段为

x=(a+b)*c

那么三地址码为

t1=a+b
t2=t1*c
x=t2

赋值语句的SDT

Image6-6.png

这个SDT中还有三个函数

  • lookup(name):查询符号表,返回name对应的记录
  • gen(code):生成三地址指令code
  • newtemp( ):生成一个新的临时变量t,返回t的地址

由上面可以看出子表达式的code属性可能是子表达式的子表达式赋值的code属性,以此类推,所以code属性可能是一条很长的字符串。但通过分析可以发现,产生式左部的文法符号的code属性,是由产生式右部的文法符号的code属性,按顺序连接起来以后,在后面追加三地址指令,因此我们可以使用增量的方式进行翻译

增量翻译(Incremental Translation)
在增量翻译的方式中,不需要设置code属性,而是直接再已生成的三地址码后面,追加新的三地址指令,那么在增量方法中,gen()不仅要构造出一个新的三地址指令,还要将它添加到至今为止已生成的指令序列之后,得到

Image6-7.png

接下来通过一个例子进行简单的分析

假设我们输入

x=(a+b)*c;

Image6-8.png

这里我直接给出自动机和结果,老师讲的很清楚,建议看原视频

数组引用的翻译

我们对前面给出的赋值语句的基本文法进行扩展

S→id=E; | L=E;
E→E1+E2 | -E| (E1) | id | L
L→id[E] | L1[E]

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

数组元素的寻址(Addressing Array Elements)

  • 一维数组
    假设每个数组元素的宽度是w,则数组元素a[i]的相对地址是:base+i*w,其中base是数组的基地址,i×w是偏移地址
  • 二维数组
    假设一行的宽度是w1,同一行中每个数组元素的宽度是w2,则数组元素ai1的相对地址是base+i1*w1+i2*w2,其中i1*w1+i2*w2,是偏移地址
  • k维数组
    数组元素ai1…[ik]的地址是base+i1*w1+i2*w2+…+ik*wk

其中w1 →a[i1]的宽度,w2 →ai1的宽度…wk →ai1 …[ik]的宽度

接下来举一个例子

Image6-9.png

接下来看带有数组引用的赋值语句翻译的例子:

例1:一维数组
假设type(a)=array(n,int),
源程序片段为c=a[i];我们也可以计算出addr(a[i])=base+i*4
三地址码

t1 = i * 4 
t2 = a [ t1]
c = t2

例2:二维数组
假设type(a)= array(3, array(5, int)),
源程序片段为 c =a[i1][i2];,我们计算出adddr(a[i1][i2])=base+i*20+i2*4,其中t1i*20t2i*4
三地址码

t1 = i1 * 20 
t2 = i2 * 4 
t3 = t1 + t2
t4 = a [ t3 ] 
c = t4

接下来是数组引用SDT的例子

Image6-10.png

根据以上分析得出数组元素的SDT

Image6-11.png

分析一堆,不写出来了,看视频吧

控制流语句及其SDT

控制流语句的基本文法

Image6-12.png

这里我们以if-else语句为例

Image6-13.png

接下来编写控制流语句的SDT

Image6-14.png

if-then-else语句的SDT

Image6-15.png

if-then语句的SDT

Image6-16.png

while-do语句的SDT

Image6-43.png

布尔表达式及其SDT

首先给出布尔表达式的基本文法

Image6-17.png

其中布尔常量TrueFalse也是关系表达式

在跳转代码中,逻辑运算符&&|| ! 被翻译成跳转指令。运算符本身不出现在代码中,布尔表达式的值是通过代码序列中的位置来表示的
例如:

if ( x<100 || x>200 && x!y )
    x=0;

三地址码为

            if x<100 goto L2
            goto L3
L3 :       if x>200
             goto L4goto L1
L 4 :      if x!=y goto L2
             goto L1
L 2 :      x=0
L 1:

我们可以看出在这个三地址码中并未出现逻辑运算符&&|| !

接下来是布尔表达式的SDT

Image6-18.png

B→B1 or B2的SDT

Image6-19.png

B→B1 and B2的SDT

Image6-20.png

控制流翻译的例子

先给出控制流语句的SDT

Image6-21.png

为了直观的说明这个SDT,我们这里采用SDT的通用实现方法:

  • 首先建立一课语法分析师,按照从左到右的深度优先顺序来执行这些动作

接下来是举的一个例子

这里给出了S的代码片段

Image6-22.png

S节点对应着while产生式的应用

Image6-23.png

S3对应着一个if-else语句的应用

Image6-24.png

最后得出完整的三地址码

Image6-25.png

布尔表达式的回填

在对布尔表达式和控制流语句生成中间代码的时候,关键的问题是确定跳转指令的目标标号,再生成跳转指令的时候,目标标号还不能确定。那么解决这一问题的方法,就是将存放标号的地址作为继承属性传递到作为跳转指令生成的地方。

但是这样做需要进一步的处理,将标号同具体的地址绑定起来,所以需要用到回填的技术

回填(Backpatching)
基本思想:
生成一个跳转指令时,暂时不指定该跳转指令的目标标号。这样的指令都被放入由跳转指令组成的列表中。同一个列表中的所有跳转指令具有相同的目标标号。等到能够确定正确的目标标号时,才去填充这些指令的目标标号

首先介绍布尔表达式的回填,我们给非终结符B设置了两个属性

  • B.truelist:指向一个包含跳转指令的列表,这些指令最终获得的目标标号就是当B为真时控制流应该转向的指令的标号
  • B.falselist:指向一个包含跳转指令的列表,这些指令最终获得的目标标号就是当B为假时控制流应该转向的指令的标号

因此我们构造三个函数

  • makelist( i )
    创建一个只包含i的列表,i是跳转指令的标号,函数返回指向新创建的列表的指针
  • merge( p1, p2 )
    将p1和p2指向的列表进行合并,返回指向合并后的
    列表的指针
  • backpatch( p, i )
    将i作为目标标号插入到 p所指列表中的各指令中

布尔表达式回填的翻译方案

B→E1 repol E2 
{
B.truelist = makelist(nextquad);
B.falselist = makelist(nextquad+1);
gen(‘if ’ E1.addr relop E2.addr ‘goto _’);
gen(‘goto _’);
}
B→true 
{
B.truelist = makelist(nextquad);
gen(‘goto _’);
}
B → false
{
B.falselist = makelist(nextquad);
gen(‘goto _’);
}
B → (B1)
{
B.truelist = B1.truelist ;
B.falselist = B1.falselist 
}
B → nor B1
{
B.truelist = B1.falselist
;B.falselist = B1.truelist
}

Image6-26.png

为了记住B2的第一条指令的标号,我们在非终结符B2之前插入一个标记非终结符M,M用于记录B2的第一条指令的标号,并给M增加了一个属性quad,用于记下下一条指令的标号,即netxquad,因为我们把M放在了B2之前,因此M.quad记录的就是B2的第一条指令的标号,即netxquad

Image6-27.png

这里M的作用和上面的用处一致

Image6-28.png

此处假设下一条指令从100号处开始编写

这里最后举了一个例子总结了上面的用法

Image6-29.png

控制流语句的回填

先给出控制流语句的文法

Image6-30.png

这里我们为S设置了综合属性S.nextlist
指向一个包含跳转指令的列表,这些指令最终获得的标号就是按照运算顺序紧跟在代码S之后的指令的标号

接下来给出每种情况对对应的翻译方案

Image6-31.png

B.truelist中的所有指令要跳转到B的真出口,即S1的第一条指令,B.falselist中的指令要跳转到B的假出口,当B为假的时候我们要跳出If语句,去执行S之后的第一条指令,因此B.falselist中的所有指令都应该放入S.nextlist中,对于S1来说,S1.nextlist中的所有指令都要跳转到S1之后的第一条指令中,当S1执行完毕,整个if语句就执行完毕,接下来要执行S之后的第一条指令,去执行S.nextlist中的所有指令,因此S1.nextlist中的所有指令都应该放入S.nextlist中。

在分析这个图的时候我们发现,我们需要用S1的第一条指令的标号来回填B.truelist中的各条指令,因此我们需要记录下S1的第一条指令的标号,为此在S1之前设置M(其实和上面没什么区别)

Image6-32.png

Image6-33.png

Image6-34.png

再赋值语句中,没有跳转指令,所以S.nextlis=null;

举个例子

while a < b do
    if c < 5 then
        while x > y do z = x + 1;
    else
            x =  y;

Image6-35.png

Image6-36.png

倒是不难,但是挺麻烦的啊

switch语句的翻译

先给出switch语句的伪代码

switchE
    begin
        case V1: S1
        case V2: S2
        ...
        case Vn–1: Sn – 1
        default:Sn
end

接下来绘制switch语句的代码结构图

Image6-37.png

为了简单起见,我们将各个分支测试指令集中在一起,这样便于在代码分析阶段生成高效的分支测试代码,于是给出了一个新的代码结构图

Image6-38.png

接下来编写翻译方案

Image6-39.png

为了便于代码生成器检测到这些分支生成代码,我们引入一种新的指令

Image6-40.png

过程调用语句的翻译

先给出文法

S→call id (Elist)
Elist→Elist, E
Elist→E

给出过程调用语句的代码结构

Image6-41.png

其中我们需要一个队列q存放E1.addr、E2.addr…En.addr

编写翻译方案

Image6-42.png

Last modification:February 3rd, 2019 at 03:28 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment