編譯原理課設(shè)報(bào)告最終版

1、 編譯原理課程設(shè)計(jì)PL0 Experiment Report（燕山大學(xué) 信息科學(xué)與工程學(xué)院） 姓 名 班 級(jí) ： 計(jì)算機(jī)* 學(xué) 生 學(xué) 號(hào) ： 130104010*&* 課 程 名 稱 ： 編譯原理 指 導(dǎo) 教 師 ： 888 2015年 12 月 24 日 一、設(shè)計(jì)目的研究、 改進(jìn)或自行設(shè)計(jì)、 開(kāi)發(fā)一個(gè)簡(jiǎn)單的編譯程序或其部分功能， 加深對(duì)編譯理論和編譯過(guò)程的理解。 編程語(yǔ)言不限。二、設(shè)計(jì)任務(wù)擴(kuò)展 PL/0 編譯程序功能目的: 擴(kuò)充 PL/0 編譯程序功能要求: (1)閱讀、 研究 PL/0 編譯程序源文件。 (2)在上述工作基礎(chǔ)上， 可有選擇地補(bǔ)充、完善其中詞法分析、語(yǔ)法分析、語(yǔ)義分

2、析、目標(biāo)代碼生成、目標(biāo)代碼解釋執(zhí)行等部分的功能。如以語(yǔ)法分析部分為例，則可以增加處理更多語(yǔ)法成分的功能，如可處理一維數(shù)組、+、-、+=、-=、*=、/=、%(取余)、!(取反)、repeat、for、else、開(kāi)方、處理注釋、錯(cuò)誤提示、標(biāo)示符或變量中可以有下劃線等。還可以增加類型，如增加字符類型、實(shí)數(shù)類型; 擴(kuò)充函數(shù)如有返回值和返回語(yǔ)句的，有參數(shù)函數(shù)等; (3)設(shè)計(jì)編制典型的運(yùn)行實(shí)例，以便能反映出自己所作的改進(jìn)。 三、設(shè)計(jì)思想:PL/0 語(yǔ)言可以看成PASCAL 語(yǔ)言的子集，它的編譯程序是一個(gè)編譯解 釋執(zhí)行系統(tǒng)。PL/0 的目標(biāo)程序?yàn)榧傧霔Ｊ接?jì)算機(jī)的匯編語(yǔ)言，與具體計(jì)算 機(jī)無(wú)關(guān)。 P

3、L/0的編譯程序和目標(biāo)程序的解釋執(zhí)行程序都是用PASCAL語(yǔ)言書(shū)寫(xiě) 的，因此PL/0 語(yǔ)言可在配備PASCAL 語(yǔ)言的任何機(jī)器上實(shí)現(xiàn) 。其編譯過(guò)程采用一趟掃描方式，以語(yǔ)法分析程序?yàn)楹诵?，詞法分析和代碼生成程序都作為一個(gè)獨(dú)立的過(guò)程，當(dāng)語(yǔ)法分析需要讀單詞時(shí)就調(diào)用詞法分析程序， 而當(dāng)語(yǔ)法分析正確需要生成相應(yīng)的目標(biāo)代碼時(shí)，則調(diào)用代碼生成程序。 用表格管理程序建立變量、常量和過(guò)程表示符的說(shuō)明與引用之間的信息聯(lián)系。當(dāng)源程序編譯正確時(shí)，PL/0 編譯程序自動(dòng)調(diào)用解釋執(zhí)行程序，對(duì)目標(biāo) 代碼進(jìn)行解釋執(zhí)行，并按用戶程序的要求輸入數(shù)據(jù)和輸出運(yùn)行結(jié)果。四、設(shè)計(jì)內(nèi)容：1 擴(kuò)充語(yǔ)句for(<語(yǔ)句>；<條

4、件>；<語(yǔ)句>)<語(yǔ)句>；2 擴(kuò)充語(yǔ)句if <條件> then <語(yǔ)句> else <語(yǔ)句>；3 擴(kuò)充語(yǔ)句repeat <語(yǔ)句>；until <條件>；4 增加自增自減運(yùn)算+和和+=，-=運(yùn)算；5 修改不等號(hào)#，為!=；6 增加一維數(shù)組聲明格式：<ident><ident>/<number>:<ident>/<number>；賦值格式：<ident><index>:=<表達(dá)式>；調(diào)用格式：<ident&g

5、t;<index>五、程序結(jié)構(gòu)：程序pl0程序block語(yǔ)句statement條件condition表達(dá)式expression項(xiàng)term因子factorPL/0源程序 詞法分析程序表格管理程序語(yǔ)法分析程序出錯(cuò)管理程序代碼生成程序目標(biāo)程序圖1 編譯程序結(jié)構(gòu) 圖2功能模塊調(diào)用1.功能模塊作用如下：Pl0.c：主程序Error：出錯(cuò)處理，打印出錯(cuò)位置和錯(cuò)誤編碼Getsym：詞法分析，讀取一個(gè)單詞Getch：漏掉空格，讀取一個(gè)字符Gen：生成目標(biāo)代碼，并送入目標(biāo)程序區(qū)Test：測(cè)試當(dāng)前符號(hào)是否合法Block：分程序分析處理過(guò)程，詞法語(yǔ)法分析Enter：登陸名字表Position：查找標(biāo)識(shí)符

6、在名字表中的位置Constdeclaration：常量定義處理Vardeclaraction：變量說(shuō)明處理Listcode：列出目標(biāo)代碼清單Statement：語(yǔ)句處理Expression：表達(dá)式處理Term：項(xiàng)處理Factor：因子處理Condition：條件處理Interpret：對(duì)目標(biāo)代碼的解釋執(zhí)行程序Base：通過(guò)靜態(tài)鏈求出數(shù)據(jù)取得基地址增加兩個(gè)功能：Arraydeclaration：數(shù)組聲明處理Arraycoef：數(shù)組索引計(jì)算和“虛擬機(jī)”動(dòng)作生成2.保留字：enum symbol nul,ident,number,plus,minus, times,slash,oddsym,eql,

7、neq, lss,leq,gtr,geq,lparen, rparen,comma,semicolon,period,becomes, beginsym,endsym,ifsym,thensym,elsesym,forsym, inc,dec,whilesym, writesym, readsym,dosym,callsym, constsym,varsym, procsym,repeatsym, untilsym, plusbk,minusbk, lbrack,rbrack,colon,共43個(gè)，其中補(bǔ)充保留字為：else, for, repeat, until, plusbk, minus

8、bk, Lbrack, rbrack, colon3.名字表中的類型enum object constant, variable, procedure, arrays, 共4個(gè)，擴(kuò)充arrays，以便實(shí)現(xiàn)數(shù)組4.虛擬機(jī)代碼enum fct lit, opr, lod, sto, cal, inte, jmp, jpc,lda, sta, 共10個(gè)，補(bǔ)充的lda，sta用于數(shù)組操作6. 錯(cuò)誤信息(1)const,var,procedure后應(yīng)為標(biāo)識(shí)符(2) 常數(shù)說(shuō)明中的=后應(yīng)是數(shù)字(3)常數(shù)說(shuō)明中的標(biāo)識(shí)符后應(yīng)是=(4)常數(shù)說(shuō)明中的=寫(xiě)成了：=(5)漏掉了，或；(6)過(guò)程說(shuō)明后的符號(hào)不正確（應(yīng)是語(yǔ)

9、句開(kāi)始符，或過(guò)程定義符）(7)應(yīng)是語(yǔ)句開(kāi)始符(8)標(biāo)識(shí)符未說(shuō)明(9)程序結(jié)尾丟了句號(hào)。(10)語(yǔ)句之間漏了；(11)call后應(yīng)為標(biāo)識(shí)符(12)賦值語(yǔ)句中，賦值號(hào)左部標(biāo)識(shí)符屬性應(yīng)是變量(13)賦值號(hào)左部標(biāo)識(shí)符屬性應(yīng)是賦值號(hào)(14)程序體內(nèi)語(yǔ)句部分的后跟符不正確(15)call后標(biāo)識(shí)符屬性應(yīng)為過(guò)程(16)條件語(yǔ)句中丟了then(17)丟了end或；(18)while循環(huán)語(yǔ)句中丟了do(19)語(yǔ)句后的符號(hào)不正確6.名字表結(jié)構(gòu)struct tablestructchar nameal;enum object kind;int val;int level;int adr;int size;/擴(kuò)充名字表

10、結(jié)構(gòu),增加一個(gè)data域保存數(shù)組的下界int data; /* 其他數(shù)據(jù),對(duì)arrays來(lái)說(shuō)是下界*/7.語(yǔ)法描述圖：程序分程序 .圖3 程序語(yǔ)法描述圖，。；，；=語(yǔ)句constidentnumbervaridentprocedureident分程序圖4 分程序語(yǔ)法描述圖語(yǔ)句語(yǔ)句until表達(dá)式表達(dá)式:=if條件endthen語(yǔ)句條件do語(yǔ)句（表達(dá)式），（ident，）begin語(yǔ)句語(yǔ)句;identcallidentwhilerepeatreadwritedecsincsincsdecselse語(yǔ)句for條件語(yǔ)句圖5 語(yǔ)句語(yǔ)法描述圖 條件=<>#>=odd表達(dá)式表達(dá)式<

11、=圖6條件語(yǔ)法描述圖表達(dá)式項(xiàng)項(xiàng)+ 圖7 表達(dá)式語(yǔ)法描述圖項(xiàng)因子因子/*%圖8 項(xiàng)語(yǔ)法描述圖因子)(表達(dá)式identnumberincsdecsdecsincs圖9 因子語(yǔ)法描述圖四、功能擴(kuò)充1.語(yǔ)句處理中加入for循環(huán)語(yǔ)句if(sym = forsym)getsymdo;if(sym != lparen) error(34);/沒(méi)有左括號(hào)出錯(cuò)else getsymdo;statementdo(nxtlev, ptx, lev); /S1代碼if(sym != semicolon) error(10); /語(yǔ)句缺少分號(hào)出錯(cuò)elsecx1=cx;getsymdo;conditiondo(nxtle

12、v, ptx, lev); /E代碼if(sym!=semicolon)error(10);/語(yǔ)句缺少分號(hào)出錯(cuò)else cx2=cx;gendo(jpc,0,0);cx3=cx;gendo(jmp,0,0);getsymdo;cx4=cx;statementdo(nxtlev, ptx, lev);/S2代碼if(sym != rparen) error(22);/缺少右括號(hào)出錯(cuò)else gendo(jmp,0,cx1);getsymdo;cx5=cx;statementdo(nxtlev, ptx, lev); /S3代碼codecx3.a=cx5;gendo(jmp,0,cx4);code

13、cx2.a=cx;2.在語(yǔ)句處理中增加repeat-until語(yǔ)句if(sym = repeatsym)cx1 = cx;getsymdo;statementdo(nxtlev, ptx, lev);if(sym = untilsym)getsymdo;conditiondo(nxtlev, ptx, lev);cx2=cx;gendo(jpc, 0, 0);codecx2.a=cx1; else error(33); /沒(méi)有寫(xiě)until出錯(cuò)3.擴(kuò)充+和運(yùn)算符對(duì)于+和-運(yùn)算符，擴(kuò)充時(shí)要注意存在兩個(gè)情況：1）作為語(yǔ)句的時(shí)候；2）作為表達(dá)式中的因子的時(shí)候。 注意：擴(kuò)充時(shí)增加因子開(kāi)始符facbegs

14、ysincs=true和facbegsysdecs=true。 擴(kuò)充的語(yǔ)法描述見(jiàn)結(jié)構(gòu)設(shè)計(jì)中的PL/0分程序和主要語(yǔ)句的語(yǔ)法描述中的描述圖，詳細(xì)代碼見(jiàn)程序。 1）作為語(yǔ)句的時(shí)候，有四種情況： a+; a-; +a; -a; 文法的EBNF表示形式為： <自增自減語(yǔ)句>:=<標(biāo)識(shí)符>+ |-|+|- <標(biāo)識(shí)符> 文法分析過(guò)程大體如下圖： 語(yǔ)句開(kāi)始符SYM=+或者-讀下個(gè)SYM，如是ident，確定為自增自減語(yǔ)句語(yǔ)句開(kāi)始符SYM=ident讀下個(gè)SYM，如是+或者-，確定為自增自減語(yǔ)句 +a和a a+和a生成中間代碼對(duì)于a+;+a;和a-;-a;語(yǔ)句的處理如下：

15、先將變量的值取出放在棧頂，后將1入棧，后執(zhí)行加法或減法運(yùn)算oprv指令的2（加法)、3（減法），后將運(yùn)算后的棧頂值存回變量。 a+;和+a;語(yǔ)句的中間代碼：lod 0 3;lit 0 1;opr 0 2;sto 0 3;a-;和-a;語(yǔ)句的中間代碼：lod 0 3;lit 0 1;opr 0 3;sto 0 3; 2） 作為因子的時(shí)候，有兩種情況： a+和a-作為因子，比如：b:=a+*a-;語(yǔ)句 +a和-a作為因子，比如：b:=-a+2*+a;語(yǔ)句 文法的EBNF表示形式為： <表達(dá)式>:=. +|-<標(biāo)識(shí)符>|<標(biāo)識(shí)符>+| -. 其中的.表示前后都可以

16、有其他的項(xiàng)或因子 生成中間代碼A對(duì)于因子+a和-a的中間代碼生成處理和a+;等語(yǔ)句處理一樣； B對(duì)于因子a+和a的中間代碼生成處理如下：a+:lod 0 3;lit 0 1;opr 0 2;sto 0 3;lod 0 3;lit 0 1;opr 0 3; a-:lod 0 3;lit 0 1;opr 0 3;sto 0 3;lod 0 3;lit 0 1;opr 0 2; 先將變量的值取出放在棧頂，后將1入棧，后執(zhí)行加法或減法運(yùn)算opr指令的2(加法)、3（減法），后將運(yùn)算后的棧頂值存回變量，后將變量的值又取出來(lái)放入棧頂，后將1入棧，如果是a+就執(zhí)行減法，如果是a就執(zhí)行加法，以實(shí)現(xiàn)先用a的值后

17、再加1。4.語(yǔ)句處理中加入if-then-else語(yǔ)句在原有程序if(sym=then).后加入下列代碼：cx1 = cx;gendo(jpc, 0, 0);statementdo(fsys, ptx, lev);if(sym = elsesym)getsymdo;cx2 = cx;gendo(jmp, 0, 0);codecx1.a = cx;statementdo(fsys, ptx, lev);codecx2.a = cx;elsecodecx1.a = cx;5.修改不等號(hào)#為!=注釋源程序中的ssym'#' = neq語(yǔ)句，在getsym中加入下列代碼：/修改不等號(hào)為

18、!=else if(ch='!')getchdo;if(ch='=')sym=neq;getchdo; else sym=nul; 6.加入對(duì)一維數(shù)組的支持本程序?qū)?shù)組看做變量的一種，由var聲明函數(shù)調(diào)用array聲明函數(shù)完成數(shù)組聲明，這樣就處加入文件輸出的相關(guān)語(yǔ)句外，可以完全保留block函數(shù)和enter函數(shù)；通過(guò)改寫(xiě)factor函數(shù)使數(shù)組因子包括了后綴的索引號(hào)，這樣就可以調(diào)用通用的表達(dá)式函數(shù)賦值數(shù)組了。為了方便完成數(shù)組相關(guān)功能，擴(kuò)充了虛擬機(jī)處理代碼。數(shù)組的越界及非法調(diào)用錯(cuò)誤處理沒(méi)有完善，僅給出了錯(cuò)誤代碼。在頭文件pl0.h中：/*定義兩個(gè)全局變量，用來(lái)保存數(shù)

19、組定義的下界和容量*/static int g_arrBase = 0;static int g_arrSize = 0;/* 虛擬機(jī)代碼*/增加lda,sta專門由于數(shù)組的處理/增加兩個(gè)虛擬機(jī)指令lda,sta,分別用來(lái)從數(shù)組中取數(shù)和存到數(shù)組中/數(shù)組元素的訪問(wèn)和存儲(chǔ)，是將()后的當(dāng)成表達(dá)式，先處理，得到元素的索引，放在棧頂/最后根據(jù)數(shù)組的首地址，得到某個(gè)元素的地址enum fct .lda, sta /擴(kuò)充名字表結(jié)構(gòu),增加一個(gè)data域保存數(shù)組的下界struct data; /* 其他數(shù)據(jù),對(duì)arrays來(lái)說(shuō)是下界*/* 名字表中的類型*/enum objec

20、t .arrays /添加數(shù)組類型/數(shù)組聲明處理, 下界和上界允許已經(jīng)定義過(guò)的常量標(biāo)識(shí)符int arraydeclaration(int* ptx, int lev, int* pdx);/數(shù)組元素索引計(jì)算與“虛擬機(jī)”生成int arraycoef(bool *fsys,int *ptx,int lev);在源程序文件pl0.c中：編寫(xiě)相關(guān)的arraydeclaration，arraycoef兩個(gè)功能函數(shù)：/* 數(shù)組聲明處理, 下界和上界允許已經(jīng)定義過(guò)的常量標(biāo)識(shí)符*/int arraydeclaration(int* ptx, int lev, int* pdx) char arrIdal;

21、/* 暫存數(shù)組標(biāo)識(shí)名,避免被覆蓋*/ int cstId; /* 常量標(biāo)識(shí)符的位置*/ int arrBase=-1, arrTop=-1; /* 數(shù)組下界、上界的數(shù)值*/getsymdo; if(sym=lbrack) /* 標(biāo)識(shí)符之后是'',則識(shí)別為數(shù)組*/ strcpy(arrId, id); /* 檢查下界*/ getsymdo; if(sym=ident) if(cstId=position(id,(*ptx)!=0)arrBase=(constant=tablecstId.kind)?tablecstId.val:-1; elsearrBase=(sym=numbe

22、r)?num:-1; if(-1=arrBase)error(50);return -1; /* 檢查冒號(hào)*/getsymdo;if(sym!=colon) error(50);return -1; /* 檢查上界*/ getsymdo; if(sym=ident) if(cstId=position(id,(*ptx)!=0)arrTop=(constant=tablecstId.kind)?tablecstId.val:-1; elsearrTop=(number=sym)?num:-1; if(arrTop=-1)error(50);/隨意指定,因?yàn)樵绦驅(qū)﹀e(cuò)誤號(hào)的規(guī)劃極差!return

23、 -1; /* 檢查'' */ getsymdo; if(sym!=rbrack) error(50);return -1; /* 上下界是否符合條件檢查*/ g_arrSize=arrTop-arrBase+1; g_arrBase=arrBase; if(g_arrSize<=0)error(50);return -1; /* 恢復(fù)數(shù)組的標(biāo)識(shí)符*/ strcpy(id, arrId); return 1; return 0;/* 數(shù)組元素索引計(jì)算與“虛擬機(jī)”生成*/int arraycoef(bool *fsys,int *ptx,int lev) bool nxtl

24、evsymnum; int i = position(id,*ptx); getsymdo; if (sym=lbrack) /* 索引是括號(hào)內(nèi)的表達(dá)式*/ getsymdo; memcpy(nxtlev,fsys,sizeof(bool)*symnum); nxtlevrbrack=true; expressiondo(nxtlev,ptx,lev); if (sym=rbrack) gendo(lit,0,tablei.data); gendo(opr,0,3); /* 系數(shù)修正,減去下界的值*/ return 0; elseerror(22); /* 缺少右括號(hào)*/ elseerror(

25、51); /* 數(shù)組訪問(wèn)錯(cuò)誤*/ return -1;修改函數(shù)enter，block，vardeclaration，factor及statement，使其具備處理數(shù)組的功能：/將數(shù)組變量登陸名字表void enter(enum object k, int * ptx, int lev, int * pdx).case arrays: /* 數(shù)組名,進(jìn)行記錄下界等*/ table(*ptx).level = lev; table(*ptx).adr = (*pdx); table(*ptx).data = g_arrBase; table(*ptx).size = g_arrSize; *pdx

26、 = (*pdx)+g_arrSize; break;./輸出數(shù)組名字表到控制臺(tái)和文件fas.tmpint block(int lev, int tx, bool * fsys).case arrays:printf("%d array %s ", i, );printf("lev=%d addr=%d size=%dn", tablei.level, tablei.adr, tablei.size);fprintf(fas, "%d array %s ", i, );fprintf(fas

27、, "lev=%d addr=%d size=%dn", tablei.level, tablei.adr, tablei.size);/加入數(shù)組聲明int vardeclaration(int * ptx, int lev, int * pdx)int arrayRet=-1; if (sym=ident) arrayRet=arraydeclaration(ptx,lev,pdx); /* 先判斷數(shù)組*/ switch(arrayRet) case 1: enter(arrays,ptx,lev,pdx); / 填寫(xiě)數(shù)組名getsymdo; break; case 0:

28、 enter(variable,ptx,lev,pdx); / 填寫(xiě)名字表 /getsymdo; break; default: return -1; /* 數(shù)組定義解析出錯(cuò)*/ elseerror(4); /* var后應(yīng)是標(biāo)識(shí)*/ return 0;/*當(dāng)因子是數(shù)組型變量時(shí)，調(diào)用arraycodefdo將數(shù)組的索引入棧頂，之后按vatiabler變量操作*/int factor(bool * fsys, int * ptx, int lev).switch (tablei.kind).case arrays: /* 名字為數(shù)組名*/arraycoefdo(fsys,ptx,lev);gen

29、do(lda,lev-tablei.level,tablei.adr); /* 找到變量地址并將其值入棧*/. . int statement(bool * fsys, int * ptx, int lev).if (sym = ident).if (tablei.kind != variable)&&(tablei.kind != arrays)error(12); i = 0;elseenum fct fct1 = sto; switch(tablei.kind)case arrays:arraycoefdo(fsys, ptx, lev);fct1 = sta; /* 數(shù)

30、組保存,要多讀一個(gè)棧*/case variable:./增加的兩個(gè)虛擬機(jī)代碼的處理:lda,stavoid interpret().case lda: /* 數(shù)組元素訪問(wèn),當(dāng)前棧頂為元素索引,執(zhí)行后,棧頂變成元素的值*/st-1 = sbase(i.l,s,b) + i.a + st-1;break;case sta: /* 棧頂?shù)闹荡娴綌?shù)組中,索引為次棧頂*/t-=2;sbase(i.l,s,b) + i.a + st = st+1;break;.五、調(diào)試及運(yùn)行結(jié)果1.測(cè)試repeat.until.語(yǔ)句功能 測(cè)試文件：4.txt 測(cè)試結(jié)果： var a,b,n; begin b:=4; a:=1; read(n); repeat a:=a+1;b:=b+1; until a>n; write(a); write(b);end.當(dāng)輸入的n為3時(shí)，repeat.until.語(yǔ)句中的循環(huán)體執(zhí)行3次，所以a=4,b=72.測(cè)試增加的+,-功能 測(cè)試文件：2.txt 測(cè)試結(jié)果：var a,b;begin a:=1; b:=3; a