語法制導(dǎo)翻譯和中間代碼學(xué)時

語法制導(dǎo)翻譯和中間代碼學(xué)時第1頁，課件共41頁，創(chuàng)作于2023年2月8.1屬性文法預(yù)備知識源程序與目標程序，語法結(jié)構(gòu)完全不同，但語義相同，所以表達的結(jié)果完全相同。語義分析的2種處理方法： 1）語法分析之后，直接調(diào)用相應(yīng)的“語義子程序”進行語義處理 2）語法分析之后，先生成“語法樹”或其他形式，再進行語義處理語義分析的處理結(jié)果： 1）目標代碼 2）中間代碼：復(fù)雜性介于源程序語言和機器語言之間第2頁，課件共41頁，創(chuàng)作于2023年2月靜態(tài)語義分析：審查語法結(jié)構(gòu)的靜態(tài)語義

確定標識符的數(shù)據(jù)類型

類型檢查和轉(zhuǎn)換：檢查運算對象的數(shù)據(jù)類型是否合法，必要時進行類型轉(zhuǎn)換

一致性檢查：一個對象只能被聲明一次

作用域檢查

控制流檢查：控制語句轉(zhuǎn)到合法的地方繼續(xù)執(zhí)行翻譯（若靜態(tài)語義分析正確后才翻譯）語義處理的任務(wù)和功能第3頁，課件共41頁，創(chuàng)作于2023年2月常用的語義分析方法——語法制導(dǎo)翻譯語法制導(dǎo)翻譯：首先，使用屬性文法為工具，描述程序設(shè)計語言的語義規(guī)則。在語法分析時，每應(yīng)用一個產(chǎn)生式（推導(dǎo)或歸約），同時完成該產(chǎn)生式上所附的語義規(guī)則描述的動作，從而完成語義處理。語義分析的方法第4頁，課件共41頁，創(chuàng)作于2023年2月用于描述語義規(guī)則的文法。對文法的每個符號引入一些屬性，這些屬性代表與文法符號相關(guān)的信息，例如：類型、值、代碼序列、符號表內(nèi)容等。屬性值可以在語法分析過程中進行計算和傳遞。屬性的加工過程就是語義的處理過程。屬性文法

(attributegrammar)第5頁，課件共41頁，創(chuàng)作于2023年2月屬性文法的組成：一個上下文無關(guān)文法

一系列語義規(guī)則（附在文法的每個產(chǎn)生式上）屬性文法的形式：三元組A=(G,V,F)G:是一個上下文無關(guān)文法V:有窮屬性集,每個屬性與文法的一個終結(jié)符或非終結(jié)符關(guān)聯(lián)F:關(guān)于屬性的斷言或謂詞集.每個斷言與一個產(chǎn)生式關(guān)聯(lián).而此斷言只引用該產(chǎn)生式的終結(jié)符或非終結(jié)符相關(guān)聯(lián)的屬性屬性文法

(attributegrammar)第6頁，課件共41頁，創(chuàng)作于2023年2月屬性文法舉例例1說明語句中各種變量的類型信息的語義規(guī)則：

產(chǎn)生式 語義規(guī)則DTLTcharTintTfloatLL1,idLid{L.in:=T.type}{T.type:=char}{T.type:=int}{T.type:=float}{L1.in:=L.inaddtype(id.entry,L.in)}{addtype(id.entry,L.in)}第7頁，課件共41頁，創(chuàng)作于2023年2月屬性文法舉例例2表達式類型檢查和求值的語義規(guī)則：假設(shè)：類型不同的兩個變量進行運算則語義錯誤。

產(chǎn)生式 語義規(guī)則LEEE1+TETTT1*FTFF(E)Fid{print(E.val);}{if(E1.type==T.type){ E.type:=E1.type; E.val:=E1.val+T.val;}elseerror(); }{E.type:=T.type;E.val:=T.val}{getType(F.type,id.entry);F.val:=id.lexval;}第8頁，課件共41頁，創(chuàng)作于2023年2月語法制導(dǎo)翻譯的實質(zhì)： 根據(jù)每個產(chǎn)生式所對應(yīng)的語義規(guī)則，隨語法分析的每一步（推導(dǎo)或歸約），執(zhí)行相應(yīng)的語義動作。語法制導(dǎo)翻譯的過程：對單詞符號串進行語法分析，構(gòu)造語法分析樹；然后根據(jù)需要構(gòu)造屬性依賴圖，遍歷語法樹，并在語法樹的各結(jié)點處按語義規(guī)則進行計算。8.2語法制導(dǎo)翻譯概論第9頁，課件共41頁，創(chuàng)作于2023年2月使用“依賴圖”，從依賴圖的拓撲排序中得到計算語義規(guī)則的順序，再依照順序?qū)斎氪M行語義分析。依賴圖 一個有向圖，用于描述分析樹中的屬性和屬性之間的相互依賴關(guān)系。 構(gòu)造依賴圖舉例：參見P172圖8.4屬性計算方法

樹遍歷：事先建立語法樹，（深度優(yōu)先）遍歷直至計算出所有屬性值。

一遍掃描：在語法分析的同時計算屬性值。計算語義規(guī)則第10頁，課件共41頁，創(chuàng)作于2023年2月屬性：綜合屬性：可以在分析輸入串的同時，自下而上地來計算。如：val繼承屬性：一個結(jié)點的繼承屬性值是由此結(jié)點的父結(jié)點和（或）兄弟結(jié)點的某些屬性來決定的。如：L.in屬性文法：S-屬性文法：L-屬性文法的一個特例L-屬性文法：例1就是一個L-屬性文法屬性文法的計算：可以是普通意義上的數(shù)學(xué)運算，也可以是打印輸出等動作。屬性文法的類型和計算第11頁，課件共41頁，創(chuàng)作于2023年2月S-屬性文法：是L-屬性文法的一個特例，只含有綜合屬性。例2是一個S-屬性文法。S-屬性文法翻譯器：可以借助LR分析器實現(xiàn)。

實現(xiàn)原理：LR分析器中增加一個棧（語義值棧）用來存放綜合屬性的值，進行歸約的同時，棧中正在歸約的產(chǎn)生式右部符號的綜合屬性值彈棧，并調(diào)用相應(yīng)語義子程序進行相應(yīng)計算（完成屬性文法中的語義規(guī)則），產(chǎn)生的新值入語義值棧。舉例：參見P174圖8.7S-屬性文法和自下而上翻譯第12頁，課件共41頁，創(chuàng)作于2023年2月L-屬性文法：對于文法中的每個產(chǎn)生式AX1X2…Xn，其每個語義規(guī)則中的每個屬性要么是綜合屬性，要么是Xj(1≤j≤n)的一個繼承屬性且該繼承屬性僅依賴于：產(chǎn)生式中X1,X2,…Xj-1的屬性和A的繼承屬性。L-屬性文法優(yōu)點：允許一次遍歷就計算出所有屬性值。L-屬性文法第13頁，課件共41頁，創(chuàng)作于2023年2月L-屬性文法翻譯器：可以借助LL分析器實現(xiàn)。

實現(xiàn)原理：在自頂向下分析的過程中，每應(yīng)用一個產(chǎn)生式進行推導(dǎo)，同時完成該產(chǎn)生式上屬性文法的計算。LL(1)分析方法的語義描述：語義動作不是附在產(chǎn)生式右部的末尾，而是嵌在兩個符號之間。這樣的語義描述稱為翻譯模式。舉例：P174例8.3例8.4L-屬性文法在自上而下分析中的實現(xiàn)第14頁，課件共41頁，創(chuàng)作于2023年2月翻譯模式：語義動作不是附在產(chǎn)生式右部的末尾，而是嵌在兩個符號之間。翻譯模式是適合語法知道翻譯的另一種描述形式。翻譯模式給出了使用語義規(guī)則進行計算的次序，可把某些實現(xiàn)細節(jié)表現(xiàn)出來。翻譯模式第15頁，課件共41頁，創(chuàng)作于2023年2月何時將屬性文法改寫成翻譯模式？消除左遞歸時，原屬性文法將被改成翻譯模式。如何將屬性文法改寫成翻譯模式？原文法：AA1Y{A.a=g(A1.a,Y.y)}

AX {A.a=f(X.x)} 翻譯模式：AX{R.i=f(X.x)}R{A.a=R.s}RY{R1.i=g(R.i,Y.y)}R1

{R.s=R1.s}Rε{R.s=R.i}改寫成翻譯模式第16頁，課件共41頁，創(chuàng)作于2023年2月L-屬性文法中，如何實現(xiàn)自下而上計算繼承屬性？方法1：去掉翻譯模式中嵌入在產(chǎn)生式中間的動作。方法2：改變原文法或重新構(gòu)造文法，用綜合屬性代替繼承屬性。自學(xué)（P176,177）L-屬性文法在自下而上分析中的實現(xiàn)第17頁，課件共41頁，創(chuàng)作于2023年2月8.3中間代碼的形式中間代碼的常見形式：逆波蘭記號三元式樹形表示四元式第18頁，課件共41頁，創(chuàng)作于2023年2月逆波蘭記號（后綴式）特點：將運算對象寫在前面，把運算符號寫在后面標識符順序與表達式中的一致運算符順序與計算順序一致無括號表達式逆波蘭式a+bab+a+b*cabc*+(a+b)*cab+c*a=b*c+b*dabc*bd*+=為什么要使用逆波蘭式？更易于計算機處理，表示簡潔、計算方便。第19頁，課件共41頁，創(chuàng)作于2023年2月逆波蘭記號的擴充用途i--i@GotoLLjumpifEthenS1elseS2ES1S2￥A[n][m]nmAsubs逆波蘭式的復(fù)雜性：壓棧的可能是地址（如變量賦值），不是值；棧中不一定產(chǎn)生結(jié)果。逆波蘭式的計算機處理方法：自左向右掃描逆波蘭式，遇到運算對象入棧，遇到算符則將相應(yīng)數(shù)目的運算對象出棧計算后結(jié)果入棧。第20頁，課件共41頁，創(chuàng)作于2023年2月三元式和樹形表示三元式的格式：

(算符,第一運算對象,第二運算對象)如：a=b*c+b*d的三元式和樹形表示

(1) (*,b,c)

(2) (*,b,d)

(3) (+,(1),(2))

(4) (=,(3),a)=a+**bcbd第21頁，課件共41頁，創(chuàng)作于2023年2月四元式四元式的格式：

(算符,第一運算對象,第二運算對象,結(jié)果)如：a=b*c+b*d的四元式表示如下(*,a,b,t1)(*,b,d,t2)(+,t1,t2,t3)(:=,t3,-,a)t1:=a*bt2:=b*dt3:=t1+t2a:=t3或特點：利于代碼優(yōu)化和目標代碼生成特例：gotoL

的四元式為（jump,-,-,L）

ifBropCgotoL的四元式為(jrop,B,C,L)

第22頁，課件共41頁，創(chuàng)作于2023年2月8.4簡單賦值語句的翻譯說明：1）表示id所表示的單詞，用作語義變量2）lookup()審查是否出現(xiàn)在符號表是：返回指向該登錄項的指針否：返回nil3）emit將四元式輸出到中間文件（或目標文件）上4）newtemp生成一臨時變量5）E.place存放E值的變量名在符號表的登錄項 若變量為臨時變量，則直接存放一整數(shù)碼第23頁，課件共41頁，創(chuàng)作于2023年2月8.4簡單賦值語句的翻譯例3將賦值語句翻譯成四元式的語義描述：Sid:=E

EE1+

E2

EE1*

E2

E-E1

E(E1)

Eid

第24頁，課件共41頁，創(chuàng)作于2023年2月Sid:=E

{ P:=lookup();

ifPnilthen

emit(P,“:=”,E.place);

else

error();

}第25頁，課件共41頁，創(chuàng)作于2023年2月(2)

EE1+E2

{E.place:=newtemp;

emit(E.place,“:=”,E1.place,“+”,E2.place);

}(3)

EE1*E2{E.place:=newtemp;

emit(E.place,“:=”,E1.place,“*”,E2.place);

}第26頁，課件共41頁，創(chuàng)作于2023年2月(4)

E-E1

{E.place=newtemp;

emit(E.place,’:=’,’-’,E1.place);

}

(5)

E(E1)

{E.place=newtemp;

emit(E.place,’:=’,E1.place);

}

(6)

Eid

{p:=lookup();

if(p!=nil)E.place=p;

elseerror();

}第27頁，課件共41頁，創(chuàng)作于2023年2月8.5布爾表達式的翻譯1、布爾表達式的作用：計算邏輯值（返回真/假）控制流語句中的條件表達式

if(~)then while(~)2、布爾表達式的文法

EEandE EEorE EnotE Eidropid Etrue Efalse第28頁，課件共41頁，創(chuàng)作于2023年2月3、布爾表達式的計算方法：一步一步計算出式中各部分真假，最終算出整個表達式的值采用優(yōu)化措施，只計算部分表達式值即可 例如：aandb //a為0時，b無論是什么表達式的值都為0aorb //a為1時，b無論是什么表達式的值都為18.5布爾表達式的翻譯第29頁，課件共41頁，創(chuàng)作于2023年2月例如aorbandnotc對應(yīng)的四元式 (1)(not,c,-,t1) (2)(and,b,t1,t2) (3)(or,a,t2,t3)布爾表達式的翻譯第30頁，課件共41頁，創(chuàng)作于2023年2月EnotE1

{ E.true:=E1.false; E.codebegin:=E1.codebegin; E.false:=E1.true;}(2)EE1andE2 { backpatch(E1.true,E2.codebegin); E.codebegin:=E1.codebegin; E.true:=E2.true; E.false:=merge(E1.false,E2.false); }(3)EE1orE2 { backpatch(E1.false,E2.codebegin); E.codebegin:=E1.codebegin; E.true:=merge(E1.true,E2.true); E.false:=E2.false; }布爾表達式譯為四元式的語義描述：第31頁，課件共41頁，創(chuàng)作于2023年2月(4)E(E1)

{ E.true:=E1.true; E.codebegin:=E1.codebegin; E.false:=E1.false;}(5)Eid1ropid2 { E.true:=nextstat; E.codebegin:=nextstat; E.false:=nextstat+1;

emit(‘if’,id1.place,‘rop’,id2.place,‘goto’,–); emit(‘goto’,-); }(6)Eid { E.true:=nextstat; E.codebegin:=nextstat; E.false:=nextstat+1;

emit(‘if’,id1.place,‘goto’,–); emit(‘goto’,-); }第32頁，課件共41頁，創(chuàng)作于2023年2月控制語句SifEthenS1elseS2

E.falseE的代碼

E.trueE.false:S2的代碼gotooutE.true:S1的代碼out:控制語句中布爾表達式的翻譯第33頁，課件共41頁，創(chuàng)作于2023年2月舉例將下列控制語句翻譯成四元式ifa<borc<dande>fthenS1elseS2

控制語句中布爾表達式的翻譯

ifa<bgoto(i+1) //i+1是S1的入口

ifc<dgoto(4)

goto(6)

ife>fgoto(i+1)

[關(guān)于S2的四元式]

┋(i)goto(n) //n是S1的出口(i+1)[關(guān)于S1的四元式]

┋(n)第34頁，課件共41頁，創(chuàng)作于2023年2月例forI:=1step1untilNdoM:=M+I

對應(yīng)的四元式

For循環(huán)語句的翻譯

I:=1

goto(4)

I:=I+1

ifI<=Ngoto(6)

goto(9)

T:=M+I

M:=T

goto(3)……第35頁，課件共41頁，創(chuàng)作于2023年2月

課堂練習(xí)1(1)(2)(5)(6)(7)2[逆波蘭式、三元式、四元式序列]356