編譯原理課件 第6章 屬性文法及語法制導翻譯

本章在編譯程序中的地位

表格管理詞法分析器語法分析器語義分析與中間代碼產(chǎn)生優(yōu)化器目標代碼生成器源程序單詞符號語法單位中間代碼中間代碼目標代碼出錯處理1教學要求掌握：兩種屬性:綜合屬性，繼承屬性基于屬性文法的處理方法---語法制導翻譯方法2教學內容6.1屬性文法綜合屬性，繼承屬性，語義規(guī)則，屬性文法6.2基于屬性文法的處理方法語法制導翻譯，依賴圖法計算屬性，樹遍歷計算屬性，一遍掃描的處理方法，抽象語法樹3

CH.6屬性文法和語法制導翻譯在分析-綜合模式的編譯器中,語義分析是分析過程的最后一個步驟，只有在這一步才真正開始考慮程序語言的意義，并著手把它們翻譯成某種中間代碼。這一過程通常采用的方法是屬性文法和語法制導翻譯方法。語法制導翻譯方法的基本思想是，根據(jù)翻譯的需要設置文法符號的屬性，用屬性描述語法結構的語義，用屬性的計算完成翻譯。屬性文法使文法符號屬性值的計算和產(chǎn)生式相聯(lián)系。隨著語法分析的進行，執(zhí)行屬性值的計算，從而完成語義分析和翻譯的任務。46.1屬性文法屬性文法,也稱屬性翻譯文法或語法制導定義,是Knuth在1968年首先提出來的。屬性：在上下文無關文法的基礎上為每個文法符號X(終結符或非終結符)配備若干個相關的“值”---這些“值”就稱為文法符號X的屬性。屬性值的設置和語法結構的語義以及翻譯程序的需要有關。屬性代表與文法符號相關語義信息，如類型、值、代碼序列、符號表內容等5屬性、語義規(guī)則、屬性文法屬性一般分為兩類：綜合屬性和繼承屬性。屬性和變量一樣，可以在語法分析過程中進行計算和傳遞。語義規(guī)則：屬性的計算規(guī)則。屬性的加工和計算的過程即是語義處理的過程。屬性文法：以一個上下文無關文法為基礎,為每個文法符號引進一組屬性，對文法的每個產(chǎn)生式都配備一組與之相關聯(lián)的屬性的計算規(guī)則(語義規(guī)則),這樣得到的文法。屬性文法是對上下文無關文法的推廣。6屬性文法、語義規(guī)則(1)屬性文法的形式：產(chǎn)生式語義規(guī)則.

Ab:=f(c1,c2,…,ck)這里,f是一個函數(shù),表示屬性b依賴于屬性c1,c2,…,ck，而且規(guī)定b:(1)b是A的一個綜合屬性并且c1,c2,…,ck是產(chǎn)生式右部文法符號的屬性；或者(2)b是產(chǎn)生式右邊某個文法符號的一個繼承屬性并且

c1,c2,…,ck是A或產(chǎn)生式右部任何文法符號的屬性

。7屬性文法的說明(1)P136(1)終結符只有綜合屬性,它由詞法分析器提供例如digit.lexval

表示單詞符號“數(shù)”的詞法值

id.entry表示單詞符號“標識符”的符號表入口(2)非終結符既可以有綜合屬性也可以有繼承屬性，在屬性文法的語義規(guī)則中計算(3)關于屬性計算的規(guī)定①文法的開始符號的所有繼承屬性作為屬性計算前的初始值。②一般來講，對出現(xiàn)在產(chǎn)生式AX1X2…Xn左邊的非終結符A的綜合屬性和出現(xiàn)在產(chǎn)生式右部的符號Xi的繼承屬性都必須提供一個計算規(guī)則。8屬性文法的說明(2)③與產(chǎn)生式AX1X2…Xn

相關聯(lián)的屬性計算不能有A的繼承屬性和Xi的綜合屬性的計算規(guī)則。④出現(xiàn)在產(chǎn)生式左邊非終結符A的繼承屬性和出現(xiàn)在產(chǎn)生式右邊符號Xi的綜合屬性由其它產(chǎn)生式的屬性規(guī)則計算或者由屬性計算器的參數(shù)提供。9屬性文法、語義規(guī)則(2)屬性文法的形式：產(chǎn)生式語義規(guī)則.

Ab:=f(c1,c2,…,ck)例如P137.表6.1的屬性文法:

EE1+TE.val:=E1.val+T.val例如P139.表6.2的屬性文法:

DTLL.in:=T.typeLL1,idL1.in:=L.in綜合屬性綜合屬性繼承屬性繼承屬性繼承屬性10例,P137.

假設：產(chǎn)生式語義規(guī)則ABCA.b:=A.a+B.cC.d:=B.c+1

A有綜合屬性b和繼承屬性aB有綜合屬性cC有繼承屬性d繼承屬性A.a和綜合屬性B.c在其他適當?shù)牡胤接嬎恪?1語義規(guī)則所描述的工作語義規(guī)則所描述的工作可以是任何希望的翻譯工作，如:屬性計算、靜態(tài)語義檢查、符號表操作、中間代碼生成、報告出錯，等等。語義規(guī)則可能產(chǎn)生副作用(如產(chǎn)生代碼)，也可能不是變元的嚴格函數(shù)b:=f(c1,c2,…,ck)，如某個規(guī)則給出可用的下一個數(shù)據(jù)單元的地址。這樣的語義規(guī)則通常寫成過程調用或過程段---這時認為定義了一個虛屬性。12屬性文法舉例：P137.表6.1一個簡單的臺式計算器的屬性文法。輸入一個含+、*、(、)和數(shù)字的算術表達式(文法的句子),計算并輸出其值,輸入行以n結束。產(chǎn)生式語義規(guī)則LEn

Print(E.val)

EE1+T

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

E.val:=T.valTT1*FT.val:=T1.val*F.valTF

T.val:=F.valF(E)

F.val:=E.valFdigit

F.val:=digit.lexval1.

非終結符E,T,F有綜合屬性val---表達式值2.

終結符digit有綜合屬性lexval---數(shù)的二進制值，由詞法分析器提供3.注：同一個產(chǎn)生式的相同非終結符加上下標，以區(qū)分這些非終結符的屬性值引用的二義性13兩種屬性：綜合屬性綜合屬性用于“自下而上”傳遞信息。綜合屬性：在語法樹中，一個結點的綜合屬性的值由其子結點的屬性值確定。通常結合使用自下而上的分析方法在每一個結點處使用語義規(guī)則計算綜合屬性的值---由下層子結點的屬性值計算上層父結點的綜合屬性值，隨著自下而上語法分析的進行，最終可計算出開始符號的綜合屬性值。AX1X2…XnA.bX1.c1X2.c2…Xn.

ckAX1X2…Xnb:=f(c1,c2,…,ck)帶注釋的語法樹14綜合屬性舉例：例6.1綜合屬性的使用及其自下而上的計算過程P137.表6.1臺式計算器的屬性文法，輸入一個表達式(以n結尾)，計算并打印其值。例如：輸入表達式3*5+4n，輸出數(shù)值19。P138.圖6.1給出了輸入串3*5+4n的帶注釋的語法樹–屬性化的語法樹。綜合屬性X.val值隨著自下而上語法分析的進行，自下而上的計算、傳遞和流動---在每次歸約時執(zhí)行語義規(guī)則，計算屬性值，最終計算出開始符號的綜合屬性值，打印出來完成翻譯。見下頁圖15digitlexvaldigitlexvaldigitlexvalFvalT1valFvalTval*E1valFvalTval+EvalLnPrint(E.val)翻譯3*5+4n求表達式值=3=3=5=5=15=15=4=4=4=19=316兩種屬性：繼承屬性繼承屬性用于“自上而下”傳遞信息。繼承屬性：在語法樹中，一個結點的繼承屬性由此結點的父結點和(或)兄結點的某些屬性確定?？梢杂美^承屬性來表示程序語言結構中的上下文依賴關系。繼承屬性的計算可以結合自上而下的語法分析進行。A

X1…X

…XnA.ck

X1.c1…X.b…XnAX1X2…Xnb:=f(c1,c2,…,ck)17表6.2帶有繼承屬性L.in的屬性文法

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

DTLLin:=TtypeTintTtype:=integerTrealTtype:=realLL1,idL1

in:=Linaddtype(identry,Lin)Lidaddtype(identry,Lin)

例6.2說明句的帶有繼承屬性計算的屬性文法T.type是綜合屬性---標識符的類型L.in為繼承屬性---傳遞類型信息18繼承屬性的使用和計算：例6.2繼承屬性的使用及其自上而下的計算過程P137.表6.2的屬性文法，用繼承屬性L.in

為說明語句中的各個標識符提供類型信息。例如：說明語句reala,b,c;inti,j,k;T.type是綜合屬性,由說明語句中的關鍵字real/int確定,結合產(chǎn)生式Tint或Treal

賦值T.type:=integer或real。TintT.type:=integerTreal

T.type:=realT.typeintT.typereal19繼承屬性的使用和計算：例6.2續(xù)例6.2,

P137.表6.2屬性文法，用繼承屬性in為說明語句中的各個標識符提供類型信息。L.in繼承屬性,在DTLL.in:=T.typeLL1,id

L1.in:=L.in中計算。D

T.type

L.inL.inL1.in，id

依賴于兄依賴于父Addtype(id.entry,L.in)把標識符的類型信息填入符號表,入口為id.entry---這個過程定義了一個虛屬性。20圖6.2說明語句

realid1,id2,id3

的帶有繼承屬性的語法樹繼承屬性in的值自上而下從左到右計算、傳遞和流動。三個L結點的L.in分別給出標識符id1、id2和id3的類型。過程addtype(id.entry,L.in)把id的類型填入符號表。id3T.type=realDL.in=realL.in=realrealL.in=real,id1id2,216.2基于屬性文法的處理方法屬性文法：產(chǎn)生式語義規(guī)則.

Aα

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

語義規(guī)則的計算可以執(zhí)行任何翻譯動作。對輸入串的翻譯也就是根據(jù)語義規(guī)則進行計算得出結果。屬性文法是比較抽象的翻譯說明，隱藏了一些實現(xiàn)細節(jié),主要是無須指明翻譯時語義規(guī)則的計算次序。本節(jié)討論語義規(guī)則的計算方法，指明屬性文法中語義規(guī)則的計算次序，從而把語義規(guī)則改造為計算屬性的語義程序，把靜態(tài)的語義規(guī)則改寫為可動態(tài)執(zhí)行的語義動作---語法制導翻譯方法。22語法制導翻譯法語法制導翻譯法：由源程序的語法結構所驅動的處理辦法。這種處理方法是基于屬性文法的處理過程：①對單詞符串進行語法分析,構造帶屬性的語法樹②根據(jù)需要遍歷語法樹,并在語法樹的各結點處按語義規(guī)則進行計算即得翻譯結果。P139.圖6.3語法制導翻譯的輪廓:

輸入串語法樹(帶屬性注釋)語法分析深度優(yōu)先樹遍歷對輸入串的翻譯結果進行計算拓撲排序語義規(guī)則計算次序結點屬性間依賴關系的依賴圖構造23所謂遍歷是指沿著某條搜索路線，依次對樹中每個結點均做一次且僅做一次訪問。訪問結點所做的操作依賴于具體的應用問題。

24一遍掃描的語法制導翻譯一個具體的語法制導翻譯的實現(xiàn)不一定非要按圖6.3的輪廓不可。在某些情況下可用一遍掃描實現(xiàn)屬性文法的語義規(guī)則計算---即在語法分析的同時完成語義規(guī)則的計算。無須明顯地構造語法樹或依賴圖。此節(jié)以后的各節(jié)以及CH7.都討論這種特殊方法---一遍掃描的語法制導翻譯方法。一遍掃描的語法制導翻譯輪廓:

輸入串───翻譯結果語法分析的同時完成語義規(guī)則的計算256.2.1依賴圖語義規(guī)則建立了屬性之間的依賴關系，這些關系可以用圖來表示，這樣的圖稱為屬性依賴圖。語法樹結點屬性的依賴圖是一個有向圖：結點：語法樹結點的屬性(綜合屬性或繼承屬性)有向邊：屬性的依賴關系，如果屬性b依賴于屬性c，即b:=f(c)，則:語義規(guī)則b:=f(c1,c2,…,ck)，b可能是一個虛綜合屬性(即沒有b,f是一個過程)，其依賴圖見右圖。依賴圖構造方法見P140.bcbc1ckc2…26依賴圖：例6.3簡例:下面屬性文法的依賴圖：AXYA.a:=f(X.x,Y.y)X.i:=g(A.a,Y.y)

例6.3:下面的屬性文法的依賴圖EE1+E2

E.val:=E1.val+E2.val語法樹EE1+E2依賴圖

P141.圖6.4E.valE1.valE2.valA.aX.iX.xY.yA

XY27例6.4圖6.5句子

realid1,id2,id3

的語法樹及依賴圖TLLid3Lid2Did1real,,4typein5L.in:=T.typein7L1.in:=L.inin9L1.in:=L.in3entry6addtype(id.entry,L.in)2entry8addtype(id.entry,L.in)1entry10addtype(id.entry,L.in)結點1、2、3是id.entry屬性結點6、8、10代表虛屬性有向邊表示屬性的依賴關系數(shù)字標識結點表示計算次序28良定義的屬性文法對語義規(guī)則b:=f(c1,c2,…,ck)來說,只有在屬性c1,c2,…,ck均已知的情況才可以使用來計算b。但，有時會出現(xiàn)一個屬性對另一個屬性的循環(huán)依賴關系。如果一屬性文法不存在屬性之間的循環(huán)依賴關系，那么該屬性文法為良定義的。為了設計編譯程序，我們只處理良定義的屬性文法。例如設p，c1，c2都是屬性，以下計算規(guī)則就無法對p求值。p:=f1(c1)c1:=f2(c2)c2:=f3(p)DAG圖：良定義屬性文法的依賴圖，

無環(huán)有向圖(DirectedAcyclicGraph)pc2c129依賴圖法：屬性的計算次序1.一個有向非循環(huán)圖(DAG圖)的拓撲序:是圖中結點的任何順序m1,m2,…,mk,使得有向邊必須是從序列中前面的結點指向后面的結點。也就是說，如果mimj

是mi

到mj

的一條邊，那么在序列中mi必須出現(xiàn)在mj

之前。2.一個依賴圖(DAG圖)的任何拓撲排序都給出一個語法樹中結點的語義規(guī)則計算的有效順序。這就是說，在拓撲排序中，在一個結點上，語義規(guī)則b:=f(c1,c2,…ck)中的屬性c1,c2,…ck在計算b以前都是可用的。30例6.5

P141.圖6.5的依賴圖的一個拓撲排序是：

1，2，3，4，5，6，7，8，9，10由此拓撲序可以得到下面的程序(an代表與n有關的屬性),該程序把3個標識符a,b,c的類型信息(real)填入符號表中每個標識符對應的符號表項中。程序

a4:=real;語義規(guī)則

T.type:=reala5:=a4;L.in:=T.typeaddtype(id3entry,a5);虛屬性6a7:=a5;L1.in:=L.inaddtype(id2entry,a7);虛屬性8a9:=a7;L1.in:=L.inaddtype(id1entry,a9);虛屬性10依賴圖法屬性的計算次序：例

31屬性文法說明的語法制導翻譯是很精確的：(1)基礎文法用于建立輸入串的語法分析樹(可帶屬性注釋);(2)構造對應語法樹的依賴圖;(3)對依賴圖進行拓撲排序;(4)從拓撲序得到計算語義規(guī)則的次序;(5)按此次序計算語義規(guī)則便得到輸入串的翻譯結果。依賴圖法屬性的計算次序：說明

326.2.2樹遍歷的屬性計算方法通過語法樹遍歷計算屬性值的方法有很多種。這些方法都假設：1.語法樹已經(jīng)建立起來了，并且樹中已帶有開始符號的繼承屬性和終結符的綜合屬性。2.然后以某種次序遍歷語法樹，直至計算出所有結點的屬性值。最常用的遍歷方法是深度優(yōu)先，對語法樹自上而下從左到右遍歷的方法。對遍歷到的結點計算其所有能夠計算的屬性值。可能需要使用多次樹遍歷，直到把所有的結點的所有屬性都計算出來。P142.有一個深度優(yōu)先樹遍歷的算法，對任何良定義的屬性文法進行屬性的計算。用例子說明。33深度優(yōu)先樹遍歷計算屬性：例6.6

P143.表6.3的屬性文法。屬性S.a(=0)繼,S.b綜;X.c繼,X.d綜;Y.e繼,Y.f綜;Z.h繼,Z.g綜圖6.6產(chǎn)生式語義規(guī)則SXYZX.c:=Z.gY.e:=S.bZ.h:=S.aS.b:=X.d-2Xx

X.d:=2*X.cYy

Y.f:=Y.e*3Zz

Z.g:=Z.h+1xyz.h=0第一次遍歷S.a=0

XYZ.g=1.d=2.c=1.b=0第二次遍歷.e=0.f=0第三次遍歷346.2.3一遍掃描的處理方法與樹遍歷的屬性計算方法不同，一遍掃描的處理方法是在語法分析的同時計算屬性值。這種屬性計算方法與兩個因素密切相關:1.所采用的語法分析方法(自上而下或自下而上)。2.屬性的計算次序，即語法分析到什么時候計算屬性。一遍掃描的處理方法語義規(guī)則執(zhí)行的時間:1.在自上而下語法分析中，若一個產(chǎn)生式匹配輸入串成功時執(zhí)行與此產(chǎn)生式相應的語義規(guī)則。2.在自下而上語法分析中，當一個產(chǎn)生式被用于進行歸約時，此產(chǎn)生式相應的語義規(guī)則就被計算。35一遍掃描的處理方法按一遍掃描的編譯程序模型來理解語法制導翻譯方法，直觀上說是為基礎文法的每個產(chǎn)生式配上一組語義規(guī)則，并且在語法分析的同時執(zhí)行這些語義規(guī)則。一遍掃描的屬性計算方法是語法分析工作和語義規(guī)則的計算穿插進行。但以語法分析作主導。S-屬性文法(僅含綜合屬性的屬性文法)可用于一遍掃描的自下而上分析。L-屬性文法(含有繼承屬性的屬性文法)可用于一遍掃描的自上而下分析。366.2.4抽象語法樹語法制導翻譯以語法樹作基礎,實際上,語法樹可以作為一種合適的中間語言形式?，F(xiàn)在對語法樹進行改造，去掉那些對翻譯不必要的信息，將語法樹進行抽象---抽象語法樹。在表達式的抽象語法樹中，運算符、關鍵字不作葉子結點而作為內部結點，葉子結點只是運算量。抽象語法樹也可以屬性化，給結點加上屬性變成帶附注的抽象語法樹。語法制導翻譯既可以基于語法分析樹也可以基于抽象語法樹進行，采用的基本方法是一樣的。37抽象語法樹：簡例例，為下面文法的句子a-4+c

建立抽象語法樹。EE+T|E－T|TT(E)Tid|num為每個運算量或運算符號都建立一個結點?？梢愿鶕?jù)表達式的運算順序自下而上的構造---手工構造。a－+c4抽象語法樹運算符作內部結點id(a)EE－TE+TTnum(4)id(c)語法樹38抽象語法樹的實現(xiàn)抽象語法樹中的每一個結點可以由包含幾個域的記錄來實現(xiàn)；有向邊用指針實現(xiàn)。在一個運算量對應的結點(葉結)中,一個域標識運算量，另一個域是該運算量的屬性值(或指針)。在一個運算符號對應的結點中,一個域標識運算符號，其它域包含指向運算分量的結點的指針。運算符號通常叫做這個結點的標號。進行翻譯時，抽象語法樹中的結點可能會用附加域來存放結點的屬性值(或指向屬性的指針）。numvalid.op..Toentryofid右子樹根結左子樹根結39建立表達式的抽象語法樹使用的函數(shù),這些函數(shù)返回新建立結點的指針。1.mknode(op,left,right)

建立一個運算符號結點，標號是op,兩個域