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

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

11/29/2022205.2語法制導翻譯例子：1234765拓撲排序：765.2語法制導翻譯屬性計算實例：P286Example5.611/29/2022215.2語法制導翻譯屬性計算實例：11/27/2022215.2語法制導翻譯屬性計算的三種方法：1、分析樹法：（1）按基礎文法構造句子（程序）的分析樹（語法分析）（2）按分析樹構造依賴圖（3）對依賴圖進行拓撲排序，得到語義規(guī)則的執(zhí)行順序（4）按上述順序執(zhí)行語義規(guī)則，計算屬性值，得到句子的翻譯結果*如果依賴圖存在回路，這種方法會失敗11/29/2022225.2語法制導翻譯屬性計算的三種方法：*如果依賴圖存在5.2語法制導翻譯2、基于語義規(guī)則的方法（Rule-basedmethods）：語法分析和屬性計算分開，先構造分析樹，然后按預先定義的策略遍歷分析樹來計算屬性語義規(guī)則的定義和計算順序(翻譯模式)在編譯器構造之前確定11/29/2022235.2語法制導翻譯2、基于語義規(guī)則的方法（Rule-ba5.2語法制導翻譯分析樹遍歷策略的確定（構造編譯器時）要考慮語義規(guī)則的定義及計算順序，因此是基于規(guī)則的方法優(yōu)點：不構造依賴圖，不對依賴圖進行拓撲排序，提高了時空效率11/29/2022245.2語法制導翻譯分析樹遍歷策略的確定（構造編譯器時）要5.2語法制導翻譯3、忽略語義規(guī)則的方法（Obliviousmethods）：在進行語法分析的同時進行翻譯，即邊分析邊計算屬性，計算次序由分析方法確定而與語義規(guī)則無關缺點：這樣確定計算次序?qū)⑾拗颇軐崿F(xiàn)的語法制導定義的種類優(yōu)點：不構造依賴圖，不對依賴圖進行拓撲排序，提高了時空效率11/29/2022255.2語法制導翻譯3、忽略語義規(guī)則的方法（Oblivio5.2語法制導翻譯S-屬性定義（S-attributeddefinitions）：只含有綜合屬性的語法制導定義例：P281Fig.5.211/29/2022265.2語法制導翻譯S-屬性定義（S-attribute5.2語法制導翻譯只有綜合屬性時（以P282Fig.5.3的依賴圖為例）依賴圖中有向邊的走向和自底向上分析時建立分析樹的順序是一致的因此，可以考慮在進行語法分析（自底向上）的同時進行翻譯（執(zhí)行語義規(guī)則）11/29/2022275.2語法制導翻譯只有綜合屬性時（以P282Fig.5.2語法制導翻譯具體實現(xiàn)：擴充LR分析器，為棧中的每一個文法符號增加一個屬性域，存放分析過程中該文法符號的綜合屬性值，當用產(chǎn)生式進行歸約時，產(chǎn)生式左邊文法符號入棧，其屬性值由棧中正在歸約的產(chǎn)生式右邊符號的屬性值計算11/29/2022285.2語法制導翻譯具體實現(xiàn)：擴充LR分析器，為棧中的每5.2語法制導翻譯例子1：P294……XX.xYY.yZZ.z…………AA.a………………toptop11/29/2022295.2語法制導翻譯例子1：……XX.xYY.y5.2語法制導翻譯例子2：P295-296Fig.5.16Fig.5.17ntop=top–r+1r是產(chǎn)生式右部符號個數(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語法制導翻譯例子2：P295-296Fig.55.2語法制導翻譯**Fig.5.16是Fig.5.2的一種具體實現(xiàn)方法11/29/2022315.2語法制導翻譯**Fig.5.16是Fig.55.2語法制導翻譯L-屬性定義（L-attributeddefinitions）：是一種語法制導定義對于產(chǎn)生式A→X1X2…Xn右部Xj的繼承屬性，它依賴于： 1、X1，X2，…，Xj-1（Xj左邊的文法符號）的屬性 2、A的繼承屬性**L-屬性定義包含S-屬性定義11/29/2022325.2語法制導翻譯L-屬性定義（L-attribute5.2語法制導翻譯例子：P298Fig.5.19（非L-屬性定義）11/29/2022335.2語法制導翻譯例子：（非L-屬性定義）11/27/25.2語法制導翻譯翻譯模式（translationscheme）：將語義規(guī)則放到{}中，并插入到產(chǎn)生式右部的適當位置，以反映語義規(guī)則的計算順序，這種書寫形式稱之為翻譯模式翻譯模式與語法制導定義的區(qū)別：翻譯模式中指明了語義規(guī)則的執(zhí)行順序11/29/2022345.2語法制導翻譯翻譯模式（translationsc5.2語法制導翻譯例子：P298例5.12（5.1）是一個翻譯模式用此翻譯模式去分析一個句子（9-5+2）把語義動作作為終結符號11/29/2022355.2語法制導翻譯例子：P298例5.12用此翻譯模ETR9{print(“9”)}-T{print(“-”)}{print(“5”)}{print(“+”)}{print(“2”)}52RT12345對分析樹（Fig.5.20）進行深度優(yōu)先遍歷，執(zhí)行語義動作，完成翻譯工作（95-2+）（5.1）是一個適合以深度優(yōu)先順序計算屬性的翻譯模式R+11/29/202236ETR9{print(“9”)}-T{print(“-”)}5.2語法制導翻譯為L-屬性定義構造翻譯模式：適合以深度優(yōu)先順序計算屬性的翻譯模式需滿足的條件：1、產(chǎn)生式右部文法符號的繼承屬性必須在這個符號以前的動作中計算出來；2、一個動作不能引用該動作右邊符號的綜合屬性；3、產(chǎn)生式左部非終結符號的綜合屬性只有在其引用的所有屬性都計算出來以后才能計算。計算該屬性的動作通常放在產(chǎn)生式右部的末尾11/29/2022375.2語法制導翻譯為L-屬性定義構造翻譯模式：適合以深5.2語法制導翻譯從L-屬性定義出發(fā)，構造一個滿足要求的翻譯模式**L-屬性定義本身考慮到了滿足這些條件（第一條件）將計算產(chǎn)生式右邊某文法符號的繼承屬性的語義規(guī)則插入到此符號之前（第二條件）L-屬性定義本身滿足（第三條件）將計算產(chǎn)生式左邊非終結符號綜合屬性的語義規(guī)則放在產(chǎn)生式右端的末尾11/29/2022385.2語法制導翻譯從L-屬性定義出發(fā)，構造一個滿足要求5.2語法制導翻譯例子：P300-301例5.13Fig.5.22----語法制導定義（L-屬性定義）Fig.5.23----翻譯模式11/29/2022395.2語法制導翻譯例子：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語法制導翻譯分析一個句子：textsubtexttextSBB2B1textB3subB4texttext分析樹11/29/2022415.2語法制導翻譯分析一個句子：textsubtex帶語義動作的分析樹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)先計算屬性11/29/202242帶語義動作的分析樹SB{B.ps:=10}{S.ht:=B.TheEnd!11/29/202243TheEnd!11/27/202243編譯原理課件CHAPTER5(SemanticAnalysisandIntermediateCodeGeneration-1)編譯原理課件CHAPTER5(SemanticAnalysisandIntermediateCodeGeneration-1)5.1語義分析概述詞法分析、語法分析——程序在書寫上是正確的、在語法上是正確的，不能保證含義（語義）上的正確性11/29/2022465.1語義分析概述詞法分析、語法分析——程序在書寫上5.1語義分析概述語義分析階段分析源程序的含義，并作相應的處理，語義分析的基本功能：確定類型：確定標識符所關聯(lián)數(shù)據(jù)對象的類型，即處理源程序的說明部分類型檢查：對運算及進行運算的運算分量進行類型檢查，檢查運算的合法性與運算分量類型的一致性（相容性），必要時作相應的類型轉(zhuǎn)換11/29/2022475.1語義分析概述語義分析階段分析源程序的含義，并作相應5.1語義分析概述識別含義：確定程序中各構成成分組合到一起的含義，對可執(zhí)行語句生成中間代碼或目標代碼*語義分析往往是和中間代碼生成緊密聯(lián)系的其他一些靜態(tài)語義檢查：控制流檢查：如對于PASCAL語言，不允許從循環(huán)外跳轉(zhuǎn)到循環(huán)內(nèi)，C語言的Break引起控制離開最小包圍的while、for等語句，檢查是否這樣的語句存在唯一性檢查：如標識符只能定義一次，枚舉類型的元素不能重復等11/29/2022485.1語義分析概述識別含義：確定程序中各構成成分組合到一5.1語義分析概述語義分析的輸入是語法分析的輸出（分析樹），輸出是中間代碼，但同時它還完成了很多語義處理工作（見上）語義分析的主流技術——語法制導翻譯技術11/29/2022495.1語義分析概述語義分析的輸入是語法分析的輸出（分析樹5.2語法制導翻譯文法符號的屬性：文法符號（GrammarSymbols）代表語言結構（LanguageConstruct），如標識符、表達式、語句、程序為每個文法符號引入一個屬性（attribute）集合，反映相應語言結構的語義信息，如標識符的類型、常量的值、變量的存儲地址等11/29/2022505.2語法制導翻譯文法符號的屬性：文法符號（Gramma屬性的類型（從分析過程中屬性值的計算方法來分類）：5.2語法制導翻譯 1、綜合屬性（SynthesizedAttributes）：屬性值是分析樹中該結點的子結點的屬性值的函數(shù) 2、繼承屬性（InheritedAttributes）：屬性值是分析樹中該結點的父結點和/或兄弟結點的屬性值的函數(shù)11/29/202251屬性的類型（從分析過程中屬性值的計算方法來分類）：5.25.2語法制導翻譯對于產(chǎn)生式AX1X2…XnAX1X2Xn…計算A的綜合屬性,S(A):=f(I(X1),…,I(Xn))計算Xj的繼承屬性,T(Xj):=f(I(A),...,I(Xn))綜合屬性用于“自下而上”傳遞信息，繼承屬性用于“自上而下”傳遞信息11/29/2022525.2語法制導翻譯對于產(chǎn)生式AX1X2…XnAX5.2語法制導翻譯非終結符（開始符號除外）既可有綜合屬性也可有繼承屬性文法開始符號沒有繼承屬性終結符號只有綜合屬性，一般由詞法分析器提供11/29/2022535.2語法制導翻譯非終結符（開始符號除外）既可有綜合屬性5.2語法制導翻譯語法制導定義：為每一條產(chǎn)生式（Aα）引入一套語義規(guī)則規(guī)則形式：b:=f(c1,c2,…,ck)b是A的綜合屬性，則c1,c2,…,ck是產(chǎn)生式文法符號的屬性b是產(chǎn)生式右部某文法符號的繼承屬性，則c1,c2,…,ck是產(chǎn)生式文法符號的屬性11/29/2022545.2語法制導翻譯語法制導定義：規(guī)則形式：b:=f5.2語法制導翻譯虛（綜合）屬性（Dummysynthesizedattribute）：針對語義動作（過程或語義子程序）只是為了形式上的統(tǒng)一語義規(guī)則可以計算屬性值，也可以（語義動作）在符號表中登錄信息、輸出錯誤信息、進行類型檢查、產(chǎn)生中間代碼等11/29/2022555.2語法制導翻譯虛（綜合）屬性語義規(guī)則可以計算屬性值，5.2語法制導翻譯例1P281Fig.5.2（只有綜合屬性）虛屬性終結符號的屬性某些非終結符加下標是為了區(qū)分一個產(chǎn)生式中同一非終結符的多次出現(xiàn)例2P283Fig.5.4（帶有繼承屬性）11/29/2022565.2語法制導翻譯例1P281Fig.5.25.2語法制導翻譯屬性文法：語法制導定義對上下文無關文法進行了擴充，擴充后的文法稱為屬性文法（attributegrammar）。11/29/2022575.2語法制導翻譯屬性文法：語法制導定義對上下文無關文法5.2語法制導翻譯語法制導翻譯（Syntax-DirectedTranslation）:根據(jù)語法分析中產(chǎn)生式對應的語義規(guī)則進行翻譯的方法稱為語法制導翻譯。語法制導：基于語法分析中用到的文法產(chǎn)生式翻譯：完成語義分析的各項功能，不僅指生成中間代碼11/29/2022585.2語法制導翻譯語法制導翻譯語法制導：基于語法分析中用5.2語法制導翻譯屬性之間的依賴關系語義規(guī)則b:=f(c1,c2,…,ck)只有在已知c1,…,ck值的基礎上，才能計算屬性值b稱屬性b依賴于屬性c1,…,ck11/29/2022595.2語法制導翻譯屬性之間的依賴關系只有在已知c1,…5.2語法制導翻譯依賴圖（DependencyGraphs）:有向邊，a→b，表示屬性b依賴于屬性a用來表示屬性之間依賴關系的有向圖（DirectedGraph）稱為依賴圖11/29/2022605.2語法制導翻譯依賴圖（DependencyGrap5.2語法制導翻譯依賴圖的構造算法：P284考慮的是分析樹中的結點一個屬性建立一個結點為每個語義動作引入一個虛屬性例Fig.5.611/29/2022615.2語法制導翻譯依賴圖的構造算法：P284例Fig.5.2語法制導翻譯依賴圖的例子：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語法制導翻譯依賴圖的例子：LE.val=19E.v5.2語法制導翻譯依賴圖的例子：Fig.5.7（Fig.5.5的依賴圖）11/29/2022635.2語法制導翻譯依賴圖的例子：11/27/2022185.2語法制導翻譯屬性計算順序有向非循環(huán)圖（directedacyclicgraph）的拓撲排序（topologicalsort）：圖中所有結點的一個排列若mi→mj是一有向邊，則在結點序列中mi在mj的前面11/29/2022645.2語法制導翻譯屬性計算順序有向非循環(huán)圖（direct5.2語法制導翻譯例子：1234765拓撲排序：765432175643214763521*依賴圖的任一拓撲排序是一個合理的屬性計算順序

11/29/2022655.2語法制導翻譯例子：1234765拓撲排序：765.2語法制導翻譯屬性計算實例：P286Example5.611/29/2022665.2語法制導翻譯屬性計算實例：11/27/2022215.2語法制導翻譯屬性計算的三種方法：1、分析樹法：（1）按基礎文法構造句子（程序）的分析樹（語法分析）（2）按分析樹構造依賴圖（3）對依賴圖進行拓撲排序，得到語義規(guī)則的執(zhí)行順序（4）按上述順序執(zhí)行語義規(guī)則，計算屬性值，得到句子的翻譯結果*如果依賴圖存在回路，這種方法會失敗11/29/2022675.2語法制導翻譯屬性計算的三種方法：*如果依賴圖存在5.2語法制導翻譯2、基于語義規(guī)則的方法（Rule-basedmethods）：語法分析和屬性計算分開，先構造分析樹，然后按預先定義的策略遍歷分析樹來計算屬性語義規(guī)則的定義和計算順序(翻譯模式)在編譯器構造之前確定11/29/2022685.2語法制導翻譯2、基于語義規(guī)則的方法（Rule-ba5.2語法制導翻譯分析樹遍歷策略的確定（構造編譯器時）要考慮語義規(guī)則的定義及計算順序，因此是基于規(guī)則的方法優(yōu)點：不構造依賴圖，不對依賴圖進行拓撲排序，提高了時空效率11/29/2022695.2語法制導翻譯分析樹遍歷策略的確定（構造編譯器時）要5.2語法制導翻譯3、忽略語義規(guī)則的方法（Obliviousmethods）：在進行語法分析的同時進行翻譯，即邊分析邊計算屬性，計算次序由分析方法確定而與語義規(guī)則無關缺點：這樣確定計算次序?qū)⑾拗颇軐崿F(xiàn)的語法制導定義的種類優(yōu)點：不構造依賴圖，不對依賴圖進行拓撲排序，提高了時空效率11/29/2022705.2語法制導翻譯3、忽略語義規(guī)則的方法（Oblivio5.2語法制導翻譯S-屬性定義（S-attributeddefinitions）：只含有綜合屬性的語法制導定義例：P281Fig.5.211/29/2022715.2語法制導翻譯S-屬性定義（S-attribute5.2語法制導翻譯只有綜合屬性時（以P282Fig.5.3的依賴圖為例）依賴圖中有向邊的走向和自底向上分析時建立分析樹的順序是一致的因此，可以考慮在進行語法分析（自底向上）的同時進行翻譯（執(zhí)行語義規(guī)則）11/29/2022725.2語法制導翻譯只有綜合屬性時（以P282Fig.5.2語法制導翻譯具體實現(xiàn)：擴充LR分析器，為棧中的每一個文法符號增加一個屬性域，存放分析過程中該文法符號的綜合屬性值，當用產(chǎn)生式進行歸約時，產(chǎn)生式左邊文法符號入棧，其屬性值由棧中正在歸約的產(chǎn)生式右邊符號的屬性值計算11/29/2022735.2語法制導翻譯具體實現(xiàn)：擴充LR分析器，為棧中的每5.2語法制導翻譯例子1：P294……XX.xYY.yZZ.z…………AA.a………………toptop11/29/2022745.2語法制導翻譯例子1：……XX.xYY.y5.2語法制導翻譯例子2：P295-296Fig.5.16Fig.5.17ntop=top–r+1r是產(chǎn)生式右部符號個數(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語法制導翻譯例子2：P295-296Fig.55.2語法制導翻譯**Fig.5.16是Fig.5.2的一種具體實現(xiàn)方法11/29/2022765.2語法制導翻譯**Fig.5.16是Fig.55.2語法制導翻譯L-屬性定義（L-attributeddefinitions）：是一種語法制導定義對于產(chǎn)生式A→X1X2…Xn右部Xj的繼承屬性，它依賴于： 1、X1，X2，…，Xj-1（Xj左邊的文法符號）的屬性 2、A的繼承屬性**L-屬性定義包含S-屬性定義11/29/2022775.2語法制導翻譯L-屬性定義（L-attribute5.2語法制導翻譯例子：P298Fig.5.19（非L-屬性定義）11/29/2022785.2語法制導翻譯例子：（非L-屬性定義）11/27/25.2語法制導翻譯翻譯模式（translationscheme）：將語義規(guī)則放到{}中，并插入到產(chǎn)生式右部的適當位置，以反映語義規(guī)則的計算順序，這種書寫形式稱之為翻譯模式翻譯模式與語法制導定義的區(qū)別：翻譯模式中指明了語義規(guī)則的執(zhí)行順序11/29/2022795.2語法制導翻譯翻譯模式（translationsc5.2語法制導翻譯例子：P298例5.12（5.1）是一個翻譯模式用此翻譯模式去分析一個句子（9-5+2）把語義動作作為終結符號11/29/2022805.2語法制導翻譯例子：P298例5.12用此翻譯模ETR9{print(“9”)}-T{print(“-”)}{print(“5”)}{print(“+”)}{print(“2”)}52RT12345對分析樹（Fig.5.20）進行深度優(yōu)先遍歷，執(zhí)行語義動作，完成翻譯工作（95-2+）（5.1）是一個適合以深度優(yōu)先順序計算屬性的翻譯模式R+11/29/202281ETR9{print(“9”)}-T{print(“-”)}5.2語法制導翻譯為L-屬性定義構造翻譯模式：適合以深度優(yōu)先順序計算屬性的翻譯模式需滿足的條件：1、產(chǎn)生式右部文法符號的繼承屬性必須在這個符號以前的動作中計算出來；2、一個動作不能引用該動作右邊符號的綜合屬性；3、產(chǎn)生式左部非終結符號的綜合屬性只有在其引用的所有屬性都計算出來以后才能計算。計算該屬性的動作通常放在產(chǎn)生式右部的末尾11/29/2022825.2語法制導翻譯為L-屬性定義構造翻譯模式：適合以深5.2語法制導翻譯從L-屬性定義出發(fā)，構造一個滿足要求的翻譯模式**L-屬性定義本身考慮到了滿足這些條件（第一條件）將計算產(chǎn)生式右邊某文法符號的