第2章PL0編譯程序的實(shí)現(xiàn)(4學(xué)時(shí))

1、12何為何為PL/0PL/0語言語言? ?l PL/0PL/0語言：語言：PASCALPASCAL語言的子集，功語言的子集，功能簡(jiǎn)單，結(jié)構(gòu)清晰，可能簡(jiǎn)單，結(jié)構(gòu)清晰，可讀性強(qiáng)，具備了一般高讀性強(qiáng)，具備了一般高級(jí)語言的必備部分。級(jí)語言的必備部分。PL/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; WHIL

2、E X#0 DO CALL P; WHILE X#0 DO CALL P; END; END; BEGINBEGIN WRITE(D); WRITE(D); CALL Q; CALL Q;END;END;BEGINBEGINCALL P;CALL P;END.END.3PL/0PL/0編譯程序編譯程序pcodepcode解釋程序解釋程序PL/0PL/0源程序源程序注：此處的注：此處的pcodepcode代碼專指代碼專指PL/0PL/0的的目標(biāo)代碼，與傳統(tǒng)目標(biāo)代碼，與傳統(tǒng)pcodepcode有區(qū)別有區(qū)別pcodepcode代碼代碼42022-2-24NEXT5l數(shù)據(jù)類型只有數(shù)據(jù)類型只有整型整型l

3、標(biāo)識(shí)符標(biāo)識(shí)符的有效長(zhǎng)度是的有效長(zhǎng)度是1010，以字母開始的字母數(shù)字串，以字母開始的字母數(shù)字串l過程過程無參，可嵌套（最多三層），可遞歸調(diào)用無參，可嵌套（最多三層），可遞歸調(diào)用l變量的變量的作用域作用域同同PASCALPASCAL，常量為全局的，無標(biāo)常量為全局的，無標(biāo)l語句類型語句類型：賦值語句，：賦值語句，if.then., while.do., if.then., while.do., read, write, call, read, write, call, 復(fù)合語句復(fù)合語句begin. endbegin. end， 說明語句：說明語句： const., var., procedureco

4、nst., var., procedurel1313個(gè)個(gè)保留字保留字：if, then, while, do, read, write, call, if, then, while, do, read, write, call, begin, end, const, var, procedure, oddbegin, end, const, var, procedure, odd62022-2-24（1 1）語法成分中的最小單位，構(gòu)成語言文法的單詞。語法成分中的最小單位，構(gòu)成語言文法的單詞。（2 2）語法成分，在書寫程序時(shí)并不出現(xiàn)，但可一直追溯語法成分，在書寫程序時(shí)并不出現(xiàn)，但可一直追溯成成

5、V VT T 表示的形式。表示的形式。（13-1513-15頁）頁）7BNFBNF（BACKUS-NAUR FORMBACKUS-NAUR FORM）是根據(jù)美國(guó)的是根據(jù)美國(guó)的John W.BackusJohn W.Backus與丹麥的與丹麥的Peter NaurPeter Naur來命名的，它從語法上描述程序設(shè)計(jì)語言的元語言。來命名的，它從語法上描述程序設(shè)計(jì)語言的元語言。采用采用BNFBNF可說明哪些符號(hào)序列是對(duì)于某給定語言在語法上有效的程序。可說明哪些符號(hào)序列是對(duì)于某給定語言在語法上有效的程序。BNFBNF引入的符號(hào)：引入的符號(hào)： 表示語法構(gòu)造成分（語法單位），為表示語法構(gòu)造成分（語法單位）

6、，為= 定義為定義為| | 或或EBNFEBNF引入的符號(hào)：引入的符號(hào)： 表示花括號(hào)內(nèi)的語法成分表示花括號(hào)內(nèi)的語法成分可重復(fù)可重復(fù) 表示方括號(hào)內(nèi)的語法成分為表示方括號(hào)內(nèi)的語法成分為任選項(xiàng)任選項(xiàng)( )( ) 表示圓括號(hào)內(nèi)的成分表示圓括號(hào)內(nèi)的成分優(yōu)先優(yōu)先88兩個(gè)用兩個(gè)用EBNFEBNF描述描述“整數(shù)整數(shù)”的例子的例子練習(xí)：練習(xí)：P.31 P.31 題題6 6（2 2）（）（3 3） 991010語法語義分析程序語法語義分析程序詞法分析程序詞法分析程序表格管理程序表格管理程序出錯(cuò)處理程序出錯(cuò)處理程序代碼生成程序代碼生成程序目標(biāo)程序目標(biāo)程序PL/0PL/0源程序源程序目標(biāo)程序目標(biāo)程序解釋執(zhí)行程序輸入數(shù)

7、據(jù)結(jié)果結(jié)果1111啟動(dòng)啟動(dòng)置初值置初值調(diào)用GETSYM取單詞調(diào)用GETSYM取單詞調(diào)用BLOCK過程調(diào)用BLOCK過程當(dāng)前單詞當(dāng)前單詞是否為源程序結(jié)束符是否為源程序結(jié)束符.？.？出錯(cuò)出錯(cuò)源程序中源程序中是否有錯(cuò)誤？是否有錯(cuò)誤？調(diào)用解釋過程INTERPRET調(diào)用解釋過程INTERPRET解釋執(zhí)行目標(biāo)程序解釋執(zhí)行目標(biāo)程序打印錯(cuò)誤打印錯(cuò)誤結(jié)束結(jié)束N NY YY YN N編譯程序總體流程圖編譯程序總體流程圖 17頁頁1212所需識(shí)別的單詞：所需識(shí)別的單詞： 關(guān)鍵字關(guān)鍵字： 如如 BEGINBEGIN、ENDEND、IFIF、THEN THEN 等等 運(yùn)算符運(yùn)算符： 如如 + +、- -、* *、/ /

8、、：、：= =、# #、=、= = 等等 標(biāo)識(shí)符標(biāo)識(shí)符： 用戶定義的變量名、常數(shù)名、過程名用戶定義的變量名、常數(shù)名、過程名 常數(shù)常數(shù)： 如如 10 10、2525、100 100 等整數(shù)等整數(shù) 界符界符： 如如 , . ; ( ) , . ; ( ) 等等2.3 PL/02.3 PL/0編譯程序的詞法分析編譯程序的詞法分析詞法分析過程詞法分析過程GETSYM GETSYM 所要完成的任務(wù)：所要完成的任務(wù)：濾空格、識(shí)別保留字、識(shí)別濾空格、識(shí)別保留字、識(shí)別標(biāo)識(shí)符、拼數(shù)、拼復(fù)合詞、輸出源程序標(biāo)識(shí)符、拼數(shù)、拼復(fù)合詞、輸出源程序 參見參見 P.19 P.19 圖圖通過通過 將識(shí)別出的單詞信息傳遞給語法分

9、析程序?qū)⒆R(shí)別出的單詞信息傳遞給語法分析程序SYMSYM： 存放單詞的類別存放單詞的類別, ,如如 beginsym, ident, numberbeginsym, ident, numberIDID ： 存放用戶所定義的標(biāo)識(shí)符的值存放用戶所定義的標(biāo)識(shí)符的值NUMNUM： 存放用戶定義的數(shù)存放用戶定義的數(shù)1313 程序程序 pl/0分程序分程序 block語句語句 statement條件條件 condition表達(dá)式表達(dá)式expression項(xiàng)項(xiàng) term因子因子 factor語法分析的語法分析的任務(wù)任務(wù)：識(shí)別由詞法分析給出的單詞符號(hào)識(shí)別由詞法分析給出的單詞符號(hào)序列在序列在“結(jié)構(gòu)結(jié)構(gòu)”上是否符合

10、給定上是否符合給定的的“文法規(guī)則文法規(guī)則”。語法分析的語法分析的過程過程：從讀入第一個(gè)單詞開始，由從讀入第一個(gè)單詞開始，由V VN N “程序程序”出發(fā)，沿語法圖箭頭所出發(fā)，沿語法圖箭頭所指進(jìn)行分析指進(jìn)行分析: : 遇到遇到V VN N ，調(diào)用相應(yīng)的處理過程調(diào)用相應(yīng)的處理過程 遇到遇到V VT T ，判斷當(dāng)前單詞是否與判斷當(dāng)前單詞是否與V VT T 匹配匹配l 若若匹配匹配：執(zhí)行語義程序，：執(zhí)行語義程序，翻譯成目標(biāo)代碼翻譯成目標(biāo)代碼l 若若不匹配不匹配：報(bào)錯(cuò)：報(bào)錯(cuò)PL/0PL/0語法調(diào)用關(guān)系圖語法調(diào)用關(guān)系圖：1414 說明部分說明部分的處理的處理名字表需要填寫：名字表需要填寫： 所在層次所在層

11、次 標(biāo)識(shí)符的屬性標(biāo)識(shí)符的屬性 分配的相對(duì)位置分配的相對(duì)位置（標(biāo)識(shí)符的屬性不同時(shí)，所需填入的信息也不同。登錄信息由（標(biāo)識(shí)符的屬性不同時(shí)，所需填入的信息也不同。登錄信息由ENTERENTER過程完成。）過程完成。） 程序體程序體的處理的處理1515名字名字 類型類型 層次層次/ /值值 地址地址 存儲(chǔ)空間存儲(chǔ)空間N NA AM ME E：A AN NA AM ME E：B BN NA AM ME E：C CN NA AM ME E：D DN NA AM ME E：E EN NA AM ME E：P PK KI IN ND D：C CO ON NS ST TA AN NT TK KI IN ND D

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

13、 EV VA AD DR R：D DX XA AD DR R：D DX X+ +1 1A AD DR R：D DX X+ +2 2A AD DR R：S SI IZ ZE E：4 4N NA AM ME E：G G K KI IN ND D：V VA AR RI IA AB BL LE EL LE EV VE EL L：L LE EV V+ +1 1A AD DR R：D DX XCONST A=35，B=49；VAR C，D，E；PROCEDURE P；VAR G表格管理舉例表格管理舉例TX0TX1注：注：TXTX為索引表的指針為索引表的指針1616名字名字 類型類型 層次層次/ /值值 地

14、址地址 存儲(chǔ)空間存儲(chǔ)空間TX0TX1TX2TX3TX41717 目標(biāo)代碼目標(biāo)代碼pcodepcode是是一種假想棧式計(jì)算機(jī)的匯編語言。一種假想棧式計(jì)算機(jī)的匯編語言。 指令格式指令格式 f l af l a2.5 2.5 PL/0PL/0編譯程序的目標(biāo)代碼結(jié)構(gòu)和代碼生成編譯程序的目標(biāo)代碼結(jié)構(gòu)和代碼生成功能碼功能碼層次差層次差通常為通常為“位移量位移量”根據(jù)不同的指令根據(jù)不同的指令有所不同有所不同1818LIT 0 aLIT 0 a將常量值取到運(yùn)行棧頂將常量值取到運(yùn)行棧頂LOD l aLOD l a將變量值放到棧頂將變量值放到棧頂STO l aSTO l a將棧頂內(nèi)容送入某變量單元中將棧頂內(nèi)容送入

15、某變量單元中CAL l aCAL l a調(diào)用過程調(diào)用過程INT 0 aINT 0 a在運(yùn)行棧中為被調(diào)用的過程開辟在運(yùn)行棧中為被調(diào)用的過程開辟a a個(gè)單元的數(shù)據(jù)區(qū)個(gè)單元的數(shù)據(jù)區(qū)JMP 0 aJMP 0 a無條件跳轉(zhuǎn)至無條件跳轉(zhuǎn)至a a地址地址JPC 0 aJPC 0 a條件跳轉(zhuǎn)，當(dāng)棧頂布爾值非真則跳轉(zhuǎn)至條件跳轉(zhuǎn)，當(dāng)棧頂布爾值非真則跳轉(zhuǎn)至a a地址，否則順地址，否則順序執(zhí)行序執(zhí)行OPR 0 0OPR 0 0函數(shù)調(diào)用結(jié)束后的返回函數(shù)調(diào)用結(jié)束后的返回OPR 0 1OPR 0 1棧頂元素取反棧頂元素取反OPR 0 2OPR 0 2次棧頂與棧頂相加，退兩個(gè)棧元素，相加值進(jìn)棧次棧頂與棧頂相加，退兩個(gè)棧元素，

16、相加值進(jìn)棧OPR 0 3OPR 0 3次棧頂減支棧頂次棧頂減支棧頂OPR 0 4OPR 0 4次棧頂乘以棧頂次棧頂乘以棧頂OPR 0 5OPR 0 5次棧頂除以棧頂次棧頂除以棧頂OPR 0 6OPR 0 6棧頂元素的奇偶判斷棧頂元素的奇偶判斷OPR 0 7OPR 0 7OPR 0 8OPR 0 8次棧頂與棧頂是否相等次棧頂與棧頂是否相等OPR 0 9OPR 0 9次棧頂與棧頂是否不等次棧頂與棧頂是否不等OPR 0 10OPR 0 10次棧頂是否小于棧頂次棧頂是否小于棧頂OPR 0 11OPR 0 11次棧頂是否大于等于棧頂次棧頂是否大于等于棧頂OPR 0 12OPR 0 12次棧頂是否大于棧頂

17、次棧頂是否大于棧頂OPR 0 13OPR 0 13次棧頂是否小于等于棧頂次棧頂是否小于等于棧頂OPR 0 14OPR 0 14棧頂值輸出至屏幕棧頂值輸出至屏幕OPR 0 15OPR 0 15屏幕輸出換行屏幕輸出換行OPR 0 16OPR 0 16從命令行讀入一個(gè)輸入置于棧頂從命令行讀入一個(gè)輸入置于棧頂目標(biāo)指令目標(biāo)指令19190 jmp 0 8 無條件跳轉(zhuǎn)至81 jmp 0 2 無條件跳轉(zhuǎn)至22 int 0 3 在棧頂中申請(qǐng)?jiān)跅ｍ斨猩暾?qǐng)3個(gè)?？臻g個(gè)?？臻g3 lod 1 3 將變量取至棧頂將變量取至棧頂（1層差層差, 3相對(duì)位置）相對(duì)位置）4 lit0 10 將常數(shù)將常數(shù)1010取至棧頂取至棧頂5

18、 opr 0 2 次棧頂與棧頂相加次棧頂與棧頂相加6 sto1 4 將棧頂值存入變量將棧頂值存入變量7 opr 0 0 函數(shù)調(diào)用結(jié)束后返回函數(shù)調(diào)用結(jié)束后返回8 int 0 5 在運(yùn)行棧中申請(qǐng)?jiān)谶\(yùn)行棧中申請(qǐng)5個(gè)?？臻g個(gè)棧空間9 opr 0 16 從命令行讀入輸入置于棧頂從命令行讀入輸入置于棧頂10 sto 0 3 將棧頂值存入變量將棧頂值存入變量11 cal 0 2 調(diào)用過程調(diào)用過程12 lod 0 4 將變量取至棧頂將變量取至棧頂13 opr 0 14 棧頂值輸出至屏幕棧頂值輸出至屏幕14 opr 0 15 換行換行15 opr 0 0 函數(shù)調(diào)用結(jié)束后返回函數(shù)調(diào)用結(jié)束后返回Const a=10

19、;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); read(b); call p; call p; write(c); write(c);end.end.目標(biāo)代碼舉例目標(biāo)代碼舉例參見P242020 PL/0PL/0語言的代碼生成是由過程語言的代碼生成是由過程GEN GEN 完成。完成。 GENGEN有三個(gè)參數(shù)，分別代表目標(biāo)代碼的有三個(gè)參數(shù)，分別代表目標(biāo)代碼的功能碼功能碼，層差層差和和位位移量移量。gen(opr,0,16); gen(sto,lev-level,adr)gen(opr,0,16); gen(sto,lev-level,adr) 生成的代碼順序放在數(shù)組生成的代碼順序放在數(shù)組CODECODE中。中。CODECODE為一維數(shù)組，數(shù)組元素為記錄型數(shù)據(jù)。為一維數(shù)組，數(shù)組元素為記錄型數(shù)據(jù)。每一個(gè)記錄就是一條目標(biāo)指令。每一個(gè)記錄就是一條目標(biāo)指令。CXCX為指令的指針，由為指令的指針，由0 0開始順序增加。開始順序增加。實(shí)際上目標(biāo)代碼的順序：內(nèi)層過程在前邊，主程序的目標(biāo)代碼實(shí)際上目標(biāo)代碼的順序：內(nèi)層過程在前邊，主程序的目