編譯原理-第6章-語法制導(dǎo)翻譯與屬性文法

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

難點(diǎn)：屬性的意義，對綜合屬性，繼承屬性，固有屬性的理解，屬性計(jì)算，怎么通過屬性來表達(dá)翻譯。

2023/2/12第6章

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

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

E.val:=E1.val+E2.val語法結(jié)構(gòu)具有規(guī)定的語義問題：如何根據(jù)被識別出的語法成分進(jìn)行語義處理？亦即怎樣將屬性值的計(jì)算及翻譯工作同產(chǎn)生式相關(guān)聯(lián)？2023/2/110典型處理方法一語法制導(dǎo)定義通過將屬性與文法符號關(guān)聯(lián)、將語義規(guī)則與產(chǎn)生式關(guān)聯(lián)來描述語言結(jié)構(gòu)的翻譯方案對應(yīng)每一個(gè)產(chǎn)生式編寫一個(gè)語義子程序，當(dāng)一個(gè)產(chǎn)生式獲得匹配時(shí)，就調(diào)用相應(yīng)的語義子程序來實(shí)現(xiàn)語義檢查與翻譯E→E1+T {E.val:=E1.val+T.val}T→T1*F {T.val:=T1.val*F.val}F→digit {F.val:=digit.lexval}適宜在完成歸約的時(shí)候進(jìn)行2023/2/111典型處理方法二翻譯模式通過將屬性與文法符號關(guān)聯(lián)，并將語義規(guī)則插入到產(chǎn)生式的右部來描述語言結(jié)構(gòu)的翻譯方案在產(chǎn)生式的右部的適當(dāng)位置，插入相應(yīng)的語義動作，按照分析的進(jìn)程，執(zhí)行遇到的語義動作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)}

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

b：=f（c1，c2，…，ck），f是一個(gè)函數(shù)，而且或者

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

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

臺式計(jì)算器的語法制導(dǎo)定義產(chǎn)生式語義規(guī)則LEn

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

Eval:=E1val+TvalET

Eval:=TvalTT1*F

Tval:=T1val+FvalTF

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

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

F→digit2023/2/118表6.3

為適于自頂向下分析的文法設(shè)計(jì)的語法制導(dǎo)定義產(chǎn)生式語義規(guī)則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中語法制導(dǎo)定義對應(yīng)的翻譯模式如果對4*8*9進(jìn)行自頂向下的語法制導(dǎo)翻譯，則val的值的計(jì)算順序?yàn)棰泞脾洽娶散盛刷挞廷微息孝迅鶕?jù)上述對val值的計(jì)算順序，可以將表6.3中的語法制導(dǎo)定義轉(zhuǎn)換成如下的翻譯模式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屬性計(jì)算語義規(guī)則定義了屬性之間的依賴關(guān)系，這種依賴關(guān)系將影響屬性的計(jì)算順序?yàn)榱舜_定分析樹中各個(gè)屬性的計(jì)算順序，我們可以用圖來表示屬性之間的依賴關(guān)系，并將其稱為依賴圖如果依賴圖中沒有回路，則利用它可以很方便地求出屬性的計(jì)算順序。注釋分析樹只是給出了屬性的值，而依賴圖則可以幫助我們確定如何將這些屬性值計(jì)算出來。2023/2/1226.3.1依賴圖所謂依賴圖其實(shí)就是一個(gè)有向圖，用于描述分析樹中節(jié)點(diǎn)的屬性和屬性間的相互依賴關(guān)系，稱為分析樹的依賴圖。每個(gè)屬性對應(yīng)依賴圖中的一個(gè)節(jié)點(diǎn)，如果屬性b依賴于屬性c，則從屬性c的節(jié)點(diǎn)有一條有向邊指向?qū)傩詁的節(jié)點(diǎn)。屬性間的依賴關(guān)系是根據(jù)相應(yīng)的語義規(guī)則確定的。2023/2/123依賴圖的構(gòu)造方法for分析樹的每個(gè)節(jié)點(diǎn)ndo for與節(jié)點(diǎn)n對應(yīng)的文法符號的每個(gè)屬性ado

在依賴圖中為a構(gòu)造一個(gè)節(jié)點(diǎn)；

for分析樹的每個(gè)節(jié)點(diǎn)ndo for節(jié)點(diǎn)n所用產(chǎn)生式對應(yīng)的每條語義規(guī)則b:=f(c1,c2,…,ck)do fori:=1tokdo

構(gòu)造一條從節(jié)點(diǎn)ci到節(jié)點(diǎn)b的有向邊；2023/2/124例6.3圖6.3中注釋分析樹的依賴圖2023/2/1256.3.2屬性的計(jì)算順序拓?fù)渑判蛞粋€(gè)無環(huán)有向圖的拓?fù)渑判蚴菆D中結(jié)點(diǎn)的任何順序m1，m2，…，mk，使得邊必須是從序列中前面的結(jié)點(diǎn)指向后面的結(jié)點(diǎn)，也就是說，如果mi→mj是mi到mj的一條邊,那么在序列中mi必須出現(xiàn)在mj的前面。若依賴圖中無環(huán)，則存在一個(gè)拓?fù)渑判?，它就是屬性值的?jì)算順序。例6.4圖6.4的拓?fù)渑判驗(yàn)椋?/p>

1，2，3，4，5，6，7，8，9，10，11，12，132023/2/1266.3.2屬性的計(jì)算順序根據(jù)拓?fù)渑判虻玫降姆g程序a4:=4a5:=a4a6:=8a7:=a5×a6a8:=9a9:=a7×a8a10:=a9a11:=a10a12:=a11a13:=a12上述屬性計(jì)算方法又稱為分析樹法，這種方法在編譯時(shí)需要顯式地構(gòu)造分析樹和依賴圖，所以編譯的時(shí)空效率比較低，而且如果分析樹的依賴圖中存在回路的話，這種方法將會失效。這種方法的優(yōu)點(diǎn)是可以多次遍歷分析樹，從而使得屬性的計(jì)算不依賴于所采用的語法分析方法以及屬性間嚴(yán)格的依賴關(guān)系。2023/2/127計(jì)算語義規(guī)則的其他方法基于規(guī)則的方法在構(gòu)造編譯器時(shí)，用手工或?qū)ｉT的工具來分析語義規(guī)則,確定屬性值的計(jì)算順序。忽略語義規(guī)則的方法在分析過程中翻譯，那么計(jì)算順序由分析方法來確定而表面上與語義規(guī)則無關(guān)。這種方法限制了能被實(shí)現(xiàn)的語法制導(dǎo)定義的種類。

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

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

L-屬性定義示例產(chǎn)生式語義規(guī)則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-屬性定義的語法制導(dǎo)定義產(chǎn)生式語義規(guī)則A→BCA.syn:=B.bB.inh:=f(C.c,A.syn)語義規(guī)則B.inh:=f(C.c,A.syn)定義了一個(gè)繼承屬性，所以整個(gè)語法制導(dǎo)定義就不是S-屬性定義了。此外，雖然這條語義規(guī)則是合法的屬性定義規(guī)則，但不滿足L-屬性定義的要求。這是因?yàn)椋簩傩訠.inh的定義中用到了屬性C.c，而C在產(chǎn)生式的右部處在B的右邊。雖然在L-屬性定義中可以使用兄弟節(jié)點(diǎn)的屬性來定義某個(gè)屬性，但這些兄弟節(jié)點(diǎn)必須是左兄弟節(jié)點(diǎn)才行。因此，該語法制導(dǎo)定義也不是L-屬性定義。2023/2/132L-屬性定義中的屬性計(jì)算visit(N){forN的每個(gè)子節(jié)點(diǎn)M(從左到右){

計(jì)算節(jié)點(diǎn)M的繼承屬性;visit(M); }

計(jì)算節(jié)點(diǎn)N的綜合屬性;};2023/2/133抽象語法樹是表示程序?qū)哟谓Y(jié)構(gòu)的樹，它把分析樹中對語義無關(guān)緊要的成分去掉，是分析樹的抽象形式，也稱作語法結(jié)構(gòu)樹，或結(jié)構(gòu)樹。語法樹是常用的一種中間表示形式。把語法分析和翻譯分開。語法分析過程中完成翻譯有許多優(yōu)點(diǎn)，但也有一些不足：

1.適于語法分析的文法可能不完全反映語言成分的自然層次結(jié)構(gòu)；

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

6.3.5屬性計(jì)算示例—抽象語法樹的構(gòu)造

2023/2/134

產(chǎn)生式S→ifBthenS1elseS2的語法樹

if-then-else

／|＼

B

S1

S2

賦值語句的語法樹

assignment

variable

expression

在語法樹中，運(yùn)算符號和關(guān)鍵字都不在葉結(jié)點(diǎn)，而是在內(nèi)部結(jié)點(diǎn)中出現(xiàn)。語法樹2023/2/135構(gòu)造表達(dá)式的語法樹使用的函數(shù)

1.mknode(op,left,right)建立一個(gè)標(biāo)記為op的運(yùn)算符結(jié)點(diǎn)，兩個(gè)域left和right分別是指向左右運(yùn)算對象的指針。

2．mkleaf(id,entry)建立一個(gè)標(biāo)記為id的標(biāo)識符結(jié)點(diǎn)，其域entry是指向該標(biāo)識符在符號表中相應(yīng)表項(xiàng)的指針。

3.mkleaf(num,val)建立一個(gè)標(biāo)記為num的數(shù)結(jié)點(diǎn)，其域val用于保存該數(shù)的值。構(gòu)造表達(dá)式的語法樹2023/2/136構(gòu)造表達(dá)式語法樹的語法制導(dǎo)定義產(chǎn)生式語義規(guī)則⑴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的語法樹的構(gòu)造2023/2/1383*x/y的抽象語法樹的構(gòu)造步驟

p1:=mkleaf(num,3)；

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

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

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

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

圖6.5的語法樹是自底向上構(gòu)造的，對于那些為便于進(jìn)行自頂向下分析而設(shè)計(jì)的文法來說，使用同樣的步驟照樣可以建立圖6.5中的抽象語法樹。當(dāng)然，分析樹的結(jié)構(gòu)可能大不相同，而且可能需要引入繼承屬性來傳遞語義信息。2023/2/139在自頂向下分析過程中構(gòu)造語法樹產(chǎn)生式語義規(guī)則⑴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根據(jù)表6.6的語法制導(dǎo)定義構(gòu)造的語法樹2023/2/141

定義

翻譯模式是語法制導(dǎo)定義的一種便于實(shí)現(xiàn)的書寫形式。其中屬性與文法符號相關(guān)聯(lián)，語義規(guī)則或語義動作用花括號｛｝括起來，并可被插入到產(chǎn)生式右部的任何合適的位置上。這是一種語法分析和語義動作交錯(cuò)的表示法，它表達(dá)在按深度優(yōu)先遍歷分析樹的過程中何時(shí)執(zhí)行語義動作。

翻譯模式給出了使用語義規(guī)則進(jìn)行計(jì)算的順序?？煽闯墒欠治鲞^程中翻譯的注釋。6.4翻譯模式2023/2/142

將中綴表達(dá)式翻譯成后綴表達(dá)式：

E→TR

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

T→num{print(num.val)}

把語義動作看成終結(jié)符號，輸入3+4-5,其分析樹如圖6.8，當(dāng)按深度優(yōu)先遍歷它，執(zhí)行遍歷中訪問的語義動作，將輸出

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

前提——語法制導(dǎo)定義是L-屬性定義

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

Tval:=T1val*Fval

轉(zhuǎn)換成：

TT1*F{Tval:=T1val*Fval}翻譯模式的設(shè)計(jì)

——根據(jù)語法制導(dǎo)定義2023/2/1452.

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

——根據(jù)語法制導(dǎo)定義2023/2/146

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

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

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

Esub1val編排結(jié)果2023/2/147

B表示盒子⑴B→B1B2代表兩個(gè)相鄰盒子的并列，且B1位于B2的左邊。⑵B→B1subB2代表盒子B1后隨下標(biāo)盒子B2，下標(biāo)盒子B2以較小的字體和較低的位置出現(xiàn)。⑶B→(B1)代表一個(gè)由括號括起來的盒子B1，主要是為了對多個(gè)盒子或下標(biāo)進(jìn)行分組。在EQN中，使用花括號進(jìn)行分組，此處使用圓括號是為了避免跟語義動作外面的花括號產(chǎn)生沖突。⑷B→text代表文本字符串，即任意字符組成的串。該文法是二義性的文法，將“并列”和“下標(biāo)”看成是左結(jié)合的，并令“下標(biāo)”的優(yōu)先級高于“并列”的話，則可以對該文法所描述的語言進(jìn)行自底向上的語法分析。2023/2/148屬性設(shè)置⑴pointsize用于表示盒子中文本的尺寸(以點(diǎn)來計(jì)算，也就是字號)。如果標(biāo)準(zhǔn)盒子的尺寸為p，則下標(biāo)盒子的尺寸為0.7×p。屬性B.ps表示盒子B的尺寸，該屬性是繼承屬性。⑵每個(gè)盒子都有一個(gè)基線(baseline)，用來表示每個(gè)文本底部的垂直位置。⑶height用來表示從盒子的頂部到基線的距離。屬性B.ht表示盒子B的高度height，該屬性是綜合屬性。⑷depth用來表示從基線到盒子底部的距離。用屬性B.dp表示盒子B的深度depth，該屬性也是綜合屬性。2023/2/149表6.7對盒子進(jìn)行排版的語法制導(dǎo)定義產(chǎn)生式語義規(guī)則⑴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構(gòu)造的翻譯模式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構(gòu)造的翻譯模式2023/2/152在分析棧中使用一個(gè)附加的域來存放綜合屬性值。下圖為一個(gè)帶有綜合屬性值域的分析棧：stackval...XX.xY...Y.y......ZZ.ztop6.4.2S-屬性定義的自底向上計(jì)算2023/2/153A

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

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

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

AXYZ

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

Yy

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

ntop:=top-r+1——r是句柄的長度執(zhí)行代碼段后執(zhí)行：top:=ntop;2023/2/155例6.14用LR分析器實(shí)現(xiàn)臺式計(jì)算器——與表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

使用的產(chǎn)生式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-屬性定義變成可執(zhí)行的代碼段，這就構(gòu)成了翻譯程序。象一座建筑，語法分析是構(gòu)架，歸約處有一個(gè)“掛鉤”，語義分析和翻譯的代碼段（語義子程序）就掛在這個(gè)鉤子上。這樣，隨著語法分析的進(jìn)行，歸約前調(diào)用相應(yīng)的語義子程序,完成翻譯的任務(wù)。S-屬性定義小結(jié)2023/2/159

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

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

例6.15考慮如下將中綴表達(dá)式翻譯為后綴表達(dá)式的翻譯模式中的兩個(gè)產(chǎn)生式：

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

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

設(shè)有如下左遞歸翻譯模式：

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

A→X

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

消除左遞歸后，文法轉(zhuǎn)換成

A→XR

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

再考慮語義動作，翻譯模式變?yōu)椋?/p>

A→X

｛Ri:=f(Xx)}

R

｛Aa:=Rs}

R→Y

｛R1i:=g(Ri,Yy)}

R1

｛Rs:=R1s}

R→ε

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

A→X{A.a:=f(X.x)}引入繼承屬性R.i來收集應(yīng)用函數(shù)g的計(jì)算結(jié)果。其初始值為A.a:=f(X.x）引入綜合屬性R.s在R結(jié)束生成Y時(shí)復(fù)制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-屬性定義的遞歸下降翻譯器的構(gòu)造：1．對每個(gè)非終結(jié)符A構(gòu)造一個(gè)函數(shù)A，將非終結(jié)符A的各個(gè)繼承屬性當(dāng)作函數(shù)A的形式參數(shù)，而將非終結(jié)符A的綜合屬性集當(dāng)作函數(shù)A的返回值，為了便于討論，假設(shè)每個(gè)非終結(jié)符只具有一個(gè)綜合屬性。2．在函數(shù)A的過程體中，不僅要進(jìn)行語法分析，而且要處理相應(yīng)的語義屬性。函數(shù)A的代碼首先根據(jù)當(dāng)前輸入確定用哪個(gè)產(chǎn)生式展開A，然后按照3中所給的方法對各產(chǎn)生式進(jìn)行編碼。2.L-屬性定義的遞歸下降翻譯法2023/2/1663．與每個(gè)產(chǎn)生式對應(yīng)的程序代碼的工作過程為：按照從左到右的次序，依次對產(chǎn)生式右部的記號、非終結(jié)符和語義動作執(zhí)行如下的動作：1)對帶有綜合屬性x的符號X，將x的值保存在X.x中，并生成一個(gè)函數(shù)調(diào)用來匹配X，然后繼續(xù)讀入下一個(gè)輸入符號；2)對非終結(jié)符B，生成一個(gè)右部帶有函數(shù)調(diào)用的賦值語句c:=B(b1,b2,…,bk)，其中，b1,b2,…,bk是代表B的繼承屬性的變量，c是代表B的綜合屬性的變量；3)對于語義動作，將其代碼復(fù)制到語法分析器中，并將對屬性的引用改為對相應(yīng)變量的引用。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 /*匹配產(chǎn)生式T'→*FT'*/

oplexeme:=lexval;

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

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

syn1:=T'(inh1);syn:=syn1endelseiflookahead=‘/’thenbegin /*匹配產(chǎn)生式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 /*匹配產(chǎn)生式F→(E)*/match(‘(‘);node:=E;match(‘)’)endelseiflookahead=idthenbegin /*匹配產(chǎn)生式F→id*/match(id);node:=mkleaf(id,id.entry)endelseiflookahead=numthenbegin /*匹配產(chǎn)生式F→num*/match(num);node:=mkleaf(num,num.val)endreturnnodeend;

2023/2/1703.L-屬性定義的LL(1)翻譯法預(yù)先在源文法中的相應(yīng)位置上嵌入語義動作符號(每個(gè)對應(yīng)一個(gè)語義子程序)，用于提示語法分析程序，當(dāng)分析到達(dá)這些位置時(shí)應(yīng)調(diào)用相應(yīng)的語義子程序。帶有語義動作符號的文法又叫翻譯文法。2023/2/1713.L-屬性定義的LL(1)翻譯法與遞歸子程序法的區(qū)別與聯(lián)系都是在掃描過程中進(jìn)行產(chǎn)生式的推導(dǎo)，同時(shí)在適當(dāng)?shù)牡胤郊尤胝Z義動作。遞歸子程序法將語義動作溶入分析程序；LL(1)分析法則由語義子程序完成相應(yīng)的翻譯。遞歸子程序法隱式地使用語義棧；LL(1)分析法則用顯式的語義棧（程序自身控制對棧的操作）。注：語義與語法棧不同步。2023/2/172例6.17對于圖6.14的翻譯模式，設(shè)置兩個(gè)棧，一個(gè)是分析棧，一個(gè)是語義棧。 ⑴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.選產(chǎn)生式①的右部進(jìn)棧{e2}{e1}FT'2023/2/175-#語義棧語法棧3*x/y#輸入串例6.17對輸入串3*x/y的翻譯語法分析動作和語義操作3.選擇產(chǎn)生式⑺,num3不進(jìn)棧，調(diào)用{e9}，調(diào)用{e9}后，葉結(jié)點(diǎn)F.node被壓入語義棧{e2}{e1}{e9}T'F.node2023/2/176-#語義棧語法棧3*x/y#輸入串例6.17對輸入串3*x/y的翻譯語法分析動作和語義操作4.執(zhí)行動作{e1}，F(xiàn).node出棧，T'.inh被壓入棧

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

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

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

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

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

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

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

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

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

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