編譯原理6語(yǔ)義分析和中間代碼生成

語(yǔ)法制導(dǎo)翻譯和中間代碼生成詞法分析和語(yǔ)法分析之后的中間代碼生成，是編譯第三階段的工作。本章介紹幾種典型的中間代碼形式，以及產(chǎn)生它的算法。中間代碼的形式很多，如逆波蘭記號(hào)、樹(shù)形表示、三元式、四元式。他們都是介于單詞流與目標(biāo)指令之間的“中間產(chǎn)品”。困難目前還不存在一種廣泛接受的方式來(lái)描述為典型程序語(yǔ)言產(chǎn)生中間代碼所需的鄰語(yǔ)言的動(dòng)作。原因是代碼生成依賴(lài)于對(duì)語(yǔ)義的解釋?zhuān)Z(yǔ)義的刻劃的形式化系統(tǒng)尚未誕生。解決辦法為每一個(gè)產(chǎn)生式配一個(gè)翻譯子程序（語(yǔ)義子程序、動(dòng)作），在語(yǔ)法分析的同時(shí)執(zhí)行它。這樣，配上語(yǔ)義動(dòng)作之后，既指定了串的意義，同時(shí)又按這種意義規(guī)定了生成某種中間代碼應(yīng)作的基本動(dòng)作。本章內(nèi)容語(yǔ)法制導(dǎo)翻譯逆波蘭表示法三元式和樹(shù)四元式簡(jiǎn)單算術(shù)表達(dá)式和賦值句到四元式的翻譯布爾表達(dá)式到四元式的翻譯控制語(yǔ)句的翻譯數(shù)組元素的引用過(guò)程調(diào)用說(shuō)明語(yǔ)句的翻譯自上而下分析制導(dǎo)翻譯概說(shuō)在語(yǔ)法分析過(guò)程中，隨著分析的步步進(jìn)展，根據(jù)每個(gè)產(chǎn)生式所對(duì)應(yīng)的語(yǔ)義子程序（語(yǔ)義動(dòng)作）進(jìn)行翻譯（產(chǎn)生中間代碼）的辦法。概念6.1語(yǔ)法制導(dǎo)翻譯概說(shuō)標(biāo)記說(shuō)明描述語(yǔ)義動(dòng)作時(shí)，需要賦予每個(gè)文法符號(hào)X（終結(jié)符或者非終結(jié)符）以種種不同方面的值，如X.TYPE(類(lèi)型），X.VAL(值）等。一個(gè)產(chǎn)生式中同一符號(hào)多次出現(xiàn)，用上角標(biāo)來(lái)區(qū)分。

EE+E表示為

E

E(1)

+E(2)每個(gè)產(chǎn)生式的語(yǔ)義動(dòng)作，寫(xiě)在該產(chǎn)生式之后的花括號(hào)內(nèi)。#--S0………XX.VALSm-1YY.VALSm文法符號(hào)，無(wú)須進(jìn)棧，讓其進(jìn)棧只是為了醒目。需要保存的某些語(yǔ)義信息。實(shí)際上為一個(gè)指示器，指向分析表的某一行。語(yǔ)法制導(dǎo)的一個(gè)具體實(shí)現(xiàn)先對(duì)LR分析器的棧作一些改進(jìn)，加入語(yǔ)義值。STATEVALSYMTOP文法及其語(yǔ)義動(dòng)作(0)S’E

{printE.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).VAL}(4)En

{E.VAL:=LEXVAL}上述的語(yǔ)義動(dòng)作等于給出了計(jì)算由＋、*組成的整數(shù)算術(shù)式的過(guò)程。其相應(yīng)的程序段如下：(0)S’E

printVAL[TOP](1)EE(1)+E(2)

VAL[TOP]:=VAL[TOP]+VAL[TOP+2](2)EE(1)*E(2)

VAL[TOP]:=VAL[TOP]*VAL[TOP+2](3)E(E(1))

VAL[TOP]:=VAL[TOP+1](4)En

VAL[TOP]:=LEXVAL若把語(yǔ)義動(dòng)作改為產(chǎn)生中間代碼的動(dòng)作，就能隨著分析的進(jìn)展逐步生成中間代碼。屬性文法(attributegrammar)屬性文法(也稱(chēng)屬性翻譯文法)是Knuth在1968年首先提出的。它是在上下文無(wú)關(guān)文法的基礎(chǔ)上，為每個(gè)文法符號(hào)(終結(jié)符或非終結(jié)符)配備若干相關(guān)的“特性”（稱(chēng)為屬性）。這些屬性代表與文法符號(hào)相關(guān)信息，例如它的類(lèi)型、值、代碼序列、符號(hào)表內(nèi)容等等。屬性與變量一樣，可以進(jìn)行計(jì)算和傳遞。屬性加工的過(guò)程即是語(yǔ)義處理的過(guò)程。對(duì)于文法的每個(gè)產(chǎn)生式都配備了一組屬性的計(jì)算規(guī)則，稱(chēng)為語(yǔ)義規(guī)則。所謂屬性，其涉及的概念比較廣泛，常用以描述事物或人的特征、性質(zhì)，品質(zhì)等等。對(duì)編譯程序使用的語(yǔ)法樹(shù)的結(jié)點(diǎn)，可以用"類(lèi)型"、"值"或"存儲(chǔ)位置"來(lái)描述它。一個(gè)屬性文法包含一個(gè)上下文無(wú)關(guān)文法和一系列語(yǔ)義規(guī)則，這些語(yǔ)義規(guī)則附在文法的每個(gè)產(chǎn)生式上。所謂語(yǔ)法制導(dǎo)的翻譯指的是在語(yǔ)法分析過(guò)程中，完成這些語(yǔ)義規(guī)則描述的動(dòng)作，從而實(shí)現(xiàn)語(yǔ)義處理。屬性文法定義定義1：形式上講，屬性文法是一個(gè)三元組

:A=(G，V，F(xiàn))，其中：G:是一個(gè)上下文無(wú)關(guān)文法；V:有窮的屬性集,每個(gè)屬性與文法的一個(gè)終結(jié)符或非終結(jié)符相連,這些屬性代表與文法符號(hào)相關(guān)信息；F:關(guān)于屬性的屬性斷言或一組屬性的計(jì)算規(guī)則(稱(chēng)為語(yǔ)義規(guī)則)。斷言或語(yǔ)義規(guī)則與一個(gè)產(chǎn)生式相聯(lián),只引用該產(chǎn)生式左端或右端的終結(jié)符或非終結(jié)符相聯(lián)的屬性。定義2：一個(gè)屬性文法是一個(gè)三元組：A=(G,V,F),其中G--基礎(chǔ)文法（一個(gè)上下文無(wú)關(guān)文法）V--每個(gè)文法符號(hào)有一組屬性F--每個(gè)文法產(chǎn)生式A有一組形式為b:=f(c1,c2,…,ck)的語(yǔ)義規(guī)則，其中f是函數(shù)，b和c1,c2,…,ck是該產(chǎn)生式文法符號(hào)的屬性。屬性的類(lèi)型（從分析過(guò)程中屬性值的計(jì)算方法來(lái)分類(lèi)）： 1、綜合屬性（SynthesizedAttributes）：屬性值是分析樹(shù)中該結(jié)點(diǎn)的子結(jié)點(diǎn)的屬性值的函數(shù) 2、繼承屬性（InheritedAttributes）：屬性值是分析樹(shù)中該結(jié)點(diǎn)的父結(jié)點(diǎn)和/或兄弟結(jié)點(diǎn)的屬性值的函數(shù)對(duì)于產(chǎn)生式AX1X2…XnAX1X2Xn…計(jì)算A的綜合屬性,S(A):=f(I(X1),…,I(Xn))計(jì)算Xj的繼承屬性,T(Xj):=f(I(A),...,I(Xn))綜合屬性用于“自下而上”傳遞信息，繼承屬性用于“自上而下”傳遞信息例1綜合屬性的例子語(yǔ)義規(guī)則

L→EE→E1+TE→TT→T1*FT→FF→(E)F→digitPrint(E.val)

E.val:=E1.val+T.val

E.val:=T.val

T.val:=T1.valF.val

T.val:=F.valF.val:=E.valF.val:=digit.lexval產(chǎn)生式非終結(jié)符E、T及F都有一個(gè)綜合屬性val,符號(hào)digit僅有一個(gè)綜合屬性，它的值由詞法分析器提供。產(chǎn)生式L→

E語(yǔ)義規(guī)則是一個(gè)過(guò)程,打印E的值,也可以理解L的屬性是空的或虛的。綜合屬性的自下而上定值LE.val=19E.val=15T.val=4T.val=15F.val=4T.val=3F.val=3F.val=5digit.lexval=4digit.lexval=5digit.lexval=3+*3*5+4的帶注釋的分析樹(shù)設(shè)表達(dá)式為3＊5+4，則語(yǔ)義動(dòng)作打印數(shù)值19例2繼承屬性的例子產(chǎn)生式語(yǔ)義規(guī)則DTL

Tint

Treal

LL1,idLidL.in:=T.typeT.type=integerT.type:=real

L1.in:=L.in

addtype(id.entry,L.in)

addtype(id.entry,L.in)L.in屬性值置為該說(shuō)明語(yǔ)句指定的類(lèi)型，是繼承屬性。Addtype是一個(gè)過(guò)程，功能是把每個(gè)標(biāo)識(shí)符的類(lèi)型信息登陸在符號(hào)表的的相關(guān)項(xiàng)中。在表所示的語(yǔ)法制導(dǎo)翻譯中，非終結(jié)符D產(chǎn)生的聲明由關(guān)鍵字int或real及標(biāo)識(shí)符表組成，非終結(jié)符T有綜合屬性type，它的值由聲明中的關(guān)鍵字決定。

繼承屬性的自上而下定值Realid1,id2,id3DL.in=realL.in=realL.in=realT.type=realrealid2id1id3.，，產(chǎn)生式語(yǔ)義規(guī)則DTL

Tint

Treal

LL1,idLidL.in:=T.typeT.type=integerT.type:=real

L1.in:=L.in

addtype(id.entry,L.in)

addtype(id.entry,L.in)屬性依賴(lài)圖依賴(lài)圖是一個(gè)有向圖，用于描述分析樹(shù)中的屬性和屬性之間的相互依賴(lài)關(guān)系。依賴(lài)圖構(gòu)造算法：for語(yǔ)法樹(shù)中每一結(jié)點(diǎn)ndofor結(jié)點(diǎn)n的文法符號(hào)的每一個(gè)屬性ado為a在依賴(lài)圖中建立一個(gè)結(jié)點(diǎn)；for語(yǔ)法樹(shù)中每一個(gè)結(jié)點(diǎn)ndofor結(jié)點(diǎn)n所用產(chǎn)生式對(duì)應(yīng)的每一個(gè)語(yǔ)義規(guī)則b:=f(c1，c2，…，ck)dofori:=1tokdo從ci結(jié)點(diǎn)到b結(jié)點(diǎn)構(gòu)造一條有向邊；注:在構(gòu)造依賴(lài)圖之前,要為每一個(gè)過(guò)程調(diào)用的語(yǔ)義規(guī)則引入一個(gè)虛綜合屬性，即在依賴(lài)圖中構(gòu)造一個(gè)結(jié)點(diǎn)。這樣，若屬性b依賴(lài)于屬性c，則從c的結(jié)點(diǎn)有一條有向邊連接到b的結(jié)點(diǎn)。DintT,id3LLLid2id1,1

entry102entry3

entryin

98in

76in

54typeintid1,id2,id3的依賴(lài)圖產(chǎn)生式語(yǔ)義規(guī)則DTL

Tint

Treal

LL1,idLidL.in:=T.typeT.type=integerT.type:=real

L1.in:=L.in

addtype(id.entry,L.in)

addtype(id.entry,L.in)大部分的編譯器都不直接產(chǎn)生目標(biāo)代碼，雖然這是可以實(shí)現(xiàn)的，但是產(chǎn)生的代碼不是最優(yōu)的。因?yàn)檫@涉及到寄存器的分配問(wèn)題，在語(yǔ)義分析階段，很難有效地分配它們。中間代碼的必要性引入中間代碼的目的 1.方便生成目標(biāo)代碼； 2.便于優(yōu)化； 3.便于移植。波蘭邏輯學(xué)家盧卡西維奇（Lukasiewicz）發(fā)明的一種表示法。一般，若e1,e2為任意的后綴表達(dá)式，Θ為任意雙目運(yùn)算符，則用Θ作用于e1和e2所代表的結(jié)果用后綴式e1e2

Θ表示。推而廣之，

Θ為k目運(yùn)算符，則Θ作用于e1e2…ek的結(jié)果用e1e2…ek

Θ來(lái)表示。概念6.2逆波蘭表示法

a*(b+c)

abc+*(a+b)*(c+d)

ab+cd+*若用？表示if-then-else,則Ifathenifc-dthena+celsea*celse

a+b

acd-ac+ac*?ab+?示例后綴式求值使用一個(gè)棧（軟件?；蛘哂布＃﹣?lái)求值。求值過(guò)程：從左到右掃描后綴式，每碰到運(yùn)算量就把它推進(jìn)棧，每碰到k目運(yùn)算符就把它作用于棧頂?shù)膋個(gè)項(xiàng)，并用運(yùn)算結(jié)果來(lái)代替這k個(gè)項(xiàng)。ab+c*的求值（a=1,b=3,c=5)a進(jìn)棧13+5*b進(jìn)棧ab相加，移去兩項(xiàng)，和置于棧頂43+1=c進(jìn)棧棧頂兩項(xiàng)相乘，移去兩項(xiàng)，積置于棧頂5*4=20計(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ǔ)方式后綴式存放在一維數(shù)組POST[1..N]中，每個(gè)元素是運(yùn)算符或者分量（指向符號(hào)表）。

pjump轉(zhuǎn)到POST[p]e1e2pjlte1<e2時(shí)，轉(zhuǎn)到POST[p]epjez若e=0,轉(zhuǎn)到POST[p]Ifethenxelsey

ep1

jez

xp2

jump

p1:yp2:

轉(zhuǎn)移算符在數(shù)組POST中出現(xiàn)的后綴式ep1jezxp2jumpyp1p2下標(biāo)數(shù)組符號(hào)表exy后跟冒號(hào)的p1,p2實(shí)際上并不存儲(chǔ)語(yǔ)法制導(dǎo)生成后綴式產(chǎn)生式所帶的語(yǔ)義動(dòng)作，由以下模式描述。EE(1)opE(2)

{E.CODE:=E(1).CODE||E(2).CODE||op}/{printop}E(E(1)){E.CODE:=E(1).CODE}

/{}Eid{E.CODE:=id}

/{printid}Eaa+b*c的翻譯a+b*cabc*+移進(jìn)a輸出輸入用Eid歸約，printa移進(jìn)+移進(jìn)b用Eid歸約，printbEb移進(jìn)*移進(jìn)c用Eid歸約，printcEc用EEopE歸約，print*E1用EEopE歸約，print+結(jié)束，結(jié)果為abc*+E三元式的構(gòu)成：OPARG1ARG2ARG1和ARG2都是指示器，指向符號(hào)表的某項(xiàng)，或者三元式表自身的某項(xiàng)。OP通常用整數(shù)編碼。X:=A+B*C的三元式(1）*BC+A

(1):=X

(2)

6.3三元式和樹(shù)語(yǔ)法制導(dǎo)生成三元式的語(yǔ)義動(dòng)作EE(1)opE(2)

{

:=

TRIP(op,E(1).VAL,E(2).VAL}(2)E(E(1))

{E.VAL:=E(1).VAL}(3)E-E(1)

{E.VAL:=

(@,E(1).VAL,-}(4)Eid

{E.VAL:=(id)}指示器，指向符號(hào)表中某一項(xiàng)，或者三元式表中某一項(xiàng)語(yǔ)義過(guò)程，產(chǎn)生新的三元式，回送新三元式在三元式表中的位置對(duì)id代表的標(biāo)示符查找符號(hào)表以獲知在表中的位置的函數(shù)過(guò)程。E.VALTRIPENTRY兩個(gè)語(yǔ)義過(guò)程LOOKUP(NAME):對(duì)NAME查符號(hào)表。查到則返回入口值，否則返回NULL.(出錯(cuò)處理，調(diào)用FILLSYM)FILLSYM(NAME):在符號(hào)表中開(kāi)辟新項(xiàng)目，返回入口值。問(wèn)題三元式中指示器連接，不能更動(dòng)，不利于優(yōu)化。間接三元式用一張間接碼表輔以三元式表來(lái)表示中間代碼。X:=(A+B)*CY:=D↑(A+B)OpARG1ARG2(1)+AB(2)*(1)C(3):=X(2)(4)↑D(1)(5):=Y(4)(1)(2)(3)(1)(4)(5)間接碼表間接碼表體現(xiàn)了順序次序。在代碼優(yōu)化需要調(diào)整順序的時(shí)候，只需要重新安排間接碼表，無(wú)需改動(dòng)三元式表。同時(shí)，相同的三元式無(wú)需重復(fù)填入三元式表。語(yǔ)義動(dòng)作對(duì)于間接三元式表示，產(chǎn)生三元式表時(shí)，應(yīng)增添產(chǎn)生間接碼表的語(yǔ)義動(dòng)作。并且，在向三元式表填進(jìn)一個(gè)三元式之前，必須先查看一下此式是否已在其中，如已在其中，就無(wú)需再填如。樹(shù)用樹(shù)形結(jié)構(gòu)來(lái)表示一個(gè)表達(dá)式或者語(yǔ)句。簡(jiǎn)單變量或者常數(shù)的樹(shù)就是該變量或者常數(shù)自身。一般葉子表示運(yùn)算量，內(nèi)結(jié)點(diǎn)表示OP。如e1和e2的樹(shù)為T(mén)1和T2,那么，e1+e2、e1*e2和-e1的樹(shù)分別為：＋T2T1*T2T1-T1例A*(B+C)/DA*(B+C)/DEEEEEE規(guī)約過(guò)程樹(shù)BAC*+/DE語(yǔ)法制導(dǎo)產(chǎn)生樹(shù)EE(1)OPE(2)

{E.VAL:=(OP,E(1).VAL,E(2).VAL)}(2)E(E(1)){E.VAL:=E(1).VAL}(3)E-E(1)

{E.VAL:=(@,E(1).VAL)}(4)Ei{E.VAL:=(i)}函數(shù)過(guò)程，建立一個(gè)以O(shè)P為結(jié)點(diǎn)，E(1).VAL和E(2).VAL為左右枝的子樹(shù)，回送新子樹(shù)根的指針NODEUNARYLEAF與NODE相仿，但是它只有一個(gè)分枝。函數(shù)過(guò)程，建立一個(gè)以i.LEXVAL為標(biāo)志的結(jié)，并回送此結(jié)的地址，該結(jié)是個(gè)端末結(jié)（葉結(jié)）。OPARG1ARG2RESULT運(yùn)算量和運(yùn)算結(jié)果有時(shí)指用戶(hù)自定義的變量，有時(shí)指編譯程序引進(jìn)的臨時(shí)變量。如果OP是算術(shù)或者邏輯算符，則RESULT總是一個(gè)新引進(jìn)的臨時(shí)變量，存放中間結(jié)果。不加限制地使用臨時(shí)變量，在優(yōu)化時(shí)壓縮。OP:算符的整數(shù)碼ARG和RESULT:符號(hào)表入口或者臨時(shí)變量的整數(shù)碼RESULT為T(mén)i時(shí)的處理：可以填入符號(hào)表，通過(guò)符號(hào)表入口進(jìn)行引用，也可以不填，用某種整數(shù)編碼代表它們。6.4四元式A:==-B*(C+D)的四元式

@B_T1+CDT2*T1T2T3:=T3_A三元式和四元式的差異是表示式中有多少間接表示的問(wèn)題。三元式對(duì)于結(jié)果用指示器指向式子表示。四元式使用臨時(shí)變量，計(jì)算和使用的聯(lián)系不那么直接了，允許重排順序，利于優(yōu)化。下面要討論的是只含整型變量的簡(jiǎn)單賦值句的翻譯。它的文法描述：

Ai:=EEE+E|E*E|-E|(E)|i(5.1)

非終結(jié)符A代表“賦值句”。該文法是一二義性文法，但接受通常對(duì)于算符的結(jié)合性和優(yōu)先級(jí)的規(guī)定，可以克服。6.5簡(jiǎn)單算數(shù)表達(dá)式和賦值句到四元式的翻譯NEWTEMP:函數(shù)過(guò)程。每次調(diào)用時(shí)，它都回送一個(gè)代表新臨時(shí)變量名的整數(shù)碼作為函數(shù)值。ENTRY(i）：函數(shù)過(guò)程E.PLACE:和非終結(jié)符E相聯(lián)系的語(yǔ)義變量，表示存放E值的變量名在符號(hào)表的入口或者整數(shù)碼（若為臨時(shí)變量）。GEN(OP,ARG1,ARG2,RESULT):

語(yǔ)義過(guò)程，把四元式（OP,ARG1,ARG2,RESULT)填入四元式表。幾個(gè)語(yǔ)義變量和過(guò)程翻譯算法的語(yǔ)義動(dòng)作描述Ai:=E

{GEN(:=,E.PLACE,_,ENTRY(i))}EE(1)+E(2)

{E.PLACE:=NEWTEMP;

GEN(+,E(1).PLACE,E(2).PLACE,E.PLACE)}(3)EE(1)*E(2)

{E.PLACE:=NEWTEMP;

GEN(*,E(1).PLACE,E(2).PLACE,E.PLACE)}(4)E-E(1)

{E.PLACE:=NEWTEMP;

GEN(@,E(1).PLACE,_,E.PLACE)}(5)E(E(1))

{E.PLACE:=E(1).PLACE}(6)Ei

{E.PLACE:=ENTRY(i)}示例歸約樹(shù)A:=-B*(C+D)EEEEEEEA12345678輸入棧PLACE四元式A:=-B*(C+D)-B*(C+D)B*(C+D)*(C+D)*(C+D)i:=i:=-i:=-ii:=-Ei:=Ei:=E*i:=E*(i:=E*(ii:=E*(Ei:=E*(E+i:=E*(E+ii:=E*(E+E*(C+D)(C+D)C+D)+D)+D)D))))i:=E*(Ei:=E*(E)i:=E*Ei:=EA:=-B*(C+D)iAA_A__A__BA__BA_T1A_T1_A_T1__A_T1__CA_T1__CA_T1__C_A_T1__C_DA_T1__C_DA_T1__T2A_T__T2_A_T1_T2A_T3(@,B,_,T1)(+,C,D,T2)(*,T1,T2,T3)(:=,T3,_,A)類(lèi)型轉(zhuǎn)換前面假定了所有i都是整型，實(shí)際上，在一個(gè)表達(dá)式中可能出現(xiàn)各種不同類(lèi)型的變量和常數(shù)。編譯程序后者拒絕混合運(yùn)算，或者產(chǎn)生有關(guān)類(lèi)型轉(zhuǎn)換的指令。例如：令文法5.1允許混合類(lèi)型。那么，在進(jìn)行混合運(yùn)算時(shí)，首先要將整型量轉(zhuǎn)換為實(shí)型量。而要進(jìn)行轉(zhuǎn)換，其前提是對(duì)每一VN，必須有類(lèi)型信息語(yǔ)義量—E.MODE。因此，對(duì)應(yīng)的產(chǎn)生式要附加關(guān)于E.MODE的語(yǔ)義規(guī)則。語(yǔ)義規(guī)則：

{IFE(1).MODE=intANDE(2).MODE=intTHENE.MODE:=intELSEE.MODE:=r}語(yǔ)義動(dòng)作的增加，意味著語(yǔ)義子程序的修改，必要時(shí)能夠產(chǎn)生對(duì)運(yùn)算量進(jìn)行類(lèi)型轉(zhuǎn)換的四元式。

(itr,A1,_,T)將整型量A1轉(zhuǎn)換成實(shí)型量。

示例輸入串為X:=Y+I*JX,Y為實(shí)型，I,J為整型。四元式：

(*i,I,J,T1)(itr,T1,_,T2)(+r,Y,T2,T3)(:=,T3,_,X)運(yùn)算符要指出相稱(chēng)的類(lèi)型，說(shuō)明是定點(diǎn)還是浮點(diǎn)運(yùn)算*i關(guān)于產(chǎn)生式

EE(1)opE(2)

在上述語(yǔ)法規(guī)則中，非終結(jié)符E的語(yǔ)義值E.MODE必須保存在翻譯棧中。

如果運(yùn)算量類(lèi)型增多，語(yǔ)義子程序必須區(qū)別的情形很快增多，從而使語(yǔ)義子程序累贅不堪。6.6布爾表達(dá)式到四元式的翻譯布爾表達(dá)式(E)是由布爾算符(∧,∨,┐)作用于布爾變量或關(guān)系表達(dá)式而形成的。形式E1ropE2rop是關(guān)系符，E1和E2是算術(shù)式。文法：

EE∧E|E∨E|┐E|(E)|i|iropi設(shè)定

布爾算符的優(yōu)先順序：┐，∧，∨?！?，∨服從左結(jié)合。所有關(guān)系符的優(yōu)先級(jí)相同，高于任何布爾算符，低于任何算術(shù)算符。關(guān)系符不得結(jié)合，如A>B>C不合法。布爾表達(dá)式(E)在語(yǔ)言中的用途

求值X:=A∨B<D

條件控制WHILE

A∨B<D

DOS

IFA∨B<DTHENS1ELSES2布爾表達(dá)式的求值1通常算法，如同算術(shù)表達(dá)式求值一樣，一步步地計(jì)算各部分的值，進(jìn)而計(jì)算出整個(gè)表達(dá)式的值。2采用優(yōu)化措施A∨BifAthentrueelseBA∧BifAthenBelsefalse┐AifAthenfalseelsetrue說(shuō)明

上述兩種計(jì)算方法對(duì)于不包含布爾函數(shù)調(diào)用的式子是沒(méi)有什么差別的。僅當(dāng)遇到布爾函數(shù)調(diào)用，并且這種函數(shù)調(diào)用引起副作用時(shí)，上述兩種算法不等價(jià)。對(duì)于第一種方法而言，可以如同翻譯算術(shù)表達(dá)式一樣來(lái)翻譯布爾表達(dá)式。A∨B∧C=D

翻譯成=CDT1∧BT1T2∨AT2T3

第二種方法是本節(jié)主要內(nèi)容，下面將詳細(xì)討論。本節(jié)內(nèi)容

一.IF語(yǔ)句的四元式結(jié)構(gòu)二.翻譯的困難和解決辦法三.E的文法和語(yǔ)義子程序四.例例IF

A∨B<D

THENS1ELSES2E的結(jié)構(gòu)從整體上，E對(duì)外只能轉(zhuǎn)向兩個(gè)目標(biāo){E}轉(zhuǎn)向E為假時(shí)的目標(biāo)轉(zhuǎn)向E為真時(shí)的目標(biāo)(1)(jnz,A,_,5)(2)(j,_,_,3)(3)(j<,B,D,5)(4)(j,_,_,p+1)(5)(p)(p+1)(q){S1}(j,_,_,q){S2}{下一語(yǔ)句}一.IF語(yǔ)句的四元式結(jié)構(gòu)

1.困難

轉(zhuǎn)移的目標(biāo)在對(duì)它的應(yīng)用之后才出現(xiàn)；

(j,_,_,0)

E可以很復(fù)雜，上面的情況可以頻繁出現(xiàn)二.翻譯的困難和解決辦法(1)(jnz,A,_,5)(2)(j,_,_,3)(3)(j<,B,D,5)(4)(j,_,_,p+1)(5)(p)(p+1)(q){S1}(j,_,_,q){S2}{下一語(yǔ)句}二.翻譯的困難和解決辦法p()...q()...r()...t()pqrQ.front

2.解決辦法

一般地討論：凡是先有目標(biāo)應(yīng)用的出現(xiàn)，后有目標(biāo)的定義，如何處理？設(shè)p、q、r三條四元式均要轉(zhuǎn)向t四元式(1)隊(duì)列法Q.rearp(2)拉鏈-返填法p(_,_,_,0)..

q(_,_,_,_)q..

q(_,_,_,p)..r(_,_,_,_)r..r(_,_,_,q)..t(_,_,_,_)(2)拉鏈-返填法

p(_,_,_,0)..q(_,_,_,p)..q(_,_,_,t)..r(_,_,_,q)r..r(_,_,_,t)..t(_,_,_,_)qp

p(_,_,_,t)qp拉鏈法應(yīng)用到布爾表達(dá)式翻譯L1((L2(

L3(

..L4(

..L5(

..Li(..Lj(

..Ln(

LiE.TCLnE.FC)))))))))000000

00L5L2L1LjL4L3001.文法定義

G1E->E∧E∣E∨E|?E|(E)|i|iropi

G2E->E^E|E°E|?E|(E)|i|iropiE^->E∧E°->E∨三.布爾表達(dá)式文法定義及語(yǔ)義動(dòng)作2.語(yǔ)義動(dòng)作

用自下而上語(yǔ)法分析方法，語(yǔ)法制導(dǎo)生成A∨B<D的四元式四.例6.7控制語(yǔ)句的翻譯本小節(jié)討論無(wú)條件和條件語(yǔ)句的翻譯，只討論四元式的產(chǎn)生。本節(jié)內(nèi)容標(biāo)號(hào)和轉(zhuǎn)移語(yǔ)句條件語(yǔ)句分叉語(yǔ)句6.7.1標(biāo)號(hào)和轉(zhuǎn)移語(yǔ)句標(biāo)號(hào)的兩種使用方法L:SGotoL語(yǔ)言中允許標(biāo)號(hào)先定義后使用，也允許先使用后定義。(1)先定義L1:S1GotoL1…遇到L1:S1L1標(biāo)號(hào)…定義P1符號(hào)表遇到GotoL1(j,_,_,P1)名字類(lèi)型…定義否地址P1()…(2)先使用

q1

gotoL2…q2

GotoL2q3

L2:S2名字類(lèi)型…定義地址L2標(biāo)號(hào)…未q1遇到gotoL2,填符號(hào)表，“未定義”，把NXQ填入L2的地址部分，作為鏈頭。產(chǎn)生(j,_,_,0)q1(j,_,_,0)遇到gotoL2,查到未定義，取符號(hào)表中L2的地址q1填入四元式q2:(j,_,_,q1),將q2填入符號(hào)表?！璹2(j,_,_,q1)q2遇到L2:S2,就可以回填。q3q3q3一般而言，帶標(biāo)號(hào)語(yǔ)句產(chǎn)生式SlabelSlabeli:Labeli:的語(yǔ)義動(dòng)作1.若i所指的標(biāo)識(shí)符(假定為L(zhǎng))不在符號(hào)表中，則把它填入，置類(lèi)型為“標(biāo)號(hào)”，“定義否”為“已”，地址為NXQ。2,若L已在符號(hào)表中，但“類(lèi)型”不為“標(biāo)號(hào)”或者“定義否”為“已”，則報(bào)告出錯(cuò)。3.若L已在符號(hào)表中，則把標(biāo)志“未”改為“已”，然后，把地址欄中的鏈頭(記為q)取出，同時(shí)把NXQ填在其中，最后，執(zhí)行BACKPATCH(q,NXQ)。6.7.2條件語(yǔ)句1較為復(fù)雜的程序控制語(yǔ)句常常是嵌套的。S1后有一條無(wú)條件轉(zhuǎn)移指令，跳轉(zhuǎn)到本語(yǔ)句之后。這里，與上一節(jié)不同的是，在S2翻譯之后，也不能確定其跳轉(zhuǎn)地址，它要跨越S2,S3。所以，轉(zhuǎn)移地址的確定與語(yǔ)句所處的環(huán)境有關(guān)。ifE1THENifE2thenS1elseS2ELSES3解決辦法

令每個(gè)非終結(jié)符S(L)附帶一項(xiàng)語(yǔ)義值S.CHAIN，它指出一條鏈的頭，該鏈?zhǔn)撬衅诖g完S后回填目標(biāo)的四元式組成的。注意

回填目標(biāo)可能是{S}得下一條四元式，也可能不是。真正的回填，要在處理完S的外層后進(jìn)行?？紤]語(yǔ)句WHILEE(1)DOS(1)譯為代碼結(jié)構(gòu)E(1)的代碼S(1)的代碼假出口真出口由于語(yǔ)句的嵌套，WHILE翻譯完了也未必知道假出口的轉(zhuǎn)移目標(biāo)，所以作為S(1).CHAIN保留下來(lái),以便伺機(jī)回填。WhileE(1)doS(1)E(1).TCE(1).FCIFETHENELSES示例文法SifEthenS|ifEtheSelseS|whileEdoS|beginLend|ALL;S|S

(5.5)

S—語(yǔ)句L—語(yǔ)句串A—賦值句E—布爾表達(dá)式為了能及時(shí)回填有關(guān)四元式的轉(zhuǎn)移目標(biāo)，如同處理布爾表達(dá)式一樣，需要對(duì)文法(5.5)進(jìn)行改寫(xiě)。SCS|TPS|WdS|beginLend|ALLSS|SCifEthenTPCSelseWdWEdoWwhileLSL;(5.6)語(yǔ)義動(dòng)作CifEthen

{BACKPATCH(E.TC,NXQ);C.CHAIN:=E.FC}SCS(1){S.CHAIN:=MERG(C.CHAIN,S(1).CHAIN}TP

CS(1)else{q:=NXQ;GEN(j,_,_,0);BACKPATCH(C.CHAIN,NXQ);TP.CHAIN:=MERGE(S(1).CHAIN,q)}STPS(2){S.CHIAN:=MERG(TP.CHIAN,S(2).CHIAN}語(yǔ)義動(dòng)作Wwhile{W.QUAD:=NXQ}WdWEdo{BACKPATCH(E.TC,NXQ);Wd.CHAIN:=E.FC;Wd.QUAD:=W.QUAD}SWdS(1){BACHPATCH(S(1).CHAIN,Wd.QUAD);GEN(j,_,_,Wd.QUAD);S.CHAIN:=Wd.CHAIN}語(yǔ)義動(dòng)作LS{L.CHAIN:=S.CHAIN}LSL;{BACKPATCH(L.CHAIN,NXQ)}LLSS(1){L.CHAIN:=S(1).CHAIN}SbeginLend{S.CHAIN:=L.CHAIN}

SA{S.CHAIN:=0}空鏈IFETHENS(1)ELSES(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)CIFETHENTP

CS(1)ELSESTPS(2)q:(j,_,_,0)TP.CHAINBACKPATCH(C.CH,NXQ)MERG(S(1).CH,q)IFETHEN

WHILEE(1)DOS(1)

ELSES(2)

的示意圖IFETHENWHILEE(1)DOS(1)ELSES(2)WCWdS1TPSIFTHENWHILEE的代碼E.TCE.FCC.CHE(1)的代碼E(1).TE(1).FWd.CWd.Q=W.QS(1)的代碼S(1).CCIFETHEN{BACKPATCH(E.TC,NXQ);C.CHAIN:=E.FC}WWHILE{W.QUAD:=NXQ}Wd

WE(1)DO{BACKPATCH(E(1).TC,NXQ);Wd.CHAIN:=E(1).FCWd.quad:=W.QUAD}S1WdS(1){BACKPATCH(S(1).C,Wd.Q);GEN(j,_,_,Wd.Q);S1.C:=Wd.C}TP

CS1ELSE{q:=NXQ;GEN(j,_,_,0);BACKPATCH(C.CH,NXQ);TP.C:=MERG(S1.C,q);}ELSES(2)的代碼S(2).Cq:(j,_,_,0)TP.CSTPS(2)

{S.CH:=MERG(TP.CH,S(2).CH)}S.C(j,_,_,Wd.Q)S1.C語(yǔ)句翻譯完成，結(jié)果如圖所示例子WhileA<BDO

ifC<DthenX:=Y+ZWE(1)WdE(2)CS(1)S(2)SE(2).TC102(j<,C,D,0)E(2).FC102103103(j,_,_,0)103S(2).CHE(1).FCE(1).TC100101100(j<,A,B,0)101(j,_,_,0)104(+,Y,Z,T)WWHILE{W.QUAD:=NXQ}W.QUAD:=100E(1)

i(1)ropi(2){E(1).TC:=NXQ;E(1).FC:=NXQ+1;GEN(jrop,ENTRY(i(1)),ENTRY(i(2)),0);GEN(j,_,_,0);}Wd WE(1)DO{BACKPATCH(E(1).TC,NXQ);Wd.CHAIN:=E(1).FC;Wd.QUAD:=W.QUAD}E(2)i(1)ropi(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:=100101102CIFE(2)THEN{BACKPATCH(E(2).TC,NXQ);C.CHAIN:=E(2).FC}104103C.CHEi(1)+i(2){E.PLACE:=NEWTEMP;GEN(+,ENTRY(i(1)),ENTRY(i(2)),E.PALCE)}Ai:=E{GEN(:=,E.PALCE,_,ENTRY(i)}105(:=,T,_,X)S(2)

CS(1){S(2).CHAIN:=MERG(C.CHAIN,S(1).CHAIN)}SWdS(2){BACKPATCH(S(2).CHAIN,Wd.QUAD);GEN(j,_,_,Wd.QUAD);S.CHAIN:=Wd.CHAIN}100106(j,_,_,100)S.CH101WhileA<BDO

ifC<DthenX:=Y+Z語(yǔ)句翻譯完成0S(1).CH控制語(yǔ)句的翻譯1設(shè)計(jì)屬性文法，討論翻譯的一般語(yǔ)義規(guī)則。1產(chǎn)生標(biāo)志，被轉(zhuǎn)目標(biāo)，在S.code中出現(xiàn)S.Begin:=newlabelE.True:=newlabel如SwhileEdoS1的語(yǔ)義規(guī)則包含四部分：E.CODES1.CODEGotoS.begin…S.beginE.tE.f2“內(nèi)部的”/可隱藏標(biāo)志用S.Next及兩標(biāo)志表示。/S.next構(gòu)成E.F:=S.nextS1.next:=S.begin3S.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)有兩類(lèi)：一類(lèi)在S.code和S.next中；另一類(lèi)是可隱藏的，內(nèi)部的。2一遍掃描產(chǎn)生代碼，翻譯模式。SwhileM1EdoM2S2

Mξ{M.quad:=nextquad}SifEthenM1S1NelseM2S2

{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}CifEthenb(e.tc,NXQ)C.C:=E.FCTPCS1ELSEq:(j,_,_,_)b(c.c,NXQ)TP.C:=merg(S1.c,q);STPS2

S.C:=merg(TP.C,S2.C)6.7.3分叉語(yǔ)句

形式:caseEofC1:S1C2:S2…Cn-1:Sn-1otherwise:Snend語(yǔ)義：

E是一個(gè)表達(dá)式，稱(chēng)為選擇子。通常是一個(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í)行完了。實(shí)現(xiàn)方法1分叉只有10個(gè)左右時(shí)，翻譯成條件轉(zhuǎn)移語(yǔ)句。T:=E;L1:IFT≠C1GOTOL2S1;GOTONEXTL2:IFT≠C2GOTOL3S2;

GOTONEXT;L3:......Ln-1:IFT≠Cn-1GOTOLn

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

編譯時(shí)，對(duì)CASE構(gòu)造該表，有的表項(xiàng)為空。運(yùn)行時(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ù)組B[0:127],每個(gè)元素B[Ci]中存放著Si的地址。

S1頭S2頭Sn頭Sj頭Sn頭S127頭S1B[2]B[j]B[127]SjB[1]SnEC1C2分叉語(yǔ)句的翻譯下面討論一種便于語(yǔ)法分析制導(dǎo)實(shí)現(xiàn)的翻譯法。中間碼形式T:=E的中間碼GotoTESTL1:關(guān)于S1的中間碼GotoNEXTL2:關(guān)于S2的中間碼GotoNEXT…Ln-1:關(guān)于Sn-1的中間碼GotoNEXTLn:關(guān)于Sn的中間碼GotoNEXTTEST:IFT=C1GOTOL1;IFT=C2TOTOL2;

…

IFT=Cn-1GOTOLn-1

GotoLnNEXT:問(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)生GOTOTEST四元式，設(shè)置一個(gè)空隊(duì)列QUEUECi產(chǎn)生一個(gè)標(biāo)號(hào)Li,連同NXQ填入符號(hào)表，(Ci,Pi)進(jìn)入隊(duì)列QUEUESi產(chǎn)生{Si四元式}{GOTONEXT}otherwise產(chǎn)生標(biāo)號(hào)Ln,連同NXQ填入符號(hào)表END產(chǎn)生n個(gè)條件轉(zhuǎn)移語(yǔ)句的四元式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)化。6.8數(shù)組元素引用本小節(jié)討論數(shù)組元素的表達(dá)式和賦值句的翻譯。由于數(shù)組元素較簡(jiǎn)單變量有一定的特殊性，分幾個(gè)方面來(lái)介紹。本節(jié)內(nèi)容地址計(jì)算公式四元式中數(shù)組元素表達(dá)形式(數(shù)組元素引用和中間代碼）賦值語(yǔ)句中數(shù)組元素的翻譯6.8.1地址計(jì)算公式簡(jiǎn)化假定數(shù)組元素按行存放，每維下限都為1，每個(gè)元素只占一個(gè)字節(jié)。對(duì)數(shù)組元素A[i1,i2,…in]地址D的計(jì)算公式如下：D=CONSPART+VARPARTCONSPART=a–CC=d2d3…dn+d3d4…dn+…+dn+1VARPART=i1d2d3…dn+i2d3d4…dn+…+in-1dn+inaaddr(A[1,1,…1]),數(shù)組首址注意

CONSPART只依賴(lài)于數(shù)組各位的界限d和數(shù)組的首址a,與數(shù)組元素各維的下標(biāo)i1,i2,…,in無(wú)關(guān)。因此，對(duì)確定數(shù)組而言，計(jì)算數(shù)組元素的地址時(shí)，無(wú)需獨(dú)立計(jì)算CONSPART。VARPART是一個(gè)可變部分，它的值隨著各維下標(biāo)i1,i2,…,in的不同而不同。計(jì)算數(shù)組元素的地址主要計(jì)算VARPART。5.8.2數(shù)組元素引用和中間代碼這兒只討論確定數(shù)組(編譯時(shí)可靜態(tài)確定體積的數(shù)組，也稱(chēng)靜態(tài)數(shù)組)的翻譯。簡(jiǎn)單變量可以在符號(hào)表中查到它的地址，而數(shù)組元素卻不行，在符號(hào)表中只有它們的總代表——數(shù)組名的入口。名字特性地址A數(shù)組i1u1d1InundnnCtypeaA[1,1,…,1]A[1,1,…,2…例如，假定A是一個(gè)10×20的二維數(shù)組，各維的下限為1，每個(gè)元素占用一個(gè)機(jī)器字（令存儲(chǔ)器是以字編址的），數(shù)組的首地址，即A[1,1]的地址為a，那么，數(shù)組元素A[i,j]的地址為：a+(i-1)×20+(j-1)=(a-21)+(20i+j)產(chǎn)生兩組計(jì)算數(shù)組元素地址的四元式：對(duì)應(yīng)“數(shù)組元素引用”（引用其值）和“對(duì)數(shù)組元素賦值”有兩個(gè)相應(yīng)的四元式：“變址取數(shù)”和“變址存數(shù)”“變址取數(shù)”的四元式是：

(=[],T1[T],-,X)/*相當(dāng)于X:=T1[T]*/“變址存數(shù)”的四元式是：

([]=,X1,-,T1[T])/*相當(dāng)于T1[T]:=X*/例如，A是一個(gè)10×20的數(shù)組，即，d1=10,d2=20,那么，賦值句X:=A[I,J]的四元式為：

(*,I,20,T1)/*其中20指d2*/

(+,J,T1,T1)/*T1為VARPART*/

(-,A,21,T2)/*相當(dāng)于T2:=a-C*/

(=[],T2[T1],_,T3)/*T3:=T2[T1]*/

(:=,T3,_,X)例如，賦值句A[I+2,J+1]:=M+N的四元式序列為：

(+,I,2,T1)

(+,J,1,T2)

(*,T1,20,T3)

(+,T2,T3,T3)/*T3=VARPART*/

(-,A,21,T4)/*T4=CONSPART*/(+,M,N,T5)([]=,T5,_,T4[T3])/*T4[T3]:=T5*/6.8.3賦值語(yǔ)句中的數(shù)組元素翻譯關(guān)鍵問(wèn)題是下標(biāo)表達(dá)式的計(jì)算，進(jìn)而計(jì)算可變部分T。文法AV:=EVi[elist]|ielistelist,E|EEE+E|(E)|V所定義的賦值句A就是變量V后跟賦值號(hào):=和算術(shù)表達(dá)式E

如果數(shù)組元素為A[B,C[D,E[F,G]]],那么，在按上面的文法歸約下標(biāo)表達(dá)式串時(shí)，無(wú)法獲得數(shù)組的內(nèi)情向量，對(duì)每一維的下標(biāo)都需要保存下來(lái)。在該表達(dá)式中，就要保存B,D,F等中間結(jié)果，如果規(guī)模進(jìn)一步擴(kuò)大的話(huà)，要保存的中間量就會(huì)迅速增加，很是繁瑣。所以，要尋求能及時(shí)計(jì)算下標(biāo)的方法。定義要點(diǎn)1文法允許數(shù)組元素嵌套定義

，A[B,C[2]+1]。2為了在歸約時(shí)完成VARPART的計(jì)算，需要修改V的文法。這樣能夠在整個(gè)下標(biāo)串elist的翻譯過(guò)程中隨時(shí)知道數(shù)組名i的入口，獲取登記在符號(hào)表中的數(shù)組信息。Vi[elist]|iVelist]|ielistelist,E|Eelistelist,E|i[E回顧一下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)在要考慮的變量有兩類(lèi)，每個(gè)變量V有兩項(xiàng)語(yǔ)義值。V.PLACE

簡(jiǎn)單變量變量名的符號(hào)表入口下標(biāo)變量保存CONSPART的臨時(shí)變量的整數(shù)碼V.OFFSET

簡(jiǎn)單變量NULL(用于區(qū)分簡(jiǎn)單變量和下標(biāo)變量）下標(biāo)變量保存VARPART的臨時(shí)變量的整數(shù)碼語(yǔ)義動(dòng)作1AV:=E

{IF(V.OFFSET=NULL)THENGEN(:=,E.PLACE,_,V.PLACE)ELSEGEN([]=,E.PLACE,_,V.PLACE[V.OFFSET])}2EE(1)+E(2)

{T:=NEWTEMP;GEN(+,E(1).PLACE,E(2).PLACE,T);E.PLACE:=T}3E(E(1))

{E.PLACE:=E(1).PLACE}4EV{IF(V.OFFSET=NULL)THENE.PLACE:=V.PLACE;ELSEBEGINT:=NEWTEMP;GEN(=[],V.PLACE[OFFSET],_,T);E.PLACE:=T;END}5Velist]

{T:=NEWTEMP;GEN(-,elist.ARRAY,C,T);V.PLACE:=T;V.OFFSET:=elist.PLACE;}6Vi{V.PLACE:=ENTRY(i);V.OFFSET:=NULL;}7elistelist(1),E

{T:=NEWTEMP;k:=elist(1).DIM+1;dk:=LIMIT(elist(1).ARRAY,k);GEN(*,elist(1).PLACE,dk,T);GEN(+,E.PLACE,T,T);elist.ARRAY:=elist(1).ARRAY;elist.PLACE:=T;elist.DIM:=k;}8elisti[E

{elist.PLACE:=E.PLACE;elist.DIM:=1;elist.ARRAY:=ENTRY(i)}A是一個(gè)10*20的數(shù)組，A[I+2,J+1]:=M+N的翻譯(+,I,2,T1)(+,J,1,T2)(*,T1,20,T3)(+,T2,T3,T3)(-,A,21,T4)(+,M,N,T5)([]=,T5,_,T4[T3])[I+2EAielist,elistEI+2{T1:=TEMP;GEN(+,I,2,T1);E.PLACE:=T1}elistA[E{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);GEN(*,elist(1).PLACE,dk,T3);GEN(+,E.PLACE,T3,T3);elist.ARRAY:=elist(1).ARRAY;elist.PLACE:=T3;elist.DIM:=k}]VVelist]{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)THENGEN(:=,E.PLACE,_,V.PLACE);ELSEGEN([]=,E.PLACE,_,V.PALCE[V.OFFSET])}_CallS(A+B,Z)__S(X,Y)過(guò)程調(diào)用或者說(shuō)轉(zhuǎn)子，本質(zhì)上是把控制權(quán)轉(zhuǎn)移給子程序。

………………6.9過(guò)程調(diào)用幾個(gè)問(wèn)題轉(zhuǎn)移目標(biāo)返回地址參數(shù)傳遞一般方案主程序：實(shí)參約定單元子程序：約定單元形參訪(fǎng)問(wèn)形參關(guān)于地址傳遞一個(gè)簡(jiǎn)單方法，由指令攜帶參數(shù)地址，把實(shí)參地址統(tǒng)一放在轉(zhuǎn)子指令前。如CALLS(A+B,Z)翻成K-4:{T:=A+B}K-3:ParTK-2:ParZK-1:CallSK:…過(guò)程調(diào)用的四元式產(chǎn)生文法G：（1）SCALLi(arglist)（2）arglistarglist,E（3）arglistE困難：如何在處理參數(shù)串的過(guò)程之中記住每個(gè)實(shí)參的地址，以便最后將它們排列在轉(zhuǎn)子指令的前面。解決：第一個(gè)實(shí)參建立隊(duì)列，后面的循序記錄，要保持隊(duì)列頭。語(yǔ)義動(dòng)作1SCALLi(arglist){FOR隊(duì)列arglist.QUEUE的每一項(xiàng)PDOGEN(par,_,_,p);GEN(call,_,_,ENTRY(i))}2arglistarglist(1),E{把E.PLACE排在arglist(1).QUEUE的末端；arglist.QUEUE:=arglist(1).QUEUE}3arglistE{建立一個(gè)arglist.QUEUE,它只包含一項(xiàng)E.PLACE}例CALLS(A+B,Z)EA+B{E.PLACE:=NEWTEMP;GEN(+,A,B,E.PLACE)}ArglistE{建立一個(gè)arglist.QUEUE,包含E.PLACE}

EI{E.PLACE:=ENTRY(Z)}Arglistarglist(1),E{把Z排在T之后，即將E.PLACE置于arglist(1).QUEUE的末尾；Arglist.QUEUE:=arglist(1).QUEUE}

SCALLi(arglist){For隊(duì)列arglist.QUEUE的每一項(xiàng)PDOGEN(par,_,_,P);GEN(Call,_,_,ENTRY(i))}(+,ENTRY(A),ENTRY(B),T)(par,_,_,T)(par,_,_,Z)(Call,_,_,ENTRY(S))隊(duì)列arglist.QUEUETZ寫(xiě)法二義性X:=A(I,J)過(guò)程調(diào)用或者數(shù)組引用，兩者難以區(qū)分。而語(yǔ)法制導(dǎo)翻譯是按語(yǔ)法規(guī)則（產(chǎn)生式）進(jìn)行的，上下文無(wú)法區(qū)分，這就造成了翻譯的困難。解決方案查符號(hào)表詞法分析器在發(fā)送A之前先查表確定其特性規(guī)定數(shù)組用[]，避免沖突先說(shuō)明后引用，則使用兩邊掃描程序說(shuō)明語(yǔ)句如IntegerL,M,N;ARRAYA;語(yǔ)義動(dòng)作是把L,M,N,A登記到符號(hào)表中，并在相應(yīng)位置填入整型等性質(zhì)。6.10說(shuō)明語(yǔ)句的翻譯文法Dintegernamelist|realnamelistNamelistnamelist,i|i問(wèn)題該文法要求把完整的namelist讀完才能做語(yǔ)義動(dòng)作（在符號(hào)表中登記性質(zhì)