for循環(huán)語句的翻譯輸出四元式精要

1、武漢理工大學編譯原理課內實踐說明書學 號： Xxxx實踐課報告課程名稱編譯原理題 目FOR循環(huán)語句的翻譯程序設計（遞歸下降法、輸出四元式）學 院計算機科學與技術專 業(yè)計算機科學與技術班 級xxxx姓 名xxxx指導教師xxxx2017年01月01日目錄1系統(tǒng)描述31.1實驗思想31.2設計內容31.3翻譯過程31.3.1詞法分析31.3.2語法分析41.3.3中間代碼生成51.3.4屬性文法52遞歸下降法62.1遞歸下降法的主要思想62.2用程序表示遞歸子程序的內部結構62.3遞歸下降法對文法的限制73四元式的表示74語法制導翻譯74.1翻譯任務的處理過程74.2語法制導翻譯85中間代碼形式的

2、描述及中間代碼序列的結構設計86簡要的分析與概要設計96.1整體流程圖96.2詞法分析流程圖106.3語法制導翻譯流程圖117測試方法和測試結果117.1測試過程117.2測試結論158課程設計總結16參考文獻18課內實踐任務書學生姓名： xxx 專業(yè)班級： xxxx 指導教師：xxxx 工作單位： 計算機科學與技術學院 題目: FOR循環(huán)語句的翻譯程序設計（遞歸下降法、輸出四元式）初始條件：理論：掌握編譯理論、技術、方法、掌握一種計算機高級語言的使用。實踐：計算機實驗室提供計算機及軟件環(huán)境。如果自己有計算機可以在其上進行設計。要求完成的主要任務: （包括實踐工作量及其技術要求，以及報告撰寫等

3、具體要求）（1） 寫出符合給定的語法分析方法的文法及屬性文法。（2） 完成題目要求的中間代碼四元式的描述。（3） 寫出給定的語法分析方法的思想，完成語法分析和語義分析程序設計。（4） 編制好分析程序后，設計若干用例，上機測試并通過所設計的分析程序。（5） 設計報告格式按附件要求書寫。課內實踐報告書正文的內容應包括：1 系統(tǒng)描述（問題域描述）；2 文法及屬性文法的描述；3 語法分析方法描述及語法分析表設計；4 按給定的題目給出中間代碼形式的描述及中間代碼序列的結構設計；5 編譯系統(tǒng)的概要設計；6 詳細的算法描述（流程圖或偽代碼）；7 軟件的測試方法和測試結果；8本設計的評價、特點、不足、收獲與體

4、會等。時間安排：4學時：詞法分析程序的設計與實現(xiàn)。4學時：復合語句的語法分析程序設計與實現(xiàn)。4學時：復合語句的翻譯程序設計與實現(xiàn)設計。驗收安排：實驗室進行上機答辯驗收，提交實踐報告。指導教師簽名： 2016年 10月 1日系主任（或責任教師）簽名： 2016年 10月 1日1系統(tǒng)描述1.1實驗思想通過設計、編制、調試一個FOR循環(huán)語句的語法及語義分析程序，加深對語法及語義分析原理的理解，實現(xiàn)詞法分析程序對單詞序列的詞法檢查和分析，并且實現(xiàn)對單詞序列的語法分析、語義分析以及中間代碼生成。1.2設計內容按給定的題目寫出符合自身分析方法要求的文法和屬性文法描述。，按給定的題目給出分析方法的思想及分析

5、表設計。給出選定的語法成分的中間代碼序列的結構設計。完成相應的詞法分析、語法分析和語義分析程序設計。本設計按照要求設計出for語句的簡單文法，編制好翻譯程序后，設計若干用例，上機測試并通過所設計的分析程序。并使用遞歸下降分析法對用戶輸入的程序進行分析和翻譯。結果程序要對該輸入進行詞法分析，然后利用遞歸下降的分析法對詞法分析得到的單詞序列進行語法分析，經過語法制導翻譯顯示出等價的四元式表示的中間代碼。對于錯誤的程序輸入，結果程序要指出程序出錯。1.3翻譯過程1.3.1詞法分析詞法分析是計算機科學中將字符序列轉換為單詞（Token）序列的過程。進行語法分析的程序或者函數(shù)叫作詞法分析器（Lexica

6、l analyzer，簡稱Lexer），也叫掃描器（Scanner）。詞法分析器一般以函數(shù)的形式存在，供語法分析器調用。詞法分析是編譯過程中的第一個階段，在語法分析前進行 。也可以和語法分析結合在一起作為一遍，由語法分析程序調用詞法分析程序來獲得當前單詞供語法分析使用。簡化設計、改進編譯效率、增加編譯系統(tǒng)的可移植性。詞法分析是編制一個讀單詞的過程，從輸入的源程序中，識別出各個具有獨立意義的單詞，即關鍵字、標識符、常量、運算符、界限符五大類。并依次輸出各個單詞的類別及單詞符號自身值。單詞的分類主要分為五類：1. 關鍵字：由程序語言定義的具有固定意義的標識符。也稱為保留字或基本字。2. 標識符：用

7、來表示程序中各種名字的字符串。3. 常 量：常量的類型一般有整型、實型、布爾型、文字型。4. 運算符：如+、 、*、/、+、=>、<=、- 等。5. 界限符：如逗號、分號、括號等。詞法分析器輸出的單詞符號常表示成如下的二元式：（單詞種別，單詞符號的屬性值）1.3.2語法分析語法分析是編譯過程的一個邏輯階段。語法分析的任務是在的基礎上將單詞序列組合成各類語法短語，如“程序”，“語句”，“表達式”等等.語法分析程序判斷源程序在結構上是否正確。源程序的結構由上下文無關文法描述。語法分析程序可以用YACC等工具自動生成。語法分析是編譯程序的核心部分,其主要任務是確定語法結構，檢查語法錯誤，

8、報告錯誤的性質和位置，并進行適當?shù)募m錯工作。語法分析的主要工作：是識別由詞法分析給出的單詞序列是否是給定的正確句子（程序）。語法分析常用的方法：自頂向下的語法分析和自底向上的語法分析兩大類。此次設計中語法分析中主要通過遞歸下降分析法對語法分析處理過程進行控制，使輸出的四元式表示的翻譯的工作有條不紊的進行，同時識別語法分析中的語法錯誤。遞歸下降法主要采用自頂向下方法，即從文法的開始符號開始進行分析，逐漸推導的往下構造語法樹，使其樹葉正好構造出所給定的源程序串。自頂向下方法的關鍵是確定在推導過程中選擇候選式的問題。當進行推導時，一個非終結符可能對應多個產生式，這樣我們就無法事先知道應該用哪個產生式

9、，因此實用都作了一些限制。以便在任何情況下都能確定應該用的產生式。自頂向下的主要思想是從開始符出發(fā)導出句型并一個符號一個符號地與給定終結符串進行匹配。如果全部匹配成功，則表示開始符號可推導出給定的終結符串。因此判定給定終結符號串是正確句子。詞法分析程序和語法分析程序的關系：1.3.3中間代碼生成中間代碼，也稱中間語言，是復雜性介于源程序語言和機器語言的一種表示形式。為了使編譯程序有較高的目標程序質量，或要求從編譯程序邏輯結構上把與機器無關和與機器有關的工作明顯的分開來時，許多編譯程序都采用了某種復雜性介于源程序語言和機器語言之間的中間語言。中間代碼（語言）是一種特殊結構的語言，編譯程序所使用的

10、中間代碼有多種形式。按其結構分常見的有逆波蘭式（后綴式）、三地址代碼（三元式、四元式）和樹形表示（抽象語法樹）、DAG表示。本次課程設計要實現(xiàn)的是輸出四元式表示。1.3.4屬性文法對于文法的每個產生式都配備了一組屬性的計算規(guī)則，稱為語義規(guī)則。所謂語法制導的翻譯指的是在語法分析過程中，完成這些語義規(guī)則描述的動作，從而實現(xiàn)語義處理。 一個屬性文法包含一個上下文無關文法和一系列語義規(guī)則，這些語義規(guī)則附在文法的每個產生式上。形式上講，屬性文法是一個三元組 :A=(G，V，F(xiàn))， 其中：G:是一個上下文無關文法；V:有窮的屬性集,每個屬性與文法的一個終結符或非終結符相連,這些屬性代表與文法符號相關信息；

11、F:關于屬性的屬性斷言或一組屬性的計算規(guī)則(稱為語義規(guī)則) 。 斷言或語義規(guī)則與一個產生式相聯(lián),只引用該產生式左端或右端的終結符或非終結符相聯(lián)的屬性。 2遞歸下降法遞歸下降法又稱遞歸子程序法。在程序語言的語法定義中有許多采用遞歸定義。我們在對它進行語法分析時，編制的處理程序也采取遞歸的方式，可使其結構簡單易讀。但由于頻繁地調用子程序大大地降低了分析速度。2.1遞歸下降法的主要思想對每個非終結符按其產生式結構寫出相應語法分析子程序。因為文法遞歸相應子程序也遞歸，子程序的結構與產生式結構幾乎一致。所以稱此種方法稱為遞歸子程序法或遞歸下降法。2.2用程序表示遞歸子程序的內部結構 設A是一個非終結符：

12、 A1 A2 An 則寫(A) Û if charfirst(1 ) then(1 ) else if charfirst(2 ) then (2 ) else if charfirst(n ) then (n) else ERROR其中(i)表示調用處理符號串i的子程序。對A的任一右部i 設為： i = y1 y2 yn 則定義( i) Û begin(y1);(y2);(yn) end其中yj可分為下列兩種情況（j=1,n):1) yjVT,則 ( yj) Û if char yj then ERROR else READ(char)2) yjVN,則(yj)

13、表示調用關于yj的遞歸子程序。2.3遞歸下降法對文法的限制1、任一非終結符B都不是左遞歸的，否則會產生死循環(huán)。2、對A的任意兩個右部i , j ,有：first(i)first(j)= 。First(i)表示i所能導出串的第一個符號的集合。顯然，每個i的first(i)是互不相同的，否則則無法判斷應執(zhí)行哪個(i )。 3四元式的表示一般形式：(op,a,b,t1)如表達式x + y * z 翻譯成的四元式代碼序列是： (1)(*,y,z,t1) (2)(+,x,t1,t2) 常用的四元式表示:賦值語句 (=,x,-,t1)無條件轉移 jump L條件轉移 if x relop y jump L

14、過程調用 param x 和call p , n過程返回 return y索引賦值 (=,yi,-,x)和 (=.y,-,xi) 地址和指針賦值 (=,$y,-,x)，(=,*y,-,x)和(=,y,-,*z)四元式結構形式: 編號 (OP，ARG1，ARG2，RESULT)4語法制導翻譯4.1翻譯任務的處理過程編譯程序的整個任務就是把源程序翻譯為目標程序。實際上可以把每個編譯階段都看作是完成一定翻譯任務的處理過程：詞法分析階段把字符流翻譯為單詞流，語法分析階段把單詞流翻譯為語法樹，目標代碼生成階段把語法樹翻譯為匯編語言等等。 4.2語法制導翻譯在語法分析過程中，隨著分析的步步進展，每當進行推

15、導或歸約時，同步的去執(zhí)行每個產生式所附帶的語義規(guī)則描述的語義動作（或語義子程序），這樣進行翻譯的辦法稱作語法制導翻譯。 所謂屬性依賴圖是一個有向圖，用于描述分析樹中的屬性和屬性間的相互依賴關系。5中間代碼形式的描述及中間代碼序列的結構設計本系統(tǒng)中所采用的中間代碼形式是四元式，是一種比較普遍采用的形式。四元式的四個組成成分是：算符op，第一和第二運算對象ARG1和ARG2及運算結果RESULT。運算對象和運算結果有時指用戶自己定義的變量，有時指編譯程序引進的臨時變量。例如a：=b*c+b*d的四元式表示如下：1）（*，b，c，t1）2）（*，b，d，t2）3）（+，t1，t2，t3）4）（：=，

16、t3，-，a）四元式對中間結果的引用必須通過給定的名字，也就是說，四元式的聯(lián)系是通過臨時變量實現(xiàn)的。將gotoL寫成（jump，-，-，L）將if B rop C goto L寫成（jrop，B，C，L）本程序中所用到的四元式語句如下：1)形如（op，arg1，arg2，result）的賦值語句2)形如（jrop，B，C，L）的條件轉移語句3)形如（jump，-，-，L）的無條件轉移語句4)形如（=，arg1，-，result）的復寫語句6簡要的分析與概要設計6.1整體流程圖6.2詞法分析流程圖6.3語法制導翻譯流程圖7測試方法和測試結果7.1測試過程針對所設計的關于 for循環(huán)語句

17、的翻譯程序，測試出結果程序的可用性和健壯性。測試中分別使用了一個單重for循環(huán)語句和一個雙重嵌套的for循環(huán)語句，對結果程序進行測試，具體的測試程序、測試過程和測試結果如下：1.在txt文件中存入for語句的單重循環(huán)語句詞法分析語法制導翻譯結果2.在txt文件中存入for語句的單重循環(huán)語句詞法分析語法制導翻譯結果 7.2測試結論經過測試，可以得知，結果程序能達到預計的要求：對合法程序進行詞法分析和遞歸下降法，并生四元式表示的中間代碼。本次設計的文法是：S1->for(W)SxW->P;W1;W2W1->iOiW2->iO1O->>|<|>=|&l

18、t;=O1->+|-Sx->AmAm->PAm1Am1->PAm1|kongP->i=E E->TE1E1->+TE1 |-TE1 | kongT->FT1T1->*FT1 |/FT1| kongF->(E) | i |digit 8課程設計總結 在做本次實踐之前我對遞歸下降原理不是很了解，在查閱了相關資料后，對此有了深入了解，只要理解了分析方法的實現(xiàn)原理，編寫程序判斷出入字符串是否滿足給定的文法比較簡單。通過閱讀大量相關書籍，利用網(wǎng)絡查找各種資料，根據(jù)相關知識，我終于寫出了符合遞歸下降法的關于for語句的屬性文法。 此次設計對for語句進行了全面詞法分析和語法制導的翻譯，并得到了用于分析for 語句的結果程序。結果程序能對用戶輸入的程序代碼進行分析，判斷是否存在詞法錯誤和語法錯誤，如果出現(xiàn)錯誤，向用戶給出提示，如果沒有錯誤，則生成于輸入程序等價的中間代碼，方便后續(xù)編譯過程工作。本課內實