FOR循環(huán)語句的翻譯程序設(shè)計(遞歸下降法、輸出四元式表示)

1、武漢理工大學(xué)編譯原理課程設(shè)計說明書學(xué) 號： 0121010340804課 程 設(shè) 計課程名稱編譯原理課程設(shè)計題 目FOR循環(huán)語句的翻譯程序設(shè)計（遞歸下降法、輸出四元式表示）學(xué) 院計算機科學(xué)與技術(shù)專 業(yè)計算機科學(xué)與技術(shù)班 級計算機1001姓 名吳垂森指導(dǎo)教師陳天煌2012年1月13日目錄課程設(shè)計任務(wù)書- 3 1、系統(tǒng)描述 4 1.1、實驗思想 4 1.2、設(shè)計內(nèi)容 4 1.3、翻譯過程 4 2、遞歸下降法 6 2.1、遞歸下降法的主要思想：6 2.2、用程序表示遞歸子程序的內(nèi)部結(jié)構(gòu)：7 3、四元式的表示：7 4、語法制導(dǎo)翻譯8 4.1、翻譯任務(wù)的處理過程8 4.2、語法制導(dǎo)翻譯：8 43、基于屬

2、性文法的處理方法-8 5、中間代碼形式的描述及中間代碼序列的結(jié)構(gòu)設(shè)計8 6、簡要的分析與概要設(shè)計9 6.1、詞法分析：9 6.2、語法遞歸分析10 6.3、制導(dǎo)翻譯-12 6.4、主函數(shù)-13 7、測試方法和測試結(jié)果-14 7.1測試過程-14 7.2測試結(jié)論-16 8、課程設(shè)計總結(jié)-17 9、參考文獻(xiàn)-18 本科生課程設(shè)計成績評定表19課程設(shè)計任務(wù)書學(xué)生姓名： 吳垂森 專業(yè)班級： 計算機1001班 指導(dǎo)教師： 陳天煌 工作單位：計算機科學(xué)與技術(shù)學(xué)院 題目: FOR循環(huán)語句的翻譯程序設(shè)計（遞歸下降法、輸出四元式表示）初始條件：理論：學(xué)完編譯課程，掌握一種計算機高級語言的使用。實踐：計算機實驗室

3、提供計算機及軟件環(huán)境。如果自己有計算機可以在其上進行設(shè)計。要求完成的主要任務(wù): （包括課程設(shè)計工作量及其技術(shù)要求，以及說明書撰寫等具體要求）（1） 寫出符合給定的語法分析方法的文法及屬性文法。（2） 完成題目要求的中間代碼四元式表示的描述。（3） 寫出給定的語法分析方法的思想，完成語法分析和語義分析程序設(shè)計。（4） 編制好分析程序后，設(shè)計若干用例，上機測試并通過所設(shè)計的分析程序。（5） 設(shè)計報告格式按附件要求書寫。課程設(shè)計報告書正文的內(nèi)容應(yīng)包括：1 系統(tǒng)描述（問題域描述）；2 文法及屬性文法的描述；3 語法分析方法描述及語法分析表設(shè)計；4 按給定的題目給出中間代碼形式的描述及中間代碼序列的結(jié)構(gòu)

4、設(shè)計；5 編譯系統(tǒng)的概要設(shè)計；6 詳細(xì)的算法描述（流程圖或偽代碼）；7 軟件的測試方法和測試結(jié)果；8 研制報告（研制過程，本設(shè)計的評價、特點、不足、收獲與體會等）；9 參考文獻(xiàn)（按公開發(fā)表的規(guī)范書寫）。時間安排：設(shè)計安排一周：周1、周2：完成系統(tǒng)分析及設(shè)計。周3、周4：完成程序調(diào)試及測試。周5：撰寫課程設(shè)計報告。設(shè)計驗收安排：設(shè)計周的星期五第1節(jié)課開始到實驗室進行上機驗收。設(shè)計報告書收取時間：設(shè)計周的次周星期一上午10點。指導(dǎo)教師簽名： 年 月 日系主任（或責(zé)任教師）簽名： 年 月 日FOR循環(huán)語句的翻譯程序設(shè)計 遞歸下降法、輸出四元式表示1、系統(tǒng)描述1.1、實驗思想通過設(shè)計、編制、調(diào)試一個F

5、OR循環(huán)語句的語法及語義分析程序，加深對語法及語義分析原理的理解，實現(xiàn)詞法分析程序?qū)卧~序列的詞法檢查和分析，并且實現(xiàn)對單詞序列的語法分析、語義分析以及中間代碼生成。1.2、設(shè)計內(nèi)容本設(shè)計按照要求設(shè)計出for語句的簡單文法，并使用遞歸下降分析法對用戶輸入的程序進行分析和翻譯。對下列正確的程序輸入： for i=1 step 1 until 10 do k=j #結(jié)果程序要對該輸入進行詞法分析，然后利用遞歸下降的分析法對詞法分析得到的單詞序列進行語法分析，經(jīng)過語法制導(dǎo)翻譯顯示出等價的三地址表示的中間代碼。對于錯誤的程序輸入，如：For i=1 step 1 until 10 k=j#結(jié)果程序要指

6、出程序出錯。1.3、翻譯過程1.3.1、 詞法分析：詞法分析是計算機科學(xué)中將字符序列轉(zhuǎn)換為單詞（Token）序列的過程。進行語法分析的程序或者函數(shù)叫作詞法分析器（Lexical analyzer，簡稱Lexer），也叫掃描器（Scanner）。詞法分析器一般以函數(shù)的形式存在，供語法分析器調(diào)用。詞法分析是編譯過程中的第一個階段，在語法分析前進行 。也可以和語法分析結(jié)合在一起作為一遍，由語法分析程序調(diào)用詞法分析程序來獲得當(dāng)前單詞供語法分析使用。簡化設(shè)計、改進編譯效率、增加編譯系統(tǒng)的可移植性。詞法分析是編制一個讀單詞的過程，從輸入的源程序中，識別出各個具有獨立意義的單詞，即基本保留字、標(biāo)識符、常數(shù)、

7、運算符、分隔符五大類。并依次輸出各個單詞的內(nèi)部編碼及單詞符號自身值。單詞的分類主要分為五類：1. 關(guān)鍵字：由程序語言定義的具有固定意義的標(biāo)識 符。也稱為保留字或基本字。2. 標(biāo)識符：用來表示程序中各種名字的字符串。3. 常 數(shù)：常數(shù)的類型一般有整型、實型、布爾型、文字型。4. 運算符：如+、 、*、/ 等。5. 界限符：如逗號、分號、括號等。詞法分析器輸出的單詞符號常表示成如下的二元式：（單詞種別，單詞符號的屬性值）1.3.2、語法分析：語法分析是編譯過程的一個邏輯階段。語法分析的任務(wù)是在的基礎(chǔ)上將單詞序列組合成各類語法短語，如“程序”，“語句”，“表達(dá)式”等等.語法分析程序判斷源程序在結(jié)構(gòu)上

8、是否正確.源程序的結(jié)構(gòu)由上下文無關(guān)文法描述.語法分析程序可以用YACC等工具自動生成。語法分析是編譯程序的核心部分,其主要任務(wù)是確定語法結(jié)構(gòu),檢查語法錯誤，報告錯誤的性質(zhì)和位置，并進行適當(dāng)?shù)募m錯工作。語法分析的主要工作：是識別由詞法分析給出的單詞序列是否是給定的正確句子（程序）。語法分析常用的方法：自頂向下的語法分析和自底向上的語法分析兩大類。此次設(shè)計中語法分析中主要通過遞歸下降分析法對語法分析處理過程進行控制，使輸出的三地址表示的翻譯的工作有條不紊的進行，同時識別語法分析中的語法錯誤。遞歸下降法主要采用自頂向下方法，即從文法的開始符號開始進行分析，逐漸推導(dǎo)的往下構(gòu)造語法樹，使其樹葉正好構(gòu)造出

9、所給定的源程序串。自頂向下方法的關(guān)鍵是確定在推導(dǎo)過程中選擇候選式的問題。當(dāng)進行推導(dǎo)時，一個非終結(jié)符可能對應(yīng)多個產(chǎn)生式，這樣我們就無法事先知道應(yīng)該用哪個產(chǎn)生式，因此實用都作了一些限制。以便在任何情況下都能確定應(yīng)該用的產(chǎn)生式。自頂向下的主要思想是從開始符出發(fā)導(dǎo)出句型并一個符號一個符號地與給定終結(jié)符串進行匹配。如果全部匹配成功，則表示開始符號可推導(dǎo)出給定的終結(jié)符串。因此判定給定終結(jié)符號串是正確句子。詞法分析程序和語法分析程序的關(guān)系：1.3.3、中間代碼生成：中間代碼，也稱中間語言，是復(fù)雜性介于源程序語言和機器語言的一種表示形式。為了使編譯程序有較高的目標(biāo)程序質(zhì)量，或要求從編譯程序邏輯結(jié)構(gòu)上把與機器無

10、關(guān)和與機器有關(guān)的工作明顯的分開來時，許多編譯程序都采用了某種復(fù)雜性介于源程序語言和機器語言之間的中間語言。中間代碼（語言）是一種特殊結(jié)構(gòu)的語言，編譯程序所使用的中間代碼有多種形式。按其結(jié)構(gòu)分常見的有逆波蘭式（后綴式）、三地址代碼（三元式、四元式）和樹形表示（抽象語法樹）、DAG表示。本次課程設(shè)計要實現(xiàn)的是三地址表示。1.3.4、屬性文法：對于文法的每個產(chǎn)生式都配備了一組屬性的計算規(guī)則，稱為語義規(guī)則。所謂語法制導(dǎo)的翻譯指的是在語法分析過程中，完成這些語義規(guī)則描述的動作，從而實現(xiàn)語義處理。 一個屬性文法包含一個上下文無關(guān)文法和一系列語義規(guī)則，這些語義規(guī)則附在文法的每個產(chǎn)生式上。形式上講，屬性文法是

11、一個三元組 :A=(G，V，F(xiàn))， 其中：G:是一個上下文無關(guān)文法；V:有窮的屬性集,每個屬性與文法的一個終結(jié)符或非終結(jié)符相連,這些屬性代表與文法符號相關(guān)信息；F:關(guān)于屬性的屬性斷言或一組屬性的計算規(guī)則(稱為語義規(guī)則) 。 斷言或語義規(guī)則與一個產(chǎn)生式相聯(lián),只引用該產(chǎn)生式左端或右端的終結(jié)符或非終結(jié)符相聯(lián)的屬性。 2、遞歸下降法遞歸下降法又稱遞歸子程序法。在程序語言的語法定義中有許多采用遞歸定義。我們在對它進行語法分析時，編制的處理程序也采取遞歸的方式，可使其結(jié)構(gòu)簡單易讀。但由于頻繁地調(diào)用子程序大大地降低了分析速度。2.1、遞歸下降法的主要思想：對每個非終結(jié)符按其產(chǎn)生式結(jié)構(gòu)寫出相應(yīng)語法分析子程序。

12、因為文法遞歸相應(yīng)子程序也遞歸，子程序的結(jié)構(gòu)與產(chǎn)生式結(jié)構(gòu)幾乎一致。所以稱此種方法稱為遞歸子程序法或遞歸下降法。2.2、用程序表示遞歸子程序的內(nèi)部結(jié)構(gòu)： 設(shè)A是一個非終結(jié)符： A1 A2 An 則寫(A) Û if charfirst(1 ) then(1 ) else if charfirst(2 ) then (2 ) else if charfirst(n ) then (n) else ERROR其中(i)表示調(diào)用處理符號串i的子程序。對A的任一右部i 設(shè)為： i = y1 y2 yn 則定義( i) Û begin(y1);(y2);(yn) end其中yj可分為下列

13、兩種情況（j=1,n):1) yjVT,則 ( yj) Û if char yj then ERROR else READ(char)2) yjVN,則(yj)表示調(diào)用關(guān)于yj的遞歸子程序。23、遞歸下降法對文法的限制：1、任一非終結(jié)符B都不是左遞歸的，否則會產(chǎn)生死循環(huán)。2、對A的任意兩個右部i , j ,有：first(i)first(j)= 。First(i)表示i所能導(dǎo)出串的第一個符號的集合。顯然，每個i的first(i)是互不相同的，否則則無法判斷應(yīng)執(zhí)行哪個(i )。 3、四元式的表示：一般形式：(op,a,b,t1)如表達(dá)式x + y * z 翻譯成的三地址代碼序列是： (

14、1)(*,y,z,t1) (2)(+,x,t1,t2) 常用的三地址表示:賦值語句 (=,x,-.t1)無條件轉(zhuǎn)移 goto L條件轉(zhuǎn)移 if x relop y goto L過程調(diào)用 param x 和call p , n過程返回 return y索引賦值 (=,yi,-,x)和 (=.y,-,xi) 地址和指針賦值 (=,$y,-,x)，(=,*y,-,x)和(=,y,-,*z)四元式結(jié)構(gòu)形式: 編號 (OP，ARG1，ARG2，RESULT)4、語法制導(dǎo)翻譯4.1、翻譯任務(wù)的處理過程編譯程序的整個任務(wù)就是把源程序翻譯為目標(biāo)程序。實際上可以把每個編譯階段都看作是完成一定翻譯任務(wù)的處理過程：

15、詞法分析階段把字符流翻譯為單詞流，語法分析階段把單詞流翻譯為語法樹，目標(biāo)代碼生成階段把語法樹翻譯為匯編語言等等。 4.2、語法制導(dǎo)翻譯：在語法分析過程中，隨著分析的步步進展，每當(dāng)進行推導(dǎo)或歸約時，同步的去執(zhí)行每個產(chǎn)生式所附帶的語義規(guī)則描述的語義動作（或語義子程序），這樣進行翻譯的辦法稱作語法制導(dǎo)翻譯。 所謂屬性依賴圖是一個有向圖，用于描述分析樹中的屬性和屬性間的相互依賴關(guān)系。43、基于屬性文法的處理方法輸入串語法樹 依賴圖 計算語義規(guī)則順序語法分析樹遍歷執(zhí)行語義規(guī)則語義規(guī)則的計算可能產(chǎn)生代碼，在符號表中存取信息，給出出錯信息或執(zhí)行其它動作。對輸入串的翻譯也就是根據(jù)語義規(guī)則進行計算的結(jié)果。5、中

16、間代碼形式的描述及中間代碼序列的結(jié)構(gòu)設(shè)計本次設(shè)計，使用的中間代碼為四元式四元式有四個組成成分：算符op，第一和第二運算對象ARG1和ARG2，運算結(jié)果RESULT。例如：有中綴式a:b*cb*c，求其等價的四元式。 四元元式 編號 算符 左對象 右對象 中間結(jié)果 op arg1 arg2 result(1) minus c t1(2) b t1 t2(3) minus c t3(4) b (3) t4(5) (4) (2) t5(6) assign a 設(shè)計并生成的結(jié)果程序，最終需要將用戶輸入的程序經(jīng)過詞法分析和語法分析，生成如上所述的式表示的中間代碼形式。6、簡要的分析與概要設(shè)計程序由詞法分

17、析和語法分析兩部分構(gòu)成： - 20 - 6.1、詞法分析：int buffer()/載入 int i=0; cout<<"輸入程序，以#作為結(jié)束標(biāo)志。"<<endl; for(int n=0;n<=MAX;n+) for(;i<=MAX;i+) scanf("%c",&stri); if(stri='#') break; /如果尾數(shù)為識別碼#,則表示程序讀完,跳出循環(huán). break; return(i); bool IsLetter(char ch)/判斷是否是字母 if(ch>=65&a

18、mp;&ch<=90|ch>=97&&ch<=122) return(true); else return(false); bool IsDigit(char ch)/判斷是否是數(shù)字 if(ch>=48&&ch<=57) return(true); else return(false); char GetChar(int i)/讀取字符 char ch; ch=stri; return(ch); char GetBC(char ch)/判斷是不是空格或者換行，如果是，直接讀取下一個字符直道不再空白為止 if(ch=32|ch

19、=10) turn+; ch=GetChar(turn); ch=GetBC(ch);/遞歸實現(xiàn) return(ch); else return(ch); void Concat()/連接，即為strtoken賦值 strTokenn=ch; n+; int Reserve()/以單詞為單位查找保留字，是則返回編碼，不是則返回0，用來區(qū)分標(biāo)志符和保留字 if(strcmp(strToken," DIM0")=0)/調(diào)用strcmp函數(shù)實現(xiàn), return(1); else if(strcmp(strToken,"for0")=0) return(2);

20、else if(strcmp(strToken,"step0")=0) return(3); else if(strcmp(strToken,"until0")=0) return(4); else if(strcmp(strToken,"do0")=0) return(5); else return(6); void clear() n=0; 6.2、語法遞歸分析int A(int * c,int & q) if(cq+=3) if(cq=7) q+; return 1; else cout<<"ste

21、p右部出錯"<<endl;return 0; else cout<<"error 'step'"<<endl;return 0; int B(int * b,int & o) if(bo+=4) if(bo=7) o+; return 1; else cout<<"until右部出錯"<<endl;return 0; else cout<<"error 'until'"<<endl;return 0;

22、int S2(int * d,int & h) if(dh+=6) if(dh+=8) if(dh=6|dh=7) h+; return 1; else cout<<"賦值語句右部出錯 "<<endl;return 0; else cout<<"賦值語句缺少賦值運算符 "<<endl;return 0; else cout<<"賦值語句左部出錯 "<<endl;return 0; int S1(int * m,int & n) if(S2(m,n)

23、 if(A(m,n) if(B(m,n) return 1; else return 0; else return 0; else return 0; int S(int *a,int & z) if (az+=2) if (S1(a,z) if(az+=5) if(S2(a,z) cout<<"succeed!"<<endl;return 1; else return 0; else cout<<"error 'do'"<<endl; return 0; else return 0

24、; else cout<<"error 'for'"<<endl; return 0; 6.3、制導(dǎo)翻譯if(!S(ana,j) cout<<"語法出錯!"<<endl; else cout<<"三地址碼如下："<<endl; cout<<"100 " int i=0; while(record1->wordi!='0') cout<<record1->wordi+;cout&

25、lt;<record2->word0; i=0; while(record3->wordi!='0') cout<<record3->wordi+;cout<<endl; cout<<"101 goto 103"<<endl; cout<<"102 " i=0; while(record1->wordi!='0') cout<<record1->wordi+;cout<<":=" i=

26、0; while(record1->wordi!='0') cout<<record1->wordi+;cout<<"+" i=0; while(record5->wordi!='0') cout<<record5->wordi+;cout<<endl; cout<<"103 if " i=0; while(record1->wordi!='0') cout<<record1->wordi+;cout

27、<<"<" i=0; while(record7->wordi!='0') cout<<record7->wordi+; cout<<" goto 105"<<endl; cout<<"104 goto 107"<<endl; cout<<"105 " i=0; while(record9->wordi!='0') cout<<record9->wordi+;

28、cout<<":=" i=0; while(record11->wordi!='0') cout<<record11->wordi+;cout<<endl; cout<<"106 goto 102"<<endl; cout<<"107 end"<<endl; 6.4、主函數(shù)void main() cout<<"*產(chǎn)生式*"<<endl;/ for step until do i j

29、 = cout<<" S ->for S1 do S2"<<endl; / 編號 2 3 4 5 6 7 8 cout<<" S1 ->S2AB"<<endl; cout<<" S2 ->i=j"<<endl; cout<<" A ->stepj"<<endl; cout<<" B ->untilj"<<endl; int num; turn=0;

30、 num=buffer()-1; int x=0;/計識別的單詞的個數(shù) for(;turn<=num;turn+)/總循環(huán),ch存放剛讀入的字符，strtoken存放已識別的標(biāo)志付或保留字，turn是數(shù)組str的下標(biāo) ch=GetChar(turn); ch=GetBC(ch); if(IsLetter(ch) while(IsLetter(ch)&&turn<=num|IsDigit(ch)&&turn<=num) Concat(); ch=GetChar(+turn); strTokenn='0' ch=NULL;/此ch不

31、是標(biāo)志符中的符號 turn=turn-1; kind=Reserve(); recordx=new Word; recordx->sort=kind;/12345或6 cout<<"(" for(int i=0;i<n;i+) recordx->wordi=strTokeni; cout<<recordx->wordi;/輸出識別的標(biāo)志符或保留字 cout<<","<<kind<<")"<<endl; recordx->wordi=&

32、#39;0' clear(); x+; else if(IsDigit(ch) while(IsDigit(ch)&&turn<=num) Concat(); ch=GetChar(+turn); ch=NULL; turn=turn-1; kind=7; cout<<"(" for(int i=0;i<n;i+) recordx->wordi=strTokeni; cout<<recordx->wordi; cout<<","<<kind<<&q

33、uot;)"<<endl; recordx->wordi='0' clear();x+; else if(ch='=') kind=8; recordx->word0='=' recordx+->sort=kind; cout<<"(=,"<<kind<<")"<<endl; else cout<<"error input!"<<endl; 7、測試方法和測試結(jié)果7.1測試過程

34、針對所設(shè)計的關(guān)于 for循環(huán)語句的翻譯程序，分別用正確的程序和有錯誤的程序進行測試，測試出結(jié)果程序的可用性和健壯性。測試中分別使用了一個合法程序和兩個非法程序，對結(jié)果程序進行測試，具體的測試程序、測試過程和測試結(jié)果如下：for循環(huán)語句語法分析過程：輸入程序: for(d=3;d<f;d+) for(c=b;c<3;c+) c=b/a+2*3; a=c*d+b+6/2; 合法程序。得到運行結(jié)果如圖所示：輸入合法程序：for(i=3;i<f;i+)a=a+i得到運行結(jié)果如圖所示： 7.2測試結(jié)論經(jīng)過測試，可以得知，結(jié)果程序能達(dá)到預(yù)計的要求：對合法程序進行詞法分析和簡單優(yōu)

35、先的語法分析，并生四元式表示的中間代碼；對于錯誤的程序輸入，結(jié)果程序能夠判斷其出錯。本次設(shè)計的文法是：S->for(A)GA->D id PD->E id O FE->id=FF->idP->+|-O-> <|>G->GBB->ID=S1s1->TE1T->FT1E1->+TE1|&|-TE1T1->*FT1|&|-TE1X->B|&*/當(dāng)輸入的程序缺少do時，將會提示error do，表明輸入出錯。又因為該文法實現(xiàn)的設(shè)計是i=j這一賦值語句，當(dāng)缺少了賦值符號“=”時，系統(tǒng)將會提醒賦值語句缺少賦值運算符這一錯誤現(xiàn)象。存在問題：對于含有非法輸入符號的程序，結(jié)果程序沒有很好地處理，程序健壯性不強。例如當(dāng)我輸入的程序為：For i=1 step -1 until 10 do k=j#，該程序處理時把-1的負(fù)號給省略掉了，把這一語句和語句For i