1、語義分析和中間代碼生成語義分析和中間代碼生成第五章第五章 本章要求本章要求 主要內(nèi)容主要內(nèi)容：語義分析和中間代碼生成的語義分析和中間代碼生成的功能，中間代碼的形式，屬性文法及語功能，中間代碼的形式，屬性文法及語法制導(dǎo)的翻譯程序，各種語句的語法制法制導(dǎo)的翻譯程序，各種語句的語法制導(dǎo)的翻譯過程導(dǎo)的翻譯過程 重點(diǎn)掌握：重點(diǎn)掌握：屬性文法，屬性文法，語義分析與處理語義分析與處理的方法的方法, ,中間代碼的表示形式，各種語句中間代碼的表示形式，各種語句的代碼結(jié)構(gòu)，各種語句的翻譯方法的代碼結(jié)構(gòu)，各種語句的翻譯方法語義分析和中間代碼生成所處的位置：5.1 概述概述. 語義分析和中間代碼生成在編譯器中的位置：

2、語義分析和中間代碼生成在編譯器中的位置： 靜態(tài)語義檢查：如：類型、運(yùn)算、數(shù)組維數(shù)、越界等的檢查 語義處理：如：變量的存儲分配、表達(dá)式的求值、語句的翻譯(中間代碼的生成) 總目標(biāo)：生成等價的中間代碼語法分析語義分析和中間代碼生成編譯的后續(xù)階段語法樹中間代碼. 功能及任務(wù)：功能及任務(wù)： 輸入-語法分析單位 輸出 - 用中間代碼形式表示的文本 - 出錯處理: 定位、繼續(xù)編譯3. 為什么要此階段為什么要此階段? 邏輯結(jié)構(gòu)清楚；利于不同目標(biāo)機(jī)上實(shí)現(xiàn)同一種語言； 利于進(jìn)行與機(jī)器無關(guān)的優(yōu)化，這些內(nèi)部形式也能用于解釋。4. 什么是中間代碼什么是中間代碼(Intermediate code) 源程序的一種內(nèi)部表

3、示，不依賴目標(biāo)機(jī)的結(jié)構(gòu)，易于機(jī)械生成目標(biāo)代碼的中間表示。5. 中間代碼的幾種形式中間代碼的幾種形式 逆波蘭、三元式、間接三元式、四元式、樹 1 1、逆波蘭式、逆波蘭式：運(yùn)算對象寫在前，運(yùn)算符寫在后(后綴后綴表示形式)例：a+b ab+ (a+b)*c ab+c*a+b*c abc*+a:=b*c+b*d abc*bd*+:=5.2中間代碼的幾種形式中間代碼的幾種形式+a b優(yōu)點(diǎn)：易于計(jì)算機(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)棧，最后

4、結(jié)果即棧頂元素。練習(xí)練習(xí)寫出下列算式的逆波蘭表示a+b*(c+d/e) a:=b a:=b* *(-c)+b (-c)+b * *(-34)(-34)not A or not (C or not D)abcde/+*+A not C D not or not or+a * b + c / d e后綴式的推廣后綴式的推廣 (1)賦值語句A:=E，后綴式為：AE:= (2)轉(zhuǎn)向語句GOTO L的后綴式為：Ljmp (3)條件語句if xy then m:=x else m:=y12345678910111213 14xy11 jezmx:=14jmy:= 2 2、三元式、三元式編號（運(yùn)算符，第一運(yùn)

5、算數(shù)，第二運(yùn)算數(shù)）編號（運(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)算對象，另一個為空對于單目運(yùn)算符，只有一個運(yùn)算對象，另一個為空注意：在三元式中的編號既代表了序號，又代表了結(jié)注意：在三元式中的編號既代表了序號，又代表了結(jié)果的存放位置。果的存放位置。 3 3、四元式、四元式 是目前最常用的中間代碼形式:( (運(yùn)算符，第一運(yùn)算數(shù)，第二運(yùn)算數(shù)，結(jié)果運(yùn)算符，第一運(yùn)算數(shù)，第二運(yùn)算數(shù)，結(jié)果) )例：a:=b*c+b*d (1)(*,b,c,t1) (2)(*,b,d,t2

6、) (3)(+,t1,t2,t3) (4)(:=,t3, ,a) 也可以寫成賦值語句形式：(1)t1:=b*c (2)t2:=b*d(3)t3:=t1+t2 (4)a:=t3練習(xí)練習(xí) 求 -B+C-B+C* *D D 的逆波蘭表示形式、三元式和四元式逆波蘭：B C D * +三元式：(1) (-,B,) (2) (*,C,D)(3) (+,(1),(2)四元式：(1) (-,B, , t1) (2) (*,C,D,t2)(3) (+,t1,t2,t3)到目前為止，已知到目前為止，已知 輸入的語法單位輸入的語法單位，又知道又知道 要翻譯的結(jié)果的形式要翻譯的結(jié)果的形式，翻譯的方法翻譯的方法是什么？

7、是什么？ 語義分析和翻譯的方法：語義表示較流行的方法仍然是屬性文法，翻譯方法是語法屬性文法，翻譯方法是語法制導(dǎo)的翻譯制導(dǎo)的翻譯。5.3 屬性文法與語法指導(dǎo)的翻譯屬性文法與語法指導(dǎo)的翻譯 屬性文法屬性文法:是在上下文無關(guān)文法的基礎(chǔ)上，為每個文法符號(含終結(jié)符和非終結(jié)符)配備若干個屬性屬性值，對文法的每個產(chǎn)生式都配備了一組屬性計(jì)算規(guī)則(稱為語義規(guī)則語義規(guī)則)。在語法分析過程中，完成語義規(guī)則所描述的動作，從而實(shí)現(xiàn)語義處理。 屬性屬性：代表與文法符號相關(guān)的信息，如類型、值、代碼序列、符號表的內(nèi)容等。與變量一樣，可以進(jìn)行計(jì)算和傳遞，屬性的加工過程就是語義的處理過程。 屬性分兩類： 綜合屬性：用于自下而上

8、傳遞信息 繼承屬性：用于自上而下傳遞信息 注意： 終結(jié)符只有綜合屬性，它由詞法分析器提供； 非終結(jié)符可有綜合屬性，也可有繼承屬性，它由詞法分析器提供； 文法的開始符號的所有繼承屬性作為屬性計(jì)算前的初始值綜合屬性綜合屬性繼承屬性繼承屬性 產(chǎn)生式右邊的文法符號的繼承屬性可以繼承左邊的文法符號的繼承屬性 產(chǎn)生式左邊的文法符號可以通過綜合右邊的文法符號的綜合屬性而得到 但必須提供一個計(jì)算規(guī)則：計(jì)算規(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)生式

9、左邊的繼承屬性和右邊的綜合屬性不由所給的產(chǎn)生式的屬性計(jì)算規(guī)則進(jìn)行計(jì)算，它們由其它產(chǎn)生式的屬性計(jì)算規(guī)則提供。digitlexval:=3Fval:=3Tval:=3Fval:=5Tval:=15*Eval:=15+digitlexval:=4Fval:=4Tval:=4Eval:=19Ln0LEn1EE1+T2ET3TT1*F4TF5F(E)6Fdigitprint(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若

10、輸入符號串為：若輸入符號串為：3*5+4n例例：綜合屬性的計(jì)算綜合屬性的計(jì)算C語言中變量定義：語言中變量定義：int id1,id2,id3綜合屬性的傳遞繼承屬性的傳遞例例：繼承屬性的計(jì)算繼承屬性的計(jì)算產(chǎn)生式語 義 規(guī) 則D TL T intT realL L1,idL idL.in:=T.typeT.type=integerT.type:=realaddtype(id.entry,L.in) L1.in:=L.inaddtype(id.entry,L.in) 語義規(guī)則描述的工作： 屬性計(jì)算、靜態(tài)語義檢查、符號表的操作、代碼生成等，通常寫成過程和函數(shù)調(diào)用，稱為語語義子程序義子程序。 語義翻譯常

11、用的方法： 語法制導(dǎo)翻譯語法制導(dǎo)翻譯：定義翻譯所必須的語義屬性和語義規(guī)則，一般不涉及計(jì)算順序。語法制導(dǎo)翻譯技術(shù)語法制導(dǎo)翻譯技術(shù) 語法制導(dǎo)翻譯(Syntax-Directed Translations)： 一個句子的語義翻譯過程與語法分析過程同時進(jìn)行。 在文法中，文法符號有明確的意義，文法符號之間有確定的語義關(guān)系。屬性描述語義信息，語義規(guī)則描述屬性間的的關(guān)系，將語義規(guī)則與語法規(guī)則相結(jié)合，在語法分析的過程中計(jì)算語義屬性值。語法制導(dǎo)翻譯的處理方法語法制導(dǎo)翻譯的處理方法 對應(yīng)每一個產(chǎn)生式編制一個語義子程序，在進(jìn)行語法分析的過程中，當(dāng)一個產(chǎn)生式獲得匹配時，就調(diào)用相應(yīng)的語義子程序語義子程序?qū)崿F(xiàn)語義檢查與翻

12、譯。即在自下而上語法分析的過程中，每一次歸約時就調(diào)用相應(yīng)的語義子程序。 在產(chǎn)生式的右部的適當(dāng)位置，插入相應(yīng)的語義動作，按照分析的進(jìn)程，執(zhí)行遇到的語義動作。 語義子程序 一個語義子程序描述了一個產(chǎn)生式對應(yīng)的翻譯翻譯工作工作。 主要有：改變編譯程序某些變量的值改變編譯程序某些變量的值、查填各查填各種符號表種符號表、發(fā)現(xiàn)并報告源程序錯誤發(fā)現(xiàn)并報告源程序錯誤、產(chǎn)生中間產(chǎn)生中間代碼代碼。 在描述語義動作時需要為每個文法符號賦以各種不同的語義值，如類型類型、地址地址、代碼值代碼值等。 如果一個產(chǎn)生式中一個符號多次出現(xiàn)，就用上角標(biāo)來區(qū)分，如：E = E(1) + E(2)v語義子程序的一般形式v語義子程序?qū)?/p>

13、在該產(chǎn)生式后面的花括號內(nèi)：v(1) X 語義子程序1 v(2) Y 語義子程序2 v(3) AXY 語義子程序3 常見的語法制導(dǎo)翻譯類型：常見的語法制導(dǎo)翻譯類型： 語法分析采用自下而上方法時，使用與語法分析棧同步操作的語義棧進(jìn)行語法制導(dǎo)翻譯。 語法分析采用遞歸下降分析方法時，利用隱含堆棧存儲各遞歸子程序中的局部變量所表示的語義信息 語法分析采用LL(1)分析法時，利用翻譯文法進(jìn)行語法制導(dǎo)的翻譯。翻譯文法是在描述語言的文法中加入語義動作的符號。 利用屬性文法進(jìn)行翻譯。屬性文法也是一種翻譯文法，它的文法符號和動作符號都帶有語義屬性和同一產(chǎn)生式中各屬性間的運(yùn)算規(guī)則。自下而上的語法制導(dǎo)翻譯舉例自下而上

14、的語法制導(dǎo)翻譯舉例 為了正確理解，需要弄清楚： 自下而上翻譯的特點(diǎn) 各種語句的目標(biāo)結(jié)構(gòu) 從源到目標(biāo)的變換方法自下而上翻譯的特點(diǎn)使用上圖形式的棧實(shí)現(xiàn)增加語義棧用X.Val表示文法符號X的語義信息。語義信息與文法符號同時出棧和入棧下面以一個例子來說明自底向上的翻譯方法例例1：下面是一個算術(shù)表達(dá)式文法，每個產(chǎn)生式右：下面是一個算術(shù)表達(dá)式文法，每個產(chǎn)生式右邊是它的語義動作，對輸入串邊是它的語義動作，對輸入串* 3 + 2的規(guī)范歸約的規(guī)范歸約的分析過程如下：的分析過程如下：例例2：在：在3*54的的LR分析過程中增加了語義棧后的分析過程中增加了語義棧后的語法制導(dǎo)的實(shí)現(xiàn)過程。語法制導(dǎo)的實(shí)現(xiàn)過程。(1) E

15、E+T|T(2) TT*F|F(3) F(E)|i 狀態(tài)actiongotoabcd#E A B01234567891011S2.r1r2r3r5r4r6S3.r1r2r3r5r4r6. S4S5S4S5r1r2r3r5r4r6. S10S11S10S11r1r2r3r5r4r6.acc.r1r2r3r5r4r.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

16、#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é)論結(jié)論 在剛才的翻譯過程中有如下特點(diǎn)： 句柄歸約在先，語義動作在后。句柄歸約在先，語義動作在后。 歸約時，棧內(nèi)句柄各符號的語義信息與該句柄歸約時，棧內(nèi)句柄各符號的語義信息與該句柄同時出同時出棧棧，整個句柄所表示的語義信息則賦給相應(yīng)產(chǎn)生式左，整個句柄所表示的語義信息則賦給相應(yīng)產(chǎn)生式左部非終結(jié)符的語義變量，并讓該非終結(jié)符及其語義變部非終結(jié)符的語義變量，并讓該非終結(jié)符及其語義變量量同時入棧同時入棧。 為了在

17、某處調(diào)用語義動作，就必須先歸約，因此，有為了在某處調(diào)用語義動作，就必須先歸約，因此，有時需要時需要改寫文法改寫文法。5.4 常見語句的語法制導(dǎo)的翻譯常見語句的語法制導(dǎo)的翻譯 高級語言的語句分類：高級語言的語句分類： 說明語句定義各種名字的屬性 可執(zhí)行語句用于完成指定的功能，涉及到指令代碼 語義翻譯也分兩類：語義翻譯也分兩類： 翻譯說明語句時，將所定義的名字的各種屬性登記到符號表中 翻譯可執(zhí)行語句時，首先應(yīng)根據(jù)各源語句的語法結(jié)構(gòu)和語義設(shè)計(jì)出它的目標(biāo)代碼結(jié)構(gòu)目標(biāo)代碼結(jié)構(gòu)，找出源與目標(biāo)的對應(yīng)關(guān)系，給出對信息(數(shù)據(jù)表示)描述和從源到目標(biāo)的變換算法變換算法。語義子程序則根據(jù)變換方法進(jìn)行翻譯。說明語句的翻

18、譯說明語句的翻譯 說明語句的作用： 就是說明類型等屬性信息，在翻譯時主要是填符號表 說明語句分多種，此處舉例兩種的翻譯： 變量說明語句的翻譯 常量說明語句的翻譯變量說明語句的翻譯變量說明語句的翻譯. 變量說明語句的文法描述變量說明語句的文法描述. 變量說明語句的翻譯變量說明語句的翻譯例如：var a,b,c: integer;策略：先翻譯第，產(chǎn)生式，再翻譯，產(chǎn)生式，以便記錄的類型，即在寫程序時，讀完讀完一個說明語句，開始?xì)w約，再開始翻譯，變量的類型朝前傳遞。. 翻譯的語義動作翻譯的語義動作FILL(entry(i),Type)表示將表示將類型類型Type填入符號表中填入符號表中entry(i)

19、 表示變量名表示變量名i在在符號表中的入口符號表中的入口NameTYPEKINDVALADDRa4integer符號表：符號表：VAR id1,id2,id3:integer;的歸約過程integer:id3,id2id2,id1id1id1VARVARVARVAR(a)(b)(c)(d)(e)常量說明語句的翻譯常量說明語句的翻譯. 常量說明語句的文法描述常量說明語句的文法描述. 常量說明語句的翻譯常量說明語句的翻譯策略：和變量說明一樣，先翻譯后面的產(chǎn)生式，再翻譯前面的產(chǎn)生式，以便在歸約時，執(zhí)行語義動作，將常量的值、類型、種屬填入符號表。例：例：Constant A=123. 翻譯的語義動作翻

20、譯的語義動作將常量將常量INT在符號表中的入在符號表中的入口或值直接填入常量符號口或值直接填入常量符號i所指符號表的所指符號表的VAL欄欄將常數(shù)的類型填將常數(shù)的類型填入符號表的入符號表的Type欄欄3，4產(chǎn)生式的翻譯與5，6產(chǎn)生式的翻譯相同1，2產(chǎn)生式?jīng)]有語義動作NameTYPEKINDVALADDRA4integer數(shù)值常數(shù)數(shù)值常數(shù) 123將常數(shù)的種屬填將常數(shù)的種屬填入符號表的入符號表的Kind欄欄可執(zhí)行語句的翻譯可執(zhí)行語句的翻譯 定義的一些語義變量和過程 GENCODE(OP,ARG1,ARG2,RESULT)：語義過程，產(chǎn)生一個四元式，并填入四元式表，編號自動增1 。 NEWT：函數(shù)，返

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

22、運(yùn)算例：賦值句A:=B+C*(-D)的自底向上分析設(shè)：翻譯此賦值句之前四元式的最大編號為K因此，四元式表中增加了因此，四元式表中增加了4條四元式：條四元式：K（翻譯此賦值語句之前的四元式）K+1(i，F(xiàn)DPLACE，_，F(xiàn)DPLACE)K+2(*i，TcPLACE，F(xiàn)DPLACE，TPLACE)K+3(+i，EBPLACE，TPLACE，EPLACE)K+4(:=，EPLACE，_，ENTRY(iA)布爾表達(dá)式的翻譯布爾表達(dá)式的翻譯3 .布爾表達(dá)式布爾表達(dá)式的文法描述的文法描述.布爾表達(dá)式布爾表達(dá)式的作用的作用用作控制語句中的條件表達(dá)式用作控制語句中的條件表達(dá)式用在邏輯賦值語句中用在邏輯賦值語

23、句中2 .布爾表達(dá)式的形式布爾表達(dá)式的形式 (1)單個布爾量單個布爾量;(2) 布爾量的運(yùn)算布爾量的運(yùn)算not, and,or, 優(yōu)先級比優(yōu)先級比關(guān)系運(yùn)算高關(guān)系運(yùn)算高;(3)關(guān)系運(yùn)算關(guān)系運(yùn)算:E1 rop E2, E1E2是算術(shù)表達(dá)是算術(shù)表達(dá)式，式，rop為關(guān)系運(yùn)算符為關(guān)系運(yùn)算符: ,=,=,=（1） or （2）（3） and （4）（5）not （6）()（7） rop （8）i rop i（9）i 例如：例如：x := not a and (yz); 布爾量翻譯為兩條四元式：布爾量翻譯為兩條四元式： (jnz, A,_,P): 真出口，當(dāng)真出口，當(dāng)A為真時跳轉(zhuǎn)到四元式為真時跳轉(zhuǎn)到四元式P

24、 (j, _,_,q) : 假出口，無條件跳轉(zhuǎn)到四元式假出口，無條件跳轉(zhuǎn)到四元式q 關(guān)系表達(dá)式也翻譯為兩條四元式：關(guān)系表達(dá)式也翻譯為兩條四元式： (jrop, i1, i2, P) : 真出口，當(dāng)真出口，當(dāng)i1 rop i2為真時轉(zhuǎn)四為真時轉(zhuǎn)四元式元式P (j, _,_,q) : 假出口，無條件跳轉(zhuǎn)到四元式假出口，無條件跳轉(zhuǎn)到四元式q3.布爾量布爾量的代碼結(jié)構(gòu)的代碼結(jié)構(gòu) 每個布爾量每個布爾量(布爾變量或關(guān)系表達(dá)式布爾變量或關(guān)系表達(dá)式)的目標(biāo)結(jié)構(gòu)有的目標(biāo)結(jié)構(gòu)有兩個出口，真出口指向?yàn)檎鏁r應(yīng)跳轉(zhuǎn)的位置；假出兩個出口，真出口指向?yàn)檎鏁r應(yīng)跳轉(zhuǎn)的位置；假出口指向?yàn)榧贂r應(yīng)跳轉(zhuǎn)的位置。口指向?yàn)榧贂r應(yīng)跳轉(zhuǎn)的位置

25、。類似于編寫類似于編寫匯編代碼匯編代碼AA.TCA.FC在翻譯布爾表達(dá)式時，后面的語句未在翻譯布爾表達(dá)式時，后面的語句未翻譯，翻譯，P,q如何知道？如何知道？ 解決方法是：回填技術(shù)回填技術(shù) 已知就直接填入；不知時先填0，等知道后再返填 若多個因子的轉(zhuǎn)移去向相同，但又不知道具體位置，應(yīng)該用鏈將這些未知且出口相同的四元式鏈在一起。 布爾表達(dá)式: A and B and CD 的四元式為： 假出口未知，填入假出口未知，填入0當(dāng)掃描到當(dāng)掃描到and時，對時，對A進(jìn)行進(jìn)行歸約，產(chǎn)生兩個四元式歸約，產(chǎn)生兩個四元式1，2，其中真出口已知，為其中真出口已知，為3當(dāng)掃描到當(dāng)掃描到B后的后的and時，時，對對B進(jìn)

26、行歸約，又產(chǎn)生進(jìn)行歸約，又產(chǎn)生兩個四元式兩個四元式3，4，其中，其中真出口已知，為真出口已知，為5假出口仍未知，假出口仍未知，但它與但它與A的假出的假出口相同，則鏈接口相同，則鏈接起來，填起來，填2當(dāng)掃描到最后，對當(dāng)掃描到最后，對CD進(jìn)行歸約，又產(chǎn)進(jìn)行歸約，又產(chǎn)生兩個四元式生兩個四元式5，6，此時真出口未知，填此時真出口未知，填0假出口仍未知，但假出口仍未知，但它與上兩個布爾量它與上兩個布爾量的假出口相同，則的假出口相同，則鏈接起來，填鏈接起來，填4生成了真、假出口兩個鏈，兩個生成了真、假出口兩個鏈，兩個0就是待填就是待填部分。等到以后翻譯到后面再填入。部分。等到以后翻譯到后面再填入。 將將P

27、1,P2為鏈?zhǔn)變蓚€四元式鏈合并在一起，可以用為鏈?zhǔn)變蓚€四元式鏈合并在一起，可以用下述過程，返回合并后的四元式鏈?zhǔn)祝合率鲞^程，返回合并后的四元式鏈?zhǔn)祝簃erge(P1，P2) if P2 = 0) return (P1); else P := P2; while (四元式P的第4分量內(nèi)容不為0) do P := 四元式P的第4分量內(nèi)容； 把P1填進(jìn)四元式P的第4分量； return (P2); 假出口鏈上的四元式應(yīng)轉(zhuǎn)向相同的位置，所以一旦假出口鏈上的四元式應(yīng)轉(zhuǎn)向相同的位置，所以一旦知道轉(zhuǎn)向的真實(shí)位置，就應(yīng)返填，返填是將已知位知道轉(zhuǎn)向的真實(shí)位置，就應(yīng)返填，返填是將已知位置填入鏈上的所有四元式的第四

28、個分量。置填入鏈上的所有四元式的第四個分量。 用用backpatch，把已知位置，把已知位置t填入以填入以P為鏈?zhǔn)椎乃脑獮殒準(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á)式的翻譯的翻譯 布爾表達(dá)式是帶有布爾表達(dá)式是帶有not, and, or 的表達(dá)式的表達(dá)式 第一種翻譯方法可以象算術(shù)表達(dá)式一樣翻譯，第一種翻譯方法可以象算術(shù)表達(dá)式一樣翻譯，先計(jì)算每個因子的值，再計(jì)算整個表達(dá)式的值。先計(jì)算每個因子的值，再計(jì)算整個表達(dá)式的值。 第二種翻譯方法采取

29、優(yōu)化措施進(jìn)行翻譯。第二種翻譯方法采取優(yōu)化措施進(jìn)行翻譯。 E1 or T 的優(yōu)化的優(yōu)化：只要：只要E為真，后面的表達(dá)式就不必計(jì)算，為真，后面的表達(dá)式就不必計(jì)算，只只 有當(dāng)有當(dāng)E為假時才讀取為假時才讀取T，目標(biāo)結(jié)構(gòu)如下：，目標(biāo)結(jié)構(gòu)如下：E1 and T 的優(yōu)化的優(yōu)化：只要：只要E為假，后面的表達(dá)式就不必計(jì)算，為假，后面的表達(dá)式就不必計(jì)算，只有當(dāng)只有當(dāng)E為真時才讀取為真時才讀取T，目標(biāo)結(jié)構(gòu)如下：，目標(biāo)結(jié)構(gòu)如下：如果是翻譯如果是翻譯not E1，則，則E的的真假出口正好與真假出口正好與E1相反相反5. 翻譯布爾表達(dá)式時，當(dāng)讀到翻譯布爾表達(dá)式時，當(dāng)讀到not, and, or時，要進(jìn)行歸約，時，要進(jìn)行歸

30、約，因此應(yīng)對文法進(jìn)行改造，改造前后的文法為：因此應(yīng)對文法進(jìn)行改造，改造前后的文法為：（1）or（2）oror（3）（4）and（5）andand（6）（7）()（8）not（9）rop（10）i rop i（11）i改造后的文法改造后的文法（1） or （2）（3） and （4）（5）not （6）()（7） rop （8）i rop i（9）i 改造前的文法改造前的文法 6. 總結(jié)前面的分析，各產(chǎn)生式的翻譯為：總結(jié)前面的分析，各產(chǎn)生式的翻譯為：NXQ表示當(dāng)前產(chǎn)生表示當(dāng)前產(chǎn)生的四元式的編號的四元式的編號單個的布爾量單個的布爾量關(guān)系運(yùn)算關(guān)系運(yùn)算Not邏輯運(yùn)算邏輯運(yùn)算帶算術(shù)運(yùn)算的關(guān)系運(yùn)算帶算術(shù)運(yùn)

31、算的關(guān)系運(yùn)算產(chǎn)生式產(chǎn)生式6: ，3: 的翻譯與的翻譯與7相相似，都是將右邊的真假出似，都是將右邊的真假出口直接賦值到左邊口直接賦值到左邊(5)(4)構(gòu)成構(gòu)成and邏輯運(yùn)算邏輯運(yùn)算(2)(1)構(gòu)成構(gòu)成or邏輯運(yùn)算邏輯運(yùn)算控制語句的翻譯控制語句的翻譯 控制語句包括： if 語句 While 語句 Repeat 語句 For 語句IF語句的翻譯語句的翻譯1. IF語句的文法語句的文法(S是開始符號是開始符號) 產(chǎn)生式產(chǎn)生式(1),(4)生成無生成無else 的的IF語句結(jié)構(gòu)語句結(jié)構(gòu) 產(chǎn)生式產(chǎn)生式(1),(2),(3)生成生成if then else 的的語句結(jié)構(gòu)語句結(jié)構(gòu)（1）SC S(1)（2）Ci

32、f E then（3）ST S(2)（4）TC S(1) else 2. IF語句的目標(biāo)結(jié)構(gòu)及其翻譯語句的目標(biāo)結(jié)構(gòu)及其翻譯 無無else的結(jié)構(gòu)的結(jié)構(gòu)C.Chain的作用：由于在用第一的作用：由于在用第一個產(chǎn)生式進(jìn)行歸約時，只生成了個產(chǎn)生式進(jìn)行歸約時，只生成了條件式條件式E的代碼，的代碼，then時可以回填時可以回填E.TC, E.FC必須向后傳遞到下一必須向后傳遞到下一各產(chǎn)生式中。各產(chǎn)生式中。if ab then x:=3;（1）SC S(1) SCHAIN :=MERG(CCHAIN，S(1)CHAIN) （2）Cif E then BACKPATCH(ETC，NXQ);CCHAIN:=EF

33、C 2. IF語句的目標(biāo)結(jié)構(gòu)及其翻譯語句的目標(biāo)結(jié)構(gòu)及其翻譯 有有else的結(jié)構(gòu)的結(jié)構(gòu)E的代碼S(1)的代碼ifthenE.TCE.FCS(1).CHAINC.CHAINS.CHAINS(2)的代碼JMP 0T.CHAINS(2).CHAINif ab then x:=3 else x:=5;(1) Cif E then BACKPATCH(ETC，NXQ);CCHAIN:=EFC (2) ST S(2) SCHAIN:=MERG(TCHAIN，S(2)CHAIN) (3) TC S(1) else q:=NXQ;GENCODE(j，_，_，0);BACKPATCH(CCHAIN，NXQ);TC

34、HAIN:=MERG(S(1) CHAIN，q) 例：將下面的例：將下面的IF語句翻譯為四元式序列語句翻譯為四元式序列if A and B and (CD) then if A,C,D,7) /*CD的四元式*/6. (j,_,_,13) 7.(j,A,B,9) /*AB的四元式*/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í):將下面的語句翻譯為四元式序列i

35、f (AC) and (BD) then if A=1 then C:=C+1 else if AD then A:=A+2; 1.(j,A,C,3)1.(j,A,C,3)2.(j,-,-,14)2.(j,-,-,14)3.(j,B,D,5)3.(j,B,D,5)4.(j,-,-,14)4.(j,-,-,14)5.(j=,A,1,7)5.(j=,A,1,7)6.(j,-,-,10) 6.(j,-,-,10) 7.(+,C,1,T7.(+,C,1,T1 1) ) 8.(:=,T,-,C) 8.(:=,T,-,C) 9.(j,-,-,14)9.(j,-,-,14)10.(j=,A,D,12) 10

36、.(j10; 3. 翻譯翻譯S(1)的代碼R.HEADS(1).CHAINE的代碼repeatuntilE.TCE.FCS.CHAIN（1） Rrepeat RHEAD:=NXQ （2） URS(1) until UHEAD:= RHEAD;BACKPATCH(S(1)CHAIN，NXQ) （3） SUE BACKPATCH(EFC，UHEAD);SCHAIN:=ETC 將下面的語句翻譯為四元式序列If w1 then a:=b*c+delse repeat a:=a-1 until a0;1.(j,w,1,3)2.(j, , ,7)3.(*,b,c,t1)4.(+,t1,d,t2)5.(:=

37、,t2, ,a)6.(j, , ,11)7.(-,a,1,t3)8.(:=,t3, , a)9.(j,a,0, 11)10.(j, , ,7 )W W 1 1a a: := =b b* *c c+ +d dg go ot to o 1 11 1a a: := =a a- -1 1a a ，F(xiàn)PLACE，T1，0) (2) SF S(1) BACKPATCH(S(1)CHAIN，F(xiàn)AGAIN);GENCODE(j，_，_，F(xiàn)AGAIN);SCHAIN:=FCHAIN 將下面的語句翻譯為四元式序列for i := a+b*2 to c+d+10 do if hg then p:=p+1;1 (*,

38、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.5 Sample語言語法制導(dǎo)翻譯語言語法制導(dǎo)翻譯程序的設(shè)計(jì)程序的設(shè)計(jì) 語法制導(dǎo)的翻譯實(shí)際上就是在語法分析的基礎(chǔ)上，當(dāng)分析完一個正確的語法單位后，調(diào)用相應(yīng)的語義處理程序，直接生成相應(yīng)的四元式表。

39、在第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(to

40、ken!= else) error; token = getnexttoken(); ST_SORT();/*處理else后的可執(zhí)行語句*/ := if then else 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 then else if tokenelse /* 處理處理else部