1、黑龍江大學(xué)“編譯原理課程設(shè)計(jì)”讀書(shū)報(bào)告學(xué)院 軟件學(xué)院年級(jí) 2012級(jí)專業(yè) 軟件工程學(xué)號(hào) 20122515姓名 張瑞報(bào)告日期 2014年6月28日成績(jī)黑龍江大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院黑龍江大學(xué)軟件學(xué)院概述  “編譯原理”課程是計(jì)算機(jī)專業(yè)中一門(mén)重要的專業(yè)理論課，是一門(mén)理論性和實(shí)踐性都很強(qiáng)的課程。為配合編譯原理課程的教學(xué)，培養(yǎng)學(xué)生的實(shí)際工作能力，加深對(duì)課堂教學(xué)內(nèi)容的理解，通過(guò)設(shè)計(jì)一個(gè)小型編譯器，更深刻地領(lǐng)會(huì)其基本概念、基本工作原理和實(shí)現(xiàn)方法，從而具有初步開(kāi)發(fā)系統(tǒng)軟件和應(yīng)用軟件的實(shí)際能力，特開(kāi)設(shè)此課程設(shè)計(jì)。通過(guò)設(shè)計(jì)、編制、調(diào)試一個(gè)對(duì)PL/0語(yǔ)言進(jìn)行詞法、語(yǔ)法及中間代碼生成的程序，加深對(duì)編譯原理的

2、理解。掌握對(duì)單詞序列的詞法檢查和分析、掌握計(jì)算機(jī)語(yǔ)言的語(yǔ)法分析的過(guò)程。熟練運(yùn)用一種分析方法（自上而下或自下而上的方法）分析一個(gè)給定的文法以及通過(guò)思考以及動(dòng)手制作分析器的過(guò)程來(lái)鍛煉自己的編程能力和邏輯思維能力體會(huì)計(jì)算機(jī)編譯器的奧妙之處。 一、開(kāi)發(fā)環(huán)境簡(jiǎn)介 Microsoft visual C+ 6.0.開(kāi)發(fā)環(huán)境:是指在基本硬件和數(shù)字軟件的基礎(chǔ)上,為支持系統(tǒng)軟件和應(yīng)用軟件的工程化開(kāi)發(fā)和維護(hù)兒使用的一組軟件,簡(jiǎn)稱SDE。它有軟件工具和環(huán)境繼承機(jī)制構(gòu)成,前者用以支持軟件開(kāi)發(fā)的相關(guān)過(guò)程、活動(dòng)和人物,后者為工具集成和軟件的開(kāi)發(fā)、維護(hù)及管理提供統(tǒng)一的支持。1.支持開(kāi)發(fā)完備模型 2.靈活控制二、基本

3、理論闡述、當(dāng)前理論或?qū)嵺`應(yīng)用現(xiàn)狀編譯原理理論和實(shí)踐并重,敘述嚴(yán)謹(jǐn)、簡(jiǎn)明,富有啟發(fā)性,且內(nèi)容深入淺出,便于自學(xué)。編譯原理不僅可以作為高等院校相關(guān)專業(yè)的教材,也可以作為計(jì)算機(jī)專業(yè)人員的參考用書(shū)。編譯器的構(gòu)造工具是根據(jù)用戶輸入的語(yǔ)言的文法,編譯器的構(gòu)造工具可以生成程序來(lái)處理以用戶輸入的文法書(shū)寫(xiě)的文本。隨著計(jì)算機(jī)應(yīng)用范圍的擴(kuò)大,在軟件自動(dòng)生成,文檔處理,特定專業(yè)的語(yǔ)言等領(lǐng)域,編譯器的構(gòu)造工具這一技術(shù)顯得越來(lái)越重要.在分析語(yǔ)法成分時(shí)比較方便直觀,更便于操作。運(yùn)行程序的同時(shí)不斷修正改進(jìn)程序,直至的到最優(yōu)源程序。3、 小型編譯器系統(tǒng)架構(gòu)它是一個(gè)編譯器的架構(gòu).通俗的來(lái)說(shuō),它實(shí)現(xiàn)了一個(gè)庫(kù),在這個(gè)庫(kù)上,可以很容易

4、的實(shí)現(xiàn)不同的編譯相關(guān)的程序,當(dāng)然,編譯器自然是其中最重要的一個(gè). 當(dāng)然其他像編譯時(shí)間的代碼分析也是很容易實(shí)現(xiàn)的。構(gòu)造識(shí)別符號(hào)串的自動(dòng)機(jī)、詞法分析程序的構(gòu)造、語(yǔ)法分析程序的構(gòu)造、中間語(yǔ)言的生成程序、編譯程序的代碼生成。四、小型編譯器主要功能模塊與實(shí)現(xiàn)（1）功能介紹 1. 詞法分析功能：對(duì)代碼進(jìn)行分詞操作，分出以下5類單詞： 關(guān)鍵字、標(biāo)識(shí)符、常量、運(yùn)算符、分隔符。 2. 算術(shù)表達(dá)式、關(guān)系表達(dá)式和邏輯表達(dá)式的分析與化簡(jiǎn)：提取代碼中的所有算術(shù)表達(dá)式，可用LL(1)分析或算符優(yōu)先分析算術(shù)表達(dá)式。關(guān)系表達(dá)式和邏輯表達(dá)式也可用算術(shù)表達(dá)式的程序進(jìn)行分析。分析成功后進(jìn)行化簡(jiǎn)操作，方便語(yǔ)法分析

5、程序分析。  3. LL(1)語(yǔ)法分析：自己寫(xiě)的簡(jiǎn)單C語(yǔ)言的方法，支持賦值語(yǔ)句、判斷語(yǔ)句、循環(huán)語(yǔ)句，用自頂向下的分析方法，對(duì)化簡(jiǎn)之后的單詞流進(jìn)行分析。  4.四元式生成與后綴式。對(duì)詞法分析分詞后的單詞流生成中間代碼。其中算術(shù)表達(dá)式先生成后綴式。然后再根據(jù)后綴式的結(jié)果生成四元式。對(duì)多條邏輯表達(dá)式采用先計(jì)算再跳轉(zhuǎn)的操作。對(duì)if語(yǔ)句判斷跳轉(zhuǎn)，if中的表達(dá)式支持多條邏輯表達(dá)式，但不支持嵌套。while和if相同。  5.匯編語(yǔ)言生成：根據(jù)四元式生成匯編語(yǔ)言。（2）相關(guān)理論1>.詞法分析（英語(yǔ)：lexical analysis）是計(jì)算機(jī)科學(xué)中將字符

6、序列轉(zhuǎn)換為單詞（Token）序列的過(guò)程。進(jìn)行詞法分析的程序或者函數(shù)叫作詞法分析器，也叫掃描器（Scanner）。詞法分析器一般以函數(shù)的形式存在，供語(yǔ)法分析器調(diào)用。詞法分析階段是編譯過(guò)程的第一個(gè)階段，是編譯的基礎(chǔ)。這個(gè)階段的任務(wù)是從左到右一個(gè)字符一個(gè)字符地讀入源程序，即對(duì)構(gòu)成源程序的字符流進(jìn)行掃描然后根據(jù)構(gòu)詞規(guī)則識(shí)別單詞(也稱單詞符號(hào)或符號(hào))。詞法分析程序?qū)崿F(xiàn)這個(gè)任務(wù)。詞法分析程序可以使用Lex等工具自動(dòng)生成。 2>.LL(1)文法：對(duì)文法G的句子進(jìn)行確定的自頂向下語(yǔ)法分析的充分必要條件是，G的任意兩個(gè)具有相同左部的產(chǎn)生式A>| 滿足下列條件： （1）

7、如果、均不能推導(dǎo)出,則 FIRST()  FIRST() = 。（2）  和  至多有一個(gè)能推導(dǎo)出 。 （3）如果  *> ,則 FIRST()  FOLLOW(A) = 。  將滿足上述條件的文法稱為L(zhǎng)L(1)文法。第一個(gè)L代表從左向右掃描輸入符號(hào)串，第二個(gè)L代表產(chǎn)生最左推導(dǎo)，1代表在分析過(guò)程中執(zhí)行每一步推導(dǎo)都要向前查看一個(gè)輸入符號(hào)當(dāng)前正在處理的輸入符號(hào)。LL(1)文法既不是二義性的，也不含左遞歸，

8、對(duì)LL(1)文法的所有句子均可進(jìn)行確定的自頂向下語(yǔ)法分析。并不是所有的語(yǔ)言都可以用LL(1)文法來(lái)描述，而且不存在判定某種語(yǔ)言是否是LL(1)文法的算法。也就是說(shuō)，確定的自頂向下分析只能實(shí)現(xiàn)一部分上下文無(wú)關(guān)語(yǔ)言的分析，這就是LL(1)文法所產(chǎn)生的語(yǔ)言。另外，在上述LL(1)文法的條件中，要求：  FIRST(1)，  FIRST(2)，  FIRST(n) 中至多有一個(gè)成立。 3>.語(yǔ)法分析是編譯過(guò)程的一個(gè)邏輯階段。語(yǔ)法分析的任務(wù)是在詞法分析的基礎(chǔ)上將單詞序列組合成各類語(yǔ)法短語(yǔ)，如“程序”，“語(yǔ)句”，“表達(dá)式

9、”等等.語(yǔ)法分析程序判斷源程序在結(jié)構(gòu)上是否正確.源程序的結(jié)構(gòu)由上下文無(wú)關(guān)文法描述.語(yǔ)法分析程序可以用YACC等工具自動(dòng)生成。 4>.后綴式：即逆波蘭式。逆波蘭式是波蘭邏輯學(xué)家盧卡西維奇（Lukasiewicz)發(fā)明的一種表示表達(dá)式的方法。這種表示方式把運(yùn)算符寫(xiě)在運(yùn)算對(duì)象的后面，例如，把a(bǔ)+b寫(xiě)成ab+，所以也稱為后綴式。這種表示法的優(yōu)點(diǎn)是根據(jù)運(yùn)算對(duì)象和算符的出現(xiàn)次序進(jìn)行計(jì)算，不需要使用括號(hào)，也便于用械實(shí)現(xiàn)求值。對(duì)于表達(dá)式x:=(a+b)*(c+d)，其后綴式為xab+cd+*:=。 原表達(dá)式：a*(b*(c+d/e)-f)# /* # 為

10、表達(dá)式結(jié)束符號(hào)*/后綴式：abcde/+*f-*#  5>.四元式：四元式是一種更接近目標(biāo)代碼的中間代碼形式。由于這種形式的中間代碼便于優(yōu)化處理，因此，在目前許多編譯程序中得到了廣泛的應(yīng)用。四元式實(shí)際上是一種“三地址語(yǔ)句”的等價(jià)表示。它的一般形式為：(op,arg1,arg2,result)其中， op為一個(gè)二元 (也可是一元或零元)運(yùn)算符；arg1,arg2分別為它的兩個(gè)運(yùn)算 (或操作)對(duì)象，它們可以是變量、常數(shù)或系統(tǒng)定義的臨時(shí)變量名；運(yùn)算的結(jié)果將放入result中。四元式還可寫(xiě)為類似于PASCAL語(yǔ)言賦值語(yǔ)句的形式：result

11、60;= arg1 op arg2 每個(gè)四元式只能有一個(gè)運(yùn)算符，所以，一個(gè)復(fù)雜的表達(dá)式須由多個(gè)四元式構(gòu)成的序列來(lái)表示。例如，表達(dá)式A+B*C可寫(xiě)為序列T1=B*C,T2=A+T1其中，T1，T2是編譯系統(tǒng)所產(chǎn)生的臨時(shí)變量名。當(dāng)op為一元、零元運(yùn)算符 (如無(wú)條件轉(zhuǎn)移)時(shí)，arg2甚至arg1應(yīng)缺省，即result=op arg1或 op result ；對(duì)應(yīng)的一般形式為：(op,arg1,arg2,result).（3） 算法描述 1>.詞法分析器1. Design the regular gramm

12、ar.2. Design the regular expression.3. Construct the DFA.4. Write the program.數(shù)據(jù)結(jié)構(gòu)typedef structint type;char tokensize;symbol;Char*keywordskeywordsnum = "auto","break","case","char","const","continue","default","do",&qu

13、ot;double","else","enum","extern","float","for","goto","if","int","long","register","return","short","signed","sizeof","static","struct"

14、;,"switch","typedef", "printf","union","unsigned","void","volatile","while","main","include","using","namespace","std","bool","cin","cout",&

15、quot;iostream","endl"char *operatorsoperatorsnum = "+","-","*","/","+","-","%"char *jiefujiefunum = ",","",".","(",")","","","","&

16、quot;,"|"char *luojiluojinum = "<",">","=","<=",">=","=","!=","&&","|","!"char *teshuteshunum = "","#","$","&","",&q

17、uot;","<<",">>"char *zhushizhushinum = "/","/*","*/"char *str8 = "關(guān)鍵字","操作符","界符","邏輯運(yùn)算符","特殊符","注釋符","常量","標(biāo)識(shí)符"*通過(guò)讀文件的形式一個(gè)字符一個(gè)字符讀入進(jìn)行分析*下面是詞法分析的主要函數(shù)void

18、lex(char *filename)int error = 0;int flag = 0;char ch;fp.open(filename);int linenum = 1;int i,j;i = 0;int x = 0;ch = fp.get();while(!fp.eof()if(ch = ' ' | ch = 't')x = 0;ch = fp.get();else if(ch = 'n')x = 0;linenum+;ch = fp.get();else if(isalpha(ch) = 1)tablei.tokenx = ch;ch

19、= fp.get();if(isalpha(ch) = 0 && isdigit(ch) = 0 && ch != '_')tablei.token+x = '0'i+;flag = 0;x = 0;else if(isdigit(ch) = 1 | isalpha(ch) = 1 | ch = '_')x+;else if(isdigit(ch) = 1)tablei.tokenx = ch;ch = fp.get();if(isdigit(ch) = 1)x+;else if(ch = '.'

20、&& flag = 0)tablei.token+x = ch;flag = 1;x+;ch = fp.get();else if(ch = '.' && flag = 1)cout<<"("<<linenum<<")"<<"error"<<endl;f<<"("<<linenum<<")"<<"error"<<

21、;endl;error+;flag = 0;if(isdigit(ch) = 0)tablei.token+x = '0'i+;x = 0;flag = 0;else if(ch = '_')tablei.tokenx = ch;ch = fp.get();if(isalpha(ch) = 1 | isdigit(ch) = 1 | ch = '_')x+;elsetablei.token+x = '0'i+;elsechar ch2 = fp.get();if(ist(ch,ch2) = 1)tablei.token0 = ch

22、;tablei.token1 = ch2;tablei.token2 = '0'x = 0;i+;ch = fp.get();elsetablei.token0 = ch;tablei.token1 = '0'x = 0;i+;ch = ch2;for(j = 0; j < i; j+)int n = typenum(tablej.token);tablej.type = n;cout<<error<<" error(s)"<<endl;f<<error<<" err

23、or(s)"<<endl;f<<"-"<<endl;cout<<"-"<<endl;for(j = 0; j < i; j+)cout<<tablej.token<<"tt"f<<tablej.token<<"tt"sf(tablej.type);2>.語(yǔ)法分析器1).自頂向下的LL（1）分析2).先求first、follow、select集構(gòu)造分析表3).進(jìn)行語(yǔ)法分析4).本實(shí)驗(yàn)采用靜

24、態(tài)存分析表的方式5).可以分析算符表達(dá)式*分析棧*和剩余串*進(jìn)棧和匹配操作3>.語(yǔ)言表達(dá)式翻譯程序*完成中間代碼的生成，*轉(zhuǎn)成四元式的形式。*利用兩個(gè)棧進(jìn)行四元式的產(chǎn)生*其一棧為算符棧根據(jù)優(yōu)先關(guān)系進(jìn)棧和出棧*另一個(gè)為操作數(shù)或變量棧*當(dāng)剩余串算符優(yōu)先級(jí)比算符棧低時(shí)出棧生成相應(yīng)的四元式*再根據(jù)四元式轉(zhuǎn)化成匯編代碼四元式結(jié)構(gòu)體struct TRchar w;char opr15;char opr25;char T5; 匯編結(jié)構(gòu)體struct ASchar L5;char operation5;char A5;char B5;v-> void maint-> intd-> 標(biāo)識(shí)

25、符e-> 常量w-> whilei-> if（4） 程序流程圖（5） 測(cè)試用例與實(shí)驗(yàn)結(jié)果 #include<iostream>void main()int a;int b;a=6;b=3;while(a>b)a=a+0;if(a>b)b=b+1;#詞法分析*輸出文件部分：*編譯器輸出部分：語(yǔ)法分析：*輸入文法PQUVWKECTSFv()td,;=diwk+-*/><cP v()QKQ UV;U tV dWW ,dWW =EW kK d=E;KK i(E)KK w(E)KK QKK kE TCC +TCC -TCC cC kC >TCC

26、 <TCT FSS *FSS /FSS cS kF (E)F c F dF =E#動(dòng)態(tài)生成的分析表此文法select有交集，當(dāng)C遇到>時(shí)可以退出 k空和">TC"此文法select有交集，當(dāng)C遇到<時(shí)可以退出 k空和"<TC"通過(guò)手動(dòng)的修改可以進(jìn)行語(yǔ)法分析四元式的生成5、 讀書(shū)工程心得總結(jié) 深入了解4遍式編譯程序的運(yùn)行原理，通過(guò)設(shè)計(jì)一個(gè)小型的編譯器，加深對(duì)課堂學(xué)習(xí)內(nèi)容的理解，更深刻的領(lǐng)會(huì)編譯器的基本工作原理和實(shí)現(xiàn)方法。實(shí)驗(yàn)中模擬了詞法分析，語(yǔ)法分析，語(yǔ)義分析，中間代碼以及目標(biāo)代碼生成。從中真正學(xué)習(xí)到了編譯的精髓，雖然其中有熬

27、夜編代碼的疲憊，但是真正做成的時(shí)候就會(huì)發(fā)現(xiàn)，做成成品的喜悅遠(yuǎn)比辛勞要重要得多，有志者事竟成。6、 參考文獻(xiàn)1.書(shū)目名稱：編譯原理(第2版) 作 者：張素琴 呂映芝出 版 社：清華大學(xué)出版社 出版時(shí)間：2005年02月內(nèi)容提要：本書(shū)介紹編譯系統(tǒng)的一般構(gòu)造原理、基本實(shí)現(xiàn)技術(shù)和一些自動(dòng)構(gòu)造工具。主要由語(yǔ)言基礎(chǔ)知識(shí)、詞法分析、語(yǔ)法分析、中間代碼生成、代碼優(yōu)化、目標(biāo)代碼生成、符號(hào)表的構(gòu)造和運(yùn)行時(shí)存儲(chǔ)空間的組織等部分組成。書(shū)中在介紹編譯程序構(gòu)造基本原理的同時(shí)引入“PL/0語(yǔ)言的編譯程序”結(jié)構(gòu)及文本,還引入了LEX、YACC使用方法與實(shí)例。 本書(shū)是高等院校計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)的本科生教材,也可作為教師、研究

28、生軟件工程技術(shù)人員的參考書(shū)。2.書(shū)目名稱：編譯原理（第2版）原書(shū)名： Compilers:Principles,Techniques,and Tools 原出版社： Pearson Education 美Alfred V.Aho,Ravi Sethi,Jeffrey D.Ullman   譯者： 李建中 姜守旭 出版社：機(jī)械工業(yè)出版社 出版日期：2003 年9月內(nèi)容提要：本書(shū)深入討論了編譯器設(shè)計(jì)的重要主題，包括詞法分析、語(yǔ)法分析、語(yǔ)法制導(dǎo)分析、類型檢查、運(yùn)行環(huán)境、中間代碼生成、代碼生成、代碼優(yōu)化等，并在最后兩章中討論了實(shí)現(xiàn)編譯器的一些編程問(wèn)題和幾個(gè)編譯器實(shí)例，每章都提供了大

29、量的練習(xí)和參考文獻(xiàn)。本書(shū)從介紹編譯的原理性概念開(kāi)始，然后通過(guò)構(gòu)建一個(gè)簡(jiǎn)單的一遍編譯器來(lái)逐一解釋這些概念。 本書(shū)是編譯原理課程的經(jīng)典教材，作者曾多次使用本書(shū)的內(nèi)容在貝爾實(shí)驗(yàn)室、哥倫比亞大學(xué)、普林斯頓大學(xué)和斯坦福大學(xué)向本科生和研究生講授初等及高等編譯課程。 本書(shū)作者alfred vaho、ravi sethi和jeffrey dullman是世界著名的計(jì)算機(jī) 科學(xué)家，他們?cè)谟?jì)算機(jī)科學(xué)理論、數(shù)據(jù)庫(kù)等很多領(lǐng)域都做出了杰出貢獻(xiàn)。本書(shū) 是編譯領(lǐng)域無(wú)可替代的經(jīng)典著作，被廣大計(jì)算機(jī)專業(yè)人士譽(yù)為“龍書(shū)”。本書(shū)一 直被世界各地的著名高等院校和科研機(jī)構(gòu)(如貝爾實(shí)驗(yàn)室、哥倫比亞大學(xué)、普 林斯頓大學(xué)和斯坦福大學(xué)等)廣泛用作本科生和研究生編譯原理與技術(shù)課程的 教材，本書(shū)對(duì)我國(guó)計(jì)算機(jī)教育界也具有重大影響。 書(shū)中深入討論了編譯器設(shè)計(jì)的重要主題，包括詞法分析、語(yǔ)法分析、語(yǔ)法制