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

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

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

3、現(xiàn)，用上角標(biāo)來區(qū)分。 E E + E 表示為 E E(1) + E(2)l每個產(chǎn)生式的語義動作，寫在該產(chǎn)生式之后的花括號 內(nèi)。#-S0XX.VALSm-1YY.VALSm文法符號，無須進(jìn)棧，讓其進(jìn)棧只是為了醒目。需要保存的某些語義信息。實際上為一個指示器，指向分析表的某一行。l先對LR分析器的棧作一些改進(jìn)，加入語義值。STATEVALSYMTOPl文法及其語義動作(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上述的語義動作等于給出了計算由、*組成的整數(shù)算術(shù)式的過程。其相應(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若把語義動作改為產(chǎn)生中間代碼的動作，就能隨著分析的進(jìn)展逐步生成中間代碼。大部分的編譯器都不直接產(chǎn)生目標(biāo)代碼，雖然這是可以實現(xiàn)的，但是產(chǎn)生的代碼不是最優(yōu)的。因為這涉及到寄存器的分配問題，在語義分析階段，很

5、難有效地分配它們。中間代碼的必要性波蘭邏輯學(xué)家盧卡西維奇（Lukasiewicz）發(fā)明的一種表示法。一般，若e1,e2為任意的后綴表達(dá)式， 為任意雙目運算符，則用作用于e1和e2所代表的結(jié)果用后綴式e1e2 表示。推而廣之， 為k目運算符，則作用于e1e2ek的結(jié)果用e1e2ek 來表示。概念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+?示例使用一個棧（軟件?；蛘哂布＃﹣砬笾怠Ｇ?/p>

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

7、方式后綴式存放在一維數(shù)組POST1.N中，每個元素是運算符或者分量（指向符號表）。 p jump 轉(zhuǎn)到POSTp e1e2pjlt e1BC不合法。布爾表達(dá)式(E)在語言中的用途 求值 X:=ABD 條件控制 WHILE ABD DO S IF ABD THEN S1 ELSE S2布爾表達(dá)式的求值1 通常算法，如同算術(shù)表達(dá)式求值一樣，一步步地計算各部分的值，進(jìn)而計算出整個表達(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說明 上述兩種計算方法對于不包含布爾函

8、數(shù)調(diào)用的式子是沒有什么差別的。僅當(dāng)遇到布爾函數(shù)調(diào)用，并且這種函數(shù)調(diào)用引起副作用時，上述兩種算法不等價。對于第一種方法而言，可以如同翻譯算術(shù)表達(dá)式一樣來翻譯布爾表達(dá)式。ABC=D 翻譯成 = C D T1 B T1 T2 A T2 T3 第二種方法是本節(jié)主要內(nèi)容，下面將詳細(xì)討論。 一.IF語句的四元式結(jié)構(gòu) 二.翻譯的困難和解決辦法 三.E的文法和語義子程序 四.例例 IF ABD THEN S1 ELSE S2E的結(jié)構(gòu)從整體上，E對外只能轉(zhuǎn)向兩個目標(biāo)EE轉(zhuǎn)向E為假時的目標(biāo)轉(zhuǎn)向E為真時的目標(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 下一語句下一語句 1.1.困難困難 轉(zhuǎn)移的目標(biāo)在對它的應(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.語義動作語義動作(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 用自下而上語法分析方法，語法制導(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é)討論無條件和條件語句的翻譯，只討論四元式的產(chǎn)生

13、。本節(jié)內(nèi)容l 標(biāo)號和轉(zhuǎn)移語句l 條件語句l 分叉語句標(biāo)號的兩種使用方法 L: S Goto L語言中允許標(biāo)號先定義后使用，也允許先使用后定義。(1) 先定義L1 : S1L1 : S1Goto L1Goto L1遇到遇到L1 : S1L1 : S1L1標(biāo)號 定義P1符號表遇到遇到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)號 未 q1遇到goto L2, 填符號表，“未定義”，把NX

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

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

16、是。真正的回填，要在處理完S的外層后進(jìn)行。考慮語句 WHILE E(1) DO S(1) 譯為代碼結(jié)構(gòu)E(1)的代碼S(1)的代碼假出口真出口由于語句的嵌套，WHILE翻譯完了也未必知道假出口的轉(zhuǎn)移目標(biāo)，所以作為S(1).CHAIN保留下來,以便伺機回填。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語句 L語句串 A賦值句 E布爾表達(dá)式為了能及時回填有關(guān)四元式的轉(zhuǎn)移目標(biāo)，如同處

17、理布爾表達(dá)式一樣，需要對文法(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)語義動作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語義動作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語義動作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語句翻譯完成，結(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語句翻譯完成0S(1).CH1 設(shè)計屬性文法，討論翻譯的一般語義規(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 的語義規(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 對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語義： E是一個表達(dá)式，稱為選擇子。通常是一個整型表達(dá)式或者字符(char)型變量。每個Ci的值為常數(shù)，Si是語句。 若E的值等于某個Ci,則執(zhí)行Si(i= 1,2,n-1),否則執(zhí)行Sn。當(dāng)某個Si執(zhí)行完之后，整個case語句也就執(zhí)行完了。1 分叉只有10個左右時，翻譯成條件轉(zhuǎn)移語句。 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值送到該表末項的指令組,以及一個對E值查找開關(guān)表的程序 3. 運行時，循環(huán)程序?qū)值查開關(guān)表，當(dāng)E與某個Ci匹配就執(zhí)行SiS2GOTONEXTSnGOTONEXT 3 如果case的分叉情況比較多，例如在10以上，最好建立雜湊表。求出H(Ci),在其中填入Ci和SiC5S5 C1S1CzSzH(E)Sn 編譯時，對CASE構(gòu)造該表，有的表項為空。運

29、行時，求H(E)值，找對應(yīng)表項(1=H(E)=M);如空白，則執(zhí)行Sn1M4 選擇子E在基本連續(xù)的一個范圍(可通過變換)內(nèi)變化， 如從0到127，只有少數(shù)幾個值不為Ci,則可建立一個數(shù)組B0:127,每個元素BCi中存放著Si的地址。 S1頭S2頭Sn頭Sj頭Sn頭S127頭S1B2BjB127SjB1SnEC1C2下面討論一種便于語法分析制導(dǎo)實現(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:問題 當(dāng)產(chǎn)生末尾的轉(zhuǎn)移語句時，Ci和Li的地址Pi無處查找！應(yīng)在每一個Li出現(xiàn)時，將這兩方面的內(nèi)容存放到隊列中。產(chǎn)生代碼過程case產(chǎn)生標(biāo)號TEST,NEXT和一個臨時單元TE產(chǎn)生 T:= E的四元式OF產(chǎn)生GOTO TEST四元式，設(shè)置一個空隊列QUEUECi產(chǎn)生一個標(biāo)號Li,連同NXQ填入符號表，(Ci,Pi)進(jìn)入隊列QUEUESi產(chǎn)生 Si 四元式 GOTO NEXTotherwise產(chǎn)生標(biāo)號Ln,連同NXQ填入符號表END產(chǎn)生n個條件轉(zhuǎn)移語句的

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又是一個case語句。怎么辦？ 應(yīng)該建立嵌套隊列，要解決隊列嵌套，棧嵌套的底標(biāo)記問題。3 在產(chǎn)生完指令之后，隊列可以不要，但符號表仍然存在，這樣可以靈活地優(yōu)化。 本小節(jié)討論數(shù)組元素的表達(dá)式和賦值句的翻譯。由于數(shù)組元素較簡單變量有一定的特殊性，分幾個方面來介紹。本節(jié)內(nèi)容l地址計算公式l四元式中數(shù)組元素表

32、達(dá)形式(數(shù)組元素引用和中間代碼）l賦值語句中數(shù)組元素的翻譯簡化假定 數(shù)組元素按行存放，每維下限都為1，每個元素只占一個機器字，目標(biāo)機器存儲器是以字編址的。對數(shù)組元素Ai1,i2,in地址D的計算公式如下： 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無關(guān)。因此，對確定數(shù)組而言，計算數(shù)組元素的地址時

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

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

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

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

37、臨時變量的整數(shù)碼V.OFFSET 簡單變量 NULL(用于區(qū)分簡單變量和下標(biāo)變量） 下標(biāo)變量 保存VARPART的臨時變量的整數(shù)碼語義動作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是一個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)過程調(diào)用或者說轉(zhuǎn)子，本質(zhì)上是把控制權(quán)轉(zhuǎn)移給子程序。 l轉(zhuǎn)移目標(biāo)l返回地址l參數(shù)傳遞l主程序：實參約定單元l子程序：約定單元形參 訪問形參一個簡單方法，由指令攜帶參數(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ù)串的過程之中記住每個實參的地 址，以便最后將它們排列在轉(zhuǎn)子指令的前面。解決解決：第一個實參建立隊列，后面的循序記錄，要保持隊列頭。1 S CALL i(arglist) FOR 隊列arglist.QUEUE的每一項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 建立一個arglist.QUEUE,它只包含一項E.PLACE 例 CALL S(A+B,Z

44、)E A + B E.PLACE := NEWTEMP; GEN( +, A, B, E.PLACE)Arglist E 建立一個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 隊列arglist.QUEUE的每一項 P DO GEN(par, _, _, P); GEN(Call,_, _, ENTRY(i)(+,ENTRY

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