編譯原理ppt99

1、第六章第六章 屬性文法和語法制導(dǎo)翻譯屬性文法和語法制導(dǎo)翻譯編譯程序的功能和組織結(jié)構(gòu)編譯程序的功能和組織結(jié)構(gòu)表表 處處 理理詞詞法法分分析析源源程程序序目目標(biāo)標(biāo)程程序序錯錯 誤誤 處處 理理語語法法分分析析語義語義分析分析和和中間中間代碼代碼生成生成目目標(biāo)標(biāo)代代碼碼生生成成前前 端端后后 端端中中間間代代碼碼優(yōu)優(yōu)化化本章學(xué)習(xí)內(nèi)容本章學(xué)習(xí)內(nèi)容v本章介紹有關(guān)本章介紹有關(guān)語義描述語義描述及及語義處理語義處理的問題。的問題。其處理的方法主要是其處理的方法主要是屬性文法屬性文法和和語法制導(dǎo)翻譯語法制導(dǎo)翻譯。v掌握：掌握：屬性文法屬性文法,語法制導(dǎo)翻譯的概念語法制導(dǎo)翻譯的概念v理解：理解：如何在自下而上分析

2、中實(shí)現(xiàn)如何在自下而上分析中實(shí)現(xiàn)S-屬性屬性計算。計算。v 6.1 6.1 屬性文法屬性文法v 6.2 6.2 語法制導(dǎo)翻譯的概述語法制導(dǎo)翻譯的概述v 6.3 6.3 S-S-屬性文法的自下向上的計算屬性文法的自下向上的計算6.16.1 屬性文法屬性文法屬性文法屬性文法: : 是在是在上下文無關(guān)文法上下文無關(guān)文法的基礎(chǔ)上為每個文法符的基礎(chǔ)上為每個文法符號配備若干個相關(guān)的號配備若干個相關(guān)的 “值值”（稱為（稱為屬性屬性）; ;對于對于文法的每一個產(chǎn)生式配備一組文法的每一個產(chǎn)生式配備一組屬性的屬性的“計算規(guī)計算規(guī)則則”( (稱為稱為語義規(guī)則語義規(guī)則) )。屬性和變量一樣，可以進(jìn)行計算和傳遞。屬性和變

3、量一樣，可以進(jìn)行計算和傳遞。屬性加工的過程即是語義處理的過程屬性加工的過程即是語義處理的過程代表與文法符號相關(guān)的信息，例如它的類型、代表與文法符號相關(guān)的信息，例如它的類型、值、代碼序列值、代碼序列 、符號表內(nèi)容等等。、符號表內(nèi)容等等。6.16.1 屬性文法屬性文法v屬性：屬性：綜合屬性綜合屬性: :用于用于“自下而上自下而上”傳遞信息傳遞信息 繼承屬性繼承屬性: :用于用于“自上而下自上而下”傳遞信息傳遞信息 繼承屬性和綜合屬性 例： E P P.env := E.env; E.val := P.val; E1 P+E2 P.env := E1.env E2.env := E1.env E1.

4、val :=P.val+E2.val P n P.val :=n.val P id P.val :=Lookup(P.env,) P (E) E.env := P.env P.val := E.val6.16.1 屬性文法屬性文法v語義規(guī)則語義規(guī)則: : 對應(yīng)于每個產(chǎn)生式對應(yīng)于每個產(chǎn)生式A A都有一套與之相關(guān)聯(lián)都有一套與之相關(guān)聯(lián)的語義規(guī)則，每條語義規(guī)則的形式為：的語義規(guī)則，每條語義規(guī)則的形式為： b:=f(cb:=f(c1 1,c,c2 2, ,c,ck k) )這里這里f f是一個函數(shù)，并滿足下面的條件之一是一個函數(shù)，并滿足下面的條件之一: :（1 1）b b是是A A的一個的

5、一個綜合屬性綜合屬性并且并且c c1 1,c,c2 2, ,c ck k是產(chǎn)生式是產(chǎn)生式右邊文法符號的屬性；右邊文法符號的屬性；（2 2）b b是產(chǎn)生式右邊某個文法符號的一個是產(chǎn)生式右邊某個文法符號的一個繼承屬性繼承屬性并且并且c c1 1,c,c2 2, ,c ck k是是A A或產(chǎn)生式右邊任何文法符號的或產(chǎn)生式右邊任何文法符號的屬性屬性在這兩種情況下，我們都說屬性在這兩種情況下，我們都說屬性b b依賴依賴于屬性于屬性c c1 1,c,c2 2,c,ck k. .用于用于“自下而上自下而上”傳遞信息傳遞信息 用于用于“自上而下自上而下”傳遞信息傳遞信息 6.16.1 屬性文法屬性文法特別強(qiáng)調(diào)

6、：特別強(qiáng)調(diào)：終結(jié)符終結(jié)符只有綜合屬性，由詞法分析器提供；只有綜合屬性，由詞法分析器提供；非終結(jié)符非終結(jié)符既可有綜合屬性也可有繼承屬性，文法開始符既可有綜合屬性也可有繼承屬性，文法開始符號的所有繼承屬性作為屬性計算前的初始值。號的所有繼承屬性作為屬性計算前的初始值。v屬性計算規(guī)則中只能使用屬性計算規(guī)則中只能使用相應(yīng)相應(yīng)產(chǎn)生式的文法符號的產(chǎn)生式的文法符號的屬性。屬性。一般而言：一般而言：v出現(xiàn)在出現(xiàn)在產(chǎn)生式右邊的繼承屬性產(chǎn)生式右邊的繼承屬性和出現(xiàn)在和出現(xiàn)在產(chǎn)生式左邊產(chǎn)生式左邊的綜合屬性的綜合屬性都必須提供一個計算規(guī)則都必須提供一個計算規(guī)則. .v出現(xiàn)在出現(xiàn)在產(chǎn)生式左邊的繼承屬性產(chǎn)生式左邊的繼承屬性

7、和出現(xiàn)和出現(xiàn)在產(chǎn)生式右邊在產(chǎn)生式右邊的綜合屬性的綜合屬性由其它產(chǎn)生式的屬性規(guī)則計算或由屬性由其它產(chǎn)生式的屬性規(guī)則計算或由屬性計算器的參數(shù)提供計算器的參數(shù)提供產(chǎn)生式產(chǎn)生式 語義規(guī)則語義規(guī)則6.16.1 屬性文法屬性文法 例例 6 .2 輸入：輸入：3*5+4ndigitlexval:=3F val:=3Tval:=3digitlexval:=5Fval:=5Tval:=15*Eval:=15+digitlexval:=4Fval:=4Tval:=4Eval:=19例例 6 .2 輸入：輸入：3*5+4nLn對于對于s-屬性定義屬性定義通常使用通常使用自下而上的分析方法自下而上的分析方法在在建立建

8、立每一個每一個結(jié)點(diǎn)處結(jié)點(diǎn)處綜合綜合屬性值屬性值使用使用語義規(guī)則語義規(guī)則來計算來計算 即在即在 用用后，就執(zhí)行那后，就執(zhí)行那個產(chǎn)生式的個產(chǎn)生式的s-屬性規(guī)則定義計算屬性的值，從屬性規(guī)則定義計算屬性的值，從進(jìn)行計算進(jìn)行計算。 例例 文法文法 DTL T int | real L L1,id | id 描述說明語句中各種變量的類型信息的描述說明語句中各種變量的類型信息的語義規(guī)則如下語義規(guī)則如下: 產(chǎn)生式產(chǎn)生式 語義規(guī)則語義規(guī)則 DTL L in:=T type T int T type :=integer T real T type :=real L L1,id L1 in :=L in addty

9、pe(id entry,L in) L id addtype(id entry,L in)分析分析real i1, i2, i3 產(chǎn)生式產(chǎn)生式 語義規(guī)則語義規(guī)則 v 翻譯的任務(wù)翻譯的任務(wù)：對對語法結(jié)構(gòu)語法結(jié)構(gòu)進(jìn)行進(jìn)行靜態(tài)靜態(tài)語義分語義分析和正確性檢查，若正確，則翻譯成中間代碼或析和正確性檢查，若正確，則翻譯成中間代碼或目標(biāo)代碼。目標(biāo)代碼。v 使用的方法使用的方法: :語法制導(dǎo)翻譯。語法制導(dǎo)翻譯。 語法制導(dǎo)翻譯語法制導(dǎo)翻譯: : 由源程序的語法結(jié)構(gòu)所驅(qū)由源程序的語法結(jié)構(gòu)所驅(qū)動的翻譯方式。動的翻譯方式。6.2 語法制導(dǎo)翻譯概述語法制導(dǎo)翻譯概述6.2 語法制導(dǎo)翻譯的概述語法制導(dǎo)翻譯的概述 語法制導(dǎo)翻

10、譯把語言的一些屬性附加到代表語法結(jié)構(gòu)的文法符號上，這些屬性值是由附加到文法產(chǎn)生式的“語義規(guī)則”中計算的，也就是為每個產(chǎn)生式配備翻譯子程序，即語義子程序。對輸入串的翻譯也就是根據(jù)語義規(guī)則進(jìn)行計算得出結(jié)果。 這種由源程序的語法結(jié)構(gòu)所驅(qū)動的處理辦法就是語法制導(dǎo)翻譯法。 語義規(guī)則的計算可能產(chǎn)生代碼、在符號表中存放信息、給出錯誤信息或執(zhí)行任何其它動作。 6.3 S-屬性文法屬性文法的自下向上的計算的自下向上的計算v綜合屬性值的計算正好可以和自下而上分析綜合屬性值的計算正好可以和自下而上分析建立分析樹結(jié)點(diǎn)的過程同步。建立分析樹結(jié)點(diǎn)的過程同步。v因此因此,S-屬性文法屬性文法的翻譯器通?？山柚诘姆g器通常

11、可借助于LR分分析器實(shí)現(xiàn)。在析器實(shí)現(xiàn)。在S-屬性文法屬性文法的基礎(chǔ)上，將的基礎(chǔ)上，將LR分分析器改造為一個翻譯器，在對輸入串進(jìn)行語析器改造為一個翻譯器，在對輸入串進(jìn)行語法分析的同時對屬性進(jìn)行計算（語法分析的法分析的同時對屬性進(jìn)行計算（語法分析的同時進(jìn)行語義分析）同時進(jìn)行語義分析） 。只含有綜合屬性的屬性文法只含有綜合屬性的屬性文法增加屬性值棧，屬性值放到與符號棧同步操作的屬性值棧中，當(dāng)Si對應(yīng)的符號為Xi時，Vali中就存放與Xi對應(yīng)的屬性值。分析棧結(jié)構(gòu)為：狀態(tài)棧符號棧 屬性值棧SmXmXm.valS1X1X1.valS0#-將LR分析器能力擴(kuò)大，增加在歸約前調(diào)用語義規(guī)則的功能 6.3 S-屬

12、性文法屬性文法的自下向上的計算的自下向上的計算產(chǎn)生式產(chǎn)生式 語義規(guī)則語義規(guī)則例例 考慮一下前面臺式計算器的考慮一下前面臺式計算器的屬性文法的具體實(shí)現(xiàn)屬性文法的具體實(shí)現(xiàn)。 狀態(tài)棧符號棧屬性值棧SmXmXm.valS1X1X1.valS0#-用第五章中的技術(shù)用第五章中的技術(shù)來為上述文法構(gòu)造來為上述文法構(gòu)造LR分析器。分析器。 產(chǎn)生式產(chǎn)生式 語義規(guī)則語義規(guī)則 為了實(shí)現(xiàn)方便，對語為了實(shí)現(xiàn)方便，對語義規(guī)則稍做改動義規(guī)則稍做改動: 用用val數(shù)組中的一個數(shù)組中的一個位置來代替規(guī)則中的位置來代替規(guī)則中的每一個屬性。每一個屬性。 修改分析程序，修改分析程序，使其在作相應(yīng)的使其在作相應(yīng)的歸約歸約以前執(zhí)行表以前執(zhí)

13、行表6.5所示的代碼所示的代碼段。段。符號棧符號棧例 簡單算術(shù)表達(dá)式求值的屬性文法1)L E print(E.val)2)EE1+T E.val :E1.val +T.val 3)ET E.val :T.val 4)TT1*digit T.val :T1.val * digit.lexval 5)Tdigit T.val :digit.lexval 狀態(tài)ACTION GOTO d+*#ET0S3 12 1S4 acc2r3 S5r3 33r5r5 r54S3 75S6 6 r4r4 r47r2S5r2步驟 狀態(tài)棧語義棧 符號棧剩余輸入串ActionGOTO00-#23*5S3103- -#23

14、*5r52202-2#T3*5r31301-2#E3*5S44014-2-#E+3*5S350143-2- -#E+3*5r5760147-2-3#E+T*5S5701475-2-3-#E+T*5S68014756 - 2-3-#E+T*5r4790147-2-15#E+T#r211001-17#E#acc分析并計算分析并計算23*5的過程如下的過程如下:L E print(E.val)EE1+T E.val :E1.val +T.val ET E.val :T.val TT1*digit T.val :T1.val * digit.lexval Tdigit T.val :digit.lexval 6.3 S-屬性文法屬性文法的自下向上的計算的自下向上的計算練習(xí) 在一個移進(jìn)歸約的分析中采用以下的屬性文法，在某產(chǎn)生式歸約時，立即執(zhí)行括號中的動作。 AaB pri