編譯原理畢業(yè)課程設(shè)計

1、( 此文檔為 word 格式，下載后您可任意編輯修改！)編譯原理課程設(shè)計課程名稱編譯原理學生學院計算機學院專業(yè)班級計算機科學與技術(shù)10（ 8）學生姓名武小亮指導教師楊勁濤2012 年 1月 2日編譯原理課程設(shè)計報告一、設(shè)計要求：基本內(nèi)容 （成績范圍：“中”、“及格”或“不及格” ）1（ 1）擴充賦值運算：*= 和 =擴充語句（ Pascal 的 FOR 語句） : FOR < 變量 >:=<表達式 > TO < 表達式 > DO < 語句> FOR < 變量 >:=< 表達式 > DOWNTO < 表達式 >

2、DO < 語句 >其中，語句 的循環(huán)變量的步長為2，語句 的循環(huán)變量的步長為-2。（ 3）增加運算：+ 和 -。選做內(nèi)容 （成績評定范圍擴大到： “優(yōu)”和“良”）（ 1）增加類型：字符類型； 實數(shù)類型。（ 2）擴充函數(shù)：有返回值和返回語句；有參數(shù)函數(shù)。（ 3）增加一維數(shù)組類型（可增加指令） 。（ 4）其他典型語言設(shè)施。二、課程設(shè)計中完成的內(nèi)容有：（ 1）擴充賦值運算：*= 和 =(2)擴充語句（ Pascal的 FOR 語句） : FOR < 變量 >:=<表達式 > TO < 表達式 > DO < 語句> FOR < 變量 &

3、gt;:=< 表達式 > DOWNTO < 表達式 > DO < 語句 >其中，語句 的循環(huán)變量的步長為2，語句 的循環(huán)變量的步長為-2。（ 3）增加運算：+ 和 - 。三、實驗環(huán)境與工具：（1）計算機及操作系統(tǒng)：PC 機， WindowsXP（ 2）程序設(shè)計語言：VC+ 6.0（ 3）教學型編譯程序：PL0四、設(shè)計方案：1、結(jié)構(gòu)說明 :PL0 語言編譯過程采用一趟掃描方式 ,以語法分析程序為核心 ,詞法分析程序和代碼生成程序都作為一個獨立的過程 ,當語法分析需要讀單詞時就調(diào)用詞法分析程序 ,而當語法分析正確需生成相應(yīng)的目標代碼時 ,則調(diào)用代碼生成程序 .此

4、外 ,用表格管理程序建立變量、常量和過程標識符的說明與引用之間的信息聯(lián)系.用出錯處理程序?qū)υ~法和語法分析研究遇到的錯誤給出在源程序中出錯的位置和錯誤性質(zhì) .當源程序編譯正確時,PL0 編譯程序自動調(diào)用解釋執(zhí)行,并按用戶程序要求輸入數(shù)據(jù)和輸出運行結(jié)果.2、流程圖：2編譯和解釋執(zhí)行的結(jié)構(gòu)圖PL0 編譯程序總體流程圖3、詞法分析詞法分析是編譯的第一個階段， 它的主要任務(wù)是從左向右逐個字符地對源程序進行掃描，產(chǎn)生一個個單詞序列用于語法分析。 PL0 詞法分析程序 GETSYM的功能是為語法分析提供單詞用的，是語法分析的基礎(chǔ)，把輸入的字符串形式的源程序分割成一個個單詞符號。經(jīng)過詞法分析程序分析出來的單詞

5、，對語言固有的單詞只給出類別存放在全程變量 SYM中，而對用戶定義的單詞（標識符或常數(shù)）既給出類別又給值，其類別放在 SYM中，值放在全程變量 ID 或全程變量NUM中，全部單詞種類由編譯程序定義的純量類型 SYMBOL給出，稱為語法詞匯表。詞法分析器的分析過程：調(diào)用 GETSYM時，它通過 GETCH過程從源程序中獲得一個字符。如果這個字符是字母，則繼續(xù)獲取字符或數(shù)字，最終可以拼成一個單詞，查保留字表，如果查到為保留字，則把SYM變量賦成相應(yīng)的保留字類型值；如果沒有查到，則這個單詞應(yīng)是一個用戶自定義的標識符（可能是變量名、常量名或是過程的名字） ，把 SYM置為 IDENT，把這個單詞存入I

6、D 變量。查保留字表時使用了二分法查找以提高效率。如果Getch 獲得的字符是數(shù)字，則繼續(xù)用Getch 獲取數(shù)字，并把它們拼成一個整數(shù)或?qū)崝?shù)，然后把SYM 置為INTEGER，并把拼成的數(shù)值放入NUM變量。如果識別出其它合法的符號（比如：賦值號、大于號、小于等于號等） ，則把 SYM則成相應(yīng)的類型。如果遇到不合法的字符，把 SYM置成 NUL。詞法分析程序 GETSYM將完成下列任務(wù)：（1）濾空格（2）識別保留字（3）識別標識符（4）拼數(shù)（5）拼復(fù)合詞（6）輸出源程序34、語法分析PL0 編譯程序的語法分析采用了自頂向下的遞歸的子程序法。 語法分析同時也根據(jù)程序的語義生成相應(yīng)三元代碼，并提供了

7、出錯處理的機制。語法分析主要由分程序分析過程（ BLOCK）、常量定義分析過程（ ConstDeclaration ）、變量定義分析過程（ Vardeclaration ）、語句分析過程（ Statement ）、表達式處理過程（ Expression ）、項處理過程（ Term）、因子處理過程（ Factor ）和條件處理過程（ Condition ）構(gòu)成。這些過程在結(jié)構(gòu)上構(gòu)成一個嵌套的層次結(jié)構(gòu)。除此之外，還有出錯報告過程（ Error ）、代碼生成過程（ Gen）、測試單詞合法性及出錯恢復(fù)過程（ Test ）、登錄名字表過程（ Enter ）、查詢名字表函數(shù)（ Position ）以及列出

8、類 PCODE代碼過程（ Listcode ）作過語法分析的輔助過程。由 PL0 的語法圖可知：一個完整的 PL0 程序是由分程序和句號構(gòu)成的。因此，本編譯程序在運行的時候，通過主程序中調(diào)用分程序處理過程block 來分析分程序部分（分程序分析過程中還可能會遞歸調(diào)用 block 過程），然后，判斷最后讀入的符號是否為句號。如果是句號且分程序分析中未出錯，則是一個合法的 PL0 程序，可以運行生成的代碼，否則就說明源 PL0 程序是不合法的，輸出出錯提示即可。45、語義分析PL0 的語義分析主要進行以下檢查：（1） 是否存在標識符先引用未聲明的情況；5（2） 是否存在己聲明的標識符的錯誤引用；（

9、3） 是否存在一般標識符的多重聲明。6、語法錯誤處理PL0 編譯程序?qū)φZ法錯誤的處理采用兩種辦法：（1）對于一些易于校正的錯誤，如丟了逗號、分號等，指出出錯的位置，加以校正，繼續(xù)進行分析。（2）對于難于校正的錯誤，給出錯誤的位置與性質(zhì)，跳過后面一些單詞，直到下一個可以進行正常語法分析的語法單位。7、解釋執(zhí)行這個過程模擬了一臺可以運行類 PCODE指令的棧式計算機。解釋程序過程中的 base 函數(shù)的功能，就是用于沿著靜態(tài)鏈，向前查找相差指定層數(shù)的局部數(shù)據(jù)段基址。這在使用 sto 、lod 等訪問局部變量的指令中會經(jīng)常用到。類 PCODE 代碼解釋執(zhí)行的部分通過循環(huán)和簡單的 case 判斷不同的指

10、令，做出相應(yīng)的動作。當遇到主程序中的返回指令時，指令指針會指到 0 位置，把這樣一個條件作為終至循環(huán)的條件，保證程序運行可以正常的結(jié)束。生產(chǎn)目標代碼后，程序調(diào)用Interpret程序解釋執(zhí)行，程序定義的一個數(shù)據(jù)區(qū) S，三個寄存器 T 棧頂寄存器， B 基址寄存器和 P 程序地址寄存器用于運行程序。五、各功能模塊描述:過程或函數(shù)名簡要功能說明P10主程序error出錯處理getsym詞法分析 , 讀取一個單詞Getch漏掉空格 , 讀取一個字符Gen生成目標代碼 , 并送入目標程序區(qū)Test測試當前單詞符號是否合法Block分程序分析處理過程Enter登錄名字表Position查找標識符在名字表

11、中的位置Constdeclaration常量定義處理Vardeclaration變量說明處理Listcode列出目標代碼清單6Statement語句部分處理Expression表達式處理Term項處理Factor因子處理Condition條件處理Interpret對目標代碼的解釋執(zhí)行程序Base( 函數(shù) )通過靜態(tài)鏈求出數(shù)據(jù)區(qū)的基地址主要成分描述1、符號表struct ALFA NAME;OBJECTS KIND;union int VAL; *CONSTANT*struct int LEVEL,ADR,SIZE; vp; *VARIABLE,PROCEDUR:*; TABLETXMAX;所有

12、符號都放在全程量一維數(shù)組TABLE 表中。 TX 為索引表的指針，表中的每個元素為記錄型數(shù)據(jù)。LEV 給出層次， DX 給出每層局部量當前已分配到的相對位置。且TABLE表的表頭索引TX 和層次單元LEV 都以 BLOCK 的參數(shù)形式出現(xiàn)。每個過程中的變量的相對初始位置在BLOCK 內(nèi)置初值DX ： =3。結(jié)構(gòu)形式如下：NAMEKINDVALLEVELADRSIZE在編譯程序中符號表用來存放語言程序中出現(xiàn)的有關(guān)標識符的屬性信息, 這些信息集中反映了標識符的語義特征屬性. 符號表的主要功能如下:1、收集符號屬性2、上下文語義合法性檢查的依據(jù)3、作為目標代碼生成階段地址分配的依據(jù).2、運行時存儲組

13、織和管理由于編譯時目標程序運行的數(shù)據(jù)空間大小已經(jīng)規(guī)定，所以存儲組織屬于靜態(tài)存儲。源程序的標識符存放在TABLE 表中，目標代碼存放在CODE 中， S 是由解釋程序定義的一維整型數(shù)組，是程序運行時的數(shù)據(jù)存儲空間。解釋程序還定義了4 個寄存器：1）P：程序地址寄存器：指向下一條要執(zhí)行的目標程序的地址（相當目標程序CODE數(shù)組的下標）。2） I ：指令寄存器：存放著當前正在解釋的下一條目標指令。3）T ：棧頂寄存器：由于每個過程當它被運行時，給它分配的數(shù)據(jù)空間（下邊稱數(shù)據(jù)7段）包括靜態(tài)部分和動態(tài)部分，對于動態(tài)部分，要注意的是，棧頂寄存器指出了當前棧中最新分配的單元。4）B：基址寄存器： 指向每個過

14、程被調(diào)用時， 在數(shù)據(jù)區(qū) S 中給它分配的數(shù)據(jù)段的起始地址，也稱基地址。3、語法分析方法自頂向下的語法分析 :<程序 ><分程序>.<變量說明部分 ><語句 >VAR <標識符 >； < 復(fù)合語句 >ABEGIN <語句 > END<讀語句 >READ（<標識符>）A4、中間代碼表示PL0 編譯程序所產(chǎn)生的目標代碼是一個假想棧式計算機的匯編語言，可稱為類PCODE指令代碼，它不依賴任何實際計算機，中間代碼生成是由過程GEN 完成， GEN 有 3 個參數(shù)，分別代表目標代碼的功能碼，層差和位

15、移量其指令集極為簡單，指令格式也很單純，其格式如下：FLA例如： gen(opr,0,16); gen(sto,lev-level,adr)lev：當前處理的過程層次level：被引用變量或過程所在層次CX ：為目標代碼code 數(shù)組的下標指針其中F 為功能號； L 為層次差，也就是變量或過程被引用的分程序與說明該變量的過程之間的層次差； A 的含義對不同指令有所區(qū)別，對存取指令表示位移，而對其它指令則分別有不同含義，解析說明如下： LIT ：將常量取到棧頂。L 為常數(shù)類型；A 為常數(shù)值。 LOD ：將變量放到棧頂。A 為變量在說明層中的相對位置，L 為調(diào)用說明層的差值。 STO ：將棧頂?shù)膬?nèi)

16、容送入某變量單元中。A、 L 含義如上。 CAL ：過程調(diào)用指令。A 為被調(diào)用過程的目標程序入口地址，L 為層差。 INT ：為被調(diào)用過程在運行棧中開辟數(shù)據(jù)區(qū)，A 為開辟的單元數(shù)。8 JMP ：無條件跳轉(zhuǎn)指令，A 為轉(zhuǎn)向地址。 JPC ：條件跳轉(zhuǎn)指令，當棧頂?shù)闹禐榧贂r，轉(zhuǎn)向A ，否則順序執(zhí)行。 OPR ： opr 的 L 域為 0， A 域的內(nèi)容決定操作含義，具體說明如下：A=0 過程調(diào)用結(jié)束后返回調(diào)用點，并釋放被調(diào)用過程在運行棧的數(shù)據(jù)空間。 A=1 棧頂值取反，結(jié)果在棧頂。A=2 次棧頂與棧頂相加，退兩個棧元素，結(jié)果值進棧。 A=3 次棧頂減去棧頂，退兩個棧元素，結(jié)果值進棧。 A=4 次棧頂

17、乘以棧頂，退兩個棧元素，結(jié)果值進棧。 A=5 次棧頂除以棧頂，退兩個棧元素，結(jié)果值進棧。A=6 對棧頂值做奇偶判斷，奇數(shù)為真，偶數(shù)為假，結(jié)果放棧頂。 A=8 次棧頂與棧頂是否相等，退兩個棧元素，結(jié)果值進棧。 A=9 次棧頂與棧頂是否不等，退兩個棧元素，結(jié)果值進棧。 A=10 次棧頂是否小于棧頂，退兩個棧元素，結(jié)果值進棧。 A=11 次棧頂是否大于等于棧頂，退兩個棧元素，結(jié)果值進棧。A=12 次棧頂是否大于棧頂，退兩個棧元素，結(jié)果值進棧。A=13 次棧頂是否小于等于棧頂，退兩個棧元素，結(jié)果值進棧。A= 14棧頂值輸出到屏幕。A=15屏幕輸出換行。A=16從命令行讀入一個輸入到棧頂。A 為其他值均

18、為非法指令。六、設(shè)計實現(xiàn)：（1）增加賦值運算符 *= 和 =以及 +,-(a)首先給這四個運算符命名， 分別命為 timeseql,slasheql ，和 pps,mms以便讀單詞時填寫符號表。分析 *= 、 =、+、- ，當遇到 +時，根據(jù) TABLE表中的 C 地址把 C 的值放在棧頂，再把棧頂元素和次棧頂元素相加，然后保存 C 的值。 - 的原理與 +相同。（ b）在 PL0 程序中的修改如下：詞法分析GetSym 中添加， 語句分析STATEMENT中添加， expression將執(zhí)行一系列指令，但最終結(jié)果將會保存在棧頂，執(zhí)行sto 命令完成賦值 *1). 詞法分析中修改else 下面

19、部分為較書本的版本增加的功能if(ch='+') 讀到 +號，判斷是否是 +getchdo;if(ch='+')sym=pps; +getchdo;else9sym=plus;單個 +elseif(ch='-')讀到 -號，判斷是否是 -getchdo;if(ch='-')sym=mms; -getchdo;elsesym=minus;單獨 -elseif(ch='*')讀到 * 號，判斷是否是 *=getchdo;if(ch='=')sym=timeseql; *=getchdo;elsesym=

20、times; 單獨 *elseif(ch='')讀到號，判斷是否是 =getchdo;if(ch='=')10sym=slasheql; =getchdo;elsesym=slash; 單獨2) 語句分析STATEMENT中添加else if(sym=slasheql)檢測到符號i=position(id,*ptx);把類 x*=3 的 x的地址取出來gendo(lod,lev-tablei.level,tablei.adr);* 找到變量地址并將其值入棧 *getsymdo;if(sym=semicolon)getsymdo;memcpy(nxtlev,fsy

21、s,sizeof(bool)* symnum);expressiondo(nxtlev,ptx,lev);gendo(opr,0,5);if(i!=0)gendo(sto,lev-tablei.level,tablei.adr);else if(sym=pps)檢測到后置 +符號gendo(lit,0,1);gendo(lod,lev-tablei.level,tablei.adr);* 找到變量地址并將其值入棧 *gendo(opr,0,2);執(zhí)行加操作，if(i!=0)gendo(sto,lev-tablei.level,tablei.adr);getsymdo;11else if(sym

22、=mms)檢測到后置 -符號gendo(lod,lev-tablei.level,tablei.adr);* 找到變量地址并將其值入棧 *gendo(lit,0,1);gendo(opr,0,3);執(zhí)行減操作，if(i!=0)gendo(sto,lev-tablei.level,tablei.adr);getsymdo;elseerror(13);if(i!=0)gendo(sto,lev-tablei.level,tablei.adr);（ 2）擴充語句（ Pascal的 FOR 語句） : FOR <變量 >:=<表達式 > TO < 表達式 > DO

23、<語句> FOR < 變量 >:=< 表達式 > DOWNTO < 表達式 > DO < 語句 >（a）增加保留字 FOR、TO、DOWNTO、DO到相應(yīng)的位置，用于詞法分析的識別(b) 其跳轉(zhuǎn)圖為12)在 statement 中添加，類似 else 的方式，主要是處理好如何出入棧的問題，代碼中有詳細的注釋。elseif(sym=forsym)準備按照for 語句處理getsymdo;if(sym=ident)i=position(id,*ptx);if(i=0) error(11);elseif(tablei.kind!=varia

24、ble)賦值語句中，賦值號左部標識符屬性應(yīng)是變量error(12);i=0;elsegetsymdo;if(sym!=becomes)error(13);賦值語句左部標識符后應(yīng)是賦值號:=else getsymdo;memcpy(nxtlev,fsys,sizeof(bool)*symnum);nxtlevtosym=true;后跟符 to 和 downtonxtlevdowntosym=true;expressiondo(nxtlev,ptx,lev);處理賦值語句右部的表達式E1gendo(sto,lev-tablei.level,tablei.adr);保存初值switch(sym)13

25、case tosym:步長為的向上增加getsymdo;cx1=cx;保存循環(huán)開始點將循環(huán)判斷變量取出放到棧頂gendo(lod,lev-tablei.level,tablei.adr);memcpy(nxtlev,fsys,sizeof(bool)*symnum);處理表達式E2nxtlevdosym=true;后跟符 doexpressiondo(nxtlev,ptx,lev);*判斷循環(huán)變量條件，比如for i:=E1 to E2 do S 中，判斷 i 是否小于E2 ，如小于等于，繼續(xù)循環(huán)，大于的話，跳出循環(huán)*gendo(opr,0,13);生成比較指令，i 是否小于等于E2 的值cx

26、2=cx;保存循環(huán)結(jié)束點生成條件跳轉(zhuǎn)指令， 跳出循環(huán)，跳出的地址未知gendo(jpc,0,0);if(sym=dosym)處理循環(huán)體Sgetsymdo;statement(fsys,ptx,lev);循環(huán)體處理增加循環(huán)變量步長為將循環(huán)變量取出放在棧頂gendo(lod,lev-tablei.level,tablei.adr);gendo(lit,0,2);將步長取到棧頂gendo(opr,0,2);循環(huán)變量加步長將棧頂?shù)闹荡嫒胙h(huán)變量14gendo(sto,lev-tablei.level,tablei.adr);gendo(jmp,0,cx1);無條件跳轉(zhuǎn)到循環(huán)開始點* 回填循環(huán)結(jié)束點的地

27、址， cx 為 else后語句執(zhí)行完的位置，它正是前面未定的跳轉(zhuǎn)地址*codecx2.a=cx;elseerror(29);for語句中少了dobreak;casedowntosym:步長為的向下減少getsymdo;cx1=cx;保存循環(huán)開始點將循環(huán)判斷變量取出放到棧頂gendo(lod,lev-tablei.level,tablei.adr);memcpy(nxtlev,fsys,sizeof(bool)*symnum);處理表達式E2nxtlevdosym=true;后跟符 doexpressiondo(nxtlev,ptx,lev);*判斷循環(huán)變量條件，比如 for i:=E1 downto E2 do S 中，判斷 i 是否大于等于E2 ，如大于等于，繼續(xù)循環(huán)，小于的話，跳出循環(huán)*gendo(opr,0,11);生成比較指令，i 是否大于等于E2 的值cx2=cx;保存循環(huán)結(jié)束點生成條件跳轉(zhuǎn)指令， 跳出循環(huán)，跳出的地址未知gendo(jpc,0,0);i