第七章_語(yǔ)義分析和中間代碼產(chǎn)生.ppt

1、第七章 語(yǔ)義分析和中間代碼產(chǎn)生,內(nèi)容,中間語(yǔ)言 說(shuō)明語(yǔ)句 賦值語(yǔ)句的翻譯 布爾表達(dá)式的翻譯 控制語(yǔ)句的翻譯 過(guò)程調(diào)用的處理 類型檢查,語(yǔ)義分析與中間代碼產(chǎn)生,詞法分析和語(yǔ)法分析之后，編譯程序的工作是進(jìn)行靜態(tài)語(yǔ)義檢查和翻譯 靜態(tài)語(yǔ)義檢查包括 類型檢查 控制流檢查 一致性檢查 相關(guān)名字檢查 名字的作用域分析,語(yǔ)法分 析器,中間代碼 產(chǎn)生器,靜態(tài)檢 查器,中間代碼,優(yōu)化器,語(yǔ)義分析與中間代碼產(chǎn)生,翻譯為中間語(yǔ)言(復(fù)雜性界于源語(yǔ)言和目標(biāo)語(yǔ)言之間)的好處： 便于進(jìn)行與機(jī)器無(wú)關(guān)的代碼優(yōu)化工作 易于移植 使編譯程序的結(jié)構(gòu)在邏輯上更為簡(jiǎn)單明確,源語(yǔ)言 程序,目標(biāo)語(yǔ) 言程序,中間語(yǔ) 言程序,7.1 中間語(yǔ)言,常

2、用的中間語(yǔ)言： 后綴式（逆波蘭表示） 三地址代碼 三元式 四元式 間接三元式 DAG圖表示,7.1.1 后綴式,后綴式表示法：Lukasiewicz發(fā)明的一種表示表達(dá)式的方法，又稱逆波蘭表示法。 后綴式表示法把運(yùn)算量（操作數(shù)）寫(xiě)在前面，把算符寫(xiě)在后面（后綴）。如a+b寫(xiě)成ab+ 一個(gè)表達(dá)式E的后綴形式可以如下定義： 1. 如果E是一個(gè)變量或常量，則E的后綴式是E自身。 2. 如果E是E1 op E2形式的表達(dá)式，其中op是任何二元操作符，則E的后綴式為E1 E2 op，其中E1 和E2 分別為E1 和E2的后綴式。 3. 如果E是(E1)形式的表達(dá)式，則E1 的后綴式就是E的后綴式。,7.1.

3、1 后綴式,abc+*等價(jià)a*(b+C) 逆波蘭表示法不用括號(hào)。只要知道每個(gè)算符的目數(shù)，對(duì)于后綴式，不論從哪一端進(jìn)行掃描，都能對(duì)它進(jìn)行唯一分解。 后綴式的計(jì)算 用一個(gè)棧實(shí)現(xiàn)。 一般的計(jì)算過(guò)程是：自左至右掃描后綴式，每碰到運(yùn)算量就把它推進(jìn)棧。每碰到k目運(yùn)算符就把它作用于棧頂?shù)膋個(gè)項(xiàng)，并用運(yùn)算結(jié)果代替這k個(gè)項(xiàng)。,把表達(dá)式翻譯成后綴式的語(yǔ)義規(guī)則描述,產(chǎn)生式 EE1op E2 E (E1) Eid,語(yǔ)義規(guī)則 E.code:= E1.code | E2.code |op E.code:= E1.code E.code:=id,E.code表示E后綴形式 op表示任意二元操作符 “|”表示后綴形式的連接。

4、,7.1.1 后綴式,數(shù)組POST存放后綴式：k為下標(biāo)，初值為1 上述語(yǔ)義動(dòng)作可實(shí)現(xiàn)為： 產(chǎn)生式程序段 EE1op E2POSTk:=op;k:=k+1 E (E1) EiPOSTk:=i;k:=k+1 例：輸入串a(chǎn)+b+c的分析和翻譯 POST： 1 2 3 4 5,7.1.1 后綴式,后綴式的推廣： 對(duì)于條件算術(shù)表達(dá)式 if e then X else Y 可表示為eXY￥，其中￥表示三目運(yùn)算if-then-else,7.1.2 圖表示法,圖表示法 DAG 抽象語(yǔ)法樹(shù) 無(wú)循環(huán)有向圖(Directed Acyclic Graph，簡(jiǎn)稱DAG) 對(duì)表達(dá)式中的每個(gè)子表達(dá)式，DAG中都有一個(gè)結(jié)點(diǎn)

5、一個(gè)內(nèi)部結(jié)點(diǎn)代表一個(gè)操作符，它的孩子代表操作數(shù) 在一個(gè)DAG中代表公共子表達(dá)式的結(jié)點(diǎn)具有多個(gè)父結(jié)點(diǎn),a:=b*(-c)+b*(-c)的圖表示法,7.1.2 圖表示法,產(chǎn)生賦值語(yǔ)句抽象語(yǔ)法樹(shù)的屬性文法,7.1.3 三地址代碼,三地址代碼： 一般形式：x := y op z 三地址代碼包含三個(gè)地址，兩個(gè)用來(lái)表示操作數(shù)，一個(gè)用來(lái)存放結(jié)果。 表達(dá)式x + y z翻譯成的三地址語(yǔ)句序列是 t1 := y z t2 := x + t1,7.1.3 三地址代碼,三地址代碼是語(yǔ)法樹(shù)或DAG的一種線性表示 a := (b + cd ) + cd 語(yǔ)法樹(shù)的代碼DAG的代碼 t1 := bt1 := b t2 :=

6、 c dt2 := c d t3 := t1 + t2t3 := t1 + t2 t4 := c dt4 := t3 + t2 t5 := t3 + t4 a := t4 a := t5,7.1.3 三地址代碼,三地址語(yǔ)句的種類 賦值語(yǔ)句x := y op z，x := op y，x := y 無(wú)條件轉(zhuǎn)移goto L 條件轉(zhuǎn)移if x relop y goto L 過(guò)程調(diào)用param x 和call p , n 過(guò)程返回return y 索引賦值x := yi和 xi := y 地址和指針賦值x := E.code:=E1.code | E2.code | gen(E.place := E1.

7、place + E2.place) EE1*E2E.place:=newtemp; E.code:=E1.code | E2.code | gen(E.place := E1.place * E2.place) E-E1E.place:=newtemp; E.code:=E1.code | gen(E.place := uminus E1.place) E (E1)E.place:=E1.place; E.code:=E1.code Eid E.place:=id.place; E.code= ,三地址語(yǔ)句,四元式 一個(gè)帶有四個(gè)域的記錄結(jié)構(gòu)，這四個(gè)域分別稱為op, arg1, arg2及res

8、ult。如： a:=b*-c+b*-c 的四元式： oparg1arg2result (0)uminuscT1 (1)*bT1T2 (2)uminuscT3 (3)*bT3T4 (4)+T2T4T5 (5):=T5a,三地址語(yǔ)句,三元式 通過(guò)計(jì)算臨時(shí)變量值的語(yǔ)句的位置來(lái)引用這個(gè)臨時(shí)變量。如： a:=b*-c+b*-c 的三元式： 三個(gè)域：op、arg1和arg2 oparg1arg2 (0)uminusc (1)*b(0) (2)uminusc (3)*b(2) (4)+(1)(3) (5)assigna(4),三地址語(yǔ)句,三元式 三元式中的多目運(yùn)算符： xi:=y op arg1 arg2

9、(0) = x i (1) assign (0) y x:=yi op arg1 arg2 (0) = y i (1) assign x (0),三地址語(yǔ)句,間接三元式 為了便于優(yōu)化，用 三元式表+間接碼表 表示中間代碼 間接碼表:一張指示器表，按運(yùn)算的先后次序列出有關(guān)三元式在三元式表中的位置。 優(yōu)點(diǎn): 方便優(yōu)化，節(jié)省空間,例如，語(yǔ)句 X:=(A+B)*C; Y:=D(A+B) 的間接三元式表示如下表所示。,7.2 說(shuō)明語(yǔ)句,為局部名字建立符號(hào)表?xiàng)l目 為它分配存儲(chǔ)單元 符號(hào)表中包含名字的類型和分配給它的存儲(chǔ)單元的相對(duì)地址等信息,7.2.1 過(guò)程中的聲明,計(jì)算被說(shuō)明名字的類型和相對(duì)地址 P D

10、offset := 0 D D ; D D id : T enter ( , T.type, offset); offset := offset + T.width T integer T.type := integer; T.width := 4 T real T.type := real; T.width := 8 T array num of T1 T.type := array (num.val, T1.type); T.width := num.val T1.width T T1 T.type := pointer (T1.type); T.width := 4,7.2

11、.2 保留作用域信息,所討論語(yǔ)言的文法（允許嵌套過(guò)程） P D D D ; D | id : T | proc id ; D ; S 語(yǔ)義動(dòng)作用到的函數(shù) mktable(previous) enter(table, name, type, offset) addwidth(table, width) enterproc(table, name, newtable),P M D addwidth (top (tblptr), top (offset) ); pop(tblptr); pop (offset) M t := mktable (nil); push(t, tblprt); push

12、(0, offset) D D1 ; D2 D proc id ; N D1; S t := top(tblptr); addwidth(t, top(offset) ); pop(tblptr); pop(offset); enterproc(top(tblptr), , t) Did : T enter(top(tblptr), , T.type, top(offset); top(offset) := top(offset) + T.width N t := mktable(top(tblptr) ); push(t, tblptr); push(0, off

13、set) ,7.2.2 保留作用域信息,7.2.3 記錄的域名,T record D end產(chǎn)生記錄類型 為記錄中域名建立一張符號(hào)表 T record L D end T.type := record (top(tblptr) ); T.width := top(offset); pop(tblptr); pop(offset) L t := mktable (nil); push(t, tblprt); push(0, offset) ,7.3 賦值語(yǔ)句的翻譯,注意：E.place表示存放E值的名字 newtemp：每次調(diào)用時(shí)，返回一個(gè)不同臨時(shí)變量 emit 生成三地址語(yǔ)句并發(fā)送到輸出文件中

14、,7.3.1 簡(jiǎn)單算術(shù)表達(dá)式及賦值語(yǔ)句,產(chǎn)生賦值語(yǔ)句三地址代碼的翻譯模式 Sid:=E p:=lookup(); if pnil then emit(p := E.place) else error EE1+E2 E.place:=newtemp; emit(E.place := E1.place + E2.place) EE1*E2 E.place:=newtemp; emit(E.place := E 1.place * E 2.place),7.3.1 簡(jiǎn)單算術(shù)表達(dá)式及賦值語(yǔ)句,產(chǎn)生賦值語(yǔ)句三地址代碼的翻譯模式 E-E1 E.place:=newtemp; emit(E.p

15、lace:= uminusE 1.place) E(E1) E.place:=E1.place Eid p:=lookup(); if pnil then E.place:=p else error ,7.3.2 數(shù)組元素的引用,數(shù)組元素地址的計(jì)算： 一維數(shù)組A的第i個(gè)元素的地址計(jì)算 base + ( i low ) w 重寫(xiě)成 i w + (base low w) 減少了運(yùn)行時(shí)的計(jì)算,7.3.2 數(shù)組元素的引用,數(shù)組元素地址的計(jì)算： 設(shè)A為n維數(shù)組，每個(gè)元素寬度為w， lowi 為第i維 的下界，ni 是為第i維 可取值的個(gè)數(shù), base為A的第一個(gè)元素相對(duì)地址 元素Ai1,i

16、2,ik相對(duì)地址公式 (i1 n2+i2)n3+i3)nk+ik)w + base-(low1 n2+low2)n3+low3)nk+lowk)w C= base-(low1 n2+low2)n3+low3)nk+lowk)w,7.3.2 數(shù)組元素的引用,數(shù)組元素地址計(jì)算的翻譯方案 下標(biāo)變量訪問(wèn)的產(chǎn)生式 L id Elist | id Elist Elist, E | E 為了便于語(yǔ)義處理，改成 L Elist | id Elist Elist, E | id E,7.3.2 數(shù)組元素的引用,所有產(chǎn)生式： S L := E E E + E E (E ) E L L Elist L id Eli

17、st Elist, E Elist id E,7.3.2 數(shù)組元素的引用,L id L.place := id.place; L.offset := null Elist id E Elist.place := E.place; Elist.ndim := 1; Elist.array := id.place Elist Elist1, E t := newtemp; m := Elist1.ndim + 1; emit (t, :=, Elist1.place, , limit(Elist1.array, m) ); emit (t, :=, t, +, E.place); Elist.ar

18、ray := Elist1.array; Elist.place := t; Elist.ndim := m L Elist L.place := newtemp; emit (L.place, :=, base(Elist.array), , invariant (Elist.array) ); L.offset := newtemp; emit (L.offset, :=, Elist.place, , w) ,7.3.2 數(shù)組元素的引用,E L if L.offset = null then / L是簡(jiǎn)單變量 / E.place := L.place else begin E.place

19、 := newtemp; emit (E.place, :=, L.place, , L.offset, ) end E E1 + E2 E.place := newtemp; emit (E.place, :=, E1.place , +, E2.place) E (E1 )E.place := E1.place S L := Eif L.offset = null then / L是簡(jiǎn)單變量 / emit (L.place, := , E.place) else emit (L.place , , L.offset, , :=, E.place) ,7.3.2 數(shù)組元素的引用,t1 :=

20、y 20 t1 := t1 + z,t2 :=A 84 t3 := 4 t1,t4 := t2 t3 ,x := t4,T1：y*20 T1：T1+z T2：A-84 T3：4 * T1 T4：T2T3 X：T4,7.3.2 數(shù)組元素的引用,類型轉(zhuǎn)換 x := y + i j （x和y的類型是real，i和j的類型是integer） 中間代碼 t1 := i int j t2 := inttoreal t1 t3 := y real+ t2 x := t3,7.3.2 數(shù)組元素的引用,關(guān)于E E1 + E2語(yǔ)義動(dòng)作如下： E.place := newtemp if E1.type = inte

21、ger and E2.type = integer then begin emit (E.place, :=, E1.place, int+, E2.place); E.type = integer end else if E1.type = integer and E2.type = real then begin u := newtemp; emit (u, :=, inttoreal, E1.place); emit (E.place, :=, u, real+, E2.place); E.type := real end . . .,7.3.3 記錄中域的引用,符號(hào)表表項(xiàng)之中保存記錄中

22、的域的類型和相對(duì)地址信息,7.4 布爾表達(dá)式的翻譯,布爾表達(dá)式有兩個(gè)基本目的 計(jì)算邏輯值 在控制流語(yǔ)句中用作條件表達(dá)式 產(chǎn)生布爾表達(dá)式的文法: EE or E | E and E | not E | (E) | id relop id | id,7.4 布爾表達(dá)式的翻譯,計(jì)算布爾表達(dá)式通常采用兩種方法: 1. 如同計(jì)算算術(shù)表達(dá)式一樣,一步步算 1 or (not 0 and 0) or 0 =1 or (1 and 0) or 0 =1 or 0 or 0 =1 or 0 =1 2. 采用某種優(yōu)化措施 把A or B解釋成 if A then true else B 把A and B解釋成 i

23、f A then B else false 把not A解釋成 if A then false else true,7.4 布爾表達(dá)式的翻譯,兩種不同的翻譯方法: 第一種翻譯法： A or B and C=D翻譯成 (1) (=, C, D, T1) (2) (and, B, T1, T2) (3) (or, A, T2, T3) 第二種翻譯法適合于作為條件表達(dá)式的布爾表達(dá)式使用.,7.4.1 數(shù)值表示法,a or b and not c 翻譯成 T1:=not c T2:=b and T1 T3:=a or T1 ab的關(guān)系表達(dá)式可等價(jià)地寫(xiě)成 if ab then 1 else 0 ，翻譯成

24、 100:if ab goto 103 101:T:=0 102:goto 104 103:T:=1 104:,7.4.1 數(shù)值表示法,關(guān)于布爾表達(dá)式的數(shù)值表示法的翻譯模式 過(guò)程emit將三地址代碼送到輸出文件中 nextstat給出輸出序列中下一條三地址語(yǔ)句的地址索引 每產(chǎn)生一條三地址語(yǔ)句后，過(guò)程emit便把nextstat加1,7.4.1 數(shù)值表示法,關(guān)于布爾表達(dá)式的數(shù)值表示法的翻譯模式 EE1 or E2 E.place:=newtemp; emit(E.place := E 1.place or E2.place) EE1 and E2 E.place:=newtemp; emit(E

25、.place := E 1.place and E2.place) Enot E1 E.place:=newtemp; emit(E.place := not E 1.place) E(E1) E.place:=E1.place,7.4.1 數(shù)值表示法,關(guān)于布爾表達(dá)式的數(shù)值表示法的翻譯模式 Eid1 relop id2 E.place:=newtemp; emit(if id1.place relop.op id2.place goto nextstat+3); emit(E.place := 0); emit(goto nextstat+2); emit(E.place:= 1) Eid E

26、.place:=id.place ,布爾表達(dá)式ab or cd and ef翻譯成如下的一串三地址代碼,100:if ab goto 103 101:T1:=0 102:goto 104 103:T1:=1 104:if cd goto 107 105:T2:=0 106:goto 108,107: T2:=1 108: if ef goto 111 109: T3:=0 110: goto 112 111: T3:=1 112: T4:=T2 and T3 113: T5:=T1 or T4,條件語(yǔ)句 if E then S1 else S2 賦予 E 兩種出口:一真一假,7.4.2 作為條

27、件控制的布爾式翻譯,E.code,S1.code,S2.code,To E.true,To E.false,goto S.next,S.next,E.true:,E.false:,例：把語(yǔ)句: if ac or bc goto L2 “真”出口 goto L1 L1:if bd goto L2 “真”出口 goto L3 “假”出口 L2:(關(guān)于S1的三地址代碼序列) goto Lnext L3:(關(guān)于S2的三地址代碼序列) Lnext:,7.4.2 作為條件控制的布爾式翻譯,每次調(diào)用函數(shù)newlabel后都返回一個(gè)新的符號(hào)標(biāo)號(hào) 對(duì)于一個(gè)布爾表達(dá)式E，引用兩個(gè)標(biāo)號(hào) E.true是E為真時(shí)控制流

28、轉(zhuǎn)向的標(biāo)號(hào) E.false是E為假時(shí)控制流轉(zhuǎn)向的標(biāo)號(hào),產(chǎn)生布爾表達(dá)式三地址代碼的語(yǔ)義規(guī)則,產(chǎn)生式語(yǔ)義規(guī)則 EE1 or E2E1.true:=E.true; E1.false:=newlabel; E2.true:=E.true; E2.false:=E.false; E.code:=E1.code | gen(E1.false :) | E2.code,產(chǎn)生布爾表達(dá)式三地址代碼的語(yǔ)義規(guī)則,產(chǎn)生式語(yǔ)義規(guī)則 EE1 and E2E1.true:=newlabel; E1.false:=E.false; E2.true:=E.true; E2.false:=E.fasle; E.code:=E1.

29、code | gen(E1.true :) | E2.code Enot E1 E1.true:=E.false; E1.false:=E.true; E.code:=E1.code,產(chǎn)生布爾表達(dá)式三地址代碼的語(yǔ)義規(guī)則,產(chǎn)生式 語(yǔ)義規(guī)則 E (E1) E1.true:=E.true; E1.false:=E.false; E.code:=E1.code Eid1 relop id2E.code:=gen(if id1.place relop.op id2.place goto E.true) | gen(goto E.false) Etrue E.code:=gen(goto E.true)

30、Efalse E.code:=gen(goto E.false),7.4.2 作為條件控制的布爾式翻譯,考慮如下表達(dá)式： ab or cd and ef假定整個(gè)表達(dá)式的真假出口已分別置為L(zhǎng)true和Lfalse，則按定義將生成如下的代碼： if ab goto Ltrue goto L1 L1:if cd goto L2 goto Lfalse L2:if ef goto Ltrue goto Lfalse,7.4.2 作為條件控制的布爾式翻譯,布爾表達(dá)式的翻譯: 兩遍掃描 為給定的輸入串構(gòu)造一棵語(yǔ)法樹(shù)； 對(duì)語(yǔ)法樹(shù)進(jìn)行深度優(yōu)先遍歷，進(jìn)行語(yǔ)義規(guī)則中規(guī)定的翻譯。 一遍掃描,一遍掃描實(shí)現(xiàn)布爾表達(dá)式的

31、翻譯,采用四元式形式 把四元式存入一個(gè)數(shù)組中，數(shù)組下標(biāo)就代表四元式的標(biāo)號(hào) 約定: 四元式(jnz, a, -, p) 表示 if a goto p 四元式(jrop, x, y, p) 表示 if x rop y goto p 四元式(j, -, -, p) 表示 goto p,有時(shí),四元式轉(zhuǎn)移地址無(wú)法立即知道,我們只好把這個(gè)未完成的四元式地址作為E的語(yǔ)義值保存,待機(jī)回填。 為非終結(jié)符E賦予兩個(gè)綜合屬性E.truelist和E.falselist。它們分別記錄布爾表達(dá)式E所應(yīng)的四元式中需回填“真”、“假”出口的四元式的標(biāo)號(hào)所構(gòu)成的鏈表,一遍掃描實(shí)現(xiàn)布爾表達(dá)式的翻譯,例如:假定E的四元式中需要回

32、填真出口的p，q，r三個(gè)四元式，則E.truelist為下列鏈: (p) (x， x，x，0) (q) (x，x，x，p) (r) (x，x，x，q),鏈尾,E. truelist =r,為了處理E.truelist和E.falselist ，引入下列語(yǔ)義變量和過(guò)程: 變量nextquad，它指向下一條將要產(chǎn)生但尚未形成的四元式的地址(標(biāo)號(hào))。nextquad的初值為1，每當(dāng)執(zhí)行一次emit之后，nextquad將自動(dòng)增1。 函數(shù)makelist(i)，它將創(chuàng)建一個(gè)僅含i的新鏈表，其中i是四元式數(shù)組的一個(gè)下標(biāo)(標(biāo)號(hào))；函數(shù)返回指向這個(gè)鏈的指針。 函數(shù)merge(p1,p2)，把以p1和p2為鏈

33、首的兩條鏈合并為一，作為函數(shù)值，回送合并后的鏈?zhǔn)住?過(guò)程backpatch(p, t)，其功能是完成“回填”，把p所鏈接的每個(gè)四元式的第四區(qū)段都填為t。,布爾表達(dá)式的文法,(1) EE1 or M E2 (2) | E1 and M E2 (3)| not E1 (4)| (E1) (5)| id1 relop id2 (6)| id (7)M,布爾表達(dá)式的翻譯模式,(1) EE1 or M E2 backpatch(E1.falselist, M.quad); E.truelist:=merge(E1.truelist, E2.truelist); E.falselist:=E2.false

34、list (2) EE1 and M E2 backpatch(E1.truelist, M.quad); E.truelist:=E2.truelist; E.falselist:=merge(E1.falselist,E2.falselist) ,布爾表達(dá)式的翻譯模式,(3) Enot E1 E.truelist:=E1.falselist; E.falselist:=E1.truelist (4) E(E1) E.truelist:=E1.truelist; E.falselist:=E1. falselist,布爾表達(dá)式的翻譯模式,(5) Eid1 relop id2 E.trueli

35、st:=makelist(nextquad); E.falselist:=makelist(nextquad+1); emit(j relop.op , id 1.place , id 2.place,0); emit(j, , , 0) (6) Eid E.truelist:=makelist(nextquad); E.falselist:=makelist(nextquad+1); emit(jnz , id .place , ,0)； emit( j, -, -, 0) ,布爾表達(dá)式的翻譯模式,(7) M M.quad:=nextquad 作為整個(gè)布爾表達(dá)式的真假出口(轉(zhuǎn)移目標(biāo))仍待回填

36、.,ab or cd and ef,100(j, a, b, 0) 101(j, -, -, 102) 102(j, c, d, 104) 103(j, -, -, 0) 104(j, e, f, 100) truelist 105(j, -, -, 103) falselist,7.5 控制語(yǔ)句的翻譯,考慮下列產(chǎn)生式所定義的語(yǔ)句 S if E then S1 | if E then S1 else S2 | while E do S1 其中E為布爾表達(dá)式。,if-then語(yǔ)句的屬性文法 產(chǎn)生式語(yǔ)義規(guī)則 Sif E then S1 E.true:=newlabel; E.flase:=S.ne

37、xt; S1.next:=S.next S.code:=E.code | gen(E.true :) | S1.code,7.5.1 控制流語(yǔ)句,7.5.1 控制流語(yǔ)句,if-then-else語(yǔ)句的屬性文法 產(chǎn)生式 語(yǔ)義規(guī)則 Sif E then S1 else S2 E.true:=newlabel; E.false:=newlabel; S1.next:=S.next S2.next:=S.next; S.code:=E.code | gen(E.true :) | S1.code | gen(goto S.next) | gen(E.false :) | S2.code,7.5.1 控

38、制流語(yǔ)句,while-do語(yǔ)句的屬性文法 產(chǎn)生式語(yǔ)義規(guī)則 Swhile E do S1S.begin:=newlabel; E.true:=newlabel; E.false:=S.next; S1.next:=S.begin; S.code:=gen(S.begin :) | E.code | gen(E.true :) | S1.code | gen(goto S.begin),考慮如下語(yǔ)句 :while ab doif cd thenx:=y+zelse x:=y-z,生成下列代碼： L1:if ab goto L2 goto Lnext L2:if cd goto L3 goto L4

39、 L3:T1:=y+z x:=T1 goto L1 L4:T2:=y-z x:=T2 goto L1 Lnext:,7.5.1 控制流語(yǔ)句,一遍掃描翻譯控制流語(yǔ)句 考慮下面文法對(duì)應(yīng)的翻譯模式: (1)Sif E then S (2) | if E then S else S (3) | while E do S (4) | begin L end (5) | A (6)LL;S (7) | S S表示語(yǔ)句;L表示語(yǔ)句表; A為賦值語(yǔ)句;E為一個(gè)布爾表達(dá)式。,if 語(yǔ)句的翻譯,相關(guān)產(chǎn)生式 S if E then S1 | if E then S1 else S2 改寫(xiě)后產(chǎn)生式 S if E th

40、en M S1 S if E then M1 S1 N else M2 S2 M N,if 語(yǔ)句的翻譯,翻譯模式: 1. Sif E then M S1 backpatch(E.truelist, M.quad); S.nextlist:=merge(E.falselist, S1.nextlist) 2. Sif E then M1 S1 N else M2 S2 backpatch(E.truelist, M1.quad); backpatch(E.falselist, M2.quad); S.nextlist:=merge(S1.nextlist, N.nextlist,S2.nextl

41、ist) 3. M M.quad:=nextquad 4. N N.nextlist:=makelist(nextquad); emit(j,) ,while 語(yǔ)句的翻譯,相關(guān)產(chǎn)生式 S while E do S1 改寫(xiě)后產(chǎn)生式 Swhile M1 E do M2 S1 M,while 語(yǔ)句的翻譯,翻譯模式: 1. Swhile M1 E do M2 S1 backpatch(S1.nextlist, M1.quad); backpatch(E.truelist, M2.quad); S.nextlist:=E.falselist emit(j, M1.quad) 2. M M.quad:=n

42、extquad ,其它語(yǔ)句的翻譯,產(chǎn)生式 LL1;S 改寫(xiě)為： LL1; M S M 翻譯模式: 1. LL1; M S backpatch(L1.nextlist, M.quad); L.nextlist:=S.nextlist 2. M M.quad:=nextquad ,其它語(yǔ)句的翻譯,1. Sbegin L end S.nextlist:=L.nextlist 2. SA S.nextlist:=makelist( ) 3. LS L.nextlist:=S.nextlist ,例:按照上述的語(yǔ)義動(dòng)作，及關(guān)于賦值句和布爾表達(dá)式的翻譯法，語(yǔ)句 while(ab) do if (cd) t

43、hen x:=yz；將被翻譯成如下的一串四元式：,100(j, a, b, 102) 101(j, -, -, 107) 102(j, c, d, 104) 103(j, -, -, 100) 104(+, y, z, T) 105(:=, T, -, x) 106 (j, -, -, 100) 107,7.5.2 標(biāo)號(hào)與goto語(yǔ)句,產(chǎn)生式Sgoto L的語(yǔ)義動(dòng)作: 查找符號(hào)表； IF L在符號(hào)表中且定義否欄為已 THEN GEN(J，-，-，P) ELSE IF L不在符號(hào)表中 THEN BEGIN 把L填入表中； 置定義否為未，地址欄為NXQ； GEN(J，-，-，0) END ELSE

44、 BEGIN Q:=L的地址欄中的編號(hào)； 置地址欄編號(hào)為NXQ； GEN(J，-，-，Q) END ,7.5.3 CASE語(yǔ)句的翻譯,語(yǔ)句結(jié)構(gòu) case E of C1:S1; C2:S2; Cn-1:Sn-1; otherwise:Sn end,翻譯法(一): T:=E L1:if TC1 goto L2 S1的代碼 goto next L2:if TC2 goto L3 S2的代碼 goto next L3: Ln-1:if TCn-1 goto Ln Sn-1的代碼 goto next Ln:Sn的代碼 next:,改進(jìn):,翻譯法(二): 計(jì)算E并放入T中 goto test L1:關(guān)于

45、S1的中間碼 goto next Ln-1:關(guān)于Sn-1的中間碼 goto next Ln:關(guān)于Sn的中間碼 goto next test:if T=C1 goto L1 if T=C2 goto L2 if T=Cn-1 goto Ln-1 goto Ln next:,(case, C1, P1) (case, C2, P2) (case, Cn-1, Pn-1) (case, T, Pn) (label, NEXT, -, -),Pi是LI在 符號(hào)表中 的位置,7.6 過(guò)程調(diào)用的處理,過(guò)程調(diào)用主要對(duì)應(yīng)兩件事: 傳遞參數(shù) 轉(zhuǎn)移到子程序 傳地址:把實(shí)在參數(shù)的地址傳遞給相應(yīng)的形式參數(shù) 調(diào)用段預(yù)先把實(shí)在參數(shù)的地址傳遞到被調(diào)用段可以拿到的地方； 程序控制轉(zhuǎn)入被調(diào)用段之后，被調(diào)用段首先把實(shí)在參數(shù)的地址抄進(jìn)自己相應(yīng)的形式單元中； 過(guò)程體對(duì)形式參數(shù)的引用或賦值被處理成對(duì)形式單元的間接訪問(wèn)。,7.6 過(guò)程調(diào)用的處理,翻譯方法： 把實(shí)參的地址逐一放在轉(zhuǎn)子指令的前面. 例， CALL S(A，X+Y) 翻譯為: 計(jì)算X+