《編譯原理實(shí)踐及應(yīng)用》第5章中間代碼生成5

語義分析和中間代碼生成第五章

本章要求主要內(nèi)容：語義分析和中間代碼生成的功能，中間代碼的形式，屬性文法及語法制導(dǎo)的翻譯程序，各種語句的語法制導(dǎo)的翻譯過程重點(diǎn)掌握：屬性文法，語義分析與處理的方法,中間代碼的表示形式，各種語句的代碼結(jié)構(gòu)，各種語句的翻譯方法語義分析和中間代碼生成所處的位置：5.1概述１.語義分析和中間代碼生成在編譯器中的位置：靜態(tài)語義檢查：如：類型、運(yùn)算、數(shù)組維數(shù)、越界等的檢查語義處理：如：變量的存儲分配、表達(dá)式的求值、語句的翻譯(中間代碼的生成)總目標(biāo)：生成等價的中間代碼語法分析語義分析和中間代碼生成編譯的后續(xù)階段語法樹中間代碼２.功能及任務(wù)：輸入-語法分析單位輸出

-用中間代碼形式表示的文本

-出錯處理:定位、繼續(xù)編譯3.為什么要此階段?邏輯結(jié)構(gòu)清楚；利于不同目標(biāo)機(jī)上實(shí)現(xiàn)同一種語言；利于進(jìn)行與機(jī)器無關(guān)的優(yōu)化，這些內(nèi)部形式也能用于解釋。4.什么是中間代碼(Intermediatecode)源程序的一種內(nèi)部表示，不依賴目標(biāo)機(jī)的結(jié)構(gòu)，易于機(jī)械生成目標(biāo)代碼的中間表示。5.中間代碼的幾種形式逆波蘭、三元式、間接三元式、四元式、樹1、逆波蘭式：運(yùn)算對象寫在前，運(yùn)算符寫在后(后綴表示形式)例：a+bab+

(a+b)*cab+c*

a+b*cabc*+

a:=b*c+b*d

abc*bd*+:=5.2中間代碼的幾種形式+ab優(yōu)點(diǎn)：易于計算機(jī)處理

利用棧，將掃描到的運(yùn)算對象入棧，碰到運(yùn)算符：若是雙目運(yùn)算符，則對棧頂?shù)膬蓚€運(yùn)算對象實(shí)施該運(yùn)算并將運(yùn)算結(jié)果代替這兩個運(yùn)算對象進(jìn)棧；若是單目運(yùn)算符，對棧頂元素，執(zhí)行該運(yùn)算，將運(yùn)算結(jié)果代替該元素進(jìn)棧，最后結(jié)果即棧頂元素。練習(xí)寫出下列算式的逆波蘭表示a+b*(c+d/e)a:=b*(-c)+b*(-34)notAornot(CornotD)abcde/+*+abc-*b34-*+:=AnotCDnotornotor+a*b+c/de后綴式的推廣(1)賦值語句A:=E，后綴式為：AE:=(2)轉(zhuǎn)向語句GOTOL的后綴式為：L’jmp(3)條件語句ifx>ythenm:=xelsem:=y1234567891011121314xy>11jezmx:=14jmy:=…2、三元式編號（運(yùn)算符，第一運(yùn)算數(shù)，第二運(yùn)算數(shù)）如：a：=b*c+b*d (1)（*，b，c）

(2)（*，b，d）

(3)（+，(1)，(2)）

(4)（：=，(3)，a）對于單目運(yùn)算符，只有一個運(yùn)算對象，另一個為空注意：在三元式中的編號既代表了序號，又代表了結(jié)果的存放位置。3、四元式

是目前最常用的中間代碼形式:

(運(yùn)算符，第一運(yùn)算數(shù)，第二運(yùn)算數(shù)，結(jié)果)例：a:=b*c+b*d

(1)(*,b,c,t1)

(2)(*,b,d,t2)

(3)(+,t1,t2,t3)

(4)(:=,t3,,a)

也可以寫成賦值語句形式：

(1)t1:=b*c

(2)t2:=b*d

(3)t3:=t1+t2(4)a:=t3練習(xí)求-B+C*D

的逆波蘭表示形式、三元式和四元式逆波蘭：B–CD*+三元式：(1)(-,B,)(2)(*,C,D)(3)(+,(1),(2))四元式：(1)(-,B,,t1)(2)(*,C,D,t2)(3)(+,t1,t2,t3)到目前為止，已知輸入的語法單位，

又知道要翻譯的結(jié)果的形式，

翻譯的方法是什么？語義分析和翻譯的方法：語義表示較流行的方法仍然是屬性文法，翻譯方法是語法制導(dǎo)的翻譯。5.3屬性文法與語法指導(dǎo)的翻譯屬性文法:是在上下文無關(guān)文法的基礎(chǔ)上，為每個文法符號(含終結(jié)符和非終結(jié)符)配備若干個屬性值，對文法的每個產(chǎn)生式都配備了一組屬性計算規(guī)則(稱為語義規(guī)則)。在語法分析過程中，完成語義規(guī)則所描述的動作，從而實(shí)現(xiàn)語義處理。屬性：代表與文法符號相關(guān)的信息，如類型、值、代碼序列、符號表的內(nèi)容等。與變量一樣，可以進(jìn)行計算和傳遞，屬性的加工過程就是語義的處理過程。屬性分兩類：綜合屬性：用于自下而上傳遞信息繼承屬性：用于自上而下傳遞信息注意：終結(jié)符只有綜合屬性，它由詞法分析器提供；非終結(jié)符可有綜合屬性，也可有繼承屬性，它由詞法分析器提供；文法的開始符號的所有繼承屬性作為屬性計算前的初始值綜合屬性繼承屬性產(chǎn)生式右邊的文法符號的繼承屬性可以繼承左邊的文法符號的繼承屬性產(chǎn)生式左邊的文法符號可以通過綜合右邊的文法符號的綜合屬性而得到但必須提供一個計算規(guī)則：計算規(guī)則中只能使用相應(yīng)產(chǎn)生式中的文法符號的屬性。實(shí)際應(yīng)用中，一個結(jié)點(diǎn)的綜合屬性的值由其子結(jié)點(diǎn)的綜合屬性值決定(產(chǎn)生式右邊)。一個結(jié)點(diǎn)的繼承屬性由此結(jié)點(diǎn)的父結(jié)點(diǎn)和/或兄結(jié)點(diǎn)的某些屬性決定(產(chǎn)生式左邊)。但產(chǎn)生式左邊的繼承屬性和右邊的綜合屬性不由所給的產(chǎn)生式的屬性計算規(guī)則進(jìn)行計算，它們由其它產(chǎn)生式的屬性計算規(guī)則提供。digitlexval:=3Fval:=3Tval:=3Fval:=5Tval:=15*Eval:=15+digitlexval:=4Fval:=4Tval:=4Eval:=19Ln0．L→En1．E→E1+T2．E→T3．T→T1*F4．T→F5．F→(E)6．F→digitprint(E.val)E.val:=E1.val+t.valE.val:=T.valT.val:=T1.val*F.valT.val:=F.valF.val:=E.valF.val:=digit.lexvaldigitlexval:=5若輸入符號串為：3*5+4n例：綜合屬性的計算C語言中變量定義：intid1,id2,id3綜合屬性的傳遞繼承屬性的傳遞例：繼承屬性的計算產(chǎn)生式語義規(guī)則DTLT

intTrealLL1,idLidL.in:=T.typeT.type=integerT.type:=realaddtype(id.entry,L.in)L1.in:=L.inaddtype(id.entry,L.in)語義規(guī)則描述的工作：屬性計算、靜態(tài)語義檢查、符號表的操作、代碼生成等，通常寫成過程和函數(shù)調(diào)用，稱為語義子程序。語義翻譯常用的方法：語法制導(dǎo)翻譯：定義翻譯所必須的語義屬性和語義規(guī)則，一般不涉及計算順序。語法制導(dǎo)翻譯技術(shù)語法制導(dǎo)翻譯(Syntax-DirectedTranslations)：一個句子的語義翻譯過程與語法分析過程同時進(jìn)行。在文法中，文法符號有明確的意義，文法符號之間有確定的語義關(guān)系。屬性描述語義信息，語義規(guī)則描述屬性間的的關(guān)系，將語義規(guī)則與語法規(guī)則相結(jié)合，在語法分析的過程中計算語義屬性值。語法制導(dǎo)翻譯的處理方法對應(yīng)每一個產(chǎn)生式編制一個語義子程序，在進(jìn)行語法分析的過程中，當(dāng)一個產(chǎn)生式獲得匹配時，就調(diào)用相應(yīng)的語義子程序?qū)崿F(xiàn)語義檢查與翻譯。即在自下而上語法分析的過程中，每一次歸約時就調(diào)用相應(yīng)的語義子程序。在產(chǎn)生式的右部的適當(dāng)位置，插入相應(yīng)的語義動作，按照分析的進(jìn)程，執(zhí)行遇到的語義動作。語義子程序一個語義子程序描述了一個產(chǎn)生式對應(yīng)的翻譯工作。主要有：改變編譯程序某些變量的值、查填各種符號表、發(fā)現(xiàn)并報告源程序錯誤、產(chǎn)生中間代碼。在描述語義動作時需要為每個文法符號賦以各種不同的語義值，如類型、地址、代碼值等。如果一個產(chǎn)生式中一個符號多次出現(xiàn)，就用上角標(biāo)來區(qū)分，如：E=E(1)+E(2)語義子程序的一般形式語義子程序?qū)懺谠摦a(chǎn)生式后面的花括號內(nèi)：(1)X…{語義子程序1}(2)Y…{語義子程序2}(3)AXY{語義子程序3}例：臺式計算器程序的語義子程序描述：產(chǎn)生式 語義子程序(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)Ei {E.VAL:=LEXVAL}常見的語法制導(dǎo)翻譯類型：語法分析采用自下而上方法時，使用與語法分析棧同步操作的語義棧進(jìn)行語法制導(dǎo)翻譯。語法分析采用遞歸下降分析方法時，利用隱含堆棧存儲各遞歸子程序中的局部變量所表示的語義信息語法分析采用LL(1)分析法時，利用翻譯文法進(jìn)行語法制導(dǎo)的翻譯。翻譯文法是在描述語言的文法中加入語義動作的符號。利用屬性文法進(jìn)行翻譯。屬性文法也是一種翻譯文法，它的文法符號和動作符號都帶有語義屬性和同一產(chǎn)生式中各屬性間的運(yùn)算規(guī)則。自下而上的語法制導(dǎo)翻譯舉例為了正確理解，需要弄清楚：自下而上翻譯的特點(diǎn)各種語句的目標(biāo)結(jié)構(gòu)從源到目標(biāo)的變換方法自下而上翻譯的特點(diǎn)使用上圖形式的棧實(shí)現(xiàn)——增加語義棧用X.Val表示文法符號X的語義信息。語義信息與文法符號同時出棧和入棧下面以一個例子來說明自底向上的翻譯方法例1：下面是一個算術(shù)表達(dá)式文法，每個產(chǎn)生式右邊是它的語義動作，對輸入串２*3+2的規(guī)范歸約的分析過程如下：例2：在3*5＋4的LR分析過程中增加了語義棧后的語法制導(dǎo)的實(shí)現(xiàn)過程。(1)EE+T|T(2)TT*F|F(3)F(E)|i狀態(tài)actiongotoabcd#EAB0

1

2

3

4

5

6

7

8

9

10

11S2

.

.

.

.

.

r1

r2

r3

r5

r4

r6S3

.

.

.

.

.

r1

r2

r3

r5

r4

r6.

.

S4

S5

S4

S5

r1

r2

r3

r5

r4

r6.

.

S10

S11

S10

S11

r1

r2

r3

r5

r4

r6..

acc

..

.

.

.

r1

r2

r3

r5

r4

r61.

.

6

.

8.

.

.

7

.

9序號狀態(tài)棧符號棧語義棧歸約產(chǎn)生式輸入串10#-3*5+4#205#3--*5+4#303#F-3Fi*5+4#402#T-3TF*5+4#5027#T*-3-5+4#60275#T*5-3--+4#702710#T*F-3-5Fi+4#802#T-15TT*F+4#901#E-15ET+4#10016#E+-15-4#110165#E+4-15--#120163#E+F-15-4Fi#130169#E+T-15-4TF#1401#E-19EE+T#15接受結(jié)論在剛才的翻譯過程中有如下特點(diǎn)：句柄歸約在先，語義動作在后。歸約時，棧內(nèi)句柄各符號的語義信息與該句柄同時出棧，整個句柄所表示的語義信息則賦給相應(yīng)產(chǎn)生式左部非終結(jié)符的語義變量，并讓該非終結(jié)符及其語義變量同時入棧。為了在某處調(diào)用語義動作，就必須先歸約，因此，有時需要改寫文法。5.4常見語句的語法制導(dǎo)的翻譯高級語言的語句分類：說明語句——定義各種名字的屬性可執(zhí)行語句——用于完成指定的功能，涉及到指令代碼語義翻譯也分兩類：翻譯說明語句時，將所定義的名字的各種屬性登記到符號表中翻譯可執(zhí)行語句時，首先應(yīng)根據(jù)各源語句的語法結(jié)構(gòu)和語義設(shè)計出它的目標(biāo)代碼結(jié)構(gòu)，找出源與目標(biāo)的對應(yīng)關(guān)系，給出對信息(數(shù)據(jù)表示)描述和從源到目標(biāo)的變換算法。語義子程序則根據(jù)變換方法進(jìn)行翻譯。說明語句的翻譯說明語句的作用：就是說明類型等屬性信息，在翻譯時主要是填符號表說明語句分多種，此處舉例兩種的翻譯：變量說明語句的翻譯常量說明語句的翻譯變量說明語句的翻譯１.變量說明語句的文法描述２.變量說明語句的翻譯例如：vara,b,c:integer;策略：先翻譯第３，４產(chǎn)生式，再翻譯２，１產(chǎn)生式，以便記錄<IDS>的類型，即在寫程序時，讀完一個說明語句，開始?xì)w約，再開始翻譯，變量的類型朝前傳遞。３.翻譯的語義動作FILL(entry(i),Type)表示將類型Type填入符號表中entry(i)表示變量名i在符號表中的入口NameTYPEKINDVALADDRa4integer符號表：VARid1,id2,id3:integer;的歸約過程integer:id3<IDS>,,id2id2<IDS>,,,id1id1id1<IDS>VARVARVARVAR…………………………(a)(b)(c)(d)(e)常量說明語句的翻譯１.常量說明語句的文法描述２.常量說明語句的翻譯策略：和變量說明一樣，先翻譯后面的產(chǎn)生式，再翻譯前面的產(chǎn)生式，以便在歸約時，執(zhí)行語義動作，將常量的值、類型、種屬填入符號表。例：ConstantA=123３.翻譯的語義動作將常量INT在符號表中的入口或值直接填入常量符號i所指符號表的VAL欄將常數(shù)的類型填入符號表的Type欄3，4產(chǎn)生式的翻譯與5，6產(chǎn)生式的翻譯相同1，2產(chǎn)生式?jīng)]有語義動作NameTYPEKINDVALADDRA4integer數(shù)值常數(shù)123將常數(shù)的種屬填入符號表的Kind欄可執(zhí)行語句的翻譯定義的一些語義變量和過程GENCODE(OP,ARG1,ARG2,RESULT)：語義過程，產(chǎn)生一個四元式，并填入四元式表，編號自動增1

。NEWT：函數(shù)，返回一個臨時變量序號。在翻譯可執(zhí)行語句的過程中，可能需要使用臨時變量，假定用NEWT過程來申請臨時變量Ti，每申請一次，i增1。ENTRY(i)：函數(shù)，查找變量i的入口地址；檢查是否在符號表中，如在則返回一指向該登陸項的指針，否則返回NULLE.PLACE：與給終結(jié)符E相聯(lián)系的語義變量，可能是某變量的入口地址，或者為臨時變量序號。簡單賦值語句的翻譯１.簡單賦值語句的文法描述2.簡單賦值語句的代碼結(jié)構(gòu)例如：x:=2+3*2;3.簡單賦值語句的翻譯

此處只假定是整數(shù)運(yùn)算例：賦值句A:=B+C*(-D)的自底向上分析

設(shè)：翻譯此賦值句之前四元式的最大編號為K因此，四元式表中增加了4條四元式：K…（翻譯此賦值語句之前的四元式）K+1(@i，F(xiàn)D·PLACE，_，F(xiàn)D'·PLACE)K+2(*i，Tc·PLACE，F(xiàn)D''·PLACE，T'·PLACE)K+3(+i，EB·PLACE，T'·PLACE，E·PLACE)K+4(:=，E·PLACE，_，ENTRY(iA))布爾表達(dá)式的翻譯3.布爾表達(dá)式的文法描述１.布爾表達(dá)式的作用 用作控制語句中的條件表達(dá)式 用在邏輯賦值語句中2.布爾表達(dá)式的形式(1)單個布爾量;(2)布爾量的運(yùn)算not,and,or,優(yōu)先級比關(guān)系運(yùn)算高;(3)關(guān)系運(yùn)算:E1ropE2,E1E2是算術(shù)表達(dá)式，rop為關(guān)系運(yùn)算符:>,<,>=,<=,=（1）<BE>→<BE>or<BT>（2）<BE>→<BT>（3）<BT>→<BT>and<BF>（4）<BT>→<BF>（5）<BF>→not<BF>（6）<BF>→(<BE>)（7）<BF>→<AE>rop<AE>（8）<BF>→iropi（9）<BF>→i例如：x:=notaand(y>z);布爾量翻譯為兩條四元式：(jnz,A,_,P):真出口，當(dāng)A為真時跳轉(zhuǎn)到四元式P(j,_,_,q):假出口，無條件跳轉(zhuǎn)到四元式q關(guān)系表達(dá)式也翻譯為兩條四元式：(jrop,i1,i2,P):真出口，當(dāng)i1ropi2為真時轉(zhuǎn)四元式P(j,_,_,q):假出口，無條件跳轉(zhuǎn)到四元式q3.布爾量的代碼結(jié)構(gòu)每個布爾量(布爾變量或關(guān)系表達(dá)式)的目標(biāo)結(jié)構(gòu)有兩個出口，真出口指向?yàn)檎鏁r應(yīng)跳轉(zhuǎn)的位置；假出口指向?yàn)榧贂r應(yīng)跳轉(zhuǎn)的位置。類似于編寫匯編代碼AA.TCA.FC在翻譯布爾表達(dá)式時，后面的語句未翻譯，P,q如何知道？解決方法是：回填技術(shù)已知就直接填入；不知時先填0，等知道后再返填若多個因子的轉(zhuǎn)移去向相同，但又不知道具體位置，應(yīng)該用鏈將這些未知且出口相同的四元式鏈在一起。布爾表達(dá)式:AandBandC>D的四元式為：假出口未知，填入0當(dāng)掃描到and時，對A進(jìn)行歸約，產(chǎn)生兩個四元式1，2，其中真出口已知，為3當(dāng)掃描到B后的and時，對B進(jìn)行歸約，又產(chǎn)生兩個四元式3，4，其中真出口已知，為5假出口仍未知，但它與A的假出口相同，則鏈接起來，填2當(dāng)掃描到最后，對C>D進(jìn)行歸約，又產(chǎn)生兩個四元式5，6，此時真出口未知，填0假出口仍未知，但它與上兩個布爾量的假出口相同，則鏈接起來，填4生成了真、假出口兩個鏈，兩個0就是待填部分。等到以后翻譯到后面再填入。將P1,P2為鏈?zhǔn)變蓚€四元式鏈合并在一起，可以用下述過程，返回合并后的四元式鏈?zhǔn)祝簃erge(P1，P2){ifP2==0)return(P1);else{P:=P2;while(四元式P的第4分量內(nèi)容不為0)doP:=四元式P的第4分量內(nèi)容；把P1填進(jìn)四元式P的第4分量；

return(P2);}}假出口鏈上的四元式應(yīng)轉(zhuǎn)向相同的位置，所以一旦知道轉(zhuǎn)向的真實(shí)位置，就應(yīng)返填，返填是將已知位置填入鏈上的所有四元式的第四個分量。用backpatch，把已知位置t填入以P為鏈?zhǔn)椎乃脑街校築ACKPATCH(P，t){Q:=P;while(Q!=0)do{m:=四元式Q的第4分量內(nèi)容；把t填進(jìn)四元式Q的第4分量；

Q:=m;}}4.布爾表達(dá)式的翻譯布爾表達(dá)式是帶有not,and,or的表達(dá)式第一種翻譯方法可以象算術(shù)表達(dá)式一樣翻譯，先計算每個因子的值，再計算整個表達(dá)式的值。第二種翻譯方法采取優(yōu)化措施進(jìn)行翻譯。E1orT的優(yōu)化：只要E為真，后面的表達(dá)式就不必計算，只有當(dāng)E為假時才讀取T，目標(biāo)結(jié)構(gòu)如下：E1andT的優(yōu)化：只要E為假，后面的表達(dá)式就不必計算，只有當(dāng)E為真時才讀取T，目標(biāo)結(jié)構(gòu)如下：如果是翻譯notE1，則E的真假出口正好與E1相反5.翻譯布爾表達(dá)式時，當(dāng)讀到not,and,or時，要進(jìn)行歸約，因此應(yīng)對文法進(jìn)行改造，改造前后的文法為：（1）<BE>→<BE>or<BT>（2）<BE>or→<BE>or（3）<BE>→<BT>（4）<BT>→<BT>and<BF>（5）<BT>and→<BT>and（6）<BT>→<BF>（7）<BF>→(<BE>)（8）<BF>→not<BF>（9）<BF>→<AE>rop<AE>（10）<BF>→iropi（11）<BF>→i改造后的文法（1）<BE>→<BE>or<BT>（2）<BE>→<BT>（3）<BT>→<BT>and<BF>（4）<BT>→<BF>（5）<BF>→not<BF>（6）<BF>→(<BE>)（7）<BF>→<AE>rop<AE>（8）<BF>→iropi（9）<BF>→i改造前的文法

6.總結(jié)前面的分析，各產(chǎn)生式的翻譯為：NXQ表示當(dāng)前產(chǎn)生的四元式的編號單個的布爾量關(guān)系運(yùn)算Not邏輯運(yùn)算帶算術(shù)運(yùn)算的關(guān)系運(yùn)算產(chǎn)生式6:<BT>→<BF>，3:<BE>→<BT>的翻譯與7相似，都是將右邊的真假出口直接賦值到左邊(5)(4)構(gòu)成and邏輯運(yùn)算(2)(1)構(gòu)成or邏輯運(yùn)算控制語句的翻譯控制語句包括：

if語句While語句Repeat語句For語句IF語句的翻譯1.IF語句的文法(S是開始符號)產(chǎn)生式(1),(4)生成無else的IF語句結(jié)構(gòu)產(chǎn)生式(1),(2),(3)生成if–then–else的語句結(jié)構(gòu)（1）S→CS(1)（2）C→ifEthen（3）S→TS(2)（4）T→CS(1)else2.IF語句的目標(biāo)結(jié)構(gòu)及其翻譯無else的結(jié)構(gòu)C.Chain的作用：由于在用第一個產(chǎn)生式進(jìn)行歸約時，只生成了條件式E的代碼，then時可以回填E.TC,E.FC必須向后傳遞到下一各產(chǎn)生式中。ifa>bthenx:=3;（1）S→CS(1){S·CHAIN:=MERG(C·CHAIN，S(1)·CHAIN)}（2）C→ifEthen{BACKPATCH(E·TC，NXQ);C·CHAIN:=E·FC}2.IF語句的目標(biāo)結(jié)構(gòu)及其翻譯有else的結(jié)構(gòu)ifa>bthenx:=3elsex:=5;(1)C→ifEthen{BACKPATCH(E·TC，NXQ);C·CHAIN:=E·FC}(2)S→TS(2){S·CHAIN:=MERG(T·CHAIN，S(2)·CHAIN)}(3)T→CS(1)else{q:=NXQ;GENCODE(j，_，_，0);BACKPATCH(C·CHAIN，NXQ);T·CHAIN:=MERG(S(1)·CHAIN，q)}例：將下面的IF語句翻譯為四元式序列ifAandBand(C>D)thenifA<BthenF:=1elseF:=0elseG:=G+1

1.(jnz,A,_,3)/*A的四元式*/2.(j,_,_,13)3.(jnz,B,_,5)/*B的四元式*/4.(j,_,_,13)5.(j>,C,D,7)/*C>D的四元式*/6.(j,_,_,13)7.(j<,A,B,9)/*A<B的四元式*/8.(j,_,_,11)9.(:=,1,_,F)/*F

:=1的四元式*/10.(j,-,-,15)11.(:=,0,_,F)/*F

:=0的四元式*/12.(j,_,_,15)13.(+,G,1,T)/*G:=G+1的四元式*/14.(:=,T,_,G)15.

練習(xí):將下面的語句翻譯為四元式序列if(A<C)and(B<D)thenifA=1thenC:=C+1

elseifA≤DthenA:=A+2;

1.(j<,A,C,3)2.(j,-,-,14)3.(j<,B,D,5)4.(j,-,-,14)5.(j=,A,1,7)6.(j,-,-,10)7.(+,C,1,T1)8.(:=,T,-,C)9.(j,-,-,14)10.(j<=,A,D,12)11.(j,-,-,14)12.(+,A,2,T2)13.(:=,T2,-,A)14.

REPEAT語句的翻譯1.文法描述2.目標(biāo)結(jié)構(gòu)(1)R→repeat(2)U→RS(1)until(3)S→UE例：repeatx:=x+1untilx>10;3.翻譯（1）R→repeat{R·HEAD:=NXQ}（2）U→RS(1)until{U·HEAD:=R·HEAD;BACKPATCH(S(1)·CHAIN，NXQ)}（3）S→UE{BACKPATCH(E·FC，U·HEAD);S·CHAIN:=E·TC}將下面的語句翻譯為四元式序列Ifw<1thena:=b*c+delserepeata:=a-1untila<0;1.(j<,w,1,3)2.(j,,,7)3.(*,b,c,t1)4.(+,t1,d,t2)5.(:=,t2,,a)6.(j,,,11)7.(-,a,1,t3)8.(:=,t3,,a)9.(j<,a,0,11)10.(j,,,7)FOR語句的翻譯1.文法描述2.目標(biāo)結(jié)構(gòu)(1)F→fori:=E(1)toE(2)do(2)S→FS(1)例：fori:=1toa+bdox:=x+I;FOR語句的翻譯fori:=1toa+bdox:=x+I;(1)F→fori:=E(1)toE(2)do{F·PLACE:=ENTRY(i);GENCODE(:=，E(1)·PLACE，_，F(xiàn)·PLACE);T1:=NEWT;/*T1用于存放循環(huán)終值*/GENCODE(:=，E(2)·PLACE，_，T1);q:=NXQ;/*OVER=q+2*/GENCODE(j，_，_，q+2);F·AGAIN:=q+1;GENCODE(+，F(xiàn)·PLACE，1，F(xiàn)·PLACE);F·CHAIN:=NXQ;GENCODE(j>，F(xiàn)·PLACE，T1，0)}(2)S→FS(1){BACKPATCH(S(1)·CHAIN，F(xiàn)·AGAIN);GENCODE(j，_，_，F(xiàn)·AGAIN);S·CHAIN:=F·CHAIN}將下面的語句翻譯為四元式序列fori:=a+b*2toc+d+10do

ifh>gthenp:=p+1;1(*,b,2,t1)2(+,a,t1,t2)3(+,c,d,t3)4(+,t3,10,t4)5(:=,t2,,i)6(:=,t4,,t)7(j,,,10)8(+,I,1,t5)9(:=,t5,,i)10(j>,I,t,12)11(j,,,17)12(j>,h,g,14)13(j,,,8)14(+,p,1,t6)15(:=,t6,,p)16(j,,,8)175.5Sample語言語法制導(dǎo)翻譯程序的設(shè)計語法制導(dǎo)的翻譯實(shí)際上就是在語法分析的基礎(chǔ)上，當(dāng)分析完一個正確的語法單位后，調(diào)用相應(yīng)的語義處理程序，直接生成相應(yīng)的四元式表。在第4章使用遞歸下降的分析方法進(jìn)行了Sample語言的語法分析器在此基礎(chǔ)上添加語義處理舉例：為IF語句添加語義處理ifs(){/*If語句的語法分析*/token=getnexttoken();

If(token!="if")error;token=getnexttoken();

bexp();token=getnexttoken();

If(token!="then")error;token=getnexttoken();ST_SORT();/*調(diào)用函數(shù)處理then后的可執(zhí)行語句*/token=getnexttoken();

If(token!="else")error;token=getnexttoken();ST_SORT();/*處理else后的可執(zhí)行語句*/}<if語句>::=if<布爾表達(dá)式>then<執(zhí)行句>else<執(zhí)行句>ifs(){/*添加語義處理后的程序*/token=getnexttoken();If(token!=“if”)error;token=getnexttoken();

(e.tc,e.fc)=bexp();

token=getnexttoken();if(token！="then")error("缺then");

backpatch(e.tc,nxq);

/*回填真出口e.tc*/

token=getnexttoken();

s1.chain=ST_SORT(token);/*處理s1,返回s1鏈*/

token=getnexttoken();<if語句>::=if<布爾表達(dá)式>then<執(zhí)行句>else<執(zhí)行句>

iftoken＝"else"/*處理else部分*/

{q=nxq;

gencode(j,—,—,0);

backpatch(e.fc,nxq);/*回填假出口e.fc*/

t.chain=merg(s1.chain,q);

getnexttoken(token);

s2.cha