2014廣工編譯原理實(shí)驗(yàn)報(bào)告

1、實(shí) 驗(yàn) 報(bào) 告 課程名稱(chēng) 編譯原理 題目名稱(chēng) PL/0編譯器的擴(kuò)充 學(xué)生學(xué)院 計(jì)算機(jī)學(xué)院 專(zhuān)業(yè)班級(jí) 計(jì)算機(jī)科學(xué)與技術(shù)12(4)學(xué) 號(hào) 學(xué)生姓名 柏石先 指導(dǎo)教師 李楊 程序功能完成情況測(cè)試用例全面程度學(xué)生對(duì)所編程序熟悉程度報(bào)告格式是否與要求相符報(bào)告內(nèi)容是否準(zhǔn)確、全面2014 年 12 月 20日一、 實(shí)驗(yàn)?zāi)康呐c要求對(duì)PL/0作以下修改擴(kuò)充：（1） 增加單詞：保留字 ELSE，F(xiàn)OR，STEP，UNTIL，DO,RETURN運(yùn)算符 *=，/=，&，|，?。?）修改單詞：不等號(hào)# 改為 （3）增加條件語(yǔ)句的ELSE子句，要求：寫(xiě)出相關(guān)文法，語(yǔ)法描述圖，語(yǔ)義描述圖。二、 實(shí)驗(yàn)環(huán)境與工具1、源語(yǔ)言：P

2、L/0語(yǔ)言，PL/0語(yǔ)言是PASCAL語(yǔ)言的子集，它的編譯程序是一個(gè)編譯解析執(zhí)行系統(tǒng)，后綴名為.PL0；2、目標(biāo)語(yǔ)言：生成文件后綴為*.COD的目標(biāo)代碼3、實(shí)現(xiàn)平臺(tái)：Borland C+Builder 64、運(yùn)行平臺(tái)：Windows 8.1三、 設(shè)計(jì)方案1、 結(jié)構(gòu)設(shè)計(jì)說(shuō)明（1）PL/0 語(yǔ)言編譯器 PL/0語(yǔ)言可看成是PASCAL語(yǔ)言的子集，它的編譯程序是一個(gè)編譯解釋執(zhí)行系統(tǒng)。PL/0的目標(biāo)程序?yàn)榧傧霔Ｊ接?jì)算機(jī)的匯編語(yǔ)言，與具體計(jì)算機(jī)無(wú)關(guān)。出錯(cuò)處理函數(shù)表格管理函數(shù)PL/0 源程序目標(biāo)代碼生成程序程序目標(biāo)代碼生成程序程序目標(biāo)代碼生成程序程序目標(biāo)代碼生成程序程序目標(biāo)代碼生成程序程序 （2） PL/

3、0編譯程序的語(yǔ)法分析過(guò)程BLOCK是整個(gè)編譯過(guò)程的核心。這里根據(jù)編譯程序的總體流程圖，來(lái)弄清BLOCK過(guò)程在整個(gè)編譯程序中的作用。總流程圖如下圖所示：PL/0 的編譯程序采用一趟掃描方式，以語(yǔ)法分析程序?yàn)楹诵?，詞法分析程序和代碼生成程序都作為一個(gè)獨(dú)立的過(guò)程，當(dāng)語(yǔ)法分析需要讀單詞時(shí)就用詞法分析程序，而當(dāng)語(yǔ)法分析正確需生成相應(yīng)的目標(biāo)代碼時(shí)，則調(diào)用代碼生成程序。此外，用表格管理程序建立變量，常量和過(guò)程標(biāo)識(shí)符的說(shuō)明與引用之間的信息聯(lián)系。用出錯(cuò)處理程序?qū)υ~法和語(yǔ)法分析遇到的錯(cuò)誤給出在源程序中出錯(cuò)的位置和錯(cuò)誤性質(zhì)。（3） 各功能模塊描述過(guò)程或函數(shù)名簡(jiǎn)要功能說(shuō)明pl0主程序error出錯(cuò)處理，打印出錯(cuò)位置和

4、錯(cuò)誤編碼getsym詞法分析，讀取一個(gè)單詞getch漏掉空格，讀取一個(gè)字符gen生成目標(biāo)代碼，并送入目標(biāo)程序區(qū)test測(cè)試當(dāng)前單詞符號(hào)是否合法block分程序分析處理過(guò)程enter登錄名字表position(函數(shù))查找標(biāo)識(shí)符在名字表中的位置constdeclaration常量定義處理vardeclaration變量說(shuō)明處理listode列出目標(biāo)代碼清單statement語(yǔ)句處理expression表達(dá)式處理term項(xiàng)處理factor因子處理condition條件處理interpret對(duì)目標(biāo)代碼的解釋執(zhí)行程序base(函數(shù))通過(guò)靜態(tài)鏈求出數(shù)據(jù)區(qū)的基地址2、主要成分描述符號(hào)表為了組成一條指令，編譯

5、程序必須知道其操作碼及其參數(shù)（數(shù)或地址）。這些值是由編譯程序本身聯(lián)系到相應(yīng)標(biāo)識(shí)符上去的。這種聯(lián)系是在處理常數(shù)、變量和過(guò)程說(shuō)明完成的。為此，標(biāo)識(shí)符表應(yīng)包含每一標(biāo)識(shí)符所聯(lián)系的屬性；如果標(biāo)識(shí)符被說(shuō)明為常數(shù)，其屬性值為常數(shù)值；如果標(biāo)識(shí)符被說(shuō)明成變量，其屬性就是由層次和修正量（偏移量）組成的地址；如果標(biāo)識(shí)符被說(shuō)明為過(guò)程，其屬性就是過(guò)程的入口地址及層次。常數(shù)的值由程序正文提供，編譯的任務(wù)就是確定存放該值的地址。我們選擇順序分配變量和代碼的方法；每遇到一個(gè)變量說(shuō)明，就將數(shù)據(jù)單元的下標(biāo)加一（PL/0 機(jī)中，每個(gè)變量占一個(gè)存貯單元）。開(kāi)始編譯一個(gè)過(guò)程時(shí)，要對(duì)數(shù)據(jù)單元的下標(biāo)dx 賦初值，表示新開(kāi)辟一個(gè)數(shù)據(jù)區(qū)。dx

6、 的初值為3，因?yàn)槊總€(gè)數(shù)據(jù)區(qū)包含三個(gè)內(nèi)部變量RA，DL 和SL。 運(yùn)行時(shí)存儲(chǔ)組織和管理對(duì)于源程序的每一個(gè)過(guò)程（包括主程序），在被調(diào)用時(shí)，首先在數(shù)據(jù)段中開(kāi)辟三個(gè)空間，存放靜態(tài)鏈SL、動(dòng)態(tài)鏈DL和返回地址RA。靜態(tài)鏈記錄了定義該過(guò)程的直接外過(guò)程（或主程序）運(yùn)行時(shí)最新數(shù)據(jù)段的基地址。動(dòng)態(tài)鏈記錄調(diào)用該過(guò)程前正在運(yùn)行的過(guò)程的數(shù)據(jù)段基址。返回地址記錄了調(diào)用該過(guò)程時(shí)程序運(yùn)行的斷點(diǎn)位置。對(duì)于主程序來(lái)說(shuō)，SL、DL和RA的值均置為0。靜態(tài)鏈的功能是在一個(gè)子過(guò)程要引用它的直接或間接父過(guò)程（這里的父過(guò)程是按定義過(guò)程時(shí)的嵌套情況來(lái)定的，而不是按執(zhí)行時(shí)的調(diào)用順序定的）的變量時(shí)，可以通過(guò)靜態(tài)鏈，跳過(guò)個(gè)數(shù)為層差的數(shù)據(jù)段，找

7、到包含要引用的變量所在的數(shù)據(jù)段基址，然后通過(guò)偏移地址訪問(wèn)它。在過(guò)程返回時(shí)，解釋程序通過(guò)返回地址恢復(fù)指令指針的值到調(diào)用前的地址，通過(guò)當(dāng)前段基址恢復(fù)數(shù)據(jù)段分配指針，通過(guò)動(dòng)態(tài)鏈恢復(fù)局部段基址指針。實(shí)現(xiàn)子過(guò)程的返回。對(duì)于主程序來(lái)說(shuō)，解釋程序會(huì)遇到返回地址為0的情況，這時(shí)就認(rèn)為程序運(yùn)行結(jié)束。解釋程序過(guò)程中的base函數(shù)的功能，就是用于沿著靜態(tài)鏈，向前查找相差指定層數(shù)的局部數(shù)據(jù)段基址。這在使用sto、lod、stoArr、lodArr等訪問(wèn)局部變量的指令中會(huì)經(jīng)常用到。類(lèi)PCODE代碼解釋執(zhí)行的部分通過(guò)循環(huán)和簡(jiǎn)單的case判斷不同的指令，做出相應(yīng)的動(dòng)作。當(dāng)遇到主程序中的返回指令時(shí)，指令指針會(huì)指到0位置，把這

8、樣一個(gè)條件作為終至循環(huán)的條件，保證程序運(yùn)行可以正常的結(jié)束。 語(yǔ)法分析方法語(yǔ)法分析子程序采用了自頂向下的遞歸子程序法，語(yǔ)法分析同時(shí)也根據(jù)程序的語(yǔ)義生成相應(yīng)三元代碼，并提供了出錯(cuò)處理的機(jī)制。語(yǔ)法分析主要由分程序分析過(guò)程（BLOCK）、參數(shù)變量分析過(guò)程（ParaDeclaration）、參數(shù)變量處理過(guò)程（ParaGetSub）、數(shù)組處理過(guò)程（ParaGetSub）、常量定義分析過(guò)程（ConstDeclaration）、變量定義分析過(guò)程（Vardeclaration）、語(yǔ)句分析過(guò)程（Statement）、表達(dá)式處理過(guò)程（Expression）、項(xiàng)處理過(guò)程（Term）、因子處理過(guò)程（Factor）和條件

9、處理過(guò)程（Condition）構(gòu)成。這些過(guò)程在結(jié)構(gòu)上構(gòu)成一個(gè)嵌套的層次結(jié)構(gòu)。除此之外，還有出錯(cuò)報(bào)告過(guò)程（Error）、代碼生成過(guò)程（Gen）、測(cè)試單詞合法性及出錯(cuò)恢復(fù)過(guò)程（Test）、登錄名字表過(guò)程（Enter）、查詢名字表函數(shù)（Position）以及列出類(lèi) PCODE代碼過(guò)程（Listcode）作過(guò)語(yǔ)法分析的輔助過(guò)程。 中間代碼表示中間代碼是是源程序的一種內(nèi)部表示，復(fù)雜性介于源語(yǔ)言和目標(biāo)機(jī)語(yǔ)言之間。中間代碼的表示方法有逆波蘭式、三元式、樹(shù)形、四元式等。(1) 逆波蘭記號(hào)是最簡(jiǎn)單的一種中間代碼表示形式，早在編譯程序出現(xiàn)之前，它就用于表示算術(shù)表達(dá)式。后綴表示法表示表達(dá)式，其最大的優(yōu)點(diǎn)是易于棧式計(jì)

10、算機(jī)處理表達(dá)式。(2) 每個(gè)三元式由三個(gè)部分組成：A. 算符opB. 第一運(yùn)算對(duì)象ARG1C. 第二運(yùn)算對(duì)象ARG2運(yùn)算對(duì)象可能是源程序中的變量，也可能是某個(gè)三元式的結(jié)果，用三元式的編號(hào)表示。(3) 樹(shù)形表示是三元式表示的翻版。(4) 四元式是一種比較普遍采用的中間代碼形式：算符op，運(yùn)算對(duì)象ARG1，運(yùn)算對(duì)象ARG2，運(yùn)算結(jié)果RESULT四、 開(kāi)發(fā)過(guò)程和完成情況（一）增加單詞：保留字 ELSE，F(xiàn)OR，STEP，UNTIL，DO , RETURN運(yùn)算符 *=，/=，&，|，！新增6個(gè)保留字和5個(gè)運(yùn)算符，合計(jì)11個(gè)單詞。其中保留字ELSE，F(xiàn)OR，STEP，UNTIL，DO, RETURN 分

11、別對(duì)應(yīng)ELSESYM,FORSYM, STEPSYM, UNTILSYM,DOSYM,RETURNSYM；運(yùn)算符 *= ，/= ，& ，| ， ！ 分別對(duì)應(yīng) TIMESBECOMES, SLASHBECOMES, ANDSYM, ORSYM, NOTSYM。注：要求只做詞法分析部分，不做語(yǔ)義分析處理，實(shí)驗(yàn)的結(jié)果只是識(shí)別新增的保留字和運(yùn)算符，并且將其打印顯示出來(lái)。1.1保留字typedef enum NUL, IDENT, NUMBER, PLUS, MINUS, TIMES, SLASH, ODDSYM, EQL, NEQ, LSS, LEQ, GTR, GEQ, LPAREN, RPAREN

12、, COMMA, SEMICOLON, PERIOD, BECOMES, BEGINSYM, ENDSYM, IFSYM, THENSYM, WHILESYM, WRITESYM, READSYM, DOSYM, CALLSYM, CONSTSYM, VARSYM, PROCSYM, PROGSYM, ELSESYM, FORSYM, STEPSYM, STEPSYM, RETURNSYM, TIMESBECOMES, SLASHBECOMES, ANDSYM, ORSYM, NOTSYM SYMBOL;char *SYMOUT = NUL, IDENT, NUMBER, PLUS, MINU

13、S, TIMES, SLASH, ODDSYM, EQL, NEQ, LSS, LEQ, GTR, GEQ, LPAREN, RPAREN, COMMA, SEMICOLON, PERIOD, BECOMES, BEGINSYM, ENDSYM, IFSYM, THENSYM, WHILESYM, WRITESYM, READSYM, DOSYM, CALLSYM, CONSTSYM, VARSYM, PROCSYM, PROGSYM, ELSESYM, FORSYM, STEPSYM, STEPSYM, RETURNSYM, TIMESBECOMES, SLASHBECOMES, ANDSY

14、M, ORSYM, NOTSYM ;strcpy(KWORD 1,BEGIN); strcpy(KWORD 2,CALL); 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(KWORD 10,PROCEDURE); strcpy(KWORD 11,PROGRAM); strcpy(KWORD12,READ); strcpy(KWORD1

15、3,RETURN); strcpy(KWORD14,STEP); strcpy(KWORD15,THEN); strcpy(KWORD16,UNTIL); strcpy(KWORD17,VAR); strcpy(KWORD18,WHILE); strcpy(KWORD19,WRITE); WSYM 1=BEGINSYM; WSYM 2=CALLSYM; WSYM 3=CONSTSYM; WSYM 4=DOSYM; WSYM 5=ELSESYM; /*增加保留字符號(hào)elsesym*/ WSYM 6=ENDSYM; WSYM 7=FORSYM; WSYM 8=IFSYM; WSYM 9=ODDSY

16、M; WSYM 10=PROCSYM; WSYM 11=PROGSYM; WSYM12=READSYM; WSYM13=RETURNSYM; WSYM14=STEPSYM; WSYM15=THENSYM; WSYM16=UNTILSYM; WSYM17=VARSYM; WSYM18=WHILESYM; WSYM19=WRITESYM; SSYM+=PLUS; SSYM-=MINUS; SSYM*=TIMES; SSYM/=SLASH; SSYM(=LPAREN; SSYM)=RPAREN; SSYM=EQL; SSYM,=COMMA; SSYM.=PERIOD; SSYM;=SEMICOLON

17、; SSYM&=ANDSYM; SSYM!=NOTSYM;在void STATEMENT(SYMSET FSYS,int LEV,int &TX)函數(shù)中增加：case FORSYM: GetSym(); Form1-printfs(保留字：FORSYM); break;case STEPSYM: GetSym(); Form1-printfs(保留字：STEPSYM); break;case UNTILSYM: GetSym(); Form1-printfs(保留字：UNTILSYM); break;case RETURNSYM: GetSym(); Form1-printfs(保留字：RET

18、URNSYM); break;case DOSYM: GetSym(); Form1-printfs(保留字：DOSYM); break; 1.2運(yùn)算符1.2.1在GetSym()函數(shù)中在相應(yīng)位置增加下面所示的語(yǔ)句：else if (CH=:) GetCh();if (CH=) SYM=BECOMES; GetCh(); else SYM=NUL; else if(CH = *) GetCh(); if(CH = =) SYM = TIMESBECOMES; GetCh(); else SYM=SSYM*; else if(CH = /) GetCh(); if(CH = =) SYM = S

19、LASHBECOMES; GetCh(); else SYM=SSYM/; else /* THE FOLLOWING TWO CHECK WERE ADDED BECAUSE ASCII DOES NOT HAVE A SINGLE CHARACTER FOR = */ if (CH=) SYM=NEQ; GetCh(); /不等號(hào)加 else SYM=LSS;else if (CH=) GetCh(); if (CH=) SYM=GEQ; GetCh(); else SYM=GTR; else if (CH=&) SYM=ANDSYM; GetCh(); else if (CH=|) Ge

20、tCh(); if (CH=|) SYM=ORSYM; GetCh(); else Error(19); else if (CH=!) SYM=NOTSYM; GetCh(); else SYM=SSYMCH; GetCh(); 1.2.2在void STATEMENT(SYMSET FSYS,int LEV,int &TX)函數(shù)中增加：case TIMESBECOMES: GetSym(); Form1-printfs(運(yùn)算符：*= ); break; case SLASHBECOMES: GetSym(); Form1-printfs(運(yùn)算符： /= ); break; case ANDS

21、YM: GetSym(); Form1-printfs(運(yùn)算符：& ); break; case ORSYM: GetSym(); Form1-printfs(運(yùn)算符：| ); break; case NOTSYM: GetSym(); Form1-printfs(運(yùn)算符：! ); break;1.3保留字的個(gè)數(shù)原保留字個(gè)數(shù)是14，故const NORW = 14; /* # OF RESERVED WORDS */因?yàn)樾略黾颖Ａ糇?個(gè)，故應(yīng)改為：const NORW = 19; /* # OF RESERVED WORDS */1.4單詞總數(shù)原單詞總數(shù)是33，故所有“i33” (i實(shí)際上是指

22、單詞總數(shù))因?yàn)樾略黾訂卧~10個(gè)，故應(yīng)改為“i43”。為了方便以后新增加單詞，特加入了常量const WNUM = 43;然后把所有的43替換成了WNUM，以后要增加單詞，就可以直接修改該值，不必再重新把所有的值找出來(lái)做替換。2.修改單詞：不等號(hào)# 改為 （1） 把源代碼中的程序段 SSYM#=NEQ; 刪除或注釋消去。 （2）在GetSym（）過(guò)程中把分析到的定義為不等號(hào)，從“”切入修改。else /* THE FOLLOWING TWO CHECK WERE ADDED BECAUSE ASCII DOES NOT HAVE A SINGLE CHARACTER FOR = */ if (C

23、H=) SYM=NEQ; GetCh(); /更改不等號(hào)為“” else SYM=LSS;3.增加條件語(yǔ)句的ELSE子句，要求：寫(xiě)出相關(guān)文法，語(yǔ)法圖，語(yǔ)義規(guī)則。（1）相關(guān)文法 G(S): Sif S else S | if S | a（2）語(yǔ)法圖（3） 語(yǔ)義規(guī)則產(chǎn)生式語(yǔ) 義 規(guī) 則Sif B then M S1 backpatch(E.truelist, M.quad );S.nextlist:=merge(E.falselist, S1.nextlist) M M.quad := nextquad ; N N.nextlist:=makelist(nextquad);Gen( j , , ,

24、 0 ) Sif B then M1 S1 N else M2 S2 backpatch(E.truelist, M1.quad );backpatch(E.falselist, M2.quad );S.nextlist:=merge(S1.nextlist, N.nextlist, S2.nextlist) （4） 代碼修改在void STATEMENT(SYMSET FSYS,int LEV,int &TX)中加入ELSE的實(shí)現(xiàn)語(yǔ)句case IFSYM: GetSym(); /* 條件語(yǔ)句*/CONDITION(SymSetUnion(SymSetNew(THENSYM,DOSYM),FS

25、YS),LEV,TX);if (SYM=THENSYM) GetSym();else Error(16); CX1=CX; GEN(JPC,0,0); STATEMENT(FSYS,LEV,TX); if (SYM=ELSESYM) /* 如果THAN后面跟ELSE，ELSE可有可無(wú),不影響IF語(yǔ)句 */ GetSym(); CX2=CX; GEN(JMP,0,0);/*無(wú)條件跳轉(zhuǎn)語(yǔ)句*/ CODECX1.A=CX; /*cx即為else語(yǔ)句的位置，回填之前的JPC語(yǔ)句跳轉(zhuǎn)的語(yǔ)句*/ STATEMENT(FSYS,LEV,TX); /*else中的語(yǔ)句體*/ CODECX2.A=CX; /*執(zhí)行完ELSE中的語(yǔ)句體后的地址，把它回填JMP中的跳轉(zhuǎn)地址*/ else /*如果than語(yǔ)句后面沒(méi)有發(fā)現(xiàn)else*/ CODECX1.A=CX; /*執(zhí)行JPC語(yǔ)句