第2章PL0編譯程序?qū)崿F(xiàn)

1、第第2 2章章 PL/0PL/0編譯程序的實現(xiàn)編譯程序的實現(xiàn)本章目的：以本章目的：以PL/0PL/0編譯程序編譯程序為實例為實例, ,學習編譯程序?qū)崿F(xiàn)的基本學習編譯程序?qū)崿F(xiàn)的基本步驟和相關技術步驟和相關技術1 PL/0編譯程序的結構編譯程序的結構2 PL/0編譯程序的分析工作編譯程序的分析工作 (詞法，語法和語義）實現(xiàn)詞法，語法和語義）實現(xiàn)3 PL/0編譯程序的編譯程序的錯誤處理方法錯誤處理方法4 目標代碼生成和目標代碼生成和類類pcodepcode代碼解釋器代碼解釋器 1. PL/0編譯程序的結構編譯程序的結構 PL/0編譯程序編譯程序 PL/0 語言程序語言程序 類類 pcode 代碼代碼

2、源語言源語言(PL/0)目標語言目標語言(類類 pcode)實現(xiàn)語言（實現(xiàn)語言（pascal/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)的結構框架編譯系統(tǒng)的結構框架PL/0PL/0語言語言 PL/0 PL/0語言：語言：PASCALPASCAL語言的語言的子集子集 PL/0PL/0程序示例程序示例 PL/0PL/0的的語法描述圖語法描述圖 PL/0PL/0語言語言的的EBNFEBNF表示表示 PL/0 PL/0

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

4、; WHILE X#0 WHILE 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過程體過程體主主程序程序體體 輸入圓柱的半徑和高，計算一些面積、體積等輸入圓柱的半徑和高，計算一些面積、體積等z z var r, h, len, a1, a2, volumn;z beginzread(r);zread(h);zzlen := 2 * 3 * r;za1 := 3 * r

5、 * r;za2 := a1 + a1 + len * h;zvolumn := a1 * h;zzwrite(len);zwrite(a1);zwrite(a2);zwrite(volumn);z end.計算最大公約數(shù)計算最大公約數(shù) l var m, n, r, q;l 計算計算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ī)定為

6、了方便，規(guī)定m = n l if 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)的文字表示單詞

7、符號內(nèi)的文字表示單詞符號程序程序.內(nèi)的文字表示內(nèi)的文字表示語法成分（短語）語法成分（短語）語法圖語法圖constidentnumbervaridentprocedureident分程序分程序語句語句分程序分程序PL/0PL/0語言的語言的EBNFEBNF表示表示 構成構成EBNFEBNF的元素的元素（非終結符，終結符，開始符，規(guī)（非終結符，終結符，開始符，規(guī)則）則） EBNFEBNF 的元符號：的元符號： 用左右尖括號括起來的內(nèi)容為用左右尖括號括起來的內(nèi)容為非終結符非終結符= = 讀做讀做定義為定義為 =的的左部由左部由右部右部定義定義 讀做讀做定義為定義為 的的左部由左部由右部右部定義定義

8、| | 讀做讀做或或 表示右部候選內(nèi)容表示右部候選內(nèi)容 表示花括號內(nèi)的內(nèi)容表示花括號內(nèi)的內(nèi)容可重復可重復任意次或限任意次或限 定次數(shù)定次數(shù) 表示方括號內(nèi)的內(nèi)容為表示方括號內(nèi)的內(nèi)容為任選項任選項( ) ( ) 表示圓括號內(nèi)的內(nèi)容表示圓括號內(nèi)的內(nèi)容優(yōu)先優(yōu)先例：用例：用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)層可引用包圍它的外層定義的可引用包圍它的外層定義的標識符），標識符），上下文約束，上下文約束， 過程可過程可嵌套定義嵌套定義，可遞歸調(diào)用可遞歸調(diào)用子集子集z 數(shù)據(jù)類型數(shù)據(jù)類型, ,只有整型只有整型z 數(shù)據(jù)結構數(shù)據(jù)結構 , ,只有簡變和常數(shù)只有簡變和常數(shù)z 數(shù)字最多為數(shù)字最多為1414位位z 標識符的有效長度是標識符的有效長度是1010z 語句種類語句種類z 過程無參，最多可過程無參，最多可嵌套嵌套三層三層 目標代碼目標代碼類類p-codep-code目標代碼目標代碼類類p-codep-code是一種是一種棧式機棧式機的的匯編語言匯編

10、語言。棧式機系統(tǒng)結構棧式機系統(tǒng)結構: :沒有累加器和寄存器，只有存儲棧指針沒有累加器和寄存器，只有存儲棧指針 所有運算都在棧頂（零地址機）所有運算都在棧頂（零地址機）指令格式：指令格式：f l af l af f功能碼功能碼l l層次差層次差 （標識符（標識符引用層引用層減去減去定義層定義層）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; end;beginbegin read(b

11、); 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 轉向轉向主程序入口主程序入口( 1) jmp 0 2 ( 1) jmp 0 2 轉向轉向過程過程p p入口入口( 2)( 2) int 0 3int 0 3 過程過程p p入口入口, ,為過程為過程p p開辟空間開辟空間( 3) lod ( 3) lod 1 1 3 3 取變量取變量b b的值到棧頂?shù)?/p>

12、值到棧頂( 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ào)用點(16)(16)( 8)( 8) int 0 5 int 0 5 主程序入口開辟主程序入口開辟5 5個?？臻g個棧空間( 9) opr 0 16 ( 9) opr 0 16 從命令行讀入值置于棧頂從命令行讀入值置于棧頂(10) sto 0 3 (10)

13、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進棧進棧(13) opr 0 9 (13) opr 0 9 次棧頂與棧頂是否不等次棧頂與棧頂是否不等(14) (14) jpc 0 24jpc 0 24 等時轉等時轉(24)(24)（條件不滿足轉條件不滿足轉）(15) (15) cal 0 2cal 0 2 調(diào)用過程調(diào)用過程p p(16) lit 0 2 (16) lit 0 2 常數(shù)值常數(shù)值2 2進棧進棧(17) lo

14、d (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) jmp 0 11 無條件轉到循環(huán)入口無條件

15、轉到循環(huán)入口(11)(11)(24) opr 0 0 (24) opr 0 0 結束退棧結束退棧 PL/0PL/0編譯程序的結構編譯程序的結構詞法分析程詞法分析程序序語法語義分析程序語法語義分析程序代碼生成程序代碼生成程序表格管理程序表格管理程序出錯處理程序出錯處理程序PL/0PL/0源程序源程序目標程序目標程序PL/0PL/0編譯程序的總體設計編譯程序的總體設計z以語法以語法、語義分析語義分析程序程序為核心為核心 詞法分析詞法分析程序和程序和代碼生成代碼生成程序都作為一個程序都作為一個過程過程，當語法分析需要讀單詞時就調(diào)用詞法分析程序，當語法分析需要讀單詞時就調(diào)用詞法分析程序，而當語法而當語

16、法、語義分析正確，需要生成相應的目標語義分析正確，需要生成相應的目標代碼時，則調(diào)用代碼生成程序。代碼時，則調(diào)用代碼生成程序。z表格管理表格管理程序?qū)崿F(xiàn)程序?qū)崿F(xiàn)變量變量，常量常量和和過程過程標識符的標識符的信信息的登錄與查找息的登錄與查找。z出錯處理出錯處理程序，對詞法和語法程序，對詞法和語法、語義分析遇到的語義分析遇到的錯誤給出在源程序中錯誤給出在源程序中出錯的位置出錯的位置和與和與錯誤錯誤 性質(zhì)性質(zhì)有關有關的編號，并進行錯誤恢復。的編號，并進行錯誤恢復。第第2 2章章 PL/0PL/0編譯程序編譯程序本章目的：以本章目的：以PL/0PL/0編譯程序編譯程序為實例為實例, ,學習編譯程序?qū)崿F(xiàn)的

17、基本學習編譯程序?qū)崿F(xiàn)的基本步驟和相關技術步驟和相關技術1 PL/0編譯程序的結構編譯程序的結構2 PL/0編譯程序的分析工作編譯程序的分析工作 (詞法，語法和語義）實現(xiàn)詞法，語法和語義）實現(xiàn)3 PL/0編譯程序的編譯程序的錯誤處理方法錯誤處理方法4 目標代碼生成和目標代碼生成和類類pcodepcode代碼解釋器代碼解釋器 2 PL/0編譯程序的分析工作編譯程序的分析工作 (詞法，語法詞法，語法和語義）和語義）2.1PL/0編譯程序詞法分析的實現(xiàn)識別的單詞：識別的單詞：y保留字或關鍵字：如：保留字或關鍵字：如：BEGINBEGIN、 ENDEND、 IFIF、 THENTHEN等等y運算符運算符

18、： 如：如：+ +、- -、* *、/ /、：、：= =、# #、=、=等等y標識符標識符： 用戶定義的變量名、常數(shù)名、過程名用戶定義的變量名、常數(shù)名、過程名y常數(shù)常數(shù)： 如：如：1010、2525、100100等整數(shù)等整數(shù)y界符界符： 如：如：,、. . 、; ; 、( ( 、)等等詞法分析過程詞法分析過程GETSYMGETSYM所要完成的任務：所要完成的任務：y從源程序讀字符（從源程序讀字符（getch)getch)y濾空格濾空格y識別識別保留字保留字y識別標識符識別標識符y拼數(shù)拼數(shù)y識別單字符單詞識別單字符單詞y拼雙字符單詞拼雙字符單詞z 詞法分析過程詞法分析過程:GETSYM:GETS

19、YM框圖（見教材圖框圖（見教材圖2.52.5）z 程序（程序（ procedure getsymprocedure getsym）當識別到標識符時先查當識別到標識符時先查保留字保留字表表z 保留字保留字表：（表：（ begin (begin (* * main main * * ) ) ）word1:=word1:=begin begin ；word2:=word2:=callcall ； .word13:=word13:=writewrite ；查到時找到相應的查到時找到相應的內(nèi)部表示內(nèi)部表示W(wǎng)sym1:=beginsym; wsym2:=callsym； wsym13:=writesym；

20、z 字符對應的字符對應的單詞表：單詞表：ssym+:=ssym+:=plusplus; ssym-:=; ssym-:=minusminus; ; ssym;:=ssym;:=semicolonsemicolon; ;z 詞法分析如何把單詞傳遞給語法分析詞法分析如何把單詞傳遞給語法分析 type symbol=(type symbol=(nulnul, ,identident, ,numbernumber, ,plusplus,varsymvarsym, ,procsymprocsym) )；3 3個個全程量全程量 SYMSYM:symbol;:symbol;IDID:alfa;:alfa;N

21、UMNUM:integer;:integer;通過三個通過三個全程量全程量 SYMSYM 、IDID和和NUMNUM 將識別出的單詞信息將識別出的單詞信息傳遞傳遞給給語法語法分析分析程序。程序。ySYMSYM：存放單詞的類別：存放單詞的類別 如：有程序段落為：如：有程序段落為： begin initial := 60begin initial := 60；endend 對應單詞翻譯后變?yōu)椋簩獑卧~翻譯后變?yōu)椋?begin begin beginsymbeginsym, initial , initial identident, ,:= := becomesbecomes, 60 , 60 nu

22、mbernumber, , ； semicolonsemicolon，end end endsymendsym 。yIDID： 存放用戶所定義的標識符的值存放用戶所定義的標識符的值 如：如： initial initial （在（在SYMSYM中放中放identident，在，在IDID中放中放initialinitial）yNUMNUM：存放用戶定義的數(shù)：存放用戶定義的數(shù) 如：如：60 60 y（在（在SYMSYM中放中放number,number,在在NUMNUM中放中放6060）使用狀態(tài)轉換圖實現(xiàn)詞法分析程序的設計方法使用狀態(tài)轉換圖實現(xiàn)詞法分析程序的設計方法詞法分析程序的設計詞法分析程序

23、的設計-使用狀態(tài)轉換圖實現(xiàn)使用狀態(tài)轉換圖實現(xiàn)表示表示狀態(tài)狀態(tài)，對應每個狀態(tài)編一段程序，對應每個狀態(tài)編一段程序，每個狀態(tài)每個狀態(tài)調(diào)用調(diào)用取字符取字符程序，根據(jù)當前字程序，根據(jù)當前字符符轉到不同的狀態(tài)，并做相應操作。轉到不同的狀態(tài)，并做相應操作。表示表示終態(tài)終態(tài)，已，已識別出一個識別出一個單詞單詞。1 12 23 35 514141313121210109 97 78 86 64 41111空格空格字母字母字母數(shù)字字母數(shù)字非字母數(shù)字非字母數(shù)字數(shù)字數(shù)字數(shù)字數(shù)字非數(shù)字非數(shù)字：= = = =非非= =, + - ( 2.2 2.2 PL/0PL/0編譯程序語法分析編譯程序語法分析 自頂向下自頂向下的語法

24、分析的語法分析 遞歸子程序法遞歸子程序法（上下文無關文法）上下文無關文法）句型的分析句型的分析句型分析句型分析就是就是識別識別一個符號串是否為某文法一個符號串是否為某文法的的句型的句型的過程，或者說是某個過程，或者說是某個推導推導的構造的構造過程。過程。對于一個給定的文法，要想判定一個符號串對于一個給定的文法，要想判定一個符號串是否為該文法的句子，需要考察是否可以是否為該文法的句子，需要考察是否可以從該文法的開始符號派生出（推導出）此從該文法的開始符號派生出（推導出）此符號串。編譯程序的語法分析工作。符號串。編譯程序的語法分析工作。分析算法分類分析算法分類分析算法可分為：分析算法可分為：自上而

25、下分析法自上而下分析法：從文法的開始符號出發(fā)從文法的開始符號出發(fā)，尋找尋找與與輸入符號輸入符號串串匹配匹配的的推導，推導，或者說，為輸入串尋找一或者說，為輸入串尋找一個最左推導。個最左推導。自下而上分析法自下而上分析法：從從輸入符號串輸入符號串開始開始，逐步進行逐步進行歸約歸約，直至，直至歸約歸約到到文法的文法的開始符號開始符號。 語法分析（從概念上講）建立一棵與輸語法分析（從概念上講）建立一棵與輸入串相匹配的語法樹。入串相匹配的語法樹。語法樹推導的幾何表示語法樹推導的幾何表示z句型句型aabbaa的可能的可能推導序列和語法樹推導序列和語法樹 例例: GS:SaASASbAASSSaAba S

26、 a A S S b A a a b aSaASaAaaSbAaaSbbaaaabbaaSaASaSbASaabASaabbaSaabbaaSaASaSbASaSbAaaabAaaabbaa兩種方法反映了語法樹的兩種構兩種方法反映了語法樹的兩種構造過程。造過程。自上而下方法自上而下方法是從文法符號開始，將它做為語法樹的根，向下逐步建立語法樹，使語法樹的結果正好是輸入符號串自下而上方法自下而上方法則是從輸入符號串開始，以它做為語法樹的結果，自底向上的構造語法樹自上而下的語法分析的一般過程自上而下的語法分析的一般過程例：文法例：文法G： S cAd A ab A a識別輸入串識別輸入串w=cabd

27、是否為該文法的是否為該文法的句子句子SSScAdcAd a b推導過程：推導過程：S cAd cAd cabd 程序程序分程序分程序.constidentnumbervaridentprocedureident分程序分程序語句語句分程序分程序identreadend語句語句表達式表達式：=begin語句語句語句語句)(ident, 自頂向下的語法分析自頂向下的語法分析VAR A;VAR A;BEGINBEGIN READ(A) READ(A)END.END. . . VARVAR ； A A BEGINBEGIN ENDEND READREAD （ ） A A 為文法的為文法的開始符號開始符號

28、，以開，以開始符號作為根結始符號作為根結點構造一棵倒掛點構造一棵倒掛著的語法樹。著的語法樹。遞歸子程序法遞歸子程序法- -語法分析程序由一組遞歸過語法分析程序由一組遞歸過程組成程組成對應對應每個非終結符（每個非終結符（語法單元），編一個獨立的語法單元），編一個獨立的處理過程（或函數(shù)，子程序）。處理過程（或函數(shù)，子程序）。 由由 （即開始符）開始，沿語法描述即開始符）開始，沿語法描述圖圖箭頭箭頭所指出的方向進行分析（規(guī)則右部）所指出的方向進行分析（規(guī)則右部） 遇到遇到非終結符非終結符（進入了又一個語法單元），（進入了又一個語法單元），則則調(diào)用調(diào)用相應的相應的處理過程處理過程 遇到遇到終結符終結符

29、，則判斷當前讀入的單詞是否，則判斷當前讀入的單詞是否與該終結符與該終結符相匹配相匹配，若匹配，再讀取下一個單，若匹配，再讀取下一個單詞繼續(xù)分析。詞繼續(xù)分析。也稱為也稱為遞歸下降分析器（遞歸下降分析器（ recursive-descent parser ） 例：表達式的語法分析程序（遞歸子程序）例：表達式的語法分析程序（遞歸子程序）項項表達式表達式+-項項+-項項 因子因子 因子因子 */語法圖語法圖因子的語法圖因子的語法圖因子因子identnumber(表達式表達式)z 表達式的表達式的EBNF表達式表達式=+|-+|-項項 （+|-+|-）項）項 項項=因子因子 （* *|/|/）因子）因子

30、 因子因子=標識符標識符| |無符號整數(shù)無符號整數(shù)|（表達式表達式）表達式表達式=+|-+|-項項 （+|-+|-）項）項 pascalpascalz 表達式表達式的分析程序（的分析程序（遞歸子程序）遞歸子程序）procedure procedure exprexpr; ;beginbegin 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 plu

31、splus, , minusminus do do begin begin getsym; getsym; termterm; ; end endend;end; z 項項=因子因子 （* *|/|/）因子）因子 pascalpascalz項項的分析程序（的分析程序（遞歸子程序）遞歸子程序）procedure procedure termterm; ;beginbegin factorfactor; ; while sym in while sym in timestimes, , slashslash do do begin begin getsym; getsym; factorfacto

32、r; ; end endend;end;因子因子=標識符標識符| |無符號整數(shù)無符號整數(shù)|（表達式表達式）z 因子因子的分析程序（的分析程序（遞歸子程序）遞歸子程序）procedure procedure factorfactor; ;begin begin if sym if sym 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

33、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 getsym else getsym end; end;表達式表達式=+|-+|-項項 （+|-+|-）項）項 in Cin Cz int expression(bool* fsys, int* ptx, int lev)z zif(sym=plus | sym=minus)/* 開頭的正負號，當前表達式被開頭的正負號

34、，當前表達式被看作一個正的或負的項看作一個正的或負的項 */zzgetsymdo;ztermdo(nxtlev, ptx, lev);/* 處理項處理項 */zzelse/* 此時表達式被看作項的加減此時表達式被看作項的加減 */zztermdo(nxtlev, ptx, lev);/* 處理項處理項 */zzwhile (sym=plus | sym=minus)zzgetsymdo;ztermdo(nxtlev, ptx, lev);/* 處理項處理項 */zzreturn 0;z 項項=因子因子 （* *|/|/）因子）因子 zint term(bool* fsys, int* ptx,

35、 int lev)zzfactordo(nxtlev, ptx, lev); /* 處理因處理因子子 */zwhile(sym=times | sym=slash)zgetsymdo;zfactordo(nxtlev, ptx, lev);zzreturn 0;z因子因子=標識符標識符| |無符號整數(shù)無符號整數(shù)|（表達式表達式）int factor(bool* fsys, int* ptx, int lev)if(sym = ident)/* 因子為常量或變量因子為常量或變量 */ getsymdo;else if(sym = number)/* 因子為因子為*/ getsymdo; else

36、 if (sym = lparen)/* 因子為表達式因子為表達式 */ expressiondo(nxtlev, ptx, lev); if (sym = rparen) getsymdo; else error(22);/* 缺少右括號缺少右括號 */ return 0; = beginbegin（* *mainmain* *) )(* *initializeinitialize* *) ) ( (* *r/w file setr/w file set* *) ) getsym; getsym; block( ); block( ); if sym period then error. i

37、f sym period then error.end.end.。 程序程序 pl0分程序分程序 block語句語句 statement條件條件 condition表達式表達式expression項項 term因子因子 factor語語法法調(diào)調(diào)用用關關系系圖圖編譯系統(tǒng)總體流程圖編譯系統(tǒng)總體流程圖啟動啟動置初值置初值調(diào)用G E TSYM取 單 詞調(diào)用G E TSYM取 單 詞調(diào)用B L OCK過 程調(diào)用B L OCK過 程當前單詞當前單詞是否為源程序結束符是否為源程序結束符.？.？出錯出錯源程序中源程序中是否有錯誤？是否有錯誤？調(diào)用解釋過程I N T E R P RET調(diào)用解釋過程I N T E

38、 R P RET解釋執(zhí)行目標程序解釋執(zhí)行目標程序打印錯誤打印錯誤結束結束N NY YY YN N2.3 2.3 PL/0PL/0編譯程序語義分析的設計與實現(xiàn)編譯程序語義分析的設計與實現(xiàn) PL/0PL/0編譯程序語法、語義分析的的核心編譯程序語法、語義分析的的核心程序是程序是BLOCKBLOCK過程過程哪些語義分析工作？哪些語義分析工作？如何實現(xiàn)？如何實現(xiàn)？-語義分析環(huán)境（符號表）語義分析環(huán)境（符號表） z 說明部分的分析說明部分的分析與處理與處理z 表格管理表格管理z 過程體過程體( (語句）的分析語句）的分析與處理與處理因子因子=標識符標識符| |無符號整數(shù)無符號整數(shù)|（表達式表達式）語義分

39、析語義分析int factor(bool* fsys, int* ptx, int lev)z if(sym = ident)/* 因子為常量或變量因子為常量或變量 */zzi = position(id, *ptx);/* 查找名字查找名字 */zif (i = 0)zerror(11);/* 標識符未聲明標識符未聲明 */zzelsezswitch (tablei.kind)zcase constant:/* 名字為常量名字為常量 */zbreak;zcase variable:/* 名字為變量名字為變量 */zbreak;zcase procedur: /* 名字為過程名字為過程 */z

40、error(21); /* 不能為過程名不能為過程名 */z登錄符號表登錄符號表說明部分的分析說明部分的分析與處理與處理對每個過程（含主程序）對每個過程（含主程序）說明的對象說明的對象（變量變量，常量常量和和過程過程）造造符號表符號表 登錄登錄標識符的標識符的屬性屬性。 標識符的屬性標識符的屬性: :種類，所在種類，所在層次層次, ,值值和分配的和分配的相對位置相對位置。 登錄信息由登錄信息由ENTERENTER過程完成。過程完成。符號表結構Enum object constant, variable, procedur ;Struct tablestruct char nameal; enu

41、m object kind; int val; int level; int adr; int size;Struct tablestruct tabletxmax; 符號表結構z 說明種類的定義： object= (constant, variable,procedur) （定義定義純量純量/ /枚舉枚舉類型）類型）z 符號表的定義 table:array0.txmax of record name:alfa; case kind:object of constant:(val:integer); variable:procedur:(level,adr,size: integer); N

42、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 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

43、 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 EL 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

44、 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，B=49B=49； VAR CVAR C，D D，E E； PROCEDURE PPROCEDURE P； VAR G VAR G ； 符號表符號表 名字名字 種類種類 層次層次/值值 地址地址 存儲空間存儲空間對應名字表對應名字表txtx ：tabletable表的下標指針表的下標指針, ,是以是以值參數(shù)值參數(shù)形式使用的。形式使用的。dx: 計算每個變量在運行棧中相對本計算每個變量在運行棧中相對

45、本過程過程基地址基地址的的偏移量偏移量 ，放在放在table表中的表中的adr域，域，生成生成目標代目標代碼碼時再放在時再放在codecode中的中的a域域變量定義語句的處理變量定義語句的處理(C)(C)語法：語法：: := varvar ， ；程序：程序：if (sym = varsym)if (sym = varsym)/ /* * 收到變量聲明符號，開始處理變量聲明收到變量聲明符號，開始處理變量聲明 * */ / getsymdo; getsymdo; do do vardeclarationdo(&tx, lev, &dx); vardeclarationdo(&

46、;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; getsymdo; else error(5); else error(5); while (sym = ident); while (sym = ident); 注意：注

47、意：&tx&tx變量說明處理變量說明處理(C)(C)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, pdx);/填寫名字表填寫名字表 getsymdo; getsymdo; else else error(4); error(4); / /* * var va

48、r后應是標識后應是標識符符 * */ / return 0; return 0; 變量定義語句的處理變量定義語句的處理語法：語法：: := varvar ， ；程序：程序： if sym=if sym=varsymvarsym then then begin begin getsym; getsym; repeat repeat vardeclarationvardeclaration;(;(* *變量說明處理變量說明處理*) while sym=while sym=commacomma do do begin begin getsym; getsym; vardeclarationvarde

49、claration end; end; if sym= if sym=semicolonsemicolon then then getsym getsym else error(5) else error(5) until sym until symidentident; ; end; end;變量說明處理變量說明處理 procedure vardeclaration; procedure vardeclaration; beginbegin if sym= if sym=ident ident thenthen begin begin enterenter( (variablevariabl

50、e);); getsym getsym end end else else error(4) error(4) end( end(* *vardeclarationvardeclaration* *););過程過程ENTERENTER的實現(xiàn)的實現(xiàn)(C)(C)/ /* * * * 在名字表中加入一項在名字表中加入一項 * * * * k: k: 名字種類名字種類const,var or procedureconst,var or procedure * * ptx: ptx: 名字表尾指針的指針名字表尾指針的指針 * * lev: lev: 名字所在的層次名字所在的層次, ,以后所有的以后所有的

51、levlev都是這樣都是這樣 * * pdx: pdx: 當前應分配變量的相對地址，分配后增加當前應分配變量的相對地址，分配后增加1 1 * */ /void enter(enum object k, intvoid enter(enum object k, int* * ptx, ptx, int lev, int int lev, int* * pdx) pdx)過程過程ENTERENTER的實現(xiàn)的實現(xiàn)(C)(C) ( (* *ptx)+;ptx)+; strcpy(table( strcpy(table(* *ptx).name, id); ptx).name, id); / /* *

52、全局變量全局變量idid中已存有當前名字的名字中已存有當前名字的名字 * */ / 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; bre

53、ak; break;過程過程ENTERENTER的實現(xiàn)的實現(xiàn)(C)(C) case variable: case 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).

54、level = lev;ptx).level = lev; break; break; 過程過程ENTERENTER的實現(xiàn)的實現(xiàn)txtx ：tabletable表的指針表的指針 procedure procedure 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 ( (* * 開域開域語句語句 * *） beginbe

55、gin namename:=:=idid;(;(* * 表示表示name:=:=idid; ;* *） kindkind:=:=k k;(;(* * 表示表示tabletx.tabletx.kindkind:=:=k k; ;* * ) )過程過程ENTERENTER的實現(xiàn)的實現(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

56、; valval:=:=numnum;(;(* * tabletx.tabletx.valval:=:=numnum; ;* *) ) end; end;過程過程ENTERENTER的實現(xiàn)的實現(xiàn) variablevariable: : begin begin levellevel:=:=levlev; ; （* *表示表示tabletx.tabletx.levellevel:=:=levlev* *） adradr:=:=dxdx; ; （* *表示表示tabletx.tabletx.adradr:=:=dxdx* *） dx:=dx+1;dx:=dx+1; end; end; procedu

57、rprocedur: : levellevel:=:=levlev ( (* * 表示表示tabletx.tabletx.levellevel:=:=levlev; ;* *） end(end(* * casecase * *); ); endendend(end(* *enterenter* *););過程體的處理過程體的處理/ /* * * * 編譯程序主體編譯程序主體 * * * * lev: lev: 當前分程序所在層當前分程序所在層 * * tx: tx: 名字表當前尾指針名字表當前尾指針 * * fsys: fsys: 當前模塊后跟符號集合當前模塊后跟符號集合 * */ /int

58、block(int lev, int tx, boolint block(int lev, int tx, bool* * fsys) fsys)過程體的處理過程體的處理 ./main() ./main()函數(shù)函數(shù) 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í)行程序 * */ / . .過程體的處理過程

59、體的處理while (sym = procsym) / block()while (sym = procsym) / block()函數(shù)函數(shù) getsymdo; getsymdo; if (sym = ident) 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) 過程體的處理變量引用的處理過程體的處理變量

60、引用的處理y對對語句進行語句進行語法語法分析分析y語義分析語義分析 當遇到當遇到標識符的引用時標識符的引用時就調(diào)用就調(diào)用POSITIONPOSITION函數(shù)函數(shù)查查TABLETABLE表表，看是否，看是否有有過過正確定義正確定義，若已有，則從表中，若已有，則從表中取相應取相應的有關的有關信息信息，供代碼的生成使用。，供代碼的生成使用。若無定義則錯若無定義則錯。y語義分析語義分析 TABLETABLE表表若已若已有有過過正確定義正確定義，檢查引用與說明的，檢查引用與說明的屬性是否一致，屬性是否一致，若不一致則錯若不一致則錯。y當當語法語義正確時語法語義正確時，就，就生成生成相應語句功能的相應語句功能的目標代碼目標代碼賦值賦值語句的處理語句的處理(C)(C)if (sym = ident)if (