中间代码生成1

1第七章中间代码生成主要内容常见的中间代码结构语法制导方法概论四元式中间代码生成过程2x=u*w/(u*l+1);中间代码:是一种复杂性介于源程序语言和目标语言之间一种语言,中间代码与具体机器无关。(*,u,w,t1）

(*,u,l,t2）(+,t2,1,t3)(/,t1,t3,t4)(=,t4,-,X)LDR,uMULTR,wSTt1,RLDR,uMULTR,lSTt2,RLDR,t2ADDR,1STt3,RLDR,t1DIVR,t3STt4,RLDR,t4STX,R虚拟机指令目标代码：

四元式中间代码：31.生成中间代码的目的便于优化让生成的目标代码效率更高优化不等同于对代码的精简和算法的优化便于移植编译前端：与目标机无关编译后端：与目标机相关4后缀式----逆波兰式特别是表达式的内部表示图结构中间代码抽象语法树有向无环图DAG三地址中间代码三元式四元式2常用的中间代码结构5将运算对象写在前面，把运算符写在后面，因而也称后缀式。程序设计语言中的表示逆波兰表示a+bab+a+b*cabc*+(a+b)*cab+c*(9-5)+2*a-495-2a*+4-表达式E的后缀表示可按照下面方式:如果E是一个变量或常量，则E后缀表示是E本身。如果E是形如E1opE2，则E后缀为E1’E2’op（Ei’为Ei后缀表示）。(E)的后缀表达式就是E的后缀表示E’。2.1后缀式(逆波兰式)逆波兰式的特点:逆波兰式中的变量的次序与中缀式中的变量的次序完全一致。逆波兰式中无括号。逆波兰式中的运算符已按计算顺序排列。程序设计语言中的表示逆波兰表示a+bab+a+b*cabc*+(a+b)*cab+c*(9-5)+2*a-495-2a*+4-7后缀式的最大优点是易于计算机处理处理过程：从左到右扫描后缀式，每碰到运算对象就推进栈；碰到运算符就从栈顶弹出相应目数的运算对象施加运算，并把结果推进栈。最后的结果留在栈顶。

dcbt1bt2t1=c*dt2=b+t1例：表达式b＋c*d的后缀式bcd*+的计值过程后缀式的计算机处理8后缀式表示法很容易扩充到表达式以外的范围

后缀式表示法的扩充语句后缀式表示说明a=b+cabc+==看成二目运算符gotoLLjumpjump看成一目运算符ifES1elseS2(i1)E’(i3)jmp0(i2)S1’(i4)jmp(i3)S2’(i4)每条语句前面(ix)为相应符号所在的序号，每个符号占用一个序号。jmp0为双目运算，表示E’结果为假时跳转到i3处开始执行S2’例

程序段的后缀式表示。if(k>i+j)a:=5;elsea:=b*c+b/d;后缀式表示如下：kij+>(13)jmp0a5:=(22)jmpabc*bd/+:=......2.2抽象语法树抽象语法树AGT（AbstractGrammarTree）可以显示地表示源程序的结构，是常用的一种标准中间代码形式。它的应用由开始的表达式已经推广到了整个程序。

例如：

c:=a*b+a*b:=c+**abab有向无环图DAG（DirectedAcyclicGraph）实际上是从抽象语法树发展而来，不同之处是DAG节点允许有多个父结点，所以当某些节点结构相同时可以共享该节点结构，这也是DAG最大的优点，2.3三地址中间代码所谓三地址是指操作符的两个运算分量及其该操作的运算结果的抽象地址。

(op，operand1，operand2，result)表示result:=operand1opoperand2

最常见的三地址中间代码有三元式和四元式两种。例如：语句a:=b*c+b/d

三元式：编号(op，ARG1，ARG2）

(1)(*,b,c) (2)(/,b,d) (3)(+,(1),(2)) (4)(:=,(3),a)

四元式:(op，ARG1，ARG2，RESULT）

(*,b,c,t1)(/,b,d,t2)(+,t1,t2,t3)(:=,t3,-,a)注：ARG1，ARG2，

RESULT为操作分量和运算结果的抽象地址表示，应包含相应语义信息。14一般的四元式操作符应包括以下几类：1．算术、逻辑、关系运算符

ADDI、ADDF、SUBI、SUBF、MULTI、

MULTF、DIVI、DIVF、MOD、AND、

OR、EQ、NE、GT、GE、LT、LE2．I/O操作(READI，─，─，id)…………整数输入(READF，─，─，id)…………实数输入(WRITE，─，─，id)…………输出id153．类型转换(FLOAT，id1，─，id2)…id2:=float(id1)4．赋值(ASSIG，id1，-，id2)…id2:=id15．地址加(AADD，id1，id2，id3)

…id3:=addr(id1)+id2

注：AADD为地址加操作，也可以用[+]表示166．标号定义(LABEL，─，─，label)….定义标号label7．条件/无条件转移(JMP，─，─，label)…转向标号label(JMP0，id，─，label)或(JMPF，id，─，label)

…若id＝0，则转label(JMP1，id，─，label)或(JMPT，id，─，label)…若id＝1，则转label178．过程调用(ENTRY，Label，Size，Level)………子程序入口(CALL，f，─，Result)………过程或函数调用9．传送参数VARACT变参类型

VALACT值参类型FUNACT函数参数PROACT过程参数18例：将下列表达式翻译成四元式序列。

X*2+A*(i+1)/(j+1)其中i和j为整型变量，其它为实型变量。(FLOAT,2,_,t1)(MULTF,X,t1,t2)(ADDI,i,1,t3)(FLOAT,t3,_,t4)(MULTF,A,t4,t5)(ADDI,j,1,t6)(FLOAT,t6,_,t7)(DIVF,t5,t7,t8)(ADDF,t2,t8,t9)193类型检查和类型转换

类型检查是静态语义分析的重要工作之一，为方便起见，我们把类型检查的工作也放在中间代码生成时进行。类型检查主要有以下几种：类型相容性检查项目类型检查的语法单元⑴各种条件表达式的类型是否是布尔类型？if语句、while语句、do语句⑵运算符的运算分量类型是否相容？表达式⑶赋值语句的左、右部类型是否相容？赋值语句⑷实参与形参的类型是否相容？过程调用语句、函数调用语句⑸下标表达式的类型是否为所允许的类型？下标变量⑹函数说明中的函数类型与返回值的类型是否一致？return语句20语法制导方法概论

语法制导技术在处理和规则有关联的任务中有着重要的应用；语法制导就是在进行语法分析的同时要完成相应的语义动作，这些语义动作都是由一些程序组成的，要完成和用户的需求相关联的任务；编译器对一个串进行语法检查的同时，可以在每个产生式的相应位置增加语义动作，在语法分析过程中，如遇语义动作，就进行对应的语义处理，完成语义分析、中间代码生成和目标代码生成等任务。21语法制导方法的组成：语法制导方法包括两个部分:抽象描述部分：即带有动作符的文法描述，称为动作文法；实现部分：语法分析的同时能够处理语义动作的驱动程序。例如：有动作语义文法G

G:S→#Init#ABA→aA│b#Add#B→b#Add#B│c#Out_Val#各动作符对应的语义子程序如下：Init

m=0;Out_Val

printf(“%d”,m);

Add

m++;22语法制导方法的种类：语法制导方法依赖于具体的语法分析方法，因此可以分为自顶向下语法制导方法和自底向上语法制导方法。自顶向下语法制导方法中通常采用LL(1)分析方法为基础，而自底向上语法制导方法中通常以LR(1)分析方法为基础。23LL(1)语法制导方法的实例设有如下LL(1)文法：G:S→ABA→aA│bB→bB│c要求：应用语法制导翻译方法完成如下任务：对输入文法G的任意句子L，输出L中b串的长度。如串abbbc是G的句子，则该处理器将输出3。24abc#SA

B

G的原始LL(1)分析表G:S→ABA→aA

│bB→bB│cS→ABS→ABA→aAA→bB→bBB→c25

G的动作文法如下：G:S→#Init#ABA→aA│b#Add#B→b#Add#B│c#Out_Val#各动作符对应的语义子程序如下：voidInit(){m=0；}voidAdd(){

m++;}voidOut_Val(){printf(“%d”,m);}

26G的带动作符的LL(1)分析表abc#SS→#init#ABS→#init#ABAA→aAA→b#Add#BB→b#Add#BB→c

#Out_Val#G[S]:S→#init#

ABA→aA│b#Add#B→b#Add#B│c#Out_Val#27#Init#m=0

#init#AB#替换对给定的终极符串abbbc，分析过程：S#

abbbc#替换匹配Match语法制导的实现过程（1）例G[s]:[1]S→#init#AB [2]A→aA [3]A→b#Add# [4]B→b#Add#B [5]B→c

#Out_Val#

{a,b}{b}{c}{a}{b}

abbbc#

AB#

aAB#

b#Add#B#替换#Add#m=1匹配Match

abbbc#

abbbc#

AB#

bbbc#

bbbc#

bbc#

#Add#B#

B#

bbc#

符号栈输入流动作28Success对给定的终极符串abbbc，分析过程(续）：语法制导的实现过程（2）例G[s]:[1]S→#init#AB [2]A→aA [3]A→b#Add# [4]B→b#Add#

B [5]B→c#Out_Val#

{a,b}{b}{c}{a}{b}替换

B#

bbc#

b#Add#

B#

bbc#匹配Match#Add#m=2

#Add#

B#

bc#

B#

bc#

b#Add#

B#

bc#替换匹配Match

#Add#B#

c##Add#m=3

B#

c#替换

c#Out_Val#

#

c#匹配Match

#Out_Val#

#

##Out_Val#输出3

#

#对给定的终极符串abbbc，分析过程：利用语法树解析过程例G[s]:[1]S→#init#AB [2]A→aA [3]A→b#Add# [4]B→b#Add#B [5]B→c

#Out_Val#

{a,b}{b}{c}{a}{b}S#initABaAb#Add#b#Add#Bb#Add#Bc#Out_val#30LR(1)语法制导方法在文法的基础上，在产生式的最右部添加语义动作。每当按照LR(1)语法分析进行归约时，用到这个产生式那就调用这个产生式最后面那个动作去完成它所代表的语义子程序。例：在自底向上的语法分析过程中，拟采用以下的语法制导翻译模式，在按一个产生式归约时，立即执行括号里相应的语义动作程序片段。

E

E+T{print“+”}|E-T{print“-”}|TT

T*F{print“*”}|FFi{print“i”}|(E)若输入序列为(i-i)+i*i，则求其分析后的输出序列并说明语法制导功能。输出：ii-ii*+功能中缀表达式转为后缀表达式324中间代码生成中的几个问题（1）语义信息的提取与保存：四元式:(算符op，ARG1，ARG2，运算结果RESULT）ARG1，ARG2，

RESULT为操作分量和运算结果的抽象地址表示(用以生成目标代码时转换为相应操作分量存储数据的内存地址)，应包含相应语义信息。语义信息的两种表示方式：1)指向相应符号表的指针2)把对应分量的语义信息放在此处如：3.5+i(ADDF,3.5,(i.level,i.off,dir),(-1,t1.off,dir))33四元式中操作分量或运算结果的抽象地址表示Form：formtype分为三大类：

标号类LabelForm：语义信息Label是相应的标号值，包括过程⁄函数体的入口标号；(LabelForm,Label)

数值类ValueForm：语义信息Value就是该数据值；(ValueForm,value)

地址类AddrForm：语义信息Addr由四部分组成：变量名、层数、偏移和访问方式(分为直接访问方式和间接访问方式)。(AddrForm,name,dataLevel,dataOff,access)

抽象地址Form的ARG_Record结构：例1：四元式中间代码抽象地址Form可表示:(ADDI,a,3,t1)(AddrForm,a,1,3,dir)(ValueForm,3）(AddrForm,-,-1,1,dir)(LabelForm,L1）例2：(JUMP,L1）临时变量ti都是局部变量，没有层数概念，因此对临时变量的层数可以取-1；其次，经过优化后只有少部分临时变量能保留下来，所以在中间代码生成阶段还不能确定临时变量的偏移值，因此偏移暂时取为临时变量的编号。35（2）语义栈Sem及其操作

中间代码生成尤其是变量和表达式的处理过程中要用到语义栈Sem，该栈主要存放运算分量和运算结果的类型和抽象地址表示。对语义栈Sem的操作有push(x):将标识符x的类型和Form压入Sem栈；pop(n):从Sem的栈顶删除n个元素。语义栈Semintptr(AddrForm,x,level,off,dir)TopTypeForm36（3）常用的语义子程序

申请临时单元new_dir(t):

申请一个临时变量t，且t是直接寻址；new_indir(t):申请一个临时变量t，且t是间接寻址。GenCode(ω):

ω为操作码，该子程序功能是产生一条四元式中间代码。此时左、右运算分量语义信息已经在语义栈Sem的次栈顶和栈顶。375表达式的中间代码生成简单表达式的LL(1)文法（1）E→TEs（2）Es→

（3）Es→+TEs（4）Es→-TEs（5）T→PTs（6）Ts→

（7）Ts→*PTs（8）Ts→/PTs（9）P→C（10）P→id（11）P→(E)38简单表达式的带有动作符的LL(1)文法（1）E→TEs（2）Es→

（3）Es→+T#GenCode(+)#Es（4）Es→-T#GenCode(-)#Es（5）T→PTs（6）Ts→

（7）Ts→*P#GenCode(*)#Ts（8）Ts→/P#GenCode(/)#Ts（9）P→C#Push(C)#（10）P→id#Push(id)#（11）P→(E)当遇到常量C和简单变量id时，把它们的语义信息压入语义栈；当处理完一个运算符（+，-，*，/）的右分量时，该运算符的左、右运算分量已经分别存放在语义栈Sem的次栈顶和栈顶的位置，因此可以生成相应的运算符的四元式，并把运算结果的语义信息压入语义栈。39简单表达式的LL(1)分析表Cid()+-*/#E111Es2342T555Ts666786P91011产生式Predict集

(1)E→TEsC,id,(（2）Es→

#,)（3）Es→+TEs＋（4）Es→-TEs－（5）T→PTsC,id,(（6）Ts→

#,),+,-（7）Ts→*PTs＊（8）Ts→/PTs／（9）P→CＣ（10）P→idId

(11）P→(E)(40分析栈S输入流T动作#Ex+y*z#LL[E,id]=[1]#EsT x+y*z#LL[T,id]=[5]#EsTsPx+y*z#LL[P,id]=[10]#EsTs#Push(id)#

id

x+y*z#Match#EsTs#Push(id)#

+y*z##Push(id)#

#EsTs+y*z#表达式x+y*z的中间代码生成过程(1)（1）E→TEs{C,id,(}（2）Es→

{#,)}（3）Es→+T#GenCode(+)#Es{+}（4）Es→-T#GenCode(-)#Es{-}（5）T→PTs{C,id,(}（6）Ts→

{#,),+,-}（7）Ts→*P#GenCode(*)#Ts{*}（8）Ts→/P#GenCode(/)#Ts{/}（9）P→C#Push(C)#{C}（10）P→id#Push(id)#{id}（11）P→(E){(}语义栈Semintptr(x,level,off,dir)TopTopTypeForm41分析栈S

输入流T动作#EsTs +y*z# LL[Ts,+]=[6]#Es +y*z# LL[Es,+]=[3]#Es

#GenCode(+)#T+

+y*z#Match#Es

#GenCode(+)#T

y*z#

LL[T,id]=[5]#Es

#GenCode(+)#TsPy*z#LL[P,id]=[10]#Es

#GenCode(+)#

Ts#Push(id)#

id

y*z#

表达式x+y*z的中间代码生成过程(2)intptr(x.level,x.off,dir)语义栈SemTop（1）E→TEs{C,id,(}（2）Es→

{#,)}（3）Es→+T#GenCode(+)#Es{+}（4）Es→-T#GenCode(-)#Es{-}（5）T→PTs{C,id,(}（6）Ts→

{#,),+,-}（7）Ts→*P#GenCode(*)#Ts{*}（8）Ts→/P#GenCode(/)#Ts{/}（9）P→C#Push(C)#{C}（10）P→id#Push(id)#{id}（11）P→(E){(}TypeForm42分析栈S输入流T动作#Es#GenCode(+)#Ts#Push(id)#

id

y*z#Match

#Es#GenCode(+)#Ts#Push(id)#

*z##Push(id)#

#Es

#GenCode(+)#Ts

*z#分析表表达式x+y*z的中间代码生成过程(3)intptr(x.level,x.off,dir)语义栈Semintptr(y,level,off,dir)TopTop（1）E→TEs{C,id,(}（2）Es→

{#,)}（3）Es→+T#GenCode(+)#Es{+}（4）Es→-T#GenCode(-)#Es{-}（5）T→PTs{C,id,(}（6）Ts→

{#,),+,-}（7）Ts→*P#GenCode(*)#Ts{*}（8）Ts→/P#GenCode(/)#Ts{/}（9）P→C#Push(C)#{C}（10）P→id#Push(id)#{id}（11）P→(E){(}TypeForm43分析栈S输入流T动作#Es

#GenCode(+)#Ts

*z#LL[Ts,*]=[7]#Es

#GenCode(+)#Ts#GenCode(*)#P*

*z#Match

#Es

#GenCode(+)#Ts#GenCode(*)#P

z#

表达式x+y*z的中间代码生成过程(4)intptr(x.level,x.off,dir)语义栈Semintptr(y.level,y.off,dir)Top（1）E→TEs{C,id,(}（2）Es→

{#,)}（3）Es→+T#GenCode(+)#Es{+}（4）Es→-T#GenCode(-)#Es{-}（5）T→PTs{C,id,(}（6）Ts→

{#,),+,-}（7）Ts→*P#GenCode(*)#Ts{*}（8）Ts→/P#GenCode(/)#Ts{/}（9）P→C#Push(C)#{C}（10）P→id#Push(id)#{id}（11）P→(E){(}TypeForm44分析栈S输入流T动作#Es

#GenCode(+)#Ts#GenCode(*)#P

z#

LL[P,id]=[10]

#Es

#GenCode(+)#Ts#GenCode(*)##Push(id)#

id

z#Match

#Es

#GenCode(+)#Ts#GenCode(*)##Push(id)#

#

表达式x+y*z的中间代码生成过程(5)intptr(x.level,x.off,dir)语义栈Semintptr(y.level,y.off,dir)Top（1）E→TEs{C,id,(}（2）Es→

{#,)}（3）Es→+T#GenCode(+)#Es{+}（4）Es→-T#GenCode(-)#Es{-}（5）T→PTs{C,id,(}（6）Ts→

{#,),+,-}（7）Ts→*P#GenCode(*)#Ts{*}（8）Ts→/P#GenCode(/)#Ts{/}（9）P→C#Push(C)#{C}（10）P→id#Push(id)#{id}（11）P→(E){(}TypeForm45分析栈S输入流T动作#Es

#GenCode(+)#Ts#GenCode(*)#

#Push(id)#

#

#Push(id)#

#Es

#GenCode(+)#Ts#GenCode(*)#

#

#GenCode(*)#

#Es

#GenCode(+)#Ts

#

分析表表达式x+y*z的中间代码生成过程(6)intptr(x,level,off,dir)语义栈Semintptr(y,level,off,dir)intptr(z,level,off,dir)(MULTI,(y,level,off,dir),(z,level,off,dir),(-,-1,t1,dir))

(-1,-1,t1off,dir)intptrTopTop（1）E→TEs{C,id,(}（2）Es→

{#,)}（3）Es→+T#GenCode(+)#Es{+}（4）Es→-T#