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

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

2、序排序2、完成對(duì)下例三類表達(dá)式的優(yōu)化（1）常值表達(dá)式的優(yōu)化（2）公共表達(dá)式的優(yōu)化（3）無(wú)用賦值的優(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入符號(hào)棧SYN；·push(SEM,entry(w)- 當(dāng)前i在符號(hào)表中的入口值壓入語(yǔ)義棧SEM；·QUAT-生成四元式函數(shù) T:=newtemp; QTj=(SYNk,SEMs

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

4、en()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<&

5、lt;","<<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<<"表達(dá)式error!"<<endl;return 0

6、;else if(ch>='a'&&ch<='z')|(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(ch); if(ch='*')push_syn(ch); ch=stri+;

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

8、); 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<<"輸入表達(dá)式(以'#'結(jié)束):"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;

9、 s00=sem-j;elses00=w;s01=' 'cout<<"("<<w2<<","<<s00<<s01<<","<<" "<<","<<w1<<")"<<endl;if(k=0) cout<<"error!"<<endl;elseif(ch='#') cout&

10、lt;<"OK!"<<endl;else cout<<"error!"<<endl;return 0;運(yùn)行結(jié)果：2.代碼優(yōu)化：（采用遞歸下降子程序法判斷表達(dá)式是否合法，方法如上）#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 syn

11、20,sem503; void SEM(void) int i,j;for(i=0;i<50;i+)for(j=0;j<3;j+)semij='0'struct quat/四元式結(jié)構(gòu)char result8;char 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;j<25;j+)for(l=0;l<8;l+)Ni-1.bzjl='0'for(j=0

12、;j<2;j+)Ni-1.prej=0;Ni-1.op='0'void dagt(void); void newquat(void);void fuzhi(void);/遞歸語(yǔ)法分析生成中間代碼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)

13、;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<<"請(qǐng)輸入表達(dá)式："<<endl; docin.get(ch);if(ch != 'n') progp+=ch;while(ch!='#');p=0;c

14、h=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='=&#

15、39;)push0(syn,ch);ch=progp+;E();if(m=0)cout<<"錯(cuò)誤1!"<<endl;system("pause"); /return;if(ch='')ch=progp+;quat1();elsecout<<"錯(cuò)誤2!"<<endl;system("pause"); return;elsecout<<"錯(cuò)誤3!"<<endl;system("pause");

16、 return;elsecout<<"錯(cuò)誤4!"<<endl;printf("%d",ch);system("pause"); return;/E、T、F是遞歸下降子程序的語(yǔ)法分析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='/

17、')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>=

18、9;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

19、+;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+)

20、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(quad

21、j.result,semtop-2);pop0(syn);pop1(sem);pop1(sem);j+;void print1(void)int i;cout<<"原來(lái)的四元組："<<endl;for(i=0;i<j;i+)cout<<(i+1)<<"、("<<quadi.op<<","<<quadi.ag1<<","<<quadi.ag2<<","<<qua

22、di.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;

23、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;br

24、eak;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=te

25、mp+'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;

26、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

27、;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

28、.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,qua

29、dm.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);N