1、編譯原理講義編譯原理講義2第二章第二章 PL/0PL/0編譯程序的實現編譯程序的實現本章目的：以本章目的：以PL/0PL/0為例學習編譯程序實現為例學習編譯程序實現的基本步驟和相關技術，熟悉并理解編譯的基本步驟和相關技術，熟悉并理解編譯程序的基本原理和概念。程序的基本原理和概念。編譯原理講義PL/0編譯程序pcode解釋程序PL/0源程序pcode代碼注：此處的pcode代碼專指PL/0的目標碼，注意與傳統pcode的區別編譯原理講義4第二章第二章 PL/0PL/0編譯程序的實現編譯程序的實現步驟步驟1 1、 認識源語言認識源語言PL/0PL/0與目標代碼與目標代碼pcodepcode及及它們

2、之間的映射它們之間的映射步驟步驟2 2、 PL/0PL/0編譯程序的總體設計編譯程序的總體設計步驟步驟3 3、 PL/0PL/0編譯程序詞法分析的設計與實編譯程序詞法分析的設計與實現現步驟步驟4 4、 PL/0PL/0編譯程序語法語義分析的設計編譯程序語法語義分析的設計與實現與實現編譯原理講義5第二章第二章 PL/0PL/0編譯程序的實現編譯程序的實現步驟步驟5 5、 PL/0PL/0編譯程序代碼生成的實現編譯程序代碼生成的實現步驟步驟6 6、 PL/0PL/0編譯程序語法錯誤處理的實現編譯程序語法錯誤處理的實現步驟步驟7 7、 pcodepcode代碼解釋器的設計與實現代碼解釋器的設計與實現

3、編譯原理講義6步驟步驟1 1、認識源語言、認識源語言PL/0PL/0與目標與目標代碼代碼pcodepcode及它們之間的映射及它們之間的映射何為何為PL/0PL/0語言語言? ?認識目標代碼認識目標代碼pcodepcodePL/0PL/0程序到程序到pcodepcode代碼的映射代碼的映射編譯原理講義7何為何為PL/0PL/0語言語言? ?PL/0PL/0語言：語言：PASCALPASCAL語言的子集，功能簡單，結語言的子集，功能簡單，結構清晰，可讀性強，具備了一般高級語言的必構清晰，可讀性強，具備了一般高級語言的必備部分備部分PL/0PL/0程序示例程序示例PL/0PL/0的非形式描述的非形

4、式描述PL/0PL/0的語法描述圖的語法描述圖PL/0PL/0語言文法的語言文法的EBNFEBNF表示表示編譯原理講義8PL/0PL/0程序示例程序示例CONST A=10;CONST A=10;VAR B,C;VAR B,C;PROCEDURE P;PROCEDURE P; VAR D; VAR D; PROCEDURE Q; PROCEDURE Q; VAR X; VAR X; BEGIN BEGIN READ(X); READ(X); D:=X; D:=X; WHILE X#0 DO CALL P; WHILE X#0 DO CALL P; END; END; BEGIN WRITE(D

5、); CALL Q; END;BEGIN CALL P;END.編譯原理講義9PL/0PL/0非形式描述非形式描述數據類型只有整型數據類型只有整型標識符的有效長度是標識符的有效長度是1010，以字母開始的字母數，以字母開始的字母數字串字串數最多為數最多為1414位位過程無參，可嵌套（最多三層），可遞歸調用過程無參，可嵌套（最多三層），可遞歸調用變量的作用域同變量的作用域同PASCALPASCAL，常量為全局的，無標，常量為全局的，無標號號編譯原理講義10PL/0PL/0非形式描述非形式描述語句類型：賦值語句，語句類型：賦值語句，if.then., if.then., while.do., re

6、ad, write, call, while.do., read, write, call, 復合語復合語句句begin. endbegin. end， 說明語句：說明語句： const., const., var., procedurevar., procedure1313個保留字：個保留字：if, then, while, do, read, if, then, while, do, read, write, call, begin, end, const, var, write, call, begin, end, const, var, procedure, oddprocedure,

7、 odd編譯原理講義11PL/0PL/0的語法描述圖的語法描述圖語句constidentnumbervaridentprocedureident分程序分程序分程序程序編譯原理講義12PL/0PL/0語言文法的語言文法的EBNFEBNF表示表示BNFBNF與與EBNFEBNF的介紹的介紹BNFBNF（BACKUS-NAUR FORMBACKUS-NAUR FORM）是根據美國的與丹）是根據美國的與丹麥的麥的Peter NaurPeter Naur來命名的，它從語法上描述程來命名的，它從語法上描述程序設計語言的元語言。采用序設計語言的元語言。采用BNFBNF就可說明哪些就可說明哪些符號序列是對于某

8、給定語言在語法上有效的程符號序列是對于某給定語言在語法上有效的程序。序。編譯原理講義13PL/0PL/0語言文法的語言文法的EBNFEBNF表示表示BNFBNF與與EBNFEBNF的介紹的介紹BNFBNF引入的符號：引入的符號： 用左右尖括號括起來的語法成分為非終結符用左右尖括號括起來的語法成分為非終結符= = 定義為定義為| | 或或EBNFEBNF引入的符號：引入的符號： 表示花括號內的語法成分可重復表示花括號內的語法成分可重復 表示方括號內的語法成分為任選項表示方括號內的語法成分為任選項( ) ( ) 表示圓括號內的成分優先表示圓括號內的成分優先編譯原理講義14PL/0PL/0語言文法的

9、語言文法的EBNFEBNF表示表示BNFBNF與與EBNFEBNF的介紹的介紹一個用一個用EBNFEBNF描述的例子：描述的例子： =+|-=+|- =0|1|2|3|4|5|6|7|8|9=0|1|2|3|4|5|6|7|8|9編譯原理講義15PL/0PL/0語言文法的語言文法的EBNFEBNF表示表示BNFBNF與與EBNFEBNF的介紹的介紹 =+|-=+|-|0|0 =1|2|3|4|5|6|7|8|9 =1|2|3|4|5|6|7|8|9 =0|1|2|3|4|5|6|7|8|9=0|1|2|3|4|5|6|7|8|9編譯原理講義16PL/0PL/0語言文法的語言文法的EBNFEBN

10、F表示表示PL/0PL/0語言文法的語言文法的EBNFEBNF表示表示程序程序=分程序分程序. .分程序分程序=常量說明部分常量說明部分變量說明部變量說明部分分過程說明部分過程說明部分 語句語句常量說明部分常量說明部分=CONST=CONST常量定義部分常量定義部分 ，常常量定義量定義 ；無符號整數無符號整數=數字數字 數字數字 變量說明部分變量說明部分=VAR=VAR標識符標識符 ，標識符標識符 ；標識符標識符=字母字母 字母字母| |數字數字 編譯原理講義17認識目標代碼認識目標代碼pcodepcode目標代碼目標代碼pcodepcode是一種假想棧式計算機的匯編是一種假想棧式計算機的匯編

11、語言。語言。指令格式指令格式f l af功能碼l層次差a根據不同的指令有所區別編譯原理講義0 jmp0 81 jmp0 22 int 0 33 lod 1 34 lit0 105 opr 0 2 次棧頂與棧頂相加6 sto 1 47 opr 0 08 int 0 5 在運行棧中申請5個棧空間9 opr 0 16 從命令行讀入輸入置于棧頂10 sto 0 3 將棧頂值存入變量11 cal 0 2 調用過程12 lod 0 4 將變量取至棧頂13 opr 0 14 棧頂值輸出至屏幕14 opr 0 15 換行15 opr 0 0SL 0DL 0RA 0變量1變量2RA 12SL 0DL 0運行棧c

12、onst a=10;v a r b , c ;procedure p; begin c : = b + a ; end;begin r e a d ( b ) ; c a l l p ; w r i t e ( c ) ;end.SL：靜態鏈DL：動態鏈RA：返回地址0編譯原理講義19PL/0PL/0程序到程序到pcodepcode代碼的映射代碼的映射const a=10;const a=10;var b,c;var b,c;procedure p;procedure p; begin begin c:=b+a; c:=b+a; end; end;beginbegin read(b); rea

13、d(b); while b#0 do while b#0 do begin begin call p; call p; write(2 write(2* *c);c); read(b); read(b); end endend.end.jmp 0 8jmp 0 2int 0 3lod 1 3lit 0 10opr 0 2 次棧頂與棧頂相加sto 1 4opr 0 0int 0 5 在運行棧中申請5個棧空間opr 0 16 從命令行讀入輸入置于棧頂sto 0 3 將棧頂值存入變量lod 0 3 將變量取至棧頂lit 0 0 將常值0進棧opr 0 9 次棧頂與棧頂是否不等jpc 0 24 cal

14、 0 2 調用過程lit 0 2 常值2進棧lod 0 4 將變量取至棧頂opr 0 4 次棧頂與棧頂相乘opr 0 14 棧頂值輸出至屏幕opr 0 15 換行opr 0 16 從命令行讀取輸入sto 0 3 jmp 0 11opr 0 0編譯原理講義20步驟步驟2 PL/02 PL/0編譯程序的總體設編譯程序的總體設計計語法語義分析程序詞法分析程序表格管理程序出錯處理程序代碼生成程序PL/0源程序目標程序編譯原理講義21步驟步驟2 PL/02 PL/0編譯程序的總體設編譯程序的總體設計計其編譯過程采用一趟掃描方式其編譯過程采用一趟掃描方式以語法分析程序為核心以語法分析程序為核心 詞法分析程

15、序和代碼生成程序都作為一個獨詞法分析程序和代碼生成程序都作為一個獨立的過程，當語法分析需要讀單詞時就調用詞立的過程，當語法分析需要讀單詞時就調用詞法分析程序，而當語法分析正確需要生成相應法分析程序，而當語法分析正確需要生成相應的目標代碼時，則調用代碼生成程序。的目標代碼時，則調用代碼生成程序。編譯原理講義22步驟步驟2 PL/02 PL/0編譯程序的總體設編譯程序的總體設計計用表格管理程序建立變量，常量和過程標識符用表格管理程序建立變量，常量和過程標識符的說明與引用之間的信息聯系。的說明與引用之間的信息聯系。用出錯處理程序對詞法和語法分析遇到的錯誤用出錯處理程序對詞法和語法分析遇到的錯誤給出在

16、源程序中出錯的位置和錯誤性質。給出在源程序中出錯的位置和錯誤性質。編譯原理講義23步驟步驟3 PL/03 PL/0編譯程序詞法分析編譯程序詞法分析的設計與實現的設計與實現所需識別的單詞所需識別的單詞基本字（保留字）：基本字（保留字）：BEGINBEGIN、 ENDEND、 IFIF、 THENTHEN等等運算符：運算符： 如如+ +、- -、* *、/ /、：、：= =、# #、=、=等等標識符：標識符： 用戶定義的變量名、常數名、過程名用戶定義的變量名、常數名、過程名常數：常數： 如如1010、2525、100100等整數等整數界符：界符： 如如,、. . 、; ; 、( ( 、)等等編譯原

17、理講義24步驟步驟3 PL/03 PL/0編譯程序詞法分析編譯程序詞法分析的設計與實現的設計與實現詞法分析過程詞法分析過程GETSYMGETSYM所要完成的任務所要完成的任務濾空格濾空格識別保留字識別保留字識別標識符識別標識符拼數拼數拼復合詞拼復合詞輸出源程序輸出源程序編譯原理講義25步驟步驟3 PL/03 PL/0編譯程序詞法分析編譯程序詞法分析的設計與實現的設計與實現通過三個全程量將識別出的單詞信息傳遞給語法分析程通過三個全程量將識別出的單詞信息傳遞給語法分析程序，序，SYMSYM，IDID，NUMNUMSYMSYM：存放單詞的類別：存放單詞的類別, ,如如beginsym, ident,

18、 numberbeginsym, ident, numberIDID： 存放用戶所定義的標識符的值存放用戶所定義的標識符的值NUMNUM：存放用戶定義的數：存放用戶定義的數編譯原理講義26步驟步驟3 PL/03 PL/0編譯程序詞法分析編譯程序詞法分析的設計與實現的設計與實現詞法分析程序的設計詞法分析程序的設計-使用狀態轉換圖使用狀態轉換圖1 12 23 35 514141313121210109 97 78 86 64 41111空格空格字母字母字母數字字母數字非字母數字非字母數字數字數字數字數字非數字非數字：= = = =非非= =, + - ( 編譯原理講義27步驟步驟4 PL/04 P

19、L/0編譯程序語法語義編譯程序語法語義分析的設計與實現分析的設計與實現語法分析的設計與實現語法分析的設計與實現自頂向下的語法分析自頂向下的語法分析遞歸子程序法遞歸子程序法如何用遞歸子程序法來實現表達式的語法分析如何用遞歸子程序法來實現表達式的語法分析編譯原理講義28自頂向下的語法分析自頂向下的語法分析VAR A;VAR A;BEGINBEGIN READ(A) READ(A)END.END.VAR；ABEGINENDREAD （ ）A編譯原理講義29遞歸子程序法遞歸子程序法遞歸子程序法遞歸子程序法：對應每個非終結符語法單元，編一個獨立對應每個非終結符語法單元，編一個獨立的處理過程（或子程序）。

20、語法分析從讀入第一個單詞開的處理過程（或子程序）。語法分析從讀入第一個單詞開始由非終結符始由非終結符程序程序即開始符出發，沿語法描述圖箭頭即開始符出發，沿語法描述圖箭頭所指出的方向進行分析。當遇到非終結符時，則調用相應所指出的方向進行分析。當遇到非終結符時，則調用相應的處理過程，從語法描述圖看也就進入了一個語法單元，的處理過程，從語法描述圖看也就進入了一個語法單元，再沿當前所進入的語法描述圖的箭頭方向進行分析，當遇再沿當前所進入的語法描述圖的箭頭方向進行分析，當遇到描述圖中是終結符時，則判斷當前讀入的單詞是否與圖到描述圖中是終結符時，則判斷當前讀入的單詞是否與圖中的終結符相匹配，若匹配，則執行

21、相應的語義程序（就中的終結符相匹配，若匹配，則執行相應的語義程序（就是翻譯程序）。再讀取下一個單詞繼續分析。遇到分支點是翻譯程序）。再讀取下一個單詞繼續分析。遇到分支點時將當前的單詞與分支點上多個終結符逐個相比較，若都時將當前的單詞與分支點上多個終結符逐個相比較，若都不匹配時可能是進入下一個非終結符語法單位或是出錯。不匹配時可能是進入下一個非終結符語法單位或是出錯。編譯原理講義30如何用遞歸子程序法來實現表達如何用遞歸子程序法來實現表達式的語法分析式的語法分析表達式的表達式的EBNF表達式表達式=+|-=+|-項項 （+|-+|-）項項 項項=因子因子 （* *|/|/）因子因子 因子因子=標

22、識符標識符| |無符號整數無符號整數|（表達式表達式）編譯原理講義31如何用遞歸子程序法來實現表達如何用遞歸子程序法來實現表達式的語法分析式的語法分析 表達式表達式的實現的實現procedure expr;procedure expr;beginbegin if sym in plus, minus then if sym in plus, minus then begin begin getsym; term; getsym; term; end end else term; else term; while sym in plus, minus do while sym in plus,

23、minus do begin begin getsym; term; getsym; term; end endend;end;編譯原理講義32如何用遞歸子程序法來實現表達如何用遞歸子程序法來實現表達式的語法分析式的語法分析項項的實現的實現procedure term;procedure term;beginbegin factor; factor; while sym in times, slash do while sym in times, slash do begin begin getsym; factor; getsym; factor; end endend;end;編譯原理講義

24、33如何用遞歸子程序法來實現表達如何用遞歸子程序法來實現表達式的語法分析式的語法分析 因子因子的實現的實現procedure factor;procedure factor;begin begin if sym # ident then if sym # ident then begin begin if sym # number then if sym # number then begin begin if sym = ( then if sym = ( then begin begin getsym; getsym; expr; expr; if sym = ) then getsym

25、if sym = ) then getsym else error else error end end else error else error end end end endend;end;編譯原理講義 程序 pl0分程序 block語句 statement條件 condition表達式expression項 term因子 factorPL/0語法調用關系圖編譯原理講義編譯程序總體流程圖編譯程序總體流程圖啟動啟動置初值置初值調用G E TSYM取 單 詞調用G E TSYM取 單 詞調用B L OCK過 程調用B L OCK過 程當前單詞當前單詞是否為源程序結束符是否為源程序結束符.？.

26、？出錯出錯源程序中源程序中是否有錯誤？是否有錯誤？調用解釋過程I N T E R P RET調用解釋過程I N T E R P RET解釋執行目標程序解釋執行目標程序打印錯誤打印錯誤結束結束N NY YY YN N編譯原理講義36程序程序BLOCKBLOCK過程的流程圖過程的流程圖見課本18頁編譯原理講義37語義分析與處理語義分析與處理說明部分的分析說明部分的分析對每個過程說明的對象（變量，常量和過程）對每個過程說明的對象（變量，常量和過程）造名字表造名字表填寫所在層次，標識符的屬性和分配的相對位填寫所在層次，標識符的屬性和分配的相對位置。標識符的屬性不同時，所需填入的信息也置。標識符的屬性不

27、同時，所需填入的信息也不同。登錄信息由不同。登錄信息由ENTERENTER過程完成。過程完成。 表格管理表格管理過程體的分析過程體的分析編譯原理講義NAMENAME：A ANAMENAME：B BNAMENAME：C CNAMENAME：D DNAMENAME：E ENAMENAME：P PKINDKIND：CONSTANTCONSTANTKINDKIND：CONSTANTCONSTANTKINDKIND：VARIABLEVARIABLEKINDKIND：VARIABLEVARIABLEKINDKIND：VARIABLEVARIABLEKINDKIND：PROCEDURPROCEDURVALV

28、AL：3535VALVAL：4949LEVELLEVEL：LEVLEVLEVELLEVEL：LEVLEVLEVELLEVEL：LEVLEVLEVELLEVEL：LEVLEVADRADR：DXDXADRADR：DX+1DX+1ADRADR：DX+2DX+2ADRADR：SIZESIZE：4 4NAMENAME：G G KINDKIND：VARIABLEVARIABLELEVELLEVEL：LEV+1LEV+1ADRADR：DXDXCONST A=35，B=49；VAR C，D，E；PROCEDURE P；VAR G表格管理表格管理 名字 類型 層次/值 地址 存儲空間編譯原理講義變量定義語句的處

29、理變量定義語句的處理 if sym=varsym then if sym=varsym thenbeginbegin getsym; getsym; repeat repeat vardeclaration; vardeclaration; while sym=comma do while sym=comma do begin begin getsym; getsym; vardeclaration vardeclaration end; end; if sym=semicolon then getsym if sym=semicolon then getsym else error(5) e

30、lse error(5) until symident; until symident;end;end;編譯原理講義40變量定義語句的處理變量定義語句的處理 p r o c e d u r e v a r d e c l a r a t i o n ; p r o c e d u r e v a r d e c l a r a t i o n ; begin begin i f s y m = i d e n t t h e n i f s y m = i d e n t t h e n begin begin e n t e r ( v a r i a b l e ) ; e n t e r

31、 ( v a r i a b l e ) ; getsym getsym end end else error(4) else error(4) end( end(* *vardeclarationvardeclaration* *););編譯原理講義41過程過程ENTERENTER的實現的實現 procedure enter(k:objects ); procedure enter(k:objects ); begin( begin(* *enter object into tableenter object into table* *) ) tx:=tx+1; tx:=tx+1; with

32、 tabletx do with tabletx do begin begin name:=id; name:=id; kind:=k; kind:=k; case k of case k of constant: begin constant: begin if numamax then if numamax then begin begin error(31); error(31); num:=0; num:=0; end; end; val:=num val:=num end; end;variable: begin level:=lev; adr:=dx; dx:=dx+1; end;

33、 procedur: level:=lev end endend(*enter*);編譯原理講義42過程體的分析過程體的分析從語法上要對語句逐句分析。從語法上要對語句逐句分析。當語法正確時就生成相應語句功能的目標代碼。當語法正確時就生成相應語句功能的目標代碼。當遇到標識符的引用時就調用當遇到標識符的引用時就調用POSITIONPOSITION函數查函數查TABLETABLE表，表，看是否有過正確定義，若已有，則從表中取相應的有關看是否有過正確定義，若已有，則從表中取相應的有關信息，供代碼的生成使用。若無定義則錯。信息，供代碼的生成使用。若無定義則錯。例：例：READREAD語句的語法語義分析處

34、理語句的語法語義分析處理 =READ(=READ(， )編譯原理講義43READREAD語句的語法語義分析處理語句的語法語義分析處理 if sym=readsym then if sym=readsym then begin begin getsym; getsym; if symlparen then error(34) if symlparen then error(34) else else repeat repeat getsym; getsym; if sym=ident then i:=position(id) if sym=ident then i:=position(id) e

35、lse i:=0; else i:=0; if i=0 then error(35) if i=0 then error(35) else else with tablei do with tablei do begin begin gen(opr,0,16); gen(opr,0,16); gen(sto,lev-level,adr) gen(sto,lev-level,adr) end; end; getsym getsym until symcomma; until symcomma; if symrparen then if symrparen then begin begin err

36、or(33); error(33); while not(sym in fsys) do getsym while not(sym in fsys) do getsym end end else getsym else getsym end end編譯原理講義44步驟步驟5 5、 PL/0PL/0編譯程序代碼生編譯程序代碼生成的實現成的實現PL/0PL/0語言的代碼生成是由過程語言的代碼生成是由過程GENGEN完成。完成。GENGEN有三個參數，分別代表目標代碼的功能碼，有三個參數，分別代表目標代碼的功能碼，層差和位移量。層差和位移量。gen(opr,0,16); gen(sto,lev-le

37、vel,adr)gen(opr,0,16); gen(sto,lev-level,adr)生成的代碼順序放在數組生成的代碼順序放在數組CODECODE中。中。 CODECODE為一維數組，數組元素為記錄型數據。每為一維數組，數組元素為記錄型數據。每一個記錄就是一條目標指令。一個記錄就是一條目標指令。CXCX為指令的指針，為指令的指針，由由0 0開始順序增加。實際上目標代碼的順序是內開始順序增加。實際上目標代碼的順序是內層過程的在前邊，主程序的目標代碼在最后。層過程的在前邊，主程序的目標代碼在最后。編譯原理講義45步驟步驟5 5、 PL/0PL/0編譯程序代碼生編譯程序代碼生成的實現成的實現 p

38、rocedure gen(x:fct;y, z:integer); procedure gen(x:fct;y, z:integer); begin begin if cxcxmax then if cxcxmax then begin begin write(program too long); write(program too long); close(fin); close(fin); writeln; writeln; exit exit end; end;with codecx do begin f:=x; l:=y; a:=z end; cx:=cx+1end (*gen*);編

39、譯原理講義46步驟步驟6 6、 PL/0PL/0編譯程序語法錯編譯程序語法錯誤處理的實現誤處理的實現對語法錯誤的兩種處理方法：對語法錯誤的兩種處理方法：(1)(1)對于易于校正的錯誤，如丟了逗號，分號對于易于校正的錯誤，如丟了逗號，分號等，指出出錯位置，加以校正，繼續進行分析等，指出出錯位置，加以校正，繼續進行分析(2)(2)對于難于校正的錯誤，給出錯誤的位置與對于難于校正的錯誤，給出錯誤的位置與性質，跳過后面的一些單詞，直到下一個可以性質，跳過后面的一些單詞，直到下一個可以進行正常語法分析的語法單位。進行正常語法分析的語法單位。編譯原理講義47步驟步驟6 6、 PL/0PL/0編譯程序語法錯

40、編譯程序語法錯誤處理的實現誤處理的實現在進入某個語法單位時，調用在進入某個語法單位時，調用TESTTEST濾去開始符號濾去開始符號前的所有符號。前的所有符號。在語法單位分析結束時，調用在語法單位分析結束時，調用TESTTEST濾去當前符號濾去當前符號到后繼符號之間的所有符號。到后繼符號之間的所有符號。 TEST TEST編譯原理講義48開始符號集合與后繼符號集合開始符號集合與后繼符號集合非終結符名非終結符名開始符號集合開始符號集合后繼符號集合后繼符號集合分程序分程序const var procedureconst var procedureident if call beginident if

41、 call beginwhile read writewhile read write. ;. ;語句語句ident call beginident call beginif while read writeif while read write. ; end. ; end條件條件odd + - (odd + - (ident numberident numberThen doThen do表達式表達式+ - (+ - (ident numberident number. ; ) rop. ; ) ropend then doend then do項項ident number (ident number (. ; ) rop + -. ; ) rop + -end then doend then do因子因子ident number (ident number (. ; ) rop + -. ; ) rop + -* / end then do*