編譯方法、技術(shù)與實(shí)踐課件：語(yǔ)義分析

語(yǔ)義分析?屬性文法?基于屬性文法的處理方式?S屬性文法和L屬性文法?語(yǔ)法制導(dǎo)的定義?語(yǔ)法制導(dǎo)的翻譯方案?SDT中左遞歸的消除?類型檢查提綱?使用上下文無(wú)關(guān)文法引導(dǎo)語(yǔ)言的翻譯O

CFG的非終結(jié)符號(hào)代表了語(yǔ)言的某個(gè)構(gòu)造O

程序設(shè)計(jì)語(yǔ)言的構(gòu)造由更小的構(gòu)造組合而成O

一個(gè)構(gòu)造的語(yǔ)義可以由小構(gòu)造的含義綜合而來(lái)?比如：表達(dá)式x+y的類型由x、y的類型和運(yùn)算符+決定O

也可以從附近的構(gòu)造繼承而來(lái)?比如：聲明int

x;中x的類型由它左邊的類型表達(dá)式?jīng)Q定引言?假設(shè)我們需要知道一個(gè)表達(dá)式的類型，以及對(duì)應(yīng)代碼將它的值存放在何處，我們就需要兩個(gè)屬性：type，place?產(chǎn)生式規(guī)則：E→E1+T?語(yǔ)義規(guī)則：(假設(shè)只有int/float類型)O

E.type

=if(E1

.type==T.type)T.typeelsefloatOE.place=newTempPlace();//返回一個(gè)新的內(nèi)存位置；?產(chǎn)生式規(guī)則：F→idO

F.type=lookupIDTable(id.lexValue)->type;O

F.place=lookupIDTable(id.lexValue)->address;分析樹(shù)和屬性值(1)E.Type

=

FLOAT

E.Place

=

&aT.Type

=

FLOAT

T.Place

=

&aF.Type

=

FLOATE.Type

=

FLOATE

E.Place

=

&tmp2

T.Type

=

INT

E

+

T

T.Place

=

&tmpT

T

*

F

F.Type

=

INT

F.Place

=

&cF

F

id

id.lexValue=c假設(shè)a,b,c是已經(jīng)聲明

的全局變量，

a的類型

為FLOAT，b,c的類型為

INT中間未標(biāo)明的T和F的

type和address都是INT

和&b;F.Place

=

&a

id.lexValue=a

id

id

id.lexValue=b分析樹(shù)和屬性值(2)?a+b*c的語(yǔ)法分析樹(shù)以及屬性值?綜合屬性(synthesized

attribute)：在分析樹(shù)結(jié)點(diǎn)N上的非終結(jié)符號(hào)A的屬性值由N對(duì)應(yīng)的產(chǎn)生式所關(guān)聯(lián)的

語(yǔ)義規(guī)則來(lái)定義O

通過(guò)N的子結(jié)點(diǎn)或N本身的屬性值來(lái)定義?繼承屬性(inherited

attribute)：結(jié)點(diǎn)N的屬性值由N的父結(jié)點(diǎn)所關(guān)聯(lián)的語(yǔ)義規(guī)則來(lái)定義O

依賴于N的父結(jié)點(diǎn)、N本身和N的兄弟結(jié)點(diǎn)上的屬性值?不允許N的繼承屬性通過(guò)N的子結(jié)點(diǎn)上的屬性來(lái)定義，

但是允許N的綜合屬性依賴于N本身的繼承屬性?終結(jié)符號(hào)有綜合屬性(由詞法分析獲得)，但是沒(méi)有繼承屬性繼承屬性和綜合屬性?綜合屬性(synthesized

attribute)：在分析樹(shù)節(jié)點(diǎn)N上的非終結(jié)符號(hào)A的綜合屬性是由N上的產(chǎn)生式所關(guān)聯(lián)的語(yǔ)義規(guī)則來(lái)定義的。

注意：這個(gè)產(chǎn)生式的頭一定是A。節(jié)點(diǎn)N上

的綜合屬性只能通過(guò)N的子節(jié)點(diǎn)或N本身的

屬性值來(lái)定義?！窘K結(jié)符可以有綜合屬性，為詞法分析器提供的詞法值】O

通過(guò)N的子結(jié)點(diǎn)或N本身的屬性值來(lái)定義繼承屬性和綜合屬性?屬性文法沒(méi)有副作用，但增加了描述的復(fù)雜度O

比如語(yǔ)法分析時(shí)如果沒(méi)有副作用，標(biāo)識(shí)符表就必須作為屬性傳遞O

可以把標(biāo)識(shí)符表作為全局變量，然后通過(guò)副作用函數(shù)來(lái)添加新標(biāo)識(shí)符?受控的副作用O

不會(huì)對(duì)屬性求值產(chǎn)生約束，即可以按照任何拓?fù)漤樞蚯笾担粫?huì)影響最終結(jié)果O

或者對(duì)求值過(guò)程添加簡(jiǎn)單的約束具有受控副作用的語(yǔ)義規(guī)則?L

t

E

n

print(E.val)O

通過(guò)副作用打印出E的值O

總是在最后執(zhí)行，而且不會(huì)影響其它屬性的求值?變量聲明的副作用O

addType將標(biāo)識(shí)符的類型信息加入到標(biāo)識(shí)符表中O

只要標(biāo)識(shí)符不被重復(fù)聲明，標(biāo)識(shí)符的類型信息總是正確的受控副作用的例子?屬性文法?基于屬性文法的處理方式?S屬性文法和L屬性文法?語(yǔ)法制導(dǎo)的定義?語(yǔ)法制導(dǎo)的翻譯方案?SDT中左遞歸的消除?類型檢查提綱?描述了某棵特定的分析樹(shù)上各個(gè)屬性實(shí)例之間的信息流(計(jì)算順序)O

從實(shí)例a1到實(shí)例a2的有向邊表示計(jì)算a2時(shí)需要a1的值(必須先計(jì)算a2，再計(jì)算a1

)?對(duì)于標(biāo)號(hào)為X的分析樹(shù)結(jié)點(diǎn)N，和X關(guān)聯(lián)的每個(gè)屬性a都對(duì)應(yīng)依賴圖的一個(gè)結(jié)點(diǎn)N.a?結(jié)點(diǎn)N對(duì)應(yīng)的產(chǎn)生式的語(yǔ)義規(guī)則通過(guò)X.c計(jì)算了A.b的值，且在分析樹(shù)中X和A分別對(duì)應(yīng)于N1和N2，那么

從N1.c到N2.b有一條邊依賴圖–邊e1、e2?可能的計(jì)算順序：–1,2,3,4,5,6,7,8.9–1,3,5,2,4,6,7,8,9?3*2的注釋分析樹(shù)；?T→FT’{T.val=T’.syn;T’.inh=F.val;}依賴圖的例子?屬性文法?基于屬性文法的處理方式?S屬性文法和L屬性文法?語(yǔ)法制導(dǎo)的定義?語(yǔ)法制導(dǎo)的翻譯方案?SDT中左遞歸的消除?類型檢查提綱?只包含綜合屬性的文法稱為S屬性文法O

每個(gè)語(yǔ)義規(guī)則都根據(jù)產(chǎn)生式體中的屬性值來(lái)計(jì)算頭部非終結(jié)符號(hào)的屬性值?S屬性文法可以和LR語(yǔ)法分析器一起實(shí)現(xiàn)O

棧中的狀態(tài)可以附加相應(yīng)的屬性值O

在進(jìn)行歸約時(shí)，按照語(yǔ)義規(guī)則計(jì)算歸約得到的符號(hào)的屬性值?語(yǔ)義規(guī)則不應(yīng)該有復(fù)雜的副作用O

要求副作用不影響其它屬性的求值S屬性文法?每個(gè)屬性O(shè)

要么是綜合屬性O(shè)

要么是繼承屬性，且產(chǎn)生式A

t

X1X2

…Xn

中計(jì)

算Xi.a的規(guī)則只能使用?A的繼承屬性?

Xi左邊的文法符號(hào)Xj的繼承屬性或綜合屬性?Xi

自身的繼承或綜合屬性，且這些屬性之間的依賴關(guān)系不形成環(huán)L屬性文法?對(duì)于輸入3*5+4n?n表示結(jié)束注釋語(yǔ)法分析樹(shù)的例子?左遞歸文法無(wú)法直接用自頂向下方法處理適用于自頂向下分析O

計(jì)算3*5所用注釋語(yǔ)法樹(shù)?

消除左遞歸之后，我們無(wú)法直接使用屬性val進(jìn)行處理O

比如規(guī)則：T

t

FT’T’t

*FT’O

T對(duì)應(yīng)的項(xiàng)中，第一個(gè)因子對(duì)應(yīng)于F，而運(yùn)算符卻在T’中O

需要繼承屬性來(lái)完成這樣的計(jì)算適用于自頂向下分析?注意：T’的屬性inh實(shí)際上繼承了相應(yīng)的*號(hào)的左運(yùn)算分量。適用于自頂向下分析3*5的注釋分析樹(shù)注意觀察inh屬性是如何傳遞的?屬性文法?基于屬性文法的處理方式?S屬性文法和L屬性文法?語(yǔ)法制導(dǎo)的定義?語(yǔ)法制導(dǎo)的翻譯方案?SDT中左遞歸的消除?類型檢查提綱?語(yǔ)法制導(dǎo)定義O

將文法符號(hào)和某些屬性相關(guān)聯(lián)O

并通過(guò)語(yǔ)義規(guī)則來(lái)描述如何計(jì)算屬性的值O

E

→E1+T

E.code=E1.code||T.code

||

‘+’?屬性code代表中綴表達(dá)式的逆波蘭表示(后綴表示

法?)，規(guī)則說(shuō)明加法表達(dá)式的逆波蘭表示由兩個(gè)

分量的逆波蘭表示并置，然后加上‘+’得到語(yǔ)法制導(dǎo)定義和語(yǔ)法制導(dǎo)翻譯?逆波蘭表達(dá)式，英文為ReversePolishnotation，跟波蘭表達(dá)式(Polish

notation)

相對(duì)應(yīng)?波蘭的數(shù)理科學(xué)家Jan?ukasiewicz

發(fā)明O

中綴表達(dá)式:(1+2)*(3+4)加減乘除等運(yùn)算符寫在中間O

波蘭表達(dá)式:(*(+12)(+34))，將運(yùn)算符寫在前面，因而也稱為前綴表達(dá)式。O

逆波蘭表達(dá)式:((12+)(34+)*)，將運(yùn)算符寫在后面，因而也稱為后綴表達(dá)式語(yǔ)法制導(dǎo)定義和語(yǔ)法制導(dǎo)翻譯?語(yǔ)法制導(dǎo)定義O

將文法符號(hào)和某些屬性相關(guān)聯(lián)O

并通過(guò)語(yǔ)義規(guī)則來(lái)描述如何計(jì)算屬性的值O

E

→E1+T

E.code=E1.code||T.code

||

‘+’?屬性code代表中綴表達(dá)式的逆波蘭表示(后綴表示法)，

規(guī)則說(shuō)明加法表達(dá)式的逆波蘭表示由兩個(gè)分量的逆波

蘭表示并置，然后加上‘+’得到?語(yǔ)法制導(dǎo)翻譯O

在產(chǎn)生式體中加入語(yǔ)義動(dòng)作，

并在適當(dāng)?shù)臅r(shí)候執(zhí)

行這些語(yǔ)義動(dòng)作O

E

→

E1+T

{print

‘+’;}語(yǔ)法制導(dǎo)定義和語(yǔ)法制導(dǎo)翻譯?SDD是對(duì)上下文無(wú)關(guān)文法的推廣O

將每個(gè)文法符號(hào)和一個(gè)語(yǔ)義屬性集合相關(guān)聯(lián)O

將每個(gè)產(chǎn)生式和一組語(yǔ)義規(guī)則相關(guān)聯(lián)，這些規(guī)則用于計(jì)算該產(chǎn)

生式中各文法符號(hào)的屬性值語(yǔ)法制導(dǎo)的定義(SDD)?SDD是上下文無(wú)關(guān)文法和屬性/規(guī)則的結(jié)合O

屬性和文法符號(hào)相關(guān)聯(lián)，按照需要來(lái)確定各個(gè)文法符號(hào)需要哪些屬性O(shè)

規(guī)則和產(chǎn)生式相關(guān)聯(lián)O

主要就是為CFG中的文法符號(hào)設(shè)置語(yǔ)義屬性，具體來(lái)說(shuō)，主要就是將一些語(yǔ)義屬性附加到代表語(yǔ)言構(gòu)造的文法符號(hào)上，從而把信息和語(yǔ)言構(gòu)造聯(lián)系起來(lái)?

對(duì)于文法符號(hào)X和屬性a，用X.a表示分析樹(shù)中的某個(gè)標(biāo)號(hào)為X的結(jié)點(diǎn)的值?一個(gè)分析樹(shù)結(jié)點(diǎn)和它的分支對(duì)應(yīng)于一個(gè)產(chǎn)生式規(guī)則，而對(duì)應(yīng)的語(yǔ)義規(guī)則確定了這些結(jié)點(diǎn)上的屬性的取值語(yǔ)法制導(dǎo)的定義(SDD)?屬性文法?基于屬性文法的處理方式?S屬性文法和L屬性文法?語(yǔ)法制導(dǎo)的定義?語(yǔ)法制導(dǎo)的翻譯方案?SDT中左遞歸的消除?類型檢查提綱?語(yǔ)法制導(dǎo)的翻譯方案(SDT)是在產(chǎn)生式體中嵌入程序片斷(語(yǔ)義動(dòng)作)的上下文

無(wú)關(guān)文法?SDT的基本實(shí)現(xiàn)方法O

建立語(yǔ)法分析樹(shù)O

將語(yǔ)義動(dòng)作看作是虛擬的結(jié)點(diǎn)O

從左到右、深度優(yōu)先地遍歷分析樹(shù)，在訪問(wèn)虛擬結(jié)點(diǎn)時(shí)執(zhí)行相應(yīng)動(dòng)作語(yǔ)法制導(dǎo)的翻譯方案?語(yǔ)句3*4*5的分析樹(shù)如右?DFS可知?jiǎng)幼鲌?zhí)行順序O

A71,A5,A72,A41,A73,A42,A2O

注意，一個(gè)動(dòng)作的不同實(shí)例所訪問(wèn)的屬性值屬于不同的結(jié)點(diǎn)在語(yǔ)法樹(shù)上實(shí)現(xiàn)SDT*F

A41digit:4F

A42digit:5digit:3

A71*A5T1FA73A72T3T2A2E?實(shí)現(xiàn)SDT時(shí)，實(shí)際上并不會(huì)真的構(gòu)造語(yǔ)法分析樹(shù)，

而是在分析過(guò)程中執(zhí)行語(yǔ)義動(dòng)作?SDT可以看做是SDD的具體實(shí)施方案?即使基礎(chǔ)文法可以應(yīng)用某種分析技術(shù)，仍可能因?yàn)閯?dòng)作的緣故(例如屬性計(jì)算過(guò)程中的循環(huán)依賴)導(dǎo)致此技術(shù)不可應(yīng)用?用SDT實(shí)現(xiàn)兩類重要的SDDO

基本文法可以使用LR分析技術(shù)，且SDD是S屬性的O

基本文法可以使用LL分析技術(shù)，且SDD是L屬性的可在語(yǔ)法分析過(guò)程中實(shí)現(xiàn)的SDT?判斷是否可在分析過(guò)程中實(shí)現(xiàn)O

將每個(gè)語(yǔ)義動(dòng)作替換為一個(gè)獨(dú)有的標(biāo)記非終結(jié)符號(hào)；每個(gè)標(biāo)記非終結(jié)符號(hào)M的產(chǎn)生式為M

t

εO

如果新的文法可以由某種方法進(jìn)行分析，那么這個(gè)SDT就可以在這個(gè)分析過(guò)程中實(shí)現(xiàn)O

注意：這個(gè)方法沒(méi)有考慮變量值的傳遞等要求可在語(yǔ)法分析過(guò)程中實(shí)現(xiàn)的SDT?非常簡(jiǎn)單，由于S屬性的SDD中，所有的屬

性均為綜合屬性，因此，只有當(dāng)所有子屬性計(jì)算完畢之后，才能計(jì)算父節(jié)點(diǎn)?因此，我們只需要把所有的語(yǔ)義規(guī)則放到對(duì)應(yīng)產(chǎn)生式的右部即可將S屬性的SDD轉(zhuǎn)換為SDT?將計(jì)算某個(gè)非終結(jié)符號(hào)A的繼承屬性的動(dòng)作插入到產(chǎn)生式右部中緊靠在A的本次出現(xiàn)之前的位置上；?將計(jì)算一個(gè)產(chǎn)生式左部符號(hào)的綜合屬性的動(dòng)作放置在這個(gè)產(chǎn)生式右部的最右端；將L屬性的SDD轉(zhuǎn)換為SDT?如果一個(gè)L屬性的SDD的基本文法可以使用LL分析技術(shù)，那么它的SDT可以在LL或者

LR語(yǔ)法分析過(guò)程中實(shí)現(xiàn)；將L屬性的SDD轉(zhuǎn)換為SDT?L

t

E

n

M1

M1

t

ε?E

t

E+T

M2

M2

t

ε?E

t

T

M3

M3

t

ε?…

…

…

…判斷SDT可否用特定分析技術(shù)實(shí)現(xiàn)例子?基本類型和數(shù)組類型的L屬性定義語(yǔ)法制導(dǎo)翻譯的應(yīng)用例子?抽象語(yǔ)法樹(shù)的構(gòu)造?抽象語(yǔ)法樹(shù)O

每個(gè)結(jié)點(diǎn)代表一個(gè)語(yǔ)法結(jié)構(gòu)；對(duì)應(yīng)于一個(gè)運(yùn)算符O

結(jié)點(diǎn)的每個(gè)子結(jié)點(diǎn)代表其子結(jié)構(gòu)；對(duì)應(yīng)于運(yùn)算分量O

表示這些子結(jié)構(gòu)按照特定方式組成了較大的結(jié)構(gòu)O

可以忽略掉一些標(biāo)點(diǎn)符號(hào)等非本質(zhì)的東西?語(yǔ)法樹(shù)的表示方法O

每個(gè)結(jié)點(diǎn)用一個(gè)對(duì)象表示O

對(duì)象有多個(gè)域?葉子結(jié)點(diǎn)中只存放詞法值?內(nèi)部結(jié)點(diǎn)中存放了op值和參數(shù)(通常指向其它結(jié)點(diǎn))構(gòu)造抽象語(yǔ)法樹(shù)的SDD?屬性E.node指向E對(duì)應(yīng)的語(yǔ)法樹(shù)的根結(jié)點(diǎn)構(gòu)造簡(jiǎn)單表達(dá)式的語(yǔ)法樹(shù)的SDD?輸入：a-4+c?步驟：O

p1=new

Leaf(id,entry_a)O

p2=new

Leaf(num,4);O

p3=new

Node(‘-’,p1,p2);O

p4=new

Leaf(id,entry_c);O

p5=new

Node(‘+’,p3,p4);表達(dá)式語(yǔ)法樹(shù)的構(gòu)造過(guò)程自頂向下方式處理的L屬性定義(1)?在消除左遞歸時(shí)，按照規(guī)則得到此SDD?

對(duì)于這個(gè)SDD，各屬性值的計(jì)算過(guò)程實(shí)際上和原來(lái)S屬性定義中的計(jì)算過(guò)程一致?繼承屬性可以把值從一個(gè)結(jié)構(gòu)傳遞到另一個(gè)并列的結(jié)構(gòu)；也可把值從父結(jié)構(gòu)傳遞到子結(jié)構(gòu)?

抽象語(yǔ)法樹(shù)和分析樹(shù)不一致時(shí)，繼承屬性很有用自頂向下方式處理的L屬性定義(2)計(jì)算a-4+c的依賴圖?

不同的語(yǔ)法分析

樹(shù)與抽象語(yǔ)法樹(shù)

?a-4+cS

t

L.LS

t

LL

t

LBL

tBB

t0B

t1按語(yǔ)法制導(dǎo)翻譯的方法，給出相應(yīng)的語(yǔ)義規(guī)則。?令S.val為下面文法由S生成的二進(jìn)制數(shù)的值(例如，對(duì)于輸入

101.101,S.val=5.625)：習(xí)題?后綴SDT：所有動(dòng)作都在產(chǎn)生式最右端的

SDT?文法可以自底向上分析且SDD是S屬性的，

必然可以構(gòu)造出后綴SDT?構(gòu)造方法O

將每個(gè)語(yǔ)義規(guī)則看作是一個(gè)賦值語(yǔ)義動(dòng)作O

將所有的語(yǔ)義動(dòng)作放在規(guī)則的最右端后綴翻譯方案注意動(dòng)作中對(duì)屬性值的引用?我們?cè)试S語(yǔ)句引用全局變量，局部變量，文法符號(hào)的屬性

?

文法符號(hào)的屬性只能被賦值一次

?實(shí)現(xiàn)桌上計(jì)算器的后綴SDT后綴翻譯方案的例子?可以在LR語(yǔ)法分析的過(guò)程中實(shí)現(xiàn)O

歸約時(shí)執(zhí)行相應(yīng)的語(yǔ)義動(dòng)作O

定義用于記錄各文法符號(hào)的屬性的union結(jié)構(gòu)O

棧中的每個(gè)文法符號(hào)(或者說(shuō)狀態(tài))都附帶一個(gè)這樣的union類型的值O

在按照產(chǎn)生式A

t

XYZ歸約時(shí)，Z的屬性可以在棧頂找到，Y的屬性可以在下一個(gè)位置找到，X的屬

性可以在再下一個(gè)位置找到后綴SDT的語(yǔ)法分析棧實(shí)現(xiàn)?假設(shè)語(yǔ)法分析棧存放在一個(gè)被稱為stack的記錄數(shù)組中，下標(biāo)top指向棧頂O

stack[top]是這個(gè)棧的棧頂O

stack[top-1]指向棧頂下一個(gè)位置O

如果不同的文法符號(hào)有不同的屬性集合，我們可以使用union來(lái)保存這些屬性值?歸約時(shí)能夠知道棧頂向下的各個(gè)符號(hào)分別是什么,因此我們也能夠確定各個(gè)union中究竟存放了什么樣的值分析棧實(shí)現(xiàn)的例子注意：

stack[top-i]

和文法符號(hào)的對(duì)應(yīng)?這個(gè)SDT中沒(méi)有局部變量，不會(huì)產(chǎn)生和局部變量有關(guān)的問(wèn)題后綴SDT的棧實(shí)現(xiàn)?動(dòng)作左邊的所有符號(hào)(以及動(dòng)作)處理完成后，就立刻執(zhí)行這個(gè)動(dòng)作O

B

t

X{a}YO

自底向上分析時(shí)，在X出現(xiàn)在棧頂時(shí)執(zhí)行動(dòng)作aO

自頂向下分析時(shí)，在試圖展開(kāi)Y或者在輸入中檢測(cè)到Y(jié)的時(shí)刻執(zhí)行a產(chǎn)生式內(nèi)部帶有語(yǔ)義動(dòng)作的SDT?

不是所有的SDT都可以在分析過(guò)程中實(shí)現(xiàn)O

后綴SDT以及L屬性對(duì)應(yīng)的SDT可以在分析時(shí)完成對(duì)于一般的SDT，可以先建

立分析樹(shù)(語(yǔ)義動(dòng)作作為

虛擬的結(jié)點(diǎn))，然后進(jìn)行

前序遍歷并執(zhí)行動(dòng)作移入/規(guī)約

沖突：M