編譯原理實習題.doc

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