編譯原理實驗報告(PL0語言功能擴充)

1、編譯原理課程實驗報告題目 PL/0編譯程序的C語言擴充專業(yè) 化學(xué)工程與工藝班級 學(xué)號姓名 任課教師 華東理工大學(xué)信息學(xué)院一實驗題目PL/0編譯程序的C語言擴充二實驗?zāi)康脑诜治隼斫釶L/0編譯程序的基礎(chǔ)上，對其詞法分析程序、語法分析程序和語義處理程序進行部分修改擴充。三實驗內(nèi)容在PL/0語言的基礎(chǔ)上增加對整型一維數(shù)組的支持、擴充IF-THEN-ELSE條件語句、增加REPEAT語句、支持帶參數(shù)的過程和增加注釋等，如下所示：(1) 整型一維數(shù)組，數(shù)組的定義格式為：VAR<數(shù)組標(biāo)識名>(<下界>:<上界>)其中上界和下界可以是整數(shù)或者常量標(biāo)識名。訪問數(shù)組元素的時候

2、，數(shù)組下表是整型的表達式，包括整數(shù)、常量或者變量和他們的組合。(2) 擴充條件語句，格式為：<條件語句> := EF<條件>THEN<語句> ELSE<語句>(3)增加REPEAT語句，格式為：<復(fù)合語句> := REPEAT<語句>UNTL<條件>四實驗過程（1）PL/0編譯程序的C語言源代碼輸入（2）運行PL/0編譯程序的C語言源代碼，調(diào)試運行PL/0編譯程序（3）對PL/0編譯程序進行功能擴充（4）PL/0編譯程序功能擴充部分的分析與設(shè)計（5）對PL/0編譯程序進行

3、功能擴充，即編寫代碼（6）進行PL/0編譯程序功能擴充部分的運行調(diào)試（7）完成實驗報告總結(jié)五PL/0編譯程序的功能擴充程序說明（1）擴充賦值運算:+=,-=.此功能擴充只需在語句分析里面進行增加如下程序： if(SYM=BECOMES|SYM=PLUSBECOMES|SYM=MINUSBECOMES) if (SYM=BECOMES) GetSym(); EXPRESSION(FSYS,LEV,TX); else if(SYM=PLUSBECOMES|SYM=MINUSBECOMES) GEN(LOD,LEV-TABLEi.vp.LEVEL,TABLEi.vp.ADR); if(SYM=PLU

4、SBECOMES) GetSym(); FACTOR(FSYS,LEV,TX); GEN(OPR,0,2); else if(SYM=MINUSBECOMES) GetSym(); FACTOR(FSYS,LEV,TX); GEN(OPR,0,3); if (i!=0) GEN(STO,LEV-TABLEi.vp.LEVEL,TABLEi.vp.ADR); （2）擴充FOR TO和FOR DOWNTO語句,此功能的關(guān)鍵是如何判斷條件是否成立,并如何進行程序跳轉(zhuǎn).在這里用到了幾條指令,和地址回填技術(shù).擴充程序如下: case FORSYM: GetSym(); if(SYM!=IDENT)Err

5、or(31); /FOR后面要標(biāo)識符 i=POSITION(ID,TX);if (i=0) Error(11);else if (TABLEi.KIND!=VARIABLE) /*ASSIGNMENT TO NON-VARIABLE*/ Error(12); /變量 GetSym(); if(SYM!=BECOMES) Error(13); GetSym(); EXPRESSION(SymSetUnion(SymSetNew(TOSYM,DOWNTOSYM,DOSYM),FSYS),LEV,TX);/表達式 if(SYM=DOWNTOSYM) CX1=CX; GetSym(); GEN(STO

6、,LEV-TABLEi.vp.LEVEL,TABLEi.vp.ADR);/保存結(jié)果至變量單元 GEN(LOD,LEV-TABLEi.vp.LEVEL,TABLEi.vp.ADR);/重新調(diào)入棧頂 EXPRESSION(SymSetAdd(DOSYM,FSYS),LEV,TX);/表達式 GEN(OPR,0,11);/判斷運算 CX2=CX; GEN(JPC,0,0);/如果棧頂非真跳轉(zhuǎn) GEN(LOD,LEV-TABLEi.vp.LEVEL,TABLEi.vp.ADR);/重新調(diào)入棧頂 GEN(LIT,0,1) ;/送1到棧頂 GEN(OPR,0,3); /減運算 if(SYM=DOSYM)

7、GetSym(); STATEMENT(FSYS,LEV,TX); GEN(JMP,0,CX1); CODECX2.A=CX; else if(SYM=TOSYM) CX1=CX;GetSym(); GEN(STO,LEV-TABLEi.vp.LEVEL,TABLEi.vp.ADR); /保存結(jié)果至變量單元 GEN(LOD,LEV-TABLEi.vp.LEVEL,TABLEi.vp.ADR); /重新調(diào)入棧頂 EXPRESSION(SymSetAdd(DOSYM,FSYS),LEV,TX);/表達式分析 GEN(OPR,0,13);/判斷運算 CX2=CX; GEN(JPC,0,0);/如果棧

8、頂非真跳轉(zhuǎn) GEN(LOD,LEV-TABLEi.vp.LEVEL,TABLEi.vp.ADR); GEN(LIT,0,1); GEN(OPR,0,2); if(SYM=DOSYM) GetSym(); STATEMENT(FSYS,LEV,TX); GEN(JMP,0,CX1); CODECX2.A=CX;/回填地址 else Error(35); break;(3) 增加條件語句的ELSE子ELSE語句的語法語義分析程序：case IFSYM:GetSym();CONDITION(SymSetUnion(SymSetNew(THENSYM,DOSYM),FSYS),LEV,TX);if (

9、SYM=THENSYM) GetSym(); else Error(16);CX1=CX; GEN(JPC,0,0);STATEMENT(FSYS,LEV,TX); CX2=CX; GEN(JMP,0,CX+1); CODECX1.A=CX; if (SYM=SEMICOLON) GetSym(); if(SYM=ELSESYM) GetSym(); STATEMENT(FSYS,LEV,TX); CODECX2.A=CX; /add the statement of ELSE else STATEMENT(FSYS,LEV,TX);break;（4）修改單詞：不等號# 改為 <>

10、 if (CH='<') GetCh(); if (CH='=') SYM=LEQ; GetCh(); else if(CH='>') SYM=NEQ; GetCh(); else SYM=LSS;六實驗設(shè)計思想1設(shè)計說明PL/0語言是Pascal語言的一個子集，這里分析的PL/0的編譯程序包括了對PL/0語言源程序進行分析處理、編譯生成類PCODE代碼，并在虛擬機上解釋運行生成的類PCODE代碼的功能。PL/0語言編譯程序采用以語法分析為核心、一遍掃描的編譯方法。詞法分析和代碼生成作為獨立的子程序供語法分析程序調(diào)用。語法分析的同時，

11、提供了出錯報告和出錯恢復(fù)的功能。在源程序沒有錯誤編譯通過的情況下，調(diào)用類PCODE解釋程序解釋執(zhí)行生成的類PCODE代碼。2各功能模塊描述詞法分析子程序分析：詞法分析子程序名為GETSYM，功能是從源程序中讀出一個單詞符號（TOTAKEN），把它的信息放入全局變量 SYM、ID和NUM中，字符變量放入CH中，語法分析器需要單詞時，直接從這三個變量中獲得。Getch過程通過反復(fù)調(diào)用Getch子過程從源程序過獲取字符，并把它們拼成單詞。GETCH過程中使用了行緩沖區(qū)技術(shù)以提高程序運行效率。詞法分析器的分析過程：調(diào)用GETSYM時，它通過GETCH過程從源程序中獲得一個字符。如果這個字符是字母，則繼

12、續(xù)獲取字符或數(shù)字，最終可以拼成一個單詞，查保留字表，如果查到為保留字，則把SYM變量賦成相應(yīng)的保留字類型值；如果沒有查到，則這個單詞應(yīng)是一個用戶自定義的標(biāo)識符（可能是變量名、常量名或是過程的名字），把SYM置為IDENT，把這個單詞存入ID變量。查保留字表時使用了二分法查找以提高效率。如果Getch獲得的字符是數(shù)字，則繼續(xù)用Getch獲取數(shù)字，并把它們拼成一個整數(shù)或?qū)崝?shù)，然后把SYM置為 INTEGER或REAL，并把拼成的數(shù)值放入NUM變量。如果識別出其它合法的符號（比如：賦值號、大于號、小于等于號等），則把SYM則成相應(yīng)的類型。如果遇到不合法的字符，把SYM置成NUL。語法分析子程序分析：

13、語法分析子程序采用了自頂向下的遞歸子程序法，語法分析同時也根據(jù)程序的語義生成相應(yīng)三元代碼，并提供了出錯處理的機制。語法分析主要由分程序分析過程（BLOCK）、參數(shù)變量分析過程（ParaDeclaration）、參數(shù)變量處理過程（ParaGetSub）、數(shù)組處理過程（ParaGetSub）、常量定義分析過程（ConstDeclaration）、變量定義分析過程（Vardeclaration）、語句分析過程（Statement）、表達式處理過程（Expression）、項處理過程（Term）、因子處理過程（Factor）和條件處理過程（Condition）構(gòu)成。這些過程在結(jié)構(gòu)上構(gòu)成一個嵌套的層次結(jié)

14、構(gòu)。除此之外，還有出錯報告過程（Error）、代碼生成過程（Gen）、測試單詞合法性及出錯恢復(fù)過程（Test）、登錄名字表過程（Enter）、查詢名字表函數(shù)（Position）以及列出類 PCODE代碼過程（Listcode）作過語法分析的輔助過程。由PL/0的語法圖可知：一個完整的PL/0程序是由分程序和句號構(gòu)成的。因此，本編譯程序在運行的時候，通過主程序中調(diào)用分程序處理過程block來分析分程序部分（分程序分析過程中還可能會遞歸調(diào)用block過程），然后，判斷最后讀入的符號是否為句號。如果是句號且分程序分析中未出錯，則是一個合法的PL/0程序，可以運行生成的代碼，否則就說明源PL/0程序是

15、不合法的，輸出出錯提示即可。下面按各語法單元分析PL/0編譯程序的運行機制。分程序處理過程：語法分析開始后，首先調(diào)用分程序處理過程（Block）處理分程序。過程入口參數(shù)置為：0層、符號表位置0、出錯恢復(fù)單詞集合為句號、聲明符或語句開始符。進入Block過程后，首先把局部數(shù)據(jù)段分配指針設(shè)為3，準(zhǔn)備分配3個單元供運行期存放靜態(tài)鏈SL、動態(tài)鏈DL 和返回地址RA。然后用Tx0記錄下當(dāng)前符號表位置并產(chǎn)生一條Jmp指令，準(zhǔn)備跳轉(zhuǎn)到主程序的開始位置，由于當(dāng)前還沒有知到主程序究竟在何處開始，所以Jmp的目標(biāo)暫時填為0，稍后再改。同時在符號表的當(dāng)前位置記錄下這個Jmp指令在代碼段中的位置。在判斷了嵌套層數(shù)沒有

16、超過規(guī)定的層數(shù)后，開始分析源程序。首先判斷是否遇到了常量聲明，如果遇到則開始常量定義，把常量存入符號表。接下去用同樣的方法分析變量聲明，變量定義過程中會用Dx變量記錄下局部數(shù)據(jù)段分配的空間個數(shù)。然后如果遇到Procedure保留字則進行過程聲明和定義，聲明的方法是把過程的名字和所在的層次記入符號表，過程定義的方法就是通過遞歸調(diào)用Block過程，因為每個過程都是一個分程序。由于這是分程序中的分程序，因此調(diào)用Block時需把當(dāng)前的層次號Lev加一傳遞給Block 過程。分程序聲明部分完成后，即將進入語句的處理，這時的代碼分配指針CX的值正好指向語句的開始位置，這個位置正是前面的Jmp指令需要跳轉(zhuǎn)到

17、的位置。于是通過前面記錄下來的地址值，把這個Jmp指令的跳轉(zhuǎn)位置改成當(dāng)前cx的位置。并在符號表中記錄下當(dāng)前的代碼段分配地址和局部數(shù)據(jù)段要分配的大?。―X 的值）。生成一條INT指令，分配DX個空間，作為這個分程序段的第一條指令。下面就調(diào)用語句處理過程Statement分析語句。分析完成后，生成操作數(shù)為0的OPR指令，用于從分程序返回（對于0層的主程序來說，就是程序運行完成，退出）。常量定義過程：通過循環(huán)，反復(fù)獲得標(biāo)識符和對應(yīng)的值，存入符號表。符號表中記錄下標(biāo)識符的名字和它對應(yīng)的值。變量定義過程：與常量定義類似，通過循環(huán)，反復(fù)獲得標(biāo)識符，存入符號表。符號表中記錄下標(biāo)識符的名字、它所在的層及它在所

18、在層中的偏移地址。參變量定義過程：類似變量定義，將參變量，存入符號表中。參變量處理過程：如果函數(shù)用參變量，依照形參的類型、個數(shù)，由實參進行賦值。數(shù)組處理過程：計算數(shù)組括號內(nèi)的偏移值，存入棧頂用于后面生成的STOARR和LODARR指令調(diào)用實際的數(shù)組中元素的地址。語句處理過程：語句處理過程是一個嵌套子程序，通過調(diào)用表達式處理、項處理、因子處理等過程及遞歸調(diào)用自己來實現(xiàn)對語句的分析。語句處理過程可以識別的語句包括賦值語句、read語句、write語句、+語句、-語句、+=語句、-=語句、if-else-then語句、while語句、For語句、repeat語句。當(dāng)遇到begin/end語句時，就遞

19、歸調(diào)用自己來分析。分析的同時生成相應(yīng)的類PCODE指令。賦值語句的處理：首先獲取賦值號左邊的標(biāo)識符，從符號表中找到它的信息，并確認(rèn)這個標(biāo)識符確為變量名。然后通過調(diào)用表達式處理過程算得賦值號右部的表達式的值并生成相應(yīng)的指令保證這個值放在運行期的數(shù)據(jù)棧頂。最后通過前面查到的左部變量的位置信息，生成相應(yīng)的STO指令，把棧頂值存入指定的變量的空間，實現(xiàn)了賦值操作。返回函數(shù)值也是用賦值語句進行返回值的儲存。對函數(shù)與過程調(diào)用的處理：首先判斷讀入的標(biāo)識符屬性為FUNCTION或PROCEDURE，從符號表中找到此標(biāo)識符，獲得其所在層次和偏移地址。然后生成相應(yīng)的cal指令。至于調(diào)用子過程所需的保護現(xiàn)場等工作是

20、由類PCODE解釋程序在解釋執(zhí)行cal指令時自動完成的。如果此標(biāo)識符不在第0層而且是該層函數(shù)的函數(shù)名則作為返回值返回。read語句的處理：確定read語句語法合理的前提下（否則報錯），由變量的類型生成相應(yīng)的指令：對于整型，第一條是16號操作的opr指令，實現(xiàn)從標(biāo)準(zhǔn)輸入設(shè)備上讀一個整數(shù)值，放在數(shù)據(jù)棧頂。如果讀入是實數(shù)就報錯，第二條是sto指令，把棧頂?shù)闹荡嫒雛ead語句括號中的變量所在的單元。對于實型，第一條是15號操作的opr指令，實現(xiàn)從標(biāo)準(zhǔn)輸入設(shè)備上讀一個實數(shù)值，放在數(shù)據(jù)棧頂。第二條是sto指令，把棧頂?shù)闹荡嫒雛ead語句括號中的變量所在的單元。對于字符型，第一條是20號操作的opr指令，實

21、現(xiàn)從標(biāo)準(zhǔn)輸入設(shè)備上讀一個字符值，第二條是sto指令，把棧頂?shù)闹荡嫒雛ead語句括號中的變量所在的單元。write語句的處理：與read語句相似。在語法正確的前提下，生成指令：通過循環(huán)調(diào)用表達式處理過程分析write語句括號中的每一個表達式，生成相應(yīng)指令保證把表達式的值算出并放到數(shù)據(jù)棧頂并生成指令，輸出表達式的值，如果是數(shù)字類型則生成14號操作的opr指令，如果是字符類型則生成19號操作的opr指令。if-then-else語句的處理：按if語句的語法，首先調(diào)用邏輯表達式處理過程處理if語句的條件，把相應(yīng)的真假值放到數(shù)據(jù)棧頂。接下去記錄下代碼段分配位置（即下面生成的jpc指令的位置），然后生成條

22、件轉(zhuǎn)移jpc指令（遇0或遇假轉(zhuǎn)移），轉(zhuǎn)移地址未知暫時填0。然后調(diào)用語句處理過程處理 then語句后面的語句或語句塊。then后的語句處理完后，如果遇到else，就調(diào)用語句處理過程處理else語句后面的語句或語句塊，這時當(dāng)前代碼段分配指針的位置就應(yīng)該是上面的jpc指令的轉(zhuǎn)移位置。通過前面記錄下的jpc指令的位置，把它的跳轉(zhuǎn)位置改成當(dāng)前的代碼段指針位置，否則沒遇到else，那么此時的當(dāng)前代碼段分配指針的位置也是上面jpc指令的轉(zhuǎn)移位置，也是通過前面記錄下的jpc位置指令的位置，把它的跳轉(zhuǎn)到當(dāng)前的代碼段指針位置。begin/end語句的處理：通過循環(huán)遍歷begin/end語句塊中的每一個語句，通過遞

23、歸調(diào)用語句分析過程分析并生成相應(yīng)代碼。while語句的處理：首先用cx1變量記下當(dāng)前代碼段分配位置，作為循環(huán)的開始位置。然后處理while語句中的條件表達式生成相應(yīng)代碼把結(jié)果放在數(shù)據(jù)棧頂，再用cx2變量記下當(dāng)前位置，生成條件轉(zhuǎn)移指令，轉(zhuǎn)移位置未知，填0。通過遞歸調(diào)用語句分析過程分析do語句后的語句或語句塊并生成相應(yīng)代碼。最后生成一條無條件跳轉(zhuǎn)指令jmp，跳轉(zhuǎn)到cx1所指位置，并把cx2所指的條件跳轉(zhuǎn)指令的跳轉(zhuǎn)位置改成當(dāng)前代碼段分配位置。Repeat語句的處理：首先用CX1變量記下當(dāng)前代碼段分配位置，作為循環(huán)的開始位置。然后通過遞歸調(diào)用語句分析過程分析，直到遇到until保留字，如果未對應(yīng)unt

24、il則出錯。調(diào)用條件表達式處理過程生成相應(yīng)代碼把結(jié)果放在數(shù)據(jù)棧頂，再生成條件轉(zhuǎn)移指令，轉(zhuǎn)移位置為上面記錄的CX1。For語句的處理：按For語句的語法，首先對For后面的一個標(biāo)識符進行初值的賦值過程（類似賦值語句處理），生成相應(yīng)的代碼。之后遇到TO或DOWNTO保留字，如果未對應(yīng)則出錯。用CX1變量記下當(dāng)前代碼段分配的位置，作為以后JMP循環(huán)的開始位置。對上面識別的標(biāo)識符變量進行存取，與TO或DOWNTO后面的表達式進行比較，生成比較指令（TO為13、DOWNTO為11），再用CX2變量記下當(dāng)前代碼段分配的位置，生成JPC指令，跳轉(zhuǎn)地址未知，之后可用CX2記錄下的位置進行回填。然后處理DO保留

25、字后的循環(huán)體，第一步遞歸調(diào)用語句分析過程，第二步將原先For后的標(biāo)識符變量進行自加處理，生成相應(yīng)代碼，然后生成無條件跳轉(zhuǎn)語句JMP跳轉(zhuǎn)代碼為CX1。最后將此時的代碼段位置回填到JPC跳轉(zhuǎn)指令上。表達式、項、因子處理：根據(jù)PL/0語法可知，表達式應(yīng)該是由正負(fù)號或無符號開頭、由若干個項以加減號連接而成。而項是由若干個因子以乘除號，mod、div符號或+、-符號連接而成，因子則可能是一個標(biāo)識符或一個數(shù)字，或是一個以括號括起來的子表達式。根據(jù)這樣的結(jié)構(gòu)，構(gòu)造出相應(yīng)的過程，遞歸調(diào)用就完成了表達式的處理。把項和因子獨立開處理解決了加減號與乘除號的優(yōu)先級問題。在這幾個過程的反復(fù)調(diào)用中，始終傳遞fsys變量的

26、值，保證可以在出錯的情況下跳過出錯的符號，使分析過程得以進行下去。邏輯表達式的處理：首先判斷是否為一元邏輯表達式：判奇偶。如果是，則通過調(diào)用表達式處理過程分析計算表達式的值，然后生成判奇指令。如果不是，則肯定是二元邏輯運算符，通過調(diào)用表達式處理過程依次分析運算符左右兩部分的值，放在棧頂?shù)膬蓚€空間中，然后依不同的邏輯運算符，生成相應(yīng)的邏輯判斷指令，放入代碼段。判斷單詞合法性與出錯恢復(fù)過程分析：本過程有三個參數(shù)，s1、s2為兩個符號集合，n為出錯代碼。本過程的功能是：測試當(dāng)前符號（即sym變量中的值）是否在s1集合中，如果不在，就通過調(diào)用出錯報告過程輸出出錯代碼n，并放棄當(dāng)前符號，通過詞法分析過程

27、獲取一下單詞，直到這個單詞出現(xiàn)在s1或s2集合中為止。這個過程在實際使用中很靈活，主要有兩個用法：在進入某個語法單位時，調(diào)用本過程，檢查當(dāng)前符號是否屬于該語法單位的開始符號集合。若不屬于，則濾去開始符號和后繼符號集合外的所有符號。在語法單位分析結(jié)束時，調(diào)用本過程，檢查當(dāng)前符號是否屬于調(diào)用該語法單位時應(yīng)有的后繼符號集合。若不屬于，則濾去后繼符號和開始符號集合外的所有符號。通過這樣的機制，可以在源程序出現(xiàn)錯誤時，及時跳過出錯的部分，保證語法分析可以繼續(xù)下去。語法分析過程中調(diào)用的其它子過程相對比較簡單，請參考源程序的注釋。類PCODE代碼解釋執(zhí)行過程分析：這個過程模擬了一臺可以運行類PCODE指令的棧式計算機。它擁有一個棧式數(shù)據(jù)段用于存放運行期數(shù)據(jù)、擁有一個代碼段用于存放類PCODE程序代碼。同時還擁用數(shù)據(jù)段分配指針、指令指針、指令寄存器、局部段基址指針等寄存器。解釋執(zhí)行類PCODE代碼時，數(shù)據(jù)段存儲分配方式如下：對于源程序的每一個過程（包括主程序），在被調(diào)用時，首先在數(shù)據(jù)段中開辟三個空間，存放靜態(tài)鏈SL、動態(tài)鏈DL和返回地址RA。靜態(tài)鏈記錄了定義該過程的直接外過程（或主程序）運行時最新數(shù)據(jù)段的基地址。動態(tài)鏈記錄調(diào)用該過程前正在運行的過程的數(shù)據(jù)段基址。返回地址記錄了調(diào)用該過程時程序運行的斷點位置。對于主程序來說，SL