語(yǔ)法制導(dǎo)翻譯中間代碼生成

語(yǔ)法制導(dǎo)翻譯中間代碼生成第1頁(yè)，共126頁(yè)，2023年，2月20日，星期二概述語(yǔ)義處理程序設(shè)計(jì)語(yǔ)言的語(yǔ)義

靜態(tài)語(yǔ)義是對(duì)程序約束的描述，這些約束無(wú)法通過(guò)抽象語(yǔ)法規(guī)則來(lái)妥善地描述，實(shí)質(zhì)上就是語(yǔ)法規(guī)則的良形式條件，它可以分為類型規(guī)則和作用域/可見(jiàn)性規(guī)則兩大類類型相容性變量先聲明后引用名稱相關(guān)要求

動(dòng)態(tài)語(yǔ)義

程序單位描述的計(jì)算編譯程序的語(yǔ)義處理工作靜態(tài)語(yǔ)義審查解釋執(zhí)行動(dòng)態(tài)語(yǔ)義（計(jì)算）生成代碼...語(yǔ)

法

分

析

后

的

源

程

序

T

語(yǔ)義處理第2頁(yè)，共126頁(yè)，2023年，2月20日，星期二概述語(yǔ)義形式化語(yǔ)義建模文法模型----屬性文法命令式或操作式模型-----操作語(yǔ)義學(xué)應(yīng)用式模型-----指稱語(yǔ)義學(xué)公理式模型-----公理語(yǔ)義學(xué)第3頁(yè)，共126頁(yè)，2023年，2月20日，星期二屬性文法

表達(dá)式文法E—>T+T|TorT

T—>n|bET1+T2

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

T1orT2

{T1.type=bool T2.type=T1.typeE.type:=bool}Tn{T.type:=int}Tb{T.type:=bool}第4頁(yè)，共126頁(yè)，2023年，2月20日，星期二

操作語(yǔ)義描述一段程序的含義是通過(guò)執(zhí)行該段程序所改變的計(jì)算機(jī)（虛擬計(jì)算機(jī)）狀態(tài)來(lái)反映。這個(gè)計(jì)算機(jī)的狀態(tài)與程序執(zhí)行時(shí)的狀態(tài)相對(duì)應(yīng)：包括變量的所有值，可執(zhí)行程序本身，各種系統(tǒng)定義的內(nèi)部數(shù)據(jù)結(jié)構(gòu)。計(jì)算機(jī)里所有的寄存器的值和存儲(chǔ)單元的值作為計(jì)算機(jī)的狀態(tài)，用一組形式定義的操作來(lái)說(shuō)明執(zhí)行一條指令相應(yīng)的狀態(tài)怎樣變化。For(expr1;expr2;expr3){expr1;

...Loop:ifexpr2=0gotoout}…

expr3;

gotoloopout:...第5頁(yè)，共126頁(yè)，2023年，2月20日，星期二公理語(yǔ)義一個(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為真。

第6頁(yè)，共126頁(yè)，2023年，2月20日，星期二

演繹規(guī)則的例子規(guī)則前驅(qū)后繼賦值：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}ifBthenS1

elseS2{Q}第7頁(yè)，共126頁(yè)，2023年，2月20日，星期二指稱語(yǔ)義指稱語(yǔ)義的基本概念是給每一段程序?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ǔ)義結(jié)構(gòu)平行于語(yǔ)法結(jié)構(gòu)。語(yǔ)義函數(shù)：程序設(shè)計(jì)語(yǔ)言的語(yǔ)義利用映射函數(shù)來(lái)證 明。語(yǔ)義函數(shù)將短語(yǔ)映射到它的指稱。第8頁(yè)，共126頁(yè)，2023年，2月20日，星期二

例：二進(jìn)制數(shù)語(yǔ)言110或10101語(yǔ)法實(shí)體指稱（自然數(shù)）6或21語(yǔ)義實(shí)體二進(jìn)制數(shù)文法Numeral::=0

::=1

::=Numeral0

::=Numeral1

自然數(shù)Natrual={0,1,2,3,…}

語(yǔ)義函數(shù)Valuation:NumeralNatural第9頁(yè)，共126頁(yè)，2023年，2月20日，星期二Valuation[101]表示把Valuation施用于101Valuation[N]------把它施用于N

定義:Valuation（用四個(gè)方程)因?yàn)橛兴膫€(gè)形式numeralValuation[0]0Valuation[1]1Valuation[N0]2Valuation[N]Valuation[N1]2Valuation[N]+1

所以：Valuation[110]=2Valuation[11]=2(2Valuation[1]+1)=2(21+1)=6第10頁(yè)，共126頁(yè)，2023年，2月20日，星期二屬性文法和語(yǔ)法制導(dǎo)翻譯雖然形式語(yǔ)義學(xué)(如指稱語(yǔ)義學(xué)、公理語(yǔ)義學(xué)、操作語(yǔ)義學(xué)等)的研究已取得了許多重大的進(jìn)展，但目前在實(shí)際應(yīng)用中比較流行的語(yǔ)義描述和語(yǔ)義處理的方法主要還是屬性文法和語(yǔ)法制導(dǎo)翻譯方法第11頁(yè)，共126頁(yè)，2023年，2月20日，星期二屬性文法屬性文法(attributegrammar)是一個(gè)三元組:A=(G,V,F),其中G:是一個(gè)上下文無(wú)關(guān)文法V:有窮的屬性集,每個(gè)屬性與文法的一個(gè)終結(jié)符或非終結(jié)符相連,這些屬性代表與文法符號(hào)相關(guān)信息，如它的類型、值、代碼序列、符號(hào)表內(nèi)容等等.屬性與變量一樣，可以進(jìn)行計(jì)算和傳遞。屬性加工的過(guò)程即是語(yǔ)義處理的過(guò)程。F:關(guān)于屬性的屬性斷言或一組屬性的計(jì)算規(guī)則(稱為語(yǔ)義規(guī)則).斷言或語(yǔ)義規(guī)則與一個(gè)產(chǎn)生式相聯(lián),只引用該產(chǎn)生式左端或右端的終結(jié)符或非終結(jié)符相聯(lián)的屬性.

第12頁(yè)，共126頁(yè)，2023年，2月20日，星期二屬性有兩種繼承的和綜合的屬性屬性通常分為兩類：綜合屬性和繼承屬性。簡(jiǎn)單地說(shuō)，綜合屬性用于“自下而上”傳遞信息，而繼承屬性用于“自上而下”傳遞信息。出現(xiàn)在產(chǎn)生式左邊的繼承屬性和出現(xiàn)在產(chǎn)生式右邊的綜合屬性不由所給定的產(chǎn)生式的屬性計(jì)算規(guī)則進(jìn)行計(jì)算，它們由其它產(chǎn)生式的屬性規(guī)則計(jì)算或者由生計(jì)算器的參數(shù)提供。

AX1X2…XnA的綜合屬性,計(jì)算S(A):=f(I(X1),…,I(Xn))Xj的繼承屬性,計(jì)算T(Xj):=f(I(A),...I(Xn))1)非終結(jié)符既可有綜合屬性也可有繼承屬性，但文法開(kāi)始符號(hào)沒(méi)有繼承屬性.2)終結(jié)符只有綜合屬性.第13頁(yè)，共126頁(yè)，2023年，2月20日，星期二在一個(gè)屬性文法中，對(duì)應(yīng)于每個(gè)產(chǎn)生式A都有一套與之相關(guān)聯(lián)的語(yǔ)義規(guī)則，每條規(guī)則的形式為b:=f(c1,c2…ck)這里，f是一個(gè)函數(shù)，而且或者 （1）b是A的一個(gè)綜合屬性并且c1,c2…ck是產(chǎn)生式右邊文法符號(hào)的屬性;或者 （2）b是產(chǎn)生式右邊某個(gè)文法符號(hào)的一個(gè)繼承屬性并且c1,c2…ck是A或產(chǎn)生式右邊任何文法符號(hào)的屬性。在兩種情況下，我們都說(shuō)屬性b依賴于屬性c1,c2…ck

。第14頁(yè)，共126頁(yè)，2023年，2月20日，星期二

一個(gè)屬性文法的例子例8.1

非終結(jié)符E、T及F都有一個(gè)綜合屬性val,符號(hào)digit有一個(gè)綜合屬性，它的值由詞法分析器提供。與產(chǎn)生式L→En對(duì)應(yīng)的語(yǔ)義規(guī)則僅僅是打印由E產(chǎn)生的算術(shù)表達(dá)式的值的一個(gè)過(guò)程，我們可認(rèn)為這條規(guī)則定義了L的一個(gè)虛屬性。某些非終結(jié)符加下標(biāo)是為了區(qū)分一個(gè)產(chǎn)生式中同一非終結(jié)符多次出現(xiàn)語(yǔ)義規(guī)則

LEEE1+TETTT1*FTFF(E)FdigitPrint(E.val)

E.val:=E1.val+T.val

E.val:=T.val

T.val:=T1.valF.val

T.val:=F.valF.val:=E.valF.val:=digit.lexval產(chǎn)生式第15頁(yè)，共126頁(yè)，2023年，2月20日，星期二設(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ù)第16頁(yè)，共126頁(yè)，2023年，2月20日，星期二繼承屬性一個(gè)結(jié)點(diǎn)的繼承屬性值是由此結(jié)點(diǎn)的父結(jié)點(diǎn)和/或兄弟結(jié)點(diǎn)的某些屬性來(lái)決定的。例8.2繼承屬性L.in生產(chǎn)式語(yǔ)義規(guī)則DTL

Tint

Treal

LL1,idLidL.in:=T.typeT.type=integerT.type:=real

L1.in:=L.in

addtype(id.entry,L.in)

addtype(id.entry,L.in)第17頁(yè)，共126頁(yè)，2023年，2月20日，星期二

DL.in=realL.in=realL.in=realT.type=realrealid2id1id3.Realid1,id2,id3，，第18頁(yè)，共126頁(yè)，2023年，2月20日，星期二例8.3P–>DSD–>varV;D|S–>V:=E;S|V–>x|y|z現(xiàn)在使用兩個(gè)屬性，name和dl，每當(dāng)一個(gè)新的變量聲明時(shí)，就把它的name屬性附給它，name屬性是綜合屬性。將所聲明的變量都放到一個(gè)變量名字清單中（用語(yǔ)義函數(shù)addlist實(shí)現(xiàn)），用屬性dl綜合聲明塊中聲明的所有變量。然后這個(gè)dl屬性又作為繼承屬性傳到后面的語(yǔ)句部分，每個(gè)語(yǔ)句用到的變量都要進(jìn)行審查，看它是否在變量名字清單中P–>DS{S.dl=D.dl}D1–>varV;D2|

{D1.dl=addlist(V.name,D2.dl)}|{D1.dl=NULL}S1–>V:=E;S2|

{check(V.name,S1.dl);S2.dl=S1.dl}V–>x|y|z{V.name='x'}|{V.name='y'}|{V.name='z'}第19頁(yè)，共126頁(yè)，2023年，2月20日，星期二varx；vary；x:=e；

PDdl={x,y}S

dl={x,y}varV；Ddl={y}V:=e；S

xvarV；Ddl={}y

y

第20頁(yè)，共126頁(yè)，2023年，2月20日，星期二語(yǔ)法制導(dǎo)的翻譯一個(gè)翻譯是符號(hào)串對(duì)的一個(gè)集合。在一個(gè)編譯程序定義的翻譯中，符號(hào)串對(duì)是源程序和目標(biāo)程序。各個(gè)編譯階段定義一個(gè)翻譯，詞法分析：（字符串，單詞串）語(yǔ)法分析：（單詞串，語(yǔ)法樹(shù)）代碼生成（語(yǔ)法樹(shù)，匯編語(yǔ)言）設(shè)是輸入字母表且是輸出字母表。定義由語(yǔ)言L1*到語(yǔ)言L2*的一個(gè)翻譯是由*到*的一個(gè)關(guān)系T,使得T的定義域?yàn)長(zhǎng)1且T的值域?yàn)長(zhǎng)2。使(x,y)∈T的句子y叫做x的一個(gè)輸出.第21頁(yè)，共126頁(yè)，2023年，2月20日，星期二語(yǔ)法制導(dǎo)的翻譯直觀地說(shuō)，一個(gè)語(yǔ)法制導(dǎo)翻譯的基礎(chǔ)是一個(gè)文法，其中翻譯成分依附在每一產(chǎn)生式上。例8.4：下列翻譯模式，它定義翻譯，即對(duì)每個(gè)輸入x，其輸出y是x的逆轉(zhuǎn)。定義此翻譯的規(guī)則是產(chǎn)生式

翻譯規(guī)則(1)s0s(2)s1s(3)sε

(1)s=s0(2)s=s1

(3)s=ε

第22頁(yè)，共126頁(yè)，2023年，2月20日，星期二

輸入輸出對(duì)可由(,)表示，其中是輸入句子形式而是輸出句子形式。(S,S)開(kāi)始用產(chǎn)生式s0s來(lái)擴(kuò)展得到(0S,S0).再用一次規(guī)則(1)，得到(00S,S00)。再用規(guī)則(2)，就得到(001S,S100).然后應(yīng)用規(guī)則(3)并得到(001,100)。第23頁(yè)，共126頁(yè)，2023年，2月20日，星期二

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

EE+TET

TTFTF

F(E)

Fa

E=ET+

E=T

T=TF

T=F

F=E

F=a產(chǎn)生式

翻譯規(guī)則第24頁(yè)，共126頁(yè)，2023年，2月20日，星期二

確定輸入a+aa的輸出：

(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+)第25頁(yè)，共126頁(yè)，2023年，2月20日，星期二

定義：一個(gè)語(yǔ)法制導(dǎo)的翻譯模式是一個(gè)五元組T=(N,,，R,S),其中

(1)N是非終結(jié)符的有限集。

(2)是有限的輸入字母表。

(3)是有限的輸出字母表。

(4)R是形如A,的規(guī)則的有限集,其中∈(N∪)*,∈(N∪)*且中那組非終結(jié)符是中那組非終結(jié)符的置換。

(5)S是N中一個(gè)特別的非終結(jié)符，即開(kāi)始符。第26頁(yè)，共126頁(yè)，2023年，2月20日，星期二

定義：若T=(N,,,R,S)是SDTS,(T)則稱為語(yǔ)法制導(dǎo)的翻譯(SDT)，文法Gi=(N,,P,S)，其中P={A|A,屬于R)，稱為SDTST的基礎(chǔ)（或輸入）文法。文法G0=(N,,P,S),，其中P={A|A,屬于R}，稱為T的輸出文法。把語(yǔ)法制導(dǎo)的翻譯方法看成是將輸入文法Gi中的推導(dǎo)樹(shù)變換成輸出文法G0中的推導(dǎo)樹(shù)。給了輸入句子x，可以按如下方式得到x的一個(gè)翻譯：先為推導(dǎo)x構(gòu)造一棵推導(dǎo)樹(shù)，再變換該樹(shù)到輸出文法中的一棵樹(shù)，然后取此輸出樹(shù)的邊緣作為x的一個(gè)翻譯。第27頁(yè)，共126頁(yè)，2023年，2月20日，星期二語(yǔ)義制導(dǎo)翻譯中的規(guī)則A,

對(duì)應(yīng)于每一個(gè)文法產(chǎn)生式A

都有與之相關(guān)聯(lián)的一套語(yǔ)義描述屬性文法(attributegrammar)是一個(gè)三元組:A=(G,V,F)屬性文法可以看作是關(guān)于語(yǔ)言翻譯的高級(jí)規(guī)范說(shuō)明，其中隱去實(shí)現(xiàn)細(xì)節(jié)，使用戶從明確說(shuō)明翻譯順序的工作中解脫出來(lái)第28頁(yè)，共126頁(yè)，2023年，2月20日，星期二語(yǔ)法制導(dǎo)翻譯實(shí)現(xiàn)從概念上講，語(yǔ)法制導(dǎo)翻譯即基于屬性文法的處理過(guò)程通常是這樣的：對(duì)單詞符號(hào)串進(jìn)行語(yǔ)法分析，構(gòu)造語(yǔ)法分析樹(shù)，然后根據(jù)需要遍歷語(yǔ)法樹(shù)并在語(yǔ)法樹(shù)的各結(jié)點(diǎn)處按語(yǔ)義規(guī)則進(jìn)行計(jì)算輸入符號(hào)串

分析樹(shù)

屬性依賴圖

語(yǔ)義規(guī)則的計(jì)算順序

第29頁(yè)，共126頁(yè)，2023年，2月20日，星期二依賴圖由稱為依賴圖的一個(gè)有向圖描述分析樹(shù)中的繼承屬性和屬性中間的相互依賴關(guān)系。

依賴圖的構(gòu)造算法：

for分析樹(shù)中每一個(gè)結(jié)點(diǎn)ndo

for

結(jié)點(diǎn)的文法符號(hào)的每一個(gè)屬性ado

為a在依賴圖中建立一個(gè)結(jié)點(diǎn)；

for

分析樹(shù)中每一個(gè)結(jié)點(diǎn)ndo

for結(jié)點(diǎn)n所用產(chǎn)生式對(duì)應(yīng)的每一個(gè)語(yǔ)義規(guī)則

b:=f(c1,c2,…ck)do

fori:=1tokdo

從ci結(jié)點(diǎn)到b結(jié)點(diǎn)構(gòu)造一條有向邊

第30頁(yè)，共126頁(yè)，2023年，2月20日，星期二依賴圖----例8.2例8.2繼承屬性L.in生產(chǎn)式語(yǔ)義規(guī)則DTL

Tint

Treal

LL1,idLidL.in:=T.typeT.type=integerT.type:=real

L1.in:=L.in

addtype(id.entry,L.in)

addtype(id.entry,L.in)第31頁(yè)，共126頁(yè)，2023年，2月20日，星期二例8.2Realid1,id2,id3分析樹(shù)的依賴圖

5678910T4DLLLRealtypeininin3entry2entryentryid3id2id1..1第32頁(yè)，共126頁(yè)，2023年，2月20日，星期二依賴圖中的結(jié)點(diǎn)由數(shù)字來(lái)標(biāo)識(shí)。從代表T.type的結(jié)點(diǎn)4有一條有向邊連到代表L.in的結(jié)點(diǎn)5，因?yàn)楦鶕?jù)產(chǎn)生式E→TL的語(yǔ)義規(guī)則L1.in=L.in，可知L1.in依賴于L.in，所以有兩條向下的有向邊分別進(jìn)入結(jié)點(diǎn)7和9。每一個(gè)與L產(chǎn)生式有關(guān)的語(yǔ)義規(guī)則addtype(id.Entry,L.in)都產(chǎn)生一個(gè)虛屬性，結(jié)點(diǎn)6、8和10都是為這些虛屬性構(gòu)造的。第33頁(yè)，共126頁(yè)，2023年，2月20日，星期二良定義的屬性文法。

很顯然，一條求值規(guī)則只有在其各變?cè)稻亚蟮玫那闆r下才可以使用。但有時(shí)候可能會(huì)出現(xiàn)一個(gè)屬性對(duì)另一個(gè)屬性的循環(huán)依賴關(guān)系。從事貿(mào)易如，p、c1、c2都是屬性，若有下求值規(guī)則：p:=f1(c1)、c1:=f2(c2)、c2:=f3(p)時(shí)，就無(wú)法對(duì)p求值。如果一屬性文法不存在屬性之間的循環(huán)依賴關(guān)系，那么稱該文法為良定義的。為了設(shè)計(jì)編譯程序，我們只處理良定義的屬性文法。第34頁(yè)，共126頁(yè)，2023年，2月20日，星期二屬性的計(jì)算順序一個(gè)有向非循環(huán)圖的拓?fù)湫蚴菆D中結(jié)點(diǎn)的任何順序m1,m2,…,mk，使得邊必須是從序列中前面的結(jié)點(diǎn)指向后面的結(jié)點(diǎn)。也就是說(shuō)，如果mi→mj是mi到mj的一條邊，那么在序列中mi必須出現(xiàn)在mj之前。一個(gè)依賴圖的任何拓?fù)渑判蚨冀o出一個(gè)分析樹(shù)中結(jié)點(diǎn)的語(yǔ)義規(guī)則計(jì)算的有效順序。這就是說(shuō)，在拓?fù)渑判蛑?，在一個(gè)結(jié)點(diǎn)，語(yǔ)義規(guī)則b:=f(c1,c2,…ck)中的屬性c1,c2,…ck在計(jì)算b以前都是可用的。第35頁(yè)，共126頁(yè)，2023年，2月20日，星期二屬性文法說(shuō)明的翻譯是很精確的。最基本的文法用于建立輸入符號(hào)串的分析樹(shù)。依賴圖如上面討論的那樣建立。從依賴圖的拓?fù)渑判蛑?，我們可以得到?jì)算語(yǔ)義規(guī)則的順序。用這個(gè)順序來(lái)計(jì)算語(yǔ)義規(guī)則就得到輸入符號(hào)串的翻譯。例8.2Realid1,id2,id3分析樹(shù)的依賴圖每一條邊都是從序號(hào)較低的結(jié)點(diǎn)指向序號(hào)較高的結(jié)點(diǎn)。歷此，依賴圖的一個(gè)拓?fù)渑判蚩梢詮牡托蛱?hào)到高序號(hào)順序?qū)懗觥倪@個(gè)拓?fù)渑判蛑形覀兛梢缘玫较铝谐绦?，用an來(lái)代表依賴圖中與序號(hào)n的結(jié)點(diǎn)有關(guān)的屬性： a4:=real a5:=a4

addtype(id3,entry,a5); a7:=a5; addtype(id2,entry,a7) a9:=a7

addtype(id1,entry,a9)這些語(yǔ)義規(guī)則的計(jì)算將把real類型填入到每個(gè)標(biāo)識(shí)符對(duì)應(yīng)的符號(hào)表項(xiàng)中。第36頁(yè)，共126頁(yè)，2023年，2月20日，星期二

屬性計(jì)算方法樹(shù)遍歷的屬性計(jì)算方法

設(shè)語(yǔ)法樹(shù)已經(jīng)建立起了，并且樹(shù)中已帶有開(kāi)始符號(hào)的繼承屬性和終結(jié)符的綜合屬性。然后以某種次序遍歷語(yǔ)法樹(shù)，直至計(jì)算出所有屬性。最常用的遍歷方法是深度優(yōu)先，從左到右的遍歷方法。如果需要的話，可使用多次遍歷（或稱遍）。一遍掃描的處理方法與樹(shù)遍歷的屬性計(jì)算文法不同，一遍掃描的處理方法是在語(yǔ)法分析的同時(shí)計(jì)算屬性值，而不是語(yǔ)法分析構(gòu)造語(yǔ)法樹(shù)之后進(jìn)行屬性的計(jì)算，而且無(wú)無(wú)需構(gòu)造實(shí)際的語(yǔ)法樹(shù)。因?yàn)橐槐閽呙璧奶幚矸椒ㄅc語(yǔ)法分析器的相互作用，它與下面兩個(gè)因素密切相關(guān)：（1）所采用的語(yǔ)法分析方法（2）屬性的計(jì)算次序。第37頁(yè)，共126頁(yè)，2023年，2月20日，星期二例：定義定點(diǎn)二進(jìn)制數(shù)的CFG:(1)NS?S(2)SSB(3)SB(4)B0(5)B1

第38頁(yè)，共126頁(yè)，2023年，2月20日，星期二非終結(jié)符N表示整個(gè)二進(jìn)制數(shù)的數(shù)值，綜合屬性v附加在N上：Nv非終結(jié)符B表示一個(gè)二進(jìn)制數(shù)字，它有自己的值v，但該值分配給N的值與它的位置有關(guān)，是與2成比例，比例因子f是從S繼承的屬性,所以：Bvf非終結(jié)符S表示一個(gè)二進(jìn)制數(shù)字串，它也有值，但該值與串的位置有關(guān)，與f有關(guān)與串的長(zhǎng)度l有關(guān):Sfvl第39頁(yè)，共126頁(yè)，2023年，2月20日，星期二構(gòu)造數(shù)值的屬性斷言可以如下:

Nv——>Sf1v1l1?Sf2v2l2[v=v1+v2;f1=1;f2=2-l2]Sfvl——>Sf1v1l1Bf2v2[f1=2f;f2=f;v=v1+v2;l=l1+1]——>Bfv[l=1]Bfv——>0[v=0]——>1[v=f]第40頁(yè)，共126頁(yè)，2023年，2月20日，星期二

NvSi1l1“?”Si2l2[v=i1+2-l2?i2]

SilSi1l1Bi2[i

=2i1+i2;;l=l1+1]

Bi[l=1]

Bi“0”[i=0]

“1”[i=1]第41頁(yè)，共126頁(yè)，2023年，2月20日，星期二

在某些情況下可用一遍掃描實(shí)現(xiàn)屬性文法的語(yǔ)義規(guī)則計(jì)算。也就是說(shuō)在語(yǔ)法分析的同時(shí)完成語(yǔ)義規(guī)則的計(jì)算，無(wú)須明顯地構(gòu)造語(yǔ)法樹(shù)或構(gòu)造屬性之間的依賴圖。因?yàn)閱伪閷?shí)現(xiàn)對(duì)于編譯效率非常重要具體的實(shí)現(xiàn)希望在單遍掃描中完成翻譯研究怎樣實(shí)現(xiàn)這種翻譯器。一個(gè)一般的屬性文法的翻譯器可能是很難建立的，然而有一大類屬性文法的翻譯器是很容易建立的s-屬性

適用于自底向上的計(jì)算L-屬性適用于自頂向下的分析，也可用于自底向上。

第42頁(yè)，共126頁(yè)，2023年，2月20日，星期二S－屬性文法的自下而上計(jì)算S－屬性文法，它只含有綜合屬性。綜合屬性可以在分析輸入符號(hào)串的同時(shí)自下而上的分析器來(lái)計(jì)算。分析器可以保存與棧中文法符號(hào)有關(guān)的綜合屬性值，每當(dāng)進(jìn)行歸約時(shí)，新的屬性值就由棧中正在歸約的產(chǎn)生式右邊符號(hào)的屬性值來(lái)計(jì)算。S－屬性文法的翻譯器通常可借助于LR分析器實(shí)現(xiàn)。在S－屬性文法的基礎(chǔ)上，LR分析器可以改造為一個(gè)翻譯器，在對(duì)輸入串進(jìn)行語(yǔ)法分析的同時(shí)對(duì)屬性進(jìn)行計(jì)算。第43頁(yè)，共126頁(yè)，2023年，2月20日，星期二產(chǎn)生式語(yǔ)義規(guī)則０）Ｌ→Ｅｐｒｉｎｔ（Ｅ.ｖａｌ）１）Ｅ→Ｅ1＋ＴＥ.ｖａｌ∶＝Ｅ1.ｖａｌ＋Ｔ.ｖａｌ２）Ｅ→ＴＥ.ｖａｌ∶＝Ｔ.ｖａl３）Ｔ→Ｔ1*ＦＴ.ｖａｌ∶＝Ｔ1.ｖａｌ×Ｆ.ｖａｌ４）Ｔ→FＴ.ｖａｌ∶＝F.ｖａｌ５）Ｆ→（Ｅ）Ｆ.ｖａｌ∶＝Ｅ.ｖａｌ６）Ｆ→ｄiｇiｔＦ.ｖａｌ:＝ｄｉｇｉｔ.ｌｅｘｖａｌLR分析器可以改造為一個(gè)翻譯器，在對(duì)輸入串進(jìn)行語(yǔ)法分析的同時(shí)對(duì)屬性進(jìn)行計(jì)算。

LR分析器增加語(yǔ)義棧

第44頁(yè)，共126頁(yè)，2023年，2月20日，星期二

２＋３*５的分析和計(jì)值過(guò)程步驟動(dòng)作狀態(tài)棧語(yǔ)義棧(值棧)符號(hào)棧余留輸入串１）０－＃２＋3*５＃２）０５－－＃２＋3*５＃３）ｒ６０３－２＃Ｆ＋３*５＃４）ｒ４０２－２＃Ｔ＋３*５＃５）ｒ２０１－２＃Ｅ＋３*５＃６）０１６－２－＃Ｅ＋３*５＃７）０１６５－２－－＃Ｅ＋３*５＃８）ｒ６０１６３－２－３＃Ｅ＋Ｆ*５＃９）ｒ４０１６９－２－３＃Ｅ＋Ｔ*５＃１０）０１６９７－２－３－＃Ｅ＋Ｔ*５＃１１）０１６９７５－２－３－－＃Ｅ＋Ｔ*５＃１２）ｒ６０１６９７（１０）－２－３－５＃Ｅ＋Ｔ*Ｆ#１３）ｒ３０１６９－２－（１５）＃Ｅ＋Ｔ＃１４）ｒ１０１－（１７）＃Ｅ＃１５）接受第45頁(yè)，共126頁(yè)，2023年，2月20日，星期二BOTTOM—UP語(yǔ)義處理是作類型檢查，對(duì)二目運(yùn)算符的運(yùn)算對(duì)象進(jìn)行類型匹配審查。(LR分析）：增加語(yǔ)義棧歸約時(shí)進(jìn)行語(yǔ)義動(dòng)作.例8.7G[E]:(1)ET+T(2)ETorT(3)Tn(4)Tb

第46頁(yè)，共126頁(yè)，2023年，2月20日，星期二ET1+T2

{ifT1.type=intandT2.type=intthenE.type:=int

elseerror}

E

T1orT2

{ifT1.type=boolandT2.type=boolthenE.type:=bool

elseerror}Tn{T.type:=int}Tb{T.type:=bool}

第47頁(yè)，共126頁(yè)，2023年，2月20日，星期二

G[E]:(1)ET+T(2)ETorT(3)Tn(4)Tb第48頁(yè)，共126頁(yè)，2023年，2月20日，星期二第49頁(yè)，共126頁(yè)，2023年，2月20日，星期二L－屬性文法和自頂向下翻譯一個(gè)屬性文法稱為L(zhǎng)－屬性文法，如果對(duì)于每個(gè)產(chǎn)生式A→X1X2…Xn，其每個(gè)語(yǔ)義規(guī)則中的每個(gè)屬性或者是綜合屬性，或者是Xj（1≤j≤n）的一個(gè)繼承屬性且這個(gè)繼承屬性僅依賴于：（1）產(chǎn)生式Xj在左邊符號(hào)X1，X2，…，Xj-1的屬性；（2）A的繼承屬性。S－屬性文法一定是L－屬性文法，因?yàn)椋?）、（2）限制只用于繼承屬性。L－屬性文法允許一次遍歷就計(jì)算出所有屬性值。LL（1）這種自上而下分析文法的分析過(guò)程，從概念上說(shuō)可以看成是深度優(yōu)先建立語(yǔ)法樹(shù)的過(guò)程，因此，我們可以在自上而下語(yǔ)法分析的同時(shí)實(shí)現(xiàn)L屬性文法的計(jì)算。第50頁(yè)，共126頁(yè)，2023年，2月20日，星期二例（中綴表達(dá)式翻譯成相應(yīng)的后綴表達(dá)式）

E→TR

R→addopT{print(addop.Lexeme)}R1|ε

T→num{print(num.val)}

翻譯模式（Translationschemes）適合語(yǔ)法制導(dǎo)翻譯的另一種描述形式。翻譯模式給出了使用語(yǔ)義規(guī)則進(jìn)行計(jì)算的次序，可把某些實(shí)現(xiàn)細(xì)節(jié)表示出來(lái)。在翻譯模式中，和文法符號(hào)相關(guān)的屬性和語(yǔ)義規(guī)則（這里我們也稱語(yǔ)義動(dòng)作），用花括號(hào)｛｝括起來(lái)，插入到產(chǎn)生式右部的合適位置上。第51頁(yè)，共126頁(yè)，2023年，2月20日，星期二輸入串9－5+2的語(yǔ)法樹(shù)，每個(gè)語(yǔ)義動(dòng)作都作為相應(yīng)產(chǎn)生式左部符號(hào)的結(jié)點(diǎn)的兒子，按深度優(yōu)先次序執(zhí)行圖中的動(dòng)作后，打印輸出95－2+。

ETR9print(‘9’)-Tprint(‘-’)R5print(‘5’)+Tprint(‘+’)R2print(‘2’)ε第52頁(yè)，共126頁(yè)，2023年，2月20日，星期二L－屬性文法在自頂向下分析中的實(shí)現(xiàn)

帶左遞歸的文法的翻譯模式E→E1+T {E.val:=E1.val+T.val}E→E1－T {E.val:=E1.val－T.val}E→T {E.val:=T.val}T→(E) {T.val:=E.val}T→num {T.val:=num.val}

第53頁(yè)，共126頁(yè)，2023年，2月20日，星期二消除左遞歸的同時(shí)考慮屬性，構(gòu)造新的翻譯模式

E→T {R.i:=T.val}R {E.val:=R.s}R→+T {R1.i:=R.i+T.val}R1 {R.s:=R1.s}R→-T {R1.i:=R.i-T.val}R1 {R.s:=R1.s}R→ε {R.s:=R.i}T→(E){T.val:=E.val}T→num {T.val:=num.val}第54頁(yè)，共126頁(yè)，2023年，2月20日，星期二計(jì)算表達(dá)式9-5+2.ER.i=9T.val=5T.val=9R.i=4

R.i=6T.val=2num.val=9num.val=5num.val=2_+第55頁(yè)，共126頁(yè)，2023年，2月20日，星期二在上頁(yè)的翻譯模式中，每個(gè)數(shù)都是由T產(chǎn)生的，并且T.val的值就是由屬性num.val給出的數(shù)的詞法值。子表達(dá)式9－5中的數(shù)字9是由最左邊的T生成的，但是減號(hào)和5是由根的右子結(jié)點(diǎn)R生成的。繼承屬性R.i從T.val得到值9。計(jì)算9－5并把結(jié)果4傳遞到中間的R結(jié)點(diǎn)這是通過(guò)產(chǎn)生式中嵌入的下面動(dòng)作實(shí)現(xiàn)：{R1.i:=R.i－T.val}類似的動(dòng)作把2加到9－5的值上，在最下面的R結(jié)點(diǎn)處產(chǎn)生結(jié)果R.i＝6。這個(gè)結(jié)將成為根結(jié)點(diǎn)處E.val的值,R的綜合屬性s在圖中沒(méi)有表示出來(lái)，它用來(lái)向上復(fù)制這一結(jié)果一直到樹(shù)根。

第56頁(yè)，共126頁(yè)，2023年，2月20日，星期二對(duì)于自頂向下分析，我們假設(shè)動(dòng)作是在處于相同位置上的符號(hào)被展開(kāi)（匹配成功）時(shí)執(zhí)行的。如圖中的第二個(gè)產(chǎn)生式中，第一個(gè)動(dòng)作（對(duì)R1.i賦值）是在T被完全展開(kāi)成終結(jié)符號(hào)后執(zhí)行的，第二個(gè)動(dòng)作是在R1被完全展開(kāi)成終結(jié)符號(hào)后執(zhí)行的。正如前面我們所討論的，一個(gè)符號(hào)的繼承屬性必須由出現(xiàn)在這個(gè)符號(hào)之前的動(dòng)作來(lái)計(jì)算，產(chǎn)生式左邊非終結(jié)符的綜合屬性必須在它所依賴的所有屬性都計(jì)算出來(lái)以后才能計(jì)算。第57頁(yè)，共126頁(yè)，2023年，2月20日，星期二轉(zhuǎn)換左遞歸翻譯模式的方法推廣到一般

假設(shè)翻譯模式1：A→A1Y {A.a:=g(A1。a,Y.y)}A→X {A.a:=f(X.x)} 每個(gè)文法符號(hào)都有一個(gè)綜合屬性，用相應(yīng)的小寫(xiě)字母表示，g和f是任意函數(shù)消除左遞歸，文法轉(zhuǎn)換成：A→XRR→YR｜ε 再考慮語(yǔ)義動(dòng)作，翻譯模式變?yōu)?A→X {R.i:=f(X.x)}R {A.a:=R.s}R→Y {R1.i:=g(R.i,Y.y)} R1 {R.s:=R1.s}R→ε {R.s:=R.i}第58頁(yè)，共126頁(yè)，2023年，2月20日，星期二翻譯模式1和翻譯模式2的結(jié)果是一樣的。可以給出串XY1Y2兩棵帶注釋的語(yǔ)法樹(shù)看出來(lái)，一棵是根據(jù)翻譯模式1自下而上計(jì)算屬性的。一棵是根據(jù)翻譯模式2自上而下計(jì)算的。第59頁(yè)，共126頁(yè)，2023年，2月20日，星期二

A→A1Y {A.a:=g(A1。a,Y.y)}

A→X {A.a:=f(X.x)}

A.a=g(g(f(X.x,Y1.y),Y2.y)A.a=g(f(X.x,Y1.y)Y2A.a=f(X.x)Y1X

AAYAYX第60頁(yè)，共126頁(yè)，2023年，2月20日，星期二

A→X{R.i:=f(X.x)}R→Y {R1.i:=g((R.i),Y.y)}

R{A.a:=R.s}

R1{R.s:=R1.s}

A→XRR→YR｜εAXRY1RY2R

AXR.i=f(X.x)Y1R.i=g(f(X.x,Y1.y)Y2R.i=g(g(f(X.x,Y1.y),Y2.y)

第61頁(yè)，共126頁(yè)，2023年，2月20日，星期二思考問(wèn)題-把建立語(yǔ)法樹(shù)的翻譯模式變換成適合預(yù)測(cè)分析的模式EE1+T{E.nptr:=mknode(‘+’,E1.nptr,T.nptr)EE1-T{E.nptr:=mknode(‘-’,E1.nptr,T.nptr)ET{E.nptr:=T.nptr)第62頁(yè)，共126頁(yè)，2023年，2月20日，星期二自下而上計(jì)算繼承屬性討論在自下而上的分析過(guò)程中實(shí)現(xiàn)L－屬性文法的方法。這種方法可以實(shí)現(xiàn)任何基于LL（1）文法的L－屬性文法，它還可以實(shí)現(xiàn)許多（不是所有）基于LR（1）文法的L－屬性文法。這種方法是S-屬性文法的自下而上翻譯技術(shù)的一般化第63頁(yè)，共126頁(yè)，2023年，2月20日，星期二自下而上分析器對(duì)產(chǎn)生式A→XY的右部是通過(guò)把X和Y從分析棧中移出并用A代替它們。假設(shè)X有一個(gè)綜合屬性X.s，按照前面所介紹的方法我們把它與X一起放在分析棧中。由于X.s的值在Y以下的子樹(shù)中的任何歸約之前已經(jīng)放在棧中，這個(gè)值可以被Y繼承。也就是說(shuō)，如果繼承屬性Y.i是由復(fù)寫(xiě)規(guī)則Y.i:=X.s定義的，則可以在需要y.i值的地方使用X.s的值。在自下而上分析中計(jì)算屬性值時(shí)復(fù)寫(xiě)規(guī)則起非常重要的作用?？聪旅胬印５?4頁(yè)，共126頁(yè)，2023年，2月20日，星期二假設(shè)某翻譯模式為：D→T {L.in:=T.type}LT→int {T.type:=integer}T→real {T.type:=real}L→ {L1.in:=L.in}L1,id {addtype(id.entry,L.in)}L→id {addtype(id.entry,L.in)}第65頁(yè)，共126頁(yè)，2023年，2月20日，星期二回顧例8.2Realid1,id2,id3分析樹(shù)的依賴圖

5678910T4DLLLRealtypeininin3entry2entryentryid3id2id1..1第66頁(yè)，共126頁(yè)，2023年，2月20日，星期二例8.2輸入串realRealid1,id2,id3的分析過(guò)程當(dāng)L的右部被歸約時(shí)，T恰好在這個(gè)右部的下面輸入狀態(tài)(符號(hào)）使用產(chǎn)生式Realid1,id2,id3#id1,id2,id3#realid1,id2,id3#TTreal,id2,id3#Tid1,id2,id3#TLLidid2,id3#TL,,id3#TL,id2,id3#TLLLi,did3#TL,#TL,id3#TLLLi,d#DDTL第67頁(yè)，共126頁(yè)，2023年，2月20日，星期二

用綜合屬性代替繼承屬性有時(shí)，改變基礎(chǔ)文法可能避免繼承屬性。例如，一個(gè)Pascal的說(shuō)明由一標(biāo)識(shí)符序列后跟類型組成，如,m,n:integer。這樣的說(shuō)明的文法可由下面形式的產(chǎn)生式構(gòu)成D→L：TT→integer|charL→L,id|id因?yàn)闃?biāo)識(shí)符由L產(chǎn)生而類型不在L的子樹(shù)中，我們不能僅僅使用綜合屬性就把類型與標(biāo)識(shí)符聯(lián)系起來(lái)。事實(shí)上，如果非終結(jié)符L從第一個(gè)產(chǎn)生式中它的右邊T中繼承了類型，則我們得到的屬性文法就不是L－屬性的，因此，基于這個(gè)屬性文法的翻譯工作不能在語(yǔ)法分析的同時(shí)進(jìn)行。第68頁(yè)，共126頁(yè)，2023年，2月20日，星期二一個(gè)解決的方法是重新構(gòu)造文法使類型作為標(biāo)識(shí)符表的最后一個(gè)元素：D→idLL→,idL|:TT→integer|char這樣，類型可以通過(guò)綜合屬性L.type進(jìn)行傳遞，當(dāng)通過(guò)L產(chǎn)生每個(gè)標(biāo)識(shí)符時(shí)，它的類型就可以填入到符號(hào)表中。

第69頁(yè)，共126頁(yè)，2023年，2月20日，星期二語(yǔ)義制導(dǎo)翻譯的編譯實(shí)現(xiàn):例8.6E–>TE'E'–>ATE'|T–>FT'T'–>MFT'|F–>(E)|intA–>+|-M–>*|/第70頁(yè)，共126頁(yè)，2023年，2月20日，星期二E->TE'E'->ATE'{rhs=PopOperand();lhs=PopOperand();switch(PopOperator()){caseADD:PushOperand(lhs+rhs);break;caseSUB:PushOperand(lhs-rhs);break;}}|

{/*empty,donothing*/}T->FT'T'->MFT'{rhs=PopOperand();lhs=PopOperand();switch(PopOperator()){caseMUL:PushOperand(lhs*rhs);break;caseDIV:PushOperand(lhs/rhs);break;}}|

{/*empty,donothing*/}A->+{PushOperator(ADD);}|-{PushOperator(SUB);}M->*{PushOperator(MUL);}|/{PushOperator(DIV);}F->int{PushOperand(intval);}|(E){/*handledduringparsingofE*/}第71頁(yè)，共126頁(yè)，2023年，2月20日，星期二parse2+4*3:分析動(dòng)作橋分析棧運(yùn)算對(duì)象棧運(yùn)算符棧PredictE–>TE‘E#PredictT–>FT'TE‘#PredictF–>intFT'E‘#MatchintintT'E‘#PredictT'–>T'E‘#2PredictE'–>ATE'ATE'#2PredictA–>+ATE‘#2Match++TE‘#2PredictT–>FT'TE‘#2+PredictF–>intFT'E‘#2+MatchintintT'E‘#2+PredictT'–>MFT'T'E‘#42+PredictM–>*MFT'E‘#42+Match**FT'E‘#42+PredictF–>intFT'E‘#42*+MatchintintT'E‘#42*+PredictT'–>

T'E‘#342*+PredictE'–>

E‘#122+Success!#14第72頁(yè)，共126頁(yè)，2023年，2月20日，星期二Yacc或bison作為編譯程序的生成工具，利用的就是語(yǔ)法制導(dǎo)翻譯方法。它使用符號(hào)$$表示產(chǎn)生式左端的屬性，$n表示存取產(chǎn)生式右端第n個(gè)文法符號(hào)相聯(lián)的屬性如例8.3作為Yacc的輸入，可寫(xiě)成：P→DS{$2.dl=$1.dl}D1→varV；D{$$.dl=addlist($2.name，$4.dl)}|{$$.dl=null}S1→V:=e；S{check($1.name，$$.dl)；

$5.dl=$$.dl}|V→x{$$.name=’x’}|y{$$.name=’y’}|z{$$.name=’z’}第73頁(yè)，共126頁(yè)，2023年，2月20日，星期二如果數(shù)據(jù)結(jié)構(gòu)attribute定義屬性name和dl，可以具體化為：

typestruct_attribute{

char*name；

struct_attribute*list；

}attribute；

P→DS{$2.list=$1.list}D1→varV；D{$$.list=add_to_list($2.name，$4.list)}|{$$.list=null}S1→V:=e；S{check($1.name，$$.list)；

$5.list=$$.list}|V→x{$$.name=’x’}|y{$$.name=’y’}|z{$$.name=’z’}第74頁(yè)，共126頁(yè)，2023年，2月20日，星期二語(yǔ)義分析語(yǔ)義分析屬性文法和語(yǔ)法制導(dǎo)翻譯方法和技術(shù)應(yīng)用于語(yǔ)義分析中。第75頁(yè)，共126頁(yè)，2023年，2月20日，星期二語(yǔ)義分析通常包括：（1）類型檢查。驗(yàn)證程序中執(zhí)行的每個(gè)操作是否遵守語(yǔ)言的類型系統(tǒng)的過(guò)程.，編譯程序必須報(bào)告不符合類型系統(tǒng)的信息。（2）控制流檢查?？刂屏髡Z(yǔ)句必須使控制轉(zhuǎn)移到合法的地方。例如，在C語(yǔ)言中break語(yǔ)句使控制跳離包括該語(yǔ)句的最小while、for或switch語(yǔ)句。如果不存在包括它的這樣的語(yǔ)句，則就報(bào)錯(cuò)。（3）一致性檢查。在很多場(chǎng)合要求對(duì)象只能被定義一次。例如Pascal語(yǔ)言規(guī)定同一標(biāo)識(shí)符在一個(gè)分程序中只能被說(shuō)明一次，同一case語(yǔ)句的標(biāo)號(hào)不能相同，枚舉類型的元素不能重復(fù)出現(xiàn)等等。（4）相關(guān)名字檢查。有時(shí)，同一名字必須出現(xiàn)兩次或多次。例如，Ada語(yǔ)言程序中，循環(huán)或程序塊可以有一個(gè)名字，出現(xiàn)在這些結(jié)構(gòu)的開(kāi)頭和結(jié)尾，編譯程序必須檢查這兩個(gè)地方用的名字是相同的。

(5)名字的作用域分析第76頁(yè)，共126頁(yè)，2023年，2月20日，星期二類型和聲明（Typesanddeclarations）一個(gè)類型是一組值和在這些值上的一組操作，程序設(shè)計(jì)語(yǔ)言中有三種類型:基本類型：int,float,double,char,bool等等.也可能允許在基本類型基礎(chǔ)上用戶自己定義的類型，如枚舉型.復(fù)合類型：數(shù)組,指針，記錄/結(jié)構(gòu)/聯(lián)合,類等等.這些類型由基本類型構(gòu)成.復(fù)雜類型：鏈表，棧，隊(duì)，樹(shù)，堆，表格等等.可以把它們組織成ADT.一個(gè)語(yǔ)言不一定支持這類高級(jí)的抽象。聲明是程序中的一個(gè)語(yǔ)句,是把數(shù)據(jù)對(duì)象的名稱和類型，以及生命周期信息傳給編譯，聲明的地方傳遞生命周期信息也有些語(yǔ)言允許聲明初始化變量。如:doublecalculate(inta,doubleb);//functionprototypeintx=0;//globalvariablesavailablethroughoutdoubley;//theprogramintmain(){intm[3];//localvariablesavailableonlyinmainchar*n;...}第77頁(yè)，共126頁(yè)，2023年，2月20日，星期二強(qiáng)類型的-任何數(shù)據(jù)類型都可以在編譯時(shí)確定弱類型的.進(jìn)行類型檢查的時(shí)間：編譯時(shí)，運(yùn)行時(shí)，或者兩者結(jié)合.靜態(tài)類型檢查編譯時(shí)進(jìn)行類型檢查動(dòng)態(tài)類型檢查，將類型信息并到運(yùn)行時(shí)每個(gè)數(shù)據(jù)單元中.隱含類型轉(zhuǎn)換.第78頁(yè)，共126頁(yè)，2023年，2月20日，星期二P→D；ED→D；|id:TT→char|integer|aray[num]ofT|↑TE→literal|num|id|EmodE|E[E]|E↑P代表程序；D代表說(shuō)明；E代表表達(dá)式。如程序語(yǔ)句：key:integer;keymod1999語(yǔ)言本身提供兩種基本類型：char和integer。除此之外還有缺省的基本類型type_error和void。假定所有數(shù)組都從下標(biāo)1開(kāi)始第79頁(yè)，共126頁(yè)，2023年，2月20日，星期二確定標(biāo)識(shí)符類型的部分翻譯模式（1）P→D；E（2）D→D；D（3）D→id:T{addtype(id.Entry,T.type)}（4）T→char{T.Type:=char}（5）T→integer{T.Type:=integer}（6）T→↑T1{T.Type:=pointer(T1.type)}（7）T→array[num]ofT1

{T.Type:=array(num.Val,T1.type)}第80頁(yè)，共126頁(yè)，2023年，2月20日，星期二

語(yǔ)句的類型檢查的翻譯模式S→id:=E{ifid.Type=E.TypeThenS.Type:=voidelseS.Type:=type_error}S→ifEthenS1{ifE.type=booleanthenS.Type:=S1.typeelseS.type:=type_error}S→whileEdoS1{ifE.type=booleanThenS.type:=S1.TypeelseS.type:=type_error}第81頁(yè)，共126頁(yè)，2023年，2月20日，星期二設(shè)計(jì)類型檢查程序1.辨認(rèn)語(yǔ)言中可用的類型2.辨認(rèn)具有類型的語(yǔ)言結(jié)構(gòu)3.辨認(rèn)語(yǔ)言的語(yǔ)義規(guī)則第82頁(yè)，共126頁(yè)，2023年，2月20日，星期二InDecaf

basetypes：int,double,bool,stringcompoundtypes：arraysandclasses.Anarraycanbemadeofanytype(eitherabasetype,aclass,oroutofotherarrays).Classesareabitspecialinthattheclassnamemustbedeclaredbeforeitcanbeusedinadeclaration.ADTscanbeconstructedusingclasses,buttheyaren’thandledinanywaydifferentlythanclasses,sowedon’tneedtoconsiderthemspecially.第83頁(yè)，共126頁(yè)，2023年，2月20日，星期二InDecaftherelevantlanguageconstructsconstants,everyconstanthasanassociatedtype.Ascannertellsusthesetypesaswellastheassociatedlexeme.variables：allvariables(global,local,andinstance)musthaveadeclaredtypeofeitherint,double,bool,string,array,orclass.functions：functionshaveareturntype,andeachparameterinthefunctiondefinitionhasatype,asdoeseachargumentinafunctioncall.expressionsanexpressioncanbeaconstant,variable,functioncall,orsomeoperator(binaryorunary)appliedtoexpressions.Eachofthevariousexpressionshaveatypebasedonthetypeoftheconstant,variable,returntypeofthefunction,ortypeofoperands.TheotherlanguageconstructsinDecaf(if,while,Print,assignments,etc.)alsohavetypesassociatedwiththem,becausesomewhereineachofthesewefindanexpression.第84頁(yè)，共126頁(yè)，2023年