語(yǔ)義分析和中間代碼生成第五章

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

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

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

(a+b)*cab+c*

a+b*cabc*+

a:=b*c+b*d

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

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

也可以寫(xiě)成賦值語(yǔ)句形式：

(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)到目前為止，已知輸入的語(yǔ)法單位，

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

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

intTrealLL1,idLidL.in:=T.typeT.type=integerT.type:=realaddtype(id.entry,L.in)L1.in:=L.inaddtype(id.entry,L.in)語(yǔ)義規(guī)則描述的工作：屬性計(jì)算、靜態(tài)語(yǔ)義檢查、符號(hào)表的操作、代碼生成等，通常寫(xiě)成過(guò)程和函數(shù)調(diào)用，稱(chēng)為語(yǔ)義子程序。語(yǔ)義翻譯常用的方法：語(yǔ)法制導(dǎo)翻譯：定義翻譯所必須的語(yǔ)義屬性和語(yǔ)義規(guī)則，一般不涉及計(jì)算順序。語(yǔ)法制導(dǎo)翻譯技術(shù)語(yǔ)法制導(dǎo)翻譯(Syntax-DirectedTranslations)：一個(gè)句子的語(yǔ)義翻譯過(guò)程與語(yǔ)法分析過(guò)程同時(shí)進(jìn)行。在文法中，文法符號(hào)有明確的意義，文法符號(hào)之間有確定的語(yǔ)義關(guān)系。屬性描述語(yǔ)義信息，語(yǔ)義規(guī)則描述屬性間的的關(guān)系，將語(yǔ)義規(guī)則與語(yǔ)法規(guī)則相結(jié)合，在語(yǔ)法分析的過(guò)程中計(jì)算語(yǔ)義屬性值。語(yǔ)法制導(dǎo)翻譯的處理方法對(duì)應(yīng)每一個(gè)產(chǎn)生式編制一個(gè)語(yǔ)義子程序，在進(jìn)行語(yǔ)法分析的過(guò)程中，當(dāng)一個(gè)產(chǎn)生式獲得匹配時(shí)，就調(diào)用相應(yīng)的語(yǔ)義子程序?qū)崿F(xiàn)語(yǔ)義檢查與翻譯。即在自下而上語(yǔ)法分析的過(guò)程中，每一次歸約時(shí)就調(diào)用相應(yīng)的語(yǔ)義子程序。在產(chǎn)生式的右部的適當(dāng)位置，插入相應(yīng)的語(yǔ)義動(dòng)作，按照分析的進(jìn)程，執(zhí)行遇到的語(yǔ)義動(dòng)作。語(yǔ)義子程序一個(gè)語(yǔ)義子程序描述了一個(gè)產(chǎn)生式對(duì)應(yīng)的翻譯工作。主要有：改變編譯程序某些變量的值、查填各種符號(hào)表、發(fā)現(xiàn)并報(bào)告源程序錯(cuò)誤、產(chǎn)生中間代碼。在描述語(yǔ)義動(dòng)作時(shí)需要為每個(gè)文法符號(hào)賦以各種不同的語(yǔ)義值，如類(lèi)型、地址、代碼值等。如果一個(gè)產(chǎn)生式中一個(gè)符號(hào)多次出現(xiàn)，就用上角標(biāo)來(lái)區(qū)分，如：E=E(1)+E(2)語(yǔ)義子程序的一般形式語(yǔ)義子程序?qū)懺谠摦a(chǎn)生式后面的花括號(hào)內(nèi)：(1)X…{語(yǔ)義子程序1}(2)Y…{語(yǔ)義子程序2}(3)AXY{語(yǔ)義子程序3}例：臺(tái)式計(jì)算器程序的語(yǔ)義子程序描述：產(chǎn)生式 語(yǔ)義子程序(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}常見(jiàn)的語(yǔ)法制導(dǎo)翻譯類(lèi)型：語(yǔ)法分析采用自下而上方法時(shí)，使用與語(yǔ)法分析棧同步操作的語(yǔ)義棧進(jìn)行語(yǔ)法制導(dǎo)翻譯。語(yǔ)法分析采用遞歸下降分析方法時(shí)，利用隱含堆棧存儲(chǔ)各遞歸子程序中的局部變量所表示的語(yǔ)義信息語(yǔ)法分析采用LL(1)分析法時(shí)，利用翻譯文法進(jìn)行語(yǔ)法制導(dǎo)的翻譯。翻譯文法是在描述語(yǔ)言的文法中加入語(yǔ)義動(dòng)作的符號(hào)。利用屬性文法進(jìn)行翻譯。屬性文法也是一種翻譯文法，它的文法符號(hào)和動(dòng)作符號(hào)都帶有語(yǔ)義屬性和同一產(chǎn)生式中各屬性間的運(yùn)算規(guī)則。自下而上的語(yǔ)法制導(dǎo)翻譯舉例為了正確理解，需要弄清楚：自下而上翻譯的特點(diǎn)各種語(yǔ)句的目標(biāo)結(jié)構(gòu)從源到目標(biāo)的變換方法自下而上翻譯的特點(diǎn)使用上圖形式的棧實(shí)現(xiàn)——增加語(yǔ)義棧用X.Val表示文法符號(hào)X的語(yǔ)義信息。語(yǔ)義信息與文法符號(hào)同時(shí)出棧和入棧下面以一個(gè)例子來(lái)說(shuō)明自底向上的翻譯方法例1：下面是一個(gè)算術(shù)表達(dá)式文法，每個(gè)產(chǎn)生式右邊是它的語(yǔ)義動(dòng)作，對(duì)輸入串２*3+2的規(guī)范歸約的分析過(guò)程如下：例2：在3*5＋4的LR分析過(guò)程中增加了語(yǔ)義棧后的語(yǔ)法制導(dǎo)的實(shí)現(xiàn)過(guò)程。(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序號(hào)狀態(tài)棧符號(hào)棧語(yǔ)義棧歸約產(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é)論在剛才的翻譯過(guò)程中有如下特點(diǎn)：句柄歸約在先，語(yǔ)義動(dòng)作在后。歸約時(shí)，棧內(nèi)句柄各符號(hào)的語(yǔ)義信息與該句柄同時(shí)出棧，整個(gè)句柄所表示的語(yǔ)義信息則賦給相應(yīng)產(chǎn)生式左部非終結(jié)符的語(yǔ)義變量，并讓該非終結(jié)符及其語(yǔ)義變量同時(shí)入棧。為了在某處調(diào)用語(yǔ)義動(dòng)作，就必須先歸約，因此，有時(shí)需要改寫(xiě)文法。5.4常見(jiàn)語(yǔ)句的語(yǔ)法制導(dǎo)的翻譯高級(jí)語(yǔ)言的語(yǔ)句分類(lèi)：說(shuō)明語(yǔ)句——定義各種名字的屬性可執(zhí)行語(yǔ)句——用于完成指定的功能，涉及到指令代碼語(yǔ)義翻譯也分兩類(lèi)：翻譯說(shuō)明語(yǔ)句時(shí)，將所定義的名字的各種屬性登記到符號(hào)表中翻譯可執(zhí)行語(yǔ)句時(shí)，首先應(yīng)根據(jù)各源語(yǔ)句的語(yǔ)法結(jié)構(gòu)和語(yǔ)義設(shè)計(jì)出它的目標(biāo)代碼結(jié)構(gòu)，找出源與目標(biāo)的對(duì)應(yīng)關(guān)系，給出對(duì)信息(數(shù)據(jù)表示)描述和從源到目標(biāo)的變換算法。語(yǔ)義子程序則根據(jù)變換方法進(jìn)行翻譯。說(shuō)明語(yǔ)句的翻譯說(shuō)明語(yǔ)句的作用：就是說(shuō)明類(lèi)型等屬性信息，在翻譯時(shí)主要是填符號(hào)表說(shuō)明語(yǔ)句分多種，此處舉例兩種的翻譯：變量說(shuō)明語(yǔ)句的翻譯常量說(shuō)明語(yǔ)句的翻譯變量說(shuō)明語(yǔ)句的翻譯１.變量說(shuō)明語(yǔ)句的文法描述２.變量說(shuō)明語(yǔ)句的翻譯例如：vara,b,c:integer;策略：先翻譯第３，４產(chǎn)生式，再翻譯２，１產(chǎn)生式，以便記錄<IDS>的類(lèi)型，即在寫(xiě)程序時(shí)，讀完一個(gè)說(shuō)明語(yǔ)句，開(kāi)始?xì)w約，再開(kāi)始翻譯，變量的類(lèi)型朝前傳遞。３.翻譯的語(yǔ)義動(dòng)作FILL(entry(i),Type)表示將類(lèi)型Type填入符號(hào)表中entry(i)表示變量名i在符號(hào)表中的入口NameTYPEKINDVALADDRa4integer符號(hào)表：VARid1,id2,id3:integer;的歸約過(guò)程integer:id3<IDS>,,id2id2<IDS>,,,id1id1id1<IDS>VARVARVARVAR…………………………(a)(b)(c)(d)(e)常量說(shuō)明語(yǔ)句的翻譯１.常量說(shuō)明語(yǔ)句的文法描述２.常量說(shuō)明語(yǔ)句的翻譯策略：和變量說(shuō)明一樣，先翻譯后面的產(chǎn)生式，再翻譯前面的產(chǎn)生式，以便在歸約時(shí)，執(zhí)行語(yǔ)義動(dòng)作，將常量的值、類(lèi)型、種屬填入符號(hào)表。例：ConstantA=123３.翻譯的語(yǔ)義動(dòng)作將常量INT在符號(hào)表中的入口或值直接填入常量符號(hào)i所指符號(hào)表的VAL欄將常數(shù)的類(lèi)型填入符號(hào)表的Type欄3，4產(chǎn)生式的翻譯與5，6產(chǎn)生式的翻譯相同1，2產(chǎn)生式?jīng)]有語(yǔ)義動(dòng)作NameTYPEKINDVALADDRA4integer數(shù)值常數(shù)123將常數(shù)的種屬填入符號(hào)表的Kind欄可執(zhí)行語(yǔ)句的翻譯定義的一些語(yǔ)義變量和過(guò)程GENCODE(OP,ARG1,ARG2,RESULT)：語(yǔ)義過(guò)程，產(chǎn)生一個(gè)四元式，并填入四元式表，編號(hào)自動(dòng)增1

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

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

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

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

Q:=m;}}4.布爾表達(dá)式的翻譯布爾表達(dá)式是帶有not,and,or的表達(dá)式第一種翻譯方法可以象算術(shù)表達(dá)式一樣翻譯，先計(jì)算每個(gè)因子的值，再計(jì)算整個(gè)表達(dá)式的值。第二種翻譯方法采取優(yōu)化措施進(jìn)行翻譯。E1orT的優(yōu)化：只要E為真，后面的表達(dá)式就不必計(jì)算，只有當(dāng)E為假時(shí)才讀取T，目標(biāo)結(jié)構(gòu)如下：E1andT的優(yōu)化：只要E為假，后面的表達(dá)式就不必計(jì)算，只有當(dāng)E為真時(shí)才讀取T，目標(biāo)結(jié)構(gòu)如下：如果是翻譯notE1，則E的真假出口正好與E1相反5.翻譯布爾表達(dá)式時(shí)，當(dāng)讀到not,and,or時(shí)，要進(jìn)行歸約，因此應(yīng)對(duì)文法進(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)生的四元式的編號(hào)單個(gè)的布爾量關(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)算控制語(yǔ)句的翻譯控制語(yǔ)句包括：

if語(yǔ)句While語(yǔ)句Repeat語(yǔ)句For語(yǔ)句IF語(yǔ)句的翻譯1.IF語(yǔ)句的文法(S是開(kāi)始符號(hào))產(chǎn)生式(1),(4)生成無(wú)else的IF語(yǔ)句結(jié)構(gòu)產(chǎn)生式(1),(2),(3)生成if–then–else的語(yǔ)句結(jié)構(gòu)（1）S→CS(1)（2）C→ifEthen（3）S→TS(2)（4）T→CS(1)else2.IF語(yǔ)句的目標(biāo)結(jié)構(gòu)及其翻譯無(wú)else的結(jié)構(gòu)C.Chain的作用：由于在用第一個(gè)產(chǎn)生式進(jìn)行歸約時(shí)，只生成了條件式E的代碼，then時(shí)可以回填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語(yǔ)句的目標(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語(yǔ)句翻譯為四元式序列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í):將下面的語(yǔ)句翻譯為四元式序列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語(yǔ)句的翻譯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}將下面的語(yǔ)句翻譯為四元式序列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語(yǔ)句的翻譯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語(yǔ)句的翻譯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}將下面的語(yǔ)句翻譯為四元式序列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語(yǔ)言語(yǔ)法制導(dǎo)翻譯程序的設(shè)計(jì)語(yǔ)法制導(dǎo)的翻譯實(shí)際上就是在語(yǔ)法分析的基礎(chǔ)上，當(dāng)分析完一個(gè)正確的語(yǔ)法單位后，調(diào)用相應(yīng)的語(yǔ)義處理程序，直接生成相應(yīng)的四元式表。在第4章使用遞歸下降的分析方法進(jìn)行了Sample語(yǔ)言的語(yǔ)法分析器在此基礎(chǔ)上添加語(yǔ)義處理舉例：為IF語(yǔ)句添加語(yǔ)義處理ifs(){/*If語(yǔ)句的語(yǔ)法分析*/token=getnexttoken();

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

bexp();token=getnexttoken();

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

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