編譯原理 第六章 語(yǔ)法制導(dǎo)翻譯及中間代碼生成

1、詞法分析和語(yǔ)法分析之后的中間代碼生成，是編譯第三階段的工作。本章介紹幾種典型的中間代碼形式，以及產(chǎn)生它的算法。中間代碼的形式很多，如逆波蘭記號(hào)、樹形表示、三元式、四元式。他們都是介于單詞流與目標(biāo)指令之間的“中間產(chǎn)品”。目前還不存在一種廣泛接受的方式來(lái)描述為典型程序語(yǔ)言產(chǎn)生中間代碼所需的鄰語(yǔ)言的動(dòng)作。原因是代碼生成依賴于對(duì)語(yǔ)義的解釋，而語(yǔ)義的刻劃的形式化系統(tǒng)尚未誕生。為每一個(gè)產(chǎn)生式配一個(gè)翻譯子程序（語(yǔ)義子程序、動(dòng)作），在語(yǔ)法分析的同時(shí)執(zhí)行它。這樣，配上語(yǔ)義動(dòng)作之后，既指定了串的意義，同時(shí)又按這種意義規(guī)定了生成某種中間代碼應(yīng)作的基本動(dòng)作。l語(yǔ)法制導(dǎo)翻譯語(yǔ)法制導(dǎo)翻譯l逆波蘭表示法逆波蘭表示法l三元式

2、和樹三元式和樹l四元式四元式l簡(jiǎn)單算術(shù)表達(dá)式和賦值句到四元式的翻譯簡(jiǎn)單算術(shù)表達(dá)式和賦值句到四元式的翻譯l布爾表達(dá)式到四元式的翻譯布爾表達(dá)式到四元式的翻譯l控制語(yǔ)句的翻譯控制語(yǔ)句的翻譯l數(shù)組元素的引用數(shù)組元素的引用l過(guò)程調(diào)用過(guò)程調(diào)用l說(shuō)明語(yǔ)句的翻譯說(shuō)明語(yǔ)句的翻譯l自上而下分析制導(dǎo)翻譯概說(shuō)自上而下分析制導(dǎo)翻譯概說(shuō)在語(yǔ)法分析過(guò)程中，隨著分析的步步進(jìn)展，根據(jù)每個(gè)產(chǎn)生式所對(duì)應(yīng)的語(yǔ)義子程序（語(yǔ)義動(dòng)作）進(jìn)行翻譯（產(chǎn)生中間代碼）的辦法。概念標(biāo)記說(shuō)明標(biāo)記說(shuō)明l描述語(yǔ)義動(dòng)作時(shí)，需要賦予每個(gè)文法符號(hào)X（終結(jié)符或者 非終結(jié)符）以種種不同方面的值，如X.TYPE(類型），X.VAL(值）等。l一個(gè)產(chǎn)生式中同一符號(hào)多次出

3、現(xiàn)，用上角標(biāo)來(lái)區(qū)分。 E E + E 表示為 E E(1) + E(2)l每個(gè)產(chǎn)生式的語(yǔ)義動(dòng)作，寫在該產(chǎn)生式之后的花括號(hào) 內(nèi)。#-S0XX.VALSm-1YY.VALSm文法符號(hào)，無(wú)須進(jìn)棧，讓其進(jìn)棧只是為了醒目。需要保存的某些語(yǔ)義信息。實(shí)際上為一個(gè)指示器，指向分析表的某一行。l先對(duì)LR分析器的棧作一些改進(jìn)，加入語(yǔ)義值。STATEVALSYMTOPl文法及其語(yǔ)義動(dòng)作(0)S E print E.VAL(1)EE(1)+E(2) E.VAL:=E(1).VAL+E(2).VAL(2)EE(1)*E(2) E.VAL:=E(1).VAL*E(2).VAL(3)E(E(1) E.VAL:=E(1).V

4、AL(4)En E.VAL:=LEXVAL上述的語(yǔ)義動(dòng)作等于給出了計(jì)算由、*組成的整數(shù)算術(shù)式的過(guò)程。其相應(yīng)的程序段如下：(0)S E print VALTOP(1)EE(1)+E(2) VALTOP:=VALTOP+VALTOP+2(2)EE(1)*E(2) VALTOP:=VALTOP*VALTOP+2(3)E(E(1) VALTOP:=VALTOP+1(4)En VALTOP:=LEXVAL若把語(yǔ)義動(dòng)作改為產(chǎn)生中間代碼的動(dòng)作，就能隨著分析的進(jìn)展逐步生成中間代碼。大部分的編譯器都不直接產(chǎn)生目標(biāo)代碼，雖然這是可以實(shí)現(xiàn)的，但是產(chǎn)生的代碼不是最優(yōu)的。因?yàn)檫@涉及到寄存器的分配問(wèn)題，在語(yǔ)義分析階段，很

5、難有效地分配它們。中間代碼的必要性波蘭邏輯學(xué)家盧卡西維奇（Lukasiewicz）發(fā)明的一種表示法。一般，若e1,e2為任意的后綴表達(dá)式， 為任意雙目運(yùn)算符，則用作用于e1和e2所代表的結(jié)果用后綴式e1e2 表示。推而廣之， 為k目運(yùn)算符，則作用于e1e2ek的結(jié)果用e1e2ek 來(lái)表示。概念l a * ( b + c ) abc+*l(a + b)*(c + d) ab + cd +*若用？表示if-then-else,則lIf a then if c-d then a+c else a*c else a+b a cd- ac+ ac*? ab+?示例使用一個(gè)棧（軟件?；蛘哂布＃﹣?lái)求值。求

6、值過(guò)程：從左到右掃描后綴式，每碰到運(yùn)算量就把它推進(jìn)棧，每碰到k目運(yùn)算符就把它作用于棧頂?shù)膋個(gè)項(xiàng)，并用運(yùn)算結(jié)果來(lái)代替這k個(gè)項(xiàng)。a進(jìn)棧1 1 3 3 + + 5 5* *b進(jìn)棧ab相加，移去兩項(xiàng)，和置于棧頂4 43+1=3+1=c進(jìn)棧棧頂兩項(xiàng)相乘，移去兩項(xiàng)，積置于棧頂5 5* *4=4=2020計(jì)算完畢，結(jié)果為20前面講到，if-then-else運(yùn)算符的實(shí)現(xiàn)”exy?” e不等于0，取x，否則取y.這種表示法要求在任何情況下都要把x,y都計(jì)算出來(lái)，盡管只用到其中一個(gè)。而且，如果運(yùn)算量無(wú)定義或者有副作用，則后綴表示法不僅無(wú)效，而且可能是錯(cuò)誤的。引入標(biāo)號(hào)，在后綴式中加入條件轉(zhuǎn)移，無(wú)條件轉(zhuǎn)移算符。存儲(chǔ)

7、方式后綴式存放在一維數(shù)組POST1.N中，每個(gè)元素是運(yùn)算符或者分量（指向符號(hào)表）。 p jump 轉(zhuǎn)到POSTp e1e2pjlt e1BC不合法。布爾表達(dá)式(E)在語(yǔ)言中的用途 求值 X:=ABD 條件控制 WHILE ABD DO S IF ABD THEN S1 ELSE S2布爾表達(dá)式的求值1 通常算法，如同算術(shù)表達(dá)式求值一樣，一步步地計(jì)算各部分的值，進(jìn)而計(jì)算出整個(gè)表達(dá)式的值。2 采用優(yōu)化措施 AB if A then true else B AB if A then B else false A if A then false else true說(shuō)明 上述兩種計(jì)算方法對(duì)于不包含布爾函

8、數(shù)調(diào)用的式子是沒(méi)有什么差別的。僅當(dāng)遇到布爾函數(shù)調(diào)用，并且這種函數(shù)調(diào)用引起副作用時(shí)，上述兩種算法不等價(jià)。對(duì)于第一種方法而言，可以如同翻譯算術(shù)表達(dá)式一樣來(lái)翻譯布爾表達(dá)式。ABC=D 翻譯成 = C D T1 B T1 T2 A T2 T3 第二種方法是本節(jié)主要內(nèi)容，下面將詳細(xì)討論。 一.IF語(yǔ)句的四元式結(jié)構(gòu) 二.翻譯的困難和解決辦法 三.E的文法和語(yǔ)義子程序 四.例例 IF ABD THEN S1 ELSE S2E的結(jié)構(gòu)從整體上，E對(duì)外只能轉(zhuǎn)向兩個(gè)目標(biāo)EE轉(zhuǎn)向E為假時(shí)的目標(biāo)轉(zhuǎn)向E為真時(shí)的目標(biāo)(1) (1) (jnz,A,_,5)(jnz,A,_,5)(2) (j,_,_,3)(2) (j,_,_,

9、3)(3) (3) (j,B,D,5)(j,B,D,5)(4) (4) (j,_,_,p+1)(j,_,_,p+1)(5) (5) (p)(p)(p+1)(p+1)(q)(q)S1S1(j,_,_,q)(j,_,_,q)S2S2 下一語(yǔ)句下一語(yǔ)句 1.1.困難困難 轉(zhuǎn)移的目標(biāo)在對(duì)它的應(yīng)用之后才出現(xiàn)； (j,_,_,0)(j,_,_,0) E可以很復(fù)雜，上面的情況可以頻繁出現(xiàn)(1) (1) (jnz,A,_,5)(jnz,A,_,5)(2) (j,_,_,3)(2) (j,_,_,3)(3) (3) (j,B,D,5)(jEEEE|E|(E)|i|i rop i G2 E-E E|EE|E|(E

10、)|i|i rop i E -E E-E 2. 2.語(yǔ)義動(dòng)作語(yǔ)義動(dòng)作(1)(2 )(1)(1)(1)(2)(1)(.:;.:1;(,( ), _,0);( , _, _,0).:;.:1;(,(),(),0);( , _, _,0).:.;.:.(1)(2)(3)()(4)E TCNXQ E FCNXQGENjnz ENTRY iGENjE TCNXQ E FCNXQGENjnop ENTRY iENTRY iGENjE TCETC E FCEFCEiEirop iEEEE (1)(1)1).:.;.:.E TCEFC E FCETC(1)(1)( 2 )( 2 )(1)0(1)( 2 )0(

11、 2 )(1)(2)0(1)0(2)(.,);.:.:.;.:(.,.)(.,);.:.:.;.:(.,.(5)(6)(7)(8)BACKPATCHETC NXQEFCEFCE TCETCE FCMERG EFC EFCBACKPATCHEFC NXQETCETCE FCEFCE TCMERG ETC EEEEE EEEEE E)TC 用自下而上語(yǔ)法分析方法，語(yǔ)法制導(dǎo)生成ABD的四元式)0,();0,)(,(; 1.;.) 1)1()1(1JGENiEntryjnzGENNXQFCENXQTCEiE）（.:.);,.()2)1(0)1()1(0TCETCENXQFCEBACKPATCHEE)0

12、 ,();0),(),(,(; 1:.;:.)3)2()1()2()1(，jGENiENTRYiENTRYjropGENNXQFCENXQTCEiropiEAE)1(. 1)0,() 1Ajnz)0,()2jTCE.)1(1FCE.)1(2)1(0.2EE)3,.(FCEB31TCE .0DBE)2(. 3TCE.)2(3FCE.)2(4)0,()3DBj )0,()4j)2(0.4EEE 4FCE.1TCE.3).,.()2(0TCETCEMERG).,.(:.;.:.)4)2(0)2()2(0TCETCEMERGTCEFCEFCEEEE 本小節(jié)討論無(wú)條件和條件語(yǔ)句的翻譯，只討論四元式的產(chǎn)生

13、。本節(jié)內(nèi)容l 標(biāo)號(hào)和轉(zhuǎn)移語(yǔ)句l 條件語(yǔ)句l 分叉語(yǔ)句標(biāo)號(hào)的兩種使用方法 L: S Goto L語(yǔ)言中允許標(biāo)號(hào)先定義后使用，也允許先使用后定義。(1) 先定義L1 : S1L1 : S1Goto L1Goto L1遇到遇到L1 : S1L1 : S1L1標(biāo)號(hào) 定義P1符號(hào)表遇到遇到Goto L1Goto L1(j, _, _, P1)名字類型定義否地址P1 ( )(2) (2) 先使用先使用 q1q1 goto L2goto L2 q2 q2 Goto L2Goto L2 q3 q3 L2 : S2L2 : S2名字類型定義地址L2標(biāo)號(hào) 未 q1遇到goto L2, 填符號(hào)表，“未定義”，把NX

14、Q填入L2的地址部分，作為鏈頭。產(chǎn)生( j, _, _, 0)q1 (j, _, _, 0 )遇到goto L2, 查到未定義，取符號(hào)表中L2的地址q1填入四元式q2:(j, _, _,q1),將q2填入符號(hào)表。 q2 (j, _, _, q1 )q2遇到L2:S2,就可以回填。q3q3q3一般而言，帶標(biāo)號(hào)語(yǔ)句產(chǎn)生式 S label S label i:Label i: 的語(yǔ)義動(dòng)作1. 若i所指的標(biāo)識(shí)符(假定為L(zhǎng))不在符號(hào)表中，則把它填入，置類型為“標(biāo)號(hào)”，“定義否”為“已”，地址為NXQ。2, 若 L已在符號(hào)表中，但“類型”不為“標(biāo)號(hào)”或者“定義否”為“已”，則報(bào)告出錯(cuò)。3. 若L已在符號(hào)表

15、中，則把標(biāo)志“未”改為“已”，然后，把地址欄中的鏈頭(記為q)取出，同時(shí)把NXQ填在其中，最后，執(zhí)行BACKPATCH(q,NXQ)。1 較為復(fù)雜的程序控制語(yǔ)句常常是嵌套的。 S1后有一條無(wú)條件轉(zhuǎn)移指令，跳轉(zhuǎn)到本語(yǔ)句之后。這里，與上一節(jié)不同的是，在S2翻譯之后，也不能確定其跳轉(zhuǎn)地址，它要跨越S2,S3。 所以，轉(zhuǎn)移地址的確定與語(yǔ)句所處的環(huán)境有關(guān)。if E1 THENif E2 then S1 else S2ELSE S3 解決辦法 令每個(gè)非終結(jié)符S(L)附帶一項(xiàng)語(yǔ)義值S.CHAIN，它指出一條鏈的頭，該鏈?zhǔn)撬衅诖g完S后回填目標(biāo)的四元式組成的。注意 回填目標(biāo)可能是S得下一條四元式，也可能不

16、是。真正的回填，要在處理完S的外層后進(jìn)行。考慮語(yǔ)句 WHILE E(1) DO S(1) 譯為代碼結(jié)構(gòu)E(1)的代碼S(1)的代碼假出口真出口由于語(yǔ)句的嵌套，WHILE翻譯完了也未必知道假出口的轉(zhuǎn)移目標(biāo)，所以作為S(1).CHAIN保留下來(lái),以便伺機(jī)回填。While E(1) do S(1)E(1).TCE(1).FCIF E THENELSE S示例示例 S if E then S |if E the S else S |while E do S |begin L end |A L L; S |S (5.5) S語(yǔ)句 L語(yǔ)句串 A賦值句 E布爾表達(dá)式為了能及時(shí)回填有關(guān)四元式的轉(zhuǎn)移目標(biāo)，如同處

17、理布爾表達(dá)式一樣，需要對(duì)文法(5.5)進(jìn)行改寫。 S C S | TP S | Wd S | begin L end | A L LS S | S C if E then TP CS else Wd W E do W while LS L; (5.6)語(yǔ)義動(dòng)作C if E then BACKPATCH (E.TC, NXQ); C.CHAIN := E.FC S C S(1) S.CHAIN := MERG(C.CHAIN, S(1).CHAINTP C S(1) else q := NXQ; GEN(j, _, _, 0); BACKPATCH(C.CHAIN,NXQ); TP.CHAIN

18、:= MERGE(S(1).CHAIN,q)S TP S(2) S.CHIAN := MERG(TP.CHIAN, S(2).CHIAN語(yǔ)義動(dòng)作W while W.QUAD := NXQ Wd W E do BACKPATCH (E.TC,NXQ); Wd.CHAIN := E.FC; Wd.QUAD := W.QUAD S Wd S(1) BACHPATCH(S(1).CHAIN,Wd.QUAD); GEN(j, _, _, Wd.QUAD); S.CHAIN := Wd.CHAIN語(yǔ)義動(dòng)作L S L.CHAIN := S.CHAINLS L; BACKPATCH(L.CHAIN,NXQ)

19、L LS S(1) L.CHAIN := S(1).CHAINS begin L end S.CHAIN := L.CHAIN S A S.CHAIN := 0 空鏈IF E THEN S(1) ELSE S(2)CTPS示例示例ES(1)的代碼S(2)的代碼E的代碼E.TCE.FCS(1).CHAINS(2).CHAINC.CHAINBACKPATCH(E.TC,NXQ)S.CHAINMERG(TP.CH,S(2).CH)C IF E THENTP C S(1) ELSES TP S(2)q: ( j, _, _, 0)TP.CHAINBACKPATCH(C.CH,NXQ)MERG(S(1)

20、.CH,q)IF E THEN WHILE E(1) DO S(1) ELSE S(2) 的示意圖IF E THEN WHILE E(1) DO S(1) ELSE S(2)WCWdS1TPSIFTHENWHILEE 的代碼E.TCE.FCC.CHE(1)的代碼E(1).TE(1).FWd.CWd.Q=W.QS(1)的代碼S(1).C C IF E THENBACKPATCH(E.TC,NXQ); C.CHAIN := E.FC W WHILEW.QUAD := NXQWd W E(1) DOBACKPATCH(E(1).TC,NXQ); Wd.CHAIN := E(1).FC Wd.quad

21、 := W.QUAD S1 Wd S(1)BACKPATCH(S(1).C,Wd.Q); GEN(j,_,_,Wd.Q); S1.C := Wd.C TP C S1 ELSE q := NXQ; GEN(j,_,_,0); BACKPATCH(C.CH,NXQ); TP.C:=MERG(S1.C,q); ELSES(2)的代碼S(2).Cq:(j,_,_,0)TP.CS TP S(2) S.CH := MERG(TP.CH,S(2).CH) S.C(j,_,_,Wd.Q)S1.C語(yǔ)句翻譯完成，結(jié)果如圖所示例子While AB DO if CD then X:= Y+ZWE(1)WdE(2)CS

22、(1)S(2)SE(2).TC102 (j,C,D, 0)E(2).FC102103103 (j,_,_, 0)103S(2).CHE(1).FC E(1).TC100101100 (j,A,B, 0)101 (j,_,_, 0 )104 (+,Y, Z, T)WWHILEW.QUAD := NXQW.QUAD:=100E(1) i(1) rop i(2)E(1).TC:=NXQ;E(1).FC:=NXQ+1;GEN(jrop,ENTRY(i(1),ENTRY(i(2),0);GEN(j,_,_,0);Wd W E(1) DOBACKPATCH(E(1).TC,NXQ); Wd.CHAIN :

23、= E(1).FC; Wd.QUAD :=W.QUADE(2)i(1) rop i(2)E(2).TC:=NXQ;E(2).FC:=NXQ+1;GEN(jrop,ENTRY(i(1),ENTRY(i(2),0);GEN(j,_,_,0);Wd.CWd.QUAD:=100101102C IF E(2) THENBACKPATCH(E(2).TC,NXQ); C.CHAIN :=E(2).FC104103C.CHE i(1)+i(2) E.PLACE := NEWTEMP; GEN(+,ENTRY(i(1),ENTRY(i(2),E.PALCE)A i:=E GEN(:=,E.PALCE,_,EN

24、TRY(i)105 (:=,T,_, X)S(2) C S(1) S(2).CHAIN := MERG(C.CHAIN,S(1).CHAIN) S Wd S(2) BACKPATCH(S(2).CHAIN,Wd.QUAD); GEN(j,_,_,Wd.QUAD); S.CHAIN := Wd.CHAIN 100106 (j,_,_,100)S.CH101While AB DO if CD then X:= Y+Z語(yǔ)句翻譯完成0S(1).CH1 設(shè)計(jì)屬性文法，討論翻譯的一般語(yǔ)義規(guī)則。1 產(chǎn)生標(biāo)志，被轉(zhuǎn)目標(biāo)，在S.code中出現(xiàn)S.Begin := newlabelE.True := newlab

25、el如 S while E do S1 的語(yǔ)義規(guī)則包含四部分：E.CODES1.CODEGoto S.beginS.beginE.tE.f2 “內(nèi)部的”/可隱藏標(biāo)志用S.Next及兩標(biāo)志表示。/S.next構(gòu)成E.F := S.nextS1.next := S.begin3 S.code 的組成 S.code := gen(S.begin :)| E.code| gen(S.true :)| S1.code | gen (goto S.begin)4 對(duì)1，2歸納，可知轉(zhuǎn)移目標(biāo)有兩類：一類在S.code和S.next中；另一類是可隱藏的，內(nèi)部的。2 一遍掃描產(chǎn)生代碼，翻譯模式。S while

26、M1 E do M2 S2 M M.quad := nextquad S if E then M1 S1 N else M2 S2 b(E.truelist, M1.q); b(E.falselist,M2.q); S.nextlist := merg(S1.nextlist,N.nextlist, S2.nextlist) N N.n := nakelist(nextquad); M M.q := nextquad C if E then b(e.tc, NXQ) C.C := E.FCTP C S1 ELSEq: (j, _,_,_)b(c.c,NXQ)TP.C := merg(S1.c,

27、q);S TP S2 S.C := merg(TP.C, S2.C) 形式: case E of C1: S1 C2: S2 Cn-1: Sn-1 otherwise : Sn end語(yǔ)義： E是一個(gè)表達(dá)式，稱為選擇子。通常是一個(gè)整型表達(dá)式或者字符(char)型變量。每個(gè)Ci的值為常數(shù)，Si是語(yǔ)句。 若E的值等于某個(gè)Ci,則執(zhí)行Si(i= 1,2,n-1),否則執(zhí)行Sn。當(dāng)某個(gè)Si執(zhí)行完之后，整個(gè)case語(yǔ)句也就執(zhí)行完了。1 分叉只有10個(gè)左右時(shí)，翻譯成條件轉(zhuǎn)移語(yǔ)句。 T := E;L1: IF TC1 GOTO L2 S1; GOTO NEXT L2: IF TC2 GOTO L3 S2;

28、GOTO NEXT;L3: .Ln-1: IF TCn-1 GOTO Ln Sn-1; GOTO NEXT;Ln: Sn;NEXT:2 開關(guān)表C1S1 C2S2Cn-1Sn-1ESnS1GOTONEXT 1. 編譯程序構(gòu)造上面的開關(guān)表 2. 產(chǎn)生將E值送到該表末項(xiàng)的指令組,以及一個(gè)對(duì)E值查找開關(guān)表的程序 3. 運(yùn)行時(shí)，循環(huán)程序?qū)值查開關(guān)表，當(dāng)E與某個(gè)Ci匹配就執(zhí)行SiS2GOTONEXTSnGOTONEXT 3 如果case的分叉情況比較多，例如在10以上，最好建立雜湊表。求出H(Ci),在其中填入Ci和SiC5S5 C1S1CzSzH(E)Sn 編譯時(shí)，對(duì)CASE構(gòu)造該表，有的表項(xiàng)為空。運(yùn)

29、行時(shí)，求H(E)值，找對(duì)應(yīng)表項(xiàng)(1=H(E)=M);如空白，則執(zhí)行Sn1M4 選擇子E在基本連續(xù)的一個(gè)范圍(可通過(guò)變換)內(nèi)變化， 如從0到127，只有少數(shù)幾個(gè)值不為Ci,則可建立一個(gè)數(shù)組B0:127,每個(gè)元素BCi中存放著Si的地址。 S1頭S2頭Sn頭Sj頭Sn頭S127頭S1B2BjB127SjB1SnEC1C2下面討論一種便于語(yǔ)法分析制導(dǎo)實(shí)現(xiàn)的翻譯法。中間碼形式 T := E 的中間碼 Goto TESTL1: 關(guān)于S1的中間碼 Goto NEXTL2: 關(guān)于S2的中間碼 Goto NEXT Ln-1: 關(guān)于Sn-1的中間碼 Goto NEXTLn: 關(guān)于Sn的中間碼 Goto NEXT

30、TEST: IF T=C1 GOTO L1; IF T=C2 TOTO L2; IF T=Cn-1 GOTO Ln-1 Goto LnNEXT:問(wèn)題 當(dāng)產(chǎn)生末尾的轉(zhuǎn)移語(yǔ)句時(shí)，Ci和Li的地址Pi無(wú)處查找！應(yīng)在每一個(gè)Li出現(xiàn)時(shí)，將這兩方面的內(nèi)容存放到隊(duì)列中。產(chǎn)生代碼過(guò)程case產(chǎn)生標(biāo)號(hào)TEST,NEXT和一個(gè)臨時(shí)單元TE產(chǎn)生 T:= E的四元式OF產(chǎn)生GOTO TEST四元式，設(shè)置一個(gè)空隊(duì)列QUEUECi產(chǎn)生一個(gè)標(biāo)號(hào)Li,連同NXQ填入符號(hào)表，(Ci,Pi)進(jìn)入隊(duì)列QUEUESi產(chǎn)生 Si 四元式 GOTO NEXTotherwise產(chǎn)生標(biāo)號(hào)Ln,連同NXQ填入符號(hào)表END產(chǎn)生n個(gè)條件轉(zhuǎn)移語(yǔ)句的

31、四元式 TEST: (case, C1, P1, _) (case, C2, P2, _) (case, Cn-1, Pn-1, _ ) (case, T, Pn, _ ) (label, NEXT, _, _) NEXT:注意1 末尾的多向轉(zhuǎn)移目標(biāo)指令組，視不同情況生成，可優(yōu) 化處理。 如果Si又是一個(gè)case語(yǔ)句。怎么辦？ 應(yīng)該建立嵌套隊(duì)列，要解決隊(duì)列嵌套，棧嵌套的底標(biāo)記問(wèn)題。3 在產(chǎn)生完指令之后，隊(duì)列可以不要，但符號(hào)表仍然存在，這樣可以靈活地優(yōu)化。 本小節(jié)討論數(shù)組元素的表達(dá)式和賦值句的翻譯。由于數(shù)組元素較簡(jiǎn)單變量有一定的特殊性，分幾個(gè)方面來(lái)介紹。本節(jié)內(nèi)容l地址計(jì)算公式l四元式中數(shù)組元素表

32、達(dá)形式(數(shù)組元素引用和中間代碼）l賦值語(yǔ)句中數(shù)組元素的翻譯簡(jiǎn)化假定 數(shù)組元素按行存放，每維下限都為1，每個(gè)元素只占一個(gè)機(jī)器字，目標(biāo)機(jī)器存儲(chǔ)器是以字編址的。對(duì)數(shù)組元素Ai1,i2,in地址D的計(jì)算公式如下： D = CONSPART + VARPART CONSPART = a C C = d2d3dn + d3d4dn + + dn +1 VARPART = i1d2d3dn+i2d3d4dn+in-1dn+inaaddr(A1,1,1),數(shù)組首址注意l CONSPART只依賴于數(shù)組各位的界限d和數(shù)組的首址a,與數(shù)組元素各維的下標(biāo)i1,i2,in無(wú)關(guān)。因此，對(duì)確定數(shù)組而言，計(jì)算數(shù)組元素的地址時(shí)

33、，無(wú)需獨(dú)立計(jì)算CONSPART。lVARPART是一個(gè)可變部分，它的值隨著各維下標(biāo)i1,i2, ,in的不同而不同。l 計(jì)算數(shù)組元素的地址主要計(jì)算VARPART。這兒只討論確定數(shù)組(編譯時(shí)可靜態(tài)確定體積的數(shù)組，也稱靜態(tài)數(shù)組)的翻譯。簡(jiǎn)單變量可以在符號(hào)表中查到它的地址，而數(shù)組元素卻不行，在符號(hào)表中只有它們的總代表數(shù)組名的入口。名字特性地址 A數(shù)組i1u1d1InundnnCtypeaA1,1,1A1,1,2因此，每個(gè)下標(biāo)變量在語(yǔ)句中出現(xiàn)，如 X:=A,在目標(biāo)指令中要有計(jì)算A地址的指令。下標(biāo)變量的表示形式不變部分CONSPART,在編譯時(shí)，可以產(chǎn)生 T1 := a-C ,將其存放在臨時(shí)單元T1中，

34、在運(yùn)行時(shí)計(jì)算下標(biāo)變量Ai1,i2,in的可變部分，產(chǎn)生計(jì)算VARPART的四元式。令T:=VARPART,所以addr(Ai1,in) = T + T1這樣，四元式有如下形式： :=, T+T1, _ , X 在四元式中出現(xiàn)T+T1不夠理想，不夠簡(jiǎn)潔。參照計(jì)算機(jī)的變址指令，考慮使用T1T如此，四元式的形式如下： 變址取數(shù) X:= T1T ( =, T1T, _, X) 變址存書 T1T := X ( =, X, _, T1T)關(guān)鍵問(wèn)題是下標(biāo)表達(dá)式的計(jì)算，進(jìn)而計(jì)算可變部分T。文法 A V:= E V ielist|i elist elist,E | E E E + E |(E) |V 所定義的賦

35、值句A就是變量V后跟賦值號(hào):=和算術(shù)表達(dá)式E 如果數(shù)組元素為AB,CD,EF,G,那么，在按上面的文法歸約下標(biāo)表達(dá)式串時(shí)，無(wú)法獲得數(shù)組的內(nèi)情向量，對(duì)每一維的下標(biāo)都需要保存下來(lái)。在該表達(dá)式中，就要保存B,D,F等中間結(jié)果，如果規(guī)模進(jìn)一步擴(kuò)大的話，要保存的中間量就會(huì)迅速增加，很是繁瑣。所以，要尋求能及時(shí)計(jì)算下標(biāo)的方法。定義要點(diǎn)1 文法允許數(shù)組元素嵌套定義 ，AB,C2+1。2 為了在歸約時(shí)完成VARPART的計(jì)算，需要修改V的文法。這樣能夠在整個(gè)下標(biāo)串elist的翻譯過(guò)程中隨時(shí)知道數(shù)組名i的入口，獲取登記在符號(hào)表中的數(shù)組信息。V ielist|i V elist | ielist elist,E

36、| E elist elist,E | iE 回顧一下VARPART的計(jì)算公式，它是一個(gè)乘加式。 (i1*d2+i2)d3+i3)+in-1)dn+inelist.PLACElimit(ARRAY,k)語(yǔ)義變量和過(guò)程Elist.ARRAY 數(shù)組名的符號(hào)表入口Elist.DIM 數(shù)組維數(shù)計(jì)數(shù)器Elist.PLACE 記存業(yè)已形成的VARPART的中間結(jié)果名字在符號(hào)表中的位置，或者是一個(gè)臨時(shí)變量的整數(shù)碼。Limit(ARRAY,k) 函數(shù)過(guò)程，數(shù)組ARRAY的第k維長(zhǎng)度dk現(xiàn)在要考慮的變量有兩類，每個(gè)變量V有兩項(xiàng)語(yǔ)義值。V.PLACE 簡(jiǎn)單變量 變量名的符號(hào)表入口 下標(biāo)變量 保存CONSPART的

37、臨時(shí)變量的整數(shù)碼V.OFFSET 簡(jiǎn)單變量 NULL(用于區(qū)分簡(jiǎn)單變量和下標(biāo)變量） 下標(biāo)變量 保存VARPART的臨時(shí)變量的整數(shù)碼語(yǔ)義動(dòng)作1 AV:=E IF (V.OFFSET=NULL) THEN GEN(:=,E.PLACE,_,V.PLACE) ELSE GEN(=,E.PLACE,_,V.PLACEV.OFFSET)2 EE(1)+E(2) T:=NEWTEMP; GEN(+,E(1).PLACE,E(2).PLACE,T); E.PLACE := T 3 E (E(1) E.PLACE := E(1).PLACE 4 EV IF (V.OFFSET=NULL) THEN E.PLA

38、CE := V.PLACE; ELSE BEGIN T:=NEWTEMP; GEN (=,V.PLACEOFFSET,_,T); E.PLACE:=T; END 5 Velist T:=NEWTEMP; GEN(-,elist.ARRAY,C,T); V.PLACE:=T; V.OFFSET := elist.PLACE; 6 V i V.PLACE:= ENTRY(i); V.OFFSET:= NULL; 7 elistelist(1),E T:=NEWTEMP; k:= elist(1).DIM + 1; dk:=LIMIT(elist(1).ARRAY,k); GEN(*,elist(1

39、).PLACE,dk,T);GEN(+,E.PLACE,T,T); elist.ARRAY := elist(1).ARRAY; elist.PLACE := T; elist.DIM := k; 8 elist iE elist.PLACE := E.PLACE; elist.DIM := 1; elist.ARRAY := ENTRY(i) A是一個(gè)10*20的數(shù)組，AI+2,J+1:= M+N的翻譯(+, I, 2, T1)(+, J, 1, T2)(*, T1, 20, T3)(+, T2, T3, T3)(-, A, 21, T4)(+, M, N, T5)(=, T5, _,T4T

40、3)I+2EAielist, ,elistE EI+2I+2 T1:=TEMP; T1:=TEMP; GEN(+,I,2,T1); GEN(+,I,2,T1); E.PLACE:= T1 E.PLACE:= T1 elist AE elist.PLACE:=E.PLACE; elist.DIM :=1; elist.ARRAY:=ENTRY(A) J+1EEJ+1 T2:=TEMP; GEN(+, J, 1, T2); E.PLACE:= T2 elistelist(1),E T3:=NEWTEMP; k:= elist(1).DIM+1; dk:=limit(elist(1).ARRAY,k

41、);GEN(*,elist(1).PLACE,dk,T3);GEN(+,E.PLACE,T3,T3);elist.ARRAY:=elist(1).ARRAY; elist.PLACE:=T3; elist.DIM:=kVVelist T4:=NEWTEMP; GEN(-,elist.ARRAY,C,T4); V.PLACE:=T4; V.OFFSET:=elist.PLACE; EM+N T5:=NEWTEMP; GEN(+, M, N, T5); E.PLACE:= T5; AV:=E IF (V.OFFSET=NULL) THEN GEN(:=,E.PLACE,_,V.PLACE); EL

42、SE GEN(=, E.PLACE, _, V.PALCEV.OFFSET) _Call S(A+B,Z)_S(X,Y)S(X,Y)過(guò)程調(diào)用或者說(shuō)轉(zhuǎn)子，本質(zhì)上是把控制權(quán)轉(zhuǎn)移給子程序。 l轉(zhuǎn)移目標(biāo)l返回地址l參數(shù)傳遞l主程序：實(shí)參約定單元l子程序：約定單元形參 訪問(wèn)形參一個(gè)簡(jiǎn)單方法，由指令攜帶參數(shù)地址，把實(shí)參地址統(tǒng)一放在轉(zhuǎn)子指令前。如 CALL S(A+B,Z) 翻成K-4: T := A+BK-3: Par TK-2: Par ZK-1: Call SK: 文法G：（1） S CALL i(arglist)（2） arglist arglist,E（3） arglist E困難困難：如何在處理

43、參數(shù)串的過(guò)程之中記住每個(gè)實(shí)參的地 址，以便最后將它們排列在轉(zhuǎn)子指令的前面。解決解決：第一個(gè)實(shí)參建立隊(duì)列，后面的循序記錄，要保持隊(duì)列頭。1 S CALL i(arglist) FOR 隊(duì)列arglist.QUEUE的每一項(xiàng)P DO GEN ( par,_,_,p); GEN (call,_,_,ENTRY(i)2 arglist arglist(1),E 把E.PLACE排在arglist(1).QUEUE的末端； arglist.QUEUE := arglist(1).QUEUE3 arglist E 建立一個(gè)arglist.QUEUE,它只包含一項(xiàng)E.PLACE 例 CALL S(A+B,Z

44、)E A + B E.PLACE := NEWTEMP; GEN( +, A, B, E.PLACE)Arglist E 建立一個(gè)arglist.QUEUE,包含E.PLACE E IE.PLACE := ENTRY(Z)Arglist arglist(1),E把Z排在T之后，即將E.PLACE置于arglist(1).QUEUE的末尾；Arglist.QUEUE := arglist(1).QUEUE S CALL i(arglist)For 隊(duì)列arglist.QUEUE的每一項(xiàng) P DO GEN(par, _, _, P); GEN(Call,_, _, ENTRY(i)(+,ENTRY

45、(A),ENTRY(B),T)(par, _, _, T)(par, _, _, Z)(Call, _, _, ENTRY(S)隊(duì)列arglist.QUEUETZ X := A(I,J)過(guò)程調(diào)用或者數(shù)組引用，兩者難以區(qū)分。而語(yǔ)法制導(dǎo)翻譯是按語(yǔ)法規(guī)則（產(chǎn)生式）進(jìn)行的，上下文無(wú)法區(qū)分，這就造成了翻譯的困難。解決方案l查符號(hào)表l詞法分析器在發(fā)送A之前先查表確定其特性l規(guī)定數(shù)組用，避免沖突l先說(shuō)明后引用，則使用兩邊掃描程序說(shuō)明語(yǔ)句如Integer L,M,N;ARRAY A;語(yǔ)義動(dòng)作是把 L,M,N,A登記到符號(hào)表中，并在相應(yīng)位置填入整型等性質(zhì)。D integer namelist | real namelistNamelist namelist,i | i問(wèn)題該文法要求把完整的namelist讀完才能做語(yǔ)義動(dòng)作（在符號(hào)表中登記性質(zhì)）。這樣，就必須用棧、隊(duì)列來(lái)保存所有這些名字。D D,i | integer i | real iD integer iFILL(ENTRY(i),int);D.ATT := intD real iFILL(EN