編譯原理 中間代碼優(yōu)化

1、實(shí)驗(yàn)三 中間的代碼優(yōu)化某些編譯程序在中間代碼或目標(biāo)代碼生產(chǎn)之后要對其進(jìn)行優(yōu)化，所謂優(yōu)化就是對代碼進(jìn)行等價(jià)的變換。而變換后的代碼運(yùn)行結(jié)果與變換前的代碼運(yùn)行結(jié)果相同。而運(yùn)行速度加快或占用內(nèi)存空間減少。中間的代碼優(yōu)化就是對中間代碼進(jìn)行等價(jià)的變換。 基本塊的有向圖 DAG（Directed Acyclic Graph)有向圖中任何一條通路都不是環(huán)路，則稱該有向圖為無環(huán)路有向圖，簡稱為DAG。一、 實(shí)驗(yàn)題目：中間代碼的局部優(yōu)化二、 實(shí)驗(yàn)?zāi)康模赫莆站植績?yōu)化方法、提高機(jī)器的運(yùn)行速度三、實(shí)驗(yàn)內(nèi)容：1 、構(gòu)造基本塊內(nèi)的優(yōu)化DAG 假設(shè)：（1） ni 為已知結(jié)點(diǎn)號，n為新結(jié)點(diǎn)號；（2）訪問各結(jié)點(diǎn)信息時(shí)，按結(jié)點(diǎn)號逆

2、序排序2、完成對下例三類表達(dá)式的優(yōu)化（1）常值表達(dá)式的優(yōu)化（2）公共表達(dá)式的優(yōu)化（3）無用賦值的優(yōu)化3、輸出根據(jù)優(yōu)化的DAG重組四元式四、設(shè)計(jì)概要：首先要實(shí)現(xiàn)表達(dá)式中間代碼生成，采用遞歸下降子程序法實(shí)現(xiàn)。ET0 “push(SYN,w)”T“QUAT” TF1”push(SYN,w)”F“QUAT”Fi“push(SEM,entry(w)”|(E)其中：push(SYN,w)-當(dāng)前單詞w入符號棧SYN；push(SEM,entry(w)- 當(dāng)前i在符號表中的入口值壓入語義棧SEM；QUAT-生成四元式函數(shù) T:=newtemp; QTj=(SYNk,SEMs-1,SEMs,T);j+; pop

3、(SYN,_);pop(SEM,_);pop(SEM,_); push(SEM,T);在對中間代碼進(jìn)行局部優(yōu)化五、程序代碼及運(yùn)行結(jié)果：1.表達(dá)式中間代碼生成#include#includeusing 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;

4、s10=sem-j;elses10=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表達(dá)式error!=a&ch=1&ch=9) push_sem(ch);ch=stri+;else/cout表達(dá)式error!endl;return 0;return 1;int T()int k,m,l;k=F();if(k=0)return 0;while(1)/push_syn(

5、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_

6、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;elses00=w;s01= ;cout(w2,s00s01, ,w1)endl;if(k=0) couterror!endl;elseif(ch=#) coutOK!

7、endl;else couterror!endl;return 0;運(yùn)行結(jié)果：2.代碼優(yōu)化：（采用遞歸下降子程序法判斷表達(dá)式是否合法，方法如上）#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/四元式結(jié)構(gòu)char result8;char

8、 ag18;char op;char ag28;quad25,newquad15;struct Ni/節(jié)點(diǎn)結(jié)構(gòu)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

9、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=

10、#;cout請輸入表達(dá)式：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=a)|(ch=A)temp0=ch;push1(sem,temp);ch=progp+;if(ch=)push0(syn,ch);ch=progp+;E();if(m=0)cout錯(cuò)誤1!endl;system(

11、pause); /return;if(ch=;)ch=progp+;quat1();elsecout錯(cuò)誤2!endl;system(pause); return;elsecout錯(cuò)誤3!endl;system(pause); return;elsecout錯(cuò)誤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)c

12、har 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;void push0(char sz,char x)int top;top=strlen(sz);sz

13、top=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+;

14、strcpy(quadj.ag1,semtop-2);strcpy(quadj.ag2,semtop-1);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);

15、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)int m,n,top,l,tag=0,tag1=0,tag2=0;char temp;for(m=0;m0;n-)for(l=0;l25;l+)if(str

16、cmp(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;elseif(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;if(tag!=0)for(l=top+1;l0;n-)for(l

17、=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=te

18、mp; 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(N

19、i-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;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;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