【正文】 t right 5 b 自下而上、從左到右構(gòu)造語法樹 2022/2/16 第 4章 語法制導(dǎo)的翻譯 58 ? a+5*b的語法樹的構(gòu)造 id + * id num id id num 5 * + 指向符號表中 a的入口 指向符號表中 b的入口 a left right 5 b 自下而上、從左到右構(gòu)造語法樹 2022/2/16 第 4章 語法制導(dǎo)的翻譯 59 ? a+5*b的語法樹的構(gòu)造 id + * id num id id num 5 * + 指向符號表中 a的入口 指向符號表中 b的入口 a left right 5 b 自下而上、從左到右構(gòu)造語法樹 2022/2/16 第 4章 語法制導(dǎo)的翻譯 60 ? a+5*b的語法樹的構(gòu)造 id + * id num id id num 5 * + 指向符號表中 a的入口 指向符號表中 b的入口 a left right 5 b 自下而上、從左到右構(gòu)造語法樹 2022/2/16 第 4章 語法制導(dǎo)的翻譯 61 ? a+5*b的語法樹的構(gòu)造 id + * id num id id num 5 * + 指向符號表中 a的入口 指向符號表中 b的入口 a left right 5 b 自下而上、從左到右構(gòu)造語法樹 2022/2/16 第 4章 語法制導(dǎo)的翻譯 62 ? a+5*b的語法樹的構(gòu)造 id + * id num id id num 5 * + 指向符號表中 a的入口 指向符號表中 b的入口 a left right 5 b 自下而上、從左到右構(gòu)造語法樹 2022/2/16 第 4章 語法制導(dǎo)的翻譯 63 ? a+5*b的語法樹的構(gòu)造 + id * num id 2022/2/16 第 4章 語法制導(dǎo)的翻譯 64 ? S屬性可以由 自下而上分析器 在語法分析輸入時(shí)完成計(jì)算，即“ 邊分析邊計(jì)算 ” ? 自下而上分析器用棧保存已經(jīng)分析的子樹的信息 ， S屬性定義的翻譯器可以借助 LR分析器的生成器來實(shí)現(xiàn) ? LR分析器 可以把文法符號的綜合屬性放在它的棧內(nèi) ，每當(dāng) 歸約 時(shí)，根據(jù)出現(xiàn)在 棧頂 的產(chǎn)生式右部符號串中符號的屬性來計(jì)算左部符號的綜合屬性 S屬性的自下而上計(jì)算 復(fù)習(xí) LR分析器的工作原理：棧內(nèi)可以不存儲文法符號 綜合屬性 來自于子節(jié)點(diǎn)或自身的繼承屬性 2022/2/16 第 4章 語法制導(dǎo)的翻譯 65 ? 將 LR分析器 增加 一個(gè)域來保存綜合屬性值 Z Z. z Y Y. y X X. x . . . . . . 棧 state val top 2022/2/16 第 4章 語法制導(dǎo)的翻譯 66 ? 將 LR分析器 增加 一個(gè)域來保存綜合屬性值 Z Z. z Y Y. y X X. x . . . . . . 棧 state val top 若產(chǎn)生式 A → XYZ的 語義規(guī)則 是 := f (, , ) 右部符號從左至右壓入棧內(nèi) 2022/2/16 第 4章 語法制導(dǎo)的翻譯 67 ? 將 LR分析器 增加 一個(gè)域來保存綜合屬性值 Z Z. z Y Y. y X . . . . . . 若產(chǎn)生式 A → XYZ的 語義規(guī)則 是 := f (, , )， 那么歸約后： . . . . . . A . . . . . . 棧 state val top top top=top2 Top’ 2022/2/16 第 4章 語法制導(dǎo)的翻譯 68 ? 例：臺式計(jì)算器的語法制導(dǎo)定義改成棧操作代碼 Z Z. z Y Y. y X . . . . . . 棧 state val top 產(chǎn) 生 式 語 義 規(guī) 則 L ? E n print () E ? E1 + T :=E1 .val + E ? T := T ? T1 * F := * T ? F := F? (E) := F ? digit := Top’ 2022/2/16 第 4章 語法制導(dǎo)的翻譯 69 ? 例：臺式計(jì)算器的語法制導(dǎo)定義改成棧操作代碼 Z Z. z Y Y. y X . . . . . . 棧 state val top 產(chǎn) 生 式 代 碼 段 L ? E n print () E ? E1 + T :=E1 .val + E ? T := T ? T1 * F := * T ? F := F? (E) := F ? digit := Top’ 2022/2/16 第 4章 語法制導(dǎo)的翻譯 70 ? 例：臺式計(jì)算器的語法制導(dǎo)定義改成棧操作代碼 n E . . . . . . . . . . . . 產(chǎn) 生 式 代 碼 段 L ? E n print (val [ top?1] ) E ? E1 + T :=E1 .val + E ? T := T ? T1 * F := * T ? F := F? (E) := F ? digit := 棧 state val top :=左邊為歸約后左部文法符號的屬性值，下標(biāo)為值的存儲位置 Top’ 2022/2/16 第 4章 語法制導(dǎo)的翻譯 71 ? 例：臺式計(jì)算器的語法制導(dǎo)定義改成棧操作代碼 T + E . . . . . . 產(chǎn) 生 式 代 碼 段 L ? E n print (val [ top?1] ) E ? E1 + T val [top ?2 ] := val [top ?2]+val [top] E ? T := T ? T1 * F := * T ? F := F? (E) := F ? digit := 棧 state val top :=左邊為歸約后左部文法符號的屬性值，下標(biāo)為值的存儲位置 Top’ 2022/2/16 第 4章 語法制導(dǎo)的翻譯 72 ? 例：臺式計(jì)算器的語法制導(dǎo)定義改成棧操作代碼 T . . . . . . . . . . . . . . . . . . 產(chǎn) 生 式 代 碼 段 L ? E n print (val [ top?1] ) E ? E1 + T val [top ?2 ] := val [top ?2]+val [top] E ? T val [top]不變 T ? T1 * F := * T ? F := F? (E) := F ? digit := 棧 state val top :=左邊為歸約后左部文法符號的屬性值，下標(biāo)為值的存儲位置 2022/2/16 第 4章 語法制導(dǎo)的翻譯 73 ? 例：臺式計(jì)算器的語法制導(dǎo)定義改成棧操作代碼 F * T . . . . . . 產(chǎn) 生 式 代 碼 段 L ? E n print (val [ top?1] ) E ? E1 + T val [top ?2 ] := val [top ?2]+val [top] E ? T val [top]不變 T ? T1 * F val [top ?2 ] := val [top ?2]?val [top] T ? F := F? (E) := F ? digit := 棧 state val top :=左邊為歸約后左部文法符號的屬性值，下標(biāo)為值的存儲位置 Top’ 2022/2/16 第 4章 語法制導(dǎo)的翻譯 74 ? 例：臺式計(jì)算器的語法制導(dǎo)定義改成棧操作代碼 F . . . . . . . . . . . . . . . . . . 產(chǎn) 生 式 代 碼 段 L ? E n print (val [ top?1] ) E ? E1 + T val [top ?2 ] := val [top ?2]+val [top] E ? T val [top]不變 T ? T1 * F val [top ?2 ] := val [top ?2]?val [top] T ? F val [top]不變 F? (E) := F ? digit := 棧 state val top :=左邊為歸約后左部文法符號的屬性值，下標(biāo)為值的存儲位置 2022/2/16 第 4章 語法制導(dǎo)的翻譯 75 ? 例：臺式計(jì)算器的語法制導(dǎo)定義改成棧操作代碼 ) E ( . . . . . . 產(chǎn) 生 式 代 碼 段 L ? E n print (val [ top?1] ) E ? E1 + T val [top ?2 ] := val [top ?2]+val [top] E ? T val [top]不變 T ? T1 * F val [top ?2 ] := val [top ?2]?val [top] T ? F val [top]不變 F? (E) val [top ?2 ] := val [top ?1] F ? digit := 棧 state val top :=左邊為歸約后左部文法符號的屬性值，下標(biāo)為值的存儲位置 Top’ 2022/2/16 第 4章 語法制導(dǎo)的翻譯 76 ? 例：臺式計(jì)算器的語法制導(dǎo)定義改成棧操作代碼 digit exval . . . . . . . . . . . . . . . . . . 產(chǎn) 生 式 代 碼 段 L ? E n print (val [ top?1] ) E ? E1 + T val [top ?2 ] := val [top ?2]+val [top] E ? T val [top]不變 T ? T1 * F val [top ?2 ] := val [top ?2]?val [top] T ? F val [top]不變 F? (E) val [top ?2 ] := val [top ?1] F ? digit val [top]不變 棧 state val top :=左邊為歸約后左部文法符號的屬性值，下標(biāo)為值的存儲位置 2022/2/16 第 4章 語法制導(dǎo)的翻譯 77 L 屬性定義的自上而下計(jì)算 邊分析邊翻譯的方式能否用于繼承屬性 ？ ? 屬性的計(jì)算次序受分析方法所限定的分析樹結(jié)點(diǎn)建立次序的限制 2022/2/16 第 4章 語法制導(dǎo)的翻譯 78 L屬性定義的自上而下計(jì)算 邊語法分析邊翻譯的方式能否用于繼承屬性 ？ ? 屬性的計(jì)算次序受分析方法所限定的分析樹結(jié)點(diǎn)建立次序的限制 ? 語法分析方法的共同特點(diǎn)：分析樹的結(jié)點(diǎn)是自左向右生成 ? 如果屬性信息自左向右流動(dòng)，那么就有可能在分析的同時(shí)完成 L 屬性計(jì)算 ? L代表屬性 從左向右 傳遞的方向 2022/2/16 第 4章 語法制導(dǎo)的翻譯 79 ? （ 1） 如果每個(gè)產(chǎn)生式 A ?X1 X2 … Xj … Xn 的每條語義規(guī)則計(jì)算的屬性是 A的綜合屬性；或者 （ 2） 如果是 Xj 的繼承屬性 ， 1 ? j ? n,但它僅依賴于： ? 該產(chǎn)生式中 Xj左邊 （ 兄弟結(jié)點(diǎn) ） 符號 X1, X2, … , Xj1的屬性 ? A的繼承屬性 那么語