屬性文法和語法制導(dǎo)翻譯市公開課金獎市賽課一等獎?wù)n件

屬性文法和語法制導(dǎo)翻譯講課：胡靜第1頁第1頁語義分析——面向語法定義第2頁第2頁所處位置第3頁第3頁分析技術(shù)LL分析辦法計算最左推導(dǎo)自頂向下結(jié)構(gòu)推導(dǎo)LL分析表指出要對最左邊非終止符進(jìn)行擴(kuò)展時，所選產(chǎn)生式。LR分析辦法計算最右推導(dǎo)自底向上結(jié)構(gòu)推導(dǎo)使用LR狀態(tài)集合和符號棧LR分析表指出針對每一個狀態(tài)，采用何種動作（移進(jìn)/歸約），并且下一個轉(zhuǎn)入狀態(tài)是什么。我們能夠使用這些技術(shù)來結(jié)構(gòu)AST第4頁第4頁AST復(fù)習(xí)推導(dǎo)：使用產(chǎn)生式序列S?E+S?1+S?1+E?1+2分析樹：描述推導(dǎo)圖并不能表示產(chǎn)生式使用順序抽象語法樹(AST)：從分析樹中去掉了那些不必要信息。第5頁第5頁AST數(shù)據(jù)結(jié)構(gòu)第6頁第6頁潛在AST結(jié)構(gòu)LL/LR分析技術(shù)都潛在結(jié)構(gòu)出了AST分析樹在推導(dǎo)過程中能夠得到LLparsing:應(yīng)用產(chǎn)生式序列潛在描述了ASTLRparsing：應(yīng)用歸約序列潛在描述了AST我們希望從分析過程中明確創(chuàng)建AST：在分析器中添加一定代碼來明確創(chuàng)建AST第7頁第7頁AST結(jié)構(gòu)LL分析:對非終止符進(jìn)行擴(kuò)展?Example:第8頁第8頁AST結(jié)構(gòu)LR分析我們也需要添加一些代碼使得AST能夠明確被結(jié)構(gòu)出來。LR分析中AST結(jié)構(gòu)辦法：將樹一部分存儲在堆棧里對每個在堆棧中非終止符B，將以B作為根節(jié)點(diǎn)自樹也存儲在堆棧里當(dāng)分析器使用產(chǎn)生式B→γ實(shí)行一個歸約操作時，為B結(jié)構(gòu)一個AST結(jié)點(diǎn)第9頁第9頁LR分析中AST結(jié)構(gòu)第10頁第10頁問題代碼結(jié)構(gòu)混亂：進(jìn)行語法分析代碼和結(jié)構(gòu)AST代碼混在一起語法分析器生成器：產(chǎn)生語法分析器需要包含AST結(jié)構(gòu)代碼怎樣使用語法分析器自動生成器結(jié)構(gòu)不同AST數(shù)據(jù)結(jié)構(gòu)？我們需要在分析階段同時進(jìn)行其它動作。比如，語義檢驗(yàn) 第11頁第11頁Syntax-DirectedDefinition處理辦法:syntax-directeddefinition擴(kuò)展每個文法產(chǎn)生式，使得每個產(chǎn)生式都和語義動作（代碼）相關(guān)聯(lián)：S→E+S {action}語法分析器生成器將這些代碼加入到生成語法分析器中。當(dāng)使用產(chǎn)生式進(jìn)行歸約時，相應(yīng)動作就會被執(zhí)行。第12頁第12頁語義動作動作：用程序設(shè)計語言編寫代碼和語法分析器生成器程序設(shè)計語言相同比如：Yacc=actionswritteninCCUP=actionswritteninJava動作需要訪問語法分析棧！語法分析器生成器將狀態(tài)棧進(jìn)行擴(kuò)展，用那些用戶定義結(jié)構(gòu)（分析樹）去替換原先符號動作代碼應(yīng)當(dāng)能夠引用狀態(tài)需要一套命名機(jī)制第13頁第13頁命名機(jī)制我們需要對那些在語義動作代碼中可能用到文法符號進(jìn)行命名。需要分別引用出現(xiàn)在不同地方同一個非終止符號E→E1+E2需要對左邊/右邊符號進(jìn)行區(qū)分E0→E+E第14頁第14頁命名機(jī)制：YaccYacc:使用關(guān)鍵字:$1引用右邊第一個符號，$2引用右邊第二個符號，以這類推關(guān)鍵字$$引用左邊非終止符Yacc例子expr::=exprPLUSexpr{$$=$1+$3;}第15頁第15頁結(jié)構(gòu)AST使用語義動作結(jié)構(gòu)ASTAST在分析過程中自底向上結(jié)構(gòu)第16頁第16頁例子分析棧保留了每個非終止符值第17頁第17頁AST設(shè)計確保AST抽象性并不是對每個分析樹中結(jié)點(diǎn)都要引入一個AST結(jié)點(diǎn)。第18頁第18頁AST設(shè)計不要使用一個單一類AST_node比如對于像if,while,+,*,ID,NUM：classAST_node{intnode_type;AST_node[]children;Stringname;intvalue;…etc…}問題：必須要為每個不同結(jié)點(diǎn)保留不同fields來保留其特性。不可擴(kuò)展，對Java類型檢驗(yàn)沒有幫助第19頁第19頁使用類繼承使用子類處理問題對每一個“感興趣”文法中非終止符集合使用一個抽象類，(比如，產(chǎn)生式)E→E+E|E*E|-E|(E)第20頁第20頁另一個例子第21頁第21頁能夠使用syntax-directed定義在語法分析時候進(jìn)行語義檢查比如，類型檢查好處：有效率一個簡樸編譯過程能夠完畢多個任務(wù)害處：代碼結(jié)構(gòu)混亂將語法分析和語義檢查過程混在一起當(dāng)AST結(jié)構(gòu)改變時候進(jìn)行檢查只能是自底向上過程中第22頁第22頁類型申明例子第23頁第23頁值傳遞當(dāng)創(chuàng)建AST時候，也要把值屬性進(jìn)行傳遞。第24頁第24頁另一個例子第25頁第25頁值傳遞值要兩個方向傳遞：自頂向下和自底向上第26頁第26頁結(jié)構(gòu)辦法從語義檢查階段能夠單獨(dú)結(jié)構(gòu)AST重復(fù)檢查AST并且進(jìn)行語義檢查(或其它動作)只有當(dāng)樹被建立起來并且他結(jié)構(gòu)是穩(wěn)定期候才干做。這個過程有更多靈活性，不容易出現(xiàn)錯誤第27頁第27頁屬性文法第28頁第28頁目錄即使形式語義學(xué)研究已經(jīng)取得了許多重大進(jìn)展，但當(dāng)前在實(shí)際應(yīng)用中比較流行語義描述和語義處理辦法主要還是屬性文法和語法制導(dǎo)翻譯。本章研究內(nèi)容：上下文無關(guān)文法所產(chǎn)生語言翻譯。把屬性附加到代表語法結(jié)構(gòu)文法符號上，能夠?qū)⒄Z義信息和程序設(shè)計語言結(jié)構(gòu)聯(lián)系起來。屬性值是用與文法產(chǎn)生式相關(guān)聯(lián)“語義規(guī)則”來計算。涉及概念屬性文法：關(guān)于語言翻譯高層次規(guī)格闡明，隱蔽了詳細(xì)實(shí)現(xiàn)細(xì)節(jié)，不顯式闡明翻譯發(fā)生順序(屬性文法)語法制導(dǎo)翻譯：指明了語義規(guī)則計算順序，闡明實(shí)現(xiàn)細(xì)節(jié)。第29頁第29頁語義規(guī)則計算可完畢工作生成代碼在符號表中保留信息發(fā)犯錯誤信息對輸入符號串翻譯過程就是對語義規(guī)則求值過程第30頁第30頁屬性文法是在上下文無關(guān)文法基礎(chǔ)上，為每個文法符號（終止符或非終止符）配備若干相關(guān)“值”。屬性代表與文法符號相關(guān)信息，如類型、值、代碼序列、符號表內(nèi)容屬性能夠代表任何對象：字符串，數(shù)組，類型，內(nèi)存單元或其它對象語法制導(dǎo)定義=文法+符號相關(guān)屬性集屬性分為兩個子集：綜合屬性、繼承屬性假如把文法符號結(jié)點(diǎn)當(dāng)作統(tǒng)計，包括若干存儲信息域，那么屬性就相稱于域名字第31頁第31頁屬性文法分析樹節(jié)點(diǎn)上屬性值由產(chǎn)生式語義規(guī)則來定義綜合屬性值：通過度析樹中其子節(jié)點(diǎn)屬性值計算出來繼承屬性值：由該節(jié)點(diǎn)弟兄節(jié)點(diǎn)及父節(jié)點(diǎn)屬性值計算出來依賴圖語義規(guī)則建立了屬性間依賴關(guān)系，這種關(guān)系用圖來表示就是依賴圖依賴圖表示了語義規(guī)則計算順序注釋分析數(shù)每個節(jié)點(diǎn)都有屬性值分析樹叫做注釋分析樹計算節(jié)點(diǎn)屬性過程稱為注釋或者裝飾分析樹第32頁第32頁屬性文法在語法制導(dǎo)定義中，每個產(chǎn)生式A→α都有一個形如b=f(c1,c2,...,ck)語義規(guī)則集合與之相關(guān)聯(lián)，其中f是函數(shù)，并且滿足下面條件之一b是A一個綜合屬性，且c1,c2,...,ck是該產(chǎn)生式文法符號屬性b是產(chǎn)生式右部某個文法符號一個繼承屬性，且c1,c2,...,ck是A或者產(chǎn)生式右邊任何文法符號屬性在這兩種情況下，我們說屬性b依賴于c1,c2,...,ck

。尤其要強(qiáng)調(diào)是：終止符只有綜合屬性，它們由詞法分析器提供；非終止符既可有綜合屬性也可有繼承屬性，文法開始符號所有繼承屬性作為屬性計算前初始值。第33頁第33頁關(guān)于屬性文法闡明通常，這種函數(shù)被寫為表示式。其它語義規(guī)則被寫為過程調(diào)用或者程序段——定義產(chǎn)生式左部非終止符虛綜合屬性值普通說來，對于出現(xiàn)在產(chǎn)生式右邊繼承屬性和出現(xiàn)在產(chǎn)生式左邊綜合屬性都必須提供一個計算規(guī)則。屬性計算規(guī)則中只能使用相應(yīng)產(chǎn)生式中文法符號屬性，這有助于在產(chǎn)生式范圍內(nèi)“封裝”屬性依賴性。出現(xiàn)在產(chǎn)生式左邊繼承屬性和出現(xiàn)在產(chǎn)生式右部綜合屬性不由所給產(chǎn)生式屬性計算規(guī)則進(jìn)行計算，它們由其它產(chǎn)生式屬性規(guī)則計算或由屬性計算器參數(shù)提供。第34頁第34頁繼承屬性和綜合屬性計算舉例對于產(chǎn)生式A→BC來講直觀上來講，這個產(chǎn)生式能夠計算A綜合屬性、B和C繼承屬性。那么對于A繼承屬性，也許需要依據(jù)某個類似于X→…A…產(chǎn)生式求。同樣B和C綜合屬性也許需要依據(jù)某個類似于B→β，以及C→γ產(chǎn)生式求。第35頁第35頁屬性文法舉例產(chǎn)生式語義規(guī)則L→Enprint(E.val)E→E1+TE.val:=E1.val+T.valE→TE.val:=T.valT→T1*FT.val:=T1.val*F.val

T→FT.val:=F.valF→(E)F.val:=E.valF→digitF.val:=digit.lexval第36頁第36頁S-屬性文法S-屬性文法在語法樹中，一個結(jié)點(diǎn)綜合屬性值由其子結(jié)點(diǎn)屬性值決定。僅使用綜合屬性屬性文法稱為S-屬性定義S屬性定義分析樹分析辦法——自底向上在每個節(jié)點(diǎn)用語義規(guī)則來計算綜合屬性值。第37頁第37頁綜合屬性舉例LnE產(chǎn)生式語義規(guī)則L→Enprint(E.val)E→E1+TE.val:=E1.val+T.valE→TE.val:=T.valT→T1*FT.val:=T1.val*F.val

T→FT.val:=F.valF→(E)F.val:=E.valF→digitF.val:=digit.lexval3*5+4ET+TF*TFFdigitdigitdigit.lexval=3.val=5.val=4.val=3.val=3.val=15.val=4.val=4.val=15.val=19.val=5第38頁第38頁繼承屬性在語法樹中，一個結(jié)點(diǎn)繼承屬性由此結(jié)點(diǎn)父結(jié)點(diǎn)和/或弟兄結(jié)點(diǎn)一些屬性確定。繼承屬性在程序設(shè)計語言中作用表示程序設(shè)計語言上下文結(jié)構(gòu)依賴性對于賦值號，其左邊和右邊標(biāo)識符在操作時候需要提供屬性不同，這時候就要跟蹤標(biāo)識符繼承屬性。假如在賦值號左邊，則需要地址，右邊則需要值。即使我們總是能夠只用綜合屬性來改寫語法制導(dǎo)定義，不過使用帶有繼承屬性屬性文法有時更為自然。第39頁第39頁繼承屬性例子DLT產(chǎn)生式語義規(guī)則D→TLL.in:=T.typeT→intT.type:=integerT→realT.type:=realL→L1,idL1.in:=L.in

addtype(id.entry,L.in)L→idaddtype(id.entry,L.in)realid1,id2,id3realid3,L.in=real.in=real.type=realid2,L.in=realid1第40頁第40頁語法制導(dǎo)翻譯基于屬性文法處理過程通常是：對符號串進(jìn)行語法分析，結(jié)構(gòu)語法分析樹依據(jù)需要遍歷語法樹并在語法樹各結(jié)點(diǎn)處按語義規(guī)則進(jìn)行計算。這種由源程序語法結(jié)構(gòu)驅(qū)動處理辦法就是語法制導(dǎo)翻譯法。在一些情況下，在進(jìn)行語法分析同時完畢語義規(guī)則計算而不必明顯地結(jié)構(gòu)語法樹或結(jié)構(gòu)屬性之間依賴圖。（一遍處理，L-屬性文法）輸入符號串分析樹依賴圖語義規(guī)格計算順序第41頁第41頁依賴圖依賴圖是有向圖表示了分析樹中各節(jié)點(diǎn)屬性間依賴關(guān)系。其中屬性包括繼承屬性和綜合屬性表示了節(jié)點(diǎn)屬性計算先后順序。假如分析樹中某個節(jié)點(diǎn)屬性b依賴于屬性c，那么在該節(jié)點(diǎn)處b語義規(guī)則必須在c語義規(guī)則之后計算。依賴圖結(jié)構(gòu)辦法為每個包括過程調(diào)用語義規(guī)則引入一個虛綜合屬性b，把每條語義規(guī)則都變成b=f(c1,c2,...,ck)形式依賴圖每個結(jié)點(diǎn)表示一個屬性邊表示屬性間依賴關(guān)系。假如屬性b依賴于屬性c，那么從c到b就有一條有向邊第42頁第42頁依賴圖舉例DLTrealid3,L.in=real.in=real.type=realid2,L.in=realid1DLTrealid3,Lid2,Lid1typeinyinyinyentryentryentry12345678910假如一屬性文法不存在屬性之間循環(huán)依賴關(guān)系，那么稱該文法為良定義產(chǎn)生式語義規(guī)則D→TLL.in:=T.typeT→intT.type:=integerT→realT.type:=realL→L1,idL1.in:=L.in

addtype(id.entry,L.in)L→idaddtype(id.entry,L.in)第43頁第43頁屬性計算順序無環(huán)有向圖拓?fù)渑判驘o環(huán)有向圖中節(jié)點(diǎn)m1,m2,…,mk拓?fù)渑判蚴牵喝鬽i→mj是從mi到mj邊，那么在此排序中mi先于mj依賴圖任何拓?fù)渑判蚨冀o出了一個分析樹中各節(jié)點(diǎn)語義規(guī)則計算正確順序，即在計算f之前，語義規(guī)則b=f(c1,c2,...,ck)中依賴屬性c1,c2,...,ck都是已知屬性文法所闡明翻譯能夠按照下面環(huán)節(jié)進(jìn)行最基本文法用于結(jié)構(gòu)輸入串分析樹用前面辦法結(jié)構(gòu)依賴圖從依賴圖拓?fù)渑判蚰軌虻玫秸Z義規(guī)則計算順序按該順序計算語義規(guī)則即可得到輸入串翻譯第44頁第44頁屬性文法計算順序舉例a4:=reala5:=a4addtype(id3.entry,a5)a7:=a5addtype(id2.entry,a7)a9:=a7addtype(id1.entry,a9)DLTrealid3,Lid2,Lid1typeinyinyinyentryentryentry12345678910第45頁第45頁計算語義規(guī)則辦法分析樹法：在編譯時，這種辦法從分析樹所構(gòu)成依賴圖拓?fù)渑判蛑械玫秸Z義規(guī)則計算順序。假如分析樹依賴圖中有環(huán)路，這種辦法將失敗基于規(guī)則辦法對于每一個產(chǎn)生式，計算該產(chǎn)生式所關(guān)聯(lián)屬性順序在編譯器結(jié)構(gòu)時已經(jīng)預(yù)先擬定好了忽略規(guī)則辦法選擇計算順序時不考慮語義規(guī)則。假如翻譯是在語法分析過程中進(jìn)行，那么計算順序選擇就由語法分析辦法來擬定。后兩種辦法在編譯時都不必顯式結(jié)構(gòu)依賴圖第46頁第46頁樹遍歷屬性計算辦法通過樹遍歷計算屬性值辦法都假設(shè)語法樹已經(jīng)建立，并且數(shù)中已帶有開始符號繼承屬性和終止符綜合屬性。最慣用遍歷辦法是深度優(yōu)先，從左到右遍歷辦法只要文法屬性是非循環(huán)定義，則每次掃描至少有一個屬性值被計算出來。假如語法樹有n個結(jié)點(diǎn)（因此最多有O(n)個屬性），最壞情況整個遍歷需要O(n2)時間。第47頁第47頁樹遍歷舉例產(chǎn)生式語義規(guī)則S→XYZZ.h:=S.aX.c:=Z.gS.b:=X.d–2Y.e:=S.bX→xX.d:=2*X.cY→yY.f:=Y.e*3Z→zZ.g:=Z.h+1S有繼承屬性a，綜合屬性bX有繼承屬性c，綜合屬性dY有繼承屬性e，綜合屬性fZ有繼承屬性h，綜合屬性g假設(shè)S.a初始值為0SZYXxyza=0初始狀態(tài)SZYXxyza=0第一遍掃描h=0g=1SZYXxyza=0第二遍掃描h=0g=1c=1d=2SZYXxyza=0第三遍掃描h=0g=1b=0e=0f=0c=1d=2第48頁第48頁一遍掃描處理辦法在語法分析同時計算屬性值，而不是語法分析結(jié)構(gòu)語法樹之后進(jìn)行屬性計算，并且無需結(jié)構(gòu)實(shí)際語法樹。一遍掃描處理辦法與語法分析器密切相關(guān)原因：所采用語法分析辦法屬性計算順序L-屬性文法可用于一遍掃描自頂向下分析，而S-屬性文法適合于一遍掃描自底向上分析。此時語法制導(dǎo)翻譯可理解為：直觀上說為文法中每個產(chǎn)生式配上一組語義規(guī)則，并且在語法分析同時執(zhí)行這些語義規(guī)則在自頂向下語法分析中，若一個產(chǎn)生式匹配輸入串成功在自底向上語法分析中，當(dāng)一個產(chǎn)生式被用于進(jìn)行歸約時第49頁第49頁抽象語法樹結(jié)構(gòu)用抽象語法樹作為中間表示，能夠把翻譯從語法分析中分離出來語法樹是分析樹壓縮形式，去掉了那些對翻譯不必要信息，對表示語言結(jié)構(gòu)很有用。表示式抽象語法樹結(jié)構(gòu)為每個運(yùn)算符和運(yùn)算對象建立節(jié)點(diǎn)來為子表示式結(jié)構(gòu)子樹。運(yùn)算符節(jié)點(diǎn)字節(jié)點(diǎn)分別是表示該運(yùn)算符各運(yùn)算對象子表示式構(gòu)成子樹根第50頁第50頁表示式語法樹結(jié)構(gòu)辦法運(yùn)算符節(jié)點(diǎn)（用統(tǒng)計實(shí)現(xiàn)，也能夠用對象實(shí)現(xiàn)）一個域標(biāo)識運(yùn)算符，其余域包括指向運(yùn)算對象指針將運(yùn)算符稱為該節(jié)點(diǎn)標(biāo)識結(jié)構(gòu)過程（辦法）mknode(op,left,right)：建立一個標(biāo)識為op運(yùn)算符節(jié)點(diǎn)，其中兩個域left和right是指向其左右運(yùn)算對象指針mkleaf(id,entry)：建立標(biāo)識為id標(biāo)識符節(jié)點(diǎn)，entry是指向該標(biāo)識符在標(biāo)識符表中相應(yīng)表項(xiàng)指針mkleaf(num,value)：建立標(biāo)識為num數(shù)節(jié)點(diǎn)，域val保留該數(shù)值。第51頁第51頁抽象語法樹例子產(chǎn)生式語義規(guī)則E→E1+TE.nptr:=mknode(‘+’,E1.nptr,T.nptr)E→E1–TE.nptr:=mknode(‘-’,E1.nptr,T.nptr)E→TE.nptr:=T.nptrT→(E)T.nptr:=E.nptrT→idT.nptr:=mkleaf(id,id.entry)T→numT.nptr:=mkleaf(num,num.val)第52頁第52頁表示式無環(huán)有向圖表示式無環(huán)有向圖（dag）能夠辨認(rèn)表示式中公共子表示式無環(huán)有向圖構(gòu)成葉子節(jié)點(diǎn)：表示式中操作數(shù)（操作符運(yùn)算對象）內(nèi)部節(jié)點(diǎn)：表示式中操作符（運(yùn)算符）子樹：表示式中每一個子表示式和抽象語法樹區(qū)別：代表公共子表示式節(jié)點(diǎn)含有多個“父結(jié)點(diǎn)”在省城抽象語法樹時，mknode和mkleaf之前先查看是否已經(jīng)存在需要創(chuàng)建節(jié)點(diǎn)，假如存在，則返回以創(chuàng)建節(jié)點(diǎn)而不是新創(chuàng)建一個節(jié)點(diǎn)第53頁第53頁S屬性文法自底向上計算第54頁第54頁S-屬性文法特點(diǎn)S-屬性文法，只有綜合屬性也就是說產(chǎn)生式左邊文法綜合屬性要依據(jù)產(chǎn)生式右邊符號綜合屬性來進(jìn)行計算。適合用于那些需要類似于表示式，需要計算結(jié)果文法。綜合屬性能夠在分?jǐn)?shù)輸入符號串同時由自底向上分析器來計算。分析器保留與棧中文法符號相關(guān)綜合屬性每當(dāng)歸約時，新屬性值就由棧中正在歸約產(chǎn)生式右邊符號屬性值來計算。第55頁第55頁S-屬性文法翻譯器實(shí)現(xiàn)S-屬性文法翻譯器通常可借助于LR分析器實(shí)現(xiàn)。在自底向上分析辦法中，我們使用棧來存儲已經(jīng)分析過了子樹，現(xiàn)在我們能夠在分析棧中使用一個附加域來存儲綜合屬性值。假設(shè)綜合屬性是剛好在每次歸約前計算S3ZZ.zS2YY.yS1XX.x………狀態(tài)棧符號棧valtopA→XYZ第56頁第56頁S-屬性文法計算舉例產(chǎn)生式語義規(guī)則L→Enprint(val[top])E→E1+Tval[top]:=val[top-2]+val[top]E→TT→T1*Fval[top]:=val[top-2]*val[top]T→FF→(E)val[top]:=val[top-1]F→digit我們要控制兩個變量top和ntop。當(dāng)右邊帶有r個符號產(chǎn)生式被歸約時，執(zhí)行相應(yīng)代碼段之前，先將top-r+1賦給ntop，在代碼段被執(zhí)行之后將ntop值賦給top代碼段剛剛好在歸約前執(zhí)行。這是利用歸約提供一個“掛鉤”，使得用戶把一個語義動作與一個產(chǎn)生式聯(lián)系起來。翻譯模式能夠提供一個與分析器互相穿插動作描述辦法。第57頁第57頁L-屬性文法和自頂向下翻譯第58頁第58頁L屬性文法定義在語法分析過程中進(jìn)行翻譯時，屬性計算順序?qū)⑴c分析辦法建立分析樹節(jié)點(diǎn)順序相關(guān)。有一個能夠描述許多自頂向下和自底向上翻譯辦法自然順序——深度優(yōu)先順序。L屬性定義一個屬性文法是L-屬性文法，假如對于每一個產(chǎn)生式A→X1X2…Xn，其右部符號Xj(1≤j≤n)每個屬性值僅依賴于下列屬性產(chǎn)生式中Xj左邊符號X1X2…Xj-1屬性A繼承屬性L屬性計算能夠使用深度優(yōu)先順序來計算LL(1)分析過程，從概念上說能夠當(dāng)作是深度優(yōu)先建立語法樹過程第59頁第59頁L屬性文法反例產(chǎn)生式語義規(guī)則A→LML.i:=l(A.i))M.i:=m(l.s)A→QRR.i:=r(A.i)Q.i:=q(R.s)A.s:=f(Q.s)第60頁第60頁語法制導(dǎo)翻譯語法制導(dǎo)翻譯給出了使用語義規(guī)則進(jìn)行計算順序，這樣就能夠把一些細(xì)節(jié)表示出來。在語法制導(dǎo)翻譯中，和文法符號相關(guān)屬性和語義規(guī)則（這里也稱語義動作），用“{}”括起來，插入到產(chǎn)生式右部適當(dāng)位置上。語法制導(dǎo)翻譯給出了使用語義規(guī)則進(jìn)行計算順序。第61頁第61頁語法制導(dǎo)翻譯舉例E→TRR→addopT{print(addop.lexeme)}R1|εT→num{print(num.val)}ERT9{print(‘9’)}-T{print(‘-’)}R5{print(‘5’)}+T{print(‘+’)}2{print(‘2’)}Rε9-5+2按深度優(yōu)先遍歷之后95-2+第62頁第62頁L-屬性定義語法制導(dǎo)翻譯設(shè)計L屬性定義語法制導(dǎo)翻譯需要注意下列幾點(diǎn)：基本設(shè)計原則：當(dāng)某個動作引用一個屬性時，這個屬性是可用。也就是說，一個動作不會引起一個沒有計算出來屬性。只有綜合屬性時為每一個語義規(guī)則建立一個賦值動作，并把該動作放在產(chǎn)生式右部末尾T→T1*FT.val:=T1.val×F.valT→T1*F{T.val:=T1.val×F.val}第63頁第63頁L-屬性定義語法制導(dǎo)翻譯同時存在綜合屬性和繼承屬性時：產(chǎn)生式右部符號繼承屬性必須在這個符號以前動作中計算出來一個動作不能引用該動作右部符號綜合屬性產(chǎn)生式左部非終止符綜合屬性只有在其引用所有屬性值都計算出來以后才干計算。計算該屬性動作通常放在產(chǎn)生式右部末尾。下面翻譯模式不符合上面定義：S→A1A2{A1.in:=1;A2.in:=2}A→a {print(A.in)}按深度優(yōu)先遍歷時，要打印第二個產(chǎn)生式里繼承屬性A.in時，該屬性還沒有被定義。第64頁第64頁L-屬性文法舉例產(chǎn)生式語義規(guī)則S→BB.ps:=10S.ht:=B.htB→B1B2B1.ps:=B.psB2.ps:=B.psB.ht:=max(B1.ht,B2.ht)B→B1subB2B1.ps:=B.psB2.ps:=shrink(B.ps)B.ht:=disp(B1.ht,B2.ht)B→textB.ht:=text.h×B.psS→{B.ps:=10}B

{S.ht:=B.ht}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:=shrink(B.ps)}B2

{B.ht:=disp(B1.ht,B2.ht)}B→text

{B.ht:=text.h×B.ps}第65頁第65頁L-屬性文法自頂向下翻譯在預(yù)測分析過程中實(shí)現(xiàn)L-屬性文法為了明顯看出動作和屬性計算發(fā)生屬性，我們使用翻譯模式而不是屬性文法。為了結(jié)構(gòu)不帶回溯自頂向下語法分析，必須消除文法中左遞歸。將前面講過辦法擴(kuò)充，從翻譯模式中消除左遞歸（LL(1)文法結(jié)構(gòu)環(huán)節(jié)），這種辦法也適合用于帶有綜合屬性翻譯模式。第66頁第66頁舉例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}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}9-5+2R-TnumRεETnumR+Tnumval=9val=9i=9val=5val=5i=4val=2val=2i=6s=6val=6一個符號繼承屬性必須由出現(xiàn)這個符號之前動作來計算，產(chǎn)生式左邊非終止符綜合屬性必須在它所依賴所有屬性都計算出來之后才干計算第67頁第67頁消除左遞歸普通辦法假設(shè)有下列翻譯模式A→A1Y{A.a:=g(A1.a,Y.y)}A→X{A.a:=f(X.x)}每個文法符號都有綜合屬性，g和f是任意函數(shù)。文法能夠轉(zhuǎn)換為：A→XRR→YR|ε考慮語義動作，變?yōu)椋篈→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}第68頁第68頁遞歸下降翻譯器設(shè)計為每個非終止符A結(jié)構(gòu)一個函數(shù)A每個繼承屬性均相應(yīng)當(dāng)函數(shù)一個形式參數(shù)，其返回值為A綜合屬性值（也許是一個統(tǒng)計、一個指針或者使用傳地址參數(shù)傳遞機(jī)制）非終止符A代碼會依據(jù)當(dāng)前輸入決定使用哪個產(chǎn)生式與每個產(chǎn)生式相關(guān)代碼執(zhí)行下列動作：從左到右考慮產(chǎn)生式右部記號、非終止符及語義動作對于帶有綜合屬性x終止符X，把x值保持在X.x中，然后產(chǎn)生一個匹配X調(diào)用，并繼續(xù)輸入對于非終止符B，產(chǎn)生一個右部帶有函數(shù)調(diào)用賦值語句c=B(b1,b2,...bk)，其中b1,b2,...bk是代表B繼承屬性變量，c是代表B綜合屬性變量對于每個動作，將其代碼復(fù)制到語法分析器，并把對屬性引用改為對相應(yīng)變量引用第69頁第69頁自底向上計算繼承屬性刪除嵌入在翻譯模式中動作在自頂向下分析中我們能夠在產(chǎn)生式右部任何地方嵌入動作在自底向上翻譯方法中，需要把全部翻譯動作都放在產(chǎn)生式右部末尾在基礎(chǔ)文法中加入新形如M→ε產(chǎn)生式，其中M為標(biāo)識非終止符。將每個嵌入動作用不同標(biāo)識非終止符M來代替，并把該動作放在此空產(chǎn)生式末端比如E→TRR→+T{print(‘+’)}R|-T{print(‘-’)}R|εT→num{print(num.val)}轉(zhuǎn)化為E→TRR→+TMR|-TNR|εM→ε{print(‘+’)}N→ε{print(‘-’)}第70頁第70頁自底向上計算繼承屬性轉(zhuǎn)換后語法制導(dǎo)翻譯和原語法制導(dǎo)翻譯比較用額外節(jié)點(diǎn)表示動作，但動作執(zhí)行順序是同樣轉(zhuǎn)換后翻譯模式中，動作都在產(chǎn)生式末尾，能夠在自底向上分析過程中剛好在產(chǎn)生式右部被歸約之前執(zhí)行第71頁第71頁分析棧中繼承屬性對于繼承屬性是由復(fù)制規(guī)則定義產(chǎn)生式自底向上語法分析器對產(chǎn)生式A→XY歸約就是從分析棧頂移走X和Y并用A來代替它們。假設(shè)X有一個綜合屬性X.s。X綜合屬性在分析中放入屬性棧，和狀態(tài)棧符號棧是一一相應(yīng)。X.s在Y下列子樹任何歸約之前已經(jīng)放在棧中，這個值能夠被Y繼承，也就是說，假如繼承屬性Y.i是由復(fù)寫規(guī)則Y.i:=X.s定義，那么在需要Y.i地方能夠使用X.s值。第72頁第72頁舉例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)}intp,q,rrL,intLDTqL,pintypeinin所用產(chǎn)生式棧輸入串-intp,q,rintp,q,rTp,q,rT→intTp,q,rTL,q,rT→intTL,q,rTL,q,rTL,rL→L,idTL,rTL,rTLL→L,idDD→TL產(chǎn)生式代碼段D→TLT→intval[notp]:=integerT→realval[notp]:=realL→L,idaddtype(val[top],val[top-3])L→idaddtype(val[top],val[top-1])第73頁第73頁模擬繼承屬性計算使用自底向上辦法計算繼承屬性，必須要能夠預(yù)測屬性值在棧中位置。產(chǎn)生式語義規(guī)則S→aACC.i:=A.sS→bABCC.i:=A.sC→cC.s:=g(C.i)產(chǎn)生式語義規(guī)則S→aACC.i:=A.sS→aABMCM.i:=A.s;C.i:=M.sC→cC.s:=g(C.i)M→εM.s:=M.i第74頁第74頁模擬繼承屬性計算模擬由復(fù)制規(guī)則計算繼承屬性引入一個新標(biāo)識非終止符M，用M繼承屬性和綜合屬性來傳遞后面非終止符需要復(fù)制繼承屬性。模擬不是復(fù)制規(guī)則語義規(guī)則（計算函數(shù)）也能夠加入新標(biāo)識非終止符，用復(fù)制規(guī)則繼承前面非終止符屬性值，其綜合屬性被置為用計算函數(shù)進(jìn)行計算第75頁第75頁產(chǎn)生式語義規(guī)則S→