编译原理 中间代码优化(15页).doc

-编译原理 中间代码优化-第 15 页实验三 中间的代码优化某些编译程序在中间代码或目标代码生产之后要对其进行优化，所谓优化就是对代码进行等价的变换。而变换后的代码运行结果与变换前的代码运行结果相同。而运行速度加快或占用内存空间减少。中间的代码优化就是对中间代码进行等价的变换。 基本块的有向图 DAG（Directed Acyclic Graph)有向图中任何一条通路都不是环路，则称该有向图为无环路有向图，简称为DAG。一、 实验题目：中间代码的局部优化二、 实验目的：掌握局部优化方法、提高机器的运行速度三、实验内容：1 、构造基本块内的优化DAG 假设：（1） ni 为已知结点号，n为新结点号；（2）访问各结点信息时，按结点号逆序排序2、完成对下例三类表达式的优化（1）常值表达式的优化（2）公共表达式的优化（3）无用赋值的优化3、输出根据优化的DAG重组四元式四、设计概要：首先要实现表达式中间代码生成，采用递归下降子程序法实现。ET0 “push(SYN,w)”T“QUAT” TF1”push(SYN,w)”F“QUAT”Fi“push(SEM,entry(w)”|(E)其中：·push(SYN,w)-当前单词w入符号栈SYN；·push(SEM,entry(w)- 当前i在符号表中的入口值压入语义栈SEM；·QUAT-生成四元式函数 T:=newtemp; QTj=(SYNk,SEMs-1,SEMs,T);j+; pop(SYN,_);pop(SEM,_);pop(SEM,_); push(SEM,T);在对中间代码进行局部优化五、程序代码及运行结果：#include<iostream>#include<cstdlib>using namespace std;char str50;char sem50;char syn50;char ch;int i=0;int j=0;int n=0;int p=1;void push_sem(char w)semj+=w;void push_syn(char w)synn+=w;void Gen()char s22;char w;w=sem-j;if(w>='1'&&w<='9')s01=w;s00=sem-j;elses00=w;s01=' 'w=sem-j;if(w>='1'&&w<='9')s11=w;s10=sem-j;elses10=w;s11=' 'cout<<"("<<syn-n<<","<<s10<<s11<<","<<s00<<s01<<","<<'t'<<p+<<")"<<endl;push_sem('t');push_sem(p+47);int F()int m;int E();if(ch='(')ch=stri+;m=E();if(ch=')') ch=stri+;else/cout<<"表达式error!"<<endl;return 0;else if(ch>='a'&&ch<='z')|(ch>='1'&&ch<='9') push_sem(ch);ch=stri+;else/cout<<"表达式error!"<<endl;return 0;return 1;int T()int k,m,l;k=F();if(k=0)return 0;while(1)/push_syn(ch); if(ch='*')push_syn(ch); ch=stri+; m=F(); if(m=0)return 0; Gen(); else if(ch='/') push_syn(ch); ch=stri+; l=F(); if(l=0)return 0; Gen();else break;return 1;int E()int k,m,l;k=T();if(k=0)return 0;while(1)/push_syn(ch); if(ch='+')push_syn(ch); ch=stri+; m=T(); if(m=0)return 0; Gen(); else if(ch='-') push_syn(ch); ch=stri+; l=T(); if(l=0)return 0; Gen();else break;return 1;int main()int k,q=0;char w1,w2,w;char s12;cout<<"输入表达式(以'#'结束):"cin>>str;w1=stri+;w2=stri+;if(w2!='=') i=i-2;q=1;ch=stri+;k=E();if(q=0)w=sem-j; if(w>='1'&&w<='9') s01=w; s00=sem-j;elses00=w;s01=' 'cout<<"("<<w2<<","<<s00<<s01<<","<<" "<<","<<w1<<")"<<endl;if(k=0) cout<<"error!"<<endl;elseif(ch='#') cout<<"OK!"<<endl;else cout<<"error!"<<endl;return 0;运行结果：2.代码优化：（采用递归下降子程序法判断表达式是否合法，方法如上）#include <iostream>#include <cstdlib>#include <string.h>using namespace std;int i=1; int j=0,n=0; int p; int m=1;int Ti=0;char prog100; char ch;char syn20,sem503; void SEM(void)int i,j;for(i=0;i<50;i+)for(j=0;j<3;j+)semij='0'struct quat/四元式结构char result8;char ag18;char op;char ag28;quad25,newquad15;struct Ni/节点结构int pre2;char op;char bz258;N25;void newN(void)int l,j;i+;for(j=0;j<25;j+)for(l=0;l<8;l+)Ni-1.bzjl='0'for(j=0;j<2;j+)Ni-1.prej=0;Ni-1.op='0'void dagt(void); void newquat(void);void fuzhi(void);/递归语法分析生成中间代码void E(void);void T(void);void F(void);void pop0(char sz);void push0(char sz,char x);void pop1(char sz503);void push1(char sz503,char x3);void quat1(void); void quat0(char w);void print1(void);void print2(void);char *newT(void)char *p;char m8;p=(char *)malloc(8);Ti+;itoa(Ti,m,10);strcpy(p+1,m);p0='t'return(p);void main()p=0;syn0='#'SEM();sem00='#'cout<<"请输入表达式："<<endl; docin.get(ch);if(ch != 'n') progp+=ch;while(ch!='#');p=0;ch=progp+;while(ch!='#')fuzhi();print1();dagt();newquat();print2();void fuzhi(void)char temp3;temp0='0'temp1='0'temp2='0'if(ch<='z'&&ch>='a')|(ch<='Z'&&ch>='A')temp0=ch;push1(sem,temp);ch=progp+;if(ch='=')push0(syn,ch);ch=progp+;E();if(m=0)cout<<"错误1!"<<endl;system("pause"); /return;if(ch='')ch=progp+;quat1();elsecout<<"错误2!"<<endl;system("pause"); return;elsecout<<"错误3!"<<endl;system("pause"); return;elsecout<<"错误4!"<<endl;printf("%d",ch);system("pause"); return;/E、T、F是递归下降子程序的语法分析void E(void)char w;T();while(ch='+'|ch='-')push0(syn,ch);w=synstrlen(syn)-1;ch=progp+;T();quat0(w);void T(void)char w;F();while(ch='*'|ch='/')push0(syn,ch);w=synstrlen(syn)-1;ch=progp+;F();quat0(w);void F(void)char temp3;temp0='0'temp1='0'temp2='0'if(ch='(')ch=progp+;E();if(ch=')')ch=progp+;else m=0;else if(ch<='z'&&ch>='a')|(ch<='Z'&&ch>='A')|(ch<='9'&&ch>='0')temp0=ch;push1(sem,temp);ch=progp+; else m=0;void push0(char sz,char x)int top;top=strlen(sz);sztop=x;top+;sztop+1='0'void pop0(char sz)int top;top=strlen(sz)-1;sztop='0'void push1(char sz503,char x3)int top=1;while(sztop0)top+;strcpy(sztop,x);top+;sztop+10='0'void pop1(char sz503)int top=1;while(sztop0)top+;top-;sztop0='0'sztop1='0'sztop2='0'void quat0(char w)int top=1,i;char *p;while(semtop0)top+;strcpy(quadj.ag1,semtop-2);strcpy(quadj.ag2,semtop-1);quadj.op=w;p=newT();for(i=0;i<8;i+)quadj.resulti=pi;pop1(sem);top-;pop1(sem);top-;for(i=0;i<3;i+)semtopi=quadj.resulti;semtop2='0'j+;void quat1(void)char ag28;int top,i;top=1;while(semtop0)top+;ag20='_'for(i=1;i<8;i+)ag2i='0'strcpy(quadj.ag1,semtop-1);strcpy(quadj.ag2,ag2);quadj.op='='strcpy(quadj.result,semtop-2);pop0(syn);pop1(sem);pop1(sem);j+;void print1(void)int i;cout<<"原来的四元组："<<endl;for(i=0;i<j;i+)cout<<(i+1)<<"、("<<quadi.op<<","<<quadi.ag1<<","<<quadi.ag2<<","<<quadi.result<<")"<<endl;void dagt(void)int m,n,top,l,tag=0,tag1=0,tag2=0;char temp;for(m=0;m<j;m+)tag=0;for(n=i;n>0;n-)for(l=0;l<25;l+)if(strcmp(quadm.ag1,Nn-1.bzl)=0)tag=n;break;if(tag!=0)tag1=tag-1;if('0'<quadm.ag10&&quadm.ag10<'9')goto N3;else goto N3;elseif('0'<quadm.ag10&&quadm.ag10<'9')if(quadm.ag20!='_')if('0'<quadm.ag20&&quadm.ag20<'9')quadm.ag10=quadm.ag10-'0'quadm.ag20=quadm.ag20-'0'switch(quadm.op)case '+':temp=quadm.ag10+quadm.ag20;break;case '-':temp=quadm.ag10-quadm.ag20;break;case '*':temp=quadm.ag10*quadm.ag20;break;case '/':temp=quadm.ag10/quadm.ag20;break;default:break;tag=0;for(n=i;n>0;n-)for(l=0;l<25;l+)if(strcmp(quadm.result,Nn-1.bzl)=0)tag=n;break;if(tag!=0)continue;elsenewN();Ni-1.bz00=temp+'0' ;strcpy(Ni-1.bz1,quadm.result);continue;else newN();tag1=i-1;strcpy(Ni-1.bz0,quadm.ag1);goto N2;else goto N1;else N1:newN();strcpy(Ni-1.bz0,quadm.ag1);tag1=i-1;N3:if(quadm.ag20='_')tag=0;for(n=i;n>0;n-)for(l=0;l<25;l+)if(strcmp(quadm.result,Nn-1.bzl)=0)tag=n;top=l;break;if(tag!=0)for(l=top+1;l<25;l+)strcpy(Ntag-1.bzl-1,Ntag-1.bzl);goto N5;elseN5:if(Ni-1.bz01)if(quadm.result1)top=0;while(Ntag1.bztop0)top+;strcpy(Ntag1.bztop,quadm.result);continue;elsetemp=Ni-1.bz01;strcpy(Ni-1.bz0,quadm.result);top=0;while(Ntag1.bztop0)top+;Ni-1.bztop0='t'Ni-1.bztop1=temp;continue;elsetop=0;while(Ntag1.bztop0)top+;strcpy(Ntag1.bztop,quadm.result);continue;elseN2:tag=0;for(n=i;n>0;n-)for(l=0;l<25;l+)if(strcmp(quadm.ag2,Nn-1.bzl)=0)tag=n;break;if(tag!=0)tag2=tag-1;tag=0;for(n=i;n>0;n-)if(Nn-1.pre0=tag1)&&(Nn-1.pre1=tag2)tag=n;break;if(tag!=0)if(Ntag-1.op=quadm.op)if(!Ntag-1.bz01)top=1;while(Ntag-1.bztop0)top+;strcpy(Ntag-1.bztop,quadm.result);else if(!quadm.result1)temp=Ntag-1.bz01;strcpy(Ntag-1.bz0,quadm.result);top=1;while(Ntag-1.bztop0)top+;Ntag.bztop0='t'Ntag.bztop1=temp; else top=1; while(Ntag-1.bztop0) top+; strcpy(Ntag-1.bztop,quadm.result);continue;elsenewN();Ni-1.op=quadm.op;strcpy(Ni-1.bz0,quadm.result);Ni-1.pre0=tag1;Ni-1.pre1=tag2;continue;elsenewN();Ni-1.op=quadm.op;strcpy(Ni-1.bz0,quadm.result);Ni-1.pre0=tag1;Ni-1.pre1=tag2;continue;elsenewN();strcpy(Ni-1.bz0,quadm.ag2);tag2=i-1;tag=0;for(n=i;n>0;n-)for(l=0;l<25;l+)if(strcmp(quadm.result,Nn-1.bzl)=0)tag=n;top=l;break;if(tag=0)newN();strcpy(Ni-1.bz0,quadm.result);Ni-1.op=quadm.op;Ni-1.pre0=tag1;Ni-1.pre1=tag2;continue;elsefor(l=top+1;l<25;l+)strcpy(Ntag-1.bzl-1,Ntag-1.bzl);newN();strcpy(Ni-1.bz0,quadm.result);Ni-1.op=quadm.op;Ni-1.pre0=tag1;Ni-1.pre1=tag2;void newquat(void)int l,top;for(l=1;l<i;l+)if(Nl.pre1=0&&Nl.pre0=0)if(!Nl.bz01)if('0'<Nl.bz00)&&(Nl.bz00<'9')continue;elsefor(top=1;Nl.bztop1;top+)if(!Nl.bztop0)strcpy(newquadn.ag1,Nl.bz0);newquadn.ag20='_'newquadn.op='='strcpy(newquadn.result,Nl.bztop);n+;else continue;else if(Nl.pre1!=0|Nl.pre0!=0)strcpy(newquadn.ag1,NNl.pre0.bz0);strcpy(newquadn.ag2,NNl.pre1.bz0);newquadn.op=Nl.op;strcpy(newquadn.result,Nl.bz0);n+;if(!Nl.bz01)for(top=1;Nl.bztop0;top+)if(!Nl.bztop1)strcpy(newquadn.ag1,Nl.bz0);newquadn.ag20='_'newquadn.op='='strcpy(newquadn.result,Nl.bztop);n+;void print2(void)int i;cout<<"优化后的代码:"<<endl;for(i=0;i<n;i+)cout<<(i+1)<<"、("<<newquadi.op<<","<<newquadi.ag1<<","<<newquadi.ag2<<","<<newquadi.result<<")"<<endl;运行结果：