11級編譯原理課程設(shè)計

1、編譯原理課程設(shè)計學(xué) 院_計算機_專 業(yè)_計算機科學(xué)與技術(shù)_年級班別_11_（8）_班_學(xué) 號_3111006033_學(xué)生姓名_李杰_指導(dǎo)教師_劉添添_ 成 績 20 14 年 1 月 2日 一課程設(shè)計目的在分析理解一個教學(xué)型編譯程序（如PL/0）的基礎(chǔ)上，對其詞法分析程序、語法分析程序和語義處理程序進行部分修改擴充。達到進一步了解程序編譯過程的基本原理和基本實現(xiàn)方法的目的。二課程設(shè)計要求1.基本內(nèi)容（1）擴充賦值運算：*= 和 /=（2）擴充語句 （Pascal的FOR語句）:FOR <變量>:=<表達式> TO <表達式> DO <語句>FOR

2、 <變量>:=<表達式> DOWNTO <表達式> DO <語句> 其中，語句的循環(huán)變量的步長為2，語句的循環(huán)變量的步長為-2。2.選做內(nèi)容（1）增加類型： 字符類型； 實數(shù)類型。（2）擴充函數(shù)： 有返回值和返回語句； 有參數(shù)函數(shù)。（3）增加一維數(shù)組類型（可增加指令）。（4）其他典型語言設(shè)施。3.本人在課程設(shè)計中已實現(xiàn)的功能（1）擴充賦值運算：*= 和 /=（2）擴充語句 （Pascal的FOR語句）:FOR <變量>:=<表達式> TO <表達式> DO <語句>FOR <變量>:=&

3、lt;表達式> DOWNTO <表達式> DO <語句>三課程設(shè)計環(huán)境與工具（1）計算機及操作系統(tǒng)：PC機，Windows 7（2）實現(xiàn)工具：C+Builder6（3） 教學(xué)型編譯程序：PL/0 四 結(jié)構(gòu)設(shè)計說明1.PL/0編譯程序的結(jié)構(gòu)圖Pl0 源 程 序詞法分析程序語法分析程序代碼生產(chǎn)程序目 標(biāo) 程 序表 格 管 理 程 序出 錯 處 理 程 序2.PL/0編譯程序的過程或函數(shù)的功能表過程或函數(shù)名簡要功能說明pl0主程序error出錯處理，打印出錯位置和錯誤編碼getsym詞法分析，讀取一個單詞getch漏掉空格，讀取一個字符gen生成目標(biāo)代碼，并送入目標(biāo)程序

4、區(qū)test測試當(dāng)前單詞符號是否合法block分程序分析處理過程enter登錄名字表position(函數(shù))查找標(biāo)識符在名字表中的位置constdeclaration常量定義處理vardeclaration變量說明處理listode列出目標(biāo)代碼清單statement語句處理expression表達式處理term項處理factor因子處理condition條件處理interpret對目標(biāo)代碼的解釋執(zhí)行程序base(函數(shù))通過靜態(tài)鏈求出數(shù)據(jù)區(qū)的基地址3、主要成分描述1、符號表為了組成一條指令，編譯程序必須知道其操作碼及其參數(shù)（數(shù)或地址）。這些值是由編譯程序本身聯(lián)系到相應(yīng)標(biāo)識符上去的。這種聯(lián)系是在處理

5、常數(shù)、變量和過程說明完成的。為此，標(biāo)識符表應(yīng)包含每一標(biāo)識符所聯(lián)系的屬性；如果標(biāo)識符被說明為常數(shù)，其屬性值為常數(shù)值；如果標(biāo)識符被說明成變量，其屬性就是由層次和修正量（偏移量）組成的地址；如果標(biāo)識符被說明為過程，其屬性就是過程的入口地址及層次。常數(shù)的值由程序正文提供，編譯的任務(wù)就是確定存放該值的地址。我們選擇順序分配變量和代碼的方法；每遇到一個變量說明，就將數(shù)據(jù)單元的下標(biāo)加一（PL/0 機中，每個變量占一個存貯單元）。開始編譯一個過程時，要對數(shù)據(jù)單元的下標(biāo)dx 賦初值，表示新開辟一個數(shù)據(jù)區(qū)。dx 的初值為3，因為每個數(shù)據(jù)區(qū)包含三個內(nèi)部變量RA，DL 和SL。 2、運行時存儲組織和管理對于源程序的每

6、一個過程（包括主程序），在被調(diào)用時，首先在數(shù)據(jù)段中開辟三個空間，存放靜態(tài)鏈SL、動態(tài)鏈DL和返回地址RA。靜態(tài)鏈記錄了定義該過程的直接外過程（或主程序）運行時最新數(shù)據(jù)段的基地址。動態(tài)鏈記錄調(diào)用該過程前正在運行的過程的數(shù)據(jù)段基址。返回地址記錄了調(diào)用該過程時程序運行的斷點位置。對于主程序來說，SL、DL和RA的值均置為0。靜態(tài)鏈的功能是在一個子過程要引用它的直接或間接父過程（這里的父過程是按定義過程時的嵌套情況來定的，而不是按執(zhí)行時的調(diào)用順序定的）的變量時，可以通過靜態(tài)鏈，跳過個數(shù)為層差的數(shù)據(jù)段，找到包含要引用的變量所在的數(shù)據(jù)段基址，然后通過偏移地址訪問它。在過程返回時，解釋程序通過返回地址恢復(fù)指

7、令指針的值到調(diào)用前的地址，通過當(dāng)前段基址恢復(fù)數(shù)據(jù)段分配指針，通過動態(tài)鏈恢復(fù)局部段基址指針。實現(xiàn)子過程的返回。對于主程序來說，解釋程序會遇到返回地址為0的情況，這時就認(rèn)為程序運行結(jié)束。解釋程序過程中的base函數(shù)的功能，就是用于沿著靜態(tài)鏈，向前查找相差指定層數(shù)的局部數(shù)據(jù)段基址。這在使用sto、lod、stoArr、lodArr等訪問局部變量的指令中會經(jīng)常用到。類PCODE代碼解釋執(zhí)行的部分通過循環(huán)和簡單的case判斷不同的指令，做出相應(yīng)的動作。當(dāng)遇到主程序中的返回指令時，指令指針會指到0位置，把這樣一個條件作為終至循環(huán)的條件，保證程序運行可以正常的結(jié)束。 3、語法分析方法語法分析子程序采用了自頂

8、向下的遞歸子程序法，語法分析同時也根據(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é)構(gòu)。除此之外，還有出錯報

9、告過程（Error）、代碼生成過程（Gen）、測試單詞合法性及出錯恢復(fù)過程（Test）、登錄名字表過程（Enter）、查詢名字表函數(shù)（Position）以及列出類 PCODE代碼過程（Listcode）作過語法分析的輔助過程。 4、中間代碼表示中間代碼是是源程序的一種內(nèi)部表示，復(fù)雜性介于源語言和目標(biāo)機語言之間。中間代碼的表示方法有逆波蘭式、三元式、樹形、四元式等。(1) 逆波蘭記號是最簡單的一種中間代碼表示形式，早在編譯程序出現(xiàn)之前，它就用于表示算術(shù)表達式。后綴表示法表示表達式，其最大的優(yōu)點是易于棧式計算機處理表達式。(2) 每個三元式由三個部分組成：A. 算符opB. 第一運算對象ARG1C

10、. 第二運算對象ARG2運算對象可能是源程序中的變量，也可能是某個三元式的結(jié)果，用三元式的編號表示。(3) 樹形表示是三元式表示的翻版。(4) 四元式是一種比較普遍采用的中間代碼形式：算符op，運算對象ARG1，運算對象ARG2，運算結(jié)果RESULT五設(shè)計過程1.增加運算: *=和/=這兩個操作都是一種對變量進行賦值的形式，其合法的語句形式的語法圖如下所示：2.增加Pascal的FOR語句:a）格式如下：FOR <變量>:=<表達式>STEP<表達式> UNTIL<表達式>Do<語句>b）添加語句for 語句的語句語法圖如下：PL0代

11、碼修改實現(xiàn)：1、修改保留字和單詞新增4個保留字和2個運算符，合計6個單詞。故const NORW = 18; /* # OF RESERVED WORDS */修改單詞總數(shù)，i<40其中保留字ELSE，F(xiàn)OR，TO，DOWNTO 分別對應(yīng)ELSESYM , FORSYM, TOSYM, DOWNTOSYM；運算符 *= ，/= 分別對應(yīng) TIMESEQL, SLASHEQL。typedef enum NUL, IDENT, NUMBER, PLUS, MINUS, TIMES, SLASH, ODDSYM, EQL, NEQ, LSS, LEQ, GTR, GEQ, LPAREN, RP

12、AREN, COMMA, SEMICOLON, PERIOD, BECOMES, BEGINSYM, ENDSYM, IFSYM, THENSYM, WHILESYM, WRITESYM, READSYM, DOSYM, CALLSYM, CONSTSYM, VARSYM, PROCSYM, PROGSYM, STEPSYM, UNTILSYM, ELSESYM, FORSYM, RETURNSYM, TIMESEQL, SLASHEQL, ANDSYM, ORSYM, NOTSYM SYMBOL;char *SYMOUT = "NUL", "IDENT"

13、;, "NUMBER", "PLUS", "MINUS", "TIMES", "SLASH", "ODDSYM", "EQL", "NEQ", "LSS", "LEQ", "GTR", "GEQ", "LPAREN", "RPAREN", "COMMA", "SEMICOLON"

14、, "PERIOD", "BECOMES", "BEGINSYM", "ENDSYM", "IFSYM", "THENSYM", "WHILESYM", "WRITESYM", "READSYM", "DOSYM", "CALLSYM", "CONSTSYM", "VARSYM", "PROCSYM", "P

15、ROGSYM", "STEPSYM", "UNTILSYM", "ELSESYM", "FORSYM", "RETURNSYM","TIMESEQL", "SLASHEQL", "ANDSYM", "ORSYM", "NOTSYM" ; /*增加保留字，按字母順序排序*/ strcpy(KWORD 1,"BEGIN"); strcpy(KWORD 2,"CA

16、LL"); strcpy(KWORD 3,"CONST"); strcpy(KWORD 4,"DO"); strcpy(KWORD 5,"ELSE"); strcpy(KWORD 6,"END"); strcpy(KWORD 7,"FOR"); strcpy(KWORD 8,"IF"); strcpy(KWORD 9,"ODD"); strcpy(KWORD10,"PROCEDURE"); strcpy(KWORD11,&qu

17、ot;PROGRAM"); strcpy(KWORD12,"READ"); strcpy(KWORD13,"RETURN"); strcpy(KWORD14,"STEP"); strcpy(KWORD15,"THEN"); strcpy(KWORD16,"UNTIL"); strcpy(KWORD17,"VAR"); strcpy(KWORD18,"WHILE"); strcpy(KWORD19,"WRITE"); WSYM

18、1=BEGINSYM; WSYM 2=CALLSYM; WSYM 3=CONSTSYM; WSYM 4=DOSYM; WSYM 5=ELSESYM; WSYM 6=ENDSYM; WSYM 7=FORSYM; WSYM 8=IFSYM; WSYM9=ODDSYM; WSYM10=PROCSYM; WSYM11=PROGSYM; WSYM12=READSYM; WSYM13=RETURNSYM; WSYM14=STEPSYM; WSYM15=THENSYM; WSYM16=UNTILSYM; WSYM17=VARSYM; WSYM18=WHILESYM; WSYM19=WRITESYM; SSY

19、M'+'=PLUS; SSYM'-'=MINUS; SSYM'*'=TIMES; SSYM'/'=SLASH; SSYM'('=LPAREN; SSYM')'=RPAREN; SSYM'='=EQL; SSYM','=COMMA; SSYM'.'=PERIOD; SSYM''=SEMICOLON;/修改乘等else if (CH='*') GetCh(); if ('=' = CH) SYM=TIMESE

20、QL; GetCh(); else SYM=TIMES; /修改除等 else if (CH='/') GetCh(); if ('=' = CH) SYM=SLASHEQL; GetCh(); else SYM=SLASH; /修改TERM增加乘等void TERM(SYMSET FSYS, int LEV, int &TX) /*TERM*/ SYMBOL MULOP; FACTOR(SymSetUnion(FSYS,SymSetNew(TIMES,SLASH), LEV,TX); while (SYM=TIMES | SYM=SLASH | SYM

21、=TIMESEQL) MULOP=SYM; GetSym();FACTOR(SymSetUnion(FSYS,SymSetNew(TIMES,SLASH,TIMESEQL),LEV,TX); if (MULOP=TIMES) GEN(OPR,0,4);else GEN(OPR,0,5); /*TERM*/;int flag = 0; void STATEMENT(SYMSET FSYS,int LEV,int &TX) /*STATEMENT*/ int i,CX1,CX2,cs; switch (SYM) case IDENT:i=POSITION(ID,TX);if (i=0) E

22、rror(11);else if (TABLEi.KIND!=VARIABLE) /*ASSIGNMENT TO NON-VARIABLE*/Error(12); i=0; GetSym();if (SYM=BECOMES | SYM=TIMESEQL | SYM=SLASHEQL) if (SYM=TIMESEQL) GEN(LOD,LEV-TABLEi.vp.LEVEL,TABLEi.vp.ADR); flag = 1; if (SYM=SLASHBEQL) GEN(LOD,LEV-TABLEi.vp.LEVEL,TABLEi.vp.ADR); flag = 2; GetSym(); el

23、se Error(13);EXPRESSION(FSYS,LEV,TX); switch (flag) case 1: GEN(OPR,0,4);flag = 0; break; case 2: GEN(OPR,0,5);flag = 0; reak; default: flag = 0; break; if (i!=0) GEN(STO,LEV-TABLEi.vp.LEVEL,TABLEi.vp.ADR);break;/修改FORSYMcase FORSYM: GetSym(); if (SYM = IDENT) i = POSITION(ID,TX); if (0 = i) Error(1

24、1); else if (VARIABLE != TABLEi.KIND) Error(12); i = 0; cs = i; GetSym(); if (BECOMES = SYM) GetSym(); else Error(13); EXPRESSION(SymSetUnion(SymSetNew(TOSYM,DOWNTOSYM),FSYS),LEV,TX); if (0 != cs) GEN(STO,LEV-TABLEcs.vp.LEVEL,TABLEcs.vp.ADR); else Error(12); if (TOSYM = SYM) GetSym(); CX1 = CX; EXPRESSION(SymSetAdd(DOSYM,FSYS),LEV,TX); if (DOSYM = SYM) GEN(LOD,LEV-TABLEcs.vp.LEVEL,TABLEcs.vp.ADR); GEN(OPR,0,11); CX2 = CX; GEN(JPC,0,0); GetSym(); STATEMENT(SymSetUnion(SymSetNew(SEMICOLON,ENDSYM),FSYS),LEV,TX); GEN(LIT,0,2); GEN(LOD,LEV-TABLEcs.vp.LEVE