1、語法制導翻譯語法制導翻譯5.1-5.45.1-5.4第五章：語法制導翻譯v語法制導翻譯主題：使用上下文無關文法來引導對語言的翻譯用途v類型檢查和中間代碼生成（第六章）v完成特殊任務的語言,如排版（第五章）2第五章：語法制導翻譯v語法制導翻譯屬性文法v通過把屬性附加到代表語法結構的文法符號上，將語義信息和程序設計語言的語法結構聯系起來，屬性的值是用與文法產生式相聯系的語義規則來計算的v語法制導定義SDD：文法產生式和語義規則分開說明關于語言翻譯的高層次規格，隱藏了許多具體實現細節，使用戶不必顯式地說明發生的順序易讀、適合作為對翻譯的規約（描述）v語法制導翻譯方案SDT：文法產生式和語義規則交錯把

2、語義規則用括起來，插入到規則右部的合適位置上，指明了語義規則的計算順序，以便說明某些實現細節高效、適合用于翻譯的實現3第五章：語法制導翻譯v語法制導翻譯翻譯過程：輸入字符串=語法分析樹=依賴圖=語義規則計算順序v對輸入符號(記號/終結符)串進行語法分析，構建語法分析樹v根據需要遍歷語法分析樹，得到描述節點屬性間依賴關系的依賴圖當實現一遍編譯程序時，可在分析期間計算語義規則而不明顯地構造語法分析樹和依賴圖v由依賴圖得到語義規則的計算順序計算語義規則：生成代碼、在符號表中保存信息、發出錯誤信息或完成其他活動v按上述計算順序在語義分析樹節點處進行語義規則計算，得到翻譯結果4第五章：語法制導翻譯v語法

3、制導翻譯本章重點本章重點vL屬性翻譯方案（L代表從左到右）：包含了所有不必顯式構造語法分析樹即可完成的翻譯方案，即可以在語法分析過程中完成的翻譯方案vS屬性翻譯方案（S代表綜合）：可以很容易和自底向上語法分析（如LR語法分析）過程聯系起來的L屬性翻譯方案55.1 語法制導定義SDD（5.1）v語法制導定義SDD：CFG+屬性+規則屬性：和文法符號相關聯v每個文法符號都有一個相關的屬性集，屬性可以代表任何對象：字符串、數字、類型、內存單元或其他對象。v與這些屬性相關的信息，即屬性值可以在語法分析過程中計算和傳遞。屬性加工的過程即語義的處理過程。規則：和產生式相關聯65.1 語法制導定義SDDv屬

4、性：綜合屬性vs繼承屬性綜合屬性v語法分析樹結點N上的非終結符A的綜合屬性是由N上的產生式所關聯的語義規則定義的這個產生式的頭一定是非終結符A；結點結點N N上的綜合屬性只能通過上的綜合屬性只能通過其子節點或其本身的屬性值來定義其子節點或其本身的屬性值來定義繼承屬性v語法分析樹結點N上的非終結符B的繼承屬性是由N的父結點上的產生式所關聯的語義規則定義的這個產生式的體中一定包含非終結符B；結點結點N N上的繼承屬性只能上的繼承屬性只能通過其父節點、其本身及其兄弟結點上的屬性值來定義通過其父節點、其本身及其兄弟結點上的屬性值來定義75.1 語法制導定義SDDv屬性：綜合屬性vs繼承屬性幾點說明v終

5、結符號只有綜合屬性，它們由詞法分析器提供，在語法制導定義中沒有計算終結符的屬性值的語義規則v非終結符既可有綜合屬性也可有繼承屬性；不允許結點N上的繼承屬性通過N的子結點上的屬性值定義允許N的綜合屬性通過結點N的繼承屬性來定義v總可以用綜合屬性來改寫語法制導定義，但使用帶有繼承屬性的語法制導定義更為自然。舉例：使用繼承屬性跟蹤一個標識符，看它是出現在賦值號的左邊還是右邊來確定它的地址還是它的值上下文有關v文法開始符號的所有繼承屬性作為屬性計算前的初始值85.1 語法制導定義SDDvS屬性SDD：一個只包含綜合屬性的SDD每個規則都根據相應產生式的產生式體中的屬性值來計算產生式頭部非終結符的一個屬

6、性可以和LR語法分析器一起自然地實現例5.1：圖5-一個簡單臺式計算器的語法制導定義（參考圖.）95.1 語法制導定義SDDvL屬性SDD一個產生式體所關聯的各個屬性之間依賴圖的邊總是從左到右，而不能從右到左 。即每個屬性v或者是綜合屬性v或者是繼承屬性，但是它的規則存在如下限制。假設存在一個產生式A-X1X2Xn,并且有一個通過這個產生式所關聯的規則計算得到的繼承屬性Xi.a，那么這個規則只能使用：1）和產生式頭A關聯的繼承屬性；2）位于Xi左邊的文法符號X1、X2、Xi-1相關的繼承屬性或者綜合屬性；3）和這個Xi的實例本身相關的繼承屬性或者綜合屬性，但是在由這個Xi全部屬性組成的依賴圖中

7、不存在環。105.2 S屬性定義的自下而上計算屬性定義的自下而上計算5.2.3 S屬性的自下而上計算屬性的自下而上計算LR分析器的棧分析器的棧增加增加一個域來保存綜合屬性值一個域來保存綜合屬性值若產生式若產生式A XYZ的語義規則是的語義規則是A.a = f (X.x, Y.y, Z.z)，那么歸約后：那么歸約后：. . . . . .AA.a. . . . . .top. . . . . .ZZ. zYY. yXX.x. . . . . .棧棧 state valtop5.2 S屬性定義的自下而上計算屬性定義的自下而上計算簡單計算器的語法制導定義改成棧操作代碼簡單計算器的語法制導定義改成棧操

8、作代碼. . . . . .ZZ. zYY. yXX.x. . . . . .棧棧 state valtop產產 生生 式式 語語 義義 規規 則則 L E n print (E.val) E E1 + T E.val =E1 .val +T.val E T E.val = T.val T T1 F T.val = T1.val F.val T F T.val = F.val F (E) F.val = E.val F digit F.val = digit.lexval5.2 S屬性定義的自下而上計算屬性定義的自下而上計算簡單計算器的語法制導定義改成棧操作代碼簡單計算器的語法制導定義改成棧操

9、作代碼. . . . . .ZZ. zYY. yXX.x. . . . . .棧棧 state valtop產產 生生 式式 代代 碼碼 段段 L E n print (E.val) E E1 + T E.val =E1 .val +T.val E T E.val = T.val T T1 F T.val = T1.val F.val T F T.val = F.val F (E) F.val = E.val F digit F.val = digit.lexval5.2 S屬性定義的自下而上計算屬性定義的自下而上計算簡單計算器的語法制導定義改成棧操作代碼簡單計算器的語法制導定義改成棧操作代碼

10、. . . . . .ZZ. zYY. yXX.x. . . . . .棧棧 state valtop產產 生生 式式 代代 碼碼 段段 L E n print (val top 1 ) E E1 + T E.val =E1 .val +T.val E T E.val = T.val T T1 F T.val = T1.val F.val T F T.val = F.val F (E) F.val = E.val F digit F.val = digit.lexval5.2 S屬性定義的自下而上計算屬性定義的自下而上計算簡單計算器的語法制導定義改成棧操作代碼簡單計算器的語法制導定義改成棧操作

11、代碼. . . . . .ZZ. zYY. yXX.x. . . . . .棧棧 state valtop產產 生生 式式 代代 碼碼 段段 L E n print (val top 1 ) E E1 + T val top 2 =val top 2+val top E T E.val = T.val T T1 F T.val = T1.val F.val T F T.val = F.val F (E) F.val = E.val F digit F.val = digit.lexval5.2 S屬性定義的自下而上計算屬性定義的自下而上計算簡單計算器的語法制導定義改成棧操作代碼簡單計算器的語法

12、制導定義改成棧操作代碼. . . . . .ZZ. zYY. yXX.x. . . . . .棧棧 state valtop產產 生生 式式 代代 碼碼 段段 L E n print (val top 1 ) E E1 + T val top 2 =val top 2+val top E T T T1 F T.val = T1.val F.val T F T.val = F.val F (E) F.val = E.val F digit F.val = digit.lexval5.2 S屬性定義的自下而上計算屬性定義的自下而上計算簡單計算器的語法制導定義改成棧操作代碼簡單計算器的語法制導定義改

13、成棧操作代碼. . . . . .ZZ. zYY. yXX.x. . . . . .棧棧 state valtop產產 生生 式式 代代 碼碼 段段 L E n print (val top 1 ) E E1 + T val top 2 =val top 2+val top E T T T1 F val top 2 = val top 2 val top T F T.val = F.val F (E) F.val = E.val F digit F.val = digit.lexval5.2 S屬性定義的自下而上計算屬性定義的自下而上計算簡單計算器的語法制導定義改成棧操作代碼簡單計算器的語法制

14、導定義改成棧操作代碼. . . . . .ZZ. zYY. yXX.x. . . . . .棧棧 state valtop產產 生生 式式 代代 碼碼 段段 L E n print (val top 1 ) E E1 + T val top 2 =val top 2+val top E T T T1 F val top 2 = val top 2 val top T F F (E) F.val = E.val F digit F.val = digit.lexval5.2 S屬性定義的自下而上計算屬性定義的自下而上計算簡單計算器的語法制導定義改成棧操作代碼簡單計算器的語法制導定義改成棧操作代碼

15、. . . . . .ZZ. zYY. yXX.x. . . . . .棧棧 state valtop產產 生生 式式 代代 碼碼 段段 L E n print (val top 1 ) E E1 + T val top 2 =val top 2+val top E T T T1 F val top 2 = val top 2 val top T F F (E) val top 2 =val top 1 F digit F.val = digit.lexval5.2 S屬性定義的自下而上計算屬性定義的自下而上計算簡單計算器的語法制導定義改成棧操作代碼簡單計算器的語法制導定義改成棧操作代碼. .

16、 . . . .ZZ. zYY. yXX.x. . . . . .棧棧 state valtop產產 生生 式式 代代 碼碼 段段 L E n print (val top 1 ) E E1 + T val top 2 =val top 2+val top E T T T1 F val top 2 = val top 2 val top T F F (E) val top 2 =val top 1 F digit 5.3 L屬性定義的自上而下計算屬性定義的自上而下計算邊分析邊翻譯的方式能否用于繼承屬性邊分析邊翻譯的方式能否用于繼承屬性？屬性的計算次序一定受分析方法所限定的分析樹結屬性的計算次序

17、一定受分析方法所限定的分析樹結點建立次序的限制點建立次序的限制分析樹的結點是自左向右生成分析樹的結點是自左向右生成如果屬性信息是自左向右流動，那么就有可能在分如果屬性信息是自左向右流動，那么就有可能在分析的同時完成屬性計算析的同時完成屬性計算5.3 L屬性定義的自上而下計算屬性定義的自上而下計算5.3.1 L屬性定義屬性定義v如果每個產生式如果每個產生式AX1Xj-1XjXn的每條語的每條語義規則計算的屬性是義規則計算的屬性是A的綜合屬性；或者是的綜合屬性；或者是Xj 的繼承屬性，但它僅依賴：的繼承屬性，但它僅依賴：該產生式中該產生式中Xj左邊符號左邊符號X1, X2, , Xj-1的屬性；的

18、屬性；A的繼承屬性的繼承屬性vS屬性定義屬于屬性定義屬于L屬性定義屬性定義5.3 L屬性定義的自上而下計算屬性定義的自上而下計算變量類型聲明的語法制導定義是一個變量類型聲明的語法制導定義是一個L屬性定義屬性定義 產產 生生 式式 語語 義義 規規 則則 D TL L.in = T.type T int T. type = integer T real T. type = real L L1, id L1.in = L.in; addType(id.entry, L.in) L id addType(id.entry, L.in) 5.3 L屬性定義的自上而下計算屬性定義的自上而下計算5.3.2

19、 翻譯方案翻譯方案例例 把有加和減的中綴表達式翻譯成后綴表達式把有加和減的中綴表達式翻譯成后綴表達式如果輸入是如果輸入是8+5 2，則輸出是，則輸出是8 5 + 2 E T RR addop T print (addop.lexeme) R1 | T num print (num.val)E T R num print (8) R numprint (8)addop Tprint (+)R numprint(8)addop numprint(5)print (+)R print(8)print(5)print(+)addop Tprint( )R print(8)print(5)print(+

20、)print(2)print( )5.3 L屬性定義的自上而下計算屬性定義的自上而下計算v例例 數學排版語言數學排版語言EQN E sub 1 .val S B B B1 B2 B B1 sub B2 B text E1.val5.3 L屬性定義的自上而下計算屬性定義的自上而下計算v例例 數學排版語言數學排版語言EQN（語法制導定義）（語法制導定義） E sub 1 .val 產產 生生 式式 語語 義義 規規 則則 S B B.ps = 10; S.ht = B.ht B B1 B2 B1.ps = B.ps; B2.ps = B.ps; B.ht = max(B1.ht, B2.ht )

21、B B1 sub B2 B1.ps =B.ps; B2.ps = shrink(B.ps); B.ht = disp (B1.ht, B2.ht ) B text B.ht = text.h B.ps E1.val5.3 L屬性定義的自上而下計算屬性定義的自上而下計算v例例 數學排版語言數學排版語言EQN（翻譯方案）（翻譯方案） S B.ps = 10 B繼承屬性的計算繼承屬性的計算BS.ht = B.ht 位于位于B的左邊的左邊5.3 L屬性定義的自上而下計算屬性定義的自上而下計算v例例 數學排版語言數學排版語言EQN（翻譯方案）（翻譯方案） S B.ps = 10 B綜合屬性的計算綜合屬性

22、的計算BS.ht = B.ht 放在右部末端放在右部末端5.3 L屬性定義的自上而下計算屬性定義的自上而下計算v例例 數學排版語言數學排版語言EQN（翻譯方案）（翻譯方案） S B.ps = 10 BS.ht = B.ht B B1.ps = B.ps B1B2.ps = B.ps B2B.ht = max(B1.ht, B2.ht ) B B1.ps =B.ps B1sub B2.ps = shrink(B.ps) B2B.ht = disp (B1.ht, B2.ht ) B textB.ht = text.h B.ps 5.3 L屬性定義的自上而下計算屬性定義的自上而下計算v例例 左遞歸

23、的消除引起繼承屬性左遞歸的消除引起繼承屬性產產 生生 式式語語 義義 規規 則則 E E1 + T E.nptr = mkNode( +, E1.nptr, T.nptr) E T E.nptr = T.nptr T T1 F T.nptr = mkNode( , T1.nptr, F.nptr) T F T.nptr = F.nptr F (E) F.nptr = E.nptr F id F.nptr = mkLeaf (id, id.entry) F num F.nptr = mkLeaf (num, num.val) 5.3 L屬性定義的自上而下計算屬性定義的自上而下計算E T R.i

24、= T.nptr T + T + T + RE.nptr = R.sR +TR1.i = mkNode ( +, R.i, T.nptr)R1R.s = R1.sR R.s = R.i T F W.i = F.nptrWT.nptr = W.sW FW1.i = mkNode ( , W.i, F.nptr)W1W.s = W1.sW W.s = W.i F 產生式部分不再給出產生式部分不再給出5.3 L屬性定義的自上而下計算屬性定義的自上而下計算TF.nptrF.nptridi W F.nptridnumididnum 5 指向符號表中指向符號表中a的入口的入口指向符號表中指向符號表中b的入

25、口的入口i W si W 略去了略去了E TR T 部分部分5.3 L屬性定義的自上而下計算屬性定義的自上而下計算TF.nptrF.nptridi W F.nptridnumididnum 5 指向符號表中指向符號表中a的入口的入口指向符號表中指向符號表中b的入口的入口i W si W 略去了略去了E TR T 部分部分5.3 L屬性定義的自上而下計算屬性定義的自上而下計算TF.nptrF.nptridi W F.nptridnumididnum 5 指向符號表中指向符號表中a的入口的入口指向符號表中指向符號表中b的入口的入口i W si W 略去了略去了E TR T 部分部分5.3 L屬性定

26、義的自上而下計算屬性定義的自上而下計算TF.nptrF.nptridi W F.nptridnumididnum 5 指向符號表中指向符號表中a的入口的入口指向符號表中指向符號表中b的入口的入口i W si W 略去了略去了E TR T 部分部分5.3 L屬性定義的自上而下計算屬性定義的自上而下計算TF.nptrF.nptridi W F.nptridnumididnum 5 指向符號表中指向符號表中a的入口的入口指向符號表中指向符號表中b的入口的入口i W si W 略去了略去了E TR T 部分部分5.3 L屬性定義的自上而下計算屬性定義的自上而下計算TF.nptrF.nptridi W

27、F.nptridnumididnum 5 指向符號表中指向符號表中a的入口的入口指向符號表中指向符號表中b的入口的入口i W si W 略去了略去了E TR T 部分部分5.3 L屬性定義的自上而下計算屬性定義的自上而下計算TF.nptrF.nptridi W F.nptridnumididnum 5 指向符號表中指向符號表中a的入口的入口指向符號表中指向符號表中b的入口的入口i W si W 略去了略去了E TR T 部分部分5.3 L屬性定義的自上而下計算屬性定義的自上而下計算TF.nptrF.nptridi W F.nptridnumididnum 5 指向符號表中指向符號表中a的入口的入口指向符號表中指向符號表中b的入口的入口i W si W 略去了略去了E TR T 部分部分練習-S屬性/語法制導定義4.1v簡單臺式計算器的語法制導定義如下：L-En print(E.val)E-E1+T E.val=E1.val+T.valE-T E.val=T.valT-T1*F T.val=T1.val*F.valT-F F.val=E.valF-(E) F.val=E.valF-digit F.val=digit.lexvalv為輸入表達式(4*7+1)*2構造注釋