PL_0_語言編譯器分析實(shí)驗(yàn)報(bào)告

1、PL/0 語言編譯器分析實(shí)驗(yàn)一、實(shí)驗(yàn)?zāi)康耐ㄟ^閱讀與解析一個(gè)實(shí)際編譯器 （PL/0 語言編譯器） 的源代碼，加深對編譯階段（包括詞法分析、語法分析、語義分析、中間代碼生成等）和編譯系統(tǒng)軟件結(jié)構(gòu)的理解，并達(dá)到提高學(xué)生學(xué)習(xí)興趣的目的。二、實(shí)驗(yàn)要求(1) 要求掌握基本的程序設(shè)計(jì)技巧（ C語言）和閱讀較大規(guī)模程序源代碼的能力；(2) 理解并掌握編譯過程的邏輯階段及各邏輯階段的功能；(3) 要求能把握整個(gè)系統(tǒng)（ PL/0 語言編譯器）的體系結(jié)構(gòu)，各功能模塊的功能，各模塊之間的接口；(4) 要求能總結(jié)出實(shí)現(xiàn)編譯過程各邏輯階段功能采用的具體算法與技三、實(shí)驗(yàn)報(bào)告pl/0 語言是 pascal 語言的一個(gè)子集，

2、我們這里分析的 pl/0 的編譯程序包括了對 pl/0 語言源程序進(jìn)行分析處理、編譯生成類 pcode代碼，并在虛擬機(jī)上解釋運(yùn)行生成的類 pcode代碼的功能。pl/0 語言編譯程序采用以語法分析為核心、 一遍掃描的編譯方法。 詞法分析和代碼生成作為獨(dú)立的子程序供語法分析程序調(diào)用。 語法分析的同時(shí)， 提供了出錯(cuò)報(bào)告和出錯(cuò)恢復(fù)的功能。在源程序沒有錯(cuò)誤編譯通過的情況下，調(diào)用類 pcode 解釋程序解釋執(zhí)行生成的類 pcode代碼。詞法分析子程序分析：詞法分析子程序名為 getsym，功能是從源程序中讀出一個(gè)單詞符號 （token ），把它的信息放入全局變量 sym、id 和num中，語法分析器需要

3、單詞時(shí)， 直接從這三個(gè)變量中獲得。（注意！語法分析器每次用完這三個(gè)變量的值就立即調(diào)用 getsym 子程序獲取新的單詞供下一次使用。 而不是在需要新單詞時(shí)才調(diào)用 getsym過程。）getsym過程通過反復(fù)調(diào)用 getch 子過程從源程序過獲取字符， 并把它們拼成單詞。 getch 過程中使用了行緩沖區(qū)技術(shù)以提高程序運(yùn)行效率。詞法分析器的分析過程：調(diào)用 getsym時(shí)，它通過 getch 過程從源程序中獲得一個(gè)字符。如果這個(gè)字符是字母，則繼續(xù)獲取字符或數(shù)字，最終可以拼成一個(gè)單詞，查保留字表，如果查到為保留字，則把 sym變量賦成相應(yīng)的保留字類型值；如果沒有查到，則這個(gè)單詞應(yīng)是一個(gè)用戶自定義的標(biāo)

4、識符（可能是變量名、常量名或是過程的名字），把 sym 置為 ident ，把這個(gè)單詞存入 id 變量。查保留字表時(shí)使用了二分法查找以提高效率。如果 getch 獲得的字符是數(shù)字， 則繼續(xù)用 getch 獲取數(shù)字，并把它們拼成一個(gè)整數(shù)，然后把 sym置為 number，并把拼成的數(shù)值放入 num變量。如果識別出其它合法的符號（比如：賦值號、大于號、小于等于號等），則把sym則成相應(yīng)的類型。如果遇到不合法的字符，把sym置成 nul 。語法分析子程序分析：語法分析子程序采用了自頂向下的遞歸子程序法， 語法分析同時(shí)也根據(jù)程序的語意生成相應(yīng)的代碼， 并提供了出錯(cuò)處理的機(jī)制。 語法分析主要由分程序分析

5、過程（ block ）、常量定義分析過程（ constdeclaration ）、變量定義分析過程（ vardeclaration ）、語句分析過程（ statement ）、表達(dá)式處理過程（expression ）、項(xiàng)處理過程（ term ）、因子處理過程（ factor ）和條件處理過程（ condition ）構(gòu)成。這些過程在結(jié)構(gòu)上構(gòu)成一個(gè)嵌套的層次結(jié)構(gòu)。 除此之外， 還有出錯(cuò)報(bào)告過程（error ）、代碼生成過程（ gen）、測試單詞合法性及出錯(cuò)恢復(fù)過程（ test ）、登錄名字表過程（ enter ）、查詢名字表函數(shù)（ position ）以及列出類 pcode代碼過程（ listc

6、ode ）作過語法分析的輔助過程。由pl/0 的語法圖可知：一個(gè)完整的 pl/0 程序是由分程序和句號構(gòu)成的。 因此，本編譯程序在運(yùn)行的時(shí)候，通過主程序中調(diào)用分程序處理過程 block 來分析分程序部分（分程序分析過程中還可能會(huì)遞歸調(diào)用 block 過程），然后，判斷最后讀入的符號是否為句號。 如果是句號且分程序分析中未出錯(cuò)， 則是一個(gè)合法的 pl/0 程序，可以運(yùn)行生成的代碼， 否則就說明源 pl/0 程序是不合法的， 輸出出錯(cuò)提示即可。語法單元分析：1、分程序處理過程：語法分析開始后，首先調(diào)用分程序處理過程（ block ）處理分程序。過程入口參數(shù)置為： 0層、符號表位置 0、出錯(cuò)恢復(fù)單詞

7、集合為句號、聲明符或語句開始符。進(jìn)入 block 過程后，首先把局部數(shù)據(jù)段分配指針設(shè)為 3，準(zhǔn)備分配 3個(gè)單元供運(yùn)行期存放靜態(tài)鏈 sl 、動(dòng)態(tài)鏈 dl 和返回地址 ra 。然后用 tx0 記錄下當(dāng)前符號表位置并產(chǎn)生一條 jmp指令，準(zhǔn)備跳轉(zhuǎn)到主程序的開始位置，由于當(dāng)前還沒有知到主程序究竟在何處開始， 所以 jmp的目標(biāo)暫時(shí)填為 0，稍后再改。同時(shí)在符號表的當(dāng)前位置記錄下這個(gè) jmp指令在代碼段中的位置。在判斷了嵌套層數(shù)沒有超過規(guī)定的層數(shù)后，開始分析源程序。 首先判斷是否遇到了常量聲明， 如果遇到則開始常量定義，把常量存入符號表。 接下去用同樣的方法分析變量聲明， 變量定義過程中會(huì)用 dx變量記

8、錄下局部數(shù)據(jù)段分配的空間個(gè)數(shù)。然后如果遇到 procedure 保留字則進(jìn)行過程聲明和定義，聲明的方法是把過程的名字和所在的層次記入符號表，過程定義的方法就是通過遞歸調(diào)用 block 過程，因?yàn)槊總€(gè)過程都是一個(gè)分程序。由于這是分程序中的分程序， 因此調(diào)用 block 時(shí)需把當(dāng)前的層次號 lev 加一傳遞給 block 過程。分程序聲明部分完成后，即將進(jìn)入語句的處理，這時(shí)的代碼分配指針 cx 的值正好指向語句的開始位置，這個(gè)位置正是前面的 jmp指令需要跳轉(zhuǎn)到的位置。于是通過前面記錄下來的地址值，把這個(gè) jmp指令的跳轉(zhuǎn)位置改成當(dāng)前 cx的位置。并在符號表中記錄下當(dāng)前的代碼段分配地址和局部數(shù)據(jù)段

9、要分配的大?。?dx的值）。生成一條 int 指令，分配 dx個(gè)空間，作為這個(gè)分程序段的第一條指令。下面就調(diào)用語句處理過程 statement 分析語句。分析完成后，生成操作數(shù)為 0的opr 指令，用于從分程序返回（對于 0層的主程序來說，就是程序運(yùn)行完成，退出）。2、常量定義過程：通過循環(huán)，反復(fù)獲得標(biāo)識符和對應(yīng)的值， 存入符號表。 符號表中記錄下標(biāo)識符的名字和它對應(yīng)的值。3、變量定義過程：與常量定義類似，通過循環(huán)，反復(fù)獲得標(biāo)識符，存入符號表。符號表中記錄下標(biāo)識符的名字、它所在的層及它在所在層中的偏移地址。4、語句處理過程：語句處理過程是一個(gè)嵌套子程序， 通過調(diào)用表達(dá)式處理、 項(xiàng)處理、因子處理

10、等過程及遞歸調(diào)用自己來實(shí)現(xiàn)對語句的分析。 語句處理過程可以識別的語句包括賦值語句、read 語句、write 語句、call 語句、if 語句、while 語句。當(dāng)遇到 begin/end 語句時(shí)，就遞歸調(diào)用自己來分析。分析的同時(shí)生成相應(yīng)的類 pcode指令。5、賦值語句的處理：首先獲取賦值號左邊的標(biāo)識符， 從符號表中找到它的信息， 并確認(rèn)這個(gè)標(biāo)識符確為變量名。然后通過調(diào)用表達(dá)式處理過程算得賦值號右部的表達(dá)式的值并生成相應(yīng)的指令保證這個(gè)值放在運(yùn)行期的數(shù)據(jù)棧頂。 最后通過前面查到的左部變量的位置信息，生成相應(yīng)的 sto 指令，把棧頂值存入指定的變量的空間，實(shí)現(xiàn)了賦值操作。6、read 語句的處理

11、：確定 read 語句語法合理的前提下（否則報(bào)錯(cuò)），生成相應(yīng)的指令：第一條是16號操作的 opr 指令，實(shí)現(xiàn)從標(biāo)準(zhǔn)輸入設(shè)備上讀一個(gè)整數(shù)值，放在數(shù)據(jù)棧頂。第二條是 sto 指令，把棧頂?shù)闹荡嫒?read 語句括號中的變量所在的單元。7、write 語句的處理：與read 語句相似。在語確的前提下， 生成指令：通過循環(huán)調(diào)用表達(dá)式處理過程分析 write 語句括號中的每一個(gè)表達(dá)式，生成相應(yīng)指令保證把表達(dá)式的值算出并放到數(shù)據(jù)棧頂并生成 14號操作的 opr 指令，輸出表達(dá)式的值。最后生成 15號操作的 opr 指令輸出一個(gè)換行。8、call 語句的處理：從符號表中找到 call 語句右部的標(biāo)識符， 獲

12、得其所在層次和偏移地址。 然后生成相應(yīng)的 cal 指令。至于調(diào)用子過程所需的保護(hù)現(xiàn)場等工作是由類 pcode解釋程序在解釋執(zhí)行 cal 指令時(shí)自動(dòng)完成的。9、if 語句的處理：按if 語句的語法，首先調(diào)用邏輯表達(dá)式處理過程處理if 語句的條件，把相應(yīng)的真假值放到數(shù)據(jù)棧頂。接下去記錄下代碼段分配位置（即下面生成的 jpc 指令的位置），然后生成條件轉(zhuǎn)移 jpc 指令（遇 0或遇假轉(zhuǎn)移），轉(zhuǎn)移地址未知暫時(shí)填0。然后調(diào)用語句處理過程處理 then 語句后面的語句或語句塊。 then 后的語句處理完后，當(dāng)前代碼段分配指針的位置就應(yīng)該是上面的 jpc 指令的轉(zhuǎn)移位置。通過前面記錄下的 jpc 指令的位置

13、，把它的跳轉(zhuǎn)位置改成當(dāng)前的代碼段指針位置。10、begin/end 語句的處理：通過循環(huán)遍歷 begin/end 語句塊中的每一個(gè)語句，通過遞歸調(diào)用語句分析過程分析并生成相應(yīng)代碼。11、while 語句的處理：首先用 cx1變量記下當(dāng)前代碼段分配位置，作為循環(huán)的開始位置。然后處理 while 語句中的條件表達(dá)式生成相應(yīng)代碼把結(jié)果放在數(shù)據(jù)棧頂， 再用 cx2變量記下當(dāng)前位置，生成條件轉(zhuǎn)移指令，轉(zhuǎn)移位置未知，填 0。通過遞歸調(diào)用語句分析過程分析 do語句后的語句或語句塊并生成相應(yīng)代碼。 最后生成一條無條件跳轉(zhuǎn)指令jmp，跳轉(zhuǎn)到 cx1所指位置，并把 cx2所指的條件跳轉(zhuǎn)指令的跳轉(zhuǎn)位置改成當(dāng)前代碼段

14、分配位置。12、表達(dá)式、項(xiàng)、因子處理：根據(jù) pl/0 語法可知，表達(dá)式應(yīng)該是由正負(fù)號或無符號開頭、 由若干個(gè)項(xiàng)以加減號連接而成。 而項(xiàng)是由若干個(gè)因子以乘除號連接而成， 因子則可能是一個(gè)標(biāo)識符或一個(gè)數(shù)字， 或是一個(gè)以括號括起來的子表達(dá)式。 根據(jù)這樣的結(jié)構(gòu)， 構(gòu)造出相應(yīng)的過程，遞歸調(diào)用就完成了表達(dá)式的處理。 把項(xiàng)和因子獨(dú)立開處理解決了加減號與乘除號的優(yōu)先級問題。 在這幾個(gè)過程的反復(fù)調(diào)用中， 始終傳遞 fsys 變量的值，保證可以在出錯(cuò)的情況下跳過出錯(cuò)的符號，使分析過程得以進(jìn)行下去。13、邏輯表達(dá)式的處理：首先判斷是否為一元邏輯表達(dá)式： 判奇偶。如果是，則通過調(diào)用表達(dá)式處理過程分析計(jì)算表達(dá)式的值，

15、然后生成判奇指令。 如果不是， 則肯定是二元邏輯運(yùn)算符，通過調(diào)用表達(dá)式處理過程依次分析運(yùn)算符左右兩部分的值， 放在棧頂?shù)膬蓚€(gè)空間中，然后依不同的邏輯運(yùn)算符，生成相應(yīng)的邏輯判斷指令，放入代碼段。14、判斷單詞合法性與出錯(cuò)恢復(fù)過程分析：本過程有三個(gè)參數(shù)， s1、s2為兩個(gè)符號集合， n為出錯(cuò)代碼。本過程的功能是：測試當(dāng)前符號（即 sym變量中的值）是否在 s1集合中，如果不在，就通過調(diào)用出錯(cuò)報(bào)告過程輸出出錯(cuò)代碼 n，并放棄當(dāng)前符號，通過詞法分析過程獲取一下單詞，直到這個(gè)單詞出現(xiàn)在 s1或 s2集合中為止。這個(gè)過程在實(shí)際使用中很靈活，主要有兩個(gè)用法：在進(jìn)入某個(gè)語法單位時(shí)， 調(diào)用本過程，檢查當(dāng)前符號是

16、否屬于該語法單位的開始符號集合。若不屬于，則濾去開始符號和后繼符號集合外的所有符號。在語法單位分析結(jié)束時(shí)， 調(diào)用本過程，檢查當(dāng)前符號是否屬于調(diào)用該語法單位時(shí)應(yīng)有的后繼符號集合。 若不屬于，則濾去后繼符號和開始符號集合外的所有符號。通過這樣的機(jī)制， 可以在源程序出現(xiàn)錯(cuò)誤時(shí)， 及時(shí)跳過出錯(cuò)的部分， 保證語法分析可以繼續(xù)下去。15、類 pcode代碼解釋執(zhí)行過程分析：這個(gè)過程模擬了一臺(tái)可以運(yùn)行類 pcode指令的棧式計(jì)算機(jī)。它擁有一個(gè)棧式數(shù)據(jù)段用于存放運(yùn)行期數(shù)據(jù)、擁有一個(gè)代碼段用于存放類 pcode程序代碼。同時(shí)還擁用數(shù)據(jù)段分配指針、指令指針、指令寄存器、局部段基址指針等寄存器。16、解釋執(zhí)行類 p

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