編譯原理課件CHAPTER5(SemanticAnalysisandIntermediateCodeGeneration-1)

5.1語(yǔ)義分析概述詞法分析、語(yǔ)法分析——程序在書(shū)寫(xiě)上是正確的、在語(yǔ)法上是正確的，不能保證含義（語(yǔ)義）上的正確性11/29/202215.1語(yǔ)義分析概述詞法分析、語(yǔ)法分析——程序在書(shū)寫(xiě)上5.1語(yǔ)義分析概述語(yǔ)義分析階段分析源程序的含義，并作相應(yīng)的處理，語(yǔ)義分析的基本功能：確定類(lèi)型：確定標(biāo)識(shí)符所關(guān)聯(lián)數(shù)據(jù)對(duì)象的類(lèi)型，即處理源程序的說(shuō)明部分類(lèi)型檢查：對(duì)運(yùn)算及進(jìn)行運(yùn)算的運(yùn)算分量進(jìn)行類(lèi)型檢查，檢查運(yùn)算的合法性與運(yùn)算分量類(lèi)型的一致性（相容性），必要時(shí)作相應(yīng)的類(lèi)型轉(zhuǎn)換11/29/202225.1語(yǔ)義分析概述語(yǔ)義分析階段分析源程序的含義，并作相應(yīng)5.1語(yǔ)義分析概述識(shí)別含義：確定程序中各構(gòu)成成分組合到一起的含義，對(duì)可執(zhí)行語(yǔ)句生成中間代碼或目標(biāo)代碼*語(yǔ)義分析往往是和中間代碼生成緊密聯(lián)系的其他一些靜態(tài)語(yǔ)義檢查：控制流檢查：如對(duì)于PASCAL語(yǔ)言，不允許從循環(huán)外跳轉(zhuǎn)到循環(huán)內(nèi)，C語(yǔ)言的Break引起控制離開(kāi)最小包圍的while、for等語(yǔ)句，檢查是否這樣的語(yǔ)句存在唯一性檢查：如標(biāo)識(shí)符只能定義一次，枚舉類(lèi)型的元素不能重復(fù)等11/29/202235.1語(yǔ)義分析概述識(shí)別含義：確定程序中各構(gòu)成成分組合到一5.1語(yǔ)義分析概述語(yǔ)義分析的輸入是語(yǔ)法分析的輸出（分析樹(shù)），輸出是中間代碼，但同時(shí)它還完成了很多語(yǔ)義處理工作（見(jiàn)上）語(yǔ)義分析的主流技術(shù)——語(yǔ)法制導(dǎo)翻譯技術(shù)11/29/202245.1語(yǔ)義分析概述語(yǔ)義分析的輸入是語(yǔ)法分析的輸出（分析樹(shù)5.2語(yǔ)法制導(dǎo)翻譯文法符號(hào)的屬性：文法符號(hào)（GrammarSymbols）代表語(yǔ)言結(jié)構(gòu)（LanguageConstruct），如標(biāo)識(shí)符、表達(dá)式、語(yǔ)句、程序?yàn)槊總€(gè)文法符號(hào)引入一個(gè)屬性（attribute）集合，反映相應(yīng)語(yǔ)言結(jié)構(gòu)的語(yǔ)義信息，如標(biāo)識(shí)符的類(lèi)型、常量的值、變量的存儲(chǔ)地址等11/29/202255.2語(yǔ)法制導(dǎo)翻譯文法符號(hào)的屬性：文法符號(hào)（Gramma屬性的類(lèi)型（從分析過(guò)程中屬性值的計(jì)算方法來(lái)分類(lèi)）：5.2語(yǔ)法制導(dǎo)翻譯 1、綜合屬性（SynthesizedAttributes）：屬性值是分析樹(shù)中該結(jié)點(diǎn)的子結(jié)點(diǎn)的屬性值的函數(shù) 2、繼承屬性（InheritedAttributes）：屬性值是分析樹(shù)中該結(jié)點(diǎn)的父結(jié)點(diǎn)和/或兄弟結(jié)點(diǎn)的屬性值的函數(shù)11/29/20226屬性的類(lèi)型（從分析過(guò)程中屬性值的計(jì)算方法來(lái)分類(lèi)）：5.25.2語(yǔ)法制導(dǎo)翻譯對(duì)于產(chǎn)生式AX1X2…XnAX1X2Xn…計(jì)算A的綜合屬性,S(A):=f(I(X1),…,I(Xn))計(jì)算Xj的繼承屬性,T(Xj):=f(I(A),...,I(Xn))綜合屬性用于“自下而上”傳遞信息，繼承屬性用于“自上而下”傳遞信息11/29/202275.2語(yǔ)法制導(dǎo)翻譯對(duì)于產(chǎn)生式AX1X2…XnAX5.2語(yǔ)法制導(dǎo)翻譯非終結(jié)符（開(kāi)始符號(hào)除外）既可有綜合屬性也可有繼承屬性文法開(kāi)始符號(hào)沒(méi)有繼承屬性終結(jié)符號(hào)只有綜合屬性，一般由詞法分析器提供11/29/202285.2語(yǔ)法制導(dǎo)翻譯非終結(jié)符（開(kāi)始符號(hào)除外）既可有綜合屬性5.2語(yǔ)法制導(dǎo)翻譯語(yǔ)法制導(dǎo)定義：為每一條產(chǎn)生式（Aα）引入一套語(yǔ)義規(guī)則規(guī)則形式：b:=f(c1,c2,…,ck)b是A的綜合屬性，則c1,c2,…,ck是產(chǎn)生式文法符號(hào)的屬性b是產(chǎn)生式右部某文法符號(hào)的繼承屬性，則c1,c2,…,ck是產(chǎn)生式文法符號(hào)的屬性11/29/202295.2語(yǔ)法制導(dǎo)翻譯語(yǔ)法制導(dǎo)定義：規(guī)則形式：b:=f5.2語(yǔ)法制導(dǎo)翻譯虛（綜合）屬性（Dummysynthesizedattribute）：針對(duì)語(yǔ)義動(dòng)作（過(guò)程或語(yǔ)義子程序）只是為了形式上的統(tǒng)一語(yǔ)義規(guī)則可以計(jì)算屬性值，也可以（語(yǔ)義動(dòng)作）在符號(hào)表中登錄信息、輸出錯(cuò)誤信息、進(jìn)行類(lèi)型檢查、產(chǎn)生中間代碼等11/29/2022105.2語(yǔ)法制導(dǎo)翻譯虛（綜合）屬性語(yǔ)義規(guī)則可以計(jì)算屬性值，5.2語(yǔ)法制導(dǎo)翻譯例1P281Fig.5.2（只有綜合屬性）虛屬性終結(jié)符號(hào)的屬性某些非終結(jié)符加下標(biāo)是為了區(qū)分一個(gè)產(chǎn)生式中同一非終結(jié)符的多次出現(xiàn)例2P283Fig.5.4（帶有繼承屬性）11/29/2022115.2語(yǔ)法制導(dǎo)翻譯例1P281Fig.5.25.2語(yǔ)法制導(dǎo)翻譯屬性文法：語(yǔ)法制導(dǎo)定義對(duì)上下文無(wú)關(guān)文法進(jìn)行了擴(kuò)充，擴(kuò)充后的文法稱為屬性文法（attributegrammar）。11/29/2022125.2語(yǔ)法制導(dǎo)翻譯屬性文法：語(yǔ)法制導(dǎo)定義對(duì)上下文無(wú)關(guān)文法5.2語(yǔ)法制導(dǎo)翻譯語(yǔ)法制導(dǎo)翻譯（Syntax-DirectedTranslation）:根據(jù)語(yǔ)法分析中產(chǎn)生式對(duì)應(yīng)的語(yǔ)義規(guī)則進(jìn)行翻譯的方法稱為語(yǔ)法制導(dǎo)翻譯。語(yǔ)法制導(dǎo)：基于語(yǔ)法分析中用到的文法產(chǎn)生式翻譯：完成語(yǔ)義分析的各項(xiàng)功能，不僅指生成中間代碼11/29/2022135.2語(yǔ)法制導(dǎo)翻譯語(yǔ)法制導(dǎo)翻譯語(yǔ)法制導(dǎo)：基于語(yǔ)法分析中用5.2語(yǔ)法制導(dǎo)翻譯屬性之間的依賴關(guān)系語(yǔ)義規(guī)則b:=f(c1,c2,…,ck)只有在已知c1,…,ck值的基礎(chǔ)上，才能計(jì)算屬性值b稱屬性b依賴于屬性c1,…,ck11/29/2022145.2語(yǔ)法制導(dǎo)翻譯屬性之間的依賴關(guān)系只有在已知c1,…5.2語(yǔ)法制導(dǎo)翻譯依賴圖（DependencyGraphs）:有向邊，a→b，表示屬性b依賴于屬性a用來(lái)表示屬性之間依賴關(guān)系的有向圖（DirectedGraph）稱為依賴圖11/29/2022155.2語(yǔ)法制導(dǎo)翻譯依賴圖（DependencyGrap5.2語(yǔ)法制導(dǎo)翻譯依賴圖的構(gòu)造算法：P284考慮的是分析樹(shù)中的結(jié)點(diǎn)一個(gè)屬性建立一個(gè)結(jié)點(diǎn)為每個(gè)語(yǔ)義動(dòng)作引入一個(gè)虛屬性例Fig.5.611/29/2022165.2語(yǔ)法制導(dǎo)翻譯依賴圖的構(gòu)造算法：P284例Fig.5.2語(yǔ)法制導(dǎo)翻譯依賴圖的例子：LE.val=19E.val=15T.val=4T.val=15F.val=4T.val=3F.val=3F.val=5digit.lexval=4digit.lexval=5digit.lexval=3+*Fig.5.3的依賴圖n11/29/2022175.2語(yǔ)法制導(dǎo)翻譯依賴圖的例子：LE.val=19E.v5.2語(yǔ)法制導(dǎo)翻譯依賴圖的例子：Fig.5.7（Fig.5.5的依賴圖）11/29/2022185.2語(yǔ)法制導(dǎo)翻譯依賴圖的例子：11/27/2022185.2語(yǔ)法制導(dǎo)翻譯屬性計(jì)算順序有向非循環(huán)圖（directedacyclicgraph）的拓?fù)渑判颍╰opologicalsort）：圖中所有結(jié)點(diǎn)的一個(gè)排列若mi→mj是一有向邊，則在結(jié)點(diǎn)序列中mi在mj的前面11/29/2022195.2語(yǔ)法制導(dǎo)翻譯屬性計(jì)算順序有向非循環(huán)圖（direct5.2語(yǔ)法制導(dǎo)翻譯例子：1234765拓?fù)渑判颍?65432175643214763521*依賴圖的任一拓?fù)渑判蚴且粋€(gè)合理的屬性計(jì)算順序

11/29/2022205.2語(yǔ)法制導(dǎo)翻譯例子：1234765拓?fù)渑判颍?65.2語(yǔ)法制導(dǎo)翻譯屬性計(jì)算實(shí)例：P286Example5.611/29/2022215.2語(yǔ)法制導(dǎo)翻譯屬性計(jì)算實(shí)例：11/27/2022215.2語(yǔ)法制導(dǎo)翻譯屬性計(jì)算的三種方法：1、分析樹(shù)法：（1）按基礎(chǔ)文法構(gòu)造句子（程序）的分析樹(shù)（語(yǔ)法分析）（2）按分析樹(shù)構(gòu)造依賴圖（3）對(duì)依賴圖進(jìn)行拓?fù)渑判?，得到語(yǔ)義規(guī)則的執(zhí)行順序（4）按上述順序執(zhí)行語(yǔ)義規(guī)則，計(jì)算屬性值，得到句子的翻譯結(jié)果*如果依賴圖存在回路，這種方法會(huì)失敗11/29/2022225.2語(yǔ)法制導(dǎo)翻譯屬性計(jì)算的三種方法：*如果依賴圖存在5.2語(yǔ)法制導(dǎo)翻譯2、基于語(yǔ)義規(guī)則的方法（Rule-basedmethods）：語(yǔ)法分析和屬性計(jì)算分開(kāi)，先構(gòu)造分析樹(shù)，然后按預(yù)先定義的策略遍歷分析樹(shù)來(lái)計(jì)算屬性語(yǔ)義規(guī)則的定義和計(jì)算順序(翻譯模式)在編譯器構(gòu)造之前確定11/29/2022235.2語(yǔ)法制導(dǎo)翻譯2、基于語(yǔ)義規(guī)則的方法（Rule-ba5.2語(yǔ)法制導(dǎo)翻譯分析樹(shù)遍歷策略的確定（構(gòu)造編譯器時(shí)）要考慮語(yǔ)義規(guī)則的定義及計(jì)算順序，因此是基于規(guī)則的方法優(yōu)點(diǎn)：不構(gòu)造依賴圖，不對(duì)依賴圖進(jìn)行拓?fù)渑判?，提高了時(shí)空效率11/29/2022245.2語(yǔ)法制導(dǎo)翻譯分析樹(shù)遍歷策略的確定（構(gòu)造編譯器時(shí)）要5.2語(yǔ)法制導(dǎo)翻譯3、忽略語(yǔ)義規(guī)則的方法（Obliviousmethods）：在進(jìn)行語(yǔ)法分析的同時(shí)進(jìn)行翻譯，即邊分析邊計(jì)算屬性，計(jì)算次序由分析方法確定而與語(yǔ)義規(guī)則無(wú)關(guān)缺點(diǎn)：這樣確定計(jì)算次序?qū)⑾拗颇軐?shí)現(xiàn)的語(yǔ)法制導(dǎo)定義的種類(lèi)優(yōu)點(diǎn)：不構(gòu)造依賴圖，不對(duì)依賴圖進(jìn)行拓?fù)渑判?，提高了時(shí)空效率11/29/2022255.2語(yǔ)法制導(dǎo)翻譯3、忽略語(yǔ)義規(guī)則的方法（Oblivio5.2語(yǔ)法制導(dǎo)翻譯S-屬性定義（S-attributeddefinitions）：只含有綜合屬性的語(yǔ)法制導(dǎo)定義例：P281Fig.5.211/29/2022265.2語(yǔ)法制導(dǎo)翻譯S-屬性定義（S-attribute5.2語(yǔ)法制導(dǎo)翻譯只有綜合屬性時(shí)（以P282Fig.5.3的依賴圖為例）依賴圖中有向邊的走向和自底向上分析時(shí)建立分析樹(shù)的順序是一致的因此，可以考慮在進(jìn)行語(yǔ)法分析（自底向上）的同時(shí)進(jìn)行翻譯（執(zhí)行語(yǔ)義規(guī)則）11/29/2022275.2語(yǔ)法制導(dǎo)翻譯只有綜合屬性時(shí)（以P282Fig.5.2語(yǔ)法制導(dǎo)翻譯具體實(shí)現(xiàn)：擴(kuò)充LR分析器，為棧中的每一個(gè)文法符號(hào)增加一個(gè)屬性域，存放分析過(guò)程中該文法符號(hào)的綜合屬性值，當(dāng)用產(chǎn)生式進(jìn)行歸約時(shí)，產(chǎn)生式左邊文法符號(hào)入棧，其屬性值由棧中正在歸約的產(chǎn)生式右邊符號(hào)的屬性值計(jì)算11/29/2022285.2語(yǔ)法制導(dǎo)翻譯具體實(shí)現(xiàn)：擴(kuò)充LR分析器，為棧中的每5.2語(yǔ)法制導(dǎo)翻譯例子1：P294……XX.xYY.yZZ.z…………AA.a………………toptop11/29/2022295.2語(yǔ)法制導(dǎo)翻譯例子1：……XX.xYY.y5.2語(yǔ)法制導(dǎo)翻譯例子2：P295-296Fig.5.16Fig.5.17ntop=top–r+1r是產(chǎn)生式右部符號(hào)個(gè)數(shù)PRODUCTION SEMANTICRULELEn print(val[top])EE1+T val[ntop]=val[top-2]+val[top]

ET TT1*F val[ntop]=val[top-2]*val[top]

TF F(E) val[ntop]=val[top-1] Fdigit 11/29/2022305.2語(yǔ)法制導(dǎo)翻譯例子2：P295-296Fig.55.2語(yǔ)法制導(dǎo)翻譯**Fig.5.16是Fig.5.2的一種具體實(shí)現(xiàn)方法11/29/2022315.2語(yǔ)法制導(dǎo)翻譯**Fig.5.16是Fig.55.2語(yǔ)法制導(dǎo)翻譯L-屬性定義（L-attributeddefinitions）：是一種語(yǔ)法制導(dǎo)定義對(duì)于產(chǎn)生式A→X1X2…Xn右部Xj的繼承屬性，它依賴于： 1、X1，X2，…，Xj-1（Xj左邊的文法符號(hào)）的屬性 2、A的繼承屬性**L-屬性定義包含S-屬性定義11/29/2022325.2語(yǔ)法制導(dǎo)翻譯L-屬性定義（L-attribute5.2語(yǔ)法制導(dǎo)翻譯例子：P298Fig.5.19（非L-屬性定義）11/29/2022335.2語(yǔ)法制導(dǎo)翻譯例子：（非L-屬性定義）11/27/25.2語(yǔ)法制導(dǎo)翻譯翻譯模式（translationscheme）：將語(yǔ)義規(guī)則放到{}中，并插入到產(chǎn)生式右部的適當(dāng)位置，以反映語(yǔ)義規(guī)則的計(jì)算順序，這種書(shū)寫(xiě)形式稱之為翻譯模式翻譯模式與語(yǔ)法制導(dǎo)定義的區(qū)別：翻譯模式中指明了語(yǔ)義規(guī)則的執(zhí)行順序11/29/2022345.2語(yǔ)法制導(dǎo)翻譯翻譯模式（translationsc5.2語(yǔ)法制導(dǎo)翻譯例子：P298例5.12（5.1）是一個(gè)翻譯模式用此翻譯模式去分析一個(gè)句子（9-5+2）把語(yǔ)義動(dòng)作作為終結(jié)符號(hào)11/29/2022355.2語(yǔ)法制導(dǎo)翻譯例子：P298例5.12用此翻譯模ETR9{print(“9”)}-T{print(“-”)}{print(“5”)}{print(“+”)}{print(“2”)}52RT12345對(duì)分析樹(shù)（Fig.5.20）進(jìn)行深度優(yōu)先遍歷，執(zhí)行語(yǔ)義動(dòng)作，完成翻譯工作（95-2+）（5.1）是一個(gè)適合以深度優(yōu)先順序計(jì)算屬性的翻譯模式R+11/29/202236ETR9{print(“9”)}-T{print(“-”)}5.2語(yǔ)法制導(dǎo)翻譯為L(zhǎng)-屬性定義構(gòu)造翻譯模式：適合以深度優(yōu)先順序計(jì)算屬性的翻譯模式需滿足的條件：1、產(chǎn)生式右部文法符號(hào)的繼承屬性必須在這個(gè)符號(hào)以前的動(dòng)作中計(jì)算出來(lái)；2、一個(gè)動(dòng)作不能引用該動(dòng)作右邊符號(hào)的綜合屬性；3、產(chǎn)生式左部非終結(jié)符號(hào)的綜合屬性只有在其引用的所有屬性都計(jì)算出來(lái)以后才能計(jì)算。計(jì)算該屬性的動(dòng)作通常放在產(chǎn)生式右部的末尾11/29/2022375.2語(yǔ)法制導(dǎo)翻譯為L(zhǎng)-屬性定義構(gòu)造翻譯模式：適合以深5.2語(yǔ)法制導(dǎo)翻譯從L-屬性定義出發(fā)，構(gòu)造一個(gè)滿足要求的翻譯模式**L-屬性定義本身考慮到了滿足這些條件（第一條件）將計(jì)算產(chǎn)生式右邊某文法符號(hào)的繼承屬性的語(yǔ)義規(guī)則插入到此符號(hào)之前（第二條件）L-屬性定義本身滿足（第三條件）將計(jì)算產(chǎn)生式左邊非終結(jié)符號(hào)綜合屬性的語(yǔ)義規(guī)則放在產(chǎn)生式右端的末尾11/29/2022385.2語(yǔ)法制導(dǎo)翻譯從L-屬性定義出發(fā)，構(gòu)造一個(gè)滿足要求5.2語(yǔ)法制導(dǎo)翻譯例子：P300-301例5.13Fig.5.22----語(yǔ)法制導(dǎo)定義（L-屬性定義）Fig.5.23----翻譯模式11/29/2022395.2語(yǔ)法制導(dǎo)翻譯例子：P300-301例5.13FPRODUCTION SEMANTICRULESB B.ps=10;S.ht=B.htBB1B2 B1.ps=B.ps;B2.ps=B.ps;

B.ht=max(B1.ht,B2.ht)BB1subB2 B1.ps=B.ps;B2.ps=shrink(B.ps);

B.ht=disp(B1.ht,B2.ht)Btext B.ht=text.h*B.psTRANSLATIONSCHEMES{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}B1sub{B2.ps=shrink(B.ps)}B2{B.ht=disp(B1.ht,B2.ht)}Btext{B.ht=text.h*B.ps}11/29/202240PRODUCTION SEMANTICRULETRANSL5.2語(yǔ)法制導(dǎo)翻譯分析一個(gè)句子：textsubtexttextSBB2B1textB3subB4texttext分析樹(shù)11/29/2022415.2語(yǔ)法制導(dǎo)翻譯分析一個(gè)句子：textsubtex帶語(yǔ)義動(dòng)作的分析樹(shù)SB{B.ps:=10}{S.ht:=B.ht}{B1.ps:=B.ps}{B.ht:=max(B1.ht,B2.ht}{B2.ps:=B.ps}B1B2{B3.ps:=B1.ps}{B4.ps:=shrink(B1.ps)}{B1.ht:=disp(B3.ht,B4.ht}B4subB3text{B2.ht:=text.h*B2.ps}text{B3.ht:=text.h*B3.ps}text{B4.ht:=text.h*B4.ps}1234567891011*深度優(yōu)先計(jì)算屬性11/29/202242帶語(yǔ)義動(dòng)作的分析樹(shù)SB{B.ps:=10}{S.ht:=B.TheEnd!11/29/202243TheEnd!11/27/202243編譯原理課件CHAPTER5(SemanticAnalysisandIntermediateCodeGeneration-1)編譯原理課件CHAPTER5(SemanticAnalysisandIntermediateCodeGeneration-1)5.1語(yǔ)義分析概述詞法分析、語(yǔ)法分析——程序在書(shū)寫(xiě)上是正確的、在語(yǔ)法上是正確的，不能保證含義（語(yǔ)義）上的正確性11/29/2022465.1語(yǔ)義分析概述詞法分析、語(yǔ)法分析——程序在書(shū)寫(xiě)上5.1語(yǔ)義分析概述語(yǔ)義分析階段分析源程序的含義，并作相應(yīng)的處理，語(yǔ)義分析的基本功能：確定類(lèi)型：確定標(biāo)識(shí)符所關(guān)聯(lián)數(shù)據(jù)對(duì)象的類(lèi)型，即處理源程序的說(shuō)明部分類(lèi)型檢查：對(duì)運(yùn)算及進(jìn)行運(yùn)算的運(yùn)算分量進(jìn)行類(lèi)型檢查，檢查運(yùn)算的合法性與運(yùn)算分量類(lèi)型的一致性（相容性），必要時(shí)作相應(yīng)的類(lèi)型轉(zhuǎn)換11/29/2022475.1語(yǔ)義分析概述語(yǔ)義分析階段分析源程序的含義，并作相應(yīng)5.1語(yǔ)義分析概述識(shí)別含義：確定程序中各構(gòu)成成分組合到一起的含義，對(duì)可執(zhí)行語(yǔ)句生成中間代碼或目標(biāo)代碼*語(yǔ)義分析往往是和中間代碼生成緊密聯(lián)系的其他一些靜態(tài)語(yǔ)義檢查：控制流檢查：如對(duì)于PASCAL語(yǔ)言，不允許從循環(huán)外跳轉(zhuǎn)到循環(huán)內(nèi)，C語(yǔ)言的Break引起控制離開(kāi)最小包圍的while、for等語(yǔ)句，檢查是否這樣的語(yǔ)句存在唯一性檢查：如標(biāo)識(shí)符只能定義一次，枚舉類(lèi)型的元素不能重復(fù)等11/29/2022485.1語(yǔ)義分析概述識(shí)別含義：確定程序中各構(gòu)成成分組合到一5.1語(yǔ)義分析概述語(yǔ)義分析的輸入是語(yǔ)法分析的輸出（分析樹(shù)），輸出是中間代碼，但同時(shí)它還完成了很多語(yǔ)義處理工作（見(jiàn)上）語(yǔ)義分析的主流技術(shù)——語(yǔ)法制導(dǎo)翻譯技術(shù)11/29/2022495.1語(yǔ)義分析概述語(yǔ)義分析的輸入是語(yǔ)法分析的輸出（分析樹(shù)5.2語(yǔ)法制導(dǎo)翻譯文法符號(hào)的屬性：文法符號(hào)（GrammarSymbols）代表語(yǔ)言結(jié)構(gòu)（LanguageConstruct），如標(biāo)識(shí)符、表達(dá)式、語(yǔ)句、程序?yàn)槊總€(gè)文法符號(hào)引入一個(gè)屬性（attribute）集合，反映相應(yīng)語(yǔ)言結(jié)構(gòu)的語(yǔ)義信息，如標(biāo)識(shí)符的類(lèi)型、常量的值、變量的存儲(chǔ)地址等11/29/2022505.2語(yǔ)法制導(dǎo)翻譯文法符號(hào)的屬性：文法符號(hào)（Gramma屬性的類(lèi)型（從分析過(guò)程中屬性值的計(jì)算方法來(lái)分類(lèi)）：5.2語(yǔ)法制導(dǎo)翻譯 1、綜合屬性（SynthesizedAttributes）：屬性值是分析樹(shù)中該結(jié)點(diǎn)的子結(jié)點(diǎn)的屬性值的函數(shù) 2、繼承屬性（InheritedAttributes）：屬性值是分析樹(shù)中該結(jié)點(diǎn)的父結(jié)點(diǎn)和/或兄弟結(jié)點(diǎn)的屬性值的函數(shù)11/29/202251屬性的類(lèi)型（從分析過(guò)程中屬性值的計(jì)算方法來(lái)分類(lèi)）：5.25.2語(yǔ)法制導(dǎo)翻譯對(duì)于產(chǎn)生式AX1X2…XnAX1X2Xn…計(jì)算A的綜合屬性,S(A):=f(I(X1),…,I(Xn))計(jì)算Xj的繼承屬性,T(Xj):=f(I(A),...,I(Xn))綜合屬性用于“自下而上”傳遞信息，繼承屬性用于“自上而下”傳遞信息11/29/2022525.2語(yǔ)法制導(dǎo)翻譯對(duì)于產(chǎn)生式AX1X2…XnAX5.2語(yǔ)法制導(dǎo)翻譯非終結(jié)符（開(kāi)始符號(hào)除外）既可有綜合屬性也可有繼承屬性文法開(kāi)始符號(hào)沒(méi)有繼承屬性終結(jié)符號(hào)只有綜合屬性，一般由詞法分析器提供11/29/2022535.2語(yǔ)法制導(dǎo)翻譯非終結(jié)符（開(kāi)始符號(hào)除外）既可有綜合屬性5.2語(yǔ)法制導(dǎo)翻譯語(yǔ)法制導(dǎo)定義：為每一條產(chǎn)生式（Aα）引入一套語(yǔ)義規(guī)則規(guī)則形式：b:=f(c1,c2,…,ck)b是A的綜合屬性，則c1,c2,…,ck是產(chǎn)生式文法符號(hào)的屬性b是產(chǎn)生式右部某文法符號(hào)的繼承屬性，則c1,c2,…,ck是產(chǎn)生式文法符號(hào)的屬性11/29/2022545.2語(yǔ)法制導(dǎo)翻譯語(yǔ)法制導(dǎo)定義：規(guī)則形式：b:=f5.2語(yǔ)法制導(dǎo)翻譯虛（綜合）屬性（Dummysynthesizedattribute）：針對(duì)語(yǔ)義動(dòng)作（過(guò)程或語(yǔ)義子程序）只是為了形式上的統(tǒng)一語(yǔ)義規(guī)則可以計(jì)算屬性值，也可以（語(yǔ)義動(dòng)作）在符號(hào)表中登錄信息、輸出錯(cuò)誤信息、進(jìn)行類(lèi)型檢查、產(chǎn)生中間代碼等11/29/2022555.2語(yǔ)法制導(dǎo)翻譯虛（綜合）屬性語(yǔ)義規(guī)則可以計(jì)算屬性值，5.2語(yǔ)法制導(dǎo)翻譯例1P281Fig.5.2（只有綜合屬性）虛屬性終結(jié)符號(hào)的屬性某些非終結(jié)符加下標(biāo)是為了區(qū)分一個(gè)產(chǎn)生式中同一非終結(jié)符的多次出現(xiàn)例2P283Fig.5.4（帶有繼承屬性）11/29/2022565.2語(yǔ)法制導(dǎo)翻譯例1P281Fig.5.25.2語(yǔ)法制導(dǎo)翻譯屬性文法：語(yǔ)法制導(dǎo)定義對(duì)上下文無(wú)關(guān)文法進(jìn)行了擴(kuò)充，擴(kuò)充后的文法稱為屬性文法（attributegrammar）。11/29/2022575.2語(yǔ)法制導(dǎo)翻譯屬性文法：語(yǔ)法制導(dǎo)定義對(duì)上下文無(wú)關(guān)文法5.2語(yǔ)法制導(dǎo)翻譯語(yǔ)法制導(dǎo)翻譯（Syntax-DirectedTranslation）:根據(jù)語(yǔ)法分析中產(chǎn)生式對(duì)應(yīng)的語(yǔ)義規(guī)則進(jìn)行翻譯的方法稱為語(yǔ)法制導(dǎo)翻譯。語(yǔ)法制導(dǎo)：基于語(yǔ)法分析中用到的文法產(chǎn)生式翻譯：完成語(yǔ)義分析的各項(xiàng)功能，不僅指生成中間代碼11/29/2022585.2語(yǔ)法制導(dǎo)翻譯語(yǔ)法制導(dǎo)翻譯語(yǔ)法制導(dǎo)：基于語(yǔ)法分析中用5.2語(yǔ)法制導(dǎo)翻譯屬性之間的依賴關(guān)系語(yǔ)義規(guī)則b:=f(c1,c2,…,ck)只有在已知c1,…,ck值的基礎(chǔ)上，才能計(jì)算屬性值b稱屬性b依賴于屬性c1,…,ck11/29/2022595.2語(yǔ)法制導(dǎo)翻譯屬性之間的依賴關(guān)系只有在已知c1,…5.2語(yǔ)法制導(dǎo)翻譯依賴圖（DependencyGraphs）:有向邊，a→b，表示屬性b依賴于屬性a用來(lái)表示屬性之間依賴關(guān)系的有向圖（DirectedGraph）稱為依賴圖11/29/2022605.2語(yǔ)法制導(dǎo)翻譯依賴圖（DependencyGrap5.2語(yǔ)法制導(dǎo)翻譯依賴圖的構(gòu)造算法：P284考慮的是分析樹(shù)中的結(jié)點(diǎn)一個(gè)屬性建立一個(gè)結(jié)點(diǎn)為每個(gè)語(yǔ)義動(dòng)作引入一個(gè)虛屬性例Fig.5.611/29/2022615.2語(yǔ)法制導(dǎo)翻譯依賴圖的構(gòu)造算法：P284例Fig.5.2語(yǔ)法制導(dǎo)翻譯依賴圖的例子：LE.val=19E.val=15T.val=4T.val=15F.val=4T.val=3F.val=3F.val=5digit.lexval=4digit.lexval=5digit.lexval=3+*Fig.5.3的依賴圖n11/29/2022625.2語(yǔ)法制導(dǎo)翻譯依賴圖的例子：LE.val=19E.v5.2語(yǔ)法制導(dǎo)翻譯依賴圖的例子：Fig.5.7（Fig.5.5的依賴圖）11/29/2022635.2語(yǔ)法制導(dǎo)翻譯依賴圖的例子：11/27/2022185.2語(yǔ)法制導(dǎo)翻譯屬性計(jì)算順序有向非循環(huán)圖（directedacyclicgraph）的拓?fù)渑判颍╰opologicalsort）：圖中所有結(jié)點(diǎn)的一個(gè)排列若mi→mj是一有向邊，則在結(jié)點(diǎn)序列中mi在mj的前面11/29/2022645.2語(yǔ)法制導(dǎo)翻譯屬性計(jì)算順序有向非循環(huán)圖（direct5.2語(yǔ)法制導(dǎo)翻譯例子：1234765拓?fù)渑判颍?65432175643214763521*依賴圖的任一拓?fù)渑判蚴且粋€(gè)合理的屬性計(jì)算順序

11/29/2022655.2語(yǔ)法制導(dǎo)翻譯例子：1234765拓?fù)渑判颍?65.2語(yǔ)法制導(dǎo)翻譯屬性計(jì)算實(shí)例：P286Example5.611/29/2022665.2語(yǔ)法制導(dǎo)翻譯屬性計(jì)算實(shí)例：11/27/2022215.2語(yǔ)法制導(dǎo)翻譯屬性計(jì)算的三種方法：1、分析樹(shù)法：（1）按基礎(chǔ)文法構(gòu)造句子（程序）的分析樹(shù)（語(yǔ)法分析）（2）按分析樹(shù)構(gòu)造依賴圖（3）對(duì)依賴圖進(jìn)行拓?fù)渑判颍玫秸Z(yǔ)義規(guī)則的執(zhí)行順序（4）按上述順序執(zhí)行語(yǔ)義規(guī)則，計(jì)算屬性值，得到句子的翻譯結(jié)果*如果依賴圖存在回路，這種方法會(huì)失敗11/29/2022675.2語(yǔ)法制導(dǎo)翻譯屬性計(jì)算的三種方法：*如果依賴圖存在5.2語(yǔ)法制導(dǎo)翻譯2、基于語(yǔ)義規(guī)則的方法（Rule-basedmethods）：語(yǔ)法分析和屬性計(jì)算分開(kāi)，先構(gòu)造分析樹(shù)，然后按預(yù)先定義的策略遍歷分析樹(shù)來(lái)計(jì)算屬性語(yǔ)義規(guī)則的定義和計(jì)算順序(翻譯模式)在編譯器構(gòu)造之前確定11/29/2022685.2語(yǔ)法制導(dǎo)翻譯2、基于語(yǔ)義規(guī)則的方法（Rule-ba5.2語(yǔ)法制導(dǎo)翻譯分析樹(shù)遍歷策略的確定（構(gòu)造編譯器時(shí)）要考慮語(yǔ)義規(guī)則的定義及計(jì)算順序，因此是基于規(guī)則的方法優(yōu)點(diǎn)：不構(gòu)造依賴圖，不對(duì)依賴圖進(jìn)行拓?fù)渑判?，提高了時(shí)空效率11/29/2022695.2語(yǔ)法制導(dǎo)翻譯分析樹(shù)遍歷策略的確定（構(gòu)造編譯器時(shí)）要5.2語(yǔ)法制導(dǎo)翻譯3、忽略語(yǔ)義規(guī)則的方法（Obliviousmethods）：在進(jìn)行語(yǔ)法分析的同時(shí)進(jìn)行翻譯，即邊分析邊計(jì)算屬性，計(jì)算次序由分析方法確定而與語(yǔ)義規(guī)則無(wú)關(guān)缺點(diǎn)：這樣確定計(jì)算次序?qū)⑾拗颇軐?shí)現(xiàn)的語(yǔ)法制導(dǎo)定義的種類(lèi)優(yōu)點(diǎn)：不構(gòu)造依賴圖，不對(duì)依賴圖進(jìn)行拓?fù)渑判?，提高了時(shí)空效率11/29/2022705.2語(yǔ)法制導(dǎo)翻譯3、忽略語(yǔ)義規(guī)則的方法（Oblivio5.2語(yǔ)法制導(dǎo)翻譯S-屬性定義（S-attributeddefinitions）：只含有綜合屬性的語(yǔ)法制導(dǎo)定義例：P281Fig.5.211/29/2022715.2語(yǔ)法制導(dǎo)翻譯S-屬性定義（S-attribute5.2語(yǔ)法制導(dǎo)翻譯只有綜合屬性時(shí)（以P282Fig.5.3的依賴圖為例）依賴圖中有向邊的走向和自底向上分析時(shí)建立分析樹(shù)的順序是一致的因此，可以考慮在進(jìn)行語(yǔ)法分析（自底向上）的同時(shí)進(jìn)行翻譯（執(zhí)行語(yǔ)義規(guī)則）11/29/2022725.2語(yǔ)法制導(dǎo)翻譯只有綜合屬性時(shí)（以P282Fig.5.2語(yǔ)法制導(dǎo)翻譯具體實(shí)現(xiàn)：擴(kuò)充LR分析器，為棧中的每一個(gè)文法符號(hào)增加一個(gè)屬性域，存放分析過(guò)程中該文法符號(hào)的綜合屬性值，當(dāng)用產(chǎn)生式進(jìn)行歸約時(shí)，產(chǎn)生式左邊文法符號(hào)入棧，其屬性值由棧中正在歸約的產(chǎn)生式右邊符號(hào)的屬性值計(jì)算11/29/2022735.2語(yǔ)法制導(dǎo)翻譯具體實(shí)現(xiàn)：擴(kuò)充LR分析器，為棧中的每5.2語(yǔ)法制導(dǎo)翻譯例子1：P294……XX.xYY.yZZ.z…………AA.a………………toptop11/29/2022745.2語(yǔ)法制導(dǎo)翻譯例子1：……XX.xYY.y5.2語(yǔ)法制導(dǎo)翻譯例子2：P295-296Fig.5.16Fig.5.17ntop=top–r+1r是產(chǎn)生式右部符號(hào)個(gè)數(shù)PRODUCTION SEMANTICRULELEn print(val[top])EE1+T val[ntop]=val[top-2]+val[top]

ET TT1*F val[ntop]=val[top-2]*val[top]

TF F(E) val[ntop]=val[top-1] Fdigit 11/29/2022755.2語(yǔ)法制導(dǎo)翻譯例子2：P295-296Fig.55.2語(yǔ)法制導(dǎo)翻譯**Fig.5.16是Fig.5.2的一種具體實(shí)現(xiàn)方法11/29/2022765.2語(yǔ)法制導(dǎo)翻譯**Fig.5.16是Fig.55.2語(yǔ)法制導(dǎo)翻譯L-屬性定義（L-attributeddefinitions）：是一種語(yǔ)法制導(dǎo)定義對(duì)于產(chǎn)生式A→X1X2…Xn右部Xj的繼承屬性，它依賴于： 1、X1，X2，…，Xj-1（Xj左邊的文法符號(hào)）的屬性 2、A的繼承屬性**L-屬性定義包含S-屬性定義11/29/2022775.2語(yǔ)法制導(dǎo)翻譯L-屬性定義（L-attribute5.2語(yǔ)法制導(dǎo)翻譯例子：P298Fig.5.19（非L-屬性定義）11/29/2022785.2語(yǔ)法制導(dǎo)翻譯例子：（非L-屬性定義）11/27/25.2語(yǔ)法制導(dǎo)翻譯翻譯模式（translationscheme）：將語(yǔ)義規(guī)則放到{}中，并插入到產(chǎn)生式右部的適當(dāng)位置，以反映語(yǔ)義規(guī)則的計(jì)算順序，這種書(shū)寫(xiě)形式稱之為翻譯模式翻譯模式與語(yǔ)法制導(dǎo)定義的區(qū)別：翻譯模式中指明了語(yǔ)義規(guī)則的執(zhí)行順序11/29/2022795.2語(yǔ)法制導(dǎo)翻譯翻譯模式（translationsc5.2語(yǔ)法制導(dǎo)翻譯例子：P298例5.12（5.1）是一個(gè)翻譯模式用此翻譯模式去分析一個(gè)句子（9-5+2）把語(yǔ)義動(dòng)作作為終結(jié)符號(hào)11/29/2022805.2語(yǔ)法制導(dǎo)翻譯例子：P298例5.12用此翻譯模ETR9{print(“9”)}-T{print(“-”)}{print(“5”)}{print(“+”)}{print(“2”)}52RT12345對(duì)分析樹(shù)（Fig.5.20）進(jìn)行深度優(yōu)先遍歷，執(zhí)行語(yǔ)義動(dòng)作，完成翻譯工作（95-2+）（5.1）是一個(gè)適合以深度優(yōu)先順序計(jì)算屬性的翻譯模式R+11/29/202281ETR9{print(“9”)}-T{print(“-”)}5.2語(yǔ)法制導(dǎo)翻譯為L(zhǎng)-屬性定義構(gòu)造翻譯模式：適合以深度優(yōu)先順序計(jì)算屬性的翻譯模式需滿足的條件：1、產(chǎn)生式右部文法符號(hào)的繼承屬性必須在這個(gè)符號(hào)以前的動(dòng)作中計(jì)算出來(lái)；2、一個(gè)動(dòng)作不能引用該動(dòng)作右邊符號(hào)的綜合屬性；3、產(chǎn)生式左部非終結(jié)符號(hào)的綜合屬性只有在其引用的所有屬性都計(jì)算出來(lái)以后才能計(jì)算。計(jì)算該屬性的動(dòng)作通常放在產(chǎn)生式右部的末尾11/29/2022825.2語(yǔ)法制導(dǎo)翻譯為L(zhǎng)-屬性定義構(gòu)造翻譯模式：適合以深5.2語(yǔ)法制導(dǎo)翻譯從L-屬性定義出發(fā)，構(gòu)造一個(gè)滿足要求的翻譯模式**L-屬性定義本身考慮到了滿足這些條件（第一條件）將計(jì)算產(chǎn)生式右邊某文法符號(hào)的