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

1、12何為何為PL/0PL/0語(yǔ)言語(yǔ)言? ?l PL/0PL/0語(yǔ)言：語(yǔ)言：PASCALPASCAL語(yǔ)言的子集，功語(yǔ)言的子集，功能簡(jiǎn)單，結(jié)構(gòu)清晰，可能簡(jiǎn)單，結(jié)構(gòu)清晰，可讀性強(qiáng)，具備了一般高讀性強(qiáng)，具備了一般高級(jí)語(yǔ)言的必備部分。級(jí)語(yǔ)言的必備部分。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代碼代碼42021-11-21NEXT51.1.數(shù)據(jù)類型只有數(shù)據(jù)類型只有整

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

4、ar., procedureconst., var., procedure6.6.1313個(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, odd62021-11-21（1 1）語(yǔ)法成分中的最小單位，構(gòu)成語(yǔ)言文法的單詞。語(yǔ)法成分中的最小單位，構(gòu)成語(yǔ)言文法的單詞。（2 2）語(yǔ)法成分，在書(shū)寫(xiě)程序時(shí)并不出現(xiàn)，但可一直追溯語(yǔ)法成分，

5、在書(shū)寫(xiě)程序時(shí)并不出現(xiàn)，但可一直追溯成成 V VT T 表示的形式。表示的形式。（13-1513-15頁(yè)）頁(yè)）7BNFBNF（BACKUS-NAUR FORMBACKUS-NAUR FORM）是根據(jù)美國(guó)的是根據(jù)美國(guó)的John W.BackusJohn W.Backus與丹麥的與丹麥的Peter NaurPeter Naur來(lái)命名的，它從語(yǔ)法上描述程序設(shè)計(jì)語(yǔ)言的元語(yǔ)言。來(lái)命名的，它從語(yǔ)法上描述程序設(shè)計(jì)語(yǔ)言的元語(yǔ)言。采用采用BNFBNF可說(shuō)明哪些符號(hào)序列是對(duì)于某給定語(yǔ)言在語(yǔ)法上有效的程序。可說(shuō)明哪些符號(hào)序列是對(duì)于某給定語(yǔ)言在語(yǔ)法上有效的程序。BNFBNF引入的符號(hào)：引入的符號(hào)： 表示語(yǔ)法構(gòu)造成分（語(yǔ)

6、法單位），為表示語(yǔ)法構(gòu)造成分（語(yǔ)法單位），為= 定義為定義為| | 或或EBNFEBNF引入的符號(hào)：引入的符號(hào)： 表示花括號(hào)內(nèi)的語(yǔ)法成分表示花括號(hào)內(nèi)的語(yǔ)法成分可重復(fù)可重復(fù) 表示方括號(hào)內(nèi)的語(yǔ)法成分為表示方括號(hào)內(nèi)的語(yǔ)法成分為任選項(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語(yǔ)法語(yǔ)義分析程序語(yǔ)法語(yǔ)義分析程序詞法分析程序詞法分析程序表格管理程序表格管理程序出錯(cuò)處理程序出錯(cuò)處理程序代碼生成程序代碼生成程序目標(biāo)程序目標(biāo)程序PL/0PL/0源程序

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

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

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

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

11、要填寫(xiě)：名字表需要填寫(xiě)： 所在層次所在層次 標(biāo)識(shí)符的屬性標(biāo)識(shí)符的屬性 分配的相對(duì)位置分配的相對(duì)位置（標(biāo)識(shí)符的屬性不同時(shí)，所需填入的信息也不同。登錄信息由（標(biāo)識(shí)符的屬性不同時(shí)，所需填入的信息也不同。登錄信息由ENTERENTER過(guò)程完成。）過(guò)程完成。） 程序體程序體的處理的處理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

12、 AN NT TK KI IN ND D：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 V

13、L LE EV VE EL L：L LE 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ī)的匯編語(yǔ)言。一種假想棧式計(jì)算機(jī)的匯編語(yǔ)言。 指令格式指令格式 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

15、將棧頂內(nèi)容送入某變量單元中將棧頂內(nèi)容送入某變量單元中CAL l aCAL l a調(diào)用過(guò)程調(diào)用過(guò)程INT 0 aINT 0 a在運(yùn)行棧中為被調(diào)用的過(guò)程開(kāi)辟在運(yùn)行棧中為被調(diào)用的過(guò)程開(kāi)辟a a個(gè)單元的數(shù)據(jù)區(qū)個(gè)單元的數(shù)據(jù)區(qū)JMP 0 aJMP 0 a無(wú)條件跳轉(zhuǎn)至無(wú)條件跳轉(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è)棧元素，相

16、加值進(jìn)棧次棧頂與棧頂相加，退兩個(gè)棧元素，相加值進(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

17、 12OPR 0 12次棧頂是否大于棧頂次棧頂是否大于棧頂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 無(wú)條件跳轉(zhuǎn)至81 jmp 0 2 無(wú)條件跳轉(zhuǎn)至22 int 0 3 在棧頂中申請(qǐng)?jiān)跅ｍ斨猩暾?qǐng)3個(gè)?？臻g個(gè)棧空間3 lod 1 3 將變量取至棧頂將變量取至棧頂（1層差層差, 3相對(duì)位置）相對(duì)位置）4 lit0 10

18、 將常數(shù)將常數(shù)1010取至棧頂取至棧頂5 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è)?？臻g9 opr 0 16 從命令行讀入輸入置于棧頂從命令行讀入輸入置于棧頂10 sto 0 3 將棧頂值存入變量將棧頂值存入變量11 cal 0 2 調(diào)用過(guò)程調(diào)用過(guò)程12 lod 0 4 將變量取至棧頂將變量取至棧頂13 opr 0 14 棧頂值輸出至屏幕棧頂值輸出至屏幕14 opr 0 15 換行換行15 opr 0 0 函數(shù)調(diào)用結(jié)束后返

19、回函數(shù)調(diào)用結(jié)束后返回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); read(b); call p; call p; write(c); write(c);end.end.目標(biāo)代碼舉例目標(biāo)代碼舉例參見(jiàn)P242020 PL/0PL/0語(yǔ)言的代碼生成是由過(guò)程語(yǔ)言的代碼生成是由過(guò)程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開(kāi)始順序增加。開(kāi)始順序增加。實(shí)際上目標(biāo)代碼的順序：內(nèi)層過(guò)程在前邊，主程序的目標(biāo)代碼實(shí)際上目標(biāo)代碼的順序：內(nèi)層過(guò)程在前邊，主程序