编译原理中间代码优化.docx

编译原理中间代码优化.docx

《编译原理中间代码优化.docx》由会员分享，可在线阅读，更多相关《编译原理中间代码优化.docx（33页珍藏版）》请在冰点文库上搜索。

编译原理中间代码优化

实验三中间的代码优化

某些编译程序在中间代码或目标代码生产之后要对其进行优化，所谓优化就是对代码进行等价的变换。

而变换后的代码运行结果与变换前的代码运行结果相同。

而运行速度加快或占用内存空间减少。

中间的代码优化就是对中间代码进行等价的变换。

基本块的有向图DAG（DirectedAcyclicGraph）

有向图中任何一条通路都不是环路，则称该有向图为无环路有向图，简称为DAG。

一、实验题目：

中间代码的局部优化

二、实验目的：

掌握局部优化方法、提高机器的运行速度

三、实验内容：

1、构造基本块内的优化DAG

假设：

（1）ni为已知结点号，n为新结点号；

（2）访问各结点信息时，按结点号逆序排序

2、完成对下例三类表达式的优化

（1）常值表达式的优化

（2）公共表达式的优化

（3）无用赋值的优化

3、输出根据优化的DAG重组四元式

四、设计概要：

首先要实现表达式中间代码生成，采用递归下降子程序法实现。

E→T{ω0“push（SYN,w）”T“QUAT”}

T→F{ω1”push（SYN,w）”F“QUAT”}

F→i“push（SEM,entry（w））”|（E）

其中：

·push（SYN,w）---当前单词w入符号栈SYN；

·push（SEM,entry（w））---当前i在符号表中的入口值压入语义栈SEM；

·QUAT---生成四元式函数

①T:

=newtemp;

②QT[j]=（SYN[k],SEM[s-1],SEM[s],T）;j++;

③pop（SYN,_）;pop（SEM,_）;pop（SEM,_）;push（SEM,T）;

在对中间代码进行局部优化

五、程序代码及运行结果：

1.表达式中间代码生成

#include

#include

usingnamespacestd;

charstr[50];

charsem[50];

charsyn[50];

charch;

inti=0;

intj=0;

intn=0;

intp=1;

voidpush_sem（charw）

{

sem[j++]=w;

}

voidpush_syn（charw）

{

syn[n++]=w;

}

voidGen（）

{

chars[2][2];

charw;

w=sem[--j];

if（w>='1'&&w<='9'）

{

s[0][1]=w;

s[0][0]=sem[--j];

}

else

{

s[0][0]=w;

s[0][1]='';

}

w=sem[--j];

if（w>='1'&&w<='9'）

{

s[1][1]=w;

s[1][0]=sem[--j];

}

else

{

s[1][0]=w;

s[1][1]='';

}

cout<<"（"<

push_sem（'t'）;

push_sem（p+47）;

}

intF（）

{

intm;

intE（）;

if（ch=='（'）

{

ch=str[i++];

m=E（）;

if（ch=='）'）ch=str[i++];

else

{

//cout<<"表达式error!

"<

return0;

}

}

else

{

if（（ch>='a'&&ch<='z'）||（ch>='1'&&ch<='9'））

{

push_sem（ch）;

ch=str[i++];

}

else

{

//cout<<"表达式error!

"<

return0;

}

}

return1;

}

intT（）

{

intk,m,l;

k=F（）;

if（k==0）{return0;}

while

（1）

{

//push_syn（ch）;

if（ch=='*'）

{

push_syn（ch）;

ch=str[i++];

m=F（）;

if（m==0）{return0;}

Gen（）;

}

elseif（ch=='/'）

{

push_syn（ch）;

ch=str[i++];

l=F（）;

if（l==0）{return0;}

Gen（）;

}

elsebreak;

}

return1;

}

intE（）

{

intk,m,l;

k=T（）;

if（k==0）{return0;}

while

（1）

{

//push_syn（ch）;

if（ch=='+'）

{

push_syn（ch）;

ch=str[i++];

m=T（）;

if（m==0）{return0;}

Gen（）;

}

elseif（ch=='-'）

{

push_syn（ch）;

ch=str[i++];

l=T（）;

if（l==0）{return0;}

Gen（）;

}

elsebreak;

}

return1;

}

intmain（）

{

intk,q=0;

charw1,w2,w;

chars[1][2];

cout<<"输入表达式（以'#'结束）:

";

cin>>str;

w1=str[i++];

w2=str[i++];

if（w2!

='='）{i=i-2;q=1;}

ch=str[i++];

k=E（）;

if（q==0）

{

w=sem[--j];

if（w>='1'&&w<='9'）

{

s[0][1]=w;

s[0][0]=sem[--j];

}

else

{

s[0][0]=w;

s[0][1]='';

}

cout<<"（"<

}

if（k==0）cout<<"error!

"<

else

{

if（ch=='#'）cout<<"OK!

"<

elsecout<<"error!

"<

}

return0;

}

运行结果：

2.代码优化：

（采用递归下降子程序法判断表达式是否合法，方法如上）

#include

#include

#include

usingnamespacestd;

inti=1;

intj=0,n=0;

intp;

intm=1;

intTi=0;

charprog[100];

charch;

charsyn[20],sem[50][3];

voidSEM（void）

{

inti,j;

for（i=0;i<50;i++）

for（j=0;j<3;j++）

sem[i][j]='\0';

}

structquat//四元式结构

{

charresult[8];

charag1[8];

charop;

charag2[8];

}quad[25],newquad[15];

structNi//节点结构

{

intpre[2];

charop;

charbz[25][8];

}N[25];

voidnewN（void）

{

intl,j;

i++;

for（j=0;j<25;j++）

{

for（l=0;l<8;l++）

{

N[i-1].bz[j][l]='\0';

}

}

for（j=0;j<2;j++）

N[i-1].pre[j]=0;

N[i-1].op='\0';

}

voiddagt（void）;

voidnewquat（void）;

voidfuzhi（void）;

//递归语法分析生成中间代码

voidE（void）;

voidT（void）;

voidF（void）;

voidpop0（charsz[]）;

voidpush0（charsz[],charx）;

voidpop1（charsz[50][3]）;

voidpush1（charsz[50][3],charx[3]）;

voidquat1（void）;

voidquat0（charw）;

voidprint1（void）;

voidprint2（void）;

char*newT（void）

{

char*p;

charm[8];

p=（char*）malloc（8）;

Ti++;

itoa（Ti,m,10）;

strcpy（p+1,m）;

p[0]='t';

return（p）;

}

voidmain（）

{

p=0;

syn[0]='#';

SEM（）;

sem[0][0]='#';

cout<<"请输入表达式：

"<

do

{

cin.get（ch）;

if（ch!

='\n'）prog[p++]=ch;

}while（ch!

='#'）;

p=0;

ch=prog[p++];

while（ch!

='#'）

{

fuzhi（）;

}

print1（）;

dagt（）;

newquat（）;

print2（）;

}

voidfuzhi（void）

{

chartemp[3];

temp[0]='\0';

temp[1]='\0';

temp[2]='\0';

if（（ch<='z'&&ch>='a'）||（ch<='Z'&&ch>='A'））

{

temp[0]=ch;

push1（sem,temp）;

ch=prog[p++];

if（ch=='='）

{

push0（syn,ch）;

ch=prog[p++];

E（）;

if（m==0）

{

cout<<"错误1!

"<

system（"pause"）;/////

return;

}

if（ch==';'）

{

ch=prog[p++];

quat1（）;

}

else

{

cout<<"错误2!

"<

system（"pause"）;

return;

}

}

else

{

cout<<"错误3!

"<

system（"pause"）;

return;

}

}

else

{

cout<<"错误4!

"<

printf（"%d",ch）;

system（"pause"）;

return;

}

}

//E、T、F是递归下降子程序的语法分析

voidE（void）

{

charw;

T（）;

while（ch=='+'||ch=='-'）

{

push0（syn,ch）;

w=syn[strlen（syn）-1];

ch=prog[p++];

T（）;

quat0（w）;

}

}

voidT（void）

{

charw;

F（）;

while（ch=='*'||ch=='/'）

{

push0（syn,ch）;

w=syn[strlen（syn）-1];

ch=prog[p++];

F（）;

quat0（w）;

}

}

voidF（void）

{

chartemp[3];

temp[0]='\0';

temp[1]='\0';

temp[2]='\0';

if（ch=='（'）

{

ch=prog[p++];

E（）;

if（ch=='）'）

{

ch=prog[p++];

}

elsem=0;

}

elseif（（ch<='z'&&ch>='a'）||（ch<='Z'&&ch>='A'）||（ch<='9'&&ch>='0'））

{

temp[0]=ch;

push1（sem,temp）;

ch=prog[p++];

}

elsem=0;

}

voidpush0（charsz[],charx）

{

inttop;

top=strlen（sz）;

sz[top]=x;

top++;

sz[top+1]='\0';

}

voidpop0（charsz[]）

{

inttop;

top=strlen（sz）-1;

sz[top]='\0';

}

voidpush1（charsz[50][3],charx[3]）

{

inttop=1;

while（sz[top][0]）

top++;

strcpy（sz[top],x）;

top++;

sz[top+1][0]='\0';

}

voidpop1（charsz[50][3]）

{

inttop=1;

while（sz[top][0]）

top++;

top--;

sz[top][0]='\0';

sz[top][1]='\0';

sz[top][2]='\0';

}

voidquat0（charw）

{

inttop=1,i;

char*p;

while（sem[top][0]）

top++;

strcpy（quad[j].ag1,sem[top-2]）;

strcpy（quad[j].ag2,sem[top-1]）;

quad[j].op=w;

p=newT（）;

for（i=0;i<8;i++）

quad[j].result[i]=p[i];

pop1（sem）;

top--;

pop1（sem）;

top--;

for（i=0;i<3;i++）

sem[top][i]=quad[j].result[i];

sem[top][2]='\0';

j++;

}

voidquat1（void）

{

charag2[8];

inttop,i;

top=1;

while（sem[top][0]）

top++;

ag2[0]='_';

for（i=1;i<8;i++）

ag2[i]='\0';

strcpy（quad[j].ag1,sem[top-1]）;

strcpy（quad[j].ag2,ag2）;

quad[j].op='=';

strcpy（quad[j].result,sem[top-2]）;

pop0（syn）;

pop1（sem）;

pop1（sem）;

j++;

}

voidprint1（void）

{

inti;

cout<<"原来的四元组：

"<

for（i=0;i

cout<<（i+1）<<"、（"<

}

voiddagt（void）

{

intm,n,top,l,tag=0,tag1=0,tag2=0;

chartemp;

for（m=0;m

{

tag=0;

for（n=i;n>0;n--）

for（l=0;l<25;l++）

{

if（strcmp（quad[m].ag1,N[n-1].bz[l]）==0）

{

tag=n;

break;

}

}

if（tag!

=0）

{

tag1=tag-1;

if（'0'

gotoN3;

elsegotoN3;

}

else

{

if（'0'

{

if（quad[m].ag2[0]!

='_'）

{

if（'0'

{

quad[m].ag1[0]=quad[m].ag1[0]-'0';

quad[m].ag2[0]=quad[m].ag2[0]-'0';

switch（quad[m].op）

{

case'+':

temp=quad[m].ag1[0]+quad[m].ag2[0];break;

case'-':

temp=quad[m].ag1[0]-quad[m].ag2[0];break;

case'*':

temp=quad[m].ag1[0]*quad[m].ag2[0];break;

case'/':

temp=quad[m].ag1[0]/quad[m].ag2[0];break;

default:

break;

}

tag=0;

for（n=i;n>0;n--）

for（l=0;l<25;l++）

{

if（strcmp（quad[m].result,N[n-1].bz[l]）==0）

{

tag=n;

break;

}

}

if（tag!

=0）

continue;

else

{

newN（）;

N[i-1].bz[0][0]=temp+'0';

strcpy（N[i-1].bz[1],quad[m].result）;

continue;

}

}

else

{

newN（）;

tag1=i-1;

strcpy（N[i-1].bz[0],quad[m].ag1）;

gotoN2;

}

}

elsegotoN1;

}

else

N1:

{

newN（）;

strcpy（N[i-1].bz[0],quad[m].ag1）;

tag1=i-1;

N3:

if（quad[m].ag2[0]=='_'）

{

tag=0;

for（n=i;n>0;n--）

for（l=0;l<25;l++）

{

if（strcmp（quad[m].result,N[n-1].bz[l]）==0）

{

tag=n;

top=l;

break;

}

}

if（tag!

=0）

{

for（l=top+1;l<25;l++）

{

strcpy（N[tag-1].bz[l-1],N[tag-1].bz[l]）;

}

gotoN5;

}

else

{

N5:

if（N[i-1].bz[0][1]）

{

if（quad[m].result[1]）

{

top=0;

while（N[tag1].bz[top][0]）

top++;

strcpy（N[tag1].bz[top],quad[m].result）;

continue;

}

else

{

temp=N[i-1].bz[0][1];

strcpy（N[i-1].bz[0],quad[m].result）;

top=0;

while（N[tag1].bz[top][0]）

top++;

N[i-1].bz[top][0]='t';

N[i-1].bz[top][1]=temp;

continue;

}

}

else

{

top=0;

while（N[tag1].bz[top][0]）

top++;

strcpy（N[tag1].bz[top],quad[m].result）;

continue;

}

}

}

else

N2:

{

tag=0;

for（n=i;n>0;n--）

for（l=0;l<25;l++）

{

if（strcmp（quad[m].ag2,N[n-1].bz[l]）==0）

{

tag=n;

break;

}

}

if（tag!

=0）

{

tag2=tag-1;

tag=0;

for（n=i;n>0;n--）

if（（N[n-1].pre[0]==tag1）&&（N[n-1].pre