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

1、 編譯原理實(shí)驗(yàn)報(bào)告 課程名稱(chēng)_編譯原理_ 題目名稱(chēng) PL0上機(jī)作業(yè) 學(xué)生學(xué)院_ 計(jì)算機(jī)學(xué)院_ 專(zhuān)業(yè)班級(jí)_ 12級(jí)計(jì)科8班 學(xué) 號(hào)_ 3112006110 _學(xué)生姓名_ 謝偲灝 _ 指導(dǎo)教師_ 楊勁濤 _2015年 1 月 3 日一、 概述目的：在分析理解一個(gè)教學(xué)型編譯程序（如PL/0）的基礎(chǔ)上，對(duì)其詞法分析程序、語(yǔ)法分析程序和語(yǔ)義處理程序進(jìn)行部分修改擴(kuò)充。達(dá)到進(jìn)一步了解程序編譯過(guò)程的基本原理和基本實(shí)現(xiàn)方法的目的。1 要求：課內(nèi)實(shí)驗(yàn)（考試前交報(bào)告）對(duì)PL/0作以下修改擴(kuò)充：（1）增加單詞：保留字：FOR，TO，DOWNTO，+=，-=，+，-；RETURN 要求：詞法識(shí)別即可（2）替換單詞：不等

2、號(hào)# 改為 < >，（3）增加條件語(yǔ)句的ELSE子句，要求：寫(xiě)出相關(guān)文法，語(yǔ)法圖，語(yǔ)義規(guī)則。二、 實(shí)驗(yàn)環(huán)境與工具（1）源：C語(yǔ)言（2）程序目標(biāo)語(yǔ)言： PL/0（3）實(shí)現(xiàn)工具（平臺(tái)）：vc+6.0 （4）運(yùn)行平臺(tái)：PC機(jī),Windows7三、 設(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)。（2） PL/0編譯程序的語(yǔ)法分析過(guò)程BLOCK是整個(gè)編譯過(guò)程的核心。這里根據(jù)編譯程序的總體流程圖，來(lái)弄清BLOCK過(guò)程在整個(gè)編譯程序中的作用?？偭?/p>

3、程圖如下圖所示：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ì)。2.各功能模塊描述過(guò)程或函數(shù)名簡(jiǎn)要功能說(shuō)明pl0主程序error出錯(cuò)處理，打印出錯(cuò)位置和錯(cuò)誤編碼getsym詞法分析，讀取一個(gè)單詞getch漏掉空格，讀取一個(gè)字符gen生成目標(biāo)代碼，并送入目標(biāo)程序區(qū)test測(cè)試當(dāng)前單詞符號(hào)是否

4、合法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ū)的基地址四、主要成分描述符號(hào)表為了組成一條指令，編譯程序必須知道其操作碼及其參數(shù)（數(shù)或地址）。這些值是由編譯程序本身聯(lián)系到相應(yīng)標(biāo)識(shí)符上去的。這種聯(lián)系是在處理常數(shù)、變量和過(guò)程說(shuō)明完成的。為此，

5、標(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 的初值為3，因?yàn)槊總€(gè)數(shù)據(jù)區(qū)包含三個(gè)內(nèi)部變量RA，DL 和SL。 運(yùn)行時(shí)存儲(chǔ)組織和管理對(duì)于源程序的每一個(gè)過(guò)程（包括主程序），在被調(diào)用時(shí)，首

6、先在數(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ù)段，找到包含要引用的變量所在的數(shù)據(jù)段基址，然后通過(guò)偏移地址訪(fǎng)問(wèn)它。在過(guò)程返回時(shí)，解釋程序通過(guò)返回地址恢復(fù)指令指針的值到調(diào)用前的地址，通過(guò)當(dāng)前段基

7、址恢復(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等訪(fǎng)問(wèn)局部變量的指令中會(huì)經(jīng)常用到。類(lèi)PCODE代碼解釋執(zhí)行的部分通過(guò)循環(huán)和簡(jiǎn)單的case判斷不同的指令，做出相應(yīng)的動(dòng)作。當(dāng)遇到主程序中的返回指令時(shí)，指令指針會(huì)指到0位置，把這樣一個(gè)條件作為終至循環(huán)的條件，保證程序運(yùn)行可以正常的結(jié)束。 語(yǔ)法分析方法語(yǔ)法分析子程序采用了自頂向下的遞歸子程序法，語(yǔ)法分析同時(shí)也根據(jù)程序

8、的語(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）和條件處理過(guò)程（Condition）構(gòu)成。這些過(guò)程在結(jié)構(gòu)上構(gòu)成一個(gè)嵌套的層次結(jié)構(gòu)。除此之外，還有出錯(cuò)報(bào)告過(guò)程（Error）、代碼生成過(guò)程（Gen

9、）、測(cè)試單詞合法性及出錯(cuò)恢復(fù)過(guò)程（Test）、登錄名字表過(guò)程（Enter）、查詢(xún)名字表函數(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ì)算機(jī)處理表達(dá)式。(2) 每個(gè)三元式由三個(gè)部分組成：A. 算符opB. 第一運(yùn)算對(duì)象ARG1C. 第二運(yùn)算對(duì)象ARG2運(yùn)算對(duì)象可能是源程序中

10、的變量，也可能是某個(gè)三元式的結(jié)果，用三元式的編號(hào)表示。(3) 樹(shù)形表示是三元式表示的翻版。(4) 四元式是一種比較普遍采用的中間代碼形式：算符op，運(yùn)算對(duì)象ARG1，運(yùn)算對(duì)象ARG2，運(yùn)算結(jié)果RESULT五、開(kāi)發(fā)過(guò)程和完成情況1.增加單詞：保留字：FOR，TO，DOWNTO，RETURN運(yùn)算符 : +=，-=，+，-；新增4個(gè)保留字和4個(gè)運(yùn)算符，合計(jì)8個(gè)單詞。其中保留字FOR，TO，DOWNTO，RETURN 分別對(duì)應(yīng)downtosym,forsym,returnsym,tosym；運(yùn)算符 +=，-=，+，- 分別對(duì)應(yīng) pluseql,minuseql,plusplus,minusminus1

11、.1保留字enum symbol nul, ident, number, plus, minus, 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,downtosym,forsym,returnsym,tosym,elsesym,pluseql

12、,plusplus,minuseql,minusminus/增加的語(yǔ)句;/*設(shè)置保留字名字,按照字母順序,便于折半查找*/strcpy(&(word00),"begin");strcpy(&(word10),"call");strcpy(&(word20),"const");strcpy(&(word30),"do");strcpy(&(word40),"downto"); /*增加保留字DOWNTO*/strcpy(&(word50),"

13、;else"); /*增加保留字ELSE*/strcpy(&(word60),"end");strcpy(&(word70),"for"); /*增加保留字FOR*/strcpy(&(word80),"if");strcpy(&(word90),"odd");strcpy(&(word100),"procedure");strcpy(&(word110),"read");strcpy(&(word120),&q

14、uot;return"); /*增加保留字RETURN*/strcpy(&(word130),"then");strcpy(&(word140),"to"); /*增加保留字TO*/strcpy(&(word150),"var");strcpy(&(word160),"while");strcpy(&(word170),"write");/*設(shè)置保留字符號(hào)*/wsym0=beginsym;wsym1=callsym;wsym2=constsym;

15、wsym3=dosym;wsym4=downtosym; /*增加保留字符號(hào)downtosym*/wsym5=elsesym; /*增加保留字符號(hào)elsesym*/wsym6=endsym;wsym7=forsym; /*增加保留字符號(hào)forsym*/wsym8=ifsym;wsym9=oddsym;wsym10=procsym;wsym11=readsym;wsym12=returnsym; /*增加保留字符號(hào)returnsym*/wsym13=thensym;wsym14=tosym; /*增加保留字符號(hào)tosym*/wsym15=varsym;wsym16=whilesym;wsym17

16、=writesym;1.2保留字和單詞的個(gè)數(shù)1),原保留字個(gè)數(shù)是14，# define norw 14。因?yàn)樾略黾颖Ａ糇?個(gè) ，所以 # define norw 182),原單詞總數(shù)是33，#define symnum 33。因?yàn)樾略黾訂卧~9個(gè)，所以#define symnum 421.3運(yùn)算符在GetSym()函數(shù)中增加：else if(ch='+')/ 增加檢測(cè)+和+=符號(hào) getchdo;if(ch='+')sym=plusplus; /構(gòu)成+號(hào)getchdo;else if(ch='=')sym=pluseql; /構(gòu)成+=號(hào)getchd

17、o;elsesym=plus;else if(ch='-') /增加檢測(cè)-和-=符號(hào) getchdo;if(ch='-')sym=minusminus; /構(gòu)成-號(hào)getchdo;else if(ch='=')sym=minuseql; /構(gòu)成-=號(hào)getchdo;elsesym=minus;2.修改單詞：不等號(hào)# 改為 <>（1） /ssym'#'=neq; 把這段刪除（2）在GetSym（）過(guò)程中把分析到的<>定義為不等號(hào)，從“<”切入修改。e if(ch='<') /*檢測(cè)

18、小于或小于等于符號(hào)*/ getchdo; if(ch='=') sym=leq; getchdo; else if (ch='>')/增加這段語(yǔ)句 sym=neq; /構(gòu)成不等號(hào) <> getchdo; 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ī) 則S®if B then M S1 backpatch(E.truelist, M.quad );S.nextlist:=merge(E.falselist, S1.nextlist) M ® M.quad := nextquad ; N ® N.nextlist:=makelist(n