1、詞法分析和語(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)作。l語(yǔ)法制導(dǎo)翻譯語(yǔ)法制導(dǎo)翻譯l逆波蘭表示法逆波蘭表示法l三元式

2、和樹(shù)三元式和樹(shù)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(類(lèi)型），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)作，寫(xiě)在該產(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)展逐步生成中間代碼。屬性文法屬性文法(attribute grammar)屬性文法屬性文法( (也稱(chēng)屬性翻譯文法也稱(chēng)屬性翻譯文法) )是是KnuthK

5、nuth在在19681968年首年首先提出的。先提出的。它是在上下文無(wú)關(guān)文法的基礎(chǔ)上，為每個(gè)文法符它是在上下文無(wú)關(guān)文法的基礎(chǔ)上，為每個(gè)文法符號(hào)號(hào)( (終結(jié)符或非終結(jié)符終結(jié)符或非終結(jié)符) )配備若干相關(guān)的配備若干相關(guān)的“特性特性”（稱(chēng)（稱(chēng)為屬性）。為屬性）。這些屬性代表與文法符號(hào)相關(guān)信息，例如它的類(lèi)這些屬性代表與文法符號(hào)相關(guān)信息，例如它的類(lèi)型、值、代碼序列、符號(hào)表內(nèi)容等等。型、值、代碼序列、符號(hào)表內(nèi)容等等。屬性與變量一樣，可以進(jìn)行計(jì)算和傳遞。屬性加屬性與變量一樣，可以進(jìn)行計(jì)算和傳遞。屬性加工的過(guò)程即是語(yǔ)義處理的過(guò)程。工的過(guò)程即是語(yǔ)義處理的過(guò)程。對(duì)于文法的每個(gè)產(chǎn)生式都配備了一組屬性的計(jì)算對(duì)于文法的

6、每個(gè)產(chǎn)生式都配備了一組屬性的計(jì)算規(guī)則，稱(chēng)為規(guī)則，稱(chēng)為語(yǔ)義規(guī)則語(yǔ)義規(guī)則。 所謂屬性，其涉及的概念比較廣泛，常用以描述所謂屬性，其涉及的概念比較廣泛，常用以描述事物或人的特征、性質(zhì)，品質(zhì)等等。事物或人的特征、性質(zhì)，品質(zhì)等等。對(duì)編譯程序使用的語(yǔ)法樹(shù)的結(jié)點(diǎn)，可以用對(duì)編譯程序使用的語(yǔ)法樹(shù)的結(jié)點(diǎn)，可以用 類(lèi)型類(lèi)型 、 值值 或或 存儲(chǔ)位置存儲(chǔ)位置 來(lái)描述它。來(lái)描述它。 一個(gè)屬性文法包含一個(gè)上下文無(wú)關(guān)文法和一系列一個(gè)屬性文法包含一個(gè)上下文無(wú)關(guān)文法和一系列語(yǔ)義規(guī)則，這些語(yǔ)義規(guī)則附在文法的每個(gè)產(chǎn)生式上。語(yǔ)義規(guī)則，這些語(yǔ)義規(guī)則附在文法的每個(gè)產(chǎn)生式上。所謂語(yǔ)法制導(dǎo)的翻譯指的是在語(yǔ)法分析過(guò)程中，所謂語(yǔ)法制導(dǎo)的翻譯指的

7、是在語(yǔ)法分析過(guò)程中，完成這些語(yǔ)義規(guī)則描述的動(dòng)作，從而實(shí)現(xiàn)語(yǔ)義處理。完成這些語(yǔ)義規(guī)則描述的動(dòng)作，從而實(shí)現(xiàn)語(yǔ)義處理。屬性文法定義屬性文法定義定義定義1： 形式上講，屬性文法是一個(gè)三元組形式上講，屬性文法是一個(gè)三元組 :A=(G，V，F(xiàn))， 其中：其中：G:是一個(gè)上下文無(wú)關(guān)文法；是一個(gè)上下文無(wú)關(guān)文法；V:有窮的屬性集有窮的屬性集,每個(gè)屬性與文法的一個(gè)終結(jié)符或非終每個(gè)屬性與文法的一個(gè)終結(jié)符或非終結(jié)符相連結(jié)符相連,這些屬性代表與文法符號(hào)相關(guān)信息；這些屬性代表與文法符號(hào)相關(guān)信息；F:關(guān)于屬性的屬性斷言或一組屬性的計(jì)算規(guī)則關(guān)于屬性的屬性斷言或一組屬性的計(jì)算規(guī)則(稱(chēng)為語(yǔ)稱(chēng)為語(yǔ)義規(guī)則義規(guī)則) 。 斷言或語(yǔ)義規(guī)則

8、與一個(gè)產(chǎn)生式相聯(lián)斷言或語(yǔ)義規(guī)則與一個(gè)產(chǎn)生式相聯(lián),只引只引用該產(chǎn)生式左端或右端的終結(jié)符或非終結(jié)符相聯(lián)的用該產(chǎn)生式左端或右端的終結(jié)符或非終結(jié)符相聯(lián)的屬性。屬性。 定義定義2 2：一個(gè)屬性文法是一個(gè)三元組：一個(gè)屬性文法是一個(gè)三元組：A=(G,V,F ),A=(G,V,F ),其中其中uG -G -基礎(chǔ)文法（基礎(chǔ)文法（一個(gè)上下文無(wú)關(guān)文法一個(gè)上下文無(wú)關(guān)文法）uV -V -每個(gè)文法符號(hào)有一組屬性每個(gè)文法符號(hào)有一組屬性u(píng)F -F -每個(gè)文法產(chǎn)生式每個(gè)文法產(chǎn)生式A A有一組形式為有一組形式為b b:=:=f f( (c c1 1, ,c c2 2,c ck k) )的語(yǔ)義規(guī)則，其中的語(yǔ)義規(guī)則，其中f f 是函

9、數(shù)，是函數(shù)，b b和和c c1 1, ,c c2 2,c ck k是該產(chǎn)生式文法符號(hào)的屬性。是該產(chǎn)生式文法符號(hào)的屬性。 屬性的類(lèi)型（從分析過(guò)程中屬性值的計(jì)算方法來(lái)分類(lèi)）：1、綜合屬性綜合屬性（Synthesized Attributes）：屬性值是分析樹(shù)中該結(jié)點(diǎn)的子結(jié)點(diǎn)的屬性值的函數(shù) 2、繼承屬性繼承屬性（Inherited Attributes）：屬性值是分析樹(shù)中該結(jié)點(diǎn)的父結(jié)點(diǎn)和和/或或兄弟結(jié)點(diǎn)的屬性值的函數(shù)對(duì)于產(chǎn)生式 AX1 X2 XnA AX X1 1X X2 2X Xn n計(jì)算 A 的綜合屬性, S ( A ) : = f ( I ( X1 ) , , I ( Xn ) )計(jì)算 Xj

10、的繼承屬性, T ( Xj ) : = f ( I ( A ) , ., I ( Xn ) )v綜合屬性用于“自下而上”傳遞信息，繼承屬性用于“自上而下”傳遞信息例例1 1 綜合屬性的例子綜合屬性的例子語(yǔ) 義 規(guī) 則 L EE E1+TETT T1 * FTFF(E)FdigitPrint(E.val) E.val:=E1.val+T.val E.val:=T.val T.val:=T1.val F.val T.val:=F.valF.val:=E.valF.val:=digit.lexval產(chǎn) 生 式非終結(jié)符非終結(jié)符E、T及及F都有一個(gè)綜合屬性都有一個(gè)綜合屬性val,符號(hào)符號(hào)digit僅有僅

11、有一個(gè)綜合屬性一個(gè)綜合屬性，它，它的值由詞法分析器的值由詞法分析器提供。產(chǎn)生式提供。產(chǎn)生式L E語(yǔ)義規(guī)則是一個(gè)語(yǔ)義規(guī)則是一個(gè)過(guò)程過(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ù)例例2繼承屬性的例子繼承屬性的例子產(chǎn) 生 式語(yǔ) 義 規(guī) 則D TL T int T rea

12、l L L1,idL idL.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é)符在表所示的語(yǔ)法制導(dǎo)翻譯中，非終結(jié)符D D產(chǎn)生的聲明由產(chǎn)生的聲明由關(guān)鍵字關(guān)鍵字intint或或realreal及標(biāo)識(shí)符表組成，非終結(jié)符及標(biāo)識(shí)符表組成，非終結(jié)符T T有綜合屬有綜合屬性性typetype，它的值

13、由聲明中的關(guān)鍵字決定。，它的值由聲明中的關(guān)鍵字決定。 繼承屬性的自上而下定值繼承屬性的自上而下定值Real id1,id2,id3DL.in= realL.in= realL.in= realT.type=realrealid2id1id3.，產(chǎn) 生 式語(yǔ) 義 規(guī) 則D TL T int T real L L1,idL idL.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)圖依賴(lài)圖是一個(gè)有向圖，用于描述分析樹(shù)中的屬性和屬性之依賴(lài)圖是一個(gè)

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

15、一個(gè)結(jié)點(diǎn)。這樣，若屬性若屬性b依賴(lài)于屬性依賴(lài)于屬性c，則從，則從c的結(jié)點(diǎn)有一條有向邊連接到的結(jié)點(diǎn)有一條有向邊連接到b的結(jié)點(diǎn)的結(jié)點(diǎn)。D intT,id3LLLid2id1,1 entry102 entry3 entryin 98in 76in 54 typeint id1, id2, id3的依賴(lài)圖的依賴(lài)圖產(chǎn) 生 式語(yǔ) 義 規(guī) 則D TL T int T real L L1,idL idL.in:=T.typeT.type=integerT.type:=real L1.in:=L.in addtype(id.entry,L.in) addtype(id.entry,L.in)大部分的編譯器都不直

16、接產(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)算符，則作用于e1e2ek的結(jié)果用e1e2ek 來(lái)表示。概念l a * ( b + c ) abc+*l(a + b)*(c + d) ab + cd +*若用？表示if-then-

17、else,則lIf a then if c-d then a+c else a*c else a+b a cd- 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)。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.這種表示法要求在

18、任何情況下都要把x,y都計(jì)算出來(lái)，盡管只用到其中一個(gè)。而且，如果運(yùn)算量無(wú)定義或者有副作用，則后綴表示法不僅無(wú)效，而且可能是錯(cuò)誤的。引入標(biāo)號(hào)，在后綴式中加入條件轉(zhuǎn)移，無(wú)條件轉(zhuǎn)移算符。存儲(chǔ)方式后綴式存放在一維數(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

19、 A then true else B AB if A then B else false A if A then false else true說(shuō)明 上述兩種計(jì)算方法對(duì)于不包含布爾函數(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的

20、結(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,_,_,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)(

21、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)|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 iG

22、ENjE TCETC E FCEFCEiEirop iEEEE (1)(1)1).:.;.:.E TCEFC E FCETC(1)(1)( 2 )( 2 )(1)0(1)( 2 )0( 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,)(,(;

23、1.;.) 1)1()1(1JGENiEntryjnzGENNXQFCENXQTCEiE）（.:.);,.()2)1(0)1()1(0TCETCENXQFCEBACKPATCHEE)0 ,();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

24、).,.()2(0TCETCEMERG).,.(:.;.:.)4)2(0)2()2(0TCETCEMERGTCEFCEFCEEEE 本小節(jié)討論無(wú)條件和條件語(yǔ)句的翻譯，只討論四元式的產(chǎn)生。本節(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)名字類(lèi)型定義否地址P1 ( )(2) (2) 先使用先使用 q1q1 goto L

25、2goto L2 q2 q2 Goto L2Goto L2 q3 q3 L2 : S2L2 : S2名字類(lèi)型定義地址L2標(biāo)號(hào) 未 q1遇到goto L2, 填符號(hào)表，“未定義”，把NXQ填入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)

26、)不在符號(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)。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 S2ELS

27、E S3 解決辦法 令每個(gè)非終結(jié)符S(L)附帶一項(xiàng)語(yǔ)義值S.CHAIN，它指出一條鏈的頭，該鏈?zhǔn)撬衅诖g完S后回填目標(biāo)的四元式組成的。注意 回填目標(biāo)可能是S得下一條四元式，也可能不是。真正的回填，要在處理完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 el

28、se 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)，如同處理布爾表達(dá)式一樣，需要對(duì)文法(5.5)進(jìn)行改寫(xiě)。 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.

29、CHAIN, S(1).CHAINTP C S(1) else q := NXQ; GEN(j, _, _, 0); BACKPATCH(C.CHAIN,NXQ); TP.CHAIN := 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

30、, _, _, Wd.QUAD); S.CHAIN := Wd.CHAIN語(yǔ)義動(dòng)作L S L.CHAIN := S.CHAINLS L; BACKPATCH(L.CHAIN,NXQ) 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(

31、2).CH)C IF E THENTP C S(1) ELSES TP S(2)q: ( j, _, _, 0)TP.CHAINBACKPATCH(C.CH,NXQ)MERG(S(1).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

32、 := E.FC W WHILEW.QUAD := NXQWd W E(1) DOBACKPATCH(E(1).TC,NXQ); Wd.CHAIN := E(1).FC Wd.quad := 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(

33、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(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;G

34、EN(jrop,ENTRY(i(1),ENTRY(i(2),0);GEN(j,_,_,0);Wd W E(1) DOBACKPATCH(E(1).TC,NXQ); Wd.CHAIN := 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

35、i(1)+i(2) E.PLACE := NEWTEMP; GEN(+,ENTRY(i(1),ENTRY(i(2),E.PALCE)A i:=E GEN(:=,E.PALCE,_,ENTRY(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

36、語(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 := newlabel如 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 |

37、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)生代碼，翻譯模式。S while 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,q);S TP S2 S.C := merg(TP.C, S2.C) 形式: case E of C1: S1 C2: S2 Cn-1: