編譯技術(shù)課程設(shè)計(jì)(2013江蘇大學(xué)版本)(共19頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上編譯技術(shù)課程設(shè)計(jì)班 級(jí) 軟件1001 學(xué) 號(hào) 姓 名 張建彬 指導(dǎo)老師 年軼 2013年 6 月目 錄一、目的2二、任務(wù)及要求. 3三、實(shí)驗(yàn)環(huán)境 4四、實(shí)現(xiàn)過程說明. 51.詞法分析器 5（1）單詞符號(hào)表. 2（2）數(shù)據(jù)結(jié)構(gòu) 5（3）函數(shù)說明 6（4）流程圖. 72.語法分析器 8（1）分析方法說明 8（2）文法 8（3）數(shù)據(jù)結(jié)構(gòu).12（4）函數(shù)說明 123.中間代碼生成器. 13（1）屬性文法. 13（2）數(shù)據(jù)結(jié)構(gòu) 13（3）函數(shù)說明. 13（4）流程圖 14五、程序運(yùn)行結(jié)果 15六、總結(jié). 18一、目的是理論與實(shí)踐并重的課程，而其課程設(shè)計(jì)要綜合運(yùn)用一、二年級(jí)所學(xué)的

2、多門課程的內(nèi)容，用來完成一個(gè)小型編譯程序。從而鞏固和加強(qiáng)對(duì)詞法分析、語法分析、語義分析、代碼生成和報(bào)錯(cuò)處理等理論的認(rèn)識(shí)和理解；培養(yǎng)學(xué)生對(duì)完整系統(tǒng)的獨(dú)立分析和設(shè)計(jì)的能力，進(jìn)一步培養(yǎng)學(xué)生的獨(dú)立編程能力。二、任務(wù)和要求基本要求：1 詞法分析器 產(chǎn)生下述小語言的單詞序列這個(gè)小語言的所有的單詞符號(hào)，以及它們的種別編碼和內(nèi)碼值如下表：?jiǎn)卧~符號(hào)種別編碼助記符內(nèi)碼值while1whileif2ifelse3elseswitch4switchcase5case標(biāo)識(shí)符6id符號(hào)表入口地址常數(shù)7num常數(shù)表入口地址=8=+9+*10*11*-12-/13/14relopMT=14relopME14relopLT0

3、i= 1;而絕對(duì)不要寫成 ifi0 i=1;因?yàn)閷?duì)于后者，我們的分析器將無條件地將ifi看成一個(gè)標(biāo)識(shí)符。這個(gè)小語言的單詞符號(hào)的狀態(tài)轉(zhuǎn)換圖，如下圖：2 語法分析器 能識(shí)別由加+ 乘* 乘方 括號(hào)（）操作數(shù)所組成的算術(shù)表達(dá)式，其文法如下：EE+T|TTT*F|FFPF|PP(E)|i 使用的算法可以是：預(yù)測(cè)分析法；遞歸下降分析法；LR分析法等。3 中間代碼生成器 產(chǎn)生上述算術(shù)表達(dá)式的中間代碼（四元式序列）較高要求：1 擴(kuò)充上述小語言的單詞；2 增加語法分析器的功能，能識(shí)別條件語句和循環(huán)語句等；3 增加中間代碼生成器的功能，能產(chǎn)生條件語句和循環(huán)語句等的中間代碼（四元式序列）4 報(bào)錯(cuò)基礎(chǔ)上增加錯(cuò)誤信息

4、；5 將中間代碼翻譯成匯編語言。三、實(shí)驗(yàn)環(huán)境開發(fā)環(huán)境：VC+；Visual Studio；Java開發(fā)環(huán)境語言：C；C+；C#；Java說明：課程設(shè)計(jì)可以使用任何一種語言工具，課程設(shè)計(jì)報(bào)告中請(qǐng)按照自己實(shí)際采用的開發(fā)工具及技術(shù)來寫。四、實(shí)現(xiàn)過程說明1.詞法分析器（1）算法和數(shù)據(jù)結(jié)構(gòu)描述詞法分析階段的基本任務(wù)是從以字符串表示的源程序中識(shí)別出具有獨(dú)立意義的單詞符號(hào)。通過DOS環(huán)境手動(dòng)輸入字符串序列（以$作為結(jié)束標(biāo)志）作為帶分析的源程序，調(diào)用詞法掃描子程序?qū)⒆址远M的形式輸出（若有不屬于該語言單詞符號(hào)出現(xiàn)，則進(jìn)行出錯(cuò)處理），詞法掃描子程序包括了對(duì)源程序的預(yù)處理（忽略、回車換行符等字符），以及對(duì)單

5、詞的識(shí)別和分類，以形成（單詞種別，單詞自身的值）形式的二元組。具體思路如下：首先建立關(guān)鍵字表，將關(guān)鍵字作為特殊標(biāo)示符處理，把它們預(yù)先安排在char *keywords13中，將需要被識(shí)別出的關(guān)鍵字存入表中，當(dāng)掃描程序識(shí)別出標(biāo)識(shí)符時(shí)，查關(guān)鍵字表。如能查到匹配的單詞，則該單詞為關(guān)鍵字，否則為一般標(biāo)識(shí)符。在主函數(shù)中讓用戶輸入要識(shí)別的符號(hào)串，然后將輸入的符號(hào)串讀入到 program500，遇$結(jié)束。再依次掃描program500中的每一個(gè)符號(hào)，調(diào)用Scan ()子函數(shù)分析每一個(gè)符號(hào)，再將分析的結(jié)果輸出，也是遇$結(jié)束。（2）函數(shù)說明在Scan ()子函數(shù)中，先全部初始化，然后讀一個(gè)字符，分析它是什么類型

6、:a.如果是字母類型，則接著往下讀，直到讀到非字母的字符，存入words10中，依次對(duì)比關(guān)鍵字表中的元素，如果相同，則將flags置為相應(yīng)的種別碼，如果全都掃描后沒發(fā)現(xiàn)相同的關(guān)鍵字，則為普通的標(biāo)識(shí)符,返回主函數(shù)輸出。b.如果是數(shù)字類型，首先分析第一個(gè)符號(hào)，接著讀下一個(gè)字符串，直到讀到一個(gè)不是數(shù)字的字符串位置，每讀一個(gè)數(shù)字字符，就將他們轉(zhuǎn)化為相應(yīng)的數(shù)字，使用輾轉(zhuǎn)相乘法，每次都讓number先自乘10，然后加上這個(gè)數(shù)字，這樣就將字符串表示的數(shù)字轉(zhuǎn)化成了相應(yīng)的數(shù)，返回主函數(shù)輸出。c.如果是其他單詞表的符號(hào)，則將他們的flags置為相應(yīng)的種別碼，并將字符存到words 中返回主函數(shù)輸出。主要變量說明：

7、用words10存放構(gòu)成單詞符號(hào)的字符串，并且用于判斷是否為關(guān)鍵字。flags500 存放單詞符號(hào)的種別碼。Number存放整數(shù)值，words存放標(biāo)識(shí)符，關(guān)鍵字或者其他符號(hào)。cntnum按順序存放讀到的字符，為下面語義分析做準(zhǔn)備。Status用于判斷是否為關(guān)鍵字，1是，0不是。（3）流程圖2.語法分析器（1）分析方法說明 本實(shí)驗(yàn)采用遞歸下降分析法，遞歸下降法又稱遞歸子程序法。在程序語言的語法定義中有許多采用遞歸定義。我們?cè)趯?duì)它進(jìn)行語法分析時(shí)，編制的處理程序也采取遞歸的方式，可使其結(jié)構(gòu)簡(jiǎn)單易讀。但由于頻繁地調(diào)用子程序大大地降低了分析速度。其主要思想： 對(duì)每個(gè)非終結(jié)符按其產(chǎn)生式結(jié)構(gòu)寫出相應(yīng)語法分析

8、子程序。因?yàn)槲姆ㄟf歸相應(yīng)子程序也遞歸，子程序的結(jié)構(gòu)與產(chǎn)生式結(jié)構(gòu)幾乎一致。所以稱此種方法稱為遞歸子程序法或遞歸下降法。（2）文法 消除左遞歸和回溯后改造的文法： ETE E +TE| TFT T*FT |FPFFF|P(E)|i LL（1）分析表： i+*( ) # EETEETE EE +TEEE TTFTTFT TTT T FFPFFPF FF F FFPPiP(E)遞歸子程序代碼描述如下：void e();void e1();void e2();void t();void t1();void t2();void f();void f1();void p();void e()coutTEen

9、dl;t();e2();void e1()if(flagstemp=9)cout+Tendl;temp+;t();else if(flagstemp=12)cout-Tendl;temp+;t();elseis_right=0;void e2()if(flagstemp=9|flagstemp=12)coutEEendl; e1(); e2(); else if (flagstemp!=0|flagstemp!=18) coutendl; return ; elseis_right=0;void t()coutFTendl;f();t2();void t1()if(flagstemp=10)c

10、out*Fendl;temp+;f();else if(flagstemp=13)cout/Fendl;temp+;f();else is_right=0;void t2()if(flagstemp=10|flagstemp=13)coutTTendl;t1();t2();else if (flagstemp!=0|flagstemp!=18) coutendl; return ; else is_right=0;void f()coutPFendl;p(); f1();void f1() if(flagstemp=11) coutFendl;temp+;f(); else if (flags

11、temp!=0&flagstemp!=18&flagstemp!=9&flagstemp!=12&flagstemp!=10&flagstemp!=13) coutendl;is_right=0; void p()if(flagstemp=6|flagstemp=7)coutiendl;temp+;elseif(flagstemp=17)cout(E)endl;temp+;e();if(flagstemp=18)cout(E)endl;temp+;elseis_right=0;else is_right =0;（3）數(shù)據(jù)結(jié)構(gòu)語法分析階段的基本任務(wù)是將詞法分析階段產(chǎn)生的二元組作為輸入，根據(jù)語言的

12、語法規(guī)則，識(shí)別出各種語法成分，并判斷該單詞符號(hào)序列是否是該語言的一個(gè)句子。在語法分析階段，采用自上而下的遞歸下降分析法，根據(jù)遞歸下降分析函數(shù)編寫規(guī)則來編寫相應(yīng)的函數(shù)，在各個(gè)函數(shù)的分析過程中調(diào)用詞法分析程序中的掃描程序，發(fā)出“取下一個(gè)單詞符號(hào)”的命令，以取得下一個(gè)單詞符號(hào)的語法分析。詞法分析和語法分析的整體設(shè)計(jì)思想可由以下圖示表示： 語法分析是在詞法分析的基礎(chǔ)上加上判斷是否符合語法規(guī)則的語句。語法分析的基本任務(wù)是使用詞法分析的結(jié)果，使用遞歸下降算法分析是否符合語法規(guī)則，如果符合，則輸出“分析成功”，若果不符合，則輸出“分析失敗”。（4）函數(shù)說明在main函數(shù)調(diào)用e()函數(shù)，如果調(diào)用之后返回時(shí),如

13、果(flagstemp=0)&is_right)為真，就輸出“分析成功”，否則輸出“分析失敗”。其中is_right為設(shè)定的標(biāo)志，初值為1，如果在調(diào)用子函數(shù)的過程中如果有錯(cuò)誤，則置is_right為0。e函數(shù): 調(diào)用t函數(shù)，調(diào)用f函數(shù), 調(diào)用p函數(shù),返回后看是否是+或-，如果是，則調(diào)用 e1函數(shù)，再調(diào)用e2函數(shù)，如果不是，進(jìn)行出錯(cuò)處理，置is_right為0。e1函數(shù)：判斷是不是”+”或者“-” 如果是，調(diào)用f函數(shù)，如果不是，進(jìn)行出錯(cuò)處理，置is_right為0。t函數(shù): 調(diào)用f函數(shù), 調(diào)用p函數(shù),返回后看是否是*或/，如果是，則調(diào)用t1函數(shù)，再調(diào)用t2函數(shù)，如果不是，進(jìn)行出錯(cuò)處理，置is_r

14、ight為0。t1函數(shù)：判斷是不是”*”或者“/” 如果是，調(diào)用f函數(shù)，如果不是，進(jìn)行出錯(cuò)處理，置is_right為0。f函數(shù)：調(diào)用p函數(shù)，f1函數(shù)。f1函數(shù)：判斷是不是”,如果是，調(diào)用f函數(shù)，如果不是，進(jìn)行出錯(cuò)處理，置is_right為0。p函數(shù): 檢查是否標(biāo)識(shí)符，如果是，調(diào)用f1函數(shù)，如果不是，檢查是否是數(shù)值，如果是，調(diào)用f1函數(shù)，如果不是，檢查是否是(，如果不是，進(jìn)行出錯(cuò)處理，置is_right為0。如果是，調(diào)用e函數(shù)，返回后檢查是否是),如果不是，進(jìn)行出錯(cuò)處理，置is_right為0。如果是，調(diào)用f1函數(shù)，返回。3.中間代碼生成器（1）屬性文法 設(shè)：X.val 為文法符號(hào) X 的值屬性

15、；下述屬性文法用于算術(shù)表達(dá)式的求值運(yùn)算：E E1 + T ; | E.val:= E1.val + T.valE E1 - T ; | E.val:= E1.val - T.valE T ; | E.val:= T.valT T1 * F ; | T.val:= T1.val * F.valT T1 / F ; | T.val:= T1.val / F.valTT1F |T.val := T1.valF.valTF ; | T.val:= F.valF( E ) ; | F.val:= E.valF i ; | F.val:= i.val【注】可以看出： X.val 屬性是綜合屬性。（2）數(shù)據(jù)

16、結(jié)構(gòu)語義棧：四元式：注解：一個(gè)四元式是一個(gè)帶有四個(gè)域的記錄結(jié)構(gòu)( op, arg1, arg2, result )op 運(yùn)算符，arg1,arg2 運(yùn)算數(shù)，result 運(yùn)算結(jié)果（3）函數(shù)說明（具體過程參見源代碼）Strn用來存放臨時(shí)變量的序號(hào)。temp用來存放數(shù)組的下表，在主程序中語法分析結(jié)束后，置0.定義函數(shù)newtemp()用于門生一個(gè)新的臨時(shí)變量的名字，具體實(shí)現(xiàn)時(shí)每產(chǎn)生一個(gè)T，就及時(shí)送到符號(hào)表中，也可以不進(jìn)符號(hào)表，直接將單詞值用整數(shù)碼表示。定義函數(shù)siyuan（）,輸出一個(gè)四元式。定義函數(shù)ye() 進(jìn)行中間代碼生成（4）流程圖主流程圖如下:(5) 較高要求i. 擴(kuò)充上述小語言的單詞；i

17、i. 增加語法分析器的功能，能識(shí)別條件語句和循環(huán)語句等；iii. 增加中間代碼生成器的功能，能產(chǎn)生條件語句和循環(huán)語句等的中間代碼（四元式序列）iv. 增加報(bào)錯(cuò)功能；v. 將中間代碼翻譯成匯編語言。 其中1，4功能完成；五、程序運(yùn)行結(jié)果對(duì)于輸入表達(dá)式：a+b*(c-d)/e-f31、詞法分析部分：2、語法分析部分：3、四元式序列部分：4、報(bào)錯(cuò)程序輸出結(jié)果：以“a+b*(c-d ”為例六、總結(jié)通過本次課程設(shè)計(jì)使我對(duì)編譯器的實(shí)現(xiàn)有了進(jìn)一步的認(rèn)識(shí)，也對(duì)編譯原理這門課程的了解更加深入，我深深體會(huì)到，要想學(xué)好一門課程，重在實(shí)踐。通過此次手動(dòng)構(gòu)造詞法分析，語法分析，和四元式的實(shí)現(xiàn)，我認(rèn)識(shí)到做程序設(shè)計(jì)并不是只掌握單純思想和方法就夠的，一定得自己動(dòng)手，這樣才能充分認(rèn)識(shí)到自己的不足，以提高自己的設(shè)計(jì)能力。通過之前書本學(xué)習(xí)，我們知道，編譯原理的編譯過程一般包括：詞法分析、語法分析、語義分析與中間代碼產(chǎn)生、優(yōu)化、目標(biāo)代碼生成五個(gè)階段。通過本次設(shè)計(jì)，要求我們做前3個(gè)階段，也是最重要的3個(gè)階段。3個(gè)子階段的設(shè)計(jì)并不是孤立的，這樣，就實(shí)現(xiàn)了引導(dǎo)我們?cè)诰幾g系統(tǒng)總體結(jié)構(gòu)的指導(dǎo)下逐漸地完成整個(gè)系統(tǒng)的構(gòu)建。無論采用哪種方式，在最后一個(gè)實(shí)驗(yàn)完