第六章語法制導翻譯與屬性文法SchoolofComputerScience&TechnologyHarbinInstituteofTechnology重點：語法制導翻譯的基本思想，語法制導定義，翻譯模式，自頂向下翻譯，自底向上翻譯。

難點：屬性的意義，對綜合屬性，繼承屬性，固有屬性的理解，屬性計算，怎么通過屬性來表達翻譯。

2023/2/12第6章

語法制導翻譯與屬性文法6.1語法制導翻譯概述6.2語法制導定義6.3屬性計算6.4翻譯模式6.5本章小結2023/2/13為什么進行詞法和語法分析？用A→α進行歸約表達的是什么意思？看：operand+termE→E1+TE1的值+T的值的結果作為E的值——即：取來E1的值和T的值做加法運算，結果作為E的值E.val=E1.val+T.val問題2023/2/146.1語法制導翻譯概述為了提高編譯程序的可移植性，一般將編譯程序劃分為前端和后端。前端通常包括詞法分析、語法分析、語義分析、中間代碼生成、符號表的建立，以及與機器無關的中間代碼優化等，它們的實現一般不依賴于具體的目標機器。后端通常包括與機器有關的代碼優化、目標代碼的生成、相關的錯誤處理以及符號表的訪問等。圖6.1編譯器前端的邏輯結構2023/2/156.1語法制導翻譯概述語義分析器的主要任務是檢查各個語法結構的靜態語義，稱為靜態語義分析或靜態檢查類型檢查：操作數和操作符的類型是否相容；控制流檢查：控制流轉向的目標地址是否合法；惟一性檢查：對象是否被重復定義；關聯名檢查：同一名字的多次特定出現是否一致。將靜態檢查和中間代碼生成結合到語法分析中進行的技術稱為語法制導翻譯。2023/2/166.1語法制導翻譯概述語法制導翻譯的基本思想在進行語法分析的同時，完成相應的語義處理。也就是說，一旦語法分析器識別出一個語法結構就要立即對其進行翻譯，翻譯是根據語言的語義進行的，并通過調用事先為該語法結構編寫的語義子程序來實現。

對文法中的每個產生式附加一個/多個語義動作(或語義子程序)，在語法分析的過程中，每當需要使用一個產生式進行推導或歸約時，語法分析程序除執行相應的語法分析動作外，還要執行相應的語義動作(或調用相應的語義子程序)。2023/2/176.1語法制導翻譯概述語義子程序的功能指明相應產生式中各個文法符號的具體含義，并規定了使用該產生式進行分析時所應采取的語義動作(如傳送或處理語義信息、查填符號表、計算值、生成中間代碼等)。語義信息的獲取和加工是和語法分析同時進行的，而且這些語義信息是通過文法符號來攜帶和傳遞的。2023/2/186.1語法制導翻譯概述一個文法符號X所攜帶的語義信息稱為X的語義屬性，簡稱為屬性，它是根據翻譯的需要設置的(對應分析樹結點的數據結構)，主要用于描述語法結構的語義。一個變量的屬性有類型、層次、存儲地址等表達式的屬性有類型、值等。2023/2/196.1語法制導翻譯概述屬性值的計算和產生式相關聯，隨著語法分析的進行，執行屬性值的計算，完成語義分析和翻譯的任務。E→E1+E2

E.val:=E1.val+E2.val語法結構具有規定的語義問題：如何根據被識別出的語法成分進行語義處理？亦即怎樣將屬性值的計算及翻譯工作同產生式相關聯？2023/2/110典型處理方法一語法制導定義通過將屬性與文法符號關聯、將語義規則與產生式關聯來描述語言結構的翻譯方案對應每一個產生式編寫一個語義子程序，當一個產生式獲得匹配時，就調用相應的語義子程序來實現語義檢查與翻譯E→E1+T {E.val:=E1.val+T.val}T→T1*F {T.val:=T1.val*F.val}F→digit {F.val:=digit.lexval}適宜在完成歸約的時候進行2023/2/111典型處理方法二翻譯模式通過將屬性與文法符號關聯，并將語義規則插入到產生式的右部來描述語言結構的翻譯方案在產生式的右部的適當位置，插入相應的語義動作，按照分析的進程，執行遇到的語義動作D→T{L.inh:=T.type}LT→int{T.type:=integer}T→real{T.type:=real}L→{L1.inh:=L.inh}L1,id{addtype(id.entry,L.inh)}L→id{addtype(id.entry,L.inh)}

適宜在進行推導時完成2023/2/1126.2語法制導定義語法制導定義是附帶有屬性和語義規則的上下文無關文法屬性是與文法符號相關聯的語義信息語義規則是與產生式相關聯的語義動作語法制導定義是基于語言結構的語義要求設計的，類似于程序設計，語法制導定義中的屬性類似于程序中用到的數據結構，用于描述語義信息，語義規則類似于計算，用于收集、傳遞和計算語義信息的。屬性通常被保存在分析樹的相關節點中2023/2/113概念術語綜合屬性：節點的屬性值是通過分析樹中該節點或其子節點的屬性值計算出來的繼承屬性：節點的屬性值是由該節點、該節點的兄弟節點或父節點的屬性值計算出來的固有屬性：通過詞法分析直接得到的屬性依賴圖：描述屬性之間依賴關系的圖，根據語義規則來構造注釋分析樹：節點帶有屬性值的分析樹2023/2/114語法制導定義的形式在一個語法制導定義中，A→P都有與之相關聯的一套語義規則，規則形式為

b：=f（c1，c2，…，ck），f是一個函數，而且或者

1．b是A的一個綜合屬性并且c1，c2，…，ck是中的符號的屬性，或者

2．b是中某個符號的一個繼承屬性并且c1，c2，…，ck是A或中的任何文法符號的屬性。這兩種情況下，都說屬性b依賴于屬性c1，c2，…，ck2023/2/115例6.1

臺式計算器的語法制導定義產生式語義規則LEn

print(Eval)(可看作是L的虛屬性)EE1+T

Eval:=E1val+TvalET

Eval:=TvalTT1*F

Tval:=T1val+FvalTF

Tval:=FvalF(E)Fval:=EvalFdigitFval:=digitlexval2023/2/116S-屬性定義只含綜合屬性的語法制導定義稱為S-屬性定義對于S-屬性定義，通常使用自底向上的分析方法，在建立每一個結點處使用語義規則來計算綜合屬性值，即在用哪個產生式進行歸約后，就執行那個產生式的S-屬性定義計算屬性的值，從葉結點到根結點進行計算。沒有副作用的語法制導定義有時又稱為屬性文法，屬性文法的語義規則單純根據常數和其它屬性的值來定義某個屬性的值2023/2/117繼承屬性當分析樹的結構同源代碼的抽象語法不“匹配”時，繼承屬性將非常有用。下面的例子可以說明怎樣用繼承屬性來解決這種不匹配問題，產生這種不匹配的原因是因為文法通常是為語法分析而不是為翻譯設計的。例6.2考慮如何在自頂向下的分析過程中計算3*5和4*8*9這樣的表達式項消除左遞歸之后的算數表達式文法的一個子集：

T→FT'T'→*FT1'T'→ε

F→digit2023/2/118表6.3

為適于自頂向下分析的文法設計的語法制導定義產生式語義規則T→FT

'T

'.inh:=F.valT.val:=T

'.syn

T

'→*FT1'T1'.inh:=T

'.inh×F.valT

'.syn:=T1'.synT

'→εT

'.syn:=T

'.inhF→digitF.val:=digit.lexval2023/2/1194*8*9的注釋分析樹2023/2/120表6.3中語法制導定義對應的翻譯模式如果對4*8*9進行自頂向下的語法制導翻譯，則val的值的計算順序為⑴⑵⑶⑷⑸⑹⑺⑻⑼⑽⑾⑿⒀根據上述對val值的計算順序，可以將表6.3中的語法制導定義轉換成如下的翻譯模式T→F{T'.inh:=F.val}T'{T.val:=T'.syn}T'→*F{T1'.inh:=T'.inh×F.val}T1'{T'.syn:=T1'.syn}T'→ε{T'.syn:=T'.inh}F→digit{F.val:=digit.lexval}2023/2/1216.3屬性計算語義規則定義了屬性之間的依賴關系，這種依賴關系將影響屬性的計算順序為了確定分析樹中各個屬性的計算順序，我們可以用圖來表示屬性之間的依賴關系，并將其稱為依賴圖如果依賴圖中沒有回路，則利用它可以很方便地求出屬性的計算順序。注釋分析樹只是給出了屬性的值，而依賴圖則可以幫助我們確定如何將這些屬性值計算出來。2023/2/1226.3.1依賴圖所謂依賴圖其實就是一個有向圖，用于描述分析樹中節點的屬性和屬性間的相互依賴關系，稱為分析樹的依賴圖。每個屬性對應依賴圖中的一個節點，如果屬性b依賴于屬性c，則從屬性c的節點有一條有向邊指向屬性b的節點。屬性間的依賴關系是根據相應的語義規則確定的。2023/2/123依賴圖的構造方法for分析樹的每個節點ndo for與節點n對應的文法符號的每個屬性ado

在依賴圖中為a構造一個節點；

for分析樹的每個節點ndo for節點n所用產生式對應的每條語義規則b:=f(c1,c2,…,ck)do fori:=1tokdo

構造一條從節點ci到節點b的有向邊；2023/2/124例6.3圖6.3中注釋分析樹的依賴圖2023/2/1256.3.2屬性的計算順序拓撲排序一個無環有向圖的拓撲排序是圖中結點的任何順序m1，m2，…，mk，使得邊必須是從序列中前面的結點指向后面的結點，也就是說，如果mi→mj是mi到mj的一條邊,那么在序列中mi必須出現在mj的前面。若依賴圖中無環，則存在一個拓撲排序，它就是屬性值的計算順序。例6.4圖6.4的拓撲排序為：

1，2，3，4，5，6，7，8，9，10，11，12，132023/2/1266.3.2屬性的計算順序根據拓撲排序得到的翻譯程序a4:=4a5:=a4a6:=8a7:=a5×a6a8:=9a9:=a7×a8a10:=a9a11:=a10a12:=a11a13:=a12上述屬性計算方法又稱為分析樹法，這種方法在編譯時需要顯式地構造分析樹和依賴圖，所以編譯的時空效率比較低，而且如果分析樹的依賴圖中存在回路的話，這種方法將會失效。這種方法的優點是可以多次遍歷分析樹，從而使得屬性的計算不依賴于所采用的語法分析方法以及屬性間嚴格的依賴關系。2023/2/127計算語義規則的其他方法基于規則的方法在構造編譯器時，用手工或專門的工具來分析語義規則,確定屬性值的計算順序。忽略語義規則的方法在分析過程中翻譯，那么計算順序由分析方法來確定而表面上與語義規則無關。這種方法限制了能被實現的語法制導定義的種類。

這兩種方法都不必顯式構造依賴圖，因此時空效率更高。2023/2/128S-屬性定義定義6.1只含綜合屬性的語法制導定義稱為S-屬性定義，又稱為S-屬性文法。如果某個語法制導定義是S-屬性定義，則可以按照自下而上的順序來計算分析樹中節點的屬性。一種簡單的屬性計算方法是對分析樹進行后根遍歷，并在最后一次遍歷節點N時計算與節點N相關聯的屬性。postorder(N){ forN的每個子節點M(從左到右)postorder(M);

計算與節點N相關聯的屬性; }2023/2/129L-屬性定義定義6.2一個語法制導定義被稱為L-屬性定義，當且僅當它的每個屬性或者是綜合屬性，或者是滿足如下條件的繼承屬性：設有產生式A→X1X2…Xn，其右部符號Xi(1≤i≤n)的繼承屬性只依賴于下列屬性：⑴A的繼承屬性；⑵產生式中Xi左邊的符號X1、X2、…、Xi-1的綜合屬性或繼承屬性；⑶Xi本身的綜合屬性或繼承屬性，但前提是Xi的屬性不能在依賴圖中形成回路。L-屬性定義又稱為L-屬性文法。2023/2/130表6.3

L-屬性定義示例產生式語義規則T→FT

'T

'.inh:=F.valT.val:=T

'.syn

T

'→*FT1'T1'.inh:=T

'.inh×F.valT

'.syn:=T1'.synT

'→εT

'.syn:=T

'.inhF→digitF.val:=digit.lexval2023/2/131例6.7不是L-屬性定義的語法制導定義產生式語義規則A→BCA.syn:=B.bB.inh:=f(C.c,A.syn)語義規則B.inh:=f(C.c,A.syn)定義了一個繼承屬性，所以整個語法制導定義就不是S-屬性定義了。此外，雖然這條語義規則是合法的屬性定義規則，但不滿足L-屬性定義的要求。這是因為：屬性B.inh的定義中用到了屬性C.c，而C在產生式的右部處在B的右邊。雖然在L-屬性定義中可以使用兄弟節點的屬性來定義某個屬性，但這些兄弟節點必須是左兄弟節點才行。因此，該語法制導定義也不是L-屬性定義。2023/2/132L-屬性定義中的屬性計算visit(N){forN的每個子節點M(從左到右){

計算節點M的繼承屬性;visit(M); }

計算節點N的綜合屬性;};2023/2/133抽象語法樹是表示程序層次結構的樹，它把分析樹中對語義無關緊要的成分去掉，是分析樹的抽象形式，也稱作語法結構樹，或結構樹。語法樹是常用的一種中間表示形式。把語法分析和翻譯分開。語法分析過程中完成翻譯有許多優點，但也有一些不足：

1.適于語法分析的文法可能不完全反映語言成分的自然層次結構；

2.由于語法分析方法的限制，對分析樹結點的訪問順序和翻譯需要的訪問順序不一致。

6.3.5屬性計算示例—抽象語法樹的構造

2023/2/134

產生式S→ifBthenS1elseS2的語法樹

if-then-else

／|＼

B

S1

S2

賦值語句的語法樹

assignment

variable

expression

在語法樹中，運算符號和關鍵字都不在葉結點，而是在內部結點中出現。語法樹2023/2/135構造表達式的語法樹使用的函數

1.mknode(op,left,right)建立一個標記為op的運算符結點，兩個域left和right分別是指向左右運算對象的指針。

2．mkleaf(id,entry)建立一個標記為id的標識符結點，其域entry是指向該標識符在符號表中相應表項的指針。

3.mkleaf(num,val)建立一個標記為num的數結點，其域val用于保存該數的值。構造表達式的語法樹2023/2/136構造表達式語法樹的語法制導定義產生式語義規則⑴T→T1*FT.node:=mknode('*',T1.node,F.node)⑵T→T1/FT.node:=mknode('/',T1.node,F.node)⑶T→FT.node:=F.node⑷F→(E)F.node:=E.node⑸F→idF.node:=mkleaf(id,id.entry)⑹F→numF.node:=mkleaf(num,num.val)2023/2/137圖6.53*x/y的語法樹的構造2023/2/1383*x/y的抽象語法樹的構造步驟

p1:=mkleaf(num,3)；

p2:=mkleaf(id,entry-x)；

p3:=mknode('*',p1,p2)；

p4:=mkleaf(id,entry-y)；

p5:=mknode('/',p3,p4)；

圖6.5的語法樹是自底向上構造的，對于那些為便于進行自頂向下分析而設計的文法來說，使用同樣的步驟照樣可以建立圖6.5中的抽象語法樹。當然，分析樹的結構可能大不相同，而且可能需要引入繼承屬性來傳遞語義信息。2023/2/139在自頂向下分析過程中構造語法樹產生式語義規則⑴T→FT

'T.node:=T

'.synT

'.inh:=F.node⑵T

'→*FT1'T1'.inh:=mknode('*',T

'.inh,F.node)T

'.syn:=T1'.syn⑶T

'→/FT1'T1'.inh:=mknode('/',T

'.inh,F.node)T

'.syn:=T1'.syn⑷T

'→ε

T

'.syn:=T

'.inh⑸F→(E)F.node:=E.node⑹F→idF.node:=mkleaf(id,id.entry)⑺F→numF.node:=mkleaf(num,num.val)2023/2/140根據表6.6的語法制導定義構造的語法樹2023/2/141

定義

翻譯模式是語法制導定義的一種便于實現的書寫形式。其中屬性與文法符號相關聯，語義規則或語義動作用花括號｛｝括起來，并可被插入到產生式右部的任何合適的位置上。這是一種語法分析和語義動作交錯的表示法，它表達在按深度優先遍歷分析樹的過程中何時執行語義動作。

翻譯模式給出了使用語義規則進行計算的順序。可看成是分析過程中翻譯的注釋。6.4翻譯模式2023/2/142

將中綴表達式翻譯成后綴表達式：

E→TR

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

T→num{print(num.val)}

把語義動作看成終結符號，輸入3+4-5,其分析樹如圖6.8，當按深度優先遍歷它，執行遍歷中訪問的語義動作，將輸出

34+5-它是輸入表達式3+4-5的后綴式。例6.10一個簡單的翻譯模式2023/2/143圖6.83+4-5的帶語義動作的分析樹2023/2/144

前提——語法制導定義是L-屬性定義

保證語義動作不會引用還沒計算出來的屬性值1.只需要綜合屬性的情況為每一個語義規則建立一個包含賦值的動作，并把該動作放在相應的產生式右部的末尾。例如：TT1*F

Tval:=T1val*Fval

轉換成：

TT1*F{Tval:=T1val*Fval}翻譯模式的設計

——根據語法制導定義2023/2/1452.

既有綜合屬性又有繼承屬性產生式右邊的符號的繼承屬性必須在這個符號以前的動作中計算出來。一個動作不能引用這個動作右邊符號的綜合屬性。產生式左邊非終結符號的綜合屬性只有在它所引用的所有屬性都計算出來以后才能計算。計算這種屬性的動作通?？煞旁诋a生式右端的末尾。翻譯模式的設計

——根據語法制導定義2023/2/146

下面的翻譯模式不滿足要求：

SA1A2{A1in:=1;A2in:=2}

Aa{print(Ain)}/*A.in尚無定義*/例6.11從L-屬性制導定義建立一個滿足上面要求的翻譯模式。使用文法產生的語言是數學排版語言EQN

Esub1val編排結果2023/2/147

B表示盒子⑴B→B1B2代表兩個相鄰盒子的并列，且B1位于B2的左邊。⑵B→B1subB2代表盒子B1后隨下標盒子B2，下標盒子B2以較小的字體和較低的位置出現。⑶B→(B1)代表一個由括號括起來的盒子B1，主要是為了對多個盒子或下標進行分組。在EQN中，使用花括號進行分組，此處使用圓括號是為了避免跟語義動作外面的花括號產生沖突。⑷B→text代表文本字符串，即任意字符組成的串。該文法是二義性的文法，將“并列”和“下標”看成是左結合的，并令“下標”的優先級高于“并列”的話，則可以對該文法所描述的語言進行自底向上的語法分析。2023/2/148屬性設置⑴pointsize用于表示盒子中文本的尺寸(以點來計算，也就是字號)。如果標準盒子的尺寸為p，則下標盒子的尺寸為0.7×p。屬性B.ps表示盒子B的尺寸，該屬性是繼承屬性。⑵每個盒子都有一個基線(baseline)，用來表示每個文本底部的垂直位置。⑶height用來表示從盒子的頂部到基線的距離。屬性B.ht表示盒子B的高度height，該屬性是綜合屬性。⑷depth用來表示從基線到盒子底部的距離。用屬性B.dp表示盒子B的深度depth，該屬性也是綜合屬性。2023/2/149表6.7對盒子進行排版的語法制導定義產生式語義規則⑴S→BB.ps:=10S.ht:=B.htS.dp:=B.dp⑵B→B1B2B1.ps:=B.psB2.ps:=B.psB.ht:=max(B1.ht,B2.ht)B.dp:=max(B1.dp,B2.dp)⑶B→B1subB2B1.ps:=B.psB2.ps:=0.7×B.psB.ht:=max(B1.ht,B2.ht-0.25×B.ps)B.dp:=max(B1.dp,B2.dp+0.25×B.ps)⑷B→(B1)B1.ps:=B.psB.ht:=B1.htB.dp:=B1.dp⑸B→textB.ht:=getheight(B.ps,text.lexval)B.dp:=getdepth(B.ps,text.lexval)2023/2/150S→{B.ps:=10}B{S.ht:=B.ht;S.dp:=B.dp}B→{B1.ps:=B.ps}B1{B2.ps:=B.ps}B2{B.ht:=max(B1.ht,B2.ht)}B→{B1.ps:=B.ps}B1sub{B2.ps:=0.7×B.ps}B2{B.ht:=max(B1.ht,B2.ht-0.25×B.ps);B.dp:=max(B1.dp,B2.dp+0.25×B.ps);}B→({B1.ps:=B.ps}B1){B.ht:=B1.ht;B.dp:=B1.dp;}B→text{B.ht:=getheight(B.ps,text.lexval);B.dp:=getdepth(B.ps,text.lexval)}從表6.7構造的翻譯模式2023/2/151T→F{T'.inh:=F.node}T'{T.node:=T'.syn}T'→*F{T1'.inh:=mknode('*',T'.inh,F.node)}

T1'{T'.syn:=T1'.syn}T'→/F{T1'.inh:=mknode('/',T'.inh,F.node)}

T1'{T'.syn:=T1'.syn}T'→ε{T'.syn:=T'.inh}F→(E){F.node:=E.node}F→id{F.node:=mkleaf(id,id.entry)}F→num{F.node:=mkleaf(num,num.val)}從表6.6構造的翻譯模式2023/2/152在分析棧中使用一個附加的域來存放綜合屬性值。下圖為一個帶有綜合屬性值域的分析棧：stackval...XX.xY...Y.y......ZZ.ztop6.4.2S-屬性定義的自底向上計算2023/2/153A

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

b是A的綜合屬性，ci(1

ik)是中符號的屬性。綜合屬性的值是在自底向上的分析過程中，每次歸約之前進行計算的。

AXYZ

Aa:=f(Xx,Yy,Zz)AaXx

Yy

Zz2023/2/154topstackval......XX.xYY.yZZ.zstackval......AA.atop實現時，將定義式A.a:=f(X.x,Y.y,Z.z)(抽象)變成stack[ntop].val:=f(stack[top-2].val,stack[top-1].val,stack[top].val)(具體可執行代碼)。在執行代碼段之前執行：

ntop:=top-r+1——r是句柄的長度執行代碼段后執行：top:=ntop;2023/2/155例6.14用LR分析器實現臺式計算器——與表6.2對比L→En{print(stack[top-1].val);top:=top-1;}E→E1+T{stack[top-2].val:=stack[top-2].val+stack[top].val;

top:=top-2;}E→TT→T1*F{stack[top-2].val:=stack[top-2].val×stack[top].val;

top:=top-2;}T→FF→(E){stack[top-2].val:=stack[top-1].val;top:=top-2;}F→digit2023/2/156表6.8翻譯輸入6+7*8n上的移動序列輸入

state

val

使用的產生式6+7*8n--+7*8n66+7*8nF6Fdigit

+7*8nT6TF

+7*8nE6ET

7*8nE+6+*8nE+76+72023/2/157*8nE+F6+7Fdigit*8nE+T6+7TF8nE+T*6+7*nE+T*86+7*8nE+T*F6+7*8FdigitnE+T6+56TT*FnE62EE+TEn62L62LEn2023/2/158

采用自底向上分析，例如LR分析，首先給出S-屬性定義，然后，把S-屬性定義變成可執行的代碼段，這就構成了翻譯程序。象一座建筑，語法分析是構架，歸約處有一個“掛鉤”，語義分析和翻譯的代碼段（語義子程序）就掛在這個鉤子上。這樣，隨著語法分析的進行，歸約前調用相應的語義子程序,完成翻譯的任務。S-屬性定義小結2023/2/159

用翻譯模式構造自頂向下的翻譯。1.從翻譯模式中消除左遞歸

對于一個翻譯模式，若采用自頂向下分析，必須消除左遞歸和提取左公因子，在改寫基礎文法時考慮屬性值的計算。對于自頂向下語法分析，假設語義動作是在與之處于同一位置的文法非終結符被展開時執行的，而且不考慮繼承屬性的處理（很簡單）。6.4.3L-屬性定義的自頂向下翻譯2023/2/160

例6.15考慮如下將中綴表達式翻譯為后綴表達式的翻譯模式中的兩個產生式：

E→E1+T{print(‘+’);} E→T E→TR R→+T{print(‘+’);}R R→ε

只有簡單語義動作時的左遞歸消除2023/2/161

設有如下左遞歸翻譯模式：

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

A→X

｛A.a:=f(X.x)}假設每個非終結符都有一個綜合屬性，用相應的小寫字母表示，g和f是任意函數。

消除左遞歸后，文法轉換成

A→XR

R→YR|εS-屬性定義的左遞歸消除2023/2/162

再考慮語義動作，翻譯模式變為：

A→X

｛Ri:=f(Xx)}

R

｛Aa:=Rs}

R→Y

｛R1i:=g(Ri,Yy)}

R1

｛Rs:=R1s}

R→ε

｛Rs:=Ri}經過轉換的翻譯模式使用R的繼承屬性i和綜合屬性s。轉換前后的結果是一樣的,為什么？S-屬性定義的左遞歸消除A→A1Y{A.a:=g(A1.a,Y.y)}

A→X{A.a:=f(X.x)}引入繼承屬性R.i來收集應用函數g的計算結果。其初始值為A.a:=f(X.x）引入綜合屬性R.s在R結束生成Y時復制R.i的值。2023/2/163Aa=g(g(f(Xx),Y1y),Y2y)Aa=g(f(Xx),Y1y)Aa=f(Xx)Y2Y1X(a)輸入：XY1Y22023/2/164ARi=f(Xx)Ri=g(f(Xx),Y1y)Ri=g(g(f(Xx),Y1y),Y2y)εY2Y1X(b)2023/2/165L-屬性定義的遞歸下降翻譯器的構造：1．對每個非終結符A構造一個函數A，將非終結符A的各個繼承屬性當作函數A的形式參數，而將非終結符A的綜合屬性集當作函數A的返回值，為了便于討論，假設每個非終結符只具有一個綜合屬性。2．在函數A的過程體中，不僅要進行語法分析，而且要處理相應的語義屬性。函數A的代碼首先根據當前輸入確定用哪個產生式展開A，然后按照3中所給的方法對各產生式進行編碼。2.L-屬性定義的遞歸下降翻譯法2023/2/1663．與每個產生式對應的程序代碼的工作過程為：按照從左到右的次序，依次對產生式右部的記號、非終結符和語義動作執行如下的動作：1)對帶有綜合屬性x的符號X，將x的值保存在X.x中，并生成一個函數調用來匹配X，然后繼續讀入下一個輸入符號；2)對非終結符B，生成一個右部帶有函數調用的賦值語句c:=B(b1,b2,…,bk)，其中，b1,b2,…,bk是代表B的繼承屬性的變量，c是代表B的綜合屬性的變量；3)對于語義動作，將其代碼復制到語法分析器中，并將對屬性的引用改為對相應變量的引用。2.L-屬性定義的遞歸下降翻譯法2023/2/167例6.16

functionT:↑syntax_tree_node;functionT'(inh:↑syntax_tree_node):↑syntax_tree_node;functionF:↑syntax_tree_node;functionT:↑syntax_tree_node; varnode,syn:↑syntax_tree_node; begin node:=F; syn:=T'(node); returnsynend;2023/2/168functionT'(inh:↑syntax_tree_node):↑syntax_tree_node;varnode,inh1,syn1:↑syntax_tree_node;oplexeme:char;begin iflookahead=‘*’thenbegin /*匹配產生式T'→*FT'*/

oplexeme:=lexval;

match(‘*’);node:=F;

inh1:=mknode(‘*’,inh,node);

syn1:=T'(inh1);syn:=syn1endelseiflookahead=‘/’thenbegin /*匹配產生式T'→/FT'*/

oplexeme:=lexval;

match(‘/’);node:=F;

inh1:=mknode(‘/’,inh,node);syn1:=T'(inh1);syn:=syn1endelsesyn:=inh;returnsynend;

2023/2/169functionF:↑syntax_tree_node;varnode:↑syntax_tree_node;beginiflookahead=‘(’thenbegin /*匹配產生式F→(E)*/match(‘(‘);node:=E;match(‘)’)endelseiflookahead=idthenbegin /*匹配產生式F→id*/match(id);node:=mkleaf(id,id.entry)endelseiflookahead=numthenbegin /*匹配產生式F→num*/match(num);node:=mkleaf(num,num.val)endreturnnodeend;

2023/2/1703.L-屬性定義的LL(1)翻譯法預先在源文法中的相應位置上嵌入語義動作符號(每個對應一個語義子程序)，用于提示語法分析程序，當分析到達這些位置時應調用相應的語義子程序。帶有語義動作符號的文法又叫翻譯文法。2023/2/1713.L-屬性定義的LL(1)翻譯法與遞歸子程序法的區別與聯系都是在掃描過程中進行產生式的推導，同時在適當的地方加入語義動作。遞歸子程序法將語義動作溶入分析程序；LL(1)分析法則由語義子程序完成相應的翻譯。遞歸子程序法隱式地使用語義棧；LL(1)分析法則用顯式的語義棧（程序自身控制對棧的操作）。注：語義與語法棧不同步。2023/2/172例6.17對于圖6.14的翻譯模式，設置兩個棧，一個是分析棧，一個是語義棧。 ⑴T→F{e1}T'{e2} ⑵T'→*F{e3}T1'{e4} ⑶T'→/F{e5}T1'{e4} ⑷T'→ε{e6} ⑸F→(E){e7} ⑹F→id{e8} ⑺F→num{e9}2023/2/173-#語義棧語法棧3*x/y#輸入串例6.17對輸入串3*x/y的翻譯語法分析動作和語義操作1.初始化T2023/2/174-#語義棧語法棧3*x/y#輸入串例6.17對輸入串3*x/y的翻譯語法分析動作和語義操作2.選產生式①的右部進棧{e2}{e1}FT'2023/2/175-#語義棧語法棧3*x/y#輸入串例6.17對輸入串3*x/y的翻譯語法分析動作和語義操作3.選擇產生式⑺,num3不進棧，調用{e9}，調用{e9}后，葉結點F.node被壓入語義棧{e2}{e1}{e9}T'F.node2023/2/176-#語義棧語法棧3*x/y#輸入串例6.17對輸入串3*x/y的翻譯語法分析動作和語義操作4.執行動作{e1}，F.node出棧，T'.inh被壓入棧

{e2}{e1}T'T'.inh2023/2/177-#語義棧語法棧3*x/y#輸入串例6.17對輸入串3*x/y的翻譯語法分析動作和語義操作5.選擇產生式⑶,*不進棧{e2}T'{e5}{e4}FT'.inh2023/2/178-#語義棧語法棧3*x/y#輸入串例6.17對輸入串3*x/y的翻譯語法分析動作和語義操作6.選擇產生式⑹,idx不進棧，調用{e8}，調用{e8}后，葉結點F.node被壓入語義棧

{e2}T'{e5}{e4}T'.inhF.node{e8}2023/2/179-#語義棧語法棧3*x/y#輸入串例6.17對輸入串3*x/y的翻譯語法分析動作和語義操作7.執行動作{e5}，F.node和T'.inh均被彈出棧，新的T'.inh被壓入棧

T'.inh{e2}T'{e5}{e4}2023/2/180-#語義棧語法棧3*x/y#輸入串例6.17對輸入串3*x/y的翻譯語法分析動作和語義操作8.選擇產生式⑵,/不進棧

T'.inh{e2}{e4}T'{e4}{e3}F2023/2/181-#語義棧語法棧3*x/y#輸入串例6.17對輸入串3*x/y的翻譯語法分析動作和語義操作9.選擇產生式⑹,idy不進棧，調用{e8}，調用{e8}后，葉結點F.node被壓入語義棧

T'.inhF.node{e2}{e4}T'{e4}{e3}{e8}2023/2/182-#語義棧語法棧3*x/y#輸入串例6.17對輸入串3*x/y的翻譯語法分析動作和語義操作10.執行動作{e3}，F.node和T'.inh均被彈出棧，新的T'.inh被壓入棧

T'.inh{e2}{e4}T'{e4}{e3}2023/2/183-#語義棧語法棧3*x/y#輸入串例6.17對輸入串3*x/y的翻譯語法分析動作和語義操作11.選擇產生式⑷，T'.inh被彈出棧，T'.syn被壓入棧

{e2}{e4}{e6}{e4}T'.inh2023/2/184-#語義棧語法棧3*x/y#輸入串例6.17對輸入串3*x/y的翻譯語法分析動作和語義操作12.依次執行動作{e6},{e4},{e4},{e2},最終語義棧中只有T.node,代表3*x/y的語法樹的根結點

T.node2023/2/1856.4.4L-屬性定義的自底向上翻譯在自底向上分析的框架中實現L屬性定義的方法它能實現任何基于LL(1)文法的L屬性定義。也能實現許多（但不是所有的）基于LR(1)文法的L屬性定義。2023/2/1866.4.4L-屬性定義的自底向上翻譯(續)⑴首先像6.4.1所介紹的那樣構造翻譯模式，它將計算繼承屬性的動作嵌入在非終結符的前面，而將計算綜合屬性的動作放在產生式的末尾。⑵在每個嵌入動作處引入一個標記性非終結符(markernonterminals)。不同位置所對應的標記是不同的，每個標記性非終結符M都有一個形如M→ε的產生式。2023/2/1876.4.4L-屬性定義的自底向上翻譯(續)⑶如果標記性非終結符M取代了某個產生式A→α{a}β中的動作a，則按如下方式將a修改為a'，并將動作{a'}放在產生式M→ε的末尾。①為M設置繼承屬性來復制動作a所需要的A或α中符號的繼承屬性； ②以與動作a相同的方式計算屬性，只不過要將這些屬性置為M的綜合屬性。2023/2/1886.4.4L-屬性定義的自底向上翻譯(續)與M→ε相關聯的語義動作可能需要用到沒出現在該產生式中的文法符號的屬性。不過，由于要在LR分析棧中實現所有的語義動作，所以在分析棧中M下面的某個已知位置總能找到所需的屬性。例如，假設在某個LL(1)文法中有一個形如A→BC的產生式，B的繼承屬性B.inh是從A的繼承屬性A.inh按照公式B.inh:=f(A.inh)來計算的，亦即翻譯模式可能包含如下片斷：

A→{B.inh:=f(A.inh);}BC2023/2/1896.4.4L-屬性定義的自底向上翻譯(續)根據上面的論述，為了在自底向上的分析過程中計算B.inh:=f(A.inh)，需要引入一個標記性非終結符M，并為其設置一個繼承屬性M.inh用來復制A的繼承屬性，而且還要用M的綜合屬性M.syn代替B.inh，于是，該翻譯模式片段將被修改為如下形式：

A→MBC M→ε{M.inh:=A.inh;M.syn:=f(M.inh)}2023/2/1906.4.4L-屬性定義的自底向上翻譯(續)注意，執行M的語義規則時，A.inh是不可用的，但實際上，實現時會把每個非終結符X的繼承屬性都放在堆棧中緊靠在X將被歸約出來的位置之下。于是，當將ε歸約為M時，A.inh恰好就在它的下面。隨M保存在棧中的M.syn的值，也就是B.inh的值，亦將被放在緊靠在B將被歸約出來的位置之下，需要的時候同樣是可用的。2023/2/1916.4.4L-屬性定義的自底向上翻譯(續)下面的化簡可以減少標記性非終結符的個數，其中第2條還可以避免左遞歸文法中的分析沖突：⑴如果Xj沒有繼承屬性，則不需要使用標記Mj。當然，如果省略了Mj，屬性在棧中的預期位置就會改變，但是分析器可以很容易地適應這種變化。⑵如果X1.inh存在，但它是由復制規則X1.inh:=A.inh計算的，此時可以省略M1。因為A.inh存放在棧中緊挨在X1下面的地方，所以該值也可同時作為X1.inh的值。2023/2/1926.4.4L-屬性定義的自底向上翻譯(續)例6.18數學排版語言EQN

S

{B.ps:=10} B {S.ht:=B.ht;S.dp:=B.dp}

B {B1.ps:=B.ps}

B1 {B2.ps:=B.ps}

B2 {B.ht:=max(B1.ht,B2.ht)}

B {B1.ps:=B.ps}

B1 sub {B2.ps:=0.7B.ps} B2 {B.ht:=disp(B1.ht,B2.ht)

B.dp:=max(B1.dp,B2.dp)