語法制導(dǎo)翻譯和中間代碼生成

1、關(guān)于語法制導(dǎo)翻譯與中間代碼生成第一張，PPT共四十八頁，創(chuàng)作于2022年6月8.1 屬性和屬性文法8.1.1屬性文法屬性(attribute)是編程語言結(jié)構(gòu)的任意特性，是一個語法概念的特征描述。屬性是想表示的任何東西，典型的屬性有：變量的數(shù)據(jù)類型、表達式的值、存儲器中變量的位置、程序的目標(biāo)代碼、數(shù)的有效位數(shù)等。屬性文法(attribute grammar)：將屬性關(guān)系等式附加在相應(yīng)文法規(guī)則上的文法屬性的表示：若a是文法符號X的一個屬性，則記作X.a。a稱為屬性變量。屬性關(guān)系等式與采用何種語法分析方式無關(guān)，但是屬性的計算次序受分析方法所限定的分析樹結(jié)點的建立次序的約束。第二張，PPT共四十八頁，

2、創(chuàng)作于2022年6月例8.1 考慮下面簡單的無符號數(shù)文法： numbernumber digit | digitdigit0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9屬性文法：文法規(guī)則語義規(guī)則number(1)number(2) digit number(1).val=number(2).val*10 + digit.valnumberdigit number.val=digit.valdigit0 digit.val=0digit9 digit.val=9第三張，PPT共四十八頁，創(chuàng)作于2022年6月屬性計算依賴于分析樹或語法樹明確或不明確的遍歷：第四張，PPT

3、共四十八頁，創(chuàng)作于2022年6月例8.2 考慮下列類似C語言中變量聲明的簡單文法：decltype var-listtypeint | floatvar-listid, var-list | id屬性文法：文法規(guī)則語義規(guī)則decltype var-list var-list.dtype=type.dtypetypeint type.dtype=integertypefloat type.dtype=realvar-list(1)id ,var-list(2) id.dtype=var-list(1).dtype var-list(2).dtype=var-list(1).dtypevar-li

4、stid id.dtype=var-list.dtype第五張，PPT共四十八頁，創(chuàng)作于2022年6月字符串float x,y的語法樹，顯示屬性文法指定的dtype屬性：第六張，PPT共四十八頁，創(chuàng)作于2022年6月輔助函數(shù)mkOpNode和mkNumNode：mkOpNode構(gòu)成一個新的樹結(jié)點；mkNumNode構(gòu)成一個葉子結(jié)點。 例8.3 考慮下列簡單的整數(shù)算術(shù)表達式文法：expexp+term | exp-term | termtermterm*factor | factorfactor(exp)| numberexp(或term或factor)的基本屬性是它的數(shù)字值，寫作val。屬性文

5、法簡單整型算術(shù)表達式的抽象語法樹的屬性文法： 文法規(guī)則 語義規(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(*,term(2).tree,factor.tree)termfactorterm.tree=factor.treefactor(exp)factor

6、.tree=exp.treefactornumberfactor.tree=mkNumNode(number.lexval)第七張，PPT共四十八頁，創(chuàng)作于2022年6月8.1.2 綜合和繼承屬性 綜合屬性(synthesized attribute) ：若產(chǎn)生式左部符號A的屬性值是通過右部符號的屬性值或A的其它屬性值得來的S屬性文法：所有的屬性都是綜合的任一右部符號的屬性計算與它所在的產(chǎn)生式無關(guān)（從語法樹看，任一結(jié)點的屬性僅依賴它的下層或它自己的其它屬性，換句話說不依賴上層和同層其它結(jié)點的屬性）S屬性文法的屬性值可以通過對樹進行簡單后序遍歷來計算：void PostEval(treenode

7、 T) for each child C of T do PostEval(C); compute all synthesized attributes of T;第八張，PPT共四十八頁，創(chuàng)作于2022年6月并不是所有的屬性都是綜合的。所有的非綜合屬性稱為繼承(inherited)屬性。例8.4 對例8.1中的文法進行修改，數(shù)可以是八進制或十進制的based-numnum basecharbasecharo | dnumnum digit | digitdigit0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9此時，num和digit均需要一個新的屬性base用來計

8、算屬性val。 第九張，PPT共四十八頁，創(chuàng)作于2022年6月文法規(guī)則語義規(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).base digit.ba

9、se=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 9第十張，PPT共四十八頁，創(chuàng)作于2022年6月345o的語法樹：第十一張，PPT共四十八頁，創(chuàng)作于2022年6月與綜合屬性不同，子孫繼承屬性計算的順序是重要的，因為在子孫的屬性中繼承屬性可能有依賴關(guān)系。此文法有兩個屬

10、性，綜合屬性val、繼承屬性base；先計算base，再用后序遍歷計算val。綜上所述，屬性文法是帶有下列說明的翻譯文法：1每個終結(jié)符、非終結(jié)符都有一個與其相關(guān)的屬性的有窮集。2每一個非終結(jié)符號的屬性可分為兩類：繼承的或綜合的。3在分析樹中，一個結(jié)點的綜合屬性值是從其子結(jié)點和它本身的屬性值計算出來的；而一個結(jié)點的繼承屬性值是由該結(jié)點兄第結(jié)點和父結(jié)點和它本身的屬性值計算出來的。第十二張，PPT共四十八頁，創(chuàng)作于2022年6月屬性計算方法樹遍歷的屬性計算方法若語法樹已經(jīng)建立起了，并且樹中已帶有開始符號的繼承屬性和終結(jié)符的綜合屬性。然后以某種次序遍歷語法樹，直至計算出所有屬性。有時可能需要進行多遍遍

11、歷。 一遍掃描的處理方法 在很多情況下，翻譯可以在掃描分析過程中完成，不需要構(gòu)造出明確的語法分析樹。L屬性翻譯的語法制導(dǎo)翻譯方案包含了所有可以在語法分析過程中完成的翻譯方案。一遍掃描的處理方法與下面兩個因素密切相關(guān)： （1）所采用的語法分析方法（不同方法對屬性計算的方便性不同） （2）屬性的計算次序。 第十三張，PPT共四十八頁，創(chuàng)作于2022年6月8.1.3 屬性的變換屬性計算主要在語義分析階段進行，但語義分析的部分工作可以放到詞法/語法分析階段進行。如，當(dāng)一個名字填入符號表時，就可以檢查這個名字是否只定義了一次。如果語義分析可以推遲到所有的語法分析完成之后進行，那么實現(xiàn)語義分析的任務(wù)就相當(dāng)

12、容易，其本質(zhì)上是對語法樹的一序列的遍歷過程，同時在遍歷中每次遇到結(jié)點時進行計算，但也這就意味著編譯程序必須是多遍的。另一方面，如果要求編譯程序在一遍中完成所有的操作(包括代碼生成)，那么語義分析的實現(xiàn)就會變成尋找計算語義信息的正確順序和方法的特別的過程。第十四張，PPT共四十八頁，創(chuàng)作于2022年6月可能會有這樣的情況，不改變語言合法的字符串而修改文法會使屬性的計算更簡單或更復(fù)雜。定理：(Knuth 1968)給定一個屬性文法，通過適當(dāng)?shù)匦薷奈姆?，而無須改變文法的語言，所有的繼承屬性可以改變成綜合屬性。雖然重寫文法使之僅使用綜合屬性總是可能的，但通常是使用帶繼承屬性的屬性文法更自然些。屬性等式

13、與使用什么樣的語法分析方法以及分析算法的具體實現(xiàn)無關(guān)。在下面的語法制導(dǎo)翻譯中，我們將會看到屬性文法的作用在于它能指導(dǎo)我們寫出更加清晰、簡練、不易出錯的的語義分析子程序，同時子程序也更加易懂。第十五張，PPT共四十八頁，創(chuàng)作于2022年6月例8.5 再次考慮變量聲明的簡單文法：decltype var-listtypeint | floatvar-listid, var-list | id可將這個文法改寫為：declvar-list idvar-listvar-list id, | typetypeint | floatint a, b, c第十六張，PPT共四十八頁，創(chuàng)作于2022年6月8.2

14、 屬性文法和語法制導(dǎo)翻譯語義分析包括構(gòu)造符號表、記錄聲明中建立的名字的含義、在表達式和語句中進行類型檢查等。 類型檢查應(yīng)驗證一種結(jié)構(gòu)的類型是否匹配其上下文的要求。如何把源程序改造成某種形式的中間語言程序？ 在語法分析中，有相當(dāng)成熟的理論和算法：使用 BNF中的上下文無關(guān)文法描述語言的語法結(jié)構(gòu)，并用自頂向下或自底向上的分析算法實現(xiàn)語法分析。 語義分析目前還沒有給出一種公認(rèn)的形式化描述系統(tǒng)，只能說有一些成功的系統(tǒng)和方法，其中比較接近形式化的一種方法是語法制導(dǎo)翻譯法。 第十七張，PPT共四十八頁，創(chuàng)作于2022年6月所謂語法制導(dǎo)翻譯，直觀上說就是為每個產(chǎn)生式配上一個翻譯子程序（語義子程序），并且在語

15、法分析的同時執(zhí)行它。語義子程序的功能包括改變編譯程序某些變量的值、查填各種符號表、診察與報告源程序錯誤、產(chǎn)生中間代碼等。語義子程序是給產(chǎn)生式賦予具體意義的手段，一方面規(guī)定了產(chǎn)生式產(chǎn)生的符號串的意義，另一方面又按照這種意義規(guī)定了生成代碼應(yīng)做的基本動作。例如，定義二進制算術(shù)表達式E的”值”的語義： 1. EE(1)+E(2)E.VAL:=E(1).VAL+E(2).VAL 2. E0E.VAL:=0 3. E1E.VAL:=1對輸入串1+1+0+1，一旦分析器認(rèn)出它是一個句子時，它的值“11”也就被語義子程序計算出來了。 第十八張，PPT共四十八頁，創(chuàng)作于2022年6月語法制導(dǎo)翻譯既可以用來產(chǎn)生中

16、間代碼，也可以用來產(chǎn)生目標(biāo)指令，甚至可用來對輸入串進行解釋執(zhí)行。 總之，按語法制導(dǎo)翻譯的方法來實現(xiàn)語言的翻譯，就是要根據(jù)語言的文法，按照各產(chǎn)生式的語義，分別編寫出完成這些操作的語義子程序，并把它們插入到各產(chǎn)生式右部的適當(dāng)位置上，從而形成翻譯文法。這樣，在語法分析過程中，就能在分析符號串的同時，執(zhí)行由翻譯文法所確定的、與該符號串相對應(yīng)的動作序列，即按動作符號的順序調(diào)用相應(yīng)的子程序完成翻譯任務(wù)。語義子程序的設(shè)計：以屬性文法為基礎(chǔ)，將屬性等式轉(zhuǎn)化為計算規(guī)則（屬性等式本身指示了屬性計算時的順序約束）。第十九張，PPT共四十八頁，創(chuàng)作于2022年6月對產(chǎn)生式 X0X1 X2 . . . Xn 的屬性等式

17、Xi.aj=fij(X0.a1，X0.ak，X1.a1，X1.ak，Xn.a1，Xn.ak)等式右邊出現(xiàn)的所有屬性值必須已經(jīng)存在。但在屬性文法的說明中，這個要求可能被忽略，可以將等式寫成任意順序而不會影響正確性。實現(xiàn)屬性文法的關(guān)鍵在于為屬性的計算尋找一個順序，以確保當(dāng)每次進行計算時使用的所有屬性值都是有效的。文法規(guī)則 語義規(guī)則declvar-list id id.dtype=var-list.dtypevar-list(1)var-list(2) id, id.dtype=var-list(2).dtype var-list(1).dtype=var-list(2).dtypevar-list

18、type var-list.dtype=type.dtypetypeint type.dtype=integertypefloat type.dtype=real仍以簡單說明句的屬性文法為例其語義動作就是在符號表中登記上這些名字的有關(guān)性質(zhì)。按此屬性文法，就可把所說明的性質(zhì)及時告訴每個名字id?；蛘哒f每當(dāng)讀進一個標(biāo)識符時，就可以把它的性質(zhì)登記在符號表中。 第二十張，PPT共四十八頁，創(chuàng)作于2022年6月幾個語義變量和語義過程：D.dtypeFILL(p, A)：把性質(zhì)A填進p所指符號表入口的有關(guān)欄中。ENTRY(i)：查詢和取得i所代表的標(biāo)識符在符號表中的入口各產(chǎn)生式語義動作：1declvar-

19、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.dtype=real可見，語法制導(dǎo)翻譯就是屬性文法的一種實現(xiàn)方式。 第二十一張，PPT共四十八頁，創(chuàng)作于2022年6月S屬性文法的語法制導(dǎo)翻譯通常可借助于LR分析器實

20、現(xiàn)，在對輸入串進行語法分析的同時對屬性進行計算。對LR分析程序，可以通過擴充分析棧，修改總控程序，使之適合于主要處理S屬性文法。 對綜合屬性，可設(shè)置一個值棧進行存儲，值棧將和分析棧并行操作，每當(dāng)在分析棧出現(xiàn)移進或規(guī)約時，就根據(jù)屬性等式來計算新值。 以簡單算術(shù)表達式的二義性版本為例：expexp+exp | exp*exp | (exp) | number文法規(guī)則語義規(guī)則exp(1)exp(2) + exp(3) exp(1).val = exp(2).val + exp(3).valexp(1)exp(2) * exp(3) exp(1).val = exp(2).val * exp(3).v

21、alexp(1)(exp(2) exp(1).val = exp(2).valexpnumber exp.val = number.val第二十二張，PPT共四十八頁，創(chuàng)作于2022年6月statevalZZ.zYY.y.XX.xtop第二十三張，PPT共四十八頁，創(chuàng)作于2022年6月在LR分析中，表達式3*4+5的語法和語義動作： 分析棧 輸入語法動作值棧 語義動作1 # 3*4+5# 移進#2 #n *4+5# 規(guī)約En #3 E.val=n.val3 #E *4+5# 移進#34 #E* 4+5# 移進#3*5 #E*n +5# 規(guī)約En#3*4 E.val=n.val6 #E*E +5

22、# 規(guī)約EE*E #3*4 E(1).val=E(2).val+E(3).val 7 #E +5# 移進#128 #E+ 5# 移進#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#17第二十四張，PPT共四十八頁，創(chuàng)作于2022年6月8.3 中間代碼的形式復(fù)雜性程度介于源程序語言和機器語言之間的語言。引入目的：為了使編譯程序結(jié)構(gòu)在邏輯上更為簡單明確, 便于編譯系統(tǒng)的建立和編譯系統(tǒng)的移植，特別是為了使目標(biāo)代碼的優(yōu)化比較容易實現(xiàn)并獨立于機器進行。 中間代碼生成是通過遍歷

23、由于法分析器建立的語法樹實現(xiàn)的。遍歷語法樹的操作可以和建立語法樹的操作同時進行，也可以在語法樹建立之后再遍歷一次語法樹，前一種叫語法制導(dǎo)翻譯。常見形式：逆波蘭記號、樹結(jié)構(gòu)表示、三元式、四元式等。第二十五張，PPT共四十八頁，創(chuàng)作于2022年6月逆波蘭式逆波蘭式是波蘭邏輯學(xué)家盧卡西維奇發(fā)明的一種表示表達式的方法，用于說明算術(shù)表達式：不使用括號，運算量在前，算符在后，故也稱為后綴式。1簡單表達式的逆波蘭表示 (a+b)*c中綴 前綴 * + a b c后綴 a b + c *2逆波蘭式的特點無括號，形式簡潔清楚；運算符的順序與運算的次序完全相同。第二十六張，PPT共四十八頁，創(chuàng)作于2022年6月三

24、元式和樹結(jié)構(gòu)表示表達式A * B + C * D的三元式序列為：（1）（*，A，B）（2）（*，C，D）（3）（+，（1），（2） 可用樹形結(jié)構(gòu)直觀地表示三元式及其序列，形成抽象的樹型數(shù)據(jù)結(jié)構(gòu)形式的中間代碼。 第二十七張，PPT共四十八頁，創(chuàng)作于2022年6月樹型表示的語法制導(dǎo)翻譯算法為：產(chǎn)生式語義動作(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：指示器，指向樹的一個結(jié)點。NO

25、DE (op , LEFT, RIGHT)：建立二叉樹，回送的值是一個指示器，指向新樹根。UNARY (OP, CHILD )：與NODE類似，只有一個枝。LEAF(i)：建立以i.LEXVAL指示的葉結(jié)點并回送此結(jié)點的地址。第二十八張，PPT共四十八頁，創(chuàng)作于2022年6月四元式表示法 四元式是四元組： (OP, ARG1, ARG2, RESULT)也稱作三地址碼。在實現(xiàn)時，OP代表算符對應(yīng)的整數(shù)碼。ARG1、ARG2和RESULT或是指向有關(guān)符號表的某一位置的指示器或是代表臨時變量的整數(shù)碼。A= -B*(C + D)可翻譯成四元式序列：（1）BT1臨時變量T1（2）+CDT2臨時變量T2

26、（3）*T1T2T3臨時變量T3（4）:=T3A賦值運算更直觀的形式：RESULT:=ARG1 OP ARG2第二十九張，PPT共四十八頁，創(chuàng)作于2022年6月抽象語法樹在語法樹中去掉那些對翻譯不必要的信息，從而獲得更有效的源程序中間表示。這種經(jīng)變換后的語法樹稱之為抽象語法樹。 在抽象語法樹中，操作符和關(guān)鍵字都不作為葉結(jié)點出現(xiàn)，而是把它們作為內(nèi)部結(jié)點如產(chǎn)生式Sif B then S1 else S2抽象語法樹表示 if-then-elseB S1 S2第三十張，PPT共四十八頁，創(chuàng)作于2022年6月8.4 簡單表達式及賦值語句的語法制導(dǎo)翻譯 一、只含整型變量的簡單賦值句的文法：Ai:=EEE+

27、E | E*E | -E | (E) | i 語義變量和語義過程： NEWTEMP：每次調(diào)用時，回送一個代表新臨時變量名的整數(shù)碼，臨時變量名產(chǎn)生順序可想象為T1,T2,。E.PLACE：表示存放E值的變量名在符號表的入口或整數(shù)碼 。GEN(OP, ARG1, ARG2, RESULT)：將四元式填進表中。ENTRY(i)：查找并取得與i相對應(yīng)的標(biāo)識符在符號表中的 入口第三十一張，PPT共四十八頁，創(chuàng)作于2022年6月產(chǎn)生式語義動作(1) Ai:=E GEN(:= ,E.PLACE , , ENTRY(i)(2) EE(1)+E(2)E.PLACE:=NEWTEMP; GEN (+ , E(1)

28、.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) EiE.PLACE:=ENTRY(i)第三十二張，PPT共四十八頁，創(chuàng)作于2022年6月在進行不同類型量混合運算時，須為非終結(jié)符增加類型屬性E.MODE。如在產(chǎn)生式EE(1) op E(2)中，E

29、.MODE的語義規(guī)則定義為：if (E(1).MODE=Int&E(2) .MODE=Int) E.MODE=Int else E.MODE=r;需增加四元式：(itr , A , T)，并在運算符上指出相應(yīng)的類型。如X=Y + I * J(X、Y為實型，I、J為整型)的四元式序列為： (*i , I , J , T1) (itr , T1, T2) (+r , Y , T2 , T3) (= , T3 , X)第三十三張，PPT共四十八頁，創(chuàng)作于2022年6月二、控制語句中的布爾表達式的翻譯 布爾表達式在程序設(shè)計語言中有兩個基本功用，一是作為控制語句的條件式；二是作為邏輯運算，獲得邏輯值。后

30、者的翻譯較為簡單，下面只考慮作為控制語句中的條件式在高級程序設(shè)計語言中，布爾表達式一般的處理方式是采用某種優(yōu)化措施簡化計算過程?？紤]下述文法的布爾表達式： EEE | EE | E | (E) | i | i rop i 我們可以用條件句來解釋布爾計算： 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=0第三十四張，PPT共四十八頁，創(chuàng)作于2022年6月為按此方式翻譯布爾式，引入如下三種形式的四元式： (

31、1) (jnz ,A1 , , p)，若A1為真，則轉(zhuǎn)向第p個四元式。 (2) (j, A1 ,A2 , p)，若A1A2為真，則轉(zhuǎn)向第p個四元式。 (3) (j , , , p)，無條件轉(zhuǎn)向第p個四元式。這樣，ab等價于if ab then 1 else 0，可翻譯為： (1) if ab goto (4) (2) t:=0 (3) goto (5) (4) t:=1 (5)其中用臨時變量t存放布爾表達式ab的值。if A10 goto pif A1 A2 goto pgoto p第三十五張，PPT共四十八頁，創(chuàng)作于2022年6月對ab & cd，得下列序列：(1) (j,a,b,3)(2)

32、 (j,-,-,5)(3) (j,c,d,7)(4) (j,-,-,5)(5) (:=,0,-,t1)(6) (j,-,-,8)(7) (:=,1,-,t1)(8)第三十六張，PPT共四十八頁，創(chuàng)作于2022年6月作為條件控制的布爾式，比如if E then S1 else S2中的E，它的作用僅僅在于控制對S1和S2的選擇，因此只涉及到E的兩個出口而不需要保留E的值。如圖8-7所示。第三十七張，PPT共四十八頁，創(chuàng)作于2022年6月例如, if ABD then S1 else S2 可解釋為：若A為真，則執(zhí)行S1，否則若BD為真，則執(zhí)行S1，否則執(zhí)行S2。其四元式序列為：(1) (jnz

33、, 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)跳過S2的代碼段。(p+1) (關(guān)于S2的四元式序列)(q)第三十八張，PPT共四十八頁，創(chuàng)作于2022年6月這里需注意，一個布爾表達式的真假出口轉(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)為

34、真，則E為真，而E(2)為假，則E為假。即E(2)的真、假出口轉(zhuǎn)移目標(biāo)就是E的真、假出口轉(zhuǎn)移目標(biāo)。問題在于在自下而上的分析過程中，一個布爾式的真假出口轉(zhuǎn)移目標(biāo)往往不能在產(chǎn)生四元式時就能確定。例如，對于ABD，當(dāng)把A歸約為E(Ei）時，產(chǎn)生四元式(jnz ,A , , p)，但當(dāng)前并不能確定p的值，此時四元式是不完整的。因此，我們需要記錄這些暫時還不完整的四元式的位置，一旦p被定義，就及時回填。而p被定義之處在后選式中的對應(yīng)點正是文法變換時的分割點。第三十九張，PPT共四十八頁，創(chuàng)作于2022年6月為了使用語法制導(dǎo)翻譯在掃描到或時能及時回填一些業(yè)已明確的待填的轉(zhuǎn)移目標(biāo)，需要把文法改寫成： EEA

35、E | EOE |E| (E) | i | i rop i EAE EOE需定義兩個語義屬性E.TC和E.FC，分別記錄表達式E所對應(yīng)的需回填真、假出口轉(zhuǎn)移目標(biāo)的四元式所構(gòu)成的鏈。 例如，若E的四元式中需回填真出口轉(zhuǎn)移目標(biāo)的有p、q和r三個四元式，則這三個四元式可以通過第四個字段鏈成一條真鏈并用E.TC記錄鏈?zhǔn)譺。(p) ( 0)0為鏈尾標(biāo)志 (q) ( p) (r) ( q) E.TC第四十張，PPT共四十八頁，創(chuàng)作于2022年6月為了處理E.TC和E.FC，需定義新的語義變量和語義過程。NXQ：是指向下一個將要形成但尚未形成的四元式的指示器。每執(zhí)行GEN一次，就自動增1MERG(p1, p

36、2)：把p1和p2鏈合二為一的函數(shù)。BACKPATCH(p, t)：回填 鏈表p中每個四元式的第四區(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填進四元式p的第四區(qū)段; RETURN p1; 第四十一張，PPT共四十八頁，創(chuàng)作于2022年6月void BACKPATCH (p, t) q=p; WHILE q0 DO q:=四元式q的第四區(qū)段的內(nèi)容;把t填進四元式p的第四區(qū)段;p=q 若不改寫文法，則子程序不一定出現(xiàn)在產(chǎn)生式的最后，而須在適當(dāng)?shù)牡胤讲迦胱映绦?。此時，LR分析器會替你進行改寫。第四十二張，PPT共四十八頁，創(chuàng)作于2022年6月語義子程序如下：Ei