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

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

For循環(huán)語(yǔ)句8.6數(shù)組的翻譯第2頁(yè),共50頁(yè)，2024年2月25日，星期天概述程序設(shè)計(jì)語(yǔ)言的語(yǔ)義靜態(tài)語(yǔ)義——是對(duì)程序約束的描述，這些約束無(wú)法通過(guò)抽象語(yǔ)法規(guī)則來(lái)妥善地描述，實(shí)質(zhì)上就是語(yǔ)法規(guī)則的良形式條件，它可以分為類(lèi)型規(guī)則和作用域/可見(jiàn)性規(guī)則兩大類(lèi)動(dòng)態(tài)語(yǔ)義——程序單位描述的計(jì)算編譯程序的語(yǔ)義處理工作靜態(tài)語(yǔ)義審查解釋執(zhí)行動(dòng)態(tài)語(yǔ)義（計(jì)算）生成代碼...第3頁(yè),共50頁(yè)，2024年2月25日，星期天語(yǔ)義處理靜態(tài)語(yǔ)義分析：審查語(yǔ)法結(jié)構(gòu)的靜態(tài)語(yǔ)義確定標(biāo)識(shí)符的數(shù)據(jù)類(lèi)型類(lèi)型檢查和轉(zhuǎn)換：檢查運(yùn)算對(duì)象的數(shù)據(jù)類(lèi)型是否合法，必要時(shí)進(jìn)行類(lèi)型轉(zhuǎn)換一致性檢查：一個(gè)對(duì)象只能被聲明一次作用域檢查控制流檢查：控制語(yǔ)句轉(zhuǎn)到合法的地方繼續(xù)執(zhí)行翻譯（若靜態(tài)語(yǔ)義分析正確后才翻譯）第4頁(yè),共50頁(yè)，2024年2月25日，星期天概述語(yǔ)義形式化 語(yǔ)義建模文法模型——屬性文法命令式或操作式模型——操作語(yǔ)義學(xué)應(yīng)用式模型——指稱(chēng)語(yǔ)義學(xué)公理式模型——公理語(yǔ)義學(xué)第5頁(yè),共50頁(yè)，2024年2月25日，星期天屬性文法表達(dá)式文法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頁(yè),共50頁(yè)，2024年2月25日，星期天操作語(yǔ)義學(xué)通過(guò)執(zhí)行該段程序所改變的計(jì)算機(jī)狀態(tài)來(lái)反映語(yǔ)義。包括變量的所有值，可執(zhí)行程序本身，各種系統(tǒng)定義的內(nèi)部數(shù)據(jù)結(jié)構(gòu)。用一組形式定義的操作來(lái)說(shuō)明執(zhí)行一條指令相應(yīng)的狀態(tài)怎樣變化。For(expr1;expr2;expr3)expr1;{Loop:ifexpr2=0gotoout

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

定義:Valuation（用四個(gè)方程)因?yàn)橛兴膫€(gè)形式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頁(yè),共50頁(yè)，2024年2月25日，星期天公理語(yǔ)義學(xué)一個(gè)語(yǔ)言的每個(gè)語(yǔ)法成分的含義定義為公理和演繹規(guī)則，用于推導(dǎo)出該成分執(zhí)行的效果。公理語(yǔ)義概念是隨著程序正確性的證明而發(fā)展的。當(dāng)正確性證明能構(gòu)造時(shí)表明程序執(zhí)行它的規(guī)格說(shuō)明所描述的計(jì)算。在一個(gè)證明中，每一個(gè)語(yǔ)句之前之后都有一個(gè)邏輯表達(dá)式對(duì)程序的變量進(jìn)行約束,以此說(shuō)明這個(gè)語(yǔ)句的含義。一般的記號(hào){P}S{Q}如果在語(yǔ)句S執(zhí)行前P為真，則在語(yǔ)句S執(zhí)行并終止后Q為真。第10頁(yè),共50頁(yè)，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頁(yè),共50頁(yè)，2024年2月25日，星期天8.2屬性文法預(yù)備知識(shí)源程序與目標(biāo)程序，語(yǔ)法結(jié)構(gòu)完全不同，但語(yǔ)義相同，所以表達(dá)的結(jié)果完全相同。語(yǔ)義分析的2種處理方法：

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

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

(attributegrammar)第14頁(yè),共50頁(yè)，2024年2月25日，星期天屬性文法的組成：一個(gè)上下文無(wú)關(guān)文法

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

(attributegrammar)第15頁(yè),共50頁(yè)，2024年2月25日，星期天屬性文法舉例例1說(shuō)明語(yǔ)句中各種變量的類(lèi)型信息的語(yǔ)義規(guī)則：

產(chǎn)生式 語(yǔ)義規(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頁(yè),共50頁(yè)，2024年2月25日，星期天屬性文法舉例例2表達(dá)式類(lèi)型檢查和求值的語(yǔ)義規(guī)則：假設(shè)：類(lèi)型不同的兩個(gè)變量進(jìn)行運(yùn)算則語(yǔ)義錯(cuò)誤。

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

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

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

EE+TET

TT

FTF

F(E)

Fa

E=ET+

E=T

T=TF

T=F

F=E

F=a產(chǎn)生式

翻譯規(guī)則第23頁(yè),共50頁(yè)，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頁(yè),共50頁(yè)，2024年2月25日，星期天8.4中間代碼的形式中間代碼的常見(jiàn)形式：逆波蘭記號(hào)三元式樹(shù)形表示四元式第25頁(yè),共50頁(yè)，2024年2月25日，星期天逆波蘭記號(hào)（后綴式）特點(diǎn)：將運(yùn)算對(duì)象寫(xiě)在前面，把運(yùn)算符號(hào)寫(xiě)在后面標(biāo)識(shí)符順序與表達(dá)式中的一致運(yùn)算符順序與計(jì)算順序一致無(wú)括號(hào)表達(dá)式逆波蘭式a+bab+a+b*cabc*+(a+b)*cab+c*a=b*c+b*dabc*bd*+=為什么要使用逆波蘭式？更易于計(jì)算機(jī)處理，表示簡(jiǎn)潔、計(jì)算方便。第26頁(yè),共50頁(yè)，2024年2月25日，星期天逆波蘭式的復(fù)雜性：壓棧的可能是地址（如變量賦值），不是值；棧中不一定產(chǎn)生結(jié)果。逆波蘭式的計(jì)算機(jī)處理方法：自左向右掃描逆波蘭式，遇到運(yùn)算對(duì)象入棧，遇到算符則將相應(yīng)數(shù)目的運(yùn)算對(duì)象出棧計(jì)算后結(jié)果入棧。第27頁(yè),共50頁(yè)，2024年2月25日，星期天三元式和樹(shù)形表示三元式的格式：

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

(1) (*,b,c)

(2) (*,b,d)

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

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

(算符,第一運(yùn)算對(duì)象,第二運(yùn)算對(duì)象,結(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或特點(diǎn)：利于代碼優(yōu)化和目標(biāo)代碼生成特例：gotoL

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

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

第29頁(yè),共50頁(yè)，2024年2月25日，星期天8.5簡(jiǎn)單語(yǔ)句的翻譯說(shuō)明：1）

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

審查是否出現(xiàn)在符號(hào)表是：返回指向該登錄項(xiàng)的指針?lè)瘢悍祷豱il3）emit

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

生成一臨時(shí)變量5）E.place

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

id:=E

E

E1+

E2

E

E1*

E2

E

-E1

E

(E1)

E

id

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

id:=E

{ P:=lookup();

ifP

nilthen

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

else

error();

}第32頁(yè),共50頁(yè)，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頁(yè),共50頁(yè)，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頁(yè),共50頁(yè)，2024年2月25日，星期天布爾表達(dá)式的翻譯1、布爾表達(dá)式的作用：計(jì)算邏輯值（返回真/假）控制流語(yǔ)句中的條件表達(dá)式

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

E

EandE E

EorE E

notE E

idropid E

true E

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

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

把AandB解釋成 ifAthenBelsefalse

把

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

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

(1)(not,c,-,t1) (2)(and,b,t1,t2) (3)(or,a,t2,t3)布爾表達(dá)式的翻譯第37頁(yè),共50頁(yè)，2024年2月25日，星期天關(guān)于布爾表達(dá)式的數(shù)值表示法的翻譯模式過(guò)程emit將三地址代碼送到輸出文件中nextstat給出輸出序列中下一條三地址語(yǔ)句的地址索引每產(chǎn)生一條三地址語(yǔ)句后，過(guò)程emit便把nextstat加1第38頁(yè),共50頁(yè)，2024年2月25日，星期天關(guān)于布爾表達(dá)式的數(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頁(yè),共50頁(yè)，2024年2月25日，星期天關(guān)于布爾表達(dá)式的數(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頁(yè),共50頁(yè)，2024年2月25日，星期天布爾表達(dá)式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頁(yè),共50頁(yè)，2024年2月25日，星期天控制語(yǔ)句S

ifEthenS1

elseS2

E.falseE的代碼

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

ifa>cgotoL2“真”出口

gotoL1L1: ifb<dgotoL2“真”出口

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

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

E→E1andE