編譯原理第5章 語(yǔ)義分析及中間代碼產(chǎn)生

第五章語(yǔ)法制導(dǎo)翻譯和中間代碼產(chǎn)生03二月20231第五章語(yǔ)法制導(dǎo)翻譯和中間代碼產(chǎn)生第五章語(yǔ)法制導(dǎo)翻譯和中間代碼產(chǎn)生03二月20232語(yǔ)義分析的任務(wù)：根據(jù)語(yǔ)法成分的結(jié)構(gòu)，分析其含義，并用一種內(nèi)部形式（中間代碼）或直接用目標(biāo)語(yǔ)言表示出來(lái)。具體：靜態(tài)語(yǔ)義檢查和翻譯包括：類(lèi)型檢查（操作符是否相容，例如%） 控制流檢查（break是否有switch和for,while） 一致性檢查（inta;floata;） 相關(guān)名字檢查、等等第五章語(yǔ)法制導(dǎo)翻譯和中間代碼產(chǎn)生03二月202335.1一般原理和樹(shù)變換5.2簡(jiǎn)單SDTS和自上而下翻譯器5.3簡(jiǎn)單后綴SDTS和自下而上翻譯器5.4抽象語(yǔ)法樹(shù)的構(gòu)造5.5屬性文法5.6中間代碼形式5.7屬性翻譯文法的應(yīng)用第五章語(yǔ)法制導(dǎo)翻譯和中間代碼產(chǎn)生03二月202345.1一般原理和樹(shù)變換語(yǔ)法制導(dǎo)翻譯法SDTS是一個(gè)五元組

T=(VT,VN,△,R,S)。VT是一個(gè)有窮的輸入字母表，包含源語(yǔ)言中的符號(hào)；VN是一個(gè)有窮的非終結(jié)符號(hào)集合；△是一個(gè)有窮的輸出字母表，包含出現(xiàn)在翻譯串中的那些符號(hào)；R是形如A→w,y的規(guī)則的有窮集合，w是由終結(jié)符或非終結(jié)符組成的串，y是由VN或△中的符號(hào)組成的串；S∈VN是一個(gè)開(kāi)始符號(hào)。第五章語(yǔ)法制導(dǎo)翻譯和中間代碼產(chǎn)生03二月20235例如：SDTST1=({a,b,c,+,-,[,]},{E,T,A},{ADD,SUB,NEG,x,y,z},R,E)，其中R由下列翻譯規(guī)則組成：

E→E+T,TEADDE→E-T,ETSUBE→–T,TNEGE→T,TT→[E],ET→A,AA→a,xA→b,yA→c,zT1的基礎(chǔ)源文法是E→E+T|E-T|-T|TT→[E]|AA→a|b|cT1的基礎(chǔ)目標(biāo)文法是E→TEADD|ETSUB|TNEG|TT→E|AA→x|y|z第五章語(yǔ)法制導(dǎo)翻譯和中間代碼產(chǎn)生03二月20236一個(gè)翻譯模式是一個(gè)形如(u,v)的串對(duì)，其中，u是SDTS基礎(chǔ)源文法的一個(gè)句型，而v稱(chēng)為與其對(duì)應(yīng)的翻譯，它是由VN和△中元素組成的串。翻譯模式的定義如下：(S,S)是一個(gè)翻譯模式，且這兩個(gè)S是相關(guān)的(S是SDTS的開(kāi)始符號(hào))。(aAb,a’Ab’)是一個(gè)翻譯模式，且兩個(gè)A是相關(guān)的；此外，若A→g,g’是R中的一條規(guī)則，那么(agb,a’g’b’)也是一個(gè)翻譯模式。規(guī)則中g(shù)和g’的非終結(jié)符之間的相關(guān)性也必須帶進(jìn)這種翻譯模式之中。表示法(aAb,a’Ab’)=>(agb,a’g’b’)表示一種翻譯模式到另一種翻譯模式的變換。第五章語(yǔ)法制導(dǎo)翻譯和中間代碼產(chǎn)生03二月20237樹(shù)變換語(yǔ)法制導(dǎo)的翻譯過(guò)程也可用語(yǔ)法樹(shù)變換來(lái)說(shuō)明。從中剪掉終結(jié)符號(hào)節(jié)點(diǎn)；根據(jù)適當(dāng)?shù)姆g規(guī)則，重排每個(gè)中間結(jié)點(diǎn)的孩子；添加對(duì)應(yīng)于輸出符號(hào)集中的中間符節(jié)點(diǎn)。第五章語(yǔ)法制導(dǎo)翻譯和中間代碼產(chǎn)生03二月202385.2簡(jiǎn)單SDTS和自上而下翻譯器

如果在每一規(guī)則的翻譯成分中，非終結(jié)符出現(xiàn)的次序與它們?cè)谠闯煞种谐霈F(xiàn)的次序相同，則稱(chēng)一個(gè)SDTS是簡(jiǎn)單的(simple)；但是，如果A→A1+A2,A2A1ADD是SDTST的一個(gè)規(guī)則，那么，該SDTST就是不簡(jiǎn)單的。第五章語(yǔ)法制導(dǎo)翻譯和中間代碼產(chǎn)生03二月20239如果T=(VN,VT,△,R,S)是其基礎(chǔ)源文法為L(zhǎng)L(k)的簡(jiǎn)單SDTS，那么，存在一個(gè)自上而下的確定的下推翻譯器PDT(Push-DownTranslater)，它接受T的輸入語(yǔ)言中的任何符號(hào)串并產(chǎn)生對(duì)應(yīng)的輸出串。PDTP的定義如下：P的一個(gè)構(gòu)形是一個(gè)四元組(q,x,y,z)，其中，q是它的有窮控制器的狀態(tài)，x是尚待掃描的輸入串，y是下推棧，z是此時(shí)被打印出的輸出符號(hào)串。于是，在某次移動(dòng)中，便有(q,ax,Yy’,z)┟(r,x,gy’,zz’)即，在狀態(tài)q面臨輸入符號(hào)a且棧頂符號(hào)為Y時(shí)，P才允許移動(dòng)到狀態(tài)r，這一移動(dòng)的結(jié)果是：輸入符號(hào)a被去掉，棧頂符號(hào)Y被g所替換，而且串z’已作為輸出串打印出。第五章語(yǔ)法制導(dǎo)翻譯和中間代碼產(chǎn)生03二月202310稱(chēng)w是關(guān)于x的輸出，如果對(duì)于某個(gè)狀態(tài)q和棧符號(hào)串u，存在(q0,x,Z0,ε)┟(q,ε,u,w)其中，q0是初態(tài)；Z0是棧的初始內(nèi)容，ε為空串。若u＝ε，則稱(chēng)P停止于空棧；若q是某個(gè)終態(tài)，則稱(chēng)P停止于終態(tài)。如果P滿(mǎn)足下述兩個(gè)條件，則稱(chēng)P是確定的：對(duì)所有的狀態(tài)q，輸入串a(chǎn)和棧符號(hào)Z，δ(q,a,Z)至多只包含一個(gè)元素；若δ(q,ε,Z)非空，則不存在符號(hào)a(a≠ε)使得δ(q,a,Z)非空，即對(duì)于某個(gè)狀態(tài)和棧符號(hào)，在空移動(dòng)和非空移動(dòng)之間不應(yīng)存在沖突。第五章語(yǔ)法制導(dǎo)翻譯和中間代碼產(chǎn)生03二月202311PDTP的操作為：①在一應(yīng)用移動(dòng)中，非終結(jié)符A已位于棧頂，借助于分析表，選定產(chǎn)生式A→w來(lái)進(jìn)行歸約。假定R中的翻譯規(guī)則為A→w,z其中，w=a0B1a1B2a2…Bkak，而z=b0B1b1B2…Bkbk。其中，Bi是非終結(jié)符，ai是輸入符號(hào)串，bi是輸出符號(hào)串。位于棧頂?shù)腁由下面的復(fù)合串b0a0B1b1a1B2…Bkbkak

所替代，而b0稱(chēng)為新棧頂符號(hào)。②若棧頂符號(hào)是輸出字母表的一個(gè)元素，則從棧中彈出，并將其作為輸出符號(hào)打印出。③若棧頂符號(hào)是輸入字母表VT的一個(gè)元素，則它應(yīng)與當(dāng)前輸入符號(hào)匹配。從棧頂彈出它，輸入指針后移。第五章語(yǔ)法制導(dǎo)翻譯和中間代碼產(chǎn)生03二月2023125.3簡(jiǎn)單后綴SDTS和自下而上翻譯器如果一個(gè)SDTS是簡(jiǎn)單的，而且它的每個(gè)翻譯規(guī)則都有下述形式：A→a0B1a1B2a2…Bkak,B1B2…Bkw也就是說(shuō)，除了最右邊的w之外，（輸出）終結(jié)符不可能出現(xiàn)在翻譯成分之中，那么，稱(chēng)這個(gè)SDTS為簡(jiǎn)單后綴的(SimplePostFix)。定理：對(duì)其基礎(chǔ)源文法為L(zhǎng)R(k)的每一簡(jiǎn)單后綴的SDTS，存在一確定的LR(k)PDT：它接受從該基礎(chǔ)源文法可推導(dǎo)出的每一句子；它將這種句子的翻譯作為輸出。后綴翻譯

IF-THEN-ELSE控制語(yǔ)句函數(shù)調(diào)用第五章語(yǔ)法制導(dǎo)翻譯和中間代碼產(chǎn)生03二月2023135.4抽象語(yǔ)法樹(shù)的構(gòu)造抽象語(yǔ)法樹(shù)AST(Abstract-Syntaxtree)是某個(gè)語(yǔ)言結(jié)構(gòu)的一種簡(jiǎn)潔的樹(shù)形表示形式，它只需包含該結(jié)構(gòu)尚須轉(zhuǎn)換或歸約的信息。語(yǔ)法樹(shù)簡(jiǎn)化成一個(gè)AST：去掉于單非產(chǎn)生式（即右部為單一終結(jié)符的產(chǎn)生式）相關(guān)的子樹(shù)，并上提相關(guān)分支上的終結(jié)符號(hào)節(jié)點(diǎn)。對(duì)于直接包含運(yùn)算符的多個(gè)子樹(shù)，上提運(yùn)算符并讓它取代其父節(jié)點(diǎn)。去掉括號(hào)，并上提運(yùn)算符，讓它取代其節(jié)點(diǎn)。最后得到的語(yǔ)法樹(shù)便是一個(gè)AST。第五章語(yǔ)法制導(dǎo)翻譯和中間代碼產(chǎn)生03二月202314§5.5屬性文法

一、屬性一、屬性：一般用來(lái)描述客觀(guān)存在的事物或人的特性。例如，學(xué)生的姓名、年齡、性別等；商品的顏色、重量、單價(jià)等。編譯技術(shù)中用屬性來(lái)描述計(jì)算機(jī)處理對(duì)象的特征。例如：X.Type,X.Place,X.val等分別描述X的類(lèi)型，存儲(chǔ)位置、值等不同的特征。 屬性分兩類(lèi)： 綜合屬性：一般用于“自下而上”傳遞信息。 繼承屬性：一般用于“自上而下”傳遞信息。第五章語(yǔ)法制導(dǎo)翻譯和中間代碼產(chǎn)生03二月202315二、屬性文法

對(duì)于某個(gè)壓縮了的上下文無(wú)關(guān)文法，當(dāng)為每個(gè)文法符號(hào)引進(jìn)一組屬性，且讓該文法中的重寫(xiě)規(guī)則附加以語(yǔ)義規(guī)則時(shí)，稱(chēng)該上下文無(wú)關(guān)文法為屬性文法。

形式定義：一個(gè)屬性文法形式上定義為一個(gè)三元組AG,AG=(G,V,E)。其中G表示一個(gè)上下文無(wú)關(guān)文法；V表示屬性的有窮集；E表示屬性的斷言或謂詞的有窮集。第五章語(yǔ)法制導(dǎo)翻譯和中間代碼產(chǎn)生03二月202316三、綜合屬性

從語(yǔ)法分析樹(shù)的角度來(lái)看，如果一個(gè)結(jié)點(diǎn)的某一屬性，其值由子結(jié)點(diǎn)的屬性之值來(lái)計(jì)算，則稱(chēng)該屬性為綜合屬性。

綜合屬性用于“自下而上”傳遞信息。第五章語(yǔ)法制導(dǎo)翻譯和中間代碼產(chǎn)生03二月202317例1：算術(shù)表達(dá)式求值的屬性文法。規(guī)則式 語(yǔ)義規(guī)則1.L→E print(E.val)2.E→E1+T E.val:=E1.val+T.val3.E→T E.val:=T.val4.T→T1*F T.val:=T1.val*F.val5.T→F T.val:=F.val6.F→(E) F.val:=E.val7.F→digit F.val:=digit.lexval

與規(guī)則式關(guān)聯(lián)的每一個(gè)語(yǔ)義規(guī)則的左部符號(hào)E,T,F等的屬性值的計(jì)算由右部非終結(jié)符決定，這種屬性稱(chēng)為綜合屬性。第五章語(yǔ)法制導(dǎo)翻譯和中間代碼產(chǎn)生03二月202318LE.val=19F.val=5+T.val=4T.val=15F.val=4digit.lexval=4E.val=15T.val=3digit.lexval=5F.val=3digit.lexval=3*n求：3*5+4第五章語(yǔ)法制導(dǎo)翻譯和中間代碼產(chǎn)生03二月202319四、繼承屬性 語(yǔ)法樹(shù)分析中，若一個(gè)結(jié)點(diǎn)的某個(gè)屬性之值由該結(jié)點(diǎn)的兄弟結(jié)點(diǎn)和/或父結(jié)點(diǎn)的屬性之值來(lái)計(jì)算，則此結(jié)點(diǎn)的屬性稱(chēng)為繼承屬性。 繼承屬性用于“自上而下”傳遞信息。第五章語(yǔ)法制導(dǎo)翻譯和中間代碼產(chǎn)生03二月202320例2、說(shuō)明語(yǔ)句中簡(jiǎn)單變量類(lèi)型信息的屬性文法。 規(guī)則式 語(yǔ)義規(guī)則 1.D→TL L.in:=T.type 2.T→int T.type:=integer 3.T→real T.type:=real 4.L→L1,id L1.in:=L.in addtype(id.entry,L.in) 5.L→id addtype(id.entry,L.in)過(guò)程addtype把每一個(gè)標(biāo)識(shí)符id的類(lèi)型信息(由L.in繼承)登錄在符號(hào)表的相關(guān)項(xiàng)id.entry中。DTLintL,ididT有一個(gè)綜合屬性type，其值為integer或real。L.in由T.type確定后逐步傳遞到下邊有關(guān)結(jié)點(diǎn)使用。這種屬性稱(chēng)為繼承屬性。第五章語(yǔ)法制導(dǎo)翻譯和中間代碼產(chǎn)生03二月202321五、屬性的初始值①終結(jié)符號(hào)只有綜合屬性，它們由詞法分析器提供。②非終結(jié)符號(hào)既有綜合屬性也可有繼承屬性，文法開(kāi)始符號(hào)的所有繼承屬性作為屬性計(jì)算前的初始值。第五章語(yǔ)法制導(dǎo)翻譯和中間代碼產(chǎn)生03二月202322§5.6

語(yǔ)法制導(dǎo)翻譯法語(yǔ)法制導(dǎo)翻譯法的基本思想：對(duì)文法的每一條產(chǎn)生式，設(shè)計(jì)語(yǔ)義子程序。在語(yǔ)法分析的過(guò)程中，當(dāng)使用一條產(chǎn)生式推導(dǎo)或歸約時(shí)，調(diào)用該語(yǔ)義子程序進(jìn)行屬性計(jì)算，完成預(yù)定的翻譯工作。

語(yǔ)法制導(dǎo)翻譯法：在語(yǔ)法分析的過(guò)程中，依隨分析過(guò)程，根據(jù)每個(gè)產(chǎn)生式添加的語(yǔ)義動(dòng)作進(jìn)行翻譯的方法。第五章語(yǔ)法制導(dǎo)翻譯和中間代碼產(chǎn)生03二月202323語(yǔ)義子程序語(yǔ)義子程序也稱(chēng)為翻譯子程序，語(yǔ)義動(dòng)作。它描述了有關(guān)產(chǎn)生式所對(duì)應(yīng)的翻譯工作。語(yǔ)義動(dòng)作一方面指出了產(chǎn)生式所對(duì)應(yīng)的符號(hào)串的意義；另一方面又按照這種意義規(guī)定了對(duì)應(yīng)的屬性計(jì)算加工動(dòng)作。 語(yǔ)義動(dòng)作： 查填各種表格 計(jì)算某變量的值 生成某種中間代碼 打印錯(cuò)誤信息等等第五章語(yǔ)法制導(dǎo)翻譯和中間代碼產(chǎn)生03二月202324LR分析制導(dǎo)的具體實(shí)現(xiàn)方法1、為文法產(chǎn)生式設(shè)計(jì)語(yǔ)義子程序。2、為文法構(gòu)造一張無(wú)沖突的LR分析表。3、修改總控程序，歸約時(shí)調(diào)用語(yǔ)義子程序。4、擴(kuò)充LR分析棧，用來(lái)存放各文法符號(hào)對(duì)應(yīng)的語(yǔ)義信息。例如：(1).E→E1+E2 {E.val=E1.val+E2.val}(2).E→E1*E2 {E.val=E1.val*E2.val}(3).E→(E1) {E.val=E1.val}(4).E→digit {E.val=lex.digit}第五章語(yǔ)法制導(dǎo)翻譯和中間代碼產(chǎn)生03二月202325#第五章語(yǔ)法制導(dǎo)翻譯和中間代碼產(chǎn)生03二月202326擴(kuò)充的LR分析棧：???S0???#???-狀態(tài)棧文法符號(hào)棧語(yǔ)義值棧E.val=7E.val=1+E.val=61E.val=2*E.val=323(1).E→E1+E2

{E.val=E1.val+E2.val}(2).E→E1*E2

{E.val=E1.val*E2.val}(3).E→(E1) {E.val=E1.val}(4).E→digit {E.val=lex.digit}第五章語(yǔ)法制導(dǎo)翻譯和中間代碼產(chǎn)生03二月202327步驟狀態(tài)棧語(yǔ)義棧符號(hào)棧輸入符號(hào)動(dòng)作10-#1+2*3#S3203-#1+2*3#r4301-1#E+2*3#S44014-1-#E+2*3#S350143-1-#E+2*3#R460147-1-2#E+E*3#S5701475-1-2#E+E*3#S38014753-1-2-#E+E*3#R49014758-1-2-3#E+E*E#R2100147-1-6#E+E#R11101-7#E#acc第五章語(yǔ)法制導(dǎo)翻譯和中間代碼產(chǎn)生03二月202328§5.7中間語(yǔ)言常用的中間語(yǔ)言有:一、逆波蘭式二、三元式與間接三元式三、樹(shù)形表示法四、四元式第五章語(yǔ)法制導(dǎo)翻譯和中間代碼產(chǎn)生03二月202329一、逆波蘭式1、逆波蘭式（后綴式）：每一運(yùn)算符都置于其運(yùn)算對(duì)象之后。（無(wú)括號(hào)表達(dá)式）

中綴表示 后綴表示

A*B AB* A+B*C ABC*+ (A+B)*(C+D) AB+CD+*

(a==0&&b>3)||(e&&x!=y) a0==b3>&&exy!=&&|| 第五章語(yǔ)法制導(dǎo)翻譯和中間代碼產(chǎn)生03二月2023302、LR分析制導(dǎo)生成逆波蘭式文法：0 E′→E {空}1 E→E(1)+E(2) {print+}2 E→E(1)*E(2) {print*}3 E→(E(1)) {空}4 E→i {printi}步驟狀態(tài)棧符號(hào)棧輸入符號(hào)輸出區(qū)10#a+b*c#203#a+b*c#301#E+b*c#a4014#E+b*c#a50143#E+b*c#a60147#E+E*c#ab701475#E+E*c#ab8014753#E+E*c#ab9014758#E+E*E#abc100147#E+E#abc*1101#E#abc*+第五章語(yǔ)法制導(dǎo)翻譯和中間代碼產(chǎn)生03二月202331二、三元式與間接三元式一般形式：（op，AG1，AG2）例如：a:=-b*(c+d)三元式為：①（－，b，

）②（+，c，d）③（*，①，②）④（:=，③，a）第五章語(yǔ)法制導(dǎo)翻譯和中間代碼產(chǎn)生03二月202332間接三元式例如：語(yǔ)句 X:=(A+B)*C Y:=D^(A+B)間接代碼⑴⑵⑶⑴⑷⑸opAG1AG2⑴+AB⑵*⑴C⑶:=X⑵⑷^D⑴⑸:=Y⑷第五章語(yǔ)法制導(dǎo)翻譯和中間代碼產(chǎn)生03二月202333三、樹(shù)形表示法抽象語(yǔ)法樹(shù)：在語(yǔ)法樹(shù)中去掉那些對(duì)翻譯不必要的信息，從而獲得更有效的源程序中間表示。這種變換后的語(yǔ)法樹(shù)稱(chēng)為抽象語(yǔ)法樹(shù)。+* 43 5 3*5+4的抽象語(yǔ)法樹(shù)

第五章語(yǔ)法制導(dǎo)翻譯和中間代碼產(chǎn)生03二月202334樹(shù)形表示

A*B+C*D+C*A*BD末端結(jié)點(diǎn)表示一個(gè)運(yùn)算對(duì)象,每一個(gè)內(nèi)結(jié)點(diǎn)表示一個(gè)一元或二元運(yùn)算符。樹(shù)形表示是三元式的翻版(3)+(1)*(2)*CABD第五章語(yǔ)法制導(dǎo)翻譯和中間代碼產(chǎn)生03二月202335四、四元式

一般形式：(op，AG1，AG2，result)

直觀(guān)形式：result:=AG1opAG2例如：求x:=a+b*c的四元式。(*，b，c，T1) 直觀(guān)式： T1:=b*c(+，a，T1，T2) T2:=a+T1(:=，T2，，x) x:=T2第五章語(yǔ)法制導(dǎo)翻譯和中間代碼產(chǎn)生03二月202336

采用自下而上的語(yǔ)法制導(dǎo)翻譯法語(yǔ)義動(dòng)作的設(shè)計(jì)（1）搞清楚源結(jié)構(gòu)和目標(biāo)結(jié)構(gòu)（2）自下而上的語(yǔ)法制導(dǎo)翻譯特點(diǎn)：棧頂形成句柄，歸約時(shí)執(zhí)行相應(yīng)語(yǔ)義動(dòng)作（3）給出從源結(jié)構(gòu)到目標(biāo)結(jié)構(gòu)的變換方法§5.8自底向上語(yǔ)法制導(dǎo)翻譯第五章語(yǔ)法制導(dǎo)翻譯和中間代碼產(chǎn)生03二月202337例.設(shè)文法及其相應(yīng)的語(yǔ)義動(dòng)作如下:S→a{print“2”}S→bTc{print“1”}T→R{print“3”}R→R/S{print“4”}R→S{print“5”}采用自下而上語(yǔ)法制導(dǎo)翻譯,給出輸入串bR/bTc/bSc/ac的翻譯結(jié)果第五章語(yǔ)法制導(dǎo)翻譯和中間代碼產(chǎn)生03二月202338分析:首先對(duì)輸入串bR/bTc/bSc/ac畫(huà)出語(yǔ)法樹(shù):ScTbRS/R/RS/RcTbaScTbRS再考慮歸約時(shí)執(zhí)行相應(yīng)語(yǔ)義動(dòng)作第五章語(yǔ)法制導(dǎo)翻譯和中間代碼產(chǎn)生03二月202339ScTbRS/R/RS/RcTbaScTbRSS→bTc{print“1”}S→a{print“2”}T→R{print“3”}R→R/S{print“4”}R→S{print“5”}14翻譯結(jié)果為:53142431第五章語(yǔ)法制導(dǎo)翻譯和中間代碼產(chǎn)生03二月202340一、簡(jiǎn)單算術(shù)表達(dá)式和賦值語(yǔ)句的翻譯定義幾個(gè)過(guò)程和函數(shù)：lookup()：檢查是否出現(xiàn)在符號(hào)表中，如果在，則返回其指針；否則，返回NULL表示沒(méi)有找到。emit（result:=AG1opAG2）：產(chǎn)生一個(gè)四元式，并填入四元式表中。newtemp()：該函數(shù)返回一個(gè)新的臨時(shí)變量。第五章語(yǔ)法制導(dǎo)翻譯和中間代碼產(chǎn)生03二月202341文法：P2161.S→i=E{p＝Lookup();if(p==NULL)error();elseemit(p’＝’E.place}2.E→E(1)＋E(2){E.place＝newtemp();emit(E.place’＝’E(1).place’＋’E(2).place)}3.E→E(1)*E(2){E.place＝newtemp();emit(E.place’＝’E(1).place’*’E(2).place)}4.E→（E(1)）{E.place＝E(1).place；}5.E→i{p＝Lookup();if(p!=NULL)E.place＝p;elseerror();}第五章語(yǔ)法制導(dǎo)翻譯和中間代碼產(chǎn)生03二月202342 算術(shù)表達(dá)式a+b*c翻譯到三地址語(yǔ)句的過(guò)程：

030$$a01$E014$E+0143$E+b－a－a－－a－－狀態(tài)棧符號(hào)棧語(yǔ)義棧輸入串a(chǎn)+b*c$+b*c$+b*c$b*c$*c$－－－第五章語(yǔ)法制導(dǎo)翻譯和中間代碼產(chǎn)生03二月202343*c$c$$$$$t1=b*ct2=a+t1

狀態(tài)棧符號(hào)棧語(yǔ)義棧輸入串014750147$E+E$E+E*014753$E+E*c014758$E+E*E0147$E+E01$E－a－b－－－a－b－c－a－t1－a－b－－a－b－t2acc第五章語(yǔ)法制導(dǎo)翻譯和中間代碼產(chǎn)生03二月202344二、布爾表達(dá)式的翻譯 1、E→E∨E 2、E→E∧E 3、E→E 4、E→(E) 5、E→idropid 6、E→id第五章語(yǔ)法制導(dǎo)翻譯和中間代碼產(chǎn)生03二月2023451、類(lèi)似算術(shù)表達(dá)式的翻譯方法 （求每個(gè)因子，再求表達(dá)式的值）例如： 布爾表達(dá)式： a∨b∧c

三地址序列： T1:=c T2:=b∧T1 T3:=a∨T2第五章語(yǔ)法制導(dǎo)翻譯和中間代碼產(chǎn)生03二月2023461.E→E(1)∨E(2){E.place＝newtemp()；emit(E.place’＝’E(1).place’∨’E(2).place)}2.E→E(1)∧E(2){E.place＝newtemp()；emit(E.place’＝’E(1).place’∧’E(2).place)}3.E→E(1){E.place＝newtemp()；emit(E.place’＝’’’

E(1).place}4.E→(E(1)){E.place＝E(1).place；}5.E→i(1)ropi(2){E.place＝newtemp()；emit(‘if’i(1).placerop.opi(2).place‘goto’next+3);emit(E.place’＝’‘0’);emit(gotonext+2);emit(E.place’＝’‘1’);}6.E→i

{E.place＝i.place；}第五章語(yǔ)法制導(dǎo)翻譯和中間代碼產(chǎn)生03二月202347EE∨Ea<bE∧Ec<de<f第五章語(yǔ)法制導(dǎo)翻譯和中間代碼產(chǎn)生03二月2023482、根據(jù)布爾表達(dá)式的特殊性采取某種優(yōu)化措施A∨B ifAthentrunelseBA∧B ifAthenBelsefalseA ifAthenfalseelsetrue①對(duì)非終結(jié)符E賦予兩個(gè)出口真出口：布爾表達(dá)式為真時(shí)，需轉(zhuǎn)移的四元式地址。假出口：布爾表達(dá)式為假時(shí)，需轉(zhuǎn)移的四元式地址。第五章語(yǔ)法制導(dǎo)翻譯和中間代碼產(chǎn)生03二月202349②設(shè)置兩個(gè)語(yǔ)義變量：E.ture:用來(lái)記錄表達(dá)式E對(duì)應(yīng)的四元式需回填真出口的四元式的地址所構(gòu)成的鏈。E.false:用來(lái)記錄表達(dá)式E對(duì)應(yīng)的四元式需回填假出口的四元式的地址所構(gòu)成的鏈。③定義三個(gè)函數(shù)：第五章語(yǔ)法制導(dǎo)翻譯和中間代碼產(chǎn)生03二月202350鏈接函數(shù)merge(P1,P2)：把以P1和P2為鏈?zhǔn)椎膬蓷l鏈合并為一，返回合并后的鏈?zhǔn)祝ó?dāng)P2=0時(shí)，返回P1;當(dāng)P2≠0時(shí)，返回P2）。

intmerge(intP1,intP2){ intP; if(!P2)returnP1; else{ P=P2; while(P.result<>0) P=P.result; P.result=P1; returnP2;}第五章語(yǔ)法制導(dǎo)翻譯和中間代碼產(chǎn)生03二月202351回填函數(shù)backpatch(p,t)：把p所鏈接的每個(gè)四元式的第四分量都回填為t。 voidBP(intp,intt){ intq=p; while(q){ intq1=q.result; q.result=t; q=q1; } return; }建鏈函數(shù)makelist(i)：創(chuàng)建一個(gè)僅含i的新鏈表。第五章語(yǔ)法制導(dǎo)翻譯和中間代碼產(chǎn)生03二月202352④定義三種四元式：(jnz,a,-,p) ifagotop(當(dāng)a為真時(shí)轉(zhuǎn)向第p四元式）(jrop,x,y,p) ifxropygotop(j,-,-,p) gotop(無(wú)條件轉(zhuǎn)向第p四元式)⑤四元式表的指針nextquad（nextq）：每執(zhí)行一次emit后，nextq自動(dòng)加1。⑥E.code：為及時(shí)回填轉(zhuǎn)移地址,使用語(yǔ)義變量E.code記錄表達(dá)式E的第一個(gè)四元式語(yǔ)句序號(hào)。第五章語(yǔ)法制導(dǎo)翻譯和中間代碼產(chǎn)生03二月2023531.E→i {E.tr=next; E.fa=next+1; E.code=next;emit(ifi.placegoto-);emit(goto_);}2.E→i(1)ropi(2){E.tr=next; E.code=next; E.fa=next+1;emit(ifi(1).placerop.opi(2).placegoto_); emit(goto_);

}3.E→(E(1)){E.code=E