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

語法制導(dǎo)翻譯和中間代碼學(xué)時8.1概述8.2屬性文法8.3語法制導(dǎo)翻譯8.4中間代碼的形式逆波蘭式、三元式、樹形表示、四元式8.5一些語句的翻譯賦值語句布爾表達式控制語句中的布爾表達式

For循環(huán)語句8.6數(shù)組的翻譯第2頁,共50頁，2024年2月25日，星期天概述程序設(shè)計語言的語義靜態(tài)語義——是對程序約束的描述，這些約束無法通過抽象語法規(guī)則來妥善地描述，實質(zhì)上就是語法規(guī)則的良形式條件，它可以分為類型規(guī)則和作用域/可見性規(guī)則兩大類動態(tài)語義——程序單位描述的計算編譯程序的語義處理工作靜態(tài)語義審查解釋執(zhí)行動態(tài)語義（計算）生成代碼...第3頁,共50頁，2024年2月25日，星期天語義處理靜態(tài)語義分析：審查語法結(jié)構(gòu)的靜態(tài)語義確定標(biāo)識符的數(shù)據(jù)類型類型檢查和轉(zhuǎn)換：檢查運算對象的數(shù)據(jù)類型是否合法，必要時進行類型轉(zhuǎn)換一致性檢查：一個對象只能被聲明一次作用域檢查控制流檢查：控制語句轉(zhuǎn)到合法的地方繼續(xù)執(zhí)行翻譯（若靜態(tài)語義分析正確后才翻譯）第4頁,共50頁，2024年2月25日，星期天概述語義形式化 語義建模文法模型——屬性文法命令式或操作式模型——操作語義學(xué)應(yīng)用式模型——指稱語義學(xué)公理式模型——公理語義學(xué)第5頁,共50頁，2024年2月25日，星期天屬性文法表達式文法E—>T+T|TorTT—>n|bE

T1+T2{T1.type=intT2.type=T1.type E.type:=int}E

T1orT2{T1.type=bool T2.type=T1.type E.type:=bool}T

n{T.type:=int}T

b{T.type:=bool}第6頁,共50頁，2024年2月25日，星期天操作語義學(xué)通過執(zhí)行該段程序所改變的計算機狀態(tài)來反映語義。包括變量的所有值，可執(zhí)行程序本身，各種系統(tǒng)定義的內(nèi)部數(shù)據(jù)結(jié)構(gòu)。用一組形式定義的操作來說明執(zhí)行一條指令相應(yīng)的狀態(tài)怎樣變化。For(expr1;expr2;expr3)expr1;{Loop:ifexpr2=0gotoout

。。?！瓆expr3;gotoloopout:...第7頁,共50頁，2024年2月25日，星期天指稱語義學(xué)基本概念是給每一段程序?qū)嶓w定義一個數(shù)學(xué)意義上的對象，和一個從實體實例向數(shù)學(xué)意義對象的映射的函數(shù)特點：不但對全部程序賦予全文而且對程序設(shè)計語法每一個語法成分短語（表達式，命令，聲明…）都給予含義。每一個語法成分（短語）的含義是以它的自身成分的含義的術(shù)語來定義的。語義函數(shù)：程序設(shè)計語言的語義利用映射函數(shù)來證明。語義函數(shù)將短語映射到它的指稱。第8頁,共50頁，2024年2月25日，星期天Valuation[101]表示把Valuation施用于101Valuation[N]------把它施用于N

定義:Valuation（用四個方程)因為有四個形式numeralValuation[0]

0Valuation[1]

1Valuation[N0]

2

Valuation[N]Valuation[N1]

2

Valuation[N]+1

所以：

Valuation[110]=2

Valuation[11]=2

(2

Valuation[1]+1)=2

(2

1+1)=6第9頁,共50頁，2024年2月25日，星期天公理語義學(xué)一個語言的每個語法成分的含義定義為公理和演繹規(guī)則，用于推導(dǎo)出該成分執(zhí)行的效果。公理語義概念是隨著程序正確性的證明而發(fā)展的。當(dāng)正確性證明能構(gòu)造時表明程序執(zhí)行它的規(guī)格說明所描述的計算。在一個證明中，每一個語句之前之后都有一個邏輯表達式對程序的變量進行約束,以此說明這個語句的含義。一般的記號{P}S{Q}如果在語句S執(zhí)行前P為真，則在語句S執(zhí)行并終止后Q為真。第10頁,共50頁，2024年2月25日，星期天演繹規(guī)則的例子賦值：x:=expr{P(expr)}x:=expr{P(x)}While:{P∧B}S{P}{P}whileBdoSend{P∧(notB)}if--then--else{B∧P}S1{Q},{(notB)∧P}S2{Q}{P}ifBthenS1elseS2{Q}第11頁,共50頁，2024年2月25日，星期天8.2屬性文法預(yù)備知識源程序與目標(biāo)程序，語法結(jié)構(gòu)完全不同，但語義相同，所以表達的結(jié)果完全相同。語義分析的2種處理方法：

1）語法分析之后，直接調(diào)用相應(yīng)的“語義子程序”進行語義處理 2）語法分析之后，先生成“語法樹”或其他形式，再進行語義處理語義分析的處理結(jié)果：

1）目標(biāo)代碼 2）中間代碼：復(fù)雜性介于源程序語言和機器語言之間第12頁,共50頁，2024年2月25日，星期天常用的語義分析方法——語法制導(dǎo)翻譯語法制導(dǎo)翻譯：首先，使用屬性文法為工具，描述程序設(shè)計語言的語義規(guī)則。在語法分析時，每應(yīng)用一個產(chǎn)生式（推導(dǎo)或歸約），同時完成該產(chǎn)生式上所附的語義規(guī)則描述的動作，從而完成語義處理。語義分析的方法第13頁,共50頁，2024年2月25日，星期天用于描述語義規(guī)則的文法。對文法的每個符號引入一些屬性，這些屬性代表與文法符號相關(guān)的信息，例如：類型、值、代碼序列、符號表內(nèi)容等。屬性值可以在語法分析過程中進行計算和傳遞。屬性的加工過程就是語義的處理過程。屬性文法

(attributegrammar)第14頁,共50頁，2024年2月25日，星期天屬性文法的組成：一個上下文無關(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)第15頁,共50頁，2024年2月25日，星期天屬性文法舉例例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)}第16頁,共50頁，2024年2月25日，星期天屬性文法舉例例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;}第17頁,共50頁，2024年2月25日，星期天語法制導(dǎo)翻譯的實質(zhì)： 根據(jù)每個產(chǎn)生式所對應(yīng)的語義規(guī)則，隨語法分析的每一步（推導(dǎo)或歸約），執(zhí)行相應(yīng)的語義動作。語法制導(dǎo)翻譯的過程：對單詞符號串進行語法分析，構(gòu)造語法分析樹；然后根據(jù)需要構(gòu)造屬性依賴圖，遍歷語法樹，并在語法樹的各結(jié)點處按語義規(guī)則進行計算。8.3語法制導(dǎo)翻譯概論第18頁,共50頁，2024年2月25日，星期天屬性：綜合屬性：可以在分析輸入串的同時，自下而上地來計算。如：val繼承屬性：一個結(jié)點的繼承屬性值是由此結(jié)點的父結(jié)點和（或）兄弟結(jié)點的某些屬性來決定的。如：L.in屬性文法的計算：可以是普通意義上的數(shù)學(xué)運算，也可以是打印輸出等動作。屬性文法的類型和計算第19頁,共50頁，2024年2月25日，星期天設(shè)表達式為3＊5+4，則語義動作打印數(shù)值19.LE.val=19E.val=15T.val=4T.val=15F.val=4T.val=3F.val=3F.val=5digit.lexval=4digit.lexval=5digit.lexval=3+*3*5+4的帶注釋的分析樹第20頁,共50頁，2024年2月25日，星期天

DL.in=realL.in=realL.in=realT.type=realrealid2id1id3.Realid1,id2,id3，，第21頁,共50頁，2024年2月25日，星期天語法制導(dǎo)的翻譯一個翻譯是符號串對的一個集合。在一個編譯程序定義的翻譯中，符號串對是源程序和目標(biāo)程序。各個編譯階段定義一個翻譯，詞法分析：（字符串，單詞串）語法分析：（單詞串，語法樹）代碼生成（語法樹，匯編語言）第22頁,共50頁，2024年2月25日，星期天

把下述產(chǎn)生式定義的算術(shù)表達式映射到后綴波蘭表示：

EE+TET

TT

FTF

F(E)

Fa

E=ET+

E=T

T=TF

T=F

F=E

F=a產(chǎn)生式

翻譯規(guī)則第23頁,共50頁，2024年2月25日，星期天

確定輸入a+a

a的輸出：

(E,E)(E+T,ET+)

(T+T,TT+)

(F+T,FT+)(a+T,aT+)(a+TF,aFF+)(a+FF,aFF+)(a+aF,aaF+)(a+aa,aaa+)第24頁,共50頁，2024年2月25日，星期天8.4中間代碼的形式中間代碼的常見形式：逆波蘭記號三元式樹形表示四元式第25頁,共50頁，2024年2月25日，星期天逆波蘭記號（后綴式）特點：將運算對象寫在前面，把運算符號寫在后面標(biāo)識符順序與表達式中的一致運算符順序與計算順序一致無括號表達式逆波蘭式a+bab+a+b*cabc*+(a+b)*cab+c*a=b*c+b*dabc*bd*+=為什么要使用逆波蘭式？更易于計算機處理，表示簡潔、計算方便。第26頁,共50頁，2024年2月25日，星期天逆波蘭式的復(fù)雜性：壓棧的可能是地址（如變量賦值），不是值；棧中不一定產(chǎn)生結(jié)果。逆波蘭式的計算機處理方法：自左向右掃描逆波蘭式，遇到運算對象入棧，遇到算符則將相應(yīng)數(shù)目的運算對象出棧計算后結(jié)果入棧。第27頁,共50頁，2024年2月25日，星期天三元式和樹形表示三元式的格式：

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

(1) (*,b,c)

(2) (*,b,d)

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

(4) (=,(3),a)=a+**bcbd第28頁,共50頁，2024年2月25日，星期天四元式四元式的格式：

(算符,第一運算對象,第二運算對象,結(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)化和目標(biāo)代碼生成特例：gotoL

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

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

第29頁,共50頁，2024年2月25日，星期天8.5簡單語句的翻譯說明：1）

表示id所表示的單詞，用作語義變量2）lookup()

審查是否出現(xiàn)在符號表是：返回指向該登錄項的指針否：返回nil3）emit

將四元式輸出到中間文件（或目標(biāo)文件）上4）newtemp

生成一臨時變量5）E.place

存放E值的變量名在符號表的登錄項 若變量為臨時變量，則直接存放一整數(shù)碼第30頁,共50頁，2024年2月25日，星期天簡單賦值語句的翻譯例3將賦值語句翻譯成四元式的語義描述：S

id:=E

E

E1+

E2

E

E1*

E2

E

-E1

E

(E1)

E

id

第31頁,共50頁，2024年2月25日，星期天S

id:=E

{ P:=lookup();

ifP

nilthen

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

else

error();

}第32頁,共50頁，2024年2月25日，星期天(2)

E

E1+E2

{E.place:=newtemp;

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

}(3)

E

E1*E2{E.place:=newtemp;

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

}第33頁,共50頁，2024年2月25日，星期天(4)

E

-E1

{E.place=newtemp;

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

}

(5)

E

(E1)

{E.place=newtemp;

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

}

(6)

E

id

{p:=lookup();

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

elseerror();

}第34頁,共50頁，2024年2月25日，星期天布爾表達式的翻譯1、布爾表達式的作用：計算邏輯值（返回真/假）控制流語句中的條件表達式

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

E

EandE E

EorE E

notE E

idropid E

true E

false第35頁,共50頁，2024年2月25日，星期天3.計算布爾表達式通常采用兩種方法:(1).如同計算算術(shù)表達式一樣,一步步算

1or(not0and0)or0=1or(1and0)or0=1or0or0=1or0=1(2).采用某種優(yōu)化措施把AorB解釋成 ifAthentrueelseB

把AandB解釋成 ifAthenBelsefalse

把

A解釋成 ifAthenfalseelsetrue第36頁,共50頁，2024年2月25日，星期天例如aorbandnotc

對應(yīng)的四元式第一種翻譯法

(1)(not,c,-,t1) (2)(and,b,t1,t2) (3)(or,a,t2,t3)布爾表達式的翻譯第37頁,共50頁，2024年2月25日，星期天關(guān)于布爾表達式的數(shù)值表示法的翻譯模式過程emit將三地址代碼送到輸出文件中nextstat給出輸出序列中下一條三地址語句的地址索引每產(chǎn)生一條三地址語句后，過程emit便把nextstat加1第38頁,共50頁，2024年2月25日，星期天關(guān)于布爾表達式的數(shù)值表示法的翻譯模式E→E1orE2{E.place:=newtemp; emit(E.place‘:=’E1.place‘or’E2.place)}E→E1andE2{E.place:=newtemp; emit(E.place‘:=’E1.place‘a(chǎn)nd’E2.place)}E→notE1 {E.place:=newtemp; emit(E.place‘:=’‘not’E1.place)}E→(E1) {E.place:=E1.place}第39頁,共50頁，2024年2月25日，星期天關(guān)于布爾表達式的數(shù)值表示法的翻譯模式E

id1relopid2{E.place:=newtemp;

emit(‘if’id1.placerelop.opid2.place ‘goto’nextstat+3);

emit(E.place‘:=’‘0’);

emit(‘goto’nextstat+2);

emit(E.place‘:=’‘1’)}E→id {E.place:=id.place}a<b翻譯成100: ifa<bgoto103101: T:=0102: goto104103: T:=1104:第40頁,共50頁，2024年2月25日，星期天布爾表達式a<borc<dande<f的翻譯結(jié)果100: ifa<bgoto103101: T1:=0 102: goto104103: T1:=1104: ifc<dgoto107105: T2:=0 106: goto108107: T2:=1108:ife<fgoto111109:T3:=0110:goto112111:T3:=1112:T4:=T2andT3113:T5:=T1orT4E

id1relopid2

{E.place:=newtemp; emit(‘if’id1.placerelop.opid2.place ‘goto’nextstat+3); emit(E.place‘:=’‘0’); emit(‘goto’nextstat+2); emit(E.place‘:=’‘1’)}E→id {E.place:=id.place}E→E1orE2

{E.place:=newtemp; emit(E.place‘:=’E1.place‘or’E2.place)}E→E1andE2{E.place:=newtemp;emit(E.place‘:=’E1.place‘a(chǎn)nd’E2.place)}第41頁,共50頁，2024年2月25日，星期天控制語句S

ifEthenS1

elseS2

E.falseE的代碼

E.trueE.false:S2的代碼gotooutE.true:S1的代碼out:控制語句中布爾表達式的翻譯第42頁,共50頁，2024年2月25日，星期天例：把語句:ifa>corb<dthenS1elseS2翻譯成如下的一串三地址代碼

ifa>cgotoL2“真”出口

gotoL1L1: ifb<dgotoL2“真”出口

gotoL3“假”出口L2: (關(guān)于S1的三地址代碼序列) gotoLnextL3: (關(guān)于S2的三地址代碼序列)Lnext:第43頁,共50頁，2024年2月25日，星期天每次調(diào)用函數(shù)newlabel后都返回一個新的符號標(biāo)號對于一個布爾表達式E，引用兩個標(biāo)號E.true是E為‘真’時控制流轉(zhuǎn)向的標(biāo)號E.false是E為‘假’時控制流轉(zhuǎn)向的標(biāo)號第44頁,共50頁，2024年2月25日，星期天產(chǎn)生布爾表達式三地址代碼的語義規(guī)則 產(chǎn)生式 語義規(guī)則

E→E1orE2

E1.true:=E.true; E1.false:=newlabel; E2.true:=E.true; E2.false:=E.false; E.code:=E1.code|| gen(E1.false‘:’)||E2.code

E1.codeToE.trueToE1.falseE2.codeToE.trueToE.false第45頁,共50頁，2024年2月25日，星期天產(chǎn)生布爾表達式三地址代碼的語義規(guī)則

產(chǎn)生式 語義規(guī)則

E→E1andE