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

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

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

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

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

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

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

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

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

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

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

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

12、 A1 A2 An 則寫(xiě)(A) Û if charfirst(1 ) then(1 ) else if charfirst(2 ) then (2 ) else if charfirst(n ) then (n) else ERROR其中(i)表示調(diào)用處理符號(hào)串i的子程序。對(duì)A的任一右部i 設(shè)為： 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、表示調(diào)用關(guān)于yj的遞歸子程序。2.3遞歸下降法對(duì)文法的限制1、任一非終結(jié)符B都不是左遞歸的，否則會(huì)產(chǎn)生死循環(huán)。2、對(duì)A的任意兩個(gè)右部i , j ,有：first(i)first(j)= 。First(i)表示i所能導(dǎo)出串的第一個(gè)符號(hào)的集合。顯然，每個(gè)i的first(i)是互不相同的，否則則無(wú)法判斷應(yīng)執(zhí)行哪個(gè)(i )。 3四元式的表示一般形式：(op,a,b,t1)如表達(dá)式x + y * z 翻譯成的四元式代碼序列是： (1)(*,y,z,t1) (2)(+,x,t1,t2) 常用的四元式表示:賦值語(yǔ)句 (=,x,-,t1)無(wú)條件轉(zhuǎn)移 jump L條件轉(zhuǎn)移 if x relop y jump L

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

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

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

17、的翻譯程序，測(cè)試出結(jié)果程序的可用性和健壯性。測(cè)試中分別使用了一個(gè)單重for循環(huán)語(yǔ)句和一個(gè)雙重嵌套的for循環(huán)語(yǔ)句，對(duì)結(jié)果程序進(jìn)行測(cè)試，具體的測(cè)試程序、測(cè)試過(guò)程和測(cè)試結(jié)果如下：1.在txt文件中存入for語(yǔ)句的單重循環(huán)語(yǔ)句詞法分析語(yǔ)法制導(dǎo)翻譯結(jié)果2.在txt文件中存入for語(yǔ)句的單重循環(huán)語(yǔ)句詞法分析語(yǔ)法制導(dǎo)翻譯結(jié)果 7.2測(cè)試結(jié)論經(jīng)過(guò)測(cè)試，可以得知，結(jié)果程序能達(dá)到預(yù)計(jì)的要求：對(duì)合法程序進(jìn)行詞法分析和遞歸下降法，并生四元式表示的中間代碼。本次設(shè)計(jì)的文法是：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課程設(shè)計(jì)總結(jié) 在做本次實(shí)踐之前我對(duì)遞歸下降原理不是很了解，在查閱了相關(guān)資料后，對(duì)此有了深入了解，只要理解了分析方法的實(shí)現(xiàn)原理，編寫(xiě)程序判斷出入字符串是否滿(mǎn)足給定的文法比較簡(jiǎn)單。通過(guò)閱讀大量相關(guān)書(shū)籍，利用網(wǎng)絡(luò)查找各種資料，根據(jù)相關(guān)知識(shí)，我終于寫(xiě)出了符合遞歸下降法的關(guān)于for語(yǔ)句的屬性文法。 此次設(shè)計(jì)對(duì)for語(yǔ)句進(jìn)行了全面詞法分析和語(yǔ)法制導(dǎo)的翻譯，并得到了用于分析for 語(yǔ)句的結(jié)果程序。結(jié)果程序能對(duì)用戶(hù)輸入的程序代碼進(jìn)行分析，判斷是否存在詞法錯(cuò)誤和語(yǔ)法錯(cuò)誤，如果出現(xiàn)錯(cuò)誤，向用戶(hù)給出提示，如果沒(méi)有錯(cuò)誤，則生成于輸入程序等價(jià)的中間代碼，方便后續(xù)編譯過(guò)程工作。本課內(nèi)實(shí)