1、第第2 2章章 PL/0PL/0編譯程序編譯程序本章目的：以本章目的：以PL/0PL/0編譯程序編譯程序?yàn)閷?shí)例為實(shí)例, ,學(xué)習(xí)編譯學(xué)習(xí)編譯程序?qū)崿F(xiàn)的基本步驟和相關(guān)技術(shù)程序?qū)崿F(xiàn)的基本步驟和相關(guān)技術(shù)(1) PL/0編譯程序的結(jié)構(gòu)編譯程序的結(jié)構(gòu)(2) PL/0編譯程序的詞法，語法和語義實(shí)現(xiàn)編譯程序的詞法，語法和語義實(shí)現(xiàn)(3) PL/0編譯程序的編譯程序的錯(cuò)誤處理方法錯(cuò)誤處理方法(4) 目標(biāo)代碼生成和目標(biāo)代碼生成和類類pcodepcode代碼解釋器代碼解釋器 1. PL/0編譯程序的結(jié)構(gòu)編譯程序的結(jié)構(gòu) PL/0編譯編譯程序程序 PL/0 語言程序語言程序 類類 pcode 代碼代碼源語言源語言(PL/

2、0)目標(biāo)語言目標(biāo)語言(類類 pcode)實(shí)現(xiàn)語言（實(shí)現(xiàn)語言（C) PL/0 類類 pcode pascal/C PL/0PL/0編譯程序編譯程序類類 p pcodecode解釋解釋程序程序類類 pcode代碼代碼PL/0源程序源程序輸入數(shù)據(jù)輸入數(shù)據(jù)輸出數(shù)據(jù)輸出數(shù)據(jù)PL/0PL/0編譯系統(tǒng)的結(jié)構(gòu)框架編譯系統(tǒng)的結(jié)構(gòu)框架PL/0PL/0語言語言 PL/0 PL/0語言：語言：PASCALPASCAL語言的語言的子集子集 PL/0PL/0程序示例程序示例 PL/0PL/0的的語法描述圖語法描述圖 PL/0PL/0語言語言的的EBNFEBNF表示表示 PL/0 PL/0程序示例程序示例 CONST A=

3、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的局部過程的局部過程說明部分說明部分 * *） VAR X;VAR X; BEGINBEGIN READ(X); READ(X); D:=X; D:=X; WHILE X#0 WHILE

4、 X#0 DO CALL P; DO CALL P; END; END; BEGINBEGIN WRITE(D); WRITE(D); CALL Q; CALL Q; END; END; BEGINBEGIN CALL P; CALL P; END. END.Q過程體過程體p過程體過程體主主程序程序體體 輸入圓柱的半徑和高，計(jì)算一些面積、體積等輸入圓柱的半徑和高，計(jì)算一些面積、體積等z z var r, h, len, a1, a2, volumn;z beginzread(r);zread(h);zzlen := 2 * 3 * r;za1 := 3 * r * r;za2 := a1 +

5、a1 + len * h;zvolumn := a1 * h;zzwrite(len);zwrite(a1);zwrite(a2);zwrite(volumn);z end.計(jì)算最大公約數(shù)計(jì)算最大公約數(shù) l var m, n, r, q;l 計(jì)算計(jì)算m和和n的最大公約數(shù)的最大公約數(shù) l procedure gcd;l beginl while r#0 do l beginl q := m / n;l r := m - q * n;l m := n;l n := r;l endl end;l beginl read(m);l read(n);l 為了方便，規(guī)定為了方便，規(guī)定m = n l if

6、m 0 thenl beginl fact := fact * m;l m := m - 1;l call factorial;l end;l end;l beginl 讀入n l read(n);l sum := 0;l while n 0 dol beginl m := n;l fact := 1;l call factorial;l sum := sum + fact;l n := n - 1;l end;l 輸出n !l write(sum);l end. 程序程序分程序分程序.內(nèi)的文字表示內(nèi)的文字表示語法成分（短語）語法成分（短語）或內(nèi)的文字表示單詞符號(hào)內(nèi)的文字表示單詞符號(hào)程序程序.

7、內(nèi)的文字表示內(nèi)的文字表示語法成分（短語）語法成分（短語）語法圖語法圖constidentnumber=,;varident,;procedureident;分程序分程序語句語句分程序分程序zP13-15PL/0PL/0語言的語言的EBNFEBNF表示表示 構(gòu)成構(gòu)成EBNFEBNF的元素的元素（非終結(jié)符，終結(jié)符，開始符，規(guī)（非終結(jié)符，終結(jié)符，開始符，規(guī)則）則） EBNFEBNF 的元符號(hào)：的元符號(hào)： 用左右尖括號(hào)括起來的內(nèi)容為用左右尖括號(hào)括起來的內(nèi)容為非終結(jié)符非終結(jié)符= = 讀做讀做定義為定義為 = =的的左部由左部由右部右部定義定義 讀做讀做定義為定義為 的的左部由左部由右部右部定義定義 |

8、| 讀做讀做或或 表示右部候選內(nèi)容表示右部候選內(nèi)容 表示花括號(hào)內(nèi)的內(nèi)容表示花括號(hào)內(nèi)的內(nèi)容可重復(fù)可重復(fù)任意次或限任意次或限 定次數(shù)定次數(shù) 表示方括號(hào)內(nèi)的內(nèi)容為表示方括號(hào)內(nèi)的內(nèi)容為任選項(xiàng)任選項(xiàng)( ) ( ) 表示圓括號(hào)內(nèi)的內(nèi)容表示圓括號(hào)內(nèi)的內(nèi)容優(yōu)先優(yōu)先zP15-16例：用例：用EBNFEBNF描述描述 的定義的定義 ： =+|-=+|- =0|1|2|3|4|5|6|7|8|9=0|1|2|3|4|5|6|7|8|9 或或 =+|-=+|-|0|0 =1|2|3|4|5|6|7|8|9 =1|2|3|4|5|6|7|8|9 =0|=0| PL/0PL/0語言是語言是PASCALPASCAL語言的語

9、言的子集子集同同PASCALPASCAL 作用域規(guī)則（內(nèi)層作用域規(guī)則（內(nèi)層可引用包圍它的外層定義的可引用包圍它的外層定義的標(biāo)識(shí)符），標(biāo)識(shí)符），上下文約束，上下文約束， 過程可過程可嵌套定義嵌套定義，可遞歸調(diào)用可遞歸調(diào)用z 數(shù)據(jù)類型數(shù)據(jù)類型, ,只有整型只有整型z 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) , ,只有簡單變量和常數(shù)只有簡單變量和常數(shù)z 數(shù)字最多為數(shù)字最多為1414位位z 標(biāo)識(shí)符的有效長度是標(biāo)識(shí)符的有效長度是1010z 語句種類：語句種類：ifif和和whilewhilez 過程無參，最多可過程無參，最多可嵌套嵌套三層三層 目標(biāo)代碼目標(biāo)代碼類類p-codep-code目標(biāo)代碼目標(biāo)代碼類類p-codep-c

10、ode是是一種一種棧式機(jī)棧式機(jī)的的匯編語言匯編語言。棧式機(jī)系統(tǒng)結(jié)構(gòu)棧式機(jī)系統(tǒng)結(jié)構(gòu): :沒有累加器和寄存器，只有存儲(chǔ)棧指針沒有累加器和寄存器，只有存儲(chǔ)棧指針 所有運(yùn)算都在棧頂（零地址機(jī)）所有運(yùn)算都在棧頂（零地址機(jī)）指令格式：指令格式：f l af l af f功能碼功能碼l l層次差層次差 （標(biāo)識(shí)符（標(biāo)識(shí)符引用層引用層減去減去定義層定義層）a a根據(jù)不同的指令有所區(qū)別根據(jù)不同的指令有所區(qū)別指指令令功功能能表表 const a=10; const a=10;var b,c;var b,c;procedure p;procedure p; beginbegin c:=b+a; c:=b+a; end

11、; end;beginbegin read(b); read(b); while while b#0b#0 do do begin begin call p; call p; write(2 write(2* *c);c); read(b); read(b); end endend.end.( 0) jmp 0 8 ( 0) jmp 0 8 轉(zhuǎn)向轉(zhuǎn)向主程序入口主程序入口( 1) jmp 0 2 ( 1) jmp 0 2 轉(zhuǎn)向轉(zhuǎn)向過程過程p p入口入口( 2)( 2) int 0 3int 0 3 過程過程p p入口入口, ,為過程為過程p p開辟空間開辟空間( 3) lod ( 3) lod

12、1 1 3 3 取變量取變量b b的值到棧頂?shù)闹档綏ｍ? 4) lit 0 10 ( 4) lit 0 10 取常數(shù)取常數(shù)1010到棧頂?shù)綏ｍ? 5) opr 0 2 ( 5) opr 0 2 次棧頂與棧頂相加次棧頂與棧頂相加( 6) sto ( 6) sto 1 1 4 4 棧頂值送變量棧頂值送變量c c中中( 7) ( 7) opr 0 0opr 0 0 退棧并返回調(diào)用點(diǎn)退棧并返回調(diào)用點(diǎn)(16)(16)( 8)( 8) int 0 5 int 0 5 主程序入口開辟主程序入口開辟5 5個(gè)棧空間個(gè)棧空間( 9) opr 0 16 ( 9) opr 0 16 從命令行讀入值置于棧頂從命令行讀入

13、值置于棧頂(10) sto 0 3 (10) sto 0 3 將棧頂值存入變量將棧頂值存入變量b b中中(11) lod 0 3 (11) lod 0 3 將變量將變量b b的值取至棧頂?shù)闹等≈翖ｍ?12) lit 0 0 (12) lit 0 0 將常數(shù)值將常數(shù)值0 0進(jìn)棧進(jìn)棧(13) opr 0 9 (13) opr 0 9 次棧頂與棧頂是否不等次棧頂與棧頂是否不等(14) (14) jpc 0 24jpc 0 24 等時(shí)轉(zhuǎn)等時(shí)轉(zhuǎn)(24)(24)（條件不滿足轉(zhuǎn)條件不滿足轉(zhuǎn)）(15) (15) cal 0 2cal 0 2 調(diào)用過程調(diào)用過程p p(16) lit 0 2 (16) lit 0

14、 2 常數(shù)值常數(shù)值2 2進(jìn)棧進(jìn)棧(17) lod (17) lod 0 0 4 4 將變量將變量c c的值取至棧頂?shù)闹等≈翖ｍ?18) opr 0 4 (18) opr 0 4 次棧頂與棧頂相乘次棧頂與棧頂相乘(2(2* *c)c)(19) opr 0 14 (19) opr 0 14 棧頂值輸出至屏幕棧頂值輸出至屏幕(20) opr 0 15 (20) opr 0 15 換行換行(21) opr 0 16 (21) opr 0 16 從命令行讀取值到棧頂從命令行讀取值到棧頂(22) sto (22) sto 0 0 3 3 棧頂值送變量棧頂值送變量b b中中(23) jmp 0 11 (23

15、) jmp 0 11 無條件轉(zhuǎn)到循環(huán)入口無條件轉(zhuǎn)到循環(huán)入口(11)(11)(24) opr 0 0 (24) opr 0 0 結(jié)束退棧結(jié)束退棧 PL/0PL/0編譯程序的結(jié)構(gòu)編譯程序的結(jié)構(gòu)詞法分析程序詞法分析程序語法語義分析程序語法語義分析程序代碼生成程序代碼生成程序表格管理程序表格管理程序出錯(cuò)處理程序出錯(cuò)處理程序PL/0PL/0源程序源程序目標(biāo)程序目標(biāo)程序PL/0PL/0編譯程序的總體設(shè)計(jì)編譯程序的總體設(shè)計(jì)z以語法以語法、語義分析語義分析程序程序?yàn)楹诵臑楹诵?詞法分析詞法分析程序和程序和代碼生成代碼生成程序都作為一個(gè)程序都作為一個(gè)過程過程，當(dāng)語法分析需要讀單詞時(shí)就調(diào)用詞法分析程序，當(dāng)語法分析

16、需要讀單詞時(shí)就調(diào)用詞法分析程序，而當(dāng)語法而當(dāng)語法、語義分析正確，需要生成相應(yīng)的目標(biāo)語義分析正確，需要生成相應(yīng)的目標(biāo)代碼時(shí)，則調(diào)用代碼生成程序。代碼時(shí)，則調(diào)用代碼生成程序。z表格管理表格管理程序?qū)崿F(xiàn)程序?qū)崿F(xiàn)變量變量，常量常量和和過程過程標(biāo)識(shí)符的標(biāo)識(shí)符的信信息的登錄與查找息的登錄與查找。z出錯(cuò)處理出錯(cuò)處理程序，對(duì)詞法和語法程序，對(duì)詞法和語法、語義分析遇到的語義分析遇到的錯(cuò)誤給出在源程序中錯(cuò)誤給出在源程序中出錯(cuò)的位置出錯(cuò)的位置和與和與錯(cuò)誤錯(cuò)誤 性質(zhì)性質(zhì)有關(guān)有關(guān)的編號(hào)，并進(jìn)行錯(cuò)誤恢復(fù)。的編號(hào)，并進(jìn)行錯(cuò)誤恢復(fù)。 2 PL/0編譯程序的分析工作編譯程序的分析工作 (詞法，語法和語義）詞法，語法和語義） 2

17、.1PL/0PL/0編譯程序詞法分析的實(shí)現(xiàn)編譯程序詞法分析的實(shí)現(xiàn)識(shí)別的單詞：識(shí)別的單詞：y保留字或關(guān)鍵字：如：保留字或關(guān)鍵字：如：BEGINBEGIN、 ENDEND、 IFIF、 THENTHEN等等y運(yùn)算符運(yùn)算符： 如：如：+ +、- -、* *、/ /、：、：= =、# #、=、=等等y標(biāo)識(shí)符標(biāo)識(shí)符： 用戶定義的變量名、常數(shù)名、過程名用戶定義的變量名、常數(shù)名、過程名y常數(shù)常數(shù)： 如：如：1010、2525、100100等整數(shù)等整數(shù)y界符界符： 如：如：, ,、. . 、; ; 、( ( 、) )等等詞法分析過程詞法分析過程GETSYM (p434)GETSYM (p434)所要完成的任務(wù)

18、：所要完成的任務(wù)：y從源程序讀字符（從源程序讀字符（getch)p433getch)p433y濾空格濾空格y識(shí)別識(shí)別保留字保留字y識(shí)別標(biāo)識(shí)符識(shí)別標(biāo)識(shí)符y拼數(shù)拼數(shù)y識(shí)別單字符單詞識(shí)別單字符單詞y拼雙字符單詞拼雙字符單詞z 詞法分析過程詞法分析過程: :GETSYMGETSYM框圖（見教材框圖（見教材p19p19圖圖2.52.5）z 程序（程序（ procedure getsymprocedure getsym） ( (見教材見教材p434)p434)當(dāng)識(shí)別到標(biāo)識(shí)符時(shí)先查當(dāng)識(shí)別到標(biāo)識(shí)符時(shí)先查保留字保留字表表z 保留保留字字表：（表：（ begin (begin (* * main main * *

19、 ) ) ）word1:=word1:=begin begin ；word2:=word2:=callcall ； .word13:=word13:=writewrite ；查到時(shí)找到相應(yīng)的查到時(shí)找到相應(yīng)的內(nèi)部表示內(nèi)部表示W(wǎng)sym1:=beginsym; wsym2:=callsym； wsym13:=writesym；z 字符對(duì)應(yīng)的字符對(duì)應(yīng)的單詞表：單詞表：ssymssym+ +:=:=plusplus; ssym; ssym- -:=:=minusminus; ; ssymssym; ;:=:=semicolonsemicolon; ;z 詞法分析如何把單詞傳遞給語法分析詞法分析如何把單詞

20、傳遞給語法分析 type symbol=(type symbol=(nulnul, ,identident, ,numbernumber, ,plusplus, , ,varsymvarsym, ,procsymprocsym) )；3 3個(gè)個(gè)全程量全程量 SYMSYM:symbol;:symbol;IDID:alfa;:alfa;NUMNUM:integer;:integer; 通過三個(gè)通過三個(gè)全程量全程量 SYMSYM 、IDID和和NUMNUM 將識(shí)別出的單詞信息將識(shí)別出的單詞信息傳遞傳遞給給語語法分析法分析程序。程序。ySYMSYM：存放單詞的類別：存放單詞的類別 如：有程序段落為：如

21、：有程序段落為： begin initial := 60begin initial := 60；endend 對(duì)應(yīng)單詞翻譯后變?yōu)椋簩?duì)應(yīng)單詞翻譯后變?yōu)椋?begin begin beginsymbeginsym, initial , initial identident, ,:= := becomesbecomes, 60 , 60 numbernumber, , ； semicolonsemicolon，end end endsymendsym 。yIDID： 存放用戶所定義的標(biāo)識(shí)符的值存放用戶所定義的標(biāo)識(shí)符的值 如：如： initial initial （在（在SYMSYM中放中放ident

22、ident，在，在IDID中放中放initialinitial）yNUMNUM：存放用戶定義的數(shù)：存放用戶定義的數(shù) 如：如：60 60 y（在（在SYMSYM中放中放number,number,在在NUMNUM中放中放6060）使用狀態(tài)轉(zhuǎn)換圖實(shí)現(xiàn)詞法分析程序的使用狀態(tài)轉(zhuǎn)換圖實(shí)現(xiàn)詞法分析程序的設(shè)計(jì)方法設(shè)計(jì)方法詞法分析程序的設(shè)計(jì)詞法分析程序的設(shè)計(jì)-使用狀態(tài)轉(zhuǎn)換圖實(shí)現(xiàn)使用狀態(tài)轉(zhuǎn)換圖實(shí)現(xiàn)表示表示狀態(tài)狀態(tài)，對(duì)應(yīng)每個(gè)狀態(tài)編一段程序，對(duì)應(yīng)每個(gè)狀態(tài)編一段程序，每個(gè)狀態(tài)每個(gè)狀態(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)，已

23、，已識(shí)別出一個(gè)識(shí)別出一個(gè)單詞單詞。1 12 23 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ù)字：= = = =非非= =, + - ( 2.2 PL/0 2.2 PL/0編譯程序語法分析編譯程序語法分析 自頂向下自頂向下的語法分析的語法分析 遞歸子程序法遞歸子程序法ch5 p92ch5 p92 程序程序分程序分程序.constidentnumber=,;varident,;procedureident;分程序分程序語句語句分程序分程序identreadend;語句語句表達(dá)式表達(dá)式：

24、=begin語句語句語句語句)(ident, 自頂向下的語法分析自頂向下的語法分析VAR A;VAR A;BEGINBEGIN READ(A) READ(A)END.END. . . VARVAR ； A A BEGINBEGIN ENDEND READREAD （ ） A A 為文法的為文法的開始符號(hào)開始符號(hào)，以開，以開始符號(hào)作為根結(jié)始符號(hào)作為根結(jié)點(diǎn)構(gòu)造一棵倒掛點(diǎn)構(gòu)造一棵倒掛著的語法樹。著的語法樹。遞歸子程序法遞歸子程序法- -語法分析程序由一組遞歸過語法分析程序由一組遞歸過程組成程組成對(duì)應(yīng)對(duì)應(yīng)每個(gè)非終結(jié)符（每個(gè)非終結(jié)符（語法單元），編一個(gè)獨(dú)立的語法單元），編一個(gè)獨(dú)立的處理過程（或函數(shù)，子程

25、序）。處理過程（或函數(shù)，子程序）。 由由 （即開始符）開始，沿語法描述即開始符）開始，沿語法描述圖圖箭頭箭頭所指出的方向進(jìn)行分析（規(guī)則右部）所指出的方向進(jìn)行分析（規(guī)則右部） 遇到遇到非終結(jié)符非終結(jié)符（進(jìn)入了又一個(gè)語法單元），（進(jìn)入了又一個(gè)語法單元），則則調(diào)用調(diào)用相應(yīng)的相應(yīng)的處理過程處理過程 遇到遇到終結(jié)符終結(jié)符，則判斷當(dāng)前讀入的單詞是否，則判斷當(dāng)前讀入的單詞是否與該終結(jié)符與該終結(jié)符相匹配相匹配，若匹配，再讀取下一個(gè)單，若匹配，再讀取下一個(gè)單詞繼續(xù)分析。詞繼續(xù)分析。也稱為也稱為遞歸下降分析器（遞歸下降分析器（ recursive-descent parser ） 例：表達(dá)式的語法分析程序（遞歸子

26、程序）例：表達(dá)式的語法分析程序（遞歸子程序）項(xiàng)項(xiàng)表達(dá)式表達(dá)式+-項(xiàng)項(xiàng)+-項(xiàng)項(xiàng) 因子因子 因子因子 */語法圖語法圖因子的語法圖因子的語法圖因子因子identnumber(表達(dá)式表達(dá)式)z 表達(dá)式的表達(dá)式的EBNF表達(dá)式表達(dá)式=+|-+|-項(xiàng)項(xiàng) （+|-+|-）項(xiàng)項(xiàng) 項(xiàng)項(xiàng)=因子因子 （* *|/|/）因子因子 因子因子=標(biāo)識(shí)符標(biāo)識(shí)符| |無符號(hào)整數(shù)無符號(hào)整數(shù)| |（表達(dá)式表達(dá)式）表達(dá)式表達(dá)式=+|-+|-項(xiàng)項(xiàng) （+|-+|-）項(xiàng)項(xiàng) pascalpascalz 表達(dá)式表達(dá)式的分析程序（的分析程序（遞歸子程序）遞歸子程序）procedure procedure exprexpr; ;beginbeg

27、in if sym in if sym in plusplus, , minusminus then then begin begin getsym; getsym; termterm; ; end end else else termterm; ; while sym in while sym in plusplus, , minusminus do do begin begin getsym; getsym; termterm; ; end endend;end; z 項(xiàng)項(xiàng)=因子因子 （* *|/|/）因子因子 pascalpascalz項(xiàng)項(xiàng)的分析程序（的分析程序（遞歸子程序）遞歸子程序）

28、procedure procedure termterm; ;beginbegin factorfactor; ; while sym in while sym in timestimes, , slashslash do do begin begin getsym; getsym; factorfactor; ; end endend;end;因子因子=標(biāo)識(shí)符標(biāo)識(shí)符| |無符號(hào)整數(shù)無符號(hào)整數(shù)| |（表達(dá)式表達(dá)式）z 因子因子的分析程序（的分析程序（遞歸子程序）遞歸子程序）procedure procedure factorfactor; ;begin begin if sym if sym

29、identident then then begin begin if sym if sym numbernumber then then begin begin if sym = if sym = ( ( then then begin begin getsym;getsym; exprexpr; ; if sym = if sym = ) ) then then getsym getsym else error else error end end else error else error end end else getsym else getsym end end else gets

30、ym else getsym end; end;表達(dá)式表達(dá)式=+|-+|-項(xiàng)項(xiàng) （+|-+|-）項(xiàng)項(xiàng) in Cin Cz int expression(bool* fsys, int* ptx, int lev)z zif(sym=plus | sym=minus)/* 開頭的正負(fù)號(hào)，當(dāng)前表達(dá)式被開頭的正負(fù)號(hào)，當(dāng)前表達(dá)式被看作一個(gè)正的或負(fù)的項(xiàng)看作一個(gè)正的或負(fù)的項(xiàng) */zzgetsymdo;ztermdo(nxtlev, ptx, lev);/* 處理項(xiàng)處理項(xiàng) */zzelse/* 此時(shí)表達(dá)式被看作項(xiàng)的加減此時(shí)表達(dá)式被看作項(xiàng)的加減 */zztermdo(nxtlev, ptx, lev);/*

31、處理項(xiàng)處理項(xiàng) */zzwhile (sym=plus | sym=minus)zzgetsymdo;ztermdo(nxtlev, ptx, lev);/* 處理項(xiàng)處理項(xiàng) */zzreturn 0;z 項(xiàng)項(xiàng)=因子因子 （* *|/|/）因子因子 zint term(bool* fsys, int* ptx, int lev)zzfactordo(nxtlev, ptx, lev); /* 處理因處理因子子 */zwhile(sym=times | sym=slash)zgetsymdo;zfactordo(nxtlev, ptx, lev);zzreturn 0;z因子因子=標(biāo)識(shí)符標(biāo)識(shí)符| |

32、無符號(hào)整數(shù)無符號(hào)整數(shù)| |（表達(dá)式表達(dá)式）int factor(bool* fsys, int* ptx, int lev)if(sym = ident)/* 因子為常量或變量因子為常量或變量 */ getsymdo;else if(sym = number)/* 因子為因子為*/ getsymdo; else if (sym = lparen)/* 因子為表達(dá)式因子為表達(dá)式 */ expressiondo(nxtlev, ptx, lev); if (sym = rparen) getsymdo; else error(22);/* 缺少右括號(hào)缺少右括號(hào) */ return 0; = beg

33、inbegin（* *mainmain* *) )( (* *initializeinitialize* *) ) ( (* *r/w file setr/w file set* *) ) getsym; getsym; block( ); block( ); if sym period then error. if sym period then error.end.end.。 程序程序 pl0分程序分程序 block語句語句 statement條件條件 condition表達(dá)式表達(dá)式expression項(xiàng)項(xiàng) term因子因子 factor語語法法調(diào)調(diào)用用關(guān)關(guān)系系圖圖編譯系統(tǒng)總體流程圖編譯系

34、統(tǒng)總體流程圖啟動(dòng)啟動(dòng)置初值置初值調(diào)用G E TSYM取 單 詞調(diào)用G E TSYM取 單 詞調(diào)用B L OCK過 程調(diào)用B L OCK過 程當(dāng)前單詞當(dāng)前單詞是否為源程序結(jié)束符是否為源程序結(jié)束符.？.？出錯(cuò)出錯(cuò)源程序中源程序中是否有錯(cuò)誤？是否有錯(cuò)誤？調(diào)用解釋過程I N T E R P RET調(diào)用解釋過程I N T E R P RET解釋執(zhí)行目標(biāo)程序解釋執(zhí)行目標(biāo)程序打印錯(cuò)誤打印錯(cuò)誤結(jié)束結(jié)束N NY YY YN N2.3 2.3 PL/0PL/0編譯程序語義分析的設(shè)計(jì)與實(shí)現(xiàn)編譯程序語義分析的設(shè)計(jì)與實(shí)現(xiàn) PL/0PL/0編譯程序語法、語義分析的的核心編譯程序語法、語義分析的的核心程序是程序是BLOCK

35、BLOCK過程過程哪些語義分析工作？哪些語義分析工作？如何實(shí)現(xiàn)？如何實(shí)現(xiàn)？-語義分析環(huán)境（符號(hào)表）語義分析環(huán)境（符號(hào)表） z 說明部分的分析說明部分的分析與處理與處理z 表格管理表格管理z 過程體過程體( (語句）的分析語句）的分析與處理與處理因子因子=標(biāo)識(shí)符標(biāo)識(shí)符| |無符號(hào)整數(shù)無符號(hào)整數(shù)| |（表達(dá)式表達(dá)式）語義分析語義分析int factor(bool* fsys, int* ptx, int lev)z if(sym = ident)/* 因子為常量或變量因子為常量或變量 */zzi = position(id, *ptx);/* 查找名字查找名字 */zif (i = 0)zerro

36、r(11);/* 標(biāo)識(shí)符未聲明標(biāo)識(shí)符未聲明 */zzelsezswitch (tablei.kind)zcase constant:/* 名字為常量名字為常量 */zbreak;zcase variable:/* 名字為變量名字為變量 */zbreak;zcase procedur: /* 名字為過程名字為過程 */zerror(21); /* 不能為過程名不能為過程名 */z登錄符號(hào)表登錄符號(hào)表ch9ch9說明部分的分析說明部分的分析與處理與處理對(duì)每個(gè)過程（含主程序）對(duì)每個(gè)過程（含主程序）說明的對(duì)象說明的對(duì)象（變量變量，常量常量和和過程過程）造造符號(hào)表符號(hào)表 登錄登錄標(biāo)識(shí)符的標(biāo)識(shí)符的屬性屬性

37、。 標(biāo)識(shí)符的屬性標(biāo)識(shí)符的屬性: :種類，所在種類，所在層次層次, ,值值和分配的和分配的相對(duì)位置相對(duì)位置。 登錄信息由登錄信息由ENTER(ENTER(見教材見教材p440)p440)過程完成。過程完成。符號(hào)表結(jié)構(gòu)(見教材見教材p455p455)Enum object constant, variable, procedur ;Struct tablestruct char nameal; enum object kind; int val; int level; int adr; int size;Struct tablestruct tabletxmax; 符號(hào)表結(jié)構(gòu)z 說明種類的定義：

38、object= (constant, variable,procedur) （定義定義純量純量/ /枚舉枚舉類型）類型）z 符號(hào)表的定義 table:array0.txmax of record name:alfa; case kind:object of constant:(val:integer); variable:procedur:(level,adr,size: integer); N NA AM ME E：A A N NA AM ME E：B B N NA AM ME E：C C N NA AM ME E：D D N NA AM ME E：E E N NA AM ME E：P P

39、K KI IN ND D：C CO ON NS ST TA AN NT T K KI IN ND D：C CO ON NS ST TA AN NT T K KI IN ND D：V VA AR RI IA AB BL LE E K KI IN ND D：V VA AR RI IA AB BL LE E K KI IN ND D：V VA AR RI IA AB BL LE E K KI IN ND D：P PR RO OC CE ED DU UR R V VA AL L：3 35 5 V VA AL L：4 49 9 L LE EV VE EL L：L LE EV V L LE EV VE E

40、L L：L LE EV V L LE EV VE EL L：L LE EV V L LE EV VE EL L：L LE EV V A AD DR R：D DX X A AD DR R：D DX X+ +1 1 A AD DR R：D DX X+ +2 2 A AD DR R： S SI IZ ZE E：4 4 N NA AM ME E：G G K KI IN ND D：V VA AR RI IA AB BL LE E L LE EV VE EL L：L LE EV V+ +1 1 A AD DR R：D DX X 例程序說明部分為：例程序說明部分為：CONST A=35CONST A=35，

41、B=49B=49； VAR CVAR C，D D，E E； PROCEDURE PPROCEDURE P； VAR G VAR G ； 符號(hào)表符號(hào)表 名字名字 種類種類 層次層次/值值 地址地址 存儲(chǔ)空間存儲(chǔ)空間對(duì)應(yīng)名字表對(duì)應(yīng)名字表txtx ：tabletable表的下標(biāo)指針表的下標(biāo)指針, ,是以是以值參數(shù)值參數(shù)形式使用的。形式使用的。dx: 計(jì)算每個(gè)變量在運(yùn)行棧中相對(duì)本計(jì)算每個(gè)變量在運(yùn)行棧中相對(duì)本過程過程基地址基地址的的偏移量偏移量 ，放在放在table表表中的中的adr域，域，生成生成目標(biāo)代目標(biāo)代碼碼時(shí)再時(shí)再放在放在codecode中的中的a域域變量定義語句的處理變量定義語句的處理(C)(

42、C)語法：語法：: := varvar ， ；程序：程序：if (sym = varsym)if (sym = varsym)/ /* * 收到變量聲明符號(hào)，開始處理變量聲明收到變量聲明符號(hào)，開始處理變量聲明 * */ / getsymdo; getsymdo; do do vardeclarationdo(&tx, lev, &dx); vardeclarationdo(&tx, lev, &dx); while (sym = comma) while (sym = comma) getsymdo; getsymdo; vardeclarationdo(&am

43、p;tx, lev, &dx); vardeclarationdo(&tx, lev, &dx); if (sym = semicolon) if (sym = semicolon) getsymdo; getsymdo; else error(5); else error(5); while (sym = ident); while (sym = ident); 注意：注意：&tx&tx變量說明處理變量說明處理(C)(C)int vardeclaration(intint vardeclaration(int* * ptx,int lev,int pt

44、x,int lev,int* * pdx) pdx) if (sym = ident) if (sym = ident) enter(variable, ptx, lev, pdx);/ enter(variable, ptx, lev, pdx);/填寫名字表填寫名字表 getsymdo; getsymdo; else else error(4); error(4); / /* * var var后應(yīng)是標(biāo)識(shí)后應(yīng)是標(biāo)識(shí)符符 * */ / return 0; return 0; 變量定義語句的處理變量定義語句的處理語法：語法：: := varvar ， ；程序：程序： if sym=if sym

45、=varsymvarsym then then begin begin getsym; getsym; repeat repeat vardeclarationvardeclaration;(;(* *變量說明處理變量說明處理*) while sym=while sym=commacomma do do begin begin getsym; getsym; vardeclarationvardeclaration end; end; if sym= if sym=semicolonsemicolon then then getsym getsym else error(5) else err

46、or(5) until sym until symidentident; ; end; end;變量說明處理變量說明處理 procedure vardeclaration; procedure vardeclaration; beginbegin if sym= if sym=ident ident thenthen begin begin enterenter( (variablevariable);); getsym getsym end end else else error(4) error(4) end( end(* *vardeclarationvardeclaration* *)

47、;);過程過程ENTERENTER的實(shí)現(xiàn)的實(shí)現(xiàn)/ /* * * * 在在符號(hào)符號(hào)表中加入一項(xiàng)表中加入一項(xiàng) * * * * k: k: 名字種類名字種類const,var or procedureconst,var or procedure * * ptx: ptx: 名字表尾指針的指針名字表尾指針的指針 * * lev: lev: 名字所在的層次名字所在的層次, ,以后所有的以后所有的levlev都是這樣都是這樣 * * pdx: pdx: 當(dāng)前應(yīng)分配變量的相對(duì)地址，分配后增加當(dāng)前應(yīng)分配變量的相對(duì)地址，分配后增加1 1 * */ /void enter(enum object k, intvo

48、id enter(enum object k, int* * ptx, ptx, int lev, int int lev, int* * pdx) pdx)過程過程ENTERENTER的實(shí)現(xiàn)的實(shí)現(xiàn)(C)(C) ( (* *ptx)+;ptx)+; strcpy(table( strcpy(table(* *ptx).name, id); ptx).name, id); / /* * 全局變量全局變量idid中已存有當(dāng)前名字的中已存有當(dāng)前名字的值值 * */ / table( table(* *ptx).kind = k;ptx).kind = k; switch (k) switch (k)

49、 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;過程過程ENTERENTER的實(shí)現(xiàn)的實(shí)現(xiàn)(C)(C) case variable: case variable: / /* * 變量名字變量名字 * */ / table( table(* *pt

50、x).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; 過程過程ENTERENTER的實(shí)現(xiàn)的實(shí)現(xiàn)txtx ：tabletable表的指針表的指針 procedure procedure

51、 enterenter( (k k:object );:object ); begin ( begin (* * enter object into table enter object into table * *) ) tx:=tx+1; tx:=tx+1; with tabletx do with tabletx do ( (* * 開域開域語句語句 * *） beginbegin namename:=:=idid;(;(* * 表示表示name:=:=idid; ;* *） kindkind:=:=k k;(;(* * 表示表示tabletx.t

52、abletx.kindkind:=:=k k; ;* * ) )過程過程ENTERENTER的實(shí)現(xiàn)的實(shí)現(xiàn) casecase k k of of constantconstant: : begin begin if if numnumamax thenamax then begin begin error(31); error(31); numnum:=0;:=0; end; end; valval:=:=numnum;(;(* * tabletx.tabletx.valval:=:=numnum; ;* *) ) end; end;過程過程ENTERENTER的實(shí)現(xiàn)的實(shí)現(xiàn) variableva

53、riable: : begin begin levellevel:=:=levlev; ; （* *表示表示tabletx.tabletx.levellevel:=:=levlev* *） adradr:=:=dxdx; ; （* *表示表示tabletx.tabletx.adradr:=:=dxdx* *） dx:=dx+1;dx:=dx+1; end; end; procedurprocedur: : levellevel:=:=levlev ( (* * 表示表示tabletx.tabletx.levellevel:=:=levlev; ;* *） end(end(* * casecas

54、e * *); ); endendend(end(* *enterenter* *););過程體的處理過程體的處理/ /* * * * 編譯程序主體編譯程序主體 * * * * lev: lev: 當(dāng)前分程序所在層當(dāng)前分程序所在層 * * tx: tx: 名字表當(dāng)前尾指針名字表當(dāng)前尾指針 * * fsys: fsys: 當(dāng)前模塊后跟符號(hào)集合當(dāng)前模塊后跟符號(hào)集合 * */ /int block(int lev, int tx, boolint block(int lev, int tx, bool* * fsys) fsys)過程體的處理過程體的處理 ./main() ./main()函數(shù)函數(shù)

55、if(-1 = block(0, if(-1 = block(0, 0 0, nxtlev), nxtlev) . . . . if (sym != period) error(9); if (sym != period) error(9); . . interpret();/ interpret();/* * 調(diào)用解釋執(zhí)行程序調(diào)用解釋執(zhí)行程序 * */ / . .過程體的處理過程體的處理while (sym = procsym) / block()while (sym = procsym) / block()函數(shù)函數(shù) getsymdo; getsymdo; if (sym = ident)

56、if (sym = ident) enter(procedur, enter(procedur, &tx&tx, lev, &dx);, lev, &dx); . . . . if (-1 = block(lev+1, if (-1 = block(lev+1, txtx, nxtlev), nxtlev) 過程體的處理過程體的處理變量引用的處理變量引用的處理y對(duì)對(duì)語句進(jìn)行語句進(jìn)行語法語法分析分析y語義分析語義分析 當(dāng)遇到當(dāng)遇到標(biāo)識(shí)符的引用時(shí)標(biāo)識(shí)符的引用時(shí)就調(diào)用就調(diào)用POSITIONPOSITION函數(shù)函數(shù)查查TABLETABLE表表，看是否，看是否有有過過正確

57、定義正確定義，若已有，則從表中，若已有，則從表中取相應(yīng)取相應(yīng)的有關(guān)的有關(guān)信息信息，供代碼的生成使用。，供代碼的生成使用。若無定義則錯(cuò)若無定義則錯(cuò)。y語義分析語義分析 TABLETABLE表表若已若已有有過過正確定義正確定義，檢查引用與說明的，檢查引用與說明的屬性是否一致，屬性是否一致，若不一致則錯(cuò)若不一致則錯(cuò)。y當(dāng)當(dāng)語法語義正確時(shí)語法語義正確時(shí)，就，就生成生成相應(yīng)語句功能的相應(yīng)語句功能的目標(biāo)代碼目標(biāo)代碼賦值賦值語句的處理語句的處理(C)(C)if (sym = ident)if (sym = ident)/ /* * 準(zhǔn)備按照賦值語句處理準(zhǔn)備按照賦值語句處理 * */ / i = positi

58、on(id, i = position(id, * *ptx);ptx); if (i = 0) if (i = 0) error(11); error(11); / /* * 變量未找到變量未找到 * */ / else else if(tablei.kind != variable) if(tablei.kind != variable) error(12); error(12); / /* * 賦值語句格式錯(cuò)誤賦值語句格式錯(cuò)誤 * */ / i = 0; i = 0; else else . . gendo(sto, lev-tablei.level, tablei.adr); gend

59、o(sto, lev-tablei.level, tablei.adr); . . 賦值賦值語句的語句的處理處理 if sym = ident thenif sym = ident then begin begin i:= position(id); i:= position(id); if i= 0 then error(11) if i= 0 then error(11) else if tablei.kind variable else if tablei.kind variable then then begin error(12); begin error(12); i:= 0 i:

60、= 0 end; end; getsym;getsym; if sym = becomes then getsym if sym = becomes then getsym else error(13); else error(13); expression(fsys); expression(fsys); if i 0 then if i 0 then with table i do gen(sto,lev-level,adr) with table i do gen(sto,lev-level,adr) end end 第第2 2章章 PL/0PL/0編譯程序編譯程序本章目的：以本章目的：以PL/0PL/0編譯程序編譯程序?yàn)閷?shí)例為實(shí)例, ,學(xué)習(xí)編譯程序?qū)崿F(xiàn)的基本學(xué)習(xí)編譯程序?qū)崿F(xiàn)的基本步驟和