編譯原理chpt2PL0

1、第二章第二章 PL/0PL/0編譯程序的實現(xiàn)編譯程序的實現(xiàn)本章以本章以PL/0PL/0編譯程序編譯程序為實例為實例, , 使大家對編譯程序的實現(xiàn)建立起整體概念，對編譯程序的構(gòu)造得到一些感性認(rèn)識和初步了解。1 PL/0PL/0語言語言2 PL/0PL/0處理機處理機假想棧式機假想棧式機3 PL/0PL/0編譯程序編譯程序4 4 符號表的一般形式討論符號表的一般形式討論5 5 棧式存儲管理的再討論棧式存儲管理的再討論1 PL/0PL/0語言語言PL/0PL/0功能簡單、結(jié)構(gòu)清晰、可讀性強，而又具備了一功能簡單、結(jié)構(gòu)清晰、可讀性強，而又具備了一般高級語言的必備部分，因而其編譯程序能充分體般高級語言的

2、必備部分，因而其編譯程序能充分體現(xiàn)一個高級語言編譯程序的基本技術(shù)和步驟?，F(xiàn)一個高級語言編譯程序的基本技術(shù)和步驟。zPL/0PL/0語言：語言：PASCALPASCAL語言的語言的子集，用于教學(xué)子集，用于教學(xué)zPL/0PL/0程序示例程序示例zPL/0PL/0的的語法描述圖語法描述圖zPL/0PL/0語言語言的的EBNFEBNF表示表示 PL/0PL/0語言是語言是PASCALPASCAL語言的語言的子集子集z 過程可過程可嵌套定義，內(nèi)層嵌套定義，內(nèi)層可引用包圍它的外層定義的可引用包圍它的外層定義的標(biāo)識符標(biāo)識符, ,可遞歸調(diào)用可遞歸調(diào)用z 數(shù)據(jù)類型數(shù)據(jù)類型, ,只有整型只有整型z 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)

3、構(gòu) , ,只有簡變和常數(shù)只有簡變和常數(shù)z 標(biāo)識符的有效長度是標(biāo)識符的有效長度是1010z 語句種類：語句種類： begin/endbegin/end、ifif、whilewhile、賦值、賦值、read/writeread/write、callcall、constconst、varvar、procedureprocedurez 過程無參，最多可過程無參，最多可嵌套嵌套三層三層z 1313個保留字：個保留字：ifif、thenthen、whilewhile、dodo、readread、writewrite、callcall、beginbegin、endend、constconst、varvar、

4、procedureprocedure、oddoddz + +、- -、* *、/ /、= =、 、= 、=、( (、) ) PL/0PL/0程序示例程序示例 CONST A=10; CONST A=10; （* * 常量說明部分常量說明部分 * *） VAR B,C; VAR B,C; （* * 變量變量說明部分說明部分 * *） PROCEDURE PROCEDURE P; P; （* * 過程過程說明部分說明部分 * *） VAR D;VAR D;（* * P P的局部變量的局部變量說明部分說明部分 * *） PROCEDURE PROCEDURE Q; Q; （* * P P的局部過程的

5、局部過程說明部分說明部分 * *） VAR X;VAR X; BEGINBEGIN READ(X); READ(X); D:=X; D:=X; IF X#0 DO CALL P; IF X#0 DO CALL P; END; END; BEGINBEGIN CALL Q; WRITE(D); CALL Q; WRITE(D); END; END; BEGIN CALL P; END.BEGIN CALL P; END.遞歸計算 sum = 1! + 2 ! + . + n! var n, m, fact, sum; 遞規(guī)計算 fact = m! procedure factorial;begi

6、n if m 0 then begin fact := fact * m; m := m - 1; call factorial; end;end;begin 讀入n read(n); sum := 0; while n 0 do begin m := n; fact := 1; call factorial; sum := sum + fact; n := n - 1; end; 輸出n ! write(sum);end.constidentnumbervaridentprocedureident分程序分程序語句語句分程序分程序程序程序分程序分程序.語法圖語法圖identreadend語句語

7、句表達式表達式：=begin語句語句語句語句)(ident,PL/0PL/0語言的語言的EBNFEBNF表示表示z BNFBNF（BACKUS-NAUR FORMBACKUS-NAUR FORM）與與EBNFEBNF的介紹的介紹BNFBNF是根據(jù)美國的是根據(jù)美國的John W.BackusJohn W.Backus與丹麥的與丹麥的Peter NaurPeter Naur來命名的，它是從來命名的，它是從語法上描述程序設(shè)計語言的語法上描述程序設(shè)計語言的元語言元語言。采用。采用BNFBNF就可說明哪些符號序列是對就可說明哪些符號序列是對于某給定語言于某給定語言在語法上在語法上有效的程序。有效的程序。

8、z 構(gòu)成構(gòu)成EBNFEBNF的元素：非終結(jié)符，終結(jié)符，開始符，規(guī)則的元素：非終結(jié)符，終結(jié)符，開始符，規(guī)則z EBNFEBNF的元符號：的元符號： 用左右尖括號括起來的內(nèi)容為用左右尖括號括起來的內(nèi)容為非終結(jié)符非終結(jié)符= =或或 讀做讀做定義為定義為，的的左部由左部由右部右部定義定義 | | 讀做讀做或或 表示右部候選內(nèi)容表示右部候選內(nèi)容 表示花括號內(nèi)的內(nèi)容表示花括號內(nèi)的內(nèi)容可重復(fù)可重復(fù)任意次或限定次數(shù)任意次或限定次數(shù) 表示方括號內(nèi)的內(nèi)容為表示方括號內(nèi)的內(nèi)容為任選項任選項 ( ) ( ) 表示圓括號內(nèi)的內(nèi)容表示圓括號內(nèi)的內(nèi)容優(yōu)先優(yōu)先PL/0PL/0語言文法的語言文法的EBNFEBNF表示表示程序-

9、分程序.分程序-常量說明部分-CONST常量定義部分，常量定義；無符號整數(shù)-數(shù)字?jǐn)?shù)字變量說明部分-VAR標(biāo)識符，標(biāo)識符；標(biāo)識符-字母字母|數(shù)字 B-C-B -先調(diào)用，后結(jié)束B區(qū)A區(qū)B區(qū)C區(qū)BT 二、運行時數(shù)據(jù)的存儲與訪問-棧式存儲假設(shè)A、C同層，且A中嵌套B子程序的調(diào)用、執(zhí)行和返回l 過程被調(diào)用時，子程序的每次調(diào)用都需在數(shù)據(jù)棧頂為其分配獨立的數(shù)據(jù)區(qū)l 子程序返回時，需做兩件事情：一是代碼返回（需記住RA），二是數(shù)據(jù)區(qū)的同步恢復(fù)（DL）l 子程序運行時，要存取外層數(shù)據(jù)區(qū)中的存儲單元當(dāng)前B數(shù)據(jù)區(qū)須記?。悍祷氐刂稲A動態(tài)鏈DL記錄調(diào)用者數(shù)據(jù)區(qū)基地址 靜態(tài)鏈SL記錄定義該過程的直接外層過程數(shù)據(jù)區(qū)的基地

10、址，以便訪問外層數(shù)據(jù)運行時數(shù)據(jù)棧運行時數(shù)據(jù)棧S S的變化的變化 var m1,m2,m3;var m1,m2,m3; Procedure A; Procedure A; var a1; var a1; procedure B; procedure B; var b1,b2; var b1,b2; procedure C; procedure C; C C過程過程call B;call B; r1r1: : B B過程過程call C; call C; r2:r2: A A過程過程call B; call B; r3:r3: 主程序主程序Call A; Call A; r4:r4: B的臨時單元

11、 b2=120 b1=50 RA: r1 DL:115 SL:106 RA: r2 DL:110 SL:110 b2=25 b1=20 RA: r3 DL:106 SL:106 a1=15 RA: r4 DL:100 SL:100 m3=118 m2=472 m1=335 RA:0 DL:0 T B SL:0 100 三、PL/0機的指令系統(tǒng) f: 功能碼l: 層次差 （標(biāo)識符引用層減去定義層）a:根據(jù)不同的指令有所區(qū)別f l af l a指令格式：指令格式：所有運算對棧頂?shù)膬蓚€或一個元素進行，并用運算結(jié)果代替原來的運算對象。指指令令功功能能表表( 0) jmp 0 8 轉(zhuǎn)向轉(zhuǎn)向主程序入口主程

12、序入口( 1) jmp 0 2 轉(zhuǎn)向轉(zhuǎn)向過程過程p入口入口( 2) int 0 3 為過程為過程p開辟空間開辟空間( 3) lod 1 3( 4) lit 0 10( 5) opr 0 2( 6) sto 1 4( 7) opr 0 0 退棧并返回調(diào)用點退棧并返回調(diào)用點( 8) int 0 5( 9) opr 0 16 (10) sto 0 3(11) lod 0 3(12) lit 0 0(13) opr 0 9(14) jpc 0 24 條件不滿足轉(zhuǎn)條件不滿足轉(zhuǎn)24(15) cal 0 2 (16) lit 0 2(17) lod 0 4(18) opr 0 4(19) opr 0 14(

13、20) opr 0 15 換行換行(21) opr 0 16(22) sto 0 3(23) jmp 0 11(24) opr 0 0 SL 0DL 0RA 0變量變量b變量變量cRA 16SL 0DL 0運行棧運行棧c o n s t a = 1 0 ;v a r b , c ;p r o c e d u r e p ; begin c : = b + a ; end;begin r e a d ( b ) ; while b#0 do begin c a l l p ; w r i t e ( 2 * c ) ; r e a d ( b ) ; endend.SL：靜態(tài)鏈：靜態(tài)鏈DL：動態(tài)

14、鏈：動態(tài)鏈RA：返回地址：返回地址0演示執(zhí)行過程3 PL/0PL/0編譯程序的實現(xiàn)編譯程序的實現(xiàn)zPL/0PL/0編譯程序的總體設(shè)計編譯程序的總體設(shè)計zPL/0PL/0編譯程序詞法分析的設(shè)計與實現(xiàn)編譯程序詞法分析的設(shè)計與實現(xiàn)zPL/0PL/0編譯程序語法分析的設(shè)計與實現(xiàn)編譯程序語法分析的設(shè)計與實現(xiàn)zPL/0PL/0編譯程序語義分析的設(shè)計與實現(xiàn)編譯程序語義分析的設(shè)計與實現(xiàn)zPL/0PL/0編譯程序語法錯誤處理的實現(xiàn)編譯程序語法錯誤處理的實現(xiàn)zPL/0PL/0編譯程序代碼生成的實現(xiàn)編譯程序代碼生成的實現(xiàn)zpcodepcode代碼解釋器的設(shè)計與實現(xiàn)代碼解釋器的設(shè)計與實現(xiàn)3.1 PL/03.1 PL/

15、0編譯程序的總體設(shè)計編譯程序的總體設(shè)計z 單趟方式z 以語法、語義分析程序為核心，詞法分析程序和代碼生成程序都作為一個過程，當(dāng)語法分析需要讀單詞時就調(diào)用詞法分析程序，而當(dāng)語法、語義分析正確，需要生成相應(yīng)的目標(biāo)代碼時，則調(diào)用代碼生成程序。z 表格管理程序?qū)崿F(xiàn)變量，常量和過程標(biāo)識符的信息的登錄與查找。z 出錯處理程序，對詞法和語法、語義分析遇到的錯誤給出在源程序中出錯的位置和與錯誤 性質(zhì)有關(guān)的編號，并進行錯誤恢復(fù)。PL/0PL/0編譯程序編譯程序PL/0PL/0編譯程序編譯程序類類 p pcodecode解釋解釋程序程序類類 pcode代碼代碼PL/0源程序源程序輸入數(shù)據(jù)輸入數(shù)據(jù)輸出數(shù)據(jù)輸出數(shù)據(jù)P

16、L/0編譯程序的結(jié)構(gòu)框架 PL/0PL/0編譯程序的結(jié)構(gòu)編譯程序的結(jié)構(gòu)詞法分析程詞法分析程序序語法語義分析程序語法語義分析程序代碼生成程序代碼生成程序表格管理程序表格管理程序出錯處理程序出錯處理程序PL/0PL/0源程序源程序目標(biāo)程序目標(biāo)程序編譯系統(tǒng)總體流程圖編譯系統(tǒng)總體流程圖PL/0編譯程序語法、語義分析的核心3.2 PL/0編譯程序詞法分析的實現(xiàn)詞法分析函數(shù)詞法分析函數(shù)getsym()getsym()所識別的單詞：所識別的單詞：y保留字或關(guān)鍵字：如：保留字或關(guān)鍵字：如：BEGINBEGIN、 ENDEND、 IFIF、 THENTHEN等等y運算符運算符： 如：如：+ +、- -、* *、

17、/ /、：、：= =、# #、=、=等等y標(biāo)識符標(biāo)識符： 用戶定義的變量名、常數(shù)名、過程名用戶定義的變量名、常數(shù)名、過程名y常數(shù)常數(shù)： 如：如：1010、2525、100100等整數(shù)等整數(shù)y界符界符： 如：如：, ,、. . 、; ; 、( ( 、) )等等詞法分析過程詞法分析過程: :getsym()getsym()框圖（框圖（P19P19圖圖2.52.5）在編譯程序中，單詞的表示方式在編譯程序中，單詞的表示方式：（：（sym, id/numsym, id/num）z enum symbol enum symbol nulnul, ,identident, ,numbernumber, ,p

18、lusplus, , ,varsymvarsym, ,procsymprocsym；z 當(dāng)識別出標(biāo)識符時先查當(dāng)識別出標(biāo)識符時先查保留字保留字表表z 保留保留字及內(nèi)部表示對應(yīng)表字及內(nèi)部表示對應(yīng)表： char wordnorwal; char wordnorwal; enum symble wsymnorw; enum symble wsymnorw;z 字符對應(yīng)的字符對應(yīng)的單詞表：單詞表： enum symble ssym256;enum symble ssym256; ssym ssym+ +=plusplus; ssym; ssym- -=minusminus; ; z 詞法分析通過三個詞法

19、分析通過三個全程量全程量 symbol symbol symsym; char id; int ; char id; int numnum; ;將識別出的單詞信息將識別出的單詞信息傳遞傳遞給給語法分析語法分析程序。程序。ysymsym：存放單詞的類別：存放單詞的類別 如：如：initial:= 60initial:= 60；中各單詞對應(yīng)的類別為：；中各單詞對應(yīng)的類別為： initial initial identident, , :=:= becomesbecomes, 60 , 60 numbernumber, , ; ; semicolonsemicolonyidid：存放用戶標(biāo)識符：存放

20、用戶標(biāo)識符, ,對對initialinitial（sym-sym-identident，id-id-initialinitial）ynumnum：存放用戶定義的數(shù)：存放用戶定義的數(shù) 對對6060（sym-sym-number,number,num-num-6060）用狀態(tài)轉(zhuǎn)換圖實現(xiàn)詞法分析程序的設(shè)計方法用狀態(tài)轉(zhuǎn)換圖實現(xiàn)詞法分析程序的設(shè)計方法狀態(tài)狀態(tài)，對應(yīng)每個狀態(tài)編一段程序，對應(yīng)每個狀態(tài)編一段程序，每個狀態(tài)每個狀態(tài)調(diào)用調(diào)用取字符取字符程程序，根據(jù)當(dāng)前字符序，根據(jù)當(dāng)前字符轉(zhuǎn)到不同的狀態(tài)，并做相應(yīng)操作。轉(zhuǎn)到不同的狀態(tài)，并做相應(yīng)操作。表示表示終態(tài)終態(tài)，已，已識識別出一個別出一個單詞單詞1 12 23

21、35 514141313121210109 97 78 86 64 41111空格空格字母字母字母數(shù)字字母數(shù)字非字母數(shù)字非字母數(shù)字?jǐn)?shù)字?jǐn)?shù)字?jǐn)?shù)字?jǐn)?shù)字非數(shù)字非數(shù)字：= = = =非非= =, + - ( 3.3 PL/03.3 PL/0編譯程序語法分析編譯程序語法分析z語法分析的設(shè)計與實現(xiàn)語法分析的設(shè)計與實現(xiàn)y 自頂向下的語法分析自頂向下的語法分析y 遞歸子程序法遞歸子程序法（遞歸下降分析器（遞歸下降分析器recursive-descent parser）：對應(yīng)對應(yīng)每個非終結(jié)符每個非終結(jié)符（語法成分），（語法成分），編一個獨立的處理子程序。編一個獨立的處理子程序。 由由 開始，按規(guī)則右部開始，按規(guī)

22、則右部(語法描述圖語法描述圖箭頭箭頭方向方向)進行分析進行分析 遇到遇到非終結(jié)符非終結(jié)符，則，則調(diào)用調(diào)用相應(yīng)的相應(yīng)的處理過程處理過程 遇到遇到終結(jié)符終結(jié)符，則判斷當(dāng)前讀入的單詞是否與該終結(jié)符，則判斷當(dāng)前讀入的單詞是否與該終結(jié)符相匹相匹配配，若匹配，再讀取下一個單詞繼續(xù)分析。，若匹配，再讀取下一個單詞繼續(xù)分析。 程序程序 pl/0分程序分程序 block語句語句statement條件條件condition表達式表達式expression 項項term因子因子 factor語語法法調(diào)調(diào)用用關(guān)關(guān)系系圖圖VAR A;VAR A;BEGINBEGIN READ(A) READ(A)END.END. .

23、. VARVAR ； A A BEGINBEGIN ENDEND READREAD （ ） A A 為文法的為文法的開始符號開始符號，以開，以開始符號作為根結(jié)始符號作為根結(jié)點存在一棵倒掛點存在一棵倒掛著的語法樹。著的語法樹。遞歸下降語法分遞歸下降語法分析過程隱含著對析過程隱含著對對語法樹的前序?qū)φZ法樹的前序遍歷遍歷表達式表達式=+|-+|-項項 （+|-+|-）項項 int expression(bool* fsys, int* ptx, int lev)if(sym=plus | sym=minus) getsymdo; termdo(nxtlev, ptx, lev); /處理項 else

24、termdo(nxtlev, ptx, lev); / 處理項 while (sym=plus | sym=minus)getsymdo; termdo(nxtlev, ptx, lev); / 處理項 return 0;注意一致性：進入每一語法單位處理程序之前，其第一個單詞已讀出，退出時，應(yīng)讀出下一個語法單位的第一個單詞項項=因子因子 （* *|/|/）因子因子 int term(bool* fsys, int* ptx, int lev)factordo(nxtlev, ptx, lev); /* 處理因子 */ while(sym=times | sym=slash)getsymdo;

25、factordo(nxtlev, ptx, lev);return 0;因子因子=標(biāo)識符標(biāo)識符| |無符號整數(shù)無符號整數(shù)| |（表達式表達式）int factor(bool* fsys, int* ptx, int lev)if(sym = ident)/* 因子為常量或變量 */ getsymdo; else if(sym = number) getsymdo; else if (sym = lparen)/* 因子為表達式 */ getsymdo; expressiondo(nxtlev, ptx, lev); if (sym = rparen) getsymdo; else error(

26、22);/* 缺少右括號 */ return 0;3.4 PL/03.4 PL/0語義分析的設(shè)計與實現(xiàn)語義分析的設(shè)計與實現(xiàn)z 說明部分的分析說明部分的分析與處理與處理z 表格管理表格管理z 過程體過程體( (語句）的分析語句）的分析與處理與處理說明部分的分析說明部分的分析與處理與處理-登錄符號表登錄符號表z 對每個過程（含主程序）對每個過程（含主程序）說明的對象說明的對象（變量變量，常量常量和和過程過程）造符號表造符號表z 登錄登錄標(biāo)識符的標(biāo)識符的屬性屬性。z 標(biāo)識符的屬性標(biāo)識符的屬性: :種類，所在種類，所在層次層次, ,值值和分配的和分配的相對位置相對位置。z 登錄信息由登錄信息由ENTE

27、RENTER過程完成。過程完成。符號表結(jié)構(gòu)enum object constant, variable, procedur;struct tablestruct char nameal; enum object kind; int val, level, adr, size; tabletxmax; const a=35;/const a=35;/常量常量無無層次層次var a1,a2,a3;var a1,a2,a3;Procedure P;Procedure P; var b1,b2; var b1,b2; procedure P1; procedure P1; var c; var c;

28、procedure P2; procedure P2; var d; var d; 注意：在單趟編譯中，對于并列的函數(shù)（或分程序），其相注意：在單趟編譯中，對于并列的函數(shù)（或分程序），其相應(yīng)的符號表不會同時存在。應(yīng)的符號表不會同時存在。過程過程P2在在code的的入口入口 (0) jmp 0 0 CX (1) jmp 0 0 (2) jmp 0 0 (k) jmp 0 0 名字名字 類類 值值 層次層次 地址地址 大小大小: :=varvar， ；if(sym=varsym)/if(sym=varsym)/* * 收到變量聲明符號，開始處理變量聲明收到變量聲明符號，開始處理變量聲明 * */

29、/ getsymdo; getsymdo; dovardeclarationdo(&tx, lev, &dx); dovardeclarationdo(&tx, lev, &dx); while (sym = comma) while (sym = comma) getsymdo; getsymdo; vardeclarationdo(&tx, lev, &dx); vardeclarationdo(&tx, lev, &dx); if (sym = semicolon) if (sym = semicolon) getsymdo

30、; getsymdo; else error(5); else error(5); while (sym = ident); while (sym = ident); 注意：注意：&tx&tx變量說明處理變量說明處理int vardeclaration(intint vardeclaration(int* * ptx,int lev,int ptx,int lev,int* * pdx) pdx)if (sym = ident)if (sym = ident) enter(variable, ptx, lev, pdx);/ enter(variable, ptx, lev,

31、pdx);/填寫名字表填寫名字表 getsymdo; getsymdo; else else error(4); error(4); / /* * var var后應(yīng)是標(biāo)識后應(yīng)是標(biāo)識符符 * */ / return 0;return 0; 過程過程ENTERENTER的實現(xiàn)的實現(xiàn)/ /* * 在名字表中加入一項在名字表中加入一項 * * * * k: k: 名字種類名字種類const,var or procedureconst,var or procedure * * ptx: ptx: 名字表尾指針名字表尾指針 * * lev: lev: 名字所在的層次名字所在的層次, ,以后所有的以后所有

32、的levlev都是這樣都是這樣 * * pdx: pdx: 當(dāng)前應(yīng)分配變量的相對地址，分配后增加當(dāng)前應(yīng)分配變量的相對地址，分配后增加1 1 * */ /void enter(enum object k, intvoid enter(enum object k, int* * ptx,int lev, int ptx,int lev, int* * pdx) pdx)(* *ptx)+;ptx)+; strcpy(table( strcpy(table(* *ptx).name, id); ptx).name, id); / /* * 全局變量全局變量idid中已存有當(dāng)前名字的名字中已存有當(dāng)前名

33、字的名字 * */ / table( table(* *ptx).kind = k;ptx).kind = k; switch (k)switch (k) case constant: case constant: / /* * 常量名字常量名字 * */ / if (num amax) if (num amax) error(31); error(31);/ /* * 數(shù)越界數(shù)越界 * */ / num = 0; num = 0; table( table(* *ptx).val = num;ptx).val = num; break; break; case variable: case

34、variable: / /* * 變量名字變量名字 * */ / table( table(* *ptx).level = lev;ptx).level = lev; table( table(* *ptx).adr = (ptx).adr = (* *pdx);pdx); ( (* *pdx)+;pdx)+; break; break; case procedur: case procedur: / /* *過程名字過程名字* */ / table( table(* *ptx).level = lev;ptx).level = lev; break; break; 過程體的處理過程體的處理變

35、量引用的處理變量引用的處理y對對語句進行語句進行語法語法分析分析y語義分析語義分析 當(dāng)遇到當(dāng)遇到標(biāo)識符的引用時標(biāo)識符的引用時就調(diào)用就調(diào)用POSITIONPOSITION函數(shù)函數(shù)查查TABLETABLE表表，看是否，看是否有有過過正確定義正確定義，若已有，則從表中，若已有，則從表中取相應(yīng)取相應(yīng)的有關(guān)的有關(guān)信息信息，供代碼的生成使用。，供代碼的生成使用。若無定義則錯若無定義則錯。y語義分析語義分析 TABLETABLE表表若已若已有有過過正確定義正確定義，檢查引用與說明的，檢查引用與說明的屬性是否一致，屬性是否一致，若不一致則錯若不一致則錯。y當(dāng)當(dāng)語法語義正確時語法語義正確時，就，就生成生成相應(yīng)語

36、句功能的相應(yīng)語句功能的目標(biāo)代碼目標(biāo)代碼intint position( position(charchar* * id) id) intint i; i; strcpy(, id); strcpy(, id); i = tx + 1; i = tx + 1; while while(strcmp(, id) != 0);(strcmp(, id) != 0); return return i; i; / position/ position思考：在造表和查表過程中，如何保證每個過程的局部量不被它的外層引

37、用？賦值賦值語句的處理語句的處理if (sym = ident) if (sym = ident) / /* * 準(zhǔn)備按照賦值語句處理準(zhǔn)備按照賦值語句處理 * */ / i = position(id, i = position(id, * *ptx);ptx); if (i = 0) error(11); if (i = 0) error(11);/ /* * 變量未找到變量未找到 * */ / elseif(tablei.kind != variable) elseif(tablei.kind != variable) error(12); error(12); / /* * 賦值語句格式

38、錯誤賦值語句格式錯誤 * */ / i = 0; i = 0; else. else. gendo(sto,lev-tablei.level,tablei.adr); gendo(sto,lev-tablei.level,tablei.adr); . . 因子因子=標(biāo)識符標(biāo)識符| |無符號整數(shù)無符號整數(shù)| |（表達式表達式）int factor(bool* fsys, int* ptx, int lev) /因子的語義分析if(sym = ident)/* 因子為常量或變量 */i = position(id, *ptx);/* 查找名字 */ if (i = 0) error(11); /*

39、 標(biāo)識符未聲明 */ else switch (tablei.kind) case constant:/* 名字為常量 */ break; case variable: /* 名字為變量 */ break; case procedur:/* 名字為過程 */ error(21); /* 不能為過程名 */3.5 編譯程序的錯誤處理錯誤處理的原則：盡可能準(zhǔn)確指出出錯位置，錯誤性質(zhì)，錯誤處理的原則：盡可能準(zhǔn)確指出出錯位置，錯誤性質(zhì)，盡可能進行校正。盡可能進行校正。PL/0PL/0編譯程序?qū)φZ法錯誤的處理：編譯程序?qū)φZ法錯誤的處理：(1)(1)對于對于易于校正易于校正的錯誤，如丟了逗號，分號等，指出

40、出的錯誤，如丟了逗號，分號等，指出出錯位置，錯位置，加以校正加以校正，繼續(xù)進行分析。，繼續(xù)進行分析。(2)(2)對于對于難于校正難于校正的錯誤，給出錯誤的位置與性質(zhì)，的錯誤，給出錯誤的位置與性質(zhì)，跳過跳過后面的一些單詞后面的一些單詞，直到下一個可以進行正常語法分析的直到下一個可以進行正常語法分析的語法單位語法單位 z 在在進入進入某個某個語法單位語法單位時，時，調(diào)用調(diào)用TESTTEST, ,檢查當(dāng)前符號檢查當(dāng)前符號是否屬于該是否屬于該語法單位的開語法單位的開始符號集合始符號集合。若不屬于，。若不屬于，則則濾去濾去開始開始符號符號和和后跟后跟符符號號集合外集合外的所有符號。的所有符號。z 在在語

41、法單位語法單位分析結(jié)束分析結(jié)束時，時，調(diào)用調(diào)用TESTTEST, ,檢查當(dāng)前符號檢查當(dāng)前符號是否屬于調(diào)用該語法單位是否屬于調(diào)用該語法單位時應(yīng)有的時應(yīng)有的后跟后跟符號集合。符號集合。若不屬于，則若不屬于，則濾去濾去后跟后跟符符號和號和開始開始符號符號集合外集合外的所的所有符號。有符號。 TEST TEST TEST TESTz 開始符號集合 bool declbegsyssymnum,statbegsyssymnum,facbegsyssymnum; declbegsys: constsym,varsym,procsym; statbegsys: beginsym,callsym,ifsym,w

42、hilesym,readsym,writesym; facbegsys: ident,number,lparen;z 后跟符號集合fsys作為參數(shù)： int test(bool* s1, bool* s2, int n); int block(int lev, int tx, bool *fsys); int statement(bool* fsys, int * ptx, int lev); int expression (bool* fsys, int * ptx, int lev); int term (bool* fsys, int * ptx, int lev); int facto

43、r (bool* fsys, int * ptx, int lev);為symble的元素數(shù)32后跟符號集TESTSYM在在S1中中?打印出錯編號打印出錯編號nS1:=S1+S2SYM在在S1中中?GETSYM返回返回YYNNTEST測試過程流程圖測試過程流程圖因子的處理過程因子的處理過程procedure factor(fsys:symset); var i:integer; begin 入口： test(facbegsys,fsys,24); while sym in facbegsys do begin if . 出口： test(fsys,facbegsys,23); end end;

44、Facbegsysy 處理處理ident number lparentestntest后跟符集是逐步補充的，需補充的內(nèi)容與當(dāng)前所處小環(huán)境有關(guān)。對調(diào)用expression(fsys); z 由于write語句的語法write(,); 所以在write語句中調(diào)用expression時后跟符為： expression(rparen,comma+fsys);zfactor的語法：factor=.|( exp ) 在factor中調(diào)用expression時后跟符 expression(rparen+fsys);3.6 代碼生成代碼生成是由過程代碼生成是由過程GENGEN完成。完成。GENGEN有有3 3

45、個個參數(shù)參數(shù)，分別代表目標(biāo)代碼的，分別代表目標(biāo)代碼的功能碼功能碼，層差層差和和位移量位移量。例如。例如 gen(opr,0,16); gen(opr,0,16); gen(sto, gen(sto,levlev- -levellevel,adr),adr) levlev：當(dāng)前：當(dāng)前處理的處理的過程過程層次層次 levellevel：被引用變量或過程所在：被引用變量或過程所在層次層次 CXCX：為目標(biāo)代碼：為目標(biāo)代碼codecode數(shù)組的下標(biāo)指針數(shù)組的下標(biāo)指針代碼結(jié)構(gòu)變換， 地址回填getsym;condition;if sym=thensym then getsym else error(16

46、);cx1:= cx;gen(jpc,0,0)statement( );codecx1.a:=cxIf c then sint main() . if(-1=block(0, 0, nxtlev) . . interpret(); / 調(diào)用解釋執(zhí)行程序 .int block(int lev, int tx, bool* fsys) dx=3; tx0=tx; tabletx.adr=cx; gen(jmp,0,0); /生成轉(zhuǎn)向過程體入口的指令 while (sym = procsym) getsymdo(); if(sym=ident) enter(procedur, &tx, le

47、v, &dx); . if (-1 = block(lev+1, tx, nxtlev) . .3.7 PL/0分程序的處理子程序分程序的處理子程序-block初值為fsysperiod+declbegsys+statbegsys下標(biāo)指針下標(biāo)指針cx，tx和和變量變量dx的作用的作用CX：為目標(biāo)代碼code數(shù)組的下標(biāo)指針。實際上目標(biāo)代碼的順序是內(nèi)層過程的在前邊，主程序的目標(biāo)代碼在最后。tx ：table表的下標(biāo)指針,是以值參數(shù)形式使用的。dx: 計算每個變量在運行棧中相對本過程基地址的偏移量 ，放在table表中的adr域，生成目標(biāo)代碼時再放在code中的a域。過程體入口時的處理cod

48、etabletx0.adr.a=cx; /過程入口地址填寫在code中tabletx0.adr=cx; /過程的入口填寫在table中tabletx0.size=dx; /過程占的空間填寫在table中 cx0=cx; /保留過程在code中的入口地址gen(int,0,dx); /生成過程入口指令3.8 類pcode解釋器z目標(biāo)代碼存放在數(shù)組CODE中（程序地址寄存器p）z解釋程序定義一個一維整型數(shù)組S作為運行棧z棧頂寄存器（指針）t，基址寄存器（指針）b，指令寄存器i（當(dāng)前正在解釋的目標(biāo)指令）目標(biāo)代碼的解釋執(zhí)行目標(biāo)代碼的解釋執(zhí)行幾條幾條特殊指令特殊指令在在code中的中的位置位置和和功能功

49、能yINT 0 AINT 0 A在在過程過程目標(biāo)程序的目標(biāo)程序的入口處入口處，開辟開辟A A個單元的數(shù)據(jù)段。個單元的數(shù)據(jù)段。A A為為局局部變量部變量的的個數(shù)個數(shù)+ +3 3。yOPR 0 0OPR 0 0在在過程過程目標(biāo)程序的目標(biāo)程序的出口處出口處，釋放數(shù)據(jù)段釋放數(shù)據(jù)段（退棧），（退棧），恢復(fù)調(diào)恢復(fù)調(diào)用用該過程該過程前前正在運行的過程正在運行的過程的數(shù)據(jù)段的數(shù)據(jù)段基址寄存器基址寄存器B B和和棧頂棧頂寄存器寄存器T T的值，并將的值，并將返回地址返回地址送送到指令地址寄存器到指令地址寄存器P P中。中。yCAL L ACAL L A調(diào)用過程調(diào)用過程，填寫填寫靜態(tài)鏈靜態(tài)鏈、動態(tài)鏈動態(tài)鏈、返回地

50、址返回地址，給出，給出被調(diào)被調(diào)用用過程過程的的基地址基地址值，值，送送入基址寄存器入基址寄存器B B中，目標(biāo)程序的中，目標(biāo)程序的入口入口地址地址A A的值的值送送指令地址寄存器指令地址寄存器P P中，使指令從中，使指令從A A開始執(zhí)行開始執(zhí)行interpret三個寄存器賦初值三個寄存器賦初值t:=0; b:=1; p:=0;主程序的主程序的SL，DL，RA賦初值賦初值s1:=0; s2=0; s3=0;i:=codep;p:=p+1;P=0?返回返回解釋執(zhí)行的流程圖解釋執(zhí)行的流程圖執(zhí)行指令執(zhí)行指令iNY幾條特殊指令的解釋執(zhí)行過程過程出口出口opr 0 0opr 0 0 RA RA DL DL

51、SL SLb. tMtbt=b-1;p=st+3;b=st+2Q調(diào)用過程調(diào)用過程-cal l acal l a st+1=base(l, s, b); 填寫靜態(tài)鏈 st+2=b; 填寫動態(tài)鏈 st+3=p; 填寫返回地址 b=t+1; 被調(diào)用過程的基地址 p=a 過程入口地址a送p /t在int中設(shè)置int base(int l, int * s, int b) int b1; b1:=b; /find base l level down while (l0) b1=sb1; l=l-1; return b1; 4 符號表的一般形式討論1、符號表的作用和內(nèi)容u 語義檢查的依據(jù)；u 目標(biāo)代碼生成

52、階段地址分配的依據(jù)；u 在編譯中，符號表被頻繁使用，表的組織方式對編譯的效率起著十分重要的作用。u 符號表中，包括名字、種類、類型、層次、相對地址、存儲類別等名字的屬性信息，以及動態(tài)數(shù)組的內(nèi)情向量、記錄結(jié)構(gòu)型的成員信息、函數(shù)及過程的形參等結(jié)構(gòu)信息。2、符號表的組織方式：線性表、散列表、樹結(jié)構(gòu)，u 符號表的組織方式必須維持源程序中的作用域信息。u 棧符號表：函數(shù)或分程序的嵌套結(jié)構(gòu)，使得程序中出現(xiàn)的符號的處理（內(nèi)層可引用外層符號、同名變量內(nèi)層優(yōu)先）與棧的操作相一致。一個過程結(jié)束時將釋放相應(yīng)的子符號表-解決作用域檢查問題。3、符號表的操作： 創(chuàng)建符號表：在編譯開始時或進入一個分程序 插入表項：定義時（包括變量和形參定義） 查詢表項：可執(zhí)行語句使用時 修改表項：在獲得新的語義值信息時進行 刪除一個或一組無用的項 釋放符號表的空間：在編譯結(jié)束前或退出一個分程序4、符號表的生存期u 對多遍掃描的編譯程序，不同遍所用的符號表也往往不同。u 編譯中的大部分符號表的生存期是編譯過程，個別特殊表（動態(tài)數(shù)組的內(nèi)情向量等）需保留到運行階段5、符號表實例-單遍掃描program sort(input,output) var a: array0.10 of integer; x: integer; pro