編譯原理實(shí)習(xí)題.doc

Pl/0語(yǔ)言文法的BNF表示：程序分程序。分程序 語(yǔ)句 CONST ,； = VAR ,； | ； procedure； | := begin ； |ood +|- |() +|- *|/ =|#|= ifthen call whiledo read( ，) write(，) a|b|cx|y|z 0|1|27|8|9一 PL/0語(yǔ)言建立一個(gè)詞法分程序GETSYM（函數(shù)）把關(guān)鍵字、算符、界符稱為語(yǔ)言固有的單詞，標(biāo)識(shí)符、常量稱為用戶自定義的單詞。為此設(shè)置三個(gè)全程量：SYM,ID,NUM 。 SYM：存放每個(gè)單詞的類別，為內(nèi)部編碼的表示形式。 ID：存放用戶所定義的標(biāo)識(shí)符的值，即標(biāo)識(shí)符字符串的機(jī)內(nèi)表示。 NUM：存放用戶定義的數(shù)。 GETSYM要完成的任務(wù)：1. 濾掉單詞間的空格。2. 識(shí)別關(guān)鍵字，用查關(guān)鍵字表的方法識(shí)別。當(dāng)單詞是關(guān)鍵字時(shí)，將對(duì)應(yīng)的類別放在SYM中。如IF的類別為IFSYM，THEN的類別為THENSYM。3. 識(shí)別標(biāo)識(shí)符，標(biāo)識(shí)符的類別為IDENT，IDRNT放在SYM中，標(biāo)識(shí)符本身的值放在ID中。關(guān)鍵字或標(biāo)識(shí)符的最大長(zhǎng)度是10。4. 拼數(shù)，將數(shù)的類別NUMBER放在SYM中，數(shù)本身的值放在NUM中。5. 拼由兩個(gè)字符組成的運(yùn)算符，如：=、=等等，識(shí)別后將類別存放在SYM中。6. 打印源程序，邊讀入字符邊打印。由于一個(gè)單詞是由一個(gè)或多個(gè)字符組成的，所以在詞法分析程序GETSYM中定義一個(gè)讀字符過程GETCH。二 PL/0語(yǔ)言建立一個(gè)語(yǔ)法分析程序BLOCK（函數(shù)）PL/0編譯程序采用一遍掃描的方法，所以語(yǔ)法分析和代碼生成都有在BLOCK中完成。BLOCK的工作分為兩步：a) 說明部分的處理說明部分的處理任務(wù)就是對(duì)每個(gè)過程（包括主程序，可以看成是一個(gè)主過程）的說明對(duì)象造名字表。填寫所在層次（主程序是0層，在主程序中定義的過程是1層，隨著嵌套的深度增加而層次數(shù)增大。PL/0最多允許3層），標(biāo)識(shí)符的屬性和分配的相對(duì)地址等。標(biāo)識(shí)符的屬性不同則填寫的信息不同。所造的表放在全程量一維數(shù)組TABLE中，TX為指針，數(shù)組元素為結(jié)構(gòu)體類型數(shù)據(jù)。LEV給出層次，DX給出每層的局部量的相對(duì)地址，每說明完一個(gè)變量后DX加1。例如：一個(gè)過程的說明部分為： const a=35,b=49; var c,d,e; procedure p;var g;對(duì)它的常量、變量和過程說明處理后，TABLE表中的信息如下：TX0 TX1 NAME: aNAME: bNAME: cNAME: dNAME: eNAME: pKIND: CONSTANTKIND: CONSTANTKIND: VARIABLEKIND: VARIABLEKIND: VAEIABLEKIND: PROCEDUREVAL: 35VAL: 49LEVEL: LEVLEVEL: LEVLEVEL: LEVLEVEL: LEVADR: DXADR: DX+1ADR: DX+2ADR: NAME: g。KIND: VARIABLE 。 。 。LEVEL: LEV+1。ADR: DX。 。對(duì)于過程名的ADR域，是在過程體的目標(biāo)代碼生成后返填過程體的入口地址。TABLE表的索引TX和層次單元LEV都是以BLOCK的參數(shù)形式出現(xiàn)，在主程序調(diào)用BLOCK時(shí)實(shí)參的值為0。每個(gè)過程的相對(duì)起始位置在BLOCK內(nèi)置初值DX=3。2語(yǔ)句處理和代碼生成 對(duì)語(yǔ)句逐句分析，語(yǔ)法正確則生目標(biāo)代碼,當(dāng)遇到標(biāo)識(shí)符的引用則去查TABLE表,看是否有過正確的定義，若有則從表中取出相關(guān)的信息,供代碼生成用。PL/0語(yǔ)言的代碼生成是由過程GEN完成。GEN過程有三個(gè)參數(shù)，分別代表目標(biāo)代碼的功能碼、層差、和位移量。生成的目標(biāo)代碼放在數(shù)組CODE中。CODE是一維數(shù)組，數(shù)組元素是結(jié)構(gòu)體類型數(shù)據(jù)。PL/0語(yǔ)言的目標(biāo)指令是一種假想的棧式計(jì)算機(jī)的匯編語(yǔ)言，其格式如下：f l a其中f代表功能碼，l代表層次差，a代表位移量。目標(biāo)指令有8條： LIT：將常數(shù)放到運(yùn)棧頂，a域?yàn)槌?shù)。 LOD：將變量放到棧頂。a域?yàn)樽兞吭谒f明層中的相對(duì)位置，l為調(diào)用層與說明層的層差值。 STO：將棧頂?shù)膬?nèi)容送到某變量單元中。a,l域的含義與LOD的相同。 CAL：調(diào)用過程的指令。a為被調(diào)用過程的目標(biāo)程序的入中地址，l為層差。 INT：為被調(diào)用的過程（或主程序）在運(yùn)行棧中開辟數(shù)據(jù)區(qū)。a域?yàn)殚_辟的個(gè)數(shù)。 JMP：無條件轉(zhuǎn)移指令，a為轉(zhuǎn)向地址。 JPC：條件轉(zhuǎn)移指令，當(dāng)棧頂?shù)牟紶栔禐榉钦鏁r(shí)，轉(zhuǎn)向a域的地址，否則順序執(zhí)行。 OPR：關(guān)系和算術(shù)運(yùn)算。具體操作由a域給出。運(yùn)算對(duì)象為棧頂和次頂?shù)膬?nèi)容進(jìn)行運(yùn)算，結(jié)果存放在次頂。a域?yàn)?時(shí)是退出數(shù)據(jù)區(qū)。三 建立一個(gè)解釋執(zhí)行目標(biāo)程序的函數(shù)編譯結(jié)束后，記錄源程序中標(biāo)識(shí)符的TABLE表已退出內(nèi)存，內(nèi)存中只剩下用于存放目標(biāo)程序的CODE數(shù)組和運(yùn)行時(shí)的數(shù)據(jù)區(qū)S。S是由解釋程序定義的一維整型數(shù)組。解釋執(zhí)行時(shí)的數(shù)據(jù)空間S為棧式計(jì)算機(jī)的存儲(chǔ)空間。遵循后進(jìn)先出的規(guī)則，對(duì)每個(gè)過程（包括主程序）當(dāng)被調(diào)用時(shí)，才分配數(shù)據(jù)空間，退出過程時(shí)，則所分配的數(shù)據(jù)空間被釋放。為解釋程序定義四個(gè)寄存器：1 I：指令寄存器，存放當(dāng)前正在解釋的一條目標(biāo)指令。2 P：程序地址寄存器，指向下一條要執(zhí)行的目標(biāo)指令（相當(dāng)于CODE數(shù)組的下標(biāo)）。3 T：棧頂寄存器，每個(gè)過程運(yùn)行時(shí)要為它分配數(shù)據(jù)區(qū)（或稱為數(shù)據(jù) 段），該數(shù)據(jù)區(qū)分為兩部分。靜態(tài)部分：包括變量存放區(qū)和三個(gè)聯(lián)單元。動(dòng)態(tài)部分：作為臨時(shí)工作單元和累加器用。需要時(shí)臨時(shí)分配，用完立即釋放。棧頂寄存器T指出了當(dāng)前棧中最新分配的單元（T也是數(shù)組S的下標(biāo)）。4 B：基地址寄存器，指出每個(gè)過程被調(diào)用時(shí)，在數(shù)據(jù)區(qū)S中給出它分配的數(shù)據(jù)段起始地址，也稱為基地址。每個(gè)過程被調(diào)用時(shí)，在棧頂分配三個(gè)聯(lián)系單元。這三個(gè)單元的內(nèi)容分別是：SL：靜態(tài)鏈，它是指向定義該過程的直接外過程運(yùn)行時(shí)數(shù)據(jù)段的基地址。DL：動(dòng)態(tài)鏈，它是指向調(diào)用該過程前正在運(yùn)行過程的數(shù)據(jù)段的基地址。RA：返回地址，記錄調(diào)用該過程時(shí)目標(biāo)程序的斷點(diǎn)，即當(dāng)時(shí)的程序地址寄存器P的值。 具體的過程調(diào)用和結(jié)束，對(duì)上述寄存器及三個(gè)聯(lián)系單元的填寫和恢復(fù)由下列目標(biāo)指令完成。1 INT 0 aa:為局部量個(gè)數(shù)加32 OPR 0 0恢復(fù)調(diào)用該過程前正在運(yùn)行過程（或主程序）的數(shù)據(jù)段的基地址寄存器的值，恢復(fù)棧頂寄存器T的值，并將返回地址送到指令寄存器P中。3 CAL l aa為被調(diào)用過程的目標(biāo)程序的入口，送入指令地址寄存器P中。CAL指令還完成填寫靜態(tài)鏈，動(dòng)態(tài)鏈，返回地址，給出被調(diào)用過程的基地址值，送入基址寄存器B中。 例：一個(gè)Pl/0源程序及生成的目標(biāo)代碼：const a=10;var b,c;procedure p;begin c:=b+aend;2 int 0 33 lod 1 34 lit 0 105 opr 0 26 sto 1 47 opr 0 0begin read(b); while b#0 do begin call p; write(2*c); read(b) endend .8 int 0 59 opr 0 1610