程序員玩轉(zhuǎn)算法清華教程-編譯原理

第2章

PL/0編譯程序的實(shí)現(xiàn)功能PL/0編譯程序PL/0語言類pcode源語言(PL/0)目標(biāo)語言(類pcode)實(shí)現(xiàn)語言（pascal)PL/0類pcodepascal類pcode是中間代碼PL/0編譯程序類pcode代碼類pcode解釋程序輸入

輸出PL/0源程序PL/0編譯程序功能的框架第2章

PL/0編譯程序的實(shí)現(xiàn)步驟1.認(rèn)識源語言PL/0與目標(biāo)代碼類pcode及它們之間的步驟2.PL/0編譯程序的總體設(shè)計(jì)步驟3.PL/0編譯程序詞法分析的設(shè)計(jì)與實(shí)現(xiàn)步驟4.

PL/0編譯程序語法語義分析的設(shè)計(jì)與實(shí)現(xiàn)第2章

PL/0編譯程序的實(shí)現(xiàn)步驟5.

PL/0編譯程序代碼生成的實(shí)現(xiàn)步驟6.

PL/0編譯程序錯(cuò)誤處理的實(shí)現(xiàn)步驟7.類pcode代碼解釋器的設(shè)計(jì)與實(shí)現(xiàn)步驟1.認(rèn)識源語言PL/0與目標(biāo)代碼類pcode及它們之間的何為PL/0語言認(rèn)識目標(biāo)代碼類pcodePL/0程序到類pcode代碼的何為PL/0語言PL/0語言：PASCAL語言的子集，功能簡單，結(jié)構(gòu)清晰，可讀性強(qiáng)，具備了一般高級語言的必備部分(如:read,write,while-do,if-then,call,begin-end,賦值語句等）PL/0程序示例PL/0的語法描述圖PL/0語言文法的EBNF表示PL/0的實(shí)用限制（語用）PL/0程序示例1：計(jì)算園面積const

p=3;

（*常量說明部分*）var

s,r;

（*變量說明部分*）beingread(r);while

r#0

dobegins:=p*r*r;write(s)

;read(r);end;end.程序體PL/0程序示例2CONST

A=10;（*常量說明部分*）VAR

B,C;（*變量說明部分*）PROCEDURE

P;（*過程說明部分*）VAR

D;PROCEDURE

Q;VAR

X;BEGINREAD(X);D:=

D

*

C

+X;WRITE(D);WHILE

X#0

DO

CALL

P;END;Q的過程體PL/0程序示例2BEGINREAD(D

,

C);CALL

Q;END;BEGINCALL

P;END.p的過程體主程序體CONSTA=10;VAR

B,C;PROCEDURE

P;VAR

D;PROCEDURE

Q;VAR

X;BEGINREAD(X);D:=D*

C

+X;WRITE(D);WHILEX#0

DO

CALL

P;END;BEGINCALL

Q;END;BEGINCALL

P;END.主程序體READ(D,C);p的過程體Q的過程體主程序說明標(biāo)識符的作用范圍過程可以

自己定義的局部標(biāo)識符，也可以

包圍它的外過程定義的局部標(biāo)識符。PL/0的語法描述圖程序分程序.內(nèi)的文字表示非終結(jié)符或內(nèi)的文字或符號表示終結(jié)符非終結(jié)符：可由其它文法符號定義終結(jié)符：不能由其它文法符號定義constidentnumber=,;varident,;;procedureident;分程序語句分程序PL/0語言文法的EBNF表示BNF與EBNF的介紹BNF（BACKUS-NAUR

FORM）是根據(jù)

的JohnW.Backus與丹麥的PeterNaur命名的，可用它作為描述程序設(shè)計(jì)語言語法的工具。采用BNF描述的語法可以檢查哪些符號序列

是某給定語言的合法程序。一個(gè)語言的語法圖或EBNF的形式描述，是該語言編譯程序構(gòu)造的依據(jù)。PL/0語言文法的EBNF表示BNF與EBNF的介紹BNF

引入的符號：<

>

用左右尖括號括起來的語法成分為非終結(jié)符∷=

‘定義為’（∷=的左部用右部定義）|

‘或’EBNF

引入的符號：{}

表示花括號內(nèi)的語法成分可重復(fù)任意次或限3定次數(shù)如：{*}重復(fù)任意次,{*}8重復(fù)3-8次[]表示方括號內(nèi)的語法成分為任選項(xiàng)()表示圓括號內(nèi)的成分優(yōu)先PL/0語言文法的EBNF表示例:用EBNF描述整數(shù)的定義：<整數(shù)>∷=[+|-]<數(shù)字>{<數(shù)字>}<數(shù)字>∷=0|1|2|3|4|5|6|7|8|9或更好的寫法為：<整數(shù)>∷=[+|-]<非零數(shù)字>{<數(shù)字>}|0<非零數(shù)字>∷=1|2|3|4|5|6|7|8|9<數(shù)字>∷=0|<非零數(shù)字>PL/0語言文法的EBNF表示PL/0語言文法的EBNF表示〈程序〉::=〈分程序〉.〈分程序〉∷=[〈常量說明部分〉][〈變量說明部分〉][〈過程說明部分〉]〈語句〉〈常量說明部分〉∷=CONST〈常量定義〉{，〈常量定義〉}；〈常量定義〉∷=〈標(biāo)識符〉=〈無符號整數(shù)〉〈無符號整數(shù)〉∷=〈數(shù)字〉{〈數(shù)字〉}PL/0語言文法的EBNF表示〈變量說明部分〉∷=VAR〈標(biāo)識符〉{，〈標(biāo)識符〉}；〈標(biāo)識符〉∷=〈字母〉{〈字母〉|〈數(shù)字〉}〈過程說明部分〉∷=〈過程首部〉〈分程序〉{；〈過程說明部分〉}；〈過程首部〉∷=PROCEDURE〈標(biāo)識符〉；〈語句〉∷=〈賦值語句〉|〈條件語句〉PL/0語言文法的EBNF表示|〈當(dāng)型循環(huán)語句〉|〈過程調(diào)用語句〉|〈讀語句〉|〈寫語句〉|〈復(fù)合語句〉|〈空〉〈賦值語句〉∷=〈標(biāo)識符〉：=〈表達(dá)式〉〈復(fù)合語句〉∷=BEGIN〈語句〉{；〈語句〉}END〈條件〉∷=〈表達(dá)式〉〈關(guān)系運(yùn)算符〉〈表達(dá)式〉|ODD〈表達(dá)式〉語法描述圖與EBNF表示的比較語法描述圖直觀，易讀，易寫。EBNF表示形式化強(qiáng)，易機(jī)器識別。通常設(shè)計(jì)

一個(gè)語言時(shí)，對文法的兩種描述都要給出。認(rèn)識目標(biāo)代碼類pcodefla目標(biāo)代碼類pcode是一種假想棧式計(jì)算機(jī)的匯編語言。指令格式f

功能碼l

層次差

（標(biāo)識符的

層減去它的定義層）a

根據(jù)不同的指令有所區(qū)別假想棧式計(jì)算機(jī)的運(yùn)行棧T是棧頂

B是

址TB每個(gè)過程被調(diào)用時(shí)分配一段數(shù)據(jù)空間，變量的位置從3開始。RADLSL210LIT

0

a將常數(shù)值取到棧頂，a為常數(shù)值LOD

l

a將變量值取到棧頂，a為偏移量，l為層差STO

l

a將棧頂內(nèi)容送入某變量單元中，a為偏移量，l為層差CAL

l

a調(diào)用過程，a為過程地址，l為層差I(lǐng)NT

0

a在運(yùn)行棧中為被調(diào)用的過程開辟a個(gè)單元的數(shù)據(jù)區(qū)JMP

0

a無條件跳轉(zhuǎn)至a地址JPC

0

a條件跳轉(zhuǎn)，當(dāng)棧頂布爾值非真則跳轉(zhuǎn)至a地址，否則順序執(zhí)行OPR

0

0過程調(diào)用結(jié)束后,返回調(diào)用點(diǎn)并退棧OPR

0

1棧頂元素取反OPR

0

2次棧頂與棧頂相加，退兩個(gè)棧元素，結(jié)果值進(jìn)棧OPR

0

3次棧頂減去棧頂，退兩個(gè)棧元素，結(jié)果值進(jìn)棧OPR

0

4次棧頂乘以棧頂，退兩個(gè)棧元素，結(jié)果值進(jìn)棧OPR

0

5次棧頂除以棧頂，退兩個(gè)棧元素，結(jié)果值進(jìn)棧OPR

0

6棧頂元素的奇偶判斷，結(jié)果值在棧頂OPR

0

7OPR

0

8次棧頂與棧頂是否相等，退兩個(gè)棧元素，結(jié)果值進(jìn)棧OPR

0

9次棧頂與棧頂是否不等，退兩個(gè)棧元素，結(jié)果值進(jìn)棧OPR

0

10次棧頂是否小于棧頂，退兩個(gè)棧元素，結(jié)果值進(jìn)棧OPR

0

11次棧頂是否大于等于棧頂，退兩個(gè)棧元素，結(jié)果值進(jìn)棧OPR

0

12次棧頂是否大于棧頂，退兩個(gè)棧元素，結(jié)果值進(jìn)棧OPR

0

13次棧頂是否小于等于棧頂，退兩個(gè)棧元素，結(jié)果值進(jìn)棧OPR

0

14棧頂值輸出至屏幕OPR

0

15屏幕輸出換行OPR

0

16從命令行讀入一個(gè)輸入置于棧頂指令功能表+_*/關(guān)系運(yùn)算PL/0程序到類pcode代碼的例如：一個(gè)PL/0程序到類pcode代碼的（編譯過程是按源程序順序進(jìn)行分析的）（常量變量說明部分不產(chǎn)生目標(biāo)代碼）const

p=3;var

s,r;beingread(r);while

r#0

dobegins:=p*r*r;write(s)

;read(r);end;end.jmp

0

1int

0

5opr

0

16sto

0

4lod

0

4lit

0

0opr

0

9jpc

0

20lit

0

3lod

0

4opr

0

4lod

0

4opr

0

4sto

0

3lod

0

3opr

0

14opr

0

15opr

0

16sto

0

4jmp

0

4opr

0

0const

a=10;var

b,c;procedure

p;beginc:=b+a;end;beginread(b);while

b#0

dobegincall

p;write(2*c);read(b);endend.轉(zhuǎn)向主程序轉(zhuǎn)向過程p過程p ,為過程p開辟空間(0)jmp

0

8(1)jmp

0

2(2)

int

0

3(3)lod

13取變量b的值到棧頂(4)lit

0

10取常數(shù)10到棧頂次棧頂與棧頂相加棧頂值送變量c中退棧并返回調(diào)用點(diǎn)(16)(5)opr

0

2(6)sto

14(7)

opr

0

0(8)

int

0

5主程序

開辟5個(gè)?？臻g(9)opr

0

16從命令行讀入輸入置于棧頂sto

0

3lod

0

3lit

0

0opr

0

9將棧頂值存入變量b中將變量b的值取至棧頂將常數(shù)值0進(jìn)棧次棧頂與棧頂是否不等(14)jpc

0

24

等時(shí)轉(zhuǎn)(24)（條件不滿足轉(zhuǎn)）cal0

2lit

0

2lod

0

4opr

0

4調(diào)用過程p常數(shù)值2進(jìn)棧將變量c的值取至棧頂次棧頂與棧頂相乘(2*c)opr

0

14棧頂值輸出至屏幕opr

015換行(21)

opr

016

從命令行

輸入到棧頂(22)sto

0

3

棧頂值送變量b中(23)

jmp

0

11

無條件轉(zhuǎn)到循環(huán)

(11)

(24)opr

0

0

結(jié)束退棧PL/0的實(shí)用限制（語用）標(biāo)識符的有效長度是10數(shù)字最多為14位過程最多可嵌套三層，可遞歸調(diào)用標(biāo)識符的作用域同PASCAL，內(nèi)層可包圍它的外層定義的標(biāo)識符（如：變量名，過程名，常量名）步驟2

PL/0編譯程序的總體設(shè)計(jì)詞法分析程代碼生成程序表格管理程序出錯(cuò)處理程序PL/0源程序序語法語義分析程序目標(biāo)程序步驟2

PL/0編譯程序的總體設(shè)計(jì)其編譯過程采用一趟掃描方式以語法、語義分析程序?yàn)樵~法分析程序和代碼生成程序都作為一個(gè)獨(dú)立的過程，當(dāng)語法分析需要讀單詞時(shí)就調(diào)用詞法分析程序，而當(dāng)語法、語義分析正確，需要生成相應(yīng)的目標(biāo)代碼時(shí)，則調(diào)用代碼生成程序。步驟2

PL/0編譯程序的總體設(shè)計(jì)用表格管理程序建立變量，常量和過程標(biāo)識符的說明與

之間的信息聯(lián)系。用出錯(cuò)處理程序，對詞法和語法、語義分析遇到的錯(cuò)誤給出在源程序中出錯(cuò)的位置和錯(cuò)誤性質(zhì)。步驟3

PL/0編譯程序詞法分析的設(shè)計(jì)與實(shí)現(xiàn)所需識別的單詞基本字（保留字或關(guān)鍵字）：如：BEGIN、END、IF、THEN等運(yùn)算符：如：+、-、*、/、：=、#、>=、<=等標(biāo)識符：用戶定義的變量名、常數(shù)名、過程名常數(shù)：

如：10、25、100等整數(shù)界符：

如：‘,’、‘.’

、‘;’

、‘(’

、‘)’等步驟3

PL/0編譯程序詞法分析的設(shè)計(jì)與實(shí)現(xiàn)詞法分析過程GETSYM所要完成的任務(wù)濾空格識別保留字（關(guān)鍵字\基本字)識別標(biāo)識符拼數(shù)拼復(fù)合詞輸出源程序步驟3

PL/0編譯程序詞法分析的設(shè)計(jì)與實(shí)現(xiàn)詞法分析程序的設(shè)計(jì)---使用狀態(tài)轉(zhuǎn)換圖實(shí)現(xiàn)表示狀態(tài)，對應(yīng)每個(gè)狀態(tài)編一段程序，每個(gè)狀態(tài)調(diào)用取字符程序，根據(jù)當(dāng)前字符轉(zhuǎn)到不同的狀態(tài)，并做相應(yīng)操作。表示終態(tài)，已識別出一個(gè)單詞。PL\0語言詞法分析的狀態(tài)轉(zhuǎn)換圖步驟3

PL/0編譯程序詞法分析的設(shè)計(jì)與實(shí)現(xiàn)詞法分析過程:GETSYM框圖（見15頁圖2.5）程序文本（見290-292頁）當(dāng)識別到標(biāo)識符時(shí)先查關(guān)鍵字表關(guān)鍵字表：（見304頁主程序）word[1]:=‘begin

‘;word[2]:=‘call

‘；...word[13]:=‘write

‘;步驟3

PL/0編譯程序詞法分析的設(shè)計(jì)與實(shí)現(xiàn)查到時(shí)找到相應(yīng)的表示W(wǎng)sym[1]:=beginsym;

wsym[2]:=callsym;…wsym[13]:=writesym;字符對應(yīng)的單詞表：ssym[‘+’]:=plus;

ssym[‘-’]:=minus;…ssym[‘;’]:=semicolon;步驟3

PL/0編譯程序詞法分析的設(shè)計(jì)與實(shí)現(xiàn)詞法分析如何把單詞傳遞給語法分析單詞定義（見

288頁）type

symbol=(nul,ident,number,plus,…,varsym,procsym);（定義純量/枚舉類型，類似C的enum）sym:symbol;id:alfa;(type

alfa=packed

array[1..al]

of

char)al=10;num:integer;步驟3

PL/0編譯程序詞法分析的設(shè)計(jì)與實(shí)現(xiàn)通過三個(gè)全程量SYM、ID和NUM將識別出的單詞信息傳遞給語法分析程序。SYM：存放單詞的類別如：begin60beginsym,

initial

ident,numberID：

存放用戶所定義的標(biāo)識符的值

如：initial

（在SYM中放ident，在ID中放initial）NUM：存放用戶定義的數(shù)

如：60（在SYM中放在number在NUM中放60）步驟4

PL/0編譯程序語法、語義分析的設(shè)計(jì)與實(shí)現(xiàn)語法分析的設(shè)計(jì)與實(shí)現(xiàn)自頂向下的語法分析遞歸子程序法例：如何用遞歸子程序法實(shí)現(xiàn)表達(dá)式的語法分析自頂向下的語法分析VAR

A;BEGINREAD(A)END.<程序>.<分程序><變量說明部分><語句>VAR

<標(biāo)識符>

；

<復(fù)合語句>A

BEGIN<語句>

END<讀語句>READ

（

<標(biāo)識符>）A<程序>為文法的開始符號，以開始符號作為根結(jié)點(diǎn),構(gòu)造一棵倒掛著的語法樹。樹的末端結(jié)點(diǎn)剛好為輸入的終結(jié)符號串。語法樹與EBNF對照PL/0語言文法的EBNF表示〈程序〉::=〈分程序〉.〈分程序〉∷=[〈常量說明部分〉][〈變量說明部分〉][〈過程說明部分〉]〈語句〉〈變量說明部分〉∷=VAR〈標(biāo)識符〉{，〈標(biāo)識符〉}；〈標(biāo)識符〉∷=〈字母〉{〈字母〉|〈數(shù)字〉}〈語句〉∷=〈賦值語句〉|〈條件語句〉|〈當(dāng)型循環(huán)語句〉|〈過程調(diào)用語句〉語法樹與EBNF對照|〈讀語句〉|〈寫語句〉|〈復(fù)合語句〉|〈空〉〈復(fù)合語句〉∷=BEGIN〈語句〉{；〈語句〉}END〈讀語句〉∷=READ‘（’〈標(biāo)識符〉{，〈標(biāo)識符〉}‘）’注：紅色為構(gòu)造例子語法樹時(shí)所選文

則的右部。語法樹的構(gòu)造：自頂向下，自左向右，若以EBNF某一規(guī)則的左部為父結(jié)點(diǎn)，那么它的右部的某一候選為子結(jié)點(diǎn)。constident

number=,;varident,;;procedureident;分程序語句分程序從語法圖看遞歸子程序法思想從語法圖看遞歸子程序法思想(begin)；語句endread，復(fù)合語句讀語句語句ident...ident......遞歸子程序法遞歸子程序法：對應(yīng)每個(gè)非終結(jié)符語法單元，，編一個(gè)獨(dú)立的處理過程（或子程序）。語法分析從讀入第一個(gè)單詞開始，由非終結(jié)符<程序>（即開始符）出發(fā)，沿語法描述圖箭頭所

的方向進(jìn)行分析。當(dāng)遇到非終結(jié)符時(shí)，則調(diào)用相應(yīng)的處理過程，從語法描述圖看，也就進(jìn)入了一個(gè)語法單元，再沿當(dāng)前所進(jìn)入的語法單元所指箭頭方向繼續(xù)進(jìn)行分析。遞歸子程序法當(dāng)遇到描述圖中是終結(jié)符時(shí)，則判斷當(dāng)前讀入的單詞是否與圖中的終結(jié)符相匹配，若匹配，則執(zhí)行相應(yīng)的語義程序（就是翻譯程序），再下一個(gè)單詞繼續(xù)分析。遇到分支點(diǎn)時(shí)，將當(dāng)前的單詞與分支點(diǎn)上多個(gè)終結(jié)符逐個(gè)相比較，若都不匹配時(shí)可能是進(jìn)入下一個(gè)非終結(jié)符語法單位或是出錯(cuò)。項(xiàng)表達(dá)式例：如何用遞歸子程序法實(shí)現(xiàn)表達(dá)式的語法分析+-項(xiàng)+-項(xiàng)因子*因子/因子的語法圖因子identnumber(表達(dá)式)例：如何用遞歸子程序法實(shí)現(xiàn)表達(dá)式的語法分析表達(dá)式的EBNF〈表達(dá)式〉∷=[+|-]〈項(xiàng)〉{（+|-）〈項(xiàng)〉}〈項(xiàng)〉∷=〈因子〉{（*|/）〈因子〉}〈因子〉∷=〈標(biāo)識符〉|〈無符號整數(shù)〉|‘（’〈表達(dá)式〉‘）’注意：[]、（

）、與‘（’‘）’的區(qū)別。[]、（

）是EBNF描述文法的元符號，‘（’‘）’是用戶定義的文法符號為了與元符號區(qū)別用引號括起。例：如何用遞歸子程序法實(shí)現(xiàn)表達(dá)式的語法分析〈表達(dá)式〉的實(shí)現(xiàn)（未加語義處理）procedure

expr;beginif

sym

in

[

plus,

minus

]

thenbegingetsym;

term;endelse

term;例：如何用遞歸子程序法實(shí)現(xiàn)表達(dá)式的語法分析while

sym

in

[plus,

minus]

dobegingetsym;

term;endend;in[plus,minus]為PASCAL語言對集合元素的表示方法。方括號內(nèi)是已定義的集合元素。例中類型定義：symset=set

of

symbol

（見288頁）時(shí)用：in[symbol中的某些元素]例：如何用遞歸子程序法實(shí)現(xiàn)表達(dá)式的語法分析〈項(xiàng)〉的實(shí)現(xiàn)procedure

term;beginfactor;while

sym

in

[

times,

slash

]

dobegingetsym;

factor;endend;例：如何用遞歸子程序法實(shí)現(xiàn)表達(dá)式的語法分析〈因子〉的實(shí)現(xiàn)

procedure

factor;beginif

sym

<>

ident

thenbeginif

sym

<>

number

thenbeginif

sym

=

‘(‘

thenbegin例：如何用遞歸子程序法實(shí)現(xiàn)表達(dá)式的語法分析getsym;expr;if

sym

=

‘)’

then

getsymelse

errorendelse

errorendendend;PL/0的語法調(diào)用關(guān)系圖和編譯程序?qū)崿F(xiàn)的流程圖對于整個(gè)PL/0來說，其語法調(diào)用關(guān)系圖和編譯程序?qū)崿F(xiàn)的總體流程圖在下面兩頁給出。程序

pl0分程序block語句statement條件condition表達(dá)式expression項(xiàng)

term因子factor語法調(diào)用關(guān)系圖編譯程序總體流程圖啟動(dòng)置初值調(diào)用GETSYM取單詞調(diào)用BLOCK過程出錯(cuò)源程序中是否有錯(cuò)誤？打印錯(cuò)誤結(jié)束NY當(dāng)前單詞是否為源程序結(jié)束符'.'？YN調(diào)用解釋過程INTERPRET解釋執(zhí)行目標(biāo)程序程序BLOCK過程的流程圖見

18頁語義分析與處理說明部分的分析表格管理過程體的分析說明部分的分析對每個(gè)過程說明的對象（變量，常量和過程）造名字表填寫標(biāo)識符的所在層次、屬性和分配的相對位置。標(biāo)識符的屬性不同時(shí)，所需填入的信息也不同。登錄信息由ENTER過程完成。說明部分的分析（程序）object=

(constant,

variable,procedur)（定義純量/枚舉類型）Table:array[0..txmax]

of

recordname:alfa;case

kind:object

ofconstant:(val:integer);variable:procedur:(level,adr,size:integer);end;Table的數(shù)組元素為變體記錄型,相當(dāng)C的union說明部分的分析（程序）對分程序的定義（見

292頁）procedureblock(lev,tx:integer;fsys:symset);var

dx:integer; (*data

allocationindex*)tx0:integer; (*initial

table

index*)cx0:integer; (*initial

code

index*)（

tx0，cx0是tx，cx的初值）第1次調(diào)用

BLOCK（0，0，…）（見

305頁）遞歸進(jìn)入分程序BLOCK（LEV+1,TX，…）說明部分的分析（程序）300頁block

的對分程序體人口的處理（見過程體）begin

(*block*)dx:=3;tx0:=tx;

（保留當(dāng)前table表指針值）table[tx].adr:=cx;（保留當(dāng)前code指針值到過程名的adr域）（注意dx，tx，cx的作用）NAME：AKIND：CONSTANTVAL：35SIZE：4NAME：BKIND：CONSTANTVAL：49NAME：CKIND：VARIABLELEVEL：LEVADR：DXNAME：DKIND：VARIABLELEVEL：LEVADR：DX+1NAME：EKIND：VARIABLELEVEL：LEVADR：DX+2NAME：PKIND：PROCEDURLEVEL：LEVADR：NAME：G……KIND：VARIABLE……LEVEL：LEV+1……ADR：DX……CONST

A=35，B=49；VAR

C，D，E；PROCEDURE

P；VAR

G表格管理名字類型層次/值地址空間Const（常量）無層次變量定義語句的處理<變量說明部分>::=var

<標(biāo)識符>{，<標(biāo)識符>}；if

sym=varsym

thenbegingetsym;repeatvardeclaration;(*變量說明處理*)ma

dowhilebegingetsym;變量定義語句的處理vardeclarationend;if

sym=semicolon

then

getsymelse

error(5)until

sym<>ident;end;變量定義語句的處理procedure

vardeclaration;ifthenbeginsym=identbeginenter(variable);getsymenderror(4)elseend(*vardeclaration*);過程ENTER的實(shí)現(xiàn)tx

：table表的指針procedure

enter(k:object

);begin (*

enter

object

into

table

*)tx:=tx+1;with

table[tx]do

(*

開域語句*）beginname:=id;(*表示table[tx].name:=id;*）kind:=k;(*表示table[tx].kind:=k;*)過程ENTER的實(shí)現(xiàn)case

k

ofconstant:beginif

num>amax

thenbeginerror(31);num:=0;end;val:=num;(*

table[tx].val:=num;*)end;過程ENTER的實(shí)現(xiàn)variable:beginlevel:=lev;（*表table[tx].level:=lev*）adr:=dx;（*表示table[tx].adr:=dx*）dx:=dx+1;end;procedur:level:=lev

(*表示table[tx].level:=lev;*）end(*

case

*);end(*

開域語句結(jié)束*）end(*enter*);過程體的分析從語法上要對語句逐句分析。當(dāng)語法正確時(shí)，就生成相應(yīng)語句功能的目標(biāo)代碼。當(dāng)遇到標(biāo)識符的

時(shí)就調(diào)用POSITION函數(shù)查TABLE表，看是否有過正確定義，若已有，則從表中取相應(yīng)的有關(guān)信息，供代碼的生成使用。若無定義則錯(cuò)。例：READ語句的語法語義分析處理<讀語句>∷=READ‘(’<標(biāo)識符>{，<標(biāo)識符>}‘)’；READ語句的語法語義分析處理if

sym=readsym

thenbegingetsym;if

sym<>lparen

then

error(34)elserepeatgetsym;READ語句的語法語義分析處理if

sym=ident

then

i:=position(id)else

i:=0;if

i=0

then

error(35)elsewith

table[i]

dobegingen(opr,0,16);gen(sto,lev-level,adr)end;（*表示gen(sto,lev-table[i].level,table[i].adr)

*）Lev為

層READ語句的語法語義分析處理getsymuntil

sym<>comma;if

sym<>rparen

thenbeginerror(33);while

not(sym

in

fsys)do

getsymendelse

getsymend出錯(cuò)處理正確出口Table表的下標(biāo)指針tx補(bǔ)充說明：BLOCK的參數(shù)分析第1次調(diào)用blockBLOCK（0，0，…）BLOCK（LEV+1,TX，…）(遞歸進(jìn)入分程序)txLEVtxLEV6

（15）1BLOCK...0

（6）0

BLOCK

主程序tx是BLOCK的實(shí)際值參步驟5

PL/0編譯程序代碼生成的實(shí)現(xiàn)CX：為目標(biāo)代碼code數(shù)組的下標(biāo)指針。code為一維數(shù)組，數(shù)組元素為記錄型數(shù)據(jù)。code:array[0..cxmax]of

instructioninstruction=packed

recordf:fct;l:0..levmax;a:0..amax;end;fct=（lit,opr,lod,sto,cal,int,jmp,jpc)步驟5

PL/0編譯程序代碼生成的實(shí)現(xiàn)每一個(gè)記錄就是一條目標(biāo)指令。CX使用時(shí)為整數(shù)變量，由0開始順序增加。實(shí)際上目標(biāo)代碼的順序是內(nèi)層過程的

邊，主程序的目標(biāo)代碼在最后。TX：table表的下標(biāo)指針,是以值參數(shù)形式使用的。dx:計(jì)算每個(gè)變量在運(yùn)行棧中相對本過程基地址的偏移量，放在table表中的adr域，生成目標(biāo)代碼時(shí)再放在code中的a域。步驟5

PL/0編譯程序代碼生成的實(shí)現(xiàn)PL/0語言的代碼生成是由過程GEN完成。GEN有3個(gè)參數(shù)，分別代表目標(biāo)代碼的功能碼，層差和位移量。例如READ語句的代碼生成gen(opr,0,16);gen(sto,lev-level,adr)lev：當(dāng)前處理的過程層次level：被

變量或過程所在層次步驟5

PL/0編譯程序代碼生成的實(shí)現(xiàn)procedure

gen(x:fct;

y,

z:integer);beginifcx>cxmax

then（*指針越界*）beginwrite(‘program

too

long’);close(fin);（*關(guān)閉文件*）wri

n;exitend;fct=（lit,opr,lod,sto,cal,int,jmp,jpc)步驟5

PL/0編譯程序代碼生成的實(shí)現(xiàn)with

code[cx]dobeginf:=x;（*表示code[cx].f:=x;*)l:=y;（*表示code[cx].l:=y;*)a:=z;（*表示code[cx].a:=z;*)end;cx:=cx+1end

(*gen*);cx:目標(biāo)代碼的指針步驟5

PL/0編譯程序代碼生成的實(shí)現(xiàn)對分程序的定義（見

292頁）procedureblock(lev,tx:integer;fsys:symset);var

dx:integer; (*data

allocationindex*)tx0:integer; (*initial

table

index*)cx0:integer; (*initial

code

index*)（

tx0，cx0是tx，cx的初值）步驟5

PL/0編譯程序代碼生成的實(shí)現(xiàn)PL/0編譯程序的目標(biāo)代碼生成實(shí)現(xiàn)的主要過程為：在block

處生成一條(jmp,0,0)指令，作為過程體

指令，該指令的第3區(qū)域的‘0’需分析到過程體

時(shí)才返填。目標(biāo)代碼生成時(shí)所用到的變量地址和層差

等信息是由名字表table提供的，而名字表的信息是在說明時(shí)填寫的。步驟5

PL/0編譯程序代碼生成的實(shí)現(xiàn)300頁）對分程序體人口的處理（見程序文本block

的過程體begin

(*block*)dx:=3;tx0:=tx;

（保留當(dāng)前table表指針值即過程名的位置）table[tx].adr:=cx;（保留當(dāng)前code指針值到過程名的adr域）gen(jmp,0,0);（生成轉(zhuǎn)向過程體

的指令，該指令的地址為cx

已保留在過程名的adr域，等生成

過程體返填到cx填到過程名的指令時(shí)，再由table[tx].adr中取出cx將過程體中，即（

jmp,0,0）的第3區(qū)域。同時(shí)將過程體的table[tx].adr中)…（注意dx，tx，cx的作用）NAME：ANAME：BNAME：CNAME：DNAME：ENAME：PKIND：CONSTANTKIND：CONSTANTKIND：VARIABLEKIND：VARIABLEKIND：VARIABLEKIND：PROCEDURVAL：35VAL：49LEVEL：LEVLEVEL：LEVLEVEL：LEVLEVEL：LEVADR：DXADR：DX+1ADR：DX+2ADR：1SIZE：4NAME：G……KIND：VARIABLE……LEVEL：LEV+1……ADR：DX……；CONST

A=35，B=49VAR

C，D，E；PROCEDURE

P；VAR

Gtable表格管理名字類型層次/值地址空間(0)

jmp

0

0CX

(1)

jmp

0

0..記錄過程在code的入口到table中的adr域NAME：AKIND：CONSTANTVAL：35NAME：BKIND：CONSTANTVAL：49NAME：CKIND：VARIABLELEVEL：LEVADR：DXNAME：DKIND：VARIABLELEVEL：LEVADR：DX+1NAME：EKIND：VARIABLELEVEL：LEVADR：DX+2NAME：PKIND：PROCEDURLEVEL：LEVADR：1

cx

SIZE：4NAME：GKIND：VARIABLELEVEL：LEV+1ADR：DX……………………CONST

A=35，B=49；VAR

C，D，E；PROCEDURE

P；VAR

Gtable表格管理名字類型層次/值地址空間(0)

jmp

0

0(1

)

jmp

0

0.

.

.(

cx

)

int

0

4過程的 地址填寫在code和table中步驟5

PL/0編譯程序代碼生成的實(shí)現(xiàn)過程體

時(shí)的處理code[table[tx0].adr].a:=cx;（過程

地址填寫在code中）with

table[tx0]

dobeginadr:=cx;

（過程的

填

寫在table中）size:=dx;（過程占的空間填寫在table中）end;cxo:=cx;gen(int,0,dx);（生成過程指令）保留過程在code中的地址，打印目標(biāo)代碼用步驟6

PL/0編譯程序語法錯(cuò)誤處理的實(shí)現(xiàn)對語法錯(cuò)誤的兩種處理方法：對于易于校正的錯(cuò)誤，如丟了逗號，分號等，出錯(cuò)位置，加以校正，繼續(xù)進(jìn)行分析。對于難于校正的錯(cuò)誤，給出錯(cuò)誤的位置與性質(zhì)，跳過后面的一些單詞，直到下一個(gè)可以進(jìn)行正常語法分析的語法單位。為了實(shí)現(xiàn)第(2)種處理方法，現(xiàn)引入文法的開始符號集合與后繼符號集合。開始符號集合與后繼符號集合非終結(jié)符名開始符號集合后繼符號集合分程序constidentwhilevar

procedureif

call

beginread

write.

;語句identwhileif

call

beginread

write.

;

end條件odd

+ident-

(numberThen

do表達(dá)式+

-

(identnumber.

;

)ropend

then

do項(xiàng)identnumber

(.

;

)rop+

-end

then

do因子identnumber

(.

;

)rop

+

-*

/end

then

doconstidentnumber=,;varident,;;procedureident;分程序語句分程序從語法圖看開始符號集合與后繼符號集合分程序程序.從語法圖看開始符號集合與后繼符號集合項(xiàng)表達(dá)式+-項(xiàng)+-項(xiàng)因子*因子/從語法圖看開始符號集合與后繼符號集合因子identnumber(表達(dá)式)步驟6

PL/0編譯程序語法錯(cuò)誤處理的實(shí)現(xiàn)╳╳╳╳╳╳╳╳╳╳╳╳╳╳╳╳╳╳╳TEST

TEST在進(jìn)入某個(gè)語法單位時(shí)，調(diào)用TEST,檢查當(dāng)前符號是否屬于該語法單位的開始符號集合。若不屬于，則濾去開始符號和后繼符號集合外的所有符號。在語法單位分析結(jié)束時(shí)，調(diào)用TEST,檢查當(dāng)前符號是否屬于調(diào)用該語法單位時(shí)應(yīng)有的后繼符號集合。若不屬于，則濾去后繼符號和開始符號集合外的所有符號。TESTSYM在S1中?打印出錯(cuò)

nS1:=S1+S2SYM在S1中?GETSYM返回YYNNTEST測試過程流程圖test(s1,s2:symset;n:integer);步驟6

PL/0編譯程序語法錯(cuò)誤處理的實(shí)現(xiàn)開始符號集合的定義（見

289頁）symset=set

of

symbol;declbegsys,

statbegsys,

facbegsys:symset;開始符號集合（見

305頁）declbegsys:=[constsym,varsym,procsym];statbegsys:=[beginsym,callsym,ifsym,whilesym,readsym,writesym];facbegsys:=[ident,number,lparen];步驟6

PL/0編譯程序語法錯(cuò)誤處理的實(shí)現(xiàn)后繼符號集合fsys作為參數(shù)是可傳遞的：

procedure

test(s1,s2:symset;n:integer);procedure

block(lev,tx:integer;

fsys:symset);procedure

statement(fsys:symset);procedure

expression

(fsys:symset);procedure

term

(fsys:symset);procedure

factor

(fsys:symset);procedure

condition(fsys:symset);因子的處理過程294頁）例：因子的處理過程片段（見procedure

factor(fsys:symset);var

i:integer;begin出口：：

test(facbegsys,fsys,24);while

sym

in

facbegsys

dobeginif...test(fsys,facbegsys,23);endend;因子的處理過程whiley處理identnumber,lparentestntestSym為出口符號Sym為入口符號步驟6

PL/0編譯程序語法錯(cuò)誤處理的實(shí)現(xiàn)增加后跟符與調(diào)用位置有關(guān)例：調(diào)用expression(fsys);

（見

298頁）write語句的語法write(<exp>{,<exp>});處理在（

）內(nèi)調(diào)用expression時(shí)應(yīng)expression([

ma]+fsys);factor的語法：factor∷=...|‘(’

exp

’)

’在處理（

）內(nèi)調(diào)用expression時(shí)應(yīng)expression([rparen]+fsys);步驟7類pcode代碼解釋器的實(shí)現(xiàn)類pcode解釋器的結(jié)構(gòu)解釋執(zhí)行的流程圖目標(biāo)代碼解釋執(zhí)行時(shí)數(shù)據(jù)棧的布局（運(yùn)行棧的

分配）類pcode解釋器的結(jié)構(gòu)目標(biāo)代碼存放在數(shù)組CODE中。解釋程序定義一個(gè)一維整型數(shù)組S作為運(yùn)行棧棧頂寄存器（指針）t，基址寄存器（指針）b，程序地址寄存器p，指令寄存器i當(dāng)一個(gè)過程被調(diào)用時(shí)，就在運(yùn)行棧（數(shù)據(jù)棧）分配相應(yīng)的空間，過程執(zhí)行結(jié)束就

空間。變量在code[cx]、table[tx]和s[t]之間的信息聯(lián)系下標(biāo)指針cx，tx和變量dx的作用code[cx]cxtable[tx]tx(0)

jmp

0

0(i

)

int

0

7.(n)sto

0

dx(cx

)

.(0) name

…adr...(i

)

a

(dx)...(

tx)s[t