語法制導(dǎo)翻譯技術(shù)市公開課金獎(jiǎng)市賽課一等獎(jiǎng)?wù)n件

語義分析任務(wù)：靜態(tài)語義審查審查每個(gè)語法結(jié)構(gòu)靜態(tài)語義,即驗(yàn)證語法結(jié)構(gòu)合法程序,是否真正故意義。第5章語法制導(dǎo)翻譯技術(shù)和中間代碼生成5.1概述第1頁第1頁比如:表示式A+B*C對運(yùn)算對象進(jìn)行類型檢查,對變量進(jìn)行先定義后使用檢查假如靜態(tài)語義正確,語義處理則要執(zhí)行真正翻譯,即生成程序某種中間代碼形式或直接生成目的代碼。執(zhí)行真正翻譯第5章語法制導(dǎo)翻譯技術(shù)和中間代碼生成第2頁第2頁當(dāng)前多數(shù)編譯程序進(jìn)行語義分析辦法是采用語法制導(dǎo)翻譯法

。它不是一個(gè)形式系統(tǒng),但它比較靠近形式化。

語法制導(dǎo)翻譯法使用屬性文法為工具來描述程序設(shè)計(jì)語言語義。第5章語法制導(dǎo)翻譯技術(shù)和中間代碼生成第3頁第3頁(1)屬性對文法每一個(gè)符號,引進(jìn)一些屬性,這些屬性代表與文法符號相關(guān)信息,如類型、值、存儲(chǔ)位置等。與屬性相關(guān)信息,即屬性值,能夠在語法分析過程中計(jì)算和傳遞。5.2屬性文法第5章語法制導(dǎo)翻譯技術(shù)和中間代碼生成第4頁第4頁屬性分為兩類:綜合屬性其計(jì)算規(guī)則按“自下而上”方式進(jìn)行,即規(guī)則左部符號一些屬性依據(jù)其右部符號屬性和(或)自己其它屬性計(jì)算而得。屬性加工過程即是語義處理過程。綜合屬性和繼承屬性。第5章語法制導(dǎo)翻譯技術(shù)和中間代碼生成第5頁第5頁繼承屬性其計(jì)算規(guī)則按“自上而下”方式進(jìn)行,即規(guī)則右部符號一些屬性依據(jù)其左部符號屬性和(或)右部其它符號一些屬性計(jì)算而得。第5章語法制導(dǎo)翻譯技術(shù)和中間代碼生成第6頁第6頁(2)屬性文法為文法每一個(gè)規(guī)則配備計(jì)算屬性計(jì)算規(guī)則,稱為語義規(guī)則(描述語義處理加工動(dòng)作)。屬性文法包括一個(gè)上下文無關(guān)文法和一系列語義規(guī)則。語義規(guī)則:第5章語法制導(dǎo)翻譯技術(shù)和中間代碼生成第7頁第7頁這些語義規(guī)則附在文法每個(gè)產(chǎn)生式上,在語法分析過程中,執(zhí)行語義規(guī)則描述動(dòng)作,從而實(shí)現(xiàn)語義處理。也就是說,附在文法每個(gè)產(chǎn)生式上語義規(guī)則描述了語義處理加工動(dòng)作。當(dāng)前流行語義描述和語義處理辦法主要是屬性文法和語法制導(dǎo)翻譯辦法。第5章語法制導(dǎo)翻譯技術(shù)和中間代碼生成第8頁第8頁G：E→E+T|TT→T*F|FF→(E)|iG：D→TLT→integer|realL→L,id|id

第9頁第9頁5.3語法制導(dǎo)翻譯概述

為文法每個(gè)產(chǎn)生式都配備一個(gè)語義動(dòng)作或語義子程序。在語法分析過程中，每當(dāng)使用一條產(chǎn)生式進(jìn)行推導(dǎo)或歸約時(shí)，就執(zhí)行相應(yīng)產(chǎn)生式語義動(dòng)作,從而實(shí)現(xiàn)語義處理。第5章語法制導(dǎo)翻譯技術(shù)和中間代碼生成(1)語法制導(dǎo)翻譯法基本思想第10頁第10頁S→……{……}………A→xy{……}………

a1a2a3…aiai+1…an語義處理加工動(dòng)作語法制導(dǎo)翻譯法使用屬性文法為工具來闡明程序設(shè)計(jì)語言語義。第5章語法制導(dǎo)翻譯技術(shù)和中間代碼生成第11頁第11頁(2)語法制導(dǎo)翻譯法在語法分析過程中，依隨分析過程，依據(jù)每個(gè)產(chǎn)生式所相應(yīng)語義子程序(或語義規(guī)則描述語義處理加工動(dòng)作)進(jìn)行翻譯辦法。第5章語法制導(dǎo)翻譯技術(shù)和中間代碼生成第12頁第12頁為文法每一產(chǎn)生式設(shè)計(jì)相應(yīng)求值語義描述(語義動(dòng)作)：比如，設(shè)有簡樸算術(shù)表示式文法：

E→E＋E|E*E|(E)|digit1.E→E(1)＋E(2)

{E.val＝E(1).val＋E(2).val}2.E→E(1)*E(2)

{E.val＝E(1).val*E(2).val}3.E→(E(1)){E.val＝E(1).val}4.E→digit{E.val＝Lex.digit}{7+8*5,3+8,6*5,…}第5章語法制導(dǎo)翻譯技術(shù)和中間代碼生成第13頁第13頁1.E→E(1)＋E(2)

{E.val＝E(1).val＋E(2).val}2.E→E(1)*E(2)

{E.val＝E(1).val*E(2).val}3.E→(E(1)){E.val＝E(1).val}4.E→digit{E.val＝Lex.digit}句子7+8*5E.val=47E.val=8E.val=40E.val=7E.val=5+5*87EEEEE第14頁第14頁 5.4

編譯中慣用中間代碼:逆波蘭式四元式三元式樹形表示第5章語法制導(dǎo)翻譯技術(shù)和中間代碼生成第15頁第15頁逆波蘭式

逆波蘭式除去了原表示式中括號，并將運(yùn)算對象寫在前面，運(yùn)算符寫在后面，因而又稱為后綴式。比如：逆波蘭式a*bab*(a+b)*(c+d)ab+cd+*中綴表示式第5章語法制導(dǎo)翻譯技術(shù)和中間代碼生成第16頁第16頁逆波蘭式表示法同中綴表示法相比其長處是:不再有括號,且運(yùn)算符出現(xiàn)順序體現(xiàn)了中綴表示式運(yùn)算順序2.易于計(jì)算機(jī)處理第5章語法制導(dǎo)翻譯技術(shù)和中間代碼生成第17頁第17頁普通表示式計(jì)值時(shí)，要處理兩類符號，一類是運(yùn)算對象，另一類是運(yùn)算符，通慣用兩個(gè)工作棧分別處理。但處理用逆波蘭式表示表示式卻只用一個(gè)工作棧。第5章語法制導(dǎo)翻譯技術(shù)和中間代碼生成第18頁第18頁當(dāng)計(jì)算機(jī)自左到右順序掃描逆蘭波式時(shí)，若當(dāng)前符號是運(yùn)算對象則進(jìn)棧，若當(dāng)前符號是運(yùn)算符，設(shè)為K元運(yùn)算符，則將棧頂K個(gè)元素依次取出，同時(shí)進(jìn)行K元運(yùn)算，并將運(yùn)算結(jié)果置于棧頂，表示式處理完畢時(shí)，其計(jì)算結(jié)果自然呈現(xiàn)在棧頂。第5章語法制導(dǎo)翻譯技術(shù)和中間代碼生成第19頁第19頁逆波蘭式ab+c*處理過程以下圖：baT1cT1T2第5章語法制導(dǎo)翻譯技術(shù)和中間代碼生成第20頁第20頁逆波蘭形式能夠推廣到其它語法結(jié)構(gòu)：賦值語句V=E逆波蘭式VE=條件語句逆波蘭式ifES1;elseS2ES1S2￥第5章語法制導(dǎo)翻譯技術(shù)和中間代碼生成第21頁第21頁三元式和樹形表示三元式主要由三部分構(gòu)成：（OP，arg1,arg2）其中OP是運(yùn)算符，arg1,arg2分別是第一和第二兩個(gè)運(yùn)算對象。當(dāng)OP是一目運(yùn)算時(shí)，經(jīng)常將運(yùn)算對象定義為arg1。第5章語法制導(dǎo)翻譯技術(shù)和中間代碼生成第22頁第22頁比如a+b*c三元式序列：(1)(*,b,c)(2)(+,a,(1))運(yùn)算對象是指向符號表某一項(xiàng)或指向三元式表某一項(xiàng)。第5章語法制導(dǎo)翻譯技術(shù)和中間代碼生成第23頁第23頁1.三元式出現(xiàn)順序和語法成份計(jì)值順序相一致。三元式特點(diǎn)：2.三元式之間聯(lián)系是通過批示器實(shí)現(xiàn)。第5章語法制導(dǎo)翻譯技術(shù)和中間代碼生成第24頁第24頁間接三元式(1)間接三元式表:用來存儲(chǔ)各三元式本身。(2)間接碼表:按執(zhí)行各三元式順序,依次列出各三元式在三元式表中位置。注意:間接三元式表中不存儲(chǔ)重復(fù)三元式。第5章語法制導(dǎo)翻譯技術(shù)和中間代碼生成第25頁第25頁比如

語句X=(A+B)*C

Y=D↑(A+B)三元式序列(1)(+,A,B)(2)(*,(1),C)(3)(=,X,(2))(5)(↑,D,(4))(4)(+,A,B)(6)(=,Y,(5))間接三元式間接碼表三元式表(1)(2)(3)(1)(4)(5)(1)(+,A,B)(2)(*,(1),C)(3)(=,X,(2))(4)(↑,D,(1))(5)(=,Y,(4))第5章語法制導(dǎo)翻譯技術(shù)和中間代碼生成第26頁第26頁樹形表示

A*B+C*D+C*A*BD末端結(jié)點(diǎn)表示一個(gè)運(yùn)算對象,每一個(gè)內(nèi)結(jié)點(diǎn)表示一個(gè)一元或二元運(yùn)算符。樹形表示是三元式翻版(3)+(1)*(2)*CABD第5章語法制導(dǎo)翻譯技術(shù)和中間代碼生成第27頁第27頁四元式主要由四部分構(gòu)成：（OP，arg1,arg2,result）其中OP是運(yùn)算符，arg1,arg2分別是第一和第二兩個(gè)運(yùn)算對象。當(dāng)OP是一目運(yùn)算時(shí)，經(jīng)常將運(yùn)算對象定義為arg1。第5章語法制導(dǎo)翻譯技術(shù)和中間代碼生成第28頁第28頁四元式第四個(gè)分量result是編譯程序?yàn)榇鎯?chǔ)中間運(yùn)算結(jié)果而暫時(shí)引進(jìn)變量，常稱為暫時(shí)變量，如Ti，也能夠是用戶自定義變量，如X。比如X＝a*b＋c/d四元式序列：(1)(*,a,b,T1)(2)(/,c,d,T2)(3)(+,T1,T2,T3)(4)(=,T3,-,X

)第5章語法制導(dǎo)翻譯技術(shù)和中間代碼生成第29頁第29頁2.四元式之間聯(lián)系是通過暫時(shí)變量實(shí)現(xiàn)，這樣易于調(diào)整和變動(dòng)四元式。1.四元式出現(xiàn)順序和語法成份計(jì)值順序相一致。四元式特點(diǎn)：3.便于優(yōu)化處理。第5章語法制導(dǎo)翻譯技術(shù)和中間代碼生成四元式還能夠表示條件轉(zhuǎn)移(ifa>bgoto0)(goto0)第30頁第30頁編譯系統(tǒng)中，有時(shí)將四元式表示成另一個(gè)更直觀，更易理解形式——三地址代碼或三地址語句。result:＝arg1OParg2

三地址語句:語句中是三個(gè)量賦值語句,每個(gè)量占一個(gè)地址。三地址代碼形式定義為：第5章語法制導(dǎo)翻譯技術(shù)和中間代碼生成第31頁第31頁比如X＝a*b＋c/d四元式序列：(1)(*,a,b,T1)(2)(/,c,d,T2)(3)(+,T1,T2,T3)(4)(=,T3,-,X

)相應(yīng)三地址語句序列為：（1）T1＝a*b（2）T2＝c/d（3）T3＝T1＋T2

（4）X＝T3

第5章語法制導(dǎo)翻譯技術(shù)和中間代碼生成第32頁第32頁例1.–a+b*(–c+d)逆波蘭式a@bc@d+*+第5章語法制導(dǎo)翻譯技術(shù)和中間代碼生成第33頁第33頁t1=@a

t2=@c

t3=t2+dt5=t1+t4

–a+b*(–c+d)四元式表示

t4=b*t3第5章語法制導(dǎo)翻譯技術(shù)和中間代碼生成第34頁第34頁i↑(i/(i–i))逆波蘭式

i↑(i/(i–i))四元式

t1=i–i

t2=i/t1t3=i↑t2iiii–/↑例2.第5章語法制導(dǎo)翻譯技術(shù)和中間代碼生成第35頁第35頁語義函數(shù)emit（T＝arg1OParg2）

功效是生成一個(gè)三地址語句，并送到輸出文獻(xiàn)中。語義函數(shù)newtemp()

功效是產(chǎn)生一個(gè)新暫時(shí)變量名字，并回送新暫時(shí)變量名整數(shù)碼。如T1，T2等。5.5.1簡樸算術(shù)表示式和賦值語句翻譯第36頁第36頁(2)不進(jìn)符號表，暫時(shí)變量單詞值部分用整數(shù)碼表示。(1)送到符號表。對暫時(shí)變量有兩種不同處理方法:第5章語法制導(dǎo)翻譯技術(shù)和中間代碼生成第37頁第37頁語義過程Lookup（）

功效是審查是否出現(xiàn)在符號表中，在則返回其指針，不然返回NULL。語義變量E.place

表示存儲(chǔ)非終止符E值變量名在符號表中入口地址或暫時(shí)變量名整數(shù)碼。第5章語法制導(dǎo)翻譯技術(shù)和中間代碼生成第38頁第38頁1.E→E(1)＋E(2)2.E→E(1)*E(2){E.place＝newtemp();emit(E.place’＝’E(1).place’＋’E(2).place)}{E.place＝newtemp();emit(E.place’＝’E(1).place’*’E(2).place)}第5章語法制導(dǎo)翻譯技術(shù)和中間代碼生成3.E→（E(1)）{E.place＝E(1).place；}第39頁第39頁4.E→i{p＝Lookup();if(p!=NULL)E.place＝p;elseerror();}第5章語法制導(dǎo)翻譯技術(shù)和中間代碼生成5.A→i=E

{p＝Lookup();if(p!=NULL)emit(p’＝’E.place;)elseerror();}第40頁第40頁5.5.2布爾表示式到四元式翻譯一.布爾表示式文法

●計(jì)算邏輯值程序設(shè)計(jì)語言中布爾表示式有兩個(gè)作用:

●用作控制語句中條件式布爾表示式是由布爾算符(∧、∨和)施于布爾變量或關(guān)系表示式而成。

第41頁第41頁布爾表示式到四元式翻譯

E→E(1)∨E(2)

E→E(1)∧E(2)

E→

E(1)

E→(E(1))

E→i(1)ropi(2)

E→i第42頁第42頁布爾表示式到四元式翻譯二.布爾表示式計(jì)值辦法1.如同計(jì)算算術(shù)表示式同樣,步步計(jì)算出各部分真、假值,最后計(jì)算出整個(gè)表示式值。2.依據(jù)布爾運(yùn)算特殊性,采用某種優(yōu)化辦法,可避免計(jì)算整個(gè)表示式值。第43頁第43頁布爾表示式到四元式翻譯

A∨B解釋成

A∧B解釋成

A解釋成ifAthentrueelseBifAthenBelsefalseifAthenfalseelsetrue三.布爾表示式翻譯辦法1.同翻譯算術(shù)表示式同樣,翻譯布爾表示式。第44頁第44頁布爾表示式到四元式翻譯1.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)}第45頁第45頁3.E→(E(1)){E.place＝E(1).place；}4.E→i(1)ropi(2){E.place＝newtemp()；emit(‘if’i(1).placerop.opi(2).place‘goto’nextq+3);emit(E.place’＝’‘0’);emit(gotonextq+2);emit(E.place’＝’‘1’);}{E.place＝i.place；}5.E→i

第46頁第46頁布爾表示式到四元式翻譯比如布爾表示式a=b∨c∧d相應(yīng)下列四元式序列:101ifa=bgoto104102t1=0103goto105104t1=1105t2=c∧d106t3=t1∨

t2

第47頁第47頁布爾表示式到四元式翻譯2.控制語句中布爾表示式翻譯條件語句語法為:依據(jù)條件語句語義,條件語句代碼結(jié)構(gòu)為:ifEthenS(1)elseS(2)E代碼S(1)代碼S(2)代碼Jumpout

out:

真

假第48頁第48頁布爾表示式到四元式翻譯

E是布爾表示式,依據(jù)布爾運(yùn)算特殊性,布爾表示式目的結(jié)構(gòu)為:假E(1)代碼∨E(2)代碼真S(1)S(2)真假真E(1)代碼∧E(2)代碼假S(2)S(1)假真第49頁第49頁(1)真出口和假出口:真出口表示布爾表示式E為真時(shí)控制流向轉(zhuǎn)移目的假出口表示布爾表示式E為假時(shí)控制流向轉(zhuǎn)移目的布爾表示式到四元式翻譯第50頁第50頁(2)作為條件轉(zhuǎn)移E,把E翻譯成代碼是一串條件轉(zhuǎn)或無條件轉(zhuǎn)四元式對于E為aropb形式生成代碼為:ifaropbgoto真出口goto假出口布爾表示式到四元式翻譯第51頁第51頁布爾表示式到四元式翻譯布爾表示式真、假出口不能在產(chǎn)生其四元式同時(shí)得知E.true:統(tǒng)計(jì)表示式E所相應(yīng)四元式需回填真出口四元式地址所構(gòu)成鏈E.false:統(tǒng)計(jì)表示式E所相應(yīng)四元式需回填假出口四元式地址所構(gòu)成鏈(3)設(shè)置兩個(gè)語義變量:第52頁第52頁布爾表示式到四元式翻譯把以p1,p2為鏈?zhǔn)變蓷l鏈合并為一,返回合并后鏈?zhǔn)?4)鏈結(jié)函數(shù)和回填函數(shù):●merge(p1,p2):●backpatch(intp,intt):

將p所鏈結(jié)每個(gè)四元式第四區(qū)別量都回填t;第53頁第53頁布爾表示式到四元式翻譯為及時(shí)回填轉(zhuǎn)移地址,使用語義變量

E.bcode統(tǒng)計(jì)表示式E第一個(gè)四元式語句序號。(6)定義語義變量nextq為四元式表指針。第54頁第54頁布爾表示式到四元式翻譯布爾表示式語義動(dòng)作設(shè)計(jì)1.E→E(1)∨E(2){backpatch(E(1).false,E(2).bcode)；E.bcode=E(1).bcode;E.true=merge(E(1).true,E(2).true);E.false=E(2).false;}第55頁第55頁布爾表示式到四元式翻譯布爾表示式語義動(dòng)作設(shè)計(jì)2.E→E(1)∧E(2){backpatch(E(1).true,E(2).bcode)；E.bcode=E(1).bcode;E.true=E(2).true;E.false=merge(E(1).false,E(2).false);}第56頁第56頁布爾表示式語義動(dòng)作設(shè)計(jì)3.E→

E(1){E.bcode=E(1).bcode;E.true=E(1).false

;E.false=E(1).true;}布爾表示式到四元式翻譯

4.E→(E(1)){E.bcode=E(1).bcode;E.true=E(1).true;E.false=E(1).false;}第57頁第57頁布爾表示式語義動(dòng)作設(shè)計(jì)

5.E→i(1)ropi(2){E.true=nextq;E.bcode=nextq;E.false=nextq+1;emit(ifi(1).placerop.opi(2).placegoto0);emit(goto0);}布爾表示式到四元式翻譯第58頁第58頁布爾表示式到四元式翻譯布爾表示式語義動(dòng)作設(shè)計(jì)

6.E→i{E.true=nextq;E.false=nextq+1;E.bcode=nextq;emit(ifi.placegoto0);emit(goto0);}第59頁第59頁布爾表示式到四元式翻譯比如布爾表示式a<b∨c<d翻譯過程第60頁第60頁5.5.3控制語句翻譯1.S→ifEthenS(1)2.

|ifEthenS(1)

elseS(2)3.

|whileEdoS(1)

4.

L→L；S5.

|S第61頁第61頁C→ifEthenS→CS(1)C→ifEthen{backpatch(E.true,nextq);C.chain=E.false}1、單分支條件句：S→CS(1){S.chain=merge(C.chain,S(1).chain)}例：ifa<bthena=b第62頁第62頁2、雙分支if語句：C→ifE