chpt7-2屬性文法和語法制導(dǎo)

7 2屬性文法和語法制導(dǎo)翻譯 程序設(shè)計語言的語義靜態(tài)語義是對程序約束的描述 這些約束無法通過抽象語法規(guī)則來妥善地描述 實質(zhì)上就是語法規(guī)則的良形式條件 它可以分為類型規(guī)則和作用域 可見性規(guī)則兩大類如 類型相容性變量先聲明后引用名稱相關(guān)要求動態(tài)語義程序單位描述的計算編譯程序的語義處理工作靜態(tài)語義審查執(zhí)行動態(tài)語義 計算 生成代碼 語義形式化語義建模 形式語義學(xué) 如指稱語義學(xué) 公理語義學(xué) 操作語義學(xué)等 的研究已取得了許多重大的進展文法模型 屬性文法命令式或操作式模型 操作語義學(xué)應(yīng)用式模型 指稱語義學(xué)公理式模型 公理語義學(xué) 屬性文法和語法制導(dǎo)翻譯 在實際應(yīng)用中比較流行的語義描述和語義處理的方法1屬性文法概述2基于屬性文法的處理方法3S 屬性文法的自下而上計算L 屬性文法L 屬性文法和自頂向下翻譯自下而上的分析中實現(xiàn)L 屬性文法 7 2 1屬性文法概述 表達(dá)式文法E T T TorTT n bE T1 T2 T1 type intT2 type T1 typeE type int E T1orT2 T1 type boolT2 type T1 typeE type bool T n T type int T b T type bool input emptystring inputline line n exp n printf t 10g n 1 error n exp NUM 1 exp exp 1 3 exp exp 1 3 exp exp 1 3 exp exp 1 3 exp precNEG 2 exp exp pow 1 3 exp 2 屬性文法 屬性文法 attributegrammar 是一個三元組 A G V F 其中G 是一個上下文無關(guān)文法V 有窮的屬性集 每個屬性與文法的一個終結(jié)符或非終結(jié)符相連 這些屬性代表與文法符號相關(guān)信息 如它的類型 值 代碼序列 符號表內(nèi)容等等 屬性與變量一樣 可以進行計算和傳遞 屬性加工的過程即是語義處理的過程 F 關(guān)于屬性的屬性斷言或一組屬性的計算規(guī)則 稱為語義規(guī)則 斷言或語義規(guī)則與一個產(chǎn)生式相聯(lián) 引用該產(chǎn)生式左端或右端的終結(jié)符或非終結(jié)符相聯(lián)的屬性 屬性通常分為兩類 綜合屬性和繼承屬性 簡單地說 綜合屬性用于 自下而上 傳遞信息 而繼承屬性用于 自上而下 傳遞信息 屬性文法中 對應(yīng)于每個產(chǎn)生式A 都有一套與之相關(guān)聯(lián)的語義規(guī)則 每條規(guī)則的形式為b f c1 c2 ck f是一個函數(shù) b和c1 c2 ck是該產(chǎn)生式文法符號的屬性 并且 1 如果b是A的一個屬性 c1 c2 ck是產(chǎn)生式右部文法符號的屬性或A的其他屬性 則稱b是A的綜合屬性 2 如果b是產(chǎn)生式右部某個文法符號X的一個屬性 并且c1 c2 ck是A或產(chǎn)生式右邊任何文法符號的屬性 則稱b是文法符號X的繼承屬性在兩種情況下 我們都說屬性b依賴于屬性c1 c2 ck 一般 對出現(xiàn)在產(chǎn)生式左邊的繼承屬性和出現(xiàn)在產(chǎn)生式右邊的綜合屬性都必須提供一個計算規(guī)則 屬性計算規(guī)則中只能使用相應(yīng)產(chǎn)生式中的文法符號的屬性 然而 出現(xiàn)在產(chǎn)生式左邊的繼承屬性和出現(xiàn)在產(chǎn)生式右邊的綜合屬性不由所給定的產(chǎn)生式的屬性計算規(guī)則進行計算 它們由其它產(chǎn)生式的屬性規(guī)則計算或者由屬性計算器的參數(shù)提供 A X1X2 XnA的綜合屬性S A 計算公式S A f I X1 I Xn Xj的繼承屬性T Xj 計算公式T Xj f I A I Xn 1 非終結(jié)符既可有綜合屬性也可有繼承屬性 但文法開始符號沒有繼承屬性 2 終結(jié)符只有綜合屬性 它們由詞法程序提供 如非終結(jié)符A B和C 其中A有一個繼承屬性a和一個綜合屬性b B有綜合屬性c C有繼承屬性d 對產(chǎn)生式A BC可能有語義規(guī)則C d B c 1和A b A a B c而屬性A a和B c是在其他地方計算的 語義規(guī)則所描述的工作可以包括屬性計算 靜態(tài)語義檢查 符號表操作 代碼 中間 生成等等 有些語義規(guī)則可能產(chǎn)生副作用 如產(chǎn)生代碼 也可能是個函數(shù) 通常把這樣的語義規(guī)則寫成過程調(diào)用或過程段 一個屬性文法和綜合屬性的例子例 1非終結(jié)符E T及F都有一個綜合屬性val 符號digit有一個綜合屬性 它的值由詞法分析器提供 與產(chǎn)生式L E對應(yīng)的語義規(guī)則僅僅是打印由E產(chǎn)生的算術(shù)表達(dá)式的值的一個過程 我們可認(rèn)為這條規(guī)則定義了L的一個虛屬性 某些非終結(jié)符加上標(biāo)是為了區(qū)分一個產(chǎn)生式中同一非終結(jié)符多次出現(xiàn) 語義規(guī)則 LE EE1 T ET TT1 F TF F E Fdigit Print E val E val E1 val T val E val T val T val T1 val F val T val F val F val E val F val digit lexval 產(chǎn)生式 設(shè)表達(dá)式為3 5 4 則語義動作打印數(shù)值19 L E val 19 E val 15 T val 4 T val 15 F val 4 T val 3 F val 3 F val 5 digit lexval 4 digit lexval 5 digit lexval 3 3 5 4的帶注釋的分析樹 繼承屬性 一個結(jié)點的繼承屬性值是由此結(jié)點的父結(jié)點和 或兄弟結(jié)點的某些屬性來決定的 例2繼承屬性L in 生產(chǎn)式 語義規(guī)則 D TL T int T real L L1 id L id L in T type T type integer T type real L1 in L in addtype id entry L in addtype id entry L in D L in real L in real L in real T type real real id2 id1 id3 Realid1 id2 id3每個L結(jié)點都帶有繼承屬性的語法樹 例3 P DSD varV D S V e S V x y z現(xiàn)在使用兩個屬性 name和dl 每當(dāng)一個新的變量聲明時 就把它的name屬性附給它 name屬性是綜合屬性 將所聲明的變量都放到一個變量名字清單中 用語義函數(shù)addlist實現(xiàn) 用屬性dl收集聲明塊中聲明的所有變量 然后這個dl屬性又作為繼承屬性傳到后面的語句部分 每個語句用到的變量都要進行審查 看它是否在變量名字清單中P DS S dl D dl D1 varV D2 D1 dl addlist V name D2 dl D1 dl NULL S1 V e S2 check V name S1 dl S2 dl S1 dl V x y z V name x V name y V name z varx vary y e PDdl x y Sdl x y varV Ddl y V e SxvarV Ddl y y 例4 定義二進制數(shù)的CFG 1 N S S 2 S SB 3 S B 4 B 0 5 B 1 1 N S S 2 S SB 3 S B 4 B 0 5 B 1非終結(jié)符N表示整個二進制數(shù)的數(shù)值 綜合屬性v附加在N上 Nv非終結(jié)符B表示一個二進制數(shù)字 它有自己的值v 但該值分配給N的值與它的位置有關(guān) 是與2成比例 比例因子f是從S繼承的屬性 所以 Bvf非終結(jié)符S表示一個二進制數(shù)字串 它也有值 但該值與串的位置 f 有關(guān) 與串的長度l有關(guān) Sfvl 構(gòu)造數(shù)值的屬性斷言可以如下 N v S f1 v1 l1 S f2 v2 l2 v v1 v2 f1 1 f2 2 l2 S f v l S f1 v1 l1B f2 v2 f1 2f f2 f v v1 v2 l l1 1 B f v l 1 B f v 0 v 0 1 v f 1 N S S 2 S SB 3 S B 4 B 0 5 B 1 文法定義的二進制數(shù)的形式為dmdm 1 d1d0 pkpk 1 p1p0 其中dmdm 1 d1d0和pkpk 1 p1p0都是二進制數(shù)字 這種形式的二進制數(shù)的數(shù)值計算公式是 dm 2m dm 1 2m 1 d1 21 d0 pk 2 1 pk 1 2 2 p1 2 k p0 2 k 1 dm 2m dm 1 2m 1 d1 21 d0 pk 2k pk 1 2 k 1 p1 21 p0 2k 1 為了計算小數(shù)部分的值 需要知道二進制數(shù)字的個數(shù) 也即S定義的數(shù)串的長度 因此對非終結(jié)符S附加兩個屬性val和length N S1 S2 N val S1 val 2 S2 len S2 val S S1B S val 2 S1 val B val S len S1 len 1 S B S val B val S len 1 B 0 B val 0 B 1 B val 1 N v S i1 l1 S i2 l2 v i1 2 l2 i2 S i l S i1 l1B i2 i 2i1 i2 l l1 1 B i l 1 B i 0 i 0 1 i 1 7 2 2基于屬性文法的處理過程 從概念上講 基于屬性文法的處理過程即語法制導(dǎo)翻譯通常是這樣的 對單詞符號串進行語法分析 構(gòu)造語法分析樹 然后根據(jù)需要構(gòu)造屬性依賴圖 遍歷語法樹并在語法樹的各結(jié)點處按語義規(guī)則進行計算輸入符號串 分析樹 屬性依賴圖 語義規(guī)則的計算順序 依賴圖 由稱為依賴圖的一個有向圖描述分析樹中的繼承屬性和屬性中間的相互依賴關(guān)系 依賴圖的構(gòu)造算法 for分析樹中每一個結(jié)點ndofor結(jié)點的文法符號的每一個屬性ado為a在依賴圖中建立一個結(jié)點 for分析樹中每一個結(jié)點ndofor結(jié)點n所用產(chǎn)生式對應(yīng)的每一個語義規(guī)則b f c1 c2 ck dofori 1tokdo從ci結(jié)點到b結(jié)點構(gòu)造一條有向邊 依賴圖 例2 例2繼承屬性L in 生產(chǎn)式 語義規(guī)則 D TL T int T real L L1 id L id L in T type T type integer T type real L1 in L in addtype id entry L in addtype id entry L in 例2Realid1 id2 id3分析樹的依賴圖 圖中的結(jié)點用數(shù)字表示 5 6 7 8 9 10 T 4 D L L L Real type in in in 3entry 2entry entry id3 id2 id1 1 例2Realid1 id2 id3分析樹的依賴圖的說明 依賴圖中的結(jié)點由數(shù)字來標(biāo)識 從代表T type的結(jié)點4有一條有向邊連到代表L in的結(jié)點5 因為根據(jù)產(chǎn)生式D TL的語義規(guī)則L in T type 可知L in依賴于T type 根據(jù)產(chǎn)生式L L1 id的語義規(guī)則L1 in L in 可知L1 in依賴于L in 所以有兩條向下的有向邊分別進入結(jié)點7和9 每一個與L產(chǎn)生式有關(guān)的語義規(guī)則addtype id Entry L in 都產(chǎn)生一個虛屬性 結(jié)點6 8和10都是為這些虛屬性構(gòu)造的 良定義的屬性文法 很顯然 一條求值規(guī)則只有在其各變元值均已求得的情況下才可以使用 但有時候可能會出現(xiàn)一個屬性對另一個屬性的循環(huán)依賴關(guān)系 如 p c1 c2都是屬性 若有下求值規(guī)則 p f1 c1 c1 f2 c2 c2 f3 p 時 就無法對p求值 如果一屬性文法不存在屬性之間的循環(huán)依賴關(guān)系 那么稱該文法為良定義的 為了設(shè)計編譯程序 我們只處理良定義的屬性文法 屬性的計算順序 一個有向非循環(huán)圖的拓?fù)湫蚴菆D中結(jié)點的任何順序m1 m2 mk 使得邊必須是從序列中前面的結(jié)點指向后面的結(jié)點 也就是說 如果mi mj是mi到mj的一條邊 那么在序列中mi必須出現(xiàn)在mj之前 一個依賴圖的任何拓?fù)渑判蚨冀o出一個分析樹中結(jié)點的語義規(guī)則計算的有效順序 這就是說 在拓?fù)渑判蛑?在一個結(jié)點 語義規(guī)則b f c1 c2 ck 中的屬性c1 c2 ck在計算b以前都是可用的 屬性文法說明的翻譯是很精確的 最基本的文法用于建立輸入符號串的分析樹 依賴圖如上面討論的那樣建立 從依賴圖的拓?fù)渑判蛑?我們可以得到計算語義規(guī)則的順序 用這個順序來計算語義規(guī)則就得到輸入符號串的翻譯 再考查例2Realid1 id2 id3分析樹的依賴圖每一條邊都是從序號較低的結(jié)點指向序號較高的結(jié)點 歷此 依賴圖的一個拓?fù)渑判蚩梢詮牡托蛱柕礁咝蛱栱樞驅(qū)懗?從這個拓?fù)渑判蛑形覀兛梢缘玫较铝谐绦?用an來代表依賴圖中與序號n的結(jié)點有關(guān)的屬性 a4 reala5 a4addtype id3 entry a5 a7 a5 addtype id2 entry a7 a9 a7addtype id1 entry a9 這些語義規(guī)則的計算將把real類型填入到每個標(biāo)識符對應(yīng)的符號表項中 屬性計算方法 樹遍歷的屬性計算方法設(shè)語法樹已經(jīng)建立起了 并且樹中已帶有開始符號的繼承屬性和終結(jié)符的綜合屬性 然后以某種次序遍歷語法樹 直至計算出所有屬性 最常用的遍歷方法是深度優(yōu)先 從左到右的遍歷方法 如果需要的話 可使用多次遍歷 或稱遍 一遍掃描的處理方法與樹遍歷的屬性計算文法不同 一遍掃描的處理方法是在語法分析的同時計算屬性值 而不是語法分析構(gòu)造語法樹之后進行屬性的計算 而且并無需構(gòu)造實際的語法樹 因為一遍掃描的處理方法與語法分析器的相互作用 它與下面兩個因素密切相關(guān) 1 所采用的語法分析方法 2 屬性的計算次序 構(gòu)造數(shù)值的屬性斷言可以如下 N v S f1 v1 l1 S f2 v2 l2 v v1 v2 f1 1 f2 2 l2 S f v l S f1 v1 l1B f2 v2 f1 2f f2 f v v1 v2 l l1 1 B f v l 1 B f v 0 v 0 1 v f 在某些情況下可用一遍掃描實現(xiàn)屬性文法的語義規(guī)則計算 也就是說在語法分析的同時完成語義規(guī)則的計算 無須明顯地構(gòu)造語法樹或構(gòu)造屬性之間的依賴圖 因為單遍實現(xiàn)對于編譯效率非常重要具體的實現(xiàn)希望在單遍掃描中完成翻譯研究怎樣實現(xiàn)這種翻譯器 一個一般的屬性文法的翻譯器可能是很難建立的 然而有一大類屬性文法的翻譯器是很容易建立的s 屬性適用于自底向上的計算L 屬性適用于自頂向下的計算 也可用于自底向上 7 2 3S 屬性文法的自下而上計算 S 屬性文法 它只含有綜合屬性 綜合屬性可以在分析輸入符號串的同時自下而上的來計算 分析器可以保存與棧中文法符號有關(guān)的綜合屬性值 每當(dāng)進行歸約時 新的屬性值就由棧中正在歸約的產(chǎn)生式右邊符號的屬性值來計算 S 屬性文法的翻譯器通?？山柚贚R分析器實現(xiàn) 在S 屬性文法的基礎(chǔ)上 LR分析器可以改造為一個翻譯器 在對輸入串進行語法分析的同時對屬性進行計算 產(chǎn)生式語義規(guī)則 1 1 l 1 1 F F i i LR分析器可以改造為一個翻譯器增加語義棧 在對輸入串進行語法分析的同時對屬性進行計算 分析器模型 總控程序 output Input S1 Xm S1 X1 S0 棧 狀態(tài) 符號 ACTION GOTO LR分析表 產(chǎn)生式表 Vm V1 語義 S1 S0 Vm V1 的分析和計值過程 步驟動作狀態(tài)棧語義棧 值棧 符號棧余留輸入串 3 2 3 接受 BOTTOM UP語義處理是作類型檢查 對二目運算符的運算對象進行類型匹配審查 LR分析 增加語義棧歸約時進行語義動作 例5G E 1 E T T 2 E TorT 3 T n 4 T b E T1 T2 ifT1 type intandT2 type intthenE type intelseerror E T1orT2 ifT1 type boolandT2 type boolthenE type boolelseerror T n T type int T b T type bool G E 1 E T T 2 E TorT 3 T n 4 T b G E 1 E T T 2 E TorT 3 T n 4 T b 7 2 4L 屬性文法 一個屬性文法稱為L 屬性文法 如果對于每個產(chǎn)生式A X1X2 Xn 其每個語義規(guī)則中的每個屬性或者是綜合屬性 或者是Xj 1 j n 的一個繼承屬性且這個繼承屬性僅依賴于 1 產(chǎn)生式Xj在左邊符號X1 X2 Xj 1的屬性 2 A的繼承屬性 S 屬性文法一定是L 屬性文法 因為 1 2 限制只用于繼承屬性 L 屬性文法例 1非終結(jié)符E T及F都有一個綜合屬性val 符號digit有一個綜合屬性 它的值由詞法分析器提供 與產(chǎn)生式L E對應(yīng)的語義規(guī)則僅僅是打印由E產(chǎn)生的算術(shù)表達(dá)式的值的一個過程 我們可認(rèn)為這條規(guī)則定義了L的一個虛屬性 某些非終結(jié)符加上標(biāo)是為了區(qū)分一個產(chǎn)生式中同一非終結(jié)符多次出現(xiàn) 語義規(guī)則 LE EE1 T ET TT1 F TF F E Fdigit Print E val E val E1 val T val E val T val T val T1 val F val T val F val F val E val F val digit lexval 產(chǎn)生式 L 屬性文法 一個結(jié)點的繼承屬性值依賴于父結(jié)點的繼承屬性和 或左部兄弟結(jié)點的某些屬性來決定的 例2繼承屬性L in 生產(chǎn)式 語義規(guī)則 D TL T int T real L L1 id L id L in T type T type integer T type real L1 in L in addtype id entry L in addtype id entry L in L 屬性文法和自頂向下翻譯 L 屬性文法允許一次遍歷就計算出所有屬性值 LL 1 這種自上而下分析文法的分析過程 從概念上說可以看成是深度優(yōu)先建立語法樹的過程 因此 我們可以在自上而下語法分析的同時實現(xiàn)L屬性文法的計算 例2Realid1 id2 id3分析樹的依賴圖 圖中的結(jié)點用數(shù)字表示 5 6 7 8 9 10 T 4 D L L L Real type in in in 3entry 2entry entry id3 id2 id1 1 例6 中綴表達(dá)式翻譯成相應(yīng)的后綴表達(dá)式 LR分析 E EaddopTprint addop Lexeme TT numprint num val LL 1 分析 E TRR addopTR T num 9 5 2的語法樹 E T E 2 T T 9 5 E 說明語義動作的語法樹 print E print 9 print 5 print print 2 消除左遞歸 9 5 2的語法樹 R R 2 說明語義動作的語法樹 R R 2 print 9 T print 5 print 2 Print 翻譯模式 Translationschemes 適合語法制導(dǎo)翻譯的另一種描述形式 翻譯模式給出了使用語義規(guī)則進行計算的次序 可把某些實現(xiàn)細(xì)節(jié)表示出來 在翻譯模式中 和文法符號相關(guān)的屬性和語義規(guī)則 這里我們也稱語義動作 用花括號 括起來 插入到產(chǎn)生式右部的合適位置上 例 中綴表達(dá)式翻譯成相應(yīng)的后綴表達(dá)式 E TRR addopT print addop Lexeme R1 T num print num val E TRR addopTR T num E EaddopT TT num 輸入串9 5 2的語法樹 ETR9 TR5 TR2 輸入串9 5 2的說明動作的語法樹 每個語義動作都作為相應(yīng)產(chǎn)生式左部符號的結(jié)點的兒子 把語義動作看作是終結(jié)符 按深度優(yōu)先次序執(zhí)行圖中的動作后 打印輸出95 2 ETR9print 9 Tprint R5print 5 Tprint R2print 2 L 屬性文法在自頂向下分析中的實現(xiàn) 帶左遞歸的文法的翻譯模式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 消除左遞歸的同時考慮屬性 構(gòu)造新的翻譯模式 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 計算表達(dá)式9 5 2 E R i 9 T val 5 T val 9 R i 4 R i 6 T val 2 num val 9 num val 5 num val 2 在這個翻譯模式中 每個數(shù)都是由T產(chǎn)生的 并且T val的值就是由屬性num val給出的數(shù)的詞法值 子表達(dá)式9 5中的數(shù)字9是由最左邊的T生成的 但是減號和5是由根的右子結(jié)點R生成的 繼承屬性R i從T val得到值9 通過產(chǎn)生式中嵌入的下面動作 R1 i R i T val 實現(xiàn)計算9 5并把結(jié)果4傳遞到中間的R結(jié)點 類似的動作把2加到9 5的值上 在最下面的R結(jié)點處產(chǎn)生結(jié)果R i 6 這個結(jié)果將成為根結(jié)點處E val的值 R的綜合屬性s在圖中沒有表示出來 它用來向上復(fù)制這一結(jié)果一直到樹根 對于自頂向下分析 我們假設(shè)動作是在處于相同位置上的符號被展開 匹配成功 時執(zhí)行的 如圖中的第二個產(chǎn)生式中 第一個動作 對R1 i賦值 是在T被完全展開成終結(jié)符號后執(zhí)行的 第二個動作是在R1被完全展開成終結(jié)符號后執(zhí)行的 正如前面我們所討論的 一個符號的繼承屬性必須由出現(xiàn)在這個符號之前的動作來計算 產(chǎn)生式左邊非終結(jié)符的綜合屬性必須在它所依賴的所有屬性都計算出來以后才能計算 轉(zhuǎn)換左遞歸翻譯模式的方法推廣到一般 假設(shè)翻譯模式1 A A1Y A a g A1 a Y y A X A a f X x 每個文法符號都有一個綜合屬性 用相應(yīng)的小寫字母表示 g和f是任意函數(shù)消除左遞歸 文法轉(zhuǎn)換成 A XRR YR 再考慮語義動作 翻譯模式變?yōu)?A 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 翻譯模式1和翻譯模式2的結(jié)果是一樣的 可以給出串XY1Y2兩棵帶注釋的語法樹看出來 一棵是根據(jù)翻譯模式1自下而上計算屬性的 一棵是根據(jù)翻譯模式2自上而下計算的 A A1Y A a g A1 a Y y A X A a f X x A a g g f X x Y1 y Y2 y A a g f X x Y1 y Y2A a f X x Y1X AAYAYX A X R i f X x R Y R1 i g R i Y y R A a R s R1 R s R1 s A XRR YR AXRY1RY2R AXR i f X x Y1R i g f X x Y1 y Y2R i g g f X x Y1 y Y2 y 自下而上計算繼承屬性 自下而上的分析中實現(xiàn)L 屬性文法 從翻譯模式中去掉嵌入在產(chǎn)生式中間的動作分析棧中的繼承屬性用綜合屬性代替繼承屬性 從翻譯模式中去掉嵌入在產(chǎn)生式中間的動作轉(zhuǎn)換方法 引入新的非終結(jié)符N和產(chǎn)生式N 把嵌入在產(chǎn)生式中間的動作用非終結(jié)符N代替 并把這個動作放在產(chǎn)生式后面 例 E TRR T print R1R T print R1R T num print num val 文法變換后 接受的語言相同 E TRR TMR1R TNR1R T num print num val M print N print 目的 使所有嵌入的動作都出現(xiàn)在產(chǎn)生式的末尾 可以自下而上處理繼承屬性 一個屬性文法稱為L 屬性文法 如果對于每個產(chǎn)生式A X1X2 Xn 其每個語義規(guī)則中的每個屬性或者是綜合屬性 或者是Xj 1 j n 的一個繼承屬性且這個繼承屬性僅依賴于 1 產(chǎn)生式Xj在左邊符號X1 X2 Xj 1的屬性 2 A的繼承屬性 分析棧中的繼承屬性 自下而上分析器對產(chǎn)生式A XY的右部是通過把X和Y從分析棧中移出并用A代替它們 假設(shè)X有一個綜合屬性X s 按照前面所介紹的方法我們把它與X一起放在分析棧中 由于X s的值在Y以下的子樹中的任何歸約之前已經(jīng)放在棧中 這個值可以被Y繼承 也就是說 如果繼承屬性Y i是由復(fù)寫規(guī)則Y i X s定義的 則可以在需要y i值的地方使用X s的值 在自下而上分析中計算屬性值時復(fù)寫規(guī)則起非常重要的作用 看下面例子 標(biāo)識符的類型通過繼承屬性的復(fù)寫規(guī)則來傳遞 翻譯模式為 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 回顧例2Realid1 id2 id3分析樹的依賴圖 5 6 7 8 9 10 T 4 D L L L Real type in in in 3entry 2entry entry id3 id2 id1 1 例2輸入串realRealid1 id2 id3的分析過程當(dāng)L的右部被歸約時 T恰好在這個右部的下面 輸入狀態(tài) 符號 使用產(chǎn)生式Realid1 id2 id3 id1 id2 id3 realid1 id2 id3 TT real id2 id3 Tid1 id2 id3 TLL idid2 id3 TL id3 TL id2 id3 TLL L idid3 TL TL id3 TLL L id DD TL 擴充分析棧Val i 存放文法符號X的綜合屬性X s D TLT int Val top integer T real Val top real L L id addtype Val top Val top 3 L id addtype Val top Val top 1 用綜合屬性代替繼承屬性 有時 改變基礎(chǔ)文法可能避免繼承屬性 例如 一個Pascal的說明由一標(biāo)識符序列后跟類型組成 如 m n integer 這樣的說明的文法可由下面形式的產(chǎn)生式構(gòu)成D L TT integer charL L id id因為標(biāo)識符由L產(chǎn)生而類型不在L的子樹中 我們不能僅僅使用綜合屬性就把類型與標(biāo)識符聯(lián)系起來 事實上 如果非終結(jié)符L從第一個產(chǎn)生式中它的右邊T中繼承了類型 則我們得到的屬性文法就不是L 屬性的 因此 基于這個屬性文法的翻譯工作不能在語法分析的同時進行 一個解決的方法是重新構(gòu)造文法 使類型作為標(biāo)識符表 identifierslist 的最后一個元素 D idLL idL TT integer char這樣 類型可以通過綜合屬性L type進行傳遞 當(dāng)通過L產(chǎn)生每個標(biāo)識符時 它的類型就可以填入到符號表中 Yacc或bison作為編譯程序的生成工具 利用的就是語法制導(dǎo)翻譯方法 它使用符號 表示產(chǎn)生式左端的屬性 n表示存取產(chǎn)生式右端第n個文法符號相聯(lián)的屬性 如例3作為Yacc的輸入 可寫成 P DS 2 dl 1 dl D1 varV D dl addlist 2 name 4 dl dl null S1 V e S check 1 name dl 5 dl dl V x name x y name y z name z 如果數(shù)據(jù)結(jié)構(gòu)attribute定義屬性name和dl 可以具體化為 typestruct attribute char name struct attribute list attribute P DS 2 list 1 list D1 varV D list add to list 2 name 4 list list null S1 V e S check 1 name list 5 list list V x name x y name y z name z Review attributegrammars Weaugmenttheconventionalgrammarwithinformationtocontrolthesemanticanalysisandtranslation Suchgrammarsarecalledattributegrammars Weaugmentagrammarbyassociatingattributeswitheachgrammarsymbolthatdescribesitsproperties Anattributehasanameandanassociatedvalue astring anumber atype amemorylocation anassignedregister generatedcode whateverinformationweneed Witheachproductioninagrammar wegivesemanticrulesoractions whichdescribehowtocomputetheattributevaluesassociatedwitheachgrammarsymbolinaproduction Theattributevalueforaparsenodemaydependoninformationfromitschildrennodesbeloworitssiblingsandparentnodeabove Review synthesizedorinheritedattributes Therearetwotypesofattributeswemightencounter synthesizedorinherited Synthesizedattributesarethoseattributesthatarepassedupaparsetree i e theleft sideattributeiscomputedfromtheright sideattributes Inheritedattributesarethosethatarepasseddownaparsetree i e theright sideattributesarederivedfromtheleft sideattributes orotherright sideattributes Theseattributesareusedforpassinginformationaboutthecontexttonodesfurtherdownthetree Review Syntax dire