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

1、第八章第八章 語(yǔ)法制導(dǎo)翻譯與中間代碼生成語(yǔ)法制導(dǎo)翻譯與中間代碼生成u語(yǔ)言的結(jié)構(gòu)可形式的用一組產(chǎn)生式(BNF)描述，這使得語(yǔ)言的詞法分析器和語(yǔ)法分析器的自動(dòng)生成成為可能。u本章：語(yǔ)義的形式化困難，語(yǔ)義處理復(fù)雜，難以形式化 語(yǔ)義處理主要包括靜態(tài)語(yǔ)義（包括類(lèi)型規(guī)則和作用域/可見(jiàn)性規(guī)則）檢查和翻譯成中間代碼； 對(duì)屬性和屬性文法作一介紹；語(yǔ)法制導(dǎo)翻譯：一種接近形式化的系統(tǒng)；典型的中間代碼；語(yǔ)義子程序設(shè)計(jì)；各種基本語(yǔ)言成分的自下而上分析的語(yǔ)法制導(dǎo)翻譯。8.1 屬性和屬性文法8.1.1屬性文法屬性(attribute)是編程語(yǔ)言結(jié)構(gòu)的任意特性，是一個(gè)語(yǔ)法概念的特征描述。屬性是想表示的任何東西，典型的屬性有：

2、變量的數(shù)據(jù)類(lèi)型、表達(dá)式的值、存儲(chǔ)器中變量的位置、程序的目標(biāo)代碼、數(shù)的有效位數(shù)等。屬性文法(attribute grammar)：將屬性關(guān)系等式附加在相應(yīng)文法規(guī)則上的文法屬性的表示：若a是文法符號(hào)X的一個(gè)屬性，則記作X.a。a稱(chēng)為屬性變量。屬性關(guān)系等式與采用何種語(yǔ)法分析方式無(wú)關(guān)，但是屬性的計(jì)算次序受分析方法所限定的分析樹(shù)結(jié)點(diǎn)的建立次序的約束。例8.1 考慮下面簡(jiǎn)單的無(wú)符號(hào)數(shù)文法： numbernumber digit | digitdigit0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9屬性文法：文法規(guī)則語(yǔ)義規(guī)則number(1)number(2) digit num

3、ber(1).val=number(2).val*10 + digit.valnumberdigit number.val=digit.valdigit0 digit.val=0digit9 digit.val=9屬性計(jì)算依賴(lài)于分析樹(shù)或語(yǔ)法樹(shù)明確或不明確的遍歷：例8.2 考慮下列類(lèi)似C語(yǔ)言中變量聲明的簡(jiǎn)單文法：decltype var-listtypeint | floatvar-listid, var-list | id屬性文法：文法規(guī)則語(yǔ)義規(guī)則decltype var-list var-list.dtype=type.dtypetypeint type.dtype=integertypef

4、loat type.dtype=realvar-list(1)id ,var-list(2) id.dtype=var-list(1).dtype var-list(2).dtype=var-list(1).dtypevar-listid id.dtype=var-list.dtype字符串float x,y的語(yǔ)法樹(shù)，顯示屬性文法指定的dtype屬性：輔助函數(shù)mkOpNode和mkNumNode：nmkOpNode構(gòu)成一個(gè)新的樹(shù)結(jié)點(diǎn)；nmkNumNode構(gòu)成一個(gè)葉子結(jié)點(diǎn)。 例8.3 考慮下列簡(jiǎn)單的整數(shù)算術(shù)表達(dá)式文法：expexp+term | exp-term | termtermterm*f

5、actor | factorfactor(exp)| numberexp(或term或factor)的基本屬性是它的數(shù)字值，寫(xiě)作val。屬性文法簡(jiǎn)單整型算術(shù)表達(dá)式的抽象語(yǔ)法樹(shù)的屬性文法： 文法規(guī)則 語(yǔ)義規(guī)則exp(1)exp(2)+termexp(1).tree=mkOpNode(+,exp(2).tree,term.tree)exp(1)exp(2)-termexp(1).tree=mkOpNode(-,exp(2).tree,term.tree)exptermexp.tree=term.treeterm(1)term(2)*factor term(1).tree=mkOpNode(*,te

6、rm(2).tree,factor.tree)termfactorterm.tree=factor.treefactor(exp)factor.tree=exp.treefactornumberfactor.tree=mkNumNode(number.lexval)8.1.2 綜合和繼承屬性綜合和繼承屬性 n綜合屬性(synthesized attribute) ：若產(chǎn)生式左部符號(hào)A的屬性值是通過(guò)右部符號(hào)的屬性值或A的其它屬性值得來(lái)的nS屬性文法：所有的屬性都是綜合的任一右部符號(hào)的屬性計(jì)算與它所在的產(chǎn)生式無(wú)關(guān)（從語(yǔ)法樹(shù)看，任一結(jié)點(diǎn)的屬性?xún)H依賴(lài)它的下層或它自己的其它屬性，換句話說(shuō)不依賴(lài)上層和同層

7、其它結(jié)點(diǎn)的屬性）nS屬性文法的屬性值可以通過(guò)對(duì)樹(shù)進(jìn)行簡(jiǎn)單后序遍歷來(lái)計(jì)算：void PostEval(treenode T) for each child C of T do PostEval(C); compute all synthesized attributes of T;n并不是所有的屬性都是綜合的。所有的非綜合屬性稱(chēng)為繼承(inherited)屬性。例8.4 對(duì)例8.1中的文法進(jìn)行修改，數(shù)可以是八進(jìn)制或十進(jìn)制的based-numnum basecharbasecharo | dnumnum digit | digitdigit0 | 1 | 2 | 3 | 4 | 5 | 6 | 7

8、 | 8 | 9此時(shí)，num和digit均需要一個(gè)新的屬性base用來(lái)計(jì)算屬性val。 文法規(guī)則語(yǔ)義規(guī)則based-numnum basecharbased-num.val=num.valnum.base=basechar.basebasecharobasechar.base=8basechardbasechar.base=10num(1)num(2) digitnum(1).val=if digit.val=error or num(2).val=error then errorelse num(2).val*num(1).base+digit.val num(2).base=num(1).

9、base digit.base=num(1).basenumdigit num.val=digit.val digit.base=num.basedigit0digit.val=0digit7digit.val=7digit8digit.val=if digit.base=8 then error else 8digit9digit.val=if digit.base=8 then error else 9345o的語(yǔ)法樹(shù)：n與綜合屬性不同，子孫繼承屬性計(jì)算的順序是重要的，因?yàn)樵谧訉O的屬性中繼承屬性可能有依賴(lài)關(guān)系。n此文法有兩個(gè)屬性，綜合屬性val、繼承屬性base；n先計(jì)算base，再用后序

10、遍歷計(jì)算val。綜上所述，屬性文法是帶有下列說(shuō)明的翻譯文法：1每個(gè)終結(jié)符、非終結(jié)符都有一個(gè)與其相關(guān)的屬性的有窮集。2每一個(gè)非終結(jié)符號(hào)的屬性可分為兩類(lèi)：繼承的或綜合的。3在分析樹(shù)中，一個(gè)結(jié)點(diǎn)的綜合屬性值是從其子結(jié)點(diǎn)和它本身的屬性值計(jì)算出來(lái)的；而一個(gè)結(jié)點(diǎn)的繼承屬性值是由該結(jié)點(diǎn)兄第結(jié)點(diǎn)和父結(jié)點(diǎn)和它本身的屬性值計(jì)算出來(lái)的。屬性計(jì)算方法n樹(shù)遍歷的屬性計(jì)算方法若語(yǔ)法樹(shù)已經(jīng)建立起了，并且樹(shù)中已帶有開(kāi)始符號(hào)的繼承屬性和終結(jié)符的綜合屬性。然后以某種次序遍歷語(yǔ)法樹(shù)，直至計(jì)算出所有屬性。有時(shí)可能需要進(jìn)行多遍遍歷。 n一遍掃描的處理方法 在很多情況下，翻譯可以在掃描分析過(guò)程中完成，不需要構(gòu)造出明確的語(yǔ)法分析樹(shù)。L屬性

11、翻譯的語(yǔ)法制導(dǎo)翻譯方案包含了所有可以在語(yǔ)法分析過(guò)程中完成的翻譯方案。n一遍掃描的處理方法與下面兩個(gè)因素密切相關(guān)： （1）所采用的語(yǔ)法分析方法（不同方法對(duì)屬性計(jì)算的方便性不同） （2）屬性的計(jì)算次序。 8.1.3 屬性的變換屬性的變換n屬性計(jì)算主要在語(yǔ)義分析階段進(jìn)行，但語(yǔ)義分析的部分工作可以放到詞法/語(yǔ)法分析階段進(jìn)行。如，當(dāng)一個(gè)名字填入符號(hào)表時(shí)，就可以檢查這個(gè)名字是否只定義了一次。n如果語(yǔ)義分析可以推遲到所有的語(yǔ)法分析完成之后進(jìn)行，那么實(shí)現(xiàn)語(yǔ)義分析的任務(wù)就相當(dāng)容易，其本質(zhì)上是對(duì)語(yǔ)法樹(shù)的一序列的遍歷過(guò)程，同時(shí)在遍歷中每次遇到結(jié)點(diǎn)時(shí)進(jìn)行計(jì)算，但也這就意味著編譯程序必須是多遍的。n另一方面，如果要求編

12、譯程序在一遍中完成所有的操作(包括代碼生成)，那么語(yǔ)義分析的實(shí)現(xiàn)就會(huì)變成尋找計(jì)算語(yǔ)義信息的正確順序和方法的特別的過(guò)程。n可能會(huì)有這樣的情況，不改變語(yǔ)言合法的字符串而修改文法會(huì)使屬性的計(jì)算更簡(jiǎn)單或更復(fù)雜。n定理：(Knuth 1968)給定一個(gè)屬性文法，通過(guò)適當(dāng)?shù)匦薷奈姆ǎ鵁o(wú)須改變文法的語(yǔ)言，所有的繼承屬性可以改變成綜合屬性。n雖然重寫(xiě)文法使之僅使用綜合屬性總是可能的，但通常是使用帶繼承屬性的屬性文法更自然些。屬性等式與使用什么樣的語(yǔ)法分析方法以及分析算法的具體實(shí)現(xiàn)無(wú)關(guān)。在下面的語(yǔ)法制導(dǎo)翻譯中，我們將會(huì)看到屬性文法的作用在于它能指導(dǎo)我們寫(xiě)出更加清晰、簡(jiǎn)練、不易出錯(cuò)的的語(yǔ)義分析子程序，同時(shí)子程序

13、也更加易懂。例8.5 再次考慮變量聲明的簡(jiǎn)單文法：decltype var-listtypeint | floatvar-listid, var-list | id可將這個(gè)文法改寫(xiě)為：declvar-list idvar-listvar-list id, | typetypeint | floatint a, b, c8.2 屬性文法和語(yǔ)法制導(dǎo)翻譯n語(yǔ)義分析包括構(gòu)造符號(hào)表、記錄聲明中建立的名字的含義、在表達(dá)式和語(yǔ)句中進(jìn)行類(lèi)型檢查等。 n類(lèi)型檢查應(yīng)驗(yàn)證一種結(jié)構(gòu)的類(lèi)型是否匹配其上下文的要求。n如何把源程序改造成某種形式的中間語(yǔ)言程序？ 在語(yǔ)法分析中，有相當(dāng)成熟的理論和算法：使用 BNF中的上下文無(wú)

14、關(guān)文法描述語(yǔ)言的語(yǔ)法結(jié)構(gòu)，并用自頂向下或自底向上的分析算法實(shí)現(xiàn)語(yǔ)法分析。 n語(yǔ)義分析目前還沒(méi)有給出一種公認(rèn)的形式化描述系統(tǒng)，只能說(shuō)有一些成功的系統(tǒng)和方法，其中比較接近形式化的一種方法是語(yǔ)法制導(dǎo)翻譯法。 n所謂語(yǔ)法制導(dǎo)翻譯，直觀上說(shuō)就是為每個(gè)產(chǎn)生式配上一個(gè)翻譯子程序（語(yǔ)義子程序），并且在語(yǔ)法分析的同時(shí)執(zhí)行它。n語(yǔ)義子程序的功能包括改變編譯程序某些變量的值、查填各種符號(hào)表、診察與報(bào)告源程序錯(cuò)誤、產(chǎn)生中間代碼等。n語(yǔ)義子程序是給產(chǎn)生式賦予具體意義的手段，一方面規(guī)定了產(chǎn)生式產(chǎn)生的符號(hào)串的意義，另一方面又按照這種意義規(guī)定了生成代碼應(yīng)做的基本動(dòng)作。例如，定義二進(jìn)制算術(shù)表達(dá)式E的”值”的語(yǔ)義： 1. EE(

15、1)+E(2)E.VAL:=E(1).VAL+E(2).VAL 2. E0E.VAL:=0 3. E1E.VAL:=1對(duì)輸入串1+1+0+1，一旦分析器認(rèn)出它是一個(gè)句子時(shí)，它的值“11”也就被語(yǔ)義子程序計(jì)算出來(lái)了。 n語(yǔ)法制導(dǎo)翻譯既可以用來(lái)產(chǎn)生中間代碼，也可以用來(lái)產(chǎn)生目標(biāo)指令，甚至可用來(lái)對(duì)輸入串進(jìn)行解釋執(zhí)行。 n總之，按語(yǔ)法制導(dǎo)翻譯的方法來(lái)實(shí)現(xiàn)語(yǔ)言的翻譯，就是要根據(jù)語(yǔ)言的文法，按照各產(chǎn)生式的語(yǔ)義，分別編寫(xiě)出完成這些操作的語(yǔ)義子程序，并把它們插入到各產(chǎn)生式右部的適當(dāng)位置上，從而形成翻譯文法。這樣，在語(yǔ)法分析過(guò)程中，就能在分析符號(hào)串的同時(shí)，執(zhí)行由翻譯文法所確定的、與該符號(hào)串相對(duì)應(yīng)的動(dòng)作序列，即按動(dòng)

16、作符號(hào)的順序調(diào)用相應(yīng)的子程序完成翻譯任務(wù)。n語(yǔ)義子程序的設(shè)計(jì)：以屬性文法為基礎(chǔ)，將屬性等式轉(zhuǎn)化為計(jì)算規(guī)則（屬性等式本身指示了屬性計(jì)算時(shí)的順序約束）。對(duì)產(chǎn)生式 X0X1 X2 . . . Xn 的屬性等式Xi.aj=fij(X0.a1，X0.ak，X1.a1，X1.ak，Xn.a1，Xn.ak)等式右邊出現(xiàn)的所有屬性值必須已經(jīng)存在。但在屬性文法的說(shuō)明中，這個(gè)要求可能被忽略，可以將等式寫(xiě)成任意順序而不會(huì)影響正確性。實(shí)現(xiàn)屬性文法的關(guān)鍵在于為屬性的計(jì)算尋找一個(gè)順序，以確保當(dāng)每次進(jìn)行計(jì)算時(shí)使用的所有屬性值都是有效的。文法規(guī)則 語(yǔ)義規(guī)則declvar-list id id.dtype=var-list.d

17、typevar-list(1)var-list(2) id, id.dtype=var-list(2).dtype var-list(1).dtype=var-list(2).dtypevar-listtype var-list.dtype=type.dtypetypeint type.dtype=integertypefloat type.dtype=real仍以簡(jiǎn)單說(shuō)明句的屬性文法為例其語(yǔ)義動(dòng)作就是在符號(hào)表中登記上這些名字的有關(guān)性質(zhì)。按此屬性文法，就可把所說(shuō)明的性質(zhì)及時(shí)告訴每個(gè)名字id?；蛘哒f(shuō)每當(dāng)讀進(jìn)一個(gè)標(biāo)識(shí)符時(shí)，就可以把它的性質(zhì)登記在符號(hào)表中。 幾個(gè)語(yǔ)義變量和語(yǔ)義過(guò)程：nD.dtypen

18、FILL(p, A)：把性質(zhì)A填進(jìn)p所指符號(hào)表入口的有關(guān)欄中。nENTRY(i)：查詢(xún)和取得i所代表的標(biāo)識(shí)符在符號(hào)表中的入口n各產(chǎn)生式語(yǔ)義動(dòng)作：1declvar-list idFILL(ENTRY(id), var-list.dtype); 2var-list(1)var-list(2) id,FILL(ENTRY(id), var-list(2).dtype); var-list(1).dtype=var-list(2).dtype3var-listtypevar-list.dtype=type.dtype4typeinttype.dtype=integer6typefloattype.dt

19、ype=real可見(jiàn)，語(yǔ)法制導(dǎo)翻譯就是屬性文法的一種實(shí)現(xiàn)方式。 nS屬性文法的語(yǔ)法制導(dǎo)翻譯通?？山柚贚R分析器實(shí)現(xiàn)，在對(duì)輸入串進(jìn)行語(yǔ)法分析的同時(shí)對(duì)屬性進(jìn)行計(jì)算。n對(duì)LR分析程序，可以通過(guò)擴(kuò)充分析棧，修改總控程序，使之適合于主要處理S屬性文法。 對(duì)綜合屬性，可設(shè)置一個(gè)值棧進(jìn)行存儲(chǔ)，值棧將和分析棧并行操作，每當(dāng)在分析棧出現(xiàn)移進(jìn)或規(guī)約時(shí)，就根據(jù)屬性等式來(lái)計(jì)算新值。 以簡(jiǎn)單算術(shù)表達(dá)式的二義性版本為例：expexp+exp | exp*exp | (exp) | number文法規(guī)則語(yǔ)義規(guī)則exp(1)exp(2) + exp(3) exp(1).val = exp(2).val + exp(3).v

20、alexp(1)exp(2) * exp(3) exp(1).val = exp(2).val * exp(3).valexp(1)(exp(2) exp(1).val = exp(2).valexpnumber exp.val = number.valstatevalZZ.zYY.y.XX.xtop在LR分析中，表達(dá)式3*4+5的語(yǔ)法和語(yǔ)義動(dòng)作： 分析棧 輸入語(yǔ)法動(dòng)作值棧 語(yǔ)義動(dòng)作1 # 3*4+5# 移進(jìn)#2 #n *4+5# 規(guī)約En #3 E.val=n.val3 #E *4+5# 移進(jìn)#34 #E* 4+5# 移進(jìn)#3*5 #E*n +5# 規(guī)約En#3*4 E.val=n.val6

21、 #E*E +5# 規(guī)約EE*E #3*4 E(1).val=E(2).val+E(3).val 7 #E +5# 移進(jìn)#128 #E+ 5# 移進(jìn)#12+9 #E+n # 規(guī)約En#12+5 E.val=n.val10 #E+E # 規(guī)約EE+E#12+5 E(1).val=E(2).val+E(3).val 11 #E#178.3 中間代碼的形式n復(fù)雜性程度介于源程序語(yǔ)言和機(jī)器語(yǔ)言之間的語(yǔ)言。n引入目的：為了使編譯程序結(jié)構(gòu)在邏輯上更為簡(jiǎn)單明確, 便于編譯系統(tǒng)的建立和編譯系統(tǒng)的移植，特別是為了使目標(biāo)代碼的優(yōu)化比較容易實(shí)現(xiàn)并獨(dú)立于機(jī)器進(jìn)行。 n中間代碼生成是通過(guò)遍歷由于法分析器建立的語(yǔ)法樹(shù)實(shí)現(xiàn)

22、的。遍歷語(yǔ)法樹(shù)的操作可以和建立語(yǔ)法樹(shù)的操作同時(shí)進(jìn)行，也可以在語(yǔ)法樹(shù)建立之后再遍歷一次語(yǔ)法樹(shù)，前一種叫語(yǔ)法制導(dǎo)翻譯。n常見(jiàn)形式：逆波蘭記號(hào)、樹(shù)結(jié)構(gòu)表示、三元式、四元式等。逆波蘭式逆波蘭式是波蘭邏輯學(xué)家盧卡西維奇發(fā)明的一種表示表達(dá)式的方法，用于說(shuō)明算術(shù)表達(dá)式：不使用括號(hào)，運(yùn)算量在前，算符在后，故也稱(chēng)為后綴式。1簡(jiǎn)單表達(dá)式的逆波蘭表示 (a+b)*c中綴 前綴 * + a b c后綴 a b + c *2逆波蘭式的特點(diǎn)l無(wú)括號(hào)，形式簡(jiǎn)潔清楚；l運(yùn)算符的順序與運(yùn)算的次序完全相同。三元式和樹(shù)結(jié)構(gòu)表示n表達(dá)式表達(dá)式A * B + C * D的三元式序列為：的三元式序列為：（1）（）（*，A，B）（2）（）

23、（*，C，D）（3）（）（+，（，（1），（），（2） n可用樹(shù)形結(jié)構(gòu)直觀地表示三元式及其序列，形成抽象的樹(shù)型數(shù)據(jù)結(jié)構(gòu)形式的中間代碼。 *(1)（1） + A B C D *(2) 圖 6-5 表示 A*B+C*D 的樹(shù) n樹(shù)型表示的語(yǔ)法制導(dǎo)翻譯算法為：產(chǎn)生式語(yǔ)義動(dòng)作(1) EE(1)op E(2)E.VAL=NODE(op ,E(1).VAL ,E(2).VAL)(2) E(E(1)E.VAL=E(1).VAL(3) E-E(1)E.VAL=UNARY( ,E(1).VAL)(4) Ei E.VAL=LEAF(i)E.VAL：指示器，指向樹(shù)的一個(gè)結(jié)點(diǎn)。NODE (op , LEFT, RIG

24、HT)：建立二叉樹(shù)，回送的值是一個(gè)指示器，指向新樹(shù)根。UNARY (OP, CHILD )：與NODE類(lèi)似，只有一個(gè)枝。LEAF(i)：建立以i.LEXVAL指示的葉結(jié)點(diǎn)并回送此結(jié)點(diǎn)的地址。四元式表示法四元式表示法 n四元式是四元組： (OP, ARG1, ARG2, RESULT)n也稱(chēng)作三地址碼。在實(shí)現(xiàn)時(shí)，OP代表算符對(duì)應(yīng)的整數(shù)碼。ARG1、ARG2和RESULT或是指向有關(guān)符號(hào)表的某一位置的指示器或是代表臨時(shí)變量的整數(shù)碼。A= -B*(C + D)可翻譯成四元式序列：（1） BT1臨時(shí)變量T1（2） +CDT2臨時(shí)變量T2（3） *T1T2T3臨時(shí)變量T3（4） :=T3A賦值運(yùn)算更直觀

25、的形式：RESULT:=ARG1 OP ARG2抽象語(yǔ)法樹(shù)在語(yǔ)法樹(shù)中去掉那些對(duì)翻譯不必要的信息，從而獲得更有效的源程序中間表示。這種經(jīng)變換后的語(yǔ)法樹(shù)稱(chēng)之為抽象語(yǔ)法樹(shù)。 在抽象語(yǔ)法樹(shù)中，操作符和關(guān)鍵字都不作為葉結(jié)點(diǎn)出現(xiàn)，而是把它們作為內(nèi)部結(jié)點(diǎn)如產(chǎn)生式Sif B then S1 else S2抽象語(yǔ)法樹(shù)表示 if-then-elseB S1 S28.4 簡(jiǎn)單表達(dá)式及賦值語(yǔ)句的語(yǔ)法制導(dǎo)翻譯簡(jiǎn)單表達(dá)式及賦值語(yǔ)句的語(yǔ)法制導(dǎo)翻譯 一、只含整型變量的簡(jiǎn)單賦值句的文法：Ai:=EEE+E | E*E | -E | (E) | i 語(yǔ)義變量和語(yǔ)義過(guò)程： NEWTEMP：每次調(diào)用時(shí)，回送一個(gè)代表新臨時(shí)變量名的整數(shù)

26、碼，臨時(shí)變量名產(chǎn)生順序可想象為T(mén)1,T2,。E.PLACE：表示存放E值的變量名在符號(hào)表的入口或整數(shù)碼 。GEN(OP, ARG1, ARG2, RESULT)：將四元式填進(jìn)表中。ENTRY(i)：查找并取得與i相對(duì)應(yīng)的標(biāo)識(shí)符在符號(hào)表中的 入口產(chǎn)生式語(yǔ)義動(dòng)作(1) Ai:=E GEN(:= ,E.PLACE , , ENTRY(i)(2) 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

27、).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) EiE.PLACE:=ENTRY(i)在進(jìn)行不同類(lèi)型量混合運(yùn)算時(shí)，須為非終結(jié)符增加類(lèi)型屬性E.MODE。如在產(chǎn)生式EE(1) op E(2)中，E.MODE的語(yǔ)義規(guī)則定義為：if (E(1).MODE=Int&E(2) .MODE=Int) E.MODE=Int else E.MODE=r;需增加四元式：(itr , A , T)，并在運(yùn)算符上指出相應(yīng)的類(lèi)型。如

28、X=Y + I * J(X、Y為實(shí)型，I、J為整型)的四元式序列為： (*i , I , J , T1) (itr , T1, T2) (+r , Y , T2 , T3) (= , T3 , X)二、控制語(yǔ)句中的布爾表達(dá)式的翻譯二、控制語(yǔ)句中的布爾表達(dá)式的翻譯 n布爾表達(dá)式在程序設(shè)計(jì)語(yǔ)言中有兩個(gè)基本功用，一是作為控制語(yǔ)句的條件式；二是作為邏輯運(yùn)算，獲得邏輯值。n后者的翻譯較為簡(jiǎn)單，下面只考慮作為控制語(yǔ)句中的條件式n在高級(jí)程序設(shè)計(jì)語(yǔ)言中，布爾表達(dá)式一般的處理方式是采用某種優(yōu)化措施簡(jiǎn)化計(jì)算過(guò)程。n考慮下述文法的布爾表達(dá)式： EEE | EE | E | (E) | i | i rop i n我們

29、可以用條件句來(lái)解釋布爾計(jì)算： AB解釋為 if A then true else B AB解釋為 if A then B else false A解釋為 if A then false else true1 a=2, b=31|a=2&b=31 a=0, b=0a=b=0n為按此方式翻譯布爾式，引入如下三種形式的四元式： (1) (jnz ,A1 , , p)，若A1為真，則轉(zhuǎn)向第p個(gè)四元式。 (2) (j, A1 ,A2 , p)，若A1A2為真，則轉(zhuǎn)向第p個(gè)四元式。 (3) (j , , , p)，無(wú)條件轉(zhuǎn)向第p個(gè)四元式。這樣，ab等價(jià)于if ab then 1 else 0，可翻

30、譯為： (1) if ab goto (4) (2) t:=0 (3) goto (5) (4) t:=1 (5)其中用臨時(shí)變量t存放布爾表達(dá)式ab的值。if A10 goto pif A1 A2 goto pgoto p對(duì)ab & cd，得下列序列：(1) (j,a,b,3)(2) (j,-,-,5)(3) (j,c,d,7)(4) (j,-,-,5)(5) (:=,0,-,t1)(6) (j,-,-,8)(7) (:=,1,-,t1)(8)作為條件控制的布爾式，比如if E then S1 else S2中的E，它的作用僅僅在于控制對(duì)S1和S2的選擇，因此只涉及到E的兩個(gè)出口而不需

31、要保留E的值。如圖8-7所示。 E 的代碼 S1的代碼 S2的代碼 圖 8-7 條件語(yǔ)句的代碼結(jié)構(gòu) 例如, if ABD then S1 else S2 可解釋為：若A為真，則執(zhí)行S1，否則若BD為真，則執(zhí)行S1，否則執(zhí)行S2。其四元式序列為：(1) (jnz , A , 5) A的“真”出口轉(zhuǎn)移目標(biāo)為5。(2) (j , , , 3)A的“假”出口轉(zhuǎn)移目標(biāo)為3。(3) (j , B , D , 5) BD的“真”出口轉(zhuǎn)移目標(biāo)為5。(4) (j , , p+1) BD的“假”出口轉(zhuǎn)移目標(biāo)為（p+1）。(5) (關(guān)于S1的四元式序列)(p) (j , , , q)跳過(guò)S2的代碼段。(p+1) (

32、關(guān)于S2的四元式序列)(q)n這里需注意，一個(gè)布爾表達(dá)式的真假出口轉(zhuǎn)移目標(biāo)。如EE(1)E(2)，若E(1)為真，則E為真，E(1)的真出口轉(zhuǎn)移目標(biāo)即E的真出口轉(zhuǎn)移目標(biāo)；若E(1)為假，需再看E(2)；若E(2)為真，則E為真，而E(2)為假，則E為假。即E(2)的真、假出口轉(zhuǎn)移目標(biāo)就是E的真、假出口轉(zhuǎn)移目標(biāo)。n問(wèn)題在于在自下而上的分析過(guò)程中，一個(gè)布爾式的真假出口轉(zhuǎn)移目標(biāo)往往不能在產(chǎn)生四元式時(shí)就能確定。n例如，對(duì)于ABD，當(dāng)把A歸約為E(Ei）時(shí)，產(chǎn)生四元式(jnz ,A , , p)，但當(dāng)前并不能確定p的值，此時(shí)四元式是不完整的。n因此，我們需要記錄這些暫時(shí)還不完整的四元式的位置，一旦p被定

33、義，就及時(shí)回填。而p被定義之處在后選式中的對(duì)應(yīng)點(diǎn)正是文法變換時(shí)的分割點(diǎn)。為了使用語(yǔ)法制導(dǎo)翻譯在掃描到或時(shí)能及時(shí)回填一些業(yè)已明確的待填的轉(zhuǎn)移目標(biāo)，需要把文法改寫(xiě)成： EEAE | EOE |E| (E) | i | i rop i EAE EOE需定義兩個(gè)語(yǔ)義屬性E.TC和E.FC，分別記錄表達(dá)式E所對(duì)應(yīng)的需回填真、假出口轉(zhuǎn)移目標(biāo)的四元式所構(gòu)成的鏈。 例如，若E的四元式中需回填真出口轉(zhuǎn)移目標(biāo)的有p、q和r三個(gè)四元式，則這三個(gè)四元式可以通過(guò)第四個(gè)字段鏈成一條真鏈并用E.TC記錄鏈?zhǔn)譺。(p) ( 0)0為鏈尾標(biāo)志 (q) ( p) (r) ( q) E.TC為了處理E.TC和E.FC，需定義新的語(yǔ)

34、義變量和語(yǔ)義過(guò)程。NXQ：是指向下一個(gè)將要形成但尚未形成的四元式的指示器。每執(zhí)行GEN一次，就自動(dòng)增1MERG(p1, p2)：把p1和p2鏈合二為一的函數(shù)。BACKPATCH(p, t)：回填 鏈表p中每個(gè)四元式的第四區(qū)段為t。POINTER MERG(p1,p2) IF (p1=0) RETURN p2 ELSE p=p1; WHILE 四元式p的第四區(qū)段的內(nèi)容不為0 DO p:=四元式p的第四區(qū)段的內(nèi)容; 把p2填進(jìn)四元式p的第四區(qū)段; RETURN p1; void BACKPATCH (p, t) q=p; WHILE q0 DO q:=四元式q的第四區(qū)段的內(nèi)容;把t填進(jìn)四元式p的第四區(qū)段;p=q 若不改寫(xiě)文法，則子程序不一定出現(xiàn)在產(chǎn)生式的最后，而須在適當(dāng)?shù)牡胤讲迦胱映绦颉４藭r(shí)，LR分析器會(huì)替你進(jìn)行改寫(xiě)。語(yǔ)義子程序如下：(1) Ei E.TC=NXQ; E.