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

实验三中间的代码优化某些编译程序在中间代码或目标代码生产之后要对其进行优化，所谓优化就是对代码进行等价的变换。而变换后的代码运行结果与变换前的代码运行结果相同。而运行速度加快或占用内存空间减少。中间的代码优化就是对中间代码进行等价的变换。基本块的有向图DAG（Directed Acyclic Graph)有向图中任何一条通路都不是环路，则称该有向图为无环路有向图，简称为DAG。一、实验题目：中间代码的局部优化二、实验目的：掌握局部优化方法、提高机器的运行速度三、实验内容：1、构造基本块内的优化DAG假设：（1）ni 为已知结点号，n 为新结点号；（2）访问各结点信息时，按结点号逆序排序2、完成对下例三类表达式的优化（1）常值表达式的优化（2）公共表达式的优化（3）无用赋值的优化3、输出根据优化的DAG 重组四元式四、设计概要：首先要实现表达式中间代码生成，采用递归下降子程序法实现。ET 0“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);名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 39 页 -在对中间代码进行局部优化名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 39 页 -五、程序代码及运行结果：1.表达式中间代码生成#include#include 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=1&w=9)s11=w;s10=sem-j;名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 39 页 -else s10=w;s11=;cout(syn-n,s10s11,s00s01,tp+)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!=a&ch=1&ch=9)push_sem(ch);ch=stri+;else /cout表达式 error!endl;return 0;return 1;int T()名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 39 页 -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=-)名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 39 页 -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;coutstr;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;else s00=w;s01=;cout(w2,s00s01,w1)endl;if(k=0)couterror!endl;else if(ch=#)coutOK!endl;else couterror!endl;名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 39 页 -return 0;运行结果：2.代码优化：（采用递归下降子程序法判断表达式是否合法，方法如上）#include#include#include 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;i50;i+)for(j=0;j3;j+)semij=0;struct quat/四元式结构 char result8;char ag18;char op;char ag28;名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 39 页 -quad25,newquad15;struct Ni/节点结构 int pre2;char op;char bz258;N25;void newN(void)int l,j;i+;for(j=0;j25;j+)for(l=0;l8;l+)Ni-1.bzjl=0;for(j=0;j2;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);名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 39 页 -strcpy(p+1,m);p0=t;return(p);void main()p=0;syn0=#;SEM();sem00=#;cout 请输入表达式：endl;do cin.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=a)|(ch=A)temp0=ch;push1(sem,temp);ch=progp+;if(ch=)push0(syn,ch);ch=progp+;名师资料总结-精品资料欢迎下载-名师精心整理-第 9 页，共 39 页 -E();if(m=0)cout 错误 1!endl;system(pause);/return;if(ch=;)ch=progp+;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是递归下降子程序的语法分析void E(void)char w;T();while(ch=+|ch=-)push0(syn,ch);w=synstrlen(syn)-1;ch=progp+;名师资料总结-精品资料欢迎下载-名师精心整理-第 10 页，共 39 页 -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=a)|(ch=A)|(ch=0)temp0=ch;push1(sem,temp);ch=progp+;else m=0;名师资料总结-精品资料欢迎下载-名师精心整理-第 11 页，共 39 页 -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);名师资料总结-精品资料欢迎下载-名师精心整理-第 12 页，共 39 页 -quadj.op=w;p=newT();for(i=0;i8;i+)quadj.resulti=pi;pop1(sem);top-;pop1(sem);top-;for(i=0;i3;i+)semtopi=quadj.resulti;semtop2=0;j+;void quat1(void)char ag28;int top,i;top=1;while(semtop0)top+;ag20=_;for(i=1;i8;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;ij;i+)cout(i+1)、(quadi.op,quadi.ag1,quadi.ag2,quadi.result)endl;void dagt(void)名师资料总结-精品资料欢迎下载-名师精心整理-第 13 页，共 39 页 -int m,n,top,l,tag=0,tag1=0,tag2=0;char temp;for(m=0;m0;n-)for(l=0;l25;l+)if(strcmp(quadm.ag1,Nn-1.bzl)=0)tag=n;break;if(tag!=0)tag1=tag-1;if(0quadm.ag10&quadm.ag109)goto N3;else goto N3;else if(0quadm.ag10&quadm.ag109)if(quadm.ag20!=_)if(0quadm.ag20&quadm.ag200;n-)for(l=0;l0;n-)for(l=0;l25;l+)if(strcmp(quadm.result,Nn-1.bzl)=0)tag=n;top=l;break;名师资料总结-精品资料欢迎下载-名师精心整理-第 15 页，共 39 页 -if(tag!=0)for(l=top+1;l0;n-)for(l=0;l0;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;名师资料总结-精品资料欢迎下载-名师精心整理-第 17 页，共 39 页 -else top=1;while(Ntag-1.bztop0)top+;strcpy(Ntag-1.bztop,quadm.result);continue;else newN();Ni-1.op=quadm.op;strcpy(Ni-1.bz0,quadm.result);Ni-1.pre0=tag1;Ni-1.pre1=tag2;continue;else newN();Ni-1.op=quadm.op;strcpy(Ni-1.bz0,quadm.result);Ni-1.pre0=tag1;Ni-1.pre1=tag2;continue;else newN();strcpy(Ni-1.bz0,quadm.ag2);tag2=i-1;tag=0;for(n=i;n0;n-)for(l=0;l25;l+)if(strcmp(quadm.result,Nn-1.bzl)=0)tag=n;top=l;break;名师资料总结-精品资料欢迎下载-名师精心整理-第 18 页，共 39 页 -if(tag=0)newN();strcpy(Ni-1.bz0,quadm.result);Ni-1.op=quadm.op;Ni-1.pre0=tag1;Ni-1.pre1=tag2;continue;else for(l=top+1;l25;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;li;l+)if(Nl.pre1=0&Nl.pre0=0)if(!Nl.bz01)if(0Nl.bz00)&(Nl.bz009)continue;else for(top=1;Nl.bztop1;top+)if(!Nl.bztop0)名师资料总结-精品资料欢迎下载-名师精心整理-第 19 页，共 39 页 -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;in;i+)cout(i+1)、(newquadi.op,newquadi.ag1,newquadi.ag2,newquadi.result)名师资料总结-精品资料欢迎下载-名师精心整理-第 20 页，共 39 页 -endl;运行结果：名师资料总结-精品资料欢迎下载-名师精心整理-第 21 页，共 39 页 -endl;运行结果：名师资料总结-精品资料欢迎下载-名师精心整理-第 22 页，共 39 页 -endl;运行结果：名师资料总结-精品资料欢迎下载-名师精心整理-第 23 页，共 39 页 -endl;运行结果：名师资料总结-精品资料欢迎下载-名师精心整理-第 24 页，共 39 页 -endl;运行结果：名师资料总结-精品资料欢迎下载-名师精心整理-第 25 页，共 39 页 -endl;运行结果：名师资料总结-精品资料欢迎下载-名师精心整理-第 26 页，共 39 页 -endl;运行结果：名师资料总结-精品资料欢迎下载-名师精心整理-第 27 页，共 39 页 -endl;运行结果：名师资料总结-精品资料欢迎下载-名师精心整理-第 28 页，共 39 页 -endl;运行结果：名师资料总结-精品资料欢迎下载-名师精心整理-第 29 页，共 39 页 -endl;运行结果：名师资料总结-精品资料欢迎下载-名师精心整理-第 30 页，共 39 页 -endl;运行结果：名师资料总结-精品资料欢迎下载-名师精心整理-第 31 页，共 39 页 -endl;运行结果：名师资料总结-精品资料欢迎下载-名师精心整理-第 32 页，共 39 页 -endl;运行结果：名师资料总结-精品资料欢迎下载-名师精心整理-第 33 页，共 39 页 -endl;运行结果：名师资料总结-精品资料欢迎下载-名师精心整理-第 34 页，共 39 页 -endl;运行结果：名师资料总结-精品资料欢迎下载-名师精心整理-第 35 页，共 39 页 -endl;运行结果：名师资料总结-精品资料欢迎下载-名师精心整理-第 36 页，共 39 页 -endl;运行结果：名师资料总结-精品资料欢迎下载-名师精心整理-第 37 页，共 39 页 -endl;运行结果：名师资料总结-精品资料欢迎下载-名师精心整理-第 38 页，共 39 页 -endl;运行结果：名师资料总结-精品资料欢迎下载-名师精心整理-第 39 页，共 39 页 -