編譯原理課程設計

編譯原理課程設計實驗報告0113631胡彬0113634邸曉峰0113619宋如強第一章 需求分析1.1 引言設計目的本次課程設計是在完成一個學期的編譯原理課程之后，為了進一步加深對編譯原理相關知識的理解，培養(yǎng)實際解決問題的能力而進行的。結合本學期所開設的軟件工程課程，本次課程設計實驗過程要求按照軟件工程的思想來組織開發(fā)過程，按照軟件生命周期的階段劃分來進行。由于課程設計規(guī)模較小，所以對軟件生命周期進行適當?shù)暮喜ⅲ喕癁槲鍌€階段，即需求分析、總體設計、詳細設計、編碼實現(xiàn)和測試。設計任務針對本次課程設計我們設計了一個簡化的pascal語言，稱為mini-pascal。設計的任務就是開發(fā)出針對mini-pascal語言的編譯程序。標準的編譯程序結構分為五部分，分別是詞法分析、語法分析、語義分析和中間代碼生成、優(yōu)化和目標代碼生成。由于時間和能力所限，我們的編譯程序只包括前三個部分，最后生成四元式形式的中間代碼。語言概述mini-pascal語言基本上保留了pascal語言的程序結構，如過程可以嵌套定義，允許遞歸調(diào)用等。包括一些常用的可執(zhí)行語句如賦值語句、條件語句、當型循環(huán)語句和輸入輸出語句等。數(shù)據(jù)類型較為簡單，只有整型常數(shù)，數(shù)據(jù)結構也只有一種簡單變量。下面是mini-pascal語言程序的基本結構：program<標識符>[<變量說明>]procedure<標識符>[<參數(shù)表>][<變量說明>]begin[<語句部分>]beginend;[<語句部分>]end.過程可以嵌套定義，每個過程最后以“;”結束。主程序最后以“?”結束。語句：賦值語句，條件語句(if??then和if??then??else兩種形式)，當型循環(huán)語句，for語句，過程調(diào)用語句(有參數(shù)和無參數(shù)兩種)，讀語句，寫語句，復合語句。數(shù)據(jù)類型：只有一種整型數(shù)據(jù)。1.1.4工作分工本組成員由三人組成，分別是宋如強(0113620)、胡彬(0113631)、邸曉峰(0113634)。分工情況如下：詞法分析器部分每人都獨立實現(xiàn)一次，語法制導翻譯部分分為三部分，由邸曉峰完成遞歸下降分析器和相關的語義處理部分，胡彬完成LR分析器和相關的語義處理部分，宋如強完成中間代碼生成部分，各自寫出詳細的文檔資料，包括總體設計、詳細設計和測試。文檔的其它部分由邸曉峰完成。界面的實現(xiàn)視項目進展情況而定，如時間允許，則設計具有Windows風格的用戶界面；如果時間緊迫，則只能在VisualC++的運行環(huán)境中完成輸入輸出操作。1.2 系統(tǒng)分析系統(tǒng)完成簡單的翻譯任務，把用mini-pascal語言書寫的源程序轉(zhuǎn)換成特定的四元式序列，整體的框架圖如下：源程序符詞法分析器號表錯（誤信語法分析器處息理表）語義分析與中間代碼生成器四元式序列圖1.1系統(tǒng)總框圖1.3 系統(tǒng)邏輯模型數(shù)據(jù)流圖變量信息變量表過程名表用戶變量信息過程信息過程四元式信息序列源程序源程序輸出詞法遞歸結構說明語句語義中間編寫者結構說明語句四元式分析語法處理代碼分析二元式生成四元式二元式鏈表四元式文件處理語句LR分析處理語句語義四元式處理圖1.2系統(tǒng)數(shù)據(jù)流圖數(shù)據(jù)字典數(shù)據(jù)字典是關于數(shù)據(jù)的信息的集合，也就是對數(shù)據(jù)流圖中包含的所有元素的定義，在軟件分析和設計的過程中給人提供關于數(shù)據(jù)的描述信息。下面以卡片的形式對在數(shù)據(jù)流圖中出現(xiàn)的數(shù)據(jù)元素進行具體定義。名字:二元式名字:單詞名稱名字:單詞種別描述:由詞法分析器從源程序中描述:mini-pascal中合法單詞符描述:為每一種單詞符號賦予的識號整別出的合法的單詞符號,以的名稱數(shù)編碼二元式的形式記錄下來定義:單詞名稱=0{字符}20定義:單詞種別=1{數(shù)字}2定義:二元式=單詞名稱+單詞種位置:二元式位置:二元式別變量表位置:二元式文件過程名表四元式表名字:變量表名字:所在過程層次名字:相對位置描述:對源程序中說明的變量的別名:嵌套深度描述:表示變量在其所屬過程中相描述:變量所在過程的嵌套深度是關信息的記錄定義:所在過程層次=非負整數(shù)第幾個變量定義:變量表=變量名+所在過程位置:變量表定義:相對位置=非負整數(shù)層次+相對位置過程名表位置:變量表名字:過程名表名字:總變元個數(shù)名字:首變元地址描述:對源程序中定義的過程的描述:過程中所含的參數(shù)和變量描述:表示過程中的一個參數(shù)(或相個變量)在變量表中的位置關信息的記錄數(shù)的總和定義:首變元地址=非負整數(shù)定義:過程名表=過程名+參數(shù)個定義:總變元個數(shù)=參數(shù)個數(shù)+變位置:過程名表數(shù)+總變元個數(shù)+首變元地量個數(shù)址+嵌套深度+外過程地址位置:過程名表+首四元式地址名字:外過程地址描述:表示包含過程的第一層外過

名字:首四元式地址描述:過程中產(chǎn)生的第一條四元式程在過程表中的位置定義:外過程地址=非負整數(shù)位置:過程名表

在四元式表中的位置定義:首四元式地址 =非負整數(shù)位置:過程名表名字:四元式名字:操作碼名字:操作數(shù)描述:由語義處理器生成的中間描述:標識中間代碼中數(shù)據(jù)操作描述:記錄有進行操作的數(shù)據(jù)信代符息碼形式號的編碼定義:操作數(shù)=名字+相對數(shù)+類定義:四元式=操作碼+第一操作定義:操作碼=1{數(shù)字}2型數(shù)+第二操作數(shù)+第三操作位置:四元式+相對層差數(shù)位置:四元式位置:四元式文件1.4 接口用戶接口需求用戶界面采用 Windows標準窗口，分為兩部分，一部分用來編輯用戶的 mini-pascal語言源程序，另一部分用來顯示編譯結果。如果編譯有錯，則顯示錯誤信息 ；如果沒有錯誤，則顯示生成的四元式序列。提供給用戶的菜單命令有文件的打開、關閉、新建、保存和開始編譯。模塊接口需求詞法分析器和遞歸下降分析器、 LR分析器的接口都是由源程序轉(zhuǎn)換成的二元式鏈表。1.5 運行環(huán)境本系統(tǒng)用C語言編寫，在VisualC++集成開發(fā)環(huán)境下開發(fā) ，在Windows操作系統(tǒng)下運行。第二章 總體設計2.1系統(tǒng)概述系統(tǒng)功能分析mini-pascal編譯器完成的任務是把mini-pascal語言寫成的源程序翻譯成特定的四元式序列?？砂颜麄€任務劃分為三個相對獨立的階段，即詞法分析、語法分析、語義處理三部分。詞法分析的任務是從輸入的源程序文件中識別出一個個單詞符號，并用二元式的形式記錄寫來，也就是把字符流轉(zhuǎn)化為單詞符號串流。語法分析的任務是在詞法分析的基礎上，根據(jù)語法規(guī)則確定輸入的單詞符號串是否構成語法上正確的程序。語義分析的任務是對語法分析所識別出的各類語法范疇，分析其含義，并翻譯成四元式形式的中間代碼 (在本系統(tǒng)中即為最終的結果代碼)。系統(tǒng)結構設計語法分析可粗略分為自上而下分析法和自下而上分析法。為熟悉不同方法的應用，本系統(tǒng)各選用一種代表性的方法來進行語法分析。用自上而下的遞歸下降分析法分析程序中的結構和說明語句部分，用自下而上的LR分析法分析程序中的可執(zhí)行語句部分。兩部分各有對應的語義分析部分。語法分析和語義分析并不完全獨立，而是交替進行，對一條語句進行完語法分析，馬上調(diào)用語義分析，并生成對應的四元式。也就是每一條語法規(guī)則的產(chǎn)生式對應一段語義分析程序。詞法分析為單獨的一遍，語法分析和語義分析合為一遍。系統(tǒng)的結構層次如下圖 :編譯器用戶界面 詞法分析器 語法制導翻譯輸入 輸出 遞歸下降分析器 LR分析器遞歸下降語法分析 語義處理 LR語法分 語義處理圖2.1 系統(tǒng)結構層次圖2.2模塊功能定義詞法分析器基本功能：組織源程序輸入，按詞法規(guī)則拼讀單詞符號，并轉(zhuǎn)換成二元式，刪除注解行、空格和無用符號，檢查詞法錯誤。需識別的單詞符號分為五種類型，分別是關鍵字、標識符、常數(shù)、運算符和界符。輸入為源程序文件，輸出為二元式鏈表。詞法分析原理：采取直接分析法進行詞法分析，根據(jù)單詞的第一個字符劃分單詞類型：若第一個字符為字母，則將緊接在字母后面的字母，數(shù)字逐一拼湊成“字母數(shù)字串”，直到遇到非字母也非數(shù)字的其他字符，則此單詞就拼湊完成。這可能是用戶定義的標識符或系統(tǒng)的關鍵字。為區(qū)分這兩種不同的單詞符號，設計一關鍵字表，將所有的關鍵字存入表中。將拼湊空白字母或數(shù)字字母1非字母或數(shù)字2*0數(shù)字數(shù)字3非數(shù)字4*+5-6*7/8=9：10=11<12>13=14非=或>*15>16=17非=*18(19)20，21；2223.圖2.2對mini-pascal語言的詞法分析狀態(tài)轉(zhuǎn)換圖出的“字母數(shù)字串”與關鍵字表中的關鍵字進行比較，看是否相同。如果在關鍵字表中查不到與此“字母數(shù)字串”相同的詞，則說明此 “字母數(shù)字串”為用戶定義的標識符 ；如查到與關鍵字表中的某個單詞一樣，則說明此 “字母數(shù)字串”就是這個關鍵字。這一過程可單獨設置一個 “查關鍵字表”過程。若第一個字符為數(shù)字，同樣向后識別，將緊跟在后面的數(shù)字和前面的數(shù)字拼接在一起直到非數(shù)字的其他字符為止，這個單詞為整數(shù)。若第一個字符為其他類型，則根據(jù)字符本身就可以識別，有的雙字符運算符 (如>=,:=等)需要再向后識別一個字符才能識別。遞歸下降分析器基本功能：在詞法分析識別出的單詞符號串的基礎上，分析并判定源程序中程序結構語句是否符合語法規(guī)則。遞歸下降分析法：語法分析器的工作本質(zhì)上就是按文法的產(chǎn)生式，識別輸入的符號串是否為一個句子。從概念上講，就是要建立一棵與輸入串相匹配的語法分析樹。按照語法分析樹的建立方法，大致可把語法分析分成兩類，一類是自上而下分析法，一類是自下而上分析法。遞歸下降分析法屬于自上而下分析法，它要求文法不含左遞歸并消除回溯。這是因為由于采用最左推導，左遞歸將使得輸入串的分析過程陷入無限循環(huán)之中；而采用試探的方法，匹配不成功回溯到前面分析的某一步，可能出現(xiàn)假匹配，造成對輸入串識別的失敗，而且不能準確報告輸入串的出錯位置。左遞歸一般有兩種情況：直接左遞歸和間接左遞歸。如果文法中任意一個非終結符P，若PP（VUV），并且在最左推導中有PP形式，稱為直接左遞歸；在最左推導中NT有+P=>P形式，稱為間接左遞歸。通過對文法的改寫,可消除左遞歸,如下：消除文法的左遞歸一般規(guī)則：P→P1P2??Pm12??ni≠改寫為：P→1PP???nP2P→1P2P???mP消除回溯可采用提取最左公共因子的方法改寫文法，使得所有侯選式的首字符集兩兩不相交。消除回溯的一般規(guī)則：A→提取公因子:A→ (改寫后為:A→ AA→

12??n12??12??)12??n12??m12??n

mmmini-pascal語言程序結構部分產(chǎn)生式：(1)PROG→programident；PP.含義:<程序>→program<名字>；<過程>.(2)PP→[IDP]{PRP}beginPLend<過程>→[<變量說明>]{<子程序>}begin<語句>end(3)PRP→procedureident[PARL]；PP；<子程序>→procedure<名字>[<參數(shù)說明>]；<過程>；(4)IDP→varident{,ident}；<變量說明>→var<變量名>{,<變量名>}；(5)PARL→(ident{,ident})<參數(shù)說明>→(<變量名>{,<變量名>})該文法程序結構部分產(chǎn)生式均不含左遞歸，也不包含公因子，所以不必改寫，符合遞歸分析法的要求。遞歸下降分析原理 ：根據(jù)每個非終結符產(chǎn)生是可以直接書寫出識別產(chǎn)生式右部符號的子程序。這里規(guī)定在進入子程序前已從輸入串中讀入下一個單詞符號在一指定緩沖區(qū) sym中。遞歸子程序就是從左到右逐一識別產(chǎn)生式右部符號的過程。若產(chǎn)生式右部的某個符號為終結符，則要判斷當時 sym中的單詞是否與之一樣，若不一樣則表示出錯 ；若識別到的某個符號是產(chǎn)生式右部的某個非終結符號，則讀入下一單詞符號并再調(diào)用此非終結符的遞歸子程序。分析器基本功能：在詞法分析識別出的單詞符號串的基礎上，分析并判定源程序中可執(zhí)行語句是否符合語法規(guī)則，并適時調(diào)用語義分析器。LR分析原理：一個LR分析器實質(zhì)上是一個帶先進后出存儲器（棧）的確定有限狀態(tài)自動機。我們把“歷史”和“展望”材料綜合地抽象成某些“狀態(tài)”。分析棧用來存放狀態(tài)。棧里的每個狀態(tài)概括了從分析開始直到某一歸約階段的全部“歷史”和“展望”資料。任何時候，棧頂?shù)臓顟B(tài)都代表了整個歷史和以推測出的展望。因此，在任何時候都可從棧頂狀態(tài)得知你所想了解的一切，而絕對沒有必要從底而上翻閱整個棧。LR分析器的每一步工作都是由棧頂狀態(tài)和現(xiàn)行輸入符號所唯一決定的。為了有助于明確歸約手續(xù)，我們把以歸約出的文法符號串也放在棧里。語義分析器基本功能：在LR語法分析器做歸約動作時被調(diào)用，進行相應的語義動作，并適時生成四元式。LR分析原理：為了生成四元式，在LR分析器進行語法分析時，應該適時做相應的語義處理。而LR分析器的歸約動作標志著一條可執(zhí)行語句的結束，因此我們應該在此時調(diào)用語義分析器，利用棧頂被歸約掉的符號完成相關的語義動作。2.3模塊設計說明把各個模塊按功能分解，劃分為若干具有獨立功能的函數(shù)模塊，體現(xiàn)了結構化程序設計方法的思想。各函數(shù)模塊的詳細設計在后續(xù)章節(jié)給予詳細介紹，本節(jié)只以IPO表的形式說明各函數(shù)模塊的基本結構。詞法分析器系統(tǒng)：mini_pascal編譯器 作者：胡彬模塊：insert 日期：2004-10-8編號：01被調(diào)用： 調(diào)用：outword 無輸入： 輸出：一個二元式 無處理：將該二元式連接到 ax_list鏈表的末尾。局部數(shù)據(jù)元素： inti;structax*temp;注釋：outword模塊在向屏幕和中間文件輸出二元式時，也同時調(diào)用本模塊，將二元式鏈接到ax_list鏈表的末尾。系統(tǒng)：mini_pascal編譯器 作者：胡彬模塊：wordscan 日期：2004-10-8編號：02被調(diào)用： 調(diào)用：mini_pascal編譯器 mpname，scan輸入： 輸出：源程序文件名 二元式文件及鏈表處理：接受用戶輸入的源程序文件名，判斷文件是否存在，若不存在，則提示用戶重新輸入。輸入正確后，掃描文件并生成二元式，輸出到顯示器和磁盤，并生成二元式鏈表供語法分析使用。局部數(shù)據(jù)元素： inti; FILE*fp;注釋：整形變量i表示詞法分析進行狀態(tài)，其值為-1時詞法分析結束。

系統(tǒng)：mini_pascal編譯器 作者：胡彬模塊：mpname 日期：2004-10-8編號：03被調(diào)用： 調(diào)用：main initiate輸入： 輸出：源程序文件名 源程序文件指針（若該文件不存在，返回 NULL）處理：接受用戶輸入的源程序文件名，判斷文件是否存在，若不存在，則返回NULL。若存在，調(diào)用initiate模塊，接受用戶輸入的文件名，初始化行計數(shù)器，初始化中間文件的文件名，并生成中間文件，返回源程序文件指針。局部數(shù)據(jù)元素： FILE*fp;注釋：文件指針*fp作為本模塊的返回值，指向源程序文件指針系統(tǒng)：mini_pascal編譯器 作者：胡彬模塊：scan 日期：2004-10-8編號：04被調(diào)用： 調(diào)用：main get_char,kind,error,outword輸入： 輸出：源程序文件指針 一個單詞的二元式處理：調(diào)用get_char()掃描源程序文件，并作單詞拼接，決定單詞種類（適時調(diào)用kind()判別其種類），調(diào)用outword()輸出二元式，遇錯調(diào)用error()報告錯誤信息。局部數(shù)據(jù)元素：structaxcur_ax;intlen;intk;charword_name[10];staticcharreback;注釋：本模塊的返回值為整形。單詞拼接成功，返回“1”；失敗，返回“0”；文件結束，返回“-1”。系統(tǒng)：mini_pascal編譯器 作者：胡彬模塊：get_char 日期：2004-10-8編號：06被調(diào)用： 調(diào)用：scan 無輸入： 輸出：源程序文件指針 讀入的一個字符處理：讀入一個字符并返回，保留換行符，遇到文件尾即關閉文件，并返回結束標志“-1”。局部數(shù)據(jù)元素：staticcharLine[81];staticintcur_position;charcur_char;charc;注釋：Line存放預讀入的一行字符，然后再從Line中讀出一個字符，這樣可以保留換行符，并更新行計數(shù)器 Linecounter，cur_position表示將要讀出的字符在 Line中的位置。cur_char保存讀出的字符，做返回值。

系統(tǒng)：mini_pascal編譯器 作者：胡彬模塊：initiate 日期：2004-10-8編號：05被調(diào)用： 調(diào)用：mpname 無輸入： 輸出：源程序文件名 中間文件及其文件名處理：接受用戶輸入的文件名，初始化行計數(shù)器，初始化二元式鏈表，初始化中間文件的文件名，并生成中間文件。局部數(shù)據(jù)元素： FILE*fp;inti,len;注釋：本模塊主要完成對行計數(shù)器Linecounter，中間文件名midfname的初始化工作。midfname由源程序文件名fname生成，其格式為“obj_fname”。系統(tǒng)：mini_pascal編譯器 作者：胡彬模塊：kind 日期：2004-10-8編號：07被調(diào)用： 調(diào)用：scan 無輸入： 輸出：一個單詞名稱 一個單詞種類處理：當一個標識符被拼讀后調(diào)用此過程查找在保留字表中有無與之相同的“字符數(shù)字串”，如查不到，則是用戶標實符，返回“17”；若查到，則返回保留字的種類。局部數(shù)據(jù)元素：inti;注釋：在本模塊中定義了全局變量keyword[16][10]，用來存放所有保留字。其下標值加1就是該保留字的單詞種類。系統(tǒng)：mini_pascal編譯器 作者：胡彬模塊：error 日期：2004-10-8編號：08被調(diào)用： 調(diào)用：scan 無輸入： 輸出：一個非法字符 錯誤信息處理：詞法分析遇到非法字符時，打印出錯信息：行數(shù)，及出錯字符。局部數(shù)據(jù)元素：無注釋：當scan模塊在拼接單詞時遇到非法字符。則調(diào)用本模塊，在顯示器上打印出錯信息：出錯行數(shù)和出錯字符。

系統(tǒng)：mini_pascal編譯器 作者：胡彬模塊：outword 日期：2004-10-8編號：09被調(diào)用： 調(diào)用：scan 無輸入： 輸出：待輸出的二元式 二元式的內(nèi)容處理：按格式將二元式輸出到顯示器和中間文件，并將該二元式連接到ax_list鏈表尾。局部數(shù)據(jù)元素： FILE*fp;注釋：當scan模塊成功拼接完成一個單詞后，調(diào)用本模塊，將其二元式輸出到顯示器和中間文件。中間文件的打開方式為 ”a”。遞歸下降分析器系統(tǒng):遞歸下降分析器作者:邸曉峰系統(tǒng):遞歸下降分析器作者:邸曉峰模塊:讀單詞符號日期:2004.10.29模塊:遞歸分析PROG日期:2004.10.29名稱:getWord名稱:reurPROG被調(diào)用:1)recurPP調(diào)用:無被調(diào)用:主程序調(diào)用:1)getWord2)recurPROG2)enterPTable3)recurIDP3)error_handle4)recurPRP4)recurPP5)recurPARL輸入:無輸出:無輸入:無輸出:無處理:從二元式鏈表表頭讀出單詞符號到一指處理:對應分析上頁第一條產(chǎn)生式定緩沖區(qū)局部數(shù)據(jù)元素:二元式指針局部數(shù)據(jù)元素:無注釋:指定緩沖區(qū) WORD為全局變量 注釋:主程序結構系統(tǒng):遞歸下降分析器作者:邸曉峰系統(tǒng):遞歸下降分析器作者:邸曉峰模塊:遞歸分析PP日期:2004.10.29模塊:遞歸分析PRP日期:2004.10.29名稱:recurPP名稱:recurPRP被調(diào)用:調(diào)用:1)getWord被調(diào)用:1)recurPP調(diào)用:1)getWord2)PL2)enterPTable1)recurPROG3)recurIDP3)recurPP2)recurPRP4)recurPRP4)recurPARL5)error_handle5)error_handle輸入:無輸出:無輸入:無輸出:無處理:對應分析上頁第二條產(chǎn)生式

處理:對應分析上頁第三條產(chǎn)生式局部數(shù)據(jù)元素

:無

局部數(shù)據(jù)元素

:無注釋:過程結構

注釋:

子程序結構系統(tǒng):遞歸下降分析器作者:邸曉峰系統(tǒng):遞歸下降分析器作者:邸曉峰模塊:遞歸分析IDP日期:2004.10.29模塊:遞歸分析PARL日期:2004.10.29名稱:recurIDP名稱:recurPARL被調(diào)用:1)recurPP調(diào)用:1)getWord被調(diào)用:調(diào)用:1)getWord2)enterVTable1)recurPRP2)enterVTable3)error_handle3)error_handle輸入:無輸出:無輸入:無輸出:無處理:對應分析上頁第四條產(chǎn)生式處理:對應分析上頁第五條產(chǎn)生式局部數(shù)據(jù)元素:無局部數(shù)據(jù)元素:無注釋:變量說明結構注釋:參數(shù)說明結構系統(tǒng):遞歸下降分析器作者:邸曉峰系統(tǒng):遞歸下降分析器作者:邸曉峰模塊:填變量名表日期:2004.11.27模塊:填過程名表日期:2004.11.27名稱:enterVTable名稱:searchVTable被調(diào)用: 調(diào)用:無recurIDPrecurPARL輸入:標志是”正常 輸出:無填入”還是”補填處理:把讀入WORD的變量信息填入變量表局部數(shù)據(jù)元素:記錄變量表當前項的下標值tempointer和臨時指針i注釋:WORD,變量表,嵌套深度,變量相對個數(shù)均為全局變量系統(tǒng):遞歸下降分析器 作者:邸曉峰模塊:填過程名表 日期名稱:enterPTable調(diào)用:無調(diào)用:無被調(diào)用:recurPRP 調(diào)用:1)searchVTable2)error_handle輸入:無 輸出:無處理:該過程只能填入過程名,嵌套深度和直接外過程位置三項局部數(shù)據(jù)元素:記錄嵌套深度templevel和表項索引值tempindex注釋:過程名表其它項在適當時候直接用賦值語句填入

被調(diào)用:PL 調(diào)用:error_handle輸出:查到的變量輸入:變量名指針 名在變量名表中的位置,未查到則為-1處理:先從本過程開始查找,若找不到,則循環(huán)查找外過程直到主程序;若還找不到,則在從表尾找,看是否已補填.局部數(shù)據(jù)元素 :記錄當前所查過程位置currentproc,該過程第一個變量位置 firstvar,該過程總的變量數(shù) sumvar和臨時指針 i注釋:需要過程名表和變量名表配合查找,還有過程棧系統(tǒng):遞歸下降分析器作者:邸曉峰模塊:查過程名表日期:2004.11.27名稱:searchPTable被調(diào)用:enterPTable調(diào)用:error_handle輸入:過程名指針輸出:查到的過程名在變量名表中的位置,未查到則為-1處理:查找已填入的過程名表中是否有與參數(shù)相同的過程名局部數(shù)據(jù)元素 :臨時指針 i注釋:無系統(tǒng):遞歸下降分析器作者:邸曉峰系統(tǒng):遞歸下降分析器作者:邸曉峰模塊:忽略讀入日期:2004.11.2模塊:初始化日期:2004.11.2名稱:skip名稱:init被調(diào)用:1)reurPROG調(diào)用:getWord被調(diào)用:主程序調(diào)用:無2)recurPP3)recurPRP4)recurIDP5)recurPARL輸入:規(guī)定的索引值輸出:無輸入:無輸出:無處理:按索引值執(zhí)行相應的分支程序些單詞直到指定的一些單詞為止

,跳過一

處理:初始化全局變量并把錯誤信息文件讀入內(nèi)存區(qū)局部數(shù)據(jù)元素

:無

局部數(shù)據(jù)元素

:無注釋:可能考慮不夠全面

注釋:讀文件代碼和文件內(nèi)容有關定

,由作者規(guī)分析器系統(tǒng)：mini_pascal編譯器 作者：胡彬模塊：LRAnalyser 日期：2004-10-20編號：01被調(diào)用：RecurAnalyser調(diào)用：WordAnalyser,checkAction,OUTQ,errorDeal,initialize,輸入：無輸出：四元式表，四元式文件處理：將詞法分析器生成的單詞序列用LR分析法進行語法分析，并輸出四元式表和四元式文件。局部數(shù)據(jù)元素： inti；注釋：整形變量i保存語法分析器運行狀態(tài)，如果出現(xiàn)語法錯誤，則調(diào)用出錯處理模塊。系統(tǒng)：mini_pascal編譯器 作者：胡彬模塊：checkAction 日期：2004-10-20編號：03被調(diào)用：LRAnalyser調(diào)用：getWord，checkGoto輸入：無輸出：語法分析狀態(tài)處理：逐一讀入單詞，并做LR語法分析，同時條用語義分析器生成四元式。局部數(shù)據(jù)元素：intcluster;intstart;intact;intplen;inti;char*temp;注釋：調(diào)用 checkGoto模塊進行歸約前，先將棧頂將要歸約的字符串保存在signCache中，以便在語義分析時使用。如果遇到語法錯誤，以后不再產(chǎn)生四元式。

系統(tǒng)：mini_pascal編譯器 作者：胡彬模塊：initialize 日期：2004-10-20編號：02被調(diào)用：LRAnalyser調(diào)用：無輸入：無輸出：無處理：完成初始化工作。局部數(shù)據(jù)元素： inti；注釋：將遞歸下降分析器讀入的“begin”去掉，以便LR分析結束時能順利返回。重新初始化行計數(shù)器為1，初始化規(guī)約字符串緩存數(shù)組：signCache為空。系統(tǒng)：mini_pascal編譯器 作者：胡彬模塊：checkGoto 日期：2004-10-20編號：04被調(diào)用： checkAction調(diào)用：LRSemanticor（語義處理模塊）輸入：歸約式編號輸出：語法分析狀態(tài)處理：按歸約式編號對棧頂字符串進行歸約，并調(diào)用語義處理模塊進行相應的語義處理。局部數(shù)據(jù)元素： intcluster;intstart;char*temp;注釋：如果遇到語法錯誤，則將 isTrue置為false，以后不再調(diào)用語義處理模塊進行語義處理系統(tǒng)：mini_pascal編譯器 作者：胡彬模塊：errorDeal 日期：2004-10-20編號：05被調(diào)用：LRAnalyser調(diào)用：getWord輸入：無輸出：出錯信息處理：語法分析遇到語法錯誤時，打印相應的錯誤信息，并跳過出錯的語句，清空已進入分析棧中的錯誤語句部分內(nèi)容。這樣就可以繼續(xù)分析后面的內(nèi)容。局部數(shù)據(jù)元素： intback;char*temp;注釋：如果end前的最后一條語句出錯，則讓分析?；赝说娇梢越邮躤nd的地方。系統(tǒng)：mini_pascal編譯器 作者：胡彬模塊：showsignStack 日期：2004-10-20編號：07被調(diào)用：LRAnalyser調(diào)用：無輸入：無輸出：符號棧的內(nèi)容處理：顯示符號棧的全部信息。局部數(shù)據(jù)元素： intk;FILE*fp;stack<int>注釋：由于使用C++類庫提供的stack類，不能直接訪問棧中內(nèi)部元素，所以定義一個臨時的棧，先將符號棧中元素一個個彈出并顯示，再保存在臨時棧中，然后再搗回到臨時棧中。（用于調(diào)試）

系統(tǒng)：mini_pascal編譯器 作者：胡彬模塊：showclusterStack 日期：2004-10-20編號：06被調(diào)用：LRAnalyser調(diào)用：無輸入：無輸出：狀態(tài)棧的內(nèi)容處理：顯示狀態(tài)棧的全部信息。局部數(shù)據(jù)元素：intk;FILE*fp;stack<int>temp;注釋：由于使用C++類庫提供的stack類，不能直接訪問棧中內(nèi)部元素，所以定義一個臨時的棧，先將狀態(tài)棧中元素一個個彈出并顯示，再保存在臨時棧中，然后再搗回到狀態(tài)棧中。（用于調(diào)試）語義分析器系統(tǒng)：mini_pascal編譯器 作者：宋如強模塊：LRSemanticor 日期：2004-10-8編號：01被調(diào)用：checkGoto（LRAnalyser）調(diào)用：ENTRY，CHECK，GEN，BACKPATCH輸入：歸約產(chǎn)生式編號輸出：無處理：LR語法分析作歸約動作時，調(diào)用本模塊，做相應的語義處理，并適時生成四元式，將其填入四元式表。局部數(shù)據(jù)元素：char*value;charc[4];intnum;Operandtemp1,temp2,temp3;注釋：字符數(shù)組c[4]，用來存放拼接中的中間變量名。系統(tǒng)：mini_pascal編譯器 作者：宋如強模塊：ENTRY 日期：2004-10-8編號：03被調(diào)用：LRSemanticor調(diào)用：無輸入：待查變量的名稱輸出：該變量在變量表中的序號處理：檢查參數(shù)所指變量是否存在于變量表中。若查到，返回該變量在表中的序號，否則返回-1局部數(shù)據(jù)元素： inti;注釋：整形變量 i用于循環(huán)查找變量表

系統(tǒng)：mini_pascal編譯器 作者：宋如強模塊：GEN 日期：2004-10-8編號：02被調(diào)用：LRSemanticor調(diào)用：無輸入：1個操作符，三個操作數(shù)輸出：無處理：生成四元式，并填入四元式表局部數(shù)據(jù)元素： Quatypetemp;注釋：對于不同的操作數(shù)類型，對其各個域進行不同設置。系統(tǒng)：mini_pascal編譯器 作者：宋如強模塊：CHECK 日期：2004-10-8編號：04被調(diào)用：LRSemanticor調(diào)用：無輸入：待查過程的名稱輸出：該過程在過程表中的序號處理：檢查參數(shù)所指過程是否存在于過程表中，并檢查調(diào)用是否合理。若查到且調(diào)用合理，返回該過程在表中的序號，否則返回 -1局部數(shù)據(jù)元素： inti,j;注釋：整形變量i用于循環(huán)查找過程表，j表示調(diào)用關系。系統(tǒng)：mini_pascal編譯器 作者：宋如強模塊：BACKPATCH 日期：2004-10-8編號：05被調(diào)用：LRSemanticor調(diào)用：無輸入：要回填的四元式序號，要跳轉(zhuǎn)到的四元式序號。輸出：無處理：將參數(shù)二填入?yún)?shù)一所指的四元式的目的操作數(shù)中。局部數(shù)據(jù)元素： inti;注釋：完成調(diào)轉(zhuǎn)語句四元式的回填工作。

系統(tǒng)：mini_pascal編譯器 作者：宋如強模塊：OUTQ 日期：2004-10-8編號：06被調(diào)用：mini_pascal編譯器調(diào)用：無輸入：無輸出：四元式表內(nèi)容及文件處理：將四元式表中的四元式逐條輸出到顯示器上，并生成四元式文件。在此過程中，要完成操作碼從編碼到符號的轉(zhuǎn)換。局部數(shù)據(jù)元素： char*temp;inti;FILE*fp;注釋：temp存放操作碼，i用于循環(huán)輸出四元式，fp指向四元式文件。第三章 詞法分析器詳細設計3.1設計思想作為一個完整編譯程序最基本的功能模塊，詞法分析器的任務是從源程序文件中識別出一個個單詞符號（合法的），并把它們用如下二元組形式表示：（單詞名稱，單詞種類）詞法分析器的輸出即是語法分析器的輸入。我們可以將詞法分析器作為語法分析器的一個子模塊，在語法分析的過程中由語法分析器在需要時調(diào)用它；也可以將詞法分析器作為編譯程序中獨立一遍的掃描程序，這時它的任務是將一個字符流文件按詞法規(guī)則改造成一個單詞流文件。也就是說輸入詞法分析器的是由一個個字符組成的源程序，通過詞法分析器識別分析后輸出由若干個單詞名稱和單詞編碼組成的紀錄文件：輸入 輸出字符流源文件 詞法分析器 單詞流文件3.2主要數(shù)據(jù)結構程序文件指針：在 mpname函數(shù)內(nèi)定義程序文件指針 *fp，指向源程序文件名，同時作mpname函數(shù)的返回值。接口文件指針：在 main函數(shù)內(nèi)定義接口文件指針 *fp，作為mpname函數(shù)的返回值，同時作為scan函數(shù)的參數(shù)。行緩沖區(qū)指針：在 get_char函數(shù)內(nèi)定義行緩沖區(qū) charLine[81]，用來預先從源程序文件讀入一行。行緩沖區(qū)當前位置指針：在 get_char函數(shù)內(nèi)定義行緩沖區(qū)當前位置指針 intcur_position，用來指示當前要讀入的字符位置。讀入行緩沖區(qū)：在 scan函數(shù)內(nèi)定義讀入行緩沖區(qū) word_name[10]，用來存放正在拼接的單詞。存放源程序文件名的字符串數(shù)組 ：全局變量fname[77]，用來存放源程序文件名。存放二元式文件名的字符串數(shù)組：全局變量 midfname[81]，用來存放二元式文件名，其二元式文件名的格式為：“ obj_源程序文件名”。二元式文件結構：二元式結構如下所示，structax{charname[10]; //單詞名稱intkind; //單詞種類};由于對C語言來說，所有的文件都只是字符流文件，也就是說在 C的文件中不存在結構體，因此只能將二元式的內(nèi)容按一定的格式輸出到文本文件。保留字表數(shù)組結構：charkeyword[16][10]={{"program"},{"var"},{"procedure"},{"begin"},{"end"},{"if"},{"then"},{"else"},{"while"},{"do"},{"for"},{"step"},{"until"},{"call"},{"read"},{"write"}};行計數(shù)器：全局變量 Linecounter，用來存放行數(shù)。3.3程序流程圖初始化模塊用戶輸入文件名文件存在？D是文件結束？否讀一行到緩沖區(qū)中B開始拼接字符已有首字符？是首字符類型(,)*,/,=,，,;,.,+,-,:>,<確定類型讀一個字符讀一個字符否否輸出編碼=？=？是是B確定類型確定類型B輸出編碼輸出編碼打印出錯信息否>？是異常，退出BA

是否 否繼續(xù)輸入？是結束，退出否讀入一個非空格字符是數(shù)字E回車 字母確定類型 讀一個字符輸出編碼字母或數(shù)字？否清空緩沖區(qū)回退該字符確定類型D輸出編碼C BA否首字符是<？C是確定類型 回退該字符輸出編碼 確定類型B輸出編碼

E讀一個字符是數(shù)字？否回退該字符確定類型輸出編碼B B第四章

遞歸下降分析器詳細設計4.1設計思想遞歸下降分析器是對 mini-pascal語言的程序結構部分語句進行識別，所以對 節(jié)中的五條產(chǎn)生式分別設計一個遞歸程序來識別。 遞歸程序的原理在 節(jié)中已有說明，這里不再贅述。相應的語義處理主要有以下兩個方面 :(1)將在分析過程中識別出的程序名、過程名、變量名、參數(shù)名及其相關的信息填到過程名表和變量名表中，為以后生成中間代碼保留必要的信息；(2)在過程的可執(zhí)行語句開始和結束時生成一些必要的四元式。所以需要設計一個填變量名表模塊，一個填過程名表模塊和生成四元式模塊 (可和語義處理部分共享 )。另外還要有錯誤處理模塊。出現(xiàn)錯誤時顯示給用戶錯誤信息和行號?？梢园阉锌赡艿腻e誤信息用編號形式組織，以文件形式保存在磁盤上。程序初始化時先把它們從文件讀入一個字符串數(shù)組中，數(shù)組一個元素放一條信息，數(shù)組下標號就是錯誤編號。調(diào)用時按錯誤編號調(diào)用錯誤處理模塊。當源程序中出現(xiàn)語法錯誤,進行錯誤處理后，為了使遞歸程序繼續(xù)進行下去，忽略出錯語句中剩下的單詞符號，直到讀入下一個可識別的終結單詞符號。這一功能設一個單獨模塊實現(xiàn)。還要設一初始化模塊，給全局變量賦初值。4.2數(shù)據(jù)結構從節(jié)中的數(shù)據(jù)流圖中可以看到，變量名表和過程名表在語法分析和語義處理階段都要使用，即在遞歸下降分析器,LR分析器和語義分析器中都要使用，所以把這兩個表設為全局變量.其數(shù)據(jù)結構如下:變量名表項:structvariable_item{char*vname;

//變量名首址

(動態(tài)分配內(nèi)存

)intplevel;

//變量所在過程的層次intrelposition;

//變量在其過程中的相對位置

(即第幾個變量

)}vitem;變量名表

:structvariable_table{vitemtable[50];

//變量表項數(shù)組intfirst;intlast;

//正確填入的標記指針//未說明的變量 "倒填"時的標記指針}vtabel;過程名表項

:structprocedure_item{char*pname;

//過程名首址

(動態(tài)分配內(nèi)存

)intparanum;

//參數(shù)個數(shù)intvariablenum;

//變量個數(shù)

(包括參數(shù)

)intfirstinvtable;

//第一個變量在變量表中的位置

(下標)intplevle;

//過程嵌套深度intoutposition;intquaterposition;

//直接外過程在過程表中的位置//本過程第一條四元式地址

(下標)}pitem;過程名表

:structprocedure_tabel{pitemtable[20];

//過程名表項數(shù)組intpointer;

//指針}ptabel;在分析執(zhí)行語句是需要記錄語句當前所在過程，便于進行查找變量是否已定義，所以設一棧結構，每分析出一過程名，即把該過程名所在過程名表中的位置 (下標)入棧；每分析出一“end”單詞，即作出棧操作，使棧頂保持為當前正在分析的過程。棧結構如下 :structstack_item{intindex; //過程所在過程名表的表項structstack_item*next;}stack_item;structstack{stack_item*base;stack_item*top;

//過程棧}stack;詞法分析器產(chǎn)生的二元式文件以二元式鏈表的結構實現(xiàn)，語法分析時要從二元式鏈表中讀入一個個單詞符號，所以設一二元式項作為緩沖區(qū)，讀入二元式鏈表中的當前項，判斷分析并作相應處理。二元式的結構如下 :structDuatype{char*value;

//單詞符號名首址

(動態(tài)分配內(nèi)存

)intindex;

//相應單詞編號structDuatype*next;

//指向下一項的指針}Duatype;緩沖區(qū)結構

:Duatypeword;錯誤信息文件需要一文件類型指針來關聯(lián)，設為

:FILE*perrorfile;把錯誤信息讀入到一字符串數(shù)組，設一字符指針數(shù)組，存放各錯誤信息串的首地址。錯誤信息以4.3節(jié)第10項錯誤情況分析中所說明的錯誤情況為主要內(nèi)容。 錯誤信息串需動態(tài)分配空間，還需一個字符串緩沖區(qū)，按錯誤編號一條一條讀入錯誤信息，設一二維數(shù)組即可 :char

errtext[16][20];在填變量名表和過程名表時，需要過程嵌套深度和變量相對個數(shù)信息顯示行號，所以設變量分別記錄上述信息，如下:

；顯示錯誤信息時要int

level;

//嵌套深度int

count;

//int

linenum;

//行數(shù)4.3程序流程圖1)讀單詞符號(getWord)模塊開始是否到鏈尾？N

YWORD.index=0用臨時變量 temp取鏈頭鏈頭移向下一項temp是否為換行?NY行數(shù)加1刪除temp項用temp取鏈頭項鏈頭移向下一項word temp所指節(jié)點內(nèi)容刪除temp項結束2)填變量名表 (enterVTable)模塊YY是否越界?N錯誤處理(變量名相對變量表越界)數(shù)=1?Y結束填過程名表第一個變量所在位置

開始參數(shù)=0?N是否與同一過程已填入變量重名?N填變量名填嵌套深度填相對個數(shù)

N是否越界?N表尾項填入變量名表尾指針減 1Y結束錯誤處理(變量名重名)結束

Y錯誤處理(變量名表越界)結束變量相對個數(shù)加 1順序填入的表項指針加 1結束3)查變量名表 (searchVTable)模塊開始取currentproc=過程棧頂項currentproc=-1?N取firstvar=當前過程的第一個變量在變量名表紅的位置取sumvar=當前過程變量個數(shù)i=firstvari<sumvar? NY

YY返回i值結束

i=表尾下標從表尾開始查是否有與變量同名的項?N錯誤處理(變量為定義)所查變量是否與變量名表第 Yi項同名?返回i值N結束再取currentproc為當前過過程的外層

返回-1結束4)填過程名表 (enterPTable)模塊開始是否查到同名過程?N填入過程名填入嵌套深度Y 是否是過程名表第一項?填外過程位置為 -1

Y錯誤處理(過程名重名)結束N比較當前深<度和前一項嵌套深度?

>按前一項的外過程位置查找,直到一項的嵌套深度與當前深度相等填外過程位置為該項的外過程位置

=填外過程位置為前一項的外過程位置

填外過程位置為前一項下標結束另外，在recurPARL模塊中分析出“)”后，填入過程名表當前項的參數(shù)個數(shù)項； 在recurIDP模塊中分析出“;”后，填入過程名表當前項的變量個數(shù)項；在 recurPP()模塊中分析出“begin”后，生成一條開辟空間的四元式，同時把該四元式在四元式表中的位置填入過程名表當前項的第一條四元式地址項；在填變量表名模塊中，若變量計數(shù)為 1，則在填入變量名表相關信息后， 把該變量在變量名表中的位置填入過程名表當前項的第一個變量位置項。5)主程序結構分析 (recurPROG)模塊開始是否是 N“program”?Y讀入下一個單詞

錯誤處理是否是用戶N定義標示符錯誤處理?Y填過程名表讀入下一個單詞N是否是”;”? 錯誤處理Y讀入下一個單詞轉(zhuǎn)入過程結構分析模塊N是否是”.”? 錯誤處理Y結束6)過程結構分析 (recurPP)模塊開始是否是“var”?Y轉(zhuǎn)入變量說明結構分析模塊是否是“procedure”?Y轉(zhuǎn)入子程序結構分析模塊是否是“begin”?Y讀入下一個單詞

N是否Y有錯錯誤處理?NN是否Y有錯?錯誤處理NN錯誤處理轉(zhuǎn)入可執(zhí)行語句 分析模塊是否是N錯誤處理“end”?Y讀入下一個單詞嵌套深度減 1過程棧棧頂出結束7)子程序結構分析 (recurPRP)模塊開始是否是“procedure”?Y嵌套深度加 1變量個數(shù)置 1讀入下一個單詞是否是用戶N定義標示符?錯誤處理Y填過程名表讀入下一個單詞是否是“(”? NY轉(zhuǎn)入?yún)?shù)說明結構 分析模塊是否是“;”?Y讀入下一個單詞

是否Y錯誤處理有錯?N錯誤處理轉(zhuǎn)入過程結構分析模塊aa是否是“;”?N錯誤處理Y讀入下一個單詞結束8)變量說明結構分析 (recurIDP)模塊開始是否是”var”?Y讀入下一個單詞是否是用戶N錯誤處理定義標示符?Y填變量名表讀入下一個單詞aa是否是”,”? NY讀入下一個單詞是否是用戶定義標示符?Y填變量名表讀入下一個單詞是否是”;”?Y填過程名表當前項的變量總讀入下一個單詞結束9)參數(shù)說明結構分析 (recurPARL)模塊開始是否是”var”?Y讀入下一個單詞

N錯誤處理錯誤處理aa是否是用戶N錯誤處理定義標示符?Y填變量名表讀入下一個單詞是否是”,”? NY讀入下一個單詞是否是用戶定義標示符?Y填變量名表讀入下一個單詞是否是”)”?Y填過程名表當前項的參數(shù)個讀入下一個單詞

N錯誤處理N錯誤處理結束10)錯誤情況分析針對每一條產(chǎn)生式，分析可能遇到的語法錯誤。以下都是對讀到緩沖區(qū)中的單詞進行判斷。以下分析說明中要顯示的內(nèi)容放在一單獨的文件中，在初始化時讀入已事先設定好的內(nèi)存區(qū)中(字符數(shù)組)，需顯示錯誤信息時按錯誤號(下標索引)顯示即可。相關的錯誤處理操作加到以上五個遞歸分析模塊流程圖的錯誤處理部分。(1)PROG→programident；PP.不是“program”，顯示“缺少program”，跳到下一個var或procedure或begin；不是用戶定義標示符，顯示“非法主程序名”，跳到下一個var或procedure或begin；不是“;”,顯示“缺少;”，跳到下一個var或procedure或begin；是“.”，但下一單詞不是結束標志，顯示“程序結束,無效語句”，并刪除剩余二元式；不是“.”，下一單詞是結束標志，顯示“缺少.”；下一單詞不是結束標志，顯示“程序結束，無效語句”，并刪除剩余二元式.(2)PP→[IDP]{PRP}beginPLend不是var，也不是procedure或begin，顯示“缺少var”，跳到下一個procedure或begin;不是procedure，也不是begin，顯示“缺少procedure”，跳到下一個begin；不是begin，顯示“缺少begin”；不是begin，顯示“缺少begin”，跳到下一個procedure或begin.(3)PRP→procedureident[PARL]；PP；只要進入這條產(chǎn)生式的遞歸分析，必定有procedure；不是用戶定義標示符，若是“(”貨“;”,顯示“缺少過程名”，否則顯示“非法過程名”，跳到下一個var或procedure或begin；不是“(”，也不是“;”，顯示“缺少(”，跳到下一個var或procedure或begin；不是“;”，顯示“缺少;”，跳到下一個var或procedure或begin；不是“;”(最后一個)，顯示“缺少(”，跳到下一個procedure或begin.(4)IDP→varident{,ident}；只要進入這條產(chǎn)生式的遞歸分析，必定有var；不是用戶定義標示符，否則顯示“非法變量名”，跳到下一個procedure或begin；不是“;”，顯示“缺少;”，跳到下一個procedure或begin.(5)PARL→(ident{,ident})只要進入這條產(chǎn)生式的遞歸分析,必定有“(”；不是用戶定義標示符，否則顯示“非法變量名”，跳到下一個var或procedure或begin；不是“)”,顯示“缺少)”，跳到下一個var或procedure或begin.第五章 LR分析器詳細設計5.1設計思想用LR分析法對mini-pascal語言的可執(zhí)行部分進行語法分析，在分析過程中加上適當?shù)恼Z義處理，就可以實現(xiàn)“邊分析，邊翻譯”，當一條語句分析完也同時生成符合此語句語義的四元式代碼。為了便于進行語義處理，將可執(zhí)行語句的產(chǎn)生式做適當修改，其文法如下：0：PL→L2：L→S4：S→beginLend6：S→CS8：S→WdS10：S→callident(PART)12：S→read(I)14：C→ifLEthen16：Wd→WLEdo18：F3→F2untilEXP20：F1→forident:=EXP22：PART→TT24：I→I,ID26：ID→ident28：E→E+E30：E→E*E32：E→-E34：E→ident36：LE→EXPROPEXP38：ROP→<>40：ROP→>=42：ROP→<=

1：L→LSS3：LS→L5：S→ident:=EXP7：S→TpS9：S→F3doS11：S→callident13：S→write(I)15：Tp→CSelse17：W→while19：F2→F1stepEXP21：PART→PART,TT23：TT→EXP25：I→ID27：EXP→E29：E→E-E31：E→E/E33：E→(E)35：E→const37：ROP→=39：ROP→>41：ROP→<這是二義文法，而不是LR文法，但對其中具有二義性的部分加上適當?shù)南拗茥l件就可以用LR分析法進行分析了。5.2數(shù)據(jù)結構ACTION 表的存放詳見：附錄 1SA數(shù)組GOTO表的存放詳見：附錄 2GL數(shù)組PL數(shù)組：下標表示產(chǎn)生式編號（為與講義協(xié)調(diào)，數(shù)組第一個元素不使用），內(nèi)容表示此產(chǎn)生式右部長度。AL二維數(shù)組：第一列表示產(chǎn)生式編號（為與講義協(xié)調(diào)，數(shù)組第一個元素不使用），第二列存放此產(chǎn)生式左部符號名稱。全局變量：DuatypeWORD; //讀入的單詞符號，用于 LR分析stack<int>clusterSta; //狀態(tài)棧stack<char*>signSta; //符號棧boolisTrue; //若置為false，不再產(chǎn)生四元式。char*signCache[5]; //保留規(guī)約時從符號棧彈出的字符5.3程序流程圖詞法分析器初始化模塊A取當前狀態(tài)讀入一個二元式是是換行符？ 行計數(shù)器+1B查SA數(shù)組，確定動作(act)出錯，調(diào)出錯處理程序 LR分析結束 狀態(tài)，符號分別入棧 取歸約產(chǎn)生式編號 (-act)跳過出錯語句取產(chǎn)生式右部長度(len)結束出錯語句相關內(nèi)容出棧Alen個狀態(tài)，符號分別出棧，同時保存出棧符號。取產(chǎn)生式左部名稱B查GL數(shù)組，確定下一狀態(tài)下一狀態(tài)，左部名稱分別入棧調(diào)用語義處理模塊A第六章語義分析器詳細設計6.1設計思想在語法制導翻譯過程中，一條語句語法分析結束時就應生成與此語句功能等效的中間代碼。中間代碼采用四元式形式：操作碼：第一操作數(shù)，第二操作數(shù)，目的操作數(shù)與mini-pascal語言有關的四元式操作碼如下：編碼四元式操作碼注解0a一元負1add加2sub減3mul乘4div除5become賦值6call調(diào)用過程（第四元中給出此過程中間代碼的首址，第四元給出層差）7return返回調(diào)用段8int這是每個過程中間代碼的最開始一條指令，用以開辟數(shù)據(jù)區(qū)（第四元指出數(shù)據(jù)區(qū)的大?。鹤兞總€數(shù)+參數(shù)個數(shù)+連接數(shù)據(jù)）9stop停機10par參數(shù)11jump無條件轉(zhuǎn)移12j>大于轉(zhuǎn)13j<小于轉(zhuǎn)14j>=大于等于轉(zhuǎn)15j<=小于等于轉(zhuǎn)16j<>不等于轉(zhuǎn)17j=等于轉(zhuǎn)18read讀19readln讀并換行20write寫21writeln寫并換行22main代表主程序的第一條四元式序號（在第四元中給出）有的四元式并不將四元全部占滿，如四元式（par，-，-，A），其中第一、第二操作數(shù)空白無用。有的四元式的第一、第二操作數(shù)和目的操作數(shù)的含義也不和其名稱相符，應視其具體規(guī)定具體安排。6.2 數(shù)據(jù)結構操作數(shù)結構體：typedefstructOperand

//結構體：操作數(shù){char*name;inttype;intoffset;intrlevel;

//單詞符號名首址 (動態(tài)分配內(nèi)存//變量：0；常數(shù)：1；臨時變量：//相對數(shù)//相對層差

)

2。}Operand;四元式結構體：typedefstructQuatype

//結構體：四元式{intstrOperator;Operandopr1;Operandopr2;Operandopr3;

//操作碼（編碼代替）//第一操作數(shù)//第二操作數(shù)//第三操作數(shù)}Quatype;全局變量：QuatypeQualist[200];stack<Operand>place;stack<int>chain;stack<int>quad;stack<int>spro;queue<Operand>part;intK;intPC;intLEVEL;vtabelvtable;ptabelptable;

//四元式表，不得超過 200條四元式//變量棧//回填鏈棧//比較運算符棧//調(diào)用子過程時，將該子過程在過程表中的序號保存//參數(shù)隊列//臨時變量序號//四元式表指針//使用變量的過程層數(shù)//變量表//過程表6.3 程序流程圖LR分析器歸約產(chǎn)生式編號1,2,3,4,14 16,17,19,23,24,25,27,33 5 6,7 8,9

其它10 見后無語義動作，返 取變量名回true查變量表否返回false 變量存在？是該變量為第三操作數(shù)取place棧頂元素為第一操作數(shù)第二操作數(shù)不使用生成操作碼為5的四元式

取chain棧頂元 取chain棧頂元素為回填四元式 素為回填四元式將PC值賦予四元式 該四元式序號為目的操作數(shù)（回填） 第三操作數(shù)第一、二操返回true作數(shù)不使用生成操作碼為 11的四元式將PC值賦予四元式目的操作數(shù)（回填）返回true

取過程名查過程表返回false過程存在？ 否是第一、二操作數(shù)不使用part隊列空？否取part對列首元素為第三操作數(shù)生成操作碼為 10的四元式返回true

取調(diào)用過程相對層差為第一操作數(shù)取調(diào)用過程四元式首址為第三操作數(shù)生成操作碼為 6的四元式返回true歸約產(chǎn)生式編號其它1112,131518見后取過程名第一、二操取chain棧頂元取place棧頂元素作數(shù)不使用素為回填四元式為第二操作數(shù)查過程表將PC+1賦予四元式取place棧頂元素part隊列空？目的操作數(shù)（回填）為第三操作數(shù)過程存在？否是取part對列首元是第一、二、三操取place棧頂元素作數(shù)不使用為第一操作數(shù)素為第三操作數(shù)該變量為第三操作數(shù)生成操作碼為11生成操作碼為18將第三操作數(shù)壓回的四元式place棧（20）的四元式取place棧頂元素為第一操作數(shù)返回true第三操作返回true數(shù)不使用第二操作數(shù)不使用將PC值壓入chain棧，需要回填生成操作碼為 5的四元式生成操作碼為17的四元式返回true取place棧頂元素返回false為第二操作數(shù)令第三操作數(shù)等于第一操作數(shù)生成操作碼為1的四元式返回true歸約產(chǎn)生式編號2021,222628,2930,31取變量名取place棧頂元素取變量名取place棧頂元素為第二操作數(shù)查變量表將其壓入part隊列查變量表取place棧頂元素返回true為第一操作數(shù)否變量存在？變量存在？否申請臨時變量是是第二操作數(shù)將該變量壓入該臨時變量為不使用part隊列第三操作數(shù)取調(diào)用過程相對層差返回true為第一操作數(shù)將第三操作數(shù)壓入place棧返回false取調(diào)用過程四元式首生成四元式，操作址為第三操作數(shù)碼為：產(chǎn)生式編號-27生成操作碼為6的四元式返回true將第三操作數(shù)壓入place棧返回true返回false

其它見后歸約產(chǎn)生式編號323435取place棧頂元取變量名取常數(shù)串素為第一操作數(shù)查變量表將其轉(zhuǎn)化第二操作數(shù)為整數(shù)不使用變量存在？申請臨時變量否是將該整數(shù)壓入將該變量壓入place棧該臨時變量為第place棧三操作數(shù)返回true將第三操作數(shù)壓返回true入place棧返回false生成操作碼為0的四元式返回true

36將PC值壓入chain棧，需要回填取place棧頂元素為第二操作數(shù)取place棧頂元素為第二操作數(shù)取quad棧頂元素為操作碼第三操作數(shù)不使用生成四元式返回true

其它見后將與當前比較運算符相反的操作碼壓入quad棧返回true第七章 測試7.1測試概述軟件測試的目標什么是測試?它的目標是什么?下面給出一些關于測試的規(guī)則，這些規(guī)則也可看作是測試的目標或定義。測試是為了發(fā)現(xiàn)程序中的錯誤而執(zhí)行程序的過程；好的測試方案是極可能發(fā)現(xiàn)迄今為止尚未發(fā)現(xiàn)的錯誤的測試方案；成功的測試是發(fā)現(xiàn)了至今為止尚未發(fā)現(xiàn)的錯誤的測試。從上述規(guī)則可以看出，測試的正確定義是“為了發(fā)現(xiàn)程序中的錯誤而執(zhí)行程序的過程”。這和某些人通常想象的“測試是為了表明程序是正確的”，“成功的測試是沒有發(fā)現(xiàn)錯誤的測試”等等是完全相反的。正確認識測試的目標是十分重要的，測試目標決定了測試方案的設計。如果為了表明程序是正確的而進行測試，就會設計一些不易暴露錯誤的測試方案；相反，如果測試是為了發(fā)現(xiàn)程序中的錯誤，就會力求設計出最能暴露錯誤的測試方案。軟件測試準則怎樣才能達到軟件測試的目標呢?為了能設計出有效的測試方案，必須深入理解并正確運用指導軟件測試的基本準則。下面講述主要的測試標準。所有測試都應該能追溯到用戶需求。正如上一小節(jié)所講，軟件測試的目標是發(fā)現(xiàn)錯誤。從用戶角度看，最嚴重的的錯誤是導致程序不能滿足用戶需求的那些錯誤。應該遠在測試開始之前就制定出測試計劃。實際上，一旦完成了需求模型就可以著手制定測試計劃，在建立了設計模型之后就可以立即開始設計詳細的測試方案。因此，在編碼之前就可以對所有測試工作進行計劃和設計。(3)把Pareto原理應用到軟件測試中。Pareto原理說明，測試發(fā)現(xiàn)的錯誤中的80%很可能是由程序中20%的模塊造成的。當然，問題是怎樣找出這些可疑的模塊并徹底地測試它們。(4)應該從“小規(guī)?！睖y試開始，并逐步進行“大規(guī)?！睖y試。通常，首先重點測試單個程序模塊，然后把測試重點轉(zhuǎn)向在集成的模塊簇中尋找錯誤，最后在整個系統(tǒng)中尋找錯誤。窮舉測試是不可能的。所謂窮舉測試就是把程序中所有可能的執(zhí)行路徑都檢查一遍的測試.即使一個中等規(guī)模的程序，其執(zhí)行路徑的排列數(shù)也十分龐大，由于受時間、人力和資源的限制，在測試過程中不可能執(zhí)行每個可能的路徑。因此，測試只能證明程序中有錯誤，不能證明程序中沒有錯誤。但是，精心地設計測試方案，有可能充分覆蓋程序邏輯并使程序達到所要求的可靠性。為了達到最佳的測試效果，應該由獨立的第三方從事測試工作。測試方法測試任何產(chǎn)品都有兩種方法：如果已經(jīng)知道了產(chǎn)品應該具有的功能，則可以通過測試來檢驗是否每個功能都能正常使用；如果知道產(chǎn)品的內(nèi)部工作過程，可以通過測試來檢驗產(chǎn)品內(nèi)部動作是否按照規(guī)格說明書的規(guī)定正常進行。前一種方法稱為黑盒測試，后一種方法稱為白盒測試。對于軟件測試而言，黑盒測試法把程序看作是一個黑盒子，完全不考慮程序內(nèi)部結構和處理過程。也就是說，黑盒測試是在程序接口進行的測試，它只檢查程序功能是否按照規(guī)格說明書的規(guī)定正常使用，程序是否能適當?shù)慕邮茌斎霐?shù)據(jù)并產(chǎn)生正確的輸出信息，程序運行過程中能否保持外部信息的完整性。黑盒測試又稱功能測試。白盒測試與黑盒測試相反，它的前提是可以把程序看成裝在一個透明的白盒子里，測試者完全知道程序的結構和處理算法。這種方法按照程序內(nèi)部的邏輯測試程序，檢測程序中的主要執(zhí)行通路是否都能按預定要求正確工作。白盒測試又稱結構測試。測試步驟除非是測試一個小程序，否則一開始就把整個系統(tǒng)作為一個單獨的實體來測試是不現(xiàn)實的。根據(jù)第4條測試準則，測試過程也必須分步驟進行，后一個步驟在邏輯上是前一個步驟的繼續(xù)。大型軟件系統(tǒng)通常由若干個子系統(tǒng)組成，每個子系統(tǒng)有由許多某塊組成，因此，大型軟件系統(tǒng)的測試過程基本上由下述幾個步驟組成。模塊測試在設計得好的軟件系統(tǒng)中，每個模塊完成一個清晰定義的子功能，而且這個子功能和同級其它模塊的功能之間沒有互相依賴關系。因此，有可能把每個模塊作為一個單獨的實體來測試，而且通常比較容易設計檢驗模塊正確性的測試方案。模塊測試的目的是保證每個模塊作為一個單元能正確運行，所以模塊測試通常又稱為單元測試。在這個測試步驟中所發(fā)現(xiàn)的往往編碼和詳細設計的錯誤。子系統(tǒng)測試子系統(tǒng)測試是把經(jīng)過單元測試的模塊放在一起形成一個子系統(tǒng)來測試。模塊相互間的協(xié)調(diào)和通信是這個測試過程中的主要問題，因此，這個步驟著重測試模塊的接口。系統(tǒng)測試系統(tǒng)測試是把經(jīng)過測試的子系統(tǒng)裝配成一個完整的系統(tǒng)來測試。在這個過程中不僅應該發(fā)現(xiàn)設計和編碼的錯誤，還應該驗證系統(tǒng)確實能提供需求說明書中指定的功能，而且系統(tǒng)的動態(tài)特性也符合預定要求。在這個測試步驟中發(fā)現(xiàn)的往往是軟件設計中的錯誤。不論是子系統(tǒng)測試還是系統(tǒng)測試，都兼有檢測和組裝兩重含義，通常稱為集成測試。驗收測試驗收測試把軟件系統(tǒng)作為單一的實體進行測試，測試內(nèi)容與系統(tǒng)測試基本類似，但是它是在用戶積極參與下進行的，而且可能主要使用實際數(shù)據(jù)進行測試。驗收測試的目的是驗證系統(tǒng)確實能夠滿足用戶的需要，在這個測試步驟中發(fā)現(xiàn)的往往是系統(tǒng)需求說明書中的錯誤。驗收測試也稱為確認測試。平行運行關系重大的軟件產(chǎn)品在驗收之后往往不立即投入生產(chǎn)性運行，而是要再經(jīng)過一段平行運行時間的考驗。所謂平行運行就是同時運行新開發(fā)出來的系統(tǒng)和將被它取代的舊系統(tǒng)，以便比較新舊兩個系統(tǒng)的處理結果.這樣做的具體目的有以下幾點：可以在準生產(chǎn)環(huán)境中運行新系統(tǒng)而又不冒風險；用戶能有一段熟悉新系統(tǒng)的時間；可以驗證用戶指南和使用手冊之類的文檔；能夠以準生產(chǎn)模式對新系統(tǒng)進行全負荷測試，可以用測試結果驗證性能指標。7.2測試策略若采用自上而下的測試方法，需加入很多的存根程序；而且由于各自模塊功能之間不完全獨立，所以采用自下而上漸增式方法，把模塊測試和集成測試同時進行。對于每一步所要檢測的目標模塊，采用白盒測試法，考慮流程圖中的所有可能分支；對于該步中所用到的其它模塊，必為已測試完的模塊，直接調(diào)用，看其處理結果是否對目標模塊的測試結果產(chǎn)生影響，即用黑盒測試法再次進行檢測。7.3測試過程按照分工，個人負責各自子系統(tǒng)的測試。詞法分析器的測試1.測試打開文件模塊 (isFile)測試目的:檢測源文件能否正確打開。驅(qū)動程序:intflag;charch;flag=isFile();while(flag==0)flag=isFile();ch=getc(sfp);while(ch!=EOF){putchar(ch);ch=fgetc(sfp);}預期結果:文件內(nèi)容2.測試預輸入模塊(BeforehandInput)測試目的:檢測預輸入模塊是否按要求對源文件做預處理，包括把大寫字母轉(zhuǎn)化為小寫，制表符轉(zhuǎn)化為空格符，合并連續(xù)空格，文件結束符轉(zhuǎn)化為 NULL。驅(qū)動程序:intflag,flagbuffer,i;flag=isFile();while(flag==0)flag=isFile();flagbuffer=BeforehandInput(buffer);//把文件內(nèi)容讀到緩沖區(qū)buffer中while(!flagbuffer){for(i=0;i<50;i++)printf("%c",buffer[i]);printf("\n");flagbuffer=BeforehandInput(buffer);}for(i=0;i<50;i++){printf("%c",buffer[i]);if(buffer[i]=='\0')break;}測試數(shù)據(jù):programmain;var w,t;PROCEDUREaddition(x,y);varz;beginend.預期結果:programmain;varw,t;procedureaddition(x,y);vaz;beginend.3.測試初始化模塊(initilize)和插入二元式鏈表模塊 (insert)測試目的:檢測源文件能否正確打開。驅(qū)動程序:Duatype*p;initilize();strcpy(strToken,"program");Insert();//新生成一二元式結點,內(nèi)容為strToken值,插入鏈表中strcpy(strToken,"var");Insert();for(p=Dualist.head->next;p!=NULL;p=p->next){printf("%s\n",p->value);}預期結果:programvar4.詞法分析模塊(WordAnalyser)測試目的:檢測能否按流程圖分析出正確的單詞符號。驅(qū)動程序

:intflagbuffer=false; //判斷源文件是否讀完標志charstrIndex[10];Duatype*p;initilize();while