編譯原理課程設(shè)計--對pl0進(jìn)行擴(kuò)充和修改

1、<p><b>　　課 程 設(shè) 計</b></p><p>　　課程名稱__編譯原理_ _______</p><p>　　題目名稱__對PL0進(jìn)行擴(kuò)充和修改</p><p>　　學(xué)生學(xué)院__計算機(jī)學(xué)院 ________</p><p>　　專業(yè)班級__計算機(jī)科學(xué)與技術(shù)___</p><

2、;p>　　學(xué) 號 3106006475 </p><p>　　學(xué)生姓名___楊振風(fēng) __ _______</p><p>　　指導(dǎo)教師__ 吳偉民____________</p><p>　　2009 年 1 月 7 日</p><p><b>　　課程設(shè)計概述</b><

3、;/p><p>　　PL0語言是Pascal語言的一個子集，它的編譯程序是一個編譯解釋執(zhí)行系統(tǒng)，PL0的目標(biāo)程序為假想棧式計算機(jī)的匯編語言，與具體的計算機(jī)無關(guān)。編譯程序采用一趟掃描方式，已語法語義分析程序為核心，詞法分析程序和代碼生成的程序都作為一個獨立的過程，當(dāng)語法分析需要讀單詞的時候就調(diào)用詞法分析程序，而當(dāng)語法分析正確需要生成相應(yīng)的目標(biāo)代碼時候 ，就調(diào)用代碼生成程序。此外用表格管理程序建立變量，常量和過程標(biāo)識符的

4、說明與引用之間的信息聯(lián)系，用出錯處理程序?qū)υ~法和語義分析遇到的錯誤給出在源程序中出錯的位置和錯誤性質(zhì)。</p><p>　　本課程設(shè)計通過對PL/0（C語言版）進(jìn)行修改和添加功能完成設(shè)計，通過修改詞法分析程序、語法分析、程序編譯主體block和解釋執(zhí)行等各部分的修改擴(kuò)充，完成基本內(nèi)容和選做內(nèi)容。擴(kuò)充了賦值運算+=、-=，運算++、--，以及擴(kuò)充語句 repeat<語句序列>dowhile<條件&

5、gt;。</p><p><b>　　操作平臺</b></p><p>　　操作系統(tǒng)Windows XP SP3,硬件：AMD athlon 3600+ 1.9GHZ,1G內(nèi)存</p><p>　　軟件：Visual C++6.0創(chuàng)天中文版</p><p><b>　　主要成分的描述</b><

6、/p><p><b>　　符號表</b></p><p>　　根據(jù)符號變量的存儲類別定義及他們除向的位置和次序來確定每一個變量應(yīng)分配的存儲區(qū)及在該區(qū)的具體位置。編譯程序有兩類的存儲區(qū)，即靜態(tài)的存儲區(qū)和動態(tài)的存儲區(qū)。由于本課程設(shè)計沒有添加其他的數(shù)據(jù)類型暫時不需要在符號表里面處理。</p><p>　　運行時存儲組織和管理</p><

7、;p>　　采用棧式存儲分配，運行時每進(jìn)入一個過程，就在棧頂為該過程分配所需的數(shù)據(jù)空間，當(dāng)一個過程工作完畢返回時，它在棧頂?shù)臄?shù)據(jù)空間也即釋放程序運行時的存儲空間，棧中在某一個時刻可能會包含某個過程的幾個活動記錄，即某個過程遞歸調(diào)用的情況，另外同樣一個存儲的位置，可能會不同運行時刻分配給不同的數(shù)據(jù)對象。</p><p><b>　　詞法分析的過程</b></p><p&

8、gt;　　PL0的詞法分析程序GETSYM是一個獨立的過程，其功能是為語法語義分析提供單詞，把輸入的字符串形式的源程序分割成一個個單詞符號傳遞給語法語義分析為此PL0設(shè)置了3個全程變量</p><p>　　SYM 存放每個單詞的類別，用內(nèi)部編碼表示</p><p>　　ID 存放用戶所定義的標(biāo)識符的值。</p><p>　　NUM 存放用戶定義的數(shù)</p>

9、;<p><b>　　語法分析方法</b></p><p>　　在PL/0中是采用遞歸子程序法進(jìn)行語法分析的，具體實現(xiàn)方法是為每個非終結(jié)符寫一個函數(shù)，如遇到變量聲明時調(diào)用變量聲明函數(shù)，遇到常量聲明時調(diào)用常量聲明函數(shù)等。</p><p><b>　　中間代碼表示</b></p><p>　　編譯程序所使用的中間

10、代碼有多種形式。常見的有逆波蘭式，三元式，四元式和樹形表示。</p><p><b>　　目標(biāo)代碼</b></p><p>　　PL0編譯程序所產(chǎn)生的目標(biāo)代碼是一個假想的棧式計算機(jī)匯編語言，可稱為類PCODE指令代碼，它不依賴于任何的實際計算機(jī)指令的格式如下：</p><p>　　其中f代表功能碼，l代表層次差，也就是引用變量或過程的分程序與說

11、明該變量或過程的分程序之間的層次差。a的含義對不同的指令有所區(qū)別。這里我們需要用到的有關(guān)目標(biāo)指令有：LIT LOD STO CAL INT JMP JPC OPR</p><p><b>　　詳細(xì)設(shè)計</b></p><p><b>　　擴(kuò)充賦值運算</b></p><p>　　①首先在頭文件的enum sy

12、mbol中添加自己定義的+=，-=運算的關(guān)鍵字peq和meq。還有#defiine symnum以便詞法分析時能夠正確的識別這些關(guān)鍵字。</p><p>　?、谠谠~法分析程序中添加對+=和-=的識別，也就是在程序中找到getsym函數(shù)，添加如下：</p><p>　　else if(ch=='+')</p><p><b>　　{</

13、b></p><p><b>　　getchdo;</b></p><p>　　if(ch=='=')</p><p><b>　　{ </b></p><p>　　sym=peq;這里是自己的定義的+=的標(biāo)識符</p><p><b>　　g

14、etchdo;</b></p><p><b>　　}</b></p><p>　　else if(ch=='+')</p><p><b>　　{</b></p><p><b>　　sym=ppl;</b></p><p>

15、;<b>　　getchdo;</b></p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p><b>　　sym=plus;</b></p&

16、gt;<p><b>　　}</b></p><p><b>　　}</b></p><p>　　同理對于-=的標(biāo)識符：</p><p>　　else if(ch=='-')</p><p><b>　　{</b></p><p

17、><b>　　getchdo;</b></p><p>　　if(ch=='=')</p><p><b>　　{ </b></p><p>　　sym=meq;這里是自己的定義的+=的標(biāo)識符</p><p><b>　　getchdo;</b></

18、p><p><b>　　}</b></p><p>　　else if(ch=='-')</p><p><b>　　{</b></p><p><b>　　sym=mmi;</b></p><p><b>　　getchdo;&l

19、t;/b></p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　sym=minus;</p><p><b>　　}</b><

20、/p><p><b>　　}</b></p><p>　?、劢又谡Z句處理函數(shù)statement添加如下的代碼：</p><p>　　if(sym==becomes||sym==peq||sym==meq)</p><p><b>　　{</b></p><p>　　peqop=

21、sym;這是自己定義的標(biāo)識符，識別運算符</p><p><b>　　getsymdo;</b></p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p

22、>　　error(13);</p><p><b>　　}</b></p><p>　　memcpy(nxtlev,fsys,sizeof(bool)* symnum);</p><p>　　expressiondo(nxtlev,ptx,lev);</p><p>　　if(i!=0&&peqop

23、==becomes)//賦值</p><p><b>　　{</b></p><p>　　gendo(sto,lev-table[i].level,table[i].adr);//將棧頂?shù)膬?nèi)容送入變量中</p><p><b>　　}</b></p><p>　　if(i!=0&&p

24、eqop==peq)//+=運算</p><p><b>　　{</b></p><p>　　gendo(lod,lev-table[i].level,table[i].adr);//將變量放到棧頂</p><p>　　gendo(opr,0,2); //加法運算</p>&

25、lt;p>　　endo(sto,lev-table[i].level,table[i].adr);//將棧頂?shù)膬?nèi)容送入變量中</p><p><b>　　}</b></p><p>　　if(i!=0&&peqop==meq)//-=運算</p><p><b>　　{</b></p>

26、<p>　　gendo(lod,lev-table[i].level,table[i].adr);//將變量放到棧頂</p><p>　　gendo(opr,0,3);</p><p>　　gendo(opr,0,1); //減法運算</p><p>　　gendo(sto,lev-tabl

27、e[i].level,table[i].adr);//將棧頂?shù)膬?nèi)容送入變量中</p><p><b>　　}</b></p><p>　　2、擴(kuò)充語句repeat dowhile</p><p>　?、偈紫仍陬^文件中的enum symbol中添加repeatsym 和dowhilesym之后同樣在#define symnum名字表的類型數(shù)相應(yīng)的

28、增加，還有在#define norw變化相應(yīng)的數(shù)字。以便在詞法分析時能夠識別。</p><p>　?、趤淼匠跏蓟瘮?shù)void init()中新增設(shè)置保留字，按照字母順序，便于折半查找：</p><p>　　strcpy(&(word[4][0]),"dowhile");</p><p>　　strcpy(&(word[4][0])

29、,"repeat");</p><p>　　接下來在設(shè)置保留字符號：</p><p>　　wsym[4]=dowhilesym;</p><p>　　wsym[4]=repeatsym;</p><p>　?、劢酉聛淼秸Z句處理函數(shù)statement中添加如下的代碼:</p><p><b>

30、;　　else</b></p><p><b>　　{</b></p><p>　　if(sym==repeatsym)/*準(zhǔn)備按照repeat語句處理*/</p><p><b>　　{</b></p><p>　　cx1=cx; /*保存判斷條件超作的位置*/</

31、p><p><b>　　getsymdo;</b></p><p>　　memcpy(nxtlev,fsys,sizeof(bool)*symnum);</p><p>　　nxtlev[dowhilesym]=true;/*后跟符號為do*/</p><p>　　statementdo(fsys,ptx,lev); /*循

32、環(huán)體*/</p><p>　　/cx2=cx; /*保存循環(huán)體的結(jié)束的下一個位置*/</p><p>　　//gendo(jmp,0,cx1);/*回頭重新判斷條件*/</p><p>　　if(sym==dowhilesym)</p><p><b>　　{</b></p><p>

33、<b>　　getsymdo;</b></p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　error(34); /*缺少dowhile*/</p

34、><p><b>　　}</b></p><p>　　conditiondo(nxtlev,ptx,lev); /*調(diào)用條件處理*/</p><p>　　cx2=cx; /*保存循環(huán)體的結(jié)束的下一個位置*/</p><p>　　gendo(jpc,0,0);/*生成條件跳轉(zhuǎn)，但跳出循環(huán)的地址未知*/</p

35、><p>　　gendo(jmp,0,cx1);/*回頭重新判斷條件*/</p><p>　　code[cx2].a=cx; /*反填跳出循環(huán)的地址，與if類似*/</p><p><b>　　}</b></p><p>　　3、增加運算++和--</p><p>　　①首先來到頭文件中找到enu

36、m symbol添加自己定義的++，--運算符關(guān)鍵字ppl和mmi。有#defiine symnum以便詞法分析時能夠正確的識別這些關(guān)鍵字。</p><p>　?、谶@里跟前面不一樣的地方就是還要添加：</p><p>　　facbegsys[ppl]=true;</p><p>　　facbegsys[mmi]=true;</p><p>　

37、　這是一個關(guān)鍵的地方，因為如果把++或—當(dāng)作表達(dá)式的開始符號時候，首先能夠正常的標(biāo)識符一樣。</p><p>　?、墼谠~法分析程序中添加對+=和-=的識別，也就是在程序中找到getsym函數(shù)，添加如下：</p><p>　　else if(ch=='+')</p><p><b>　　{</b></p><p

38、><b>　　getchdo;</b></p><p>　　if(ch=='=')</p><p><b>　　{ </b></p><p>　　sym=peq;這里是自己的定義的+=的標(biāo)識符</p><p><b>　　getchdo;</b></

39、p><p><b>　　}</b></p><p>　　else if(ch=='+')</p><p><b>　　{</b></p><p>　　sym=ppl; 這里是自己的定義的+=的標(biāo)識符</p><p><b>　　getchdo;</

40、b></p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p><b>　　sym=plus;</b></p><p><b>　　

41、}</b></p><p><b>　　}</b></p><p>　　同理對于-=的標(biāo)識符：</p><p>　　else if(ch=='-')</p><p><b>　　{</b></p><p><b>　　getchdo;&l

42、t;/b></p><p>　　if(ch=='=')</p><p><b>　　{ </b></p><p>　　sym=meq;這里是自己的定義的+=的標(biāo)識符</p><p><b>　　getchdo;</b></p><p><b>

43、　　}</b></p><p>　　else if(ch=='-')</p><p><b>　　{</b></p><p>　　sym=mmi; 這里是自己的定義的+=的標(biāo)識符</p><p><b>　　getchdo;</b></p><p>

44、;<b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　sym=minus;</p><p><b>　　}</b></p><p><b>　　

45、}</b></p><p>　?、芨鶕?jù)前面語法描述，可以看出我這里是把i++或i—作為語句或因子來進(jìn)行處理的，這就得在相應(yīng)地方添加語句處理功能。</p><p>　　作為語句處理時，在statement中添加代碼如下：</p><p>　　情況一：如a++，a—運算符在后面：</p><p>　　if(sym==ident)這里是

46、以變量開始</p><p><b>　　{</b></p><p>　　i=position(id,*ptx);變量在符號表的位置</p><p><b>　　if(i==0)</b></p><p><b>　　{</b></p><p>　　erro

47、r(11);出錯處理</p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　if(table[i].kind!=variable)只有對變量才可以做自增自減運算</p>&

48、lt;p><b>　　{</b></p><p>　　error(12);</p><p><b>　　i=0;</b></p><p><b>　　}</b></p><p><b>　　else</b></p><p>&

49、lt;b>　　{</b></p><p><b>　　getsymdo;</b></p><p>　　if(sym==ppl)++運算</p><p><b>　　{ </b></p><p>　　gendo(lod,lev-table[i].level,table[i].ad

50、r);把變量放入棧頂</p><p>　　gendo(lit,0,1);將常量1取到運行棧頂</p><p>　　gendo(opr,0,2);將棧頂和次棧頂?shù)膬?nèi)容作算術(shù)加運算結(jié)果存放在次棧頂</p><p>　　gendo(sto,lev-table[i].level,table[i].adr);將棧頂?shù)膬?nèi)容送入變量中</p><p>&l

51、t;b>　　getsymdo;</b></p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　if(sym==mmi)—運算</p><p>&

52、lt;b>　　{ </b></p><p>　　gendo(lod,lev-table[i].level,table[i].adr); 把變量放入棧頂</p><p>　　gendo(lit,0,1); 將常量1取到運行棧頂</p><p>　　gendo(opr,0,3); 將棧頂和次棧頂?shù)膬?nèi)容作算術(shù)減運算結(jié)果存放在次棧頂</p>

53、<p>　　gendo(sto,lev-table[i].level,table[i].adr); 將棧頂?shù)膬?nèi)容送入變量中</p><p><b>　　getsymdo;</b></p><p><b>　　}</b></p><p>　　情況二：如++a，—a運算符在前面：</p><p&

54、gt;　　if(sym==ppl)</p><p><b>　　{ </b></p><p>　　i=position(id,*ptx);</p><p><b>　　if(i==0)</b></p><p><b>　　{</b></p><p>

55、　　error(11);</p><p>　　}//參考書上面的例子，即I為標(biāo)識符在符號表的位置</p><p><b>　　else{</b></p><p><b>　　getsymdo;</b></p><p>　　gendo(lod,lev-table[i].level,table[i]

56、.adr);把變量放入棧頂</p><p>　　gendo(lit,0,1);將常量1取到運行棧頂</p><p>　　gendo(opr,0,2);將棧頂和次棧頂?shù)膬?nèi)容作算術(shù)加運算結(jié)果存放在次棧頂</p><p>　　gendo(sto,lev-table[i].level,table[i].adr);將棧頂?shù)膬?nèi)容送入變量中</p><p>

57、;<b>　　getsymdo;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　if(sym==mmi)</p><p><b>　　{ </b></p><p>　　

58、i=position(id,*ptx);</p><p><b>　　if(i==0)</b></p><p><b>　　{</b></p><p>　　error(11);</p><p><b>　　}//同理，</b></p><p><b

59、>　　else</b></p><p><b>　　{</b></p><p><b>　　getsymdo;</b></p><p>　　gendo(lod,lev-table[i].level,table[i].adr); 把變量放入棧頂</p><p>　　gendo(lit

60、,0,1); 將常量1取到運行棧頂</p><p>　　gendo(opr,0,3); 將棧頂和次棧頂?shù)膬?nèi)容作算術(shù)減運算結(jié)果存放在次棧頂</p><p>　　gendo(sto,lev-table[i].level,table[i].adr); 將棧頂?shù)膬?nèi)容送入變量中</p><p><b>　　getsymdo;</b></p>

61、<p><b>　　}</b></p><p><b>　　}</b></p><p>　　作為因子處理時，在factor中添加代碼如下：</p><p>　　情況一：如a++，a—運算符在后面：</p><p>　　作為因子處理時，得在因子處理函數(shù)factor中當(dāng)檢測到當(dāng)前單詞是標(biāo)識符

62、時，通過查找名字表確定類型，然后再通過switch進(jìn)行選擇操作，在switch中添加代碼如下：</p><p>　　switch(table[i].kind)</p><p><b>　　{</b></p><p>　　case constant: /*名字為常量*/</p><p>　　gendo(lit,0,tab

63、le[i].val); </p><p>　　getsymdo; /*直接把常量的值入棧*/</p><p><b>　　break;</b></p><p>　　case variable: /*名字為變

64、量*/</p><p>　　gendo(lod,lev-table[i].level,table[i].adr); /*找到變量地址并將其值入棧*/</p><p><b>　　getsymdo;</b></p><p>　　if(sym==ppl)++運算</p><p><b>　　{ </

65、b></p><p>　　gendo(lod,lev-table[i].level,table[i].adr);把變量放入棧頂</p><p>　　gendo(lit,0,1);將常量1取到運行棧頂</p><p>　　gendo(opr,0,2);將棧頂和次棧頂?shù)膬?nèi)容作算術(shù)加運算結(jié)果存放在次棧頂</p><p>　　gendo(sto

66、,lev-table[i].level,table[i].adr);將棧頂?shù)膬?nèi)容送入變量中</p><p><b>　　getsymdo;</b></p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{&l

67、t;/b></p><p>　　if(sym==mmi)—運算</p><p><b>　　{ </b></p><p>　　gendo(lod,lev-table[i].level,table[i].adr); 把變量放入棧頂</p><p>　　gendo(lit,0,1); 將常量1取到運行棧頂</p

68、><p>　　gendo(opr,0,3); 將棧頂和次棧頂?shù)膬?nèi)容作算術(shù)減運算結(jié)果存放在次棧頂</p><p>　　gendo(sto,lev-table[i].level,table[i].adr); 將棧頂?shù)膬?nèi)容送入變量中</p><p><b>　　getsymdo;</b></p><p><b>　　}&

69、lt;/b></p><p>　　case procedur: </p><p>　　getsymdo;/*名字為過程*/</p><p>　　error(21); /*不能為過程*/</p><p><b>　　break;</b></p><p><b>　　}</

70、b></p><p>　　情況二：如++a，—a運算符在前面：</p><p>　　if(sym==ppl)</p><p><b>　　{</b></p><p>　　getsymdo; </p><p>　　if(sym==ident)</p><p><b

71、>　　{</b></p><p>　　i=position(id,*ptx);</p><p><b>　　if(i==0)</b></p><p><b>　　{</b></p><p>　　error(11);</p><p>　　}//參考書上面的例

72、子，即I為標(biāo)識符在符號表的位置</p><p>　　else if(table[i].kind==variable) { </p><p>　　gendo(lod,lev-table[i].level,table[i].adr);把變量放入棧頂</p><p>　　gendo(lit,0,1);將常量1取到運行棧頂</p

73、><p>　　gendo(opr,0,2);將棧頂和次棧頂?shù)膬?nèi)容作算術(shù)加運算結(jié)果存放在次棧頂</p><p>　　gendo(sto,lev-table[i].level,table[i].adr);將棧頂?shù)膬?nèi)容送入變量中</p><p><b>　　getsymdo;</b></p><p><b>　　}<

74、;/b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　if(sym==mmi)<

75、;/p><p><b>　　{</b></p><p><b>　　getsymdo;</b></p><p>　　if(sym==ident)</p><p><b>　　{</b></p><p>　　i=position(id,*ptx);</p

76、><p><b>　　if(i==0)</b></p><p><b>　　{</b></p><p>　　error(11);</p><p>　　}//參考書上面的例子，即I為標(biāo)識符在符號表的位置</p><p>　　else if(table[i].kind==vari

77、able) </p><p><b>　　{</b></p><p>　　gendo(lod,lev-table[i].level,table[i].adr); 把變量放入棧頂</p><p>　　gendo(lit,0,1); 將常量1取到運行棧頂</p><p>　　gendo(opr,0,3); 將棧頂和次棧頂?shù)膬?nèi)

78、容作算術(shù)減運算結(jié)果存放在次棧頂</p><p>　　gendo(sto,lev-table[i].level,table[i].adr); 將棧頂?shù)膬?nèi)容送入變量中</p><p><b>　　getsymdo;</b></p><p><b>　　}</b></p><p><b>　　}

79、</b></p><p><b>　　}</b></p><p><b>　　五、測試用例</b></p><p>　　測試時，完成一個功能就先測試，保證后面的程序不會因前面的不通過而影響到后面的。由于把全部的例子寫在一個PL0文件中，提示程序太長所以就寫了兩個例子，這里就只測試+=，-=賦值運算，++，--運

80、算以及repeat dowhile語句：</p><p>　　六、開發(fā)過程和完成情況</p><p><b>　　開發(fā)過程：</b></p><p>　　這次編譯原理課程設(shè)計是在昨晚實驗的基礎(chǔ)上完成的總體來說難度不是很。之前在做實驗時已對基本的關(guān)鍵字進(jìn)行了添加，這次課程設(shè)計主要是對一些功能進(jìn)行擴(kuò)充和修改。在做+=和-=運算時關(guān)鍵是理解變量在符號

81、表的位置，以及如何進(jìn)行把變量放到棧頂和把棧頂?shù)膬?nèi)容送入變量單元中。在gendo功能上似乎遇到了問題，即3個參數(shù)的功能碼，層差和位移量。關(guān)鍵在理解后面兩個參數(shù)lev-table[i].level和table[i].adr.還有 i=position(id,*ptx)中i的功能。需要 說明的是在做-=運算時結(jié)果總是為負(fù)數(shù)，經(jīng)過慢慢思考其運算的過程，最終也解決了。其實在這一步一步的過程就逐漸理解PL0的過程。到了repeat dowhile

82、的過程，參照了原來程序就帶有的功能。即while do，難度也不是很大！在做++，--運算時，開始時候在statement函數(shù)添加了處理語句。對于a++能編譯通過，而++a就不行，后面在網(wǎng)上參考了例子，原來還有一種情況就是++當(dāng)作因子處理的情況。前面只是當(dāng)作語句處理。之后就能處理形如b:=++a的語句。解決了這些問題后，后面打算添加如for to do的語句，但是在</p><p><b>　　完成情況

83、</b></p><p>　　完成內(nèi)容：擴(kuò)充賦值運算+=，-=和repeat <語句序列>dowhile<條件>，</p><p>　　以及自增++自減—運算。For <條件>to<條件> do<語句序列>最后因為多次調(diào)試沒有通過，也就沒有完成這一功能。</p><p><b>　　七