编译原理-中间代码优化

实验三中间的代码优化某些编译程序在中间代码或目标代码生产之后要对其进行优化，所谓优化就是对代码进行等价的变换。而变换后的代码运行结果与变换前的代码运行结果相同。而运行速度加快或占用内存空间减少。中间的代码优化就是对中间代码进行等价的变换。基本块的有向图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.表达式中间代码生成#includeiostream#includecstdlibusingnamespacestd;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(syn[--n],s[1][0]s[1][1],s[0][0]s[0][1],'t'p++)endl;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!endl;return0;}}else{if((ch='a'&&ch='z')||(ch='1'&&ch='9')){push_sem(ch);ch=str[i++];}else{//cout表达式error!endl;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输入表达式(以'#'结束):;cinstr;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(w2,s[0][0]s[0][1],,w1)endl;}if(k==0)couterror!endl;else{if(ch=='#')coutOK!endl;elsecouterror!endl;}return0;}运行结果：2.代码优化：（采用递归下降子程序法判断表达式是否合法，方法如上）#includeiostream#includecstdlib#includestring.husingnamespacestd;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;i50;i++)for(j=0;j3;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;j25;j++){for(l=0;l8;l++){N[i-1].bz[j][l]='\0';}}for(j=0;j2;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请输入表达式：endl;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!endl;system(pause);/////return;}if(ch==';'){ch=prog[p++];quat1();}else{cout错误2!endl;system(pause);return;}}else{cout错误3!endl;system(pause);return;}}else{cout错误4!endl;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;i8;i++)quad[j].result[i]=p[i];pop1(sem);top--;pop1(sem);top--;for(i=0;i3;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;i8;i++)ag2[i]