目標(biāo)代碼生成器

1、實(shí)驗(yàn)報告實(shí)驗(yàn)課名稱：編譯原理實(shí)驗(yàn)實(shí)驗(yàn)名稱：目標(biāo)代碼生成器實(shí)驗(yàn)班級：學(xué)號：姓名：時間：2016-4-30一、問題描述 代碼生成器著重考慮兩個問題: 一是如何使生成的目標(biāo)代碼較短；另一個是如何充分利用計(jì)算機(jī)的寄存器，減少目標(biāo)代碼中訪問存儲單元的次數(shù)。這兩個問題直接影響代碼的執(zhí)行速度。其中基本問題:所有代碼生成器都要面對何種中間代碼輸入, （是逆波蘭式，四元式，還是三元式？等問題）何種代碼做為目標(biāo)程序,選擇適當(dāng)?shù)拇a指令,最優(yōu)的寄存器分配方案,和計(jì)算順序等基本問提二、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)逆波蘭式 目標(biāo)代碼 ,采用堆棧。char x1,x2; /* 從語義棧中彈出倆個操作數(shù)，用于判斷與運(yùn)算 */ x2=SEM

2、.top(); /* SEM.top 記得后面要加(),否則沒有值! */ coutx2endl; /* 用于調(diào)試用的，看棧是怎樣變化的 */ SEM.pop(); x1=SEM.top(); coutx1endl; SEM.pop();三、算法設(shè)計(jì)代碼生成算法：對每個四元式: i: A:=B op C，依次執(zhí)行： 1. 以四元式: i: A:=B op C 為參數(shù)，調(diào)用函數(shù)過程GETREG(i: A:=B op C)，返回一個寄存器R，用作存放A的寄存器。 2. 利用AVALUEB和AVALUEC，確定B和C現(xiàn)行值的存放位置B和C。如果其現(xiàn)行值在寄存器中，則把寄存器取作B和C 3. 如果BR

3、，則生成目標(biāo)代碼： LD R, B op R, C否則生成目標(biāo)代碼 op R, C 如果B或C為R，則刪除AVALUEB或AVALUEC中的R。 4. 令A(yù)VALUEA=R, RVALUER=A。 5. 若B或C的現(xiàn)行值在基本塊中不再被引用，也不是基本塊出口之后的活躍變量，且其現(xiàn)行值在某寄存器Rk中，則刪除RVALUERk中的B或C以及AVALUEB或AVALUEC 中的Rk ，使得該寄存器不再為B或C占用。寄存器分配：GETREG(i: A:=B op C) 返回一個用來存放A的值的寄存器（1） 如果B的現(xiàn)行值在某個寄存器Ri中，RVALUERi中只包含B，此外，或者B與A是同一個標(biāo)識符，或

4、者B的現(xiàn)行值在執(zhí)行四元式A:=B op C之后不會再引用，則選取Ri為所需要的寄存器R，并轉(zhuǎn)4；（2 ） 如果有尚未分配的寄存器，則從中選取一個Ri為所需要的寄存器R，并轉(zhuǎn)4；（3 ）從已分配的寄存器中選取一個Ri為所需要的寄存器R。最好使得Ri滿足一下條件： 占用Ri的變量的值也同時存放在該變量的貯存單元中，或者在基本塊中要在最遠(yuǎn)的將來才會引用到或不會引用到。對RVALUERi中每一變量M，如果M不是A，或者如果M是A又是C，但不是B并且B也不在RVALUERi中，則1) 如果AVALUEM不包含M，則生成 目標(biāo)代碼 ST Ri，M2) 如果M是B，或者M(jìn)是C但同時B也在RVALUERi中，

5、則令A(yù)VALUEM=M， Ri ，否則令A(yù)VALUEM=M3) 刪除RVALUERi中的M（4） 給出R，返回。 中間代碼目標(biāo)代碼RVALUEAVALUET:=ABLD R0，AR0含有TT在R0中SUB R0，BU:=ACLD R1，AR0含有TT在R0中SUB R1，CR1含有UU在R1中V:=TUADD R0，R1R0含有VV在R0中R1含有UU在R0中D:=VUADD R0，R1R0含有DD在R0中分配操作寄存器R:GETREG（i:A:=B OP C)取B,C現(xiàn)行值存放的位置B，CB：=AVALUEBC：=AVALUECB=R？生成目標(biāo)代碼Op R,C生成目標(biāo)代碼LD R，BOP R

6、,Cyesno圖1.1 設(shè)計(jì)流程圖程序代碼：#include /* 基本輸入輸出流 */#include /* 運(yùn)用棧，省去自己再寫棧 */#include #include#include using namespace std;/* 數(shù)據(jù)結(jié)構(gòu) * 逆波蘭式 目標(biāo)代碼 */* 目標(biāo)代碼指令：LD，ST，ADD，SUB，MUL，DIV * 相應(yīng)的數(shù)值 ：1， 2， 3， 4， 5， 6 * 數(shù)據(jù)段開始：設(shè)置為a-z；單個寄存器 * acc為寄存器標(biāo)志：為0表示為空，非0，被占用*/char temp=a-1; /* 臨時變量a-z */stack SEM; /* 語義棧 */int s; /*

7、 棧指針 */typedef struct int op; /* 操作符對應(yīng)的數(shù)值 */ char rt; /* 單個寄存器 */ char num; /* 操作數(shù) */ObjType;ObjType OB40; /* 目標(biāo)代碼區(qū) */int o_pt=0; /* 區(qū)指針 */int acc; /* 寄存器標(biāo)志 */char blexp40; /* 逆波蘭式區(qū) */* 代碼區(qū) */* 函數(shù)聲明 */int isop(char); /* 判斷操作符是否是+-/* */void build(char); /* 根據(jù)操作符生成目標(biāo)代碼函數(shù) */void B_O(); /* 生成算法 */char*

8、OpString(int); /* 操作符轉(zhuǎn)化成字符顯示 */void display(); /* 顯示目標(biāo)代碼 */* 判斷當(dāng)前操作符是否是運(yùn)算符 * 如果是返回相應(yīng)的正數(shù)(3-6) * 否則返回零 */int isop(char ch) if(ch=+) return 3; else if(ch=-) return 4; else if(ch=*) return 5; else if(ch=/) return 6; else return 0;/* 目標(biāo)代碼生成表生成目標(biāo)代碼 */*目標(biāo)代碼生成表* 操作符W SEMs-1即x1 SEMs即x2 acc OBJ * +-/* X1 X2 0

9、 LD R,X1;W R,X2; * +-/* X1 X2 K!=0 T=NEW T;ST R,T;LD R,X1;W R,X2;* +-/* R X s-1 W R,X; * +* X R s W R,X; * /- X R s T=NEW T;ST R,T;LD R,X;W R,T; */void build(char ch) char x1,x2; /* 從語義棧中彈出倆個操作數(shù)，用于判斷與運(yùn)算 */ x2=SEM.top(); /* SEM.top 記得后面要加(),否則沒有值! */ coutx2endl; /* 用于調(diào)試用的，看棧是怎樣變化的 */ SEM.pop(); x1=SE

10、M.top(); coutx1endl; SEM.pop(); if(acc=0) /* 如果寄存器沒被占用，直接生成運(yùn)算指令 */ OBo_pt.op=1; /* 裝載SEMS-1即x1 到寄存器R */ OBo_pt.rt=R; OBo_pt.num=x1; o_pt+; OBo_pt.op=isop(ch); /* 生成對應(yīng)的運(yùn)算指令 */ OBo_pt.rt=R; OBo_pt.num=x2; o_pt+; else if(x1!=R&x2!=R&acc!=0) /* x1和x2都不是寄存器的值，且寄存器被占用 */ temp+; /* 申請一個臨時變量，在執(zhí)行代碼生成過程中，由操作系

11、統(tǒng)生成，這個是模擬 */ OBo_pt.op=2; /* 將寄存器的值移出到臨時變量 */ OBo_pt.rt=R; OBo_pt.num=temp; SEM.pop(); /* 將臨時變量壓入語義棧 */ SEM.push(temp); o_pt+; OBo_pt.op=1; /* 裝載操作數(shù) */ OBo_pt.rt=R; OBo_pt.num=x1; o_pt+; OBo_pt.op=isop(ch); /* 生成運(yùn)算指令 */ OBo_pt.rt=R; OBo_pt.num=x2; o_pt+; else if(x1=R&x2!=R&acc=(s-1)/* SEMs-1即x1為寄存器的

12、值而x2是操作數(shù)且acc為s-1，說明寄存器現(xiàn)在的值為x1 */ OBo_pt.op=isop(ch); /* 直接生成運(yùn)算指令，因?yàn)榇藭r的寄存器中已經(jīng)存在一個操作數(shù) */ OBo_pt.rt=R; OBo_pt.num=x2; o_pt+; else if(x1!=R&x2=R&acc=s&(isop(ch)=3|isop(ch)=5)/* 寄存器的值在SEMs即x2，如果操作符為+* */ OBo_pt.op=isop(ch); /* 直接生成運(yùn)算指令 */ OBo_pt.rt=R; OBo_pt.num=x1; o_pt+; else if(x1!=R&x2=R&acc=s&(isop(

13、ch)=4|isop(ch)=6)/* 如果是- /，則需要調(diào)換一下位置 */ temp+; /* 生成臨時變量，用于存儲下寄存器值 */ OBo_pt.op=2; OBo_pt.rt=R; /* 不需要壓棧，因?yàn)轳R上就要用到 */ OBo_pt.num=temp; o_pt+; OBo_pt.op=1; /* 裝載x1如寄存器 */ OBo_pt.rt=R; OBo_pt.num=x1; o_pt+; OBo_pt.op=isop(ch); /* 利用臨時變量生成運(yùn)算指令 */ OBo_pt.rt=R; OBo_pt.num=temp; o_pt+; else /* 出錯處理 */ cout

14、”不符合目標(biāo)代碼生成條件，出錯!”endl; exit(0); SEM.push(R); /* 將寄存器R壓棧，用于下次判斷，而不是寄存器的值 */ s-; return; /* 生成算法 */void B_O() int i=0; /* 置初始值s=0，acc=0，i=0 */ char ch; /* 當(dāng)前處理字符 */ s=0; /* s 為棧頂指示 */ acc=0; while(blexpi!=0) /* 逆波蘭式區(qū)還沒處理完 */ ch=blexpi+; /* 取當(dāng)前處理字符 */ if(isalnum(ch) /* 是操作數(shù)，入棧 */ SEM.push(ch); s+; else

15、 if(isop(ch) /* 是操作符，生成指令 */ build(ch); acc=s; /* acc標(biāo)志到棧頂，因?yàn)镽入棧了，指示R的位置用，是個技巧 */ else /* 字符不符合要求，出錯處理 */ cout”逆波蘭式內(nèi)字符有錯!”endl; exit(0); /*l 將操作指令的數(shù)值轉(zhuǎn)換成相應(yīng)的字符串 */char* OpString(int i) switch(i) case 1: return “LD”; case 2: return “ST”; case 3: return “ADD”; case 4: return “SUB”; case 5: return “MUL”; case 6: return “DIV”; default: cout”操作符有錯!”endl; exit(0); /* 顯示目標(biāo)代碼 */void display() int i; cout”=目標(biāo)代碼=”endl; for(i=0;io_pt;i+) coutOpString(OBi.op)”t”O(jiān)Bi.rt”,”O(jiān)Bi.numendl; int main() cout”逆波蘭式生成目標(biāo)代碼”endl; cout”請輸入逆波蘭式：”endl; gets(blexp); B_O(); display(); return 1;四、界面設(shè)計(jì) 程序包含輸入提示功能和輸出提示功能。五、運(yùn)