【正文】 第六章 語(yǔ)法制導(dǎo)翻譯與屬性文法 School of Computer Science amp。 Technology Harbin Institute of Technology 重點(diǎn)： 語(yǔ)法制導(dǎo)翻譯的基本思想，語(yǔ)法制導(dǎo)定義， 翻譯模式，自頂向下翻譯，自底向上翻譯。 難點(diǎn)： 屬性的意義，對(duì)綜合屬性，繼承屬性， 固有屬性的理解，屬性計(jì)算， 怎么通過(guò)屬性來(lái)表達(dá)翻譯。 2020/11/29 2 第 6章 語(yǔ)法制導(dǎo)翻譯與屬性文法 語(yǔ)法制導(dǎo)翻譯概述 語(yǔ)法制導(dǎo)定義 屬性計(jì)算 翻譯模式 本章小結(jié) 2020/11/29 3 ? 為什么進(jìn)行詞法和語(yǔ)法分析？ ? 用 A→α進(jìn)行歸約表達(dá)的是什么意思？ ? 看： operand+term ? E→E1+T ? E1的值 +T的值的結(jié)果作為 E的值 —— 即：取來(lái)E1的值和 T的值做加法運(yùn)算，結(jié)果作為 E的值 ? =+ 問(wèn)題 2020/11/29 4 語(yǔ)法制導(dǎo)翻譯概述 ? 為了提高編譯程序的可移植性，一般將編譯程序劃分為前端和后端。 ? 前端通常包括詞法分析、語(yǔ)法分析、語(yǔ)義分析、中間代碼生成、符號(hào)表的建立，以及與機(jī)器無(wú)關(guān)的中間代碼優(yōu)化等，它們的實(shí)現(xiàn)一般不依賴于具體的目標(biāo)機(jī)器。 ? 后端通常包括與機(jī)器有關(guān)的代碼優(yōu)化、目標(biāo)代碼的生成、相關(guān)的錯(cuò)誤處理以及符號(hào)表的訪問(wèn)等。 語(yǔ) 法 分 析 器語(yǔ) 義分 析 器中 間 代 碼生 成 器代 碼生 成 器中 間代 碼前 端 后 端注 釋分 析 樹(shù)分 析 樹(shù)圖 編譯器前端的邏輯結(jié)構(gòu) 2020/11/29 5 語(yǔ)法制導(dǎo)翻譯概述 ? 語(yǔ)義分析器的主要任務(wù)是檢查各個(gè)語(yǔ)法結(jié)構(gòu)的靜態(tài)語(yǔ)義 ，稱為靜態(tài)語(yǔ)義分析或靜態(tài)檢查 ? 類型檢查：操作數(shù)和操作符的類型是否相容； ? 控制流檢查：控制流轉(zhuǎn)向的目標(biāo)地址是否合法； ? 惟一性檢查：對(duì)象是否被重復(fù)定義； ? 關(guān)聯(lián)名檢查：同一名字的多次特定出現(xiàn)是否一致。 ? 將靜態(tài)檢查和中間代碼生成結(jié)合到語(yǔ)法分析中進(jìn)行的技術(shù)稱為 語(yǔ)法制導(dǎo)翻譯 。 2020/11/29 6 語(yǔ)法制導(dǎo)翻譯概述 ? 語(yǔ)法制導(dǎo)翻譯的基本思想 ? 在進(jìn)行語(yǔ)法分析的同時(shí)，完成相應(yīng)的語(yǔ)義處理。也就是說(shuō)，一旦語(yǔ)法分析器識(shí)別出一個(gè)語(yǔ)法結(jié)構(gòu)就要立即對(duì)其進(jìn)行翻譯，翻譯是根據(jù)語(yǔ)言的語(yǔ)義進(jìn)行的，并通過(guò)調(diào)用事先為該語(yǔ)法結(jié)構(gòu)編寫(xiě)的語(yǔ)義子程序來(lái)實(shí)現(xiàn)。 ? 對(duì)文法中的每個(gè)產(chǎn)生式附加一個(gè) /多個(gè)語(yǔ)義動(dòng)作 (或語(yǔ)義子程序 )，在語(yǔ)法分析的過(guò)程中，每當(dāng)需要使用一個(gè)產(chǎn)生式進(jìn)行推導(dǎo)或歸約時(shí)，語(yǔ)法分析程序除執(zhí)行相應(yīng)的語(yǔ)法分析動(dòng)作外，還要執(zhí)行相應(yīng)的語(yǔ)義動(dòng)作 (或調(diào)用相應(yīng)的語(yǔ)義子程序 )。 2020/11/29 7 語(yǔ)法制導(dǎo)翻譯概述 ? 語(yǔ)義子程序的功能 ? 指明相應(yīng)產(chǎn)生式中各個(gè)文法符號(hào)的具體含義，并規(guī)定了使用該產(chǎn)生式進(jìn)行分析時(shí)所應(yīng)采取的語(yǔ)義動(dòng)作 (如傳送或處理語(yǔ)義信息、查填符號(hào)表、計(jì)算值、生成中間代碼等 )。 ? 語(yǔ)義信息的獲取和加工是和語(yǔ)法分析同時(shí)進(jìn)行的，而且這些語(yǔ)義信息是通過(guò)文法符號(hào)來(lái)攜帶和傳遞的。 2020/11/29 8 語(yǔ)法制導(dǎo)翻譯概述 ? 一個(gè)文法符號(hào) X所攜帶的語(yǔ)義信息稱為 X的語(yǔ)義屬性，簡(jiǎn)稱為屬性，它是根據(jù)翻譯的需要設(shè)置的 (對(duì)應(yīng)分析樹(shù)結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu) )，主要用于描述語(yǔ)法結(jié)構(gòu)的語(yǔ)義。 ? 一個(gè)變量的屬性有類型、層次、存儲(chǔ)地址等 ? 表達(dá)式的屬性有類型、值等。 2020/11/29 9 語(yǔ)法制導(dǎo)翻譯概述 ? 屬性值的計(jì)算和產(chǎn)生式相關(guān)聯(lián)，隨著語(yǔ)法分析的進(jìn)行，執(zhí)行屬性值的計(jì)算，完成語(yǔ)義分析和翻譯的任務(wù)。 ? E→E1 + E2 :=+ ? 語(yǔ)法結(jié)構(gòu)具有規(guī)定的語(yǔ)義 ? 問(wèn)題：如何根據(jù)被識(shí)別出的語(yǔ)法成分進(jìn)行語(yǔ)義處理？ ? 亦即怎樣 將屬性值的計(jì)算及翻譯工作同產(chǎn)生式相關(guān)聯(lián)？ 2020/11/29 10 典型處理方法一 ? 語(yǔ)法制導(dǎo)定義 ? 通過(guò)將屬性與文法符號(hào)關(guān)聯(lián)、將語(yǔ)義規(guī)則與產(chǎn)生式關(guān)聯(lián)來(lái)描述語(yǔ)言結(jié)構(gòu)的翻譯方案 ? 對(duì)應(yīng)每一個(gè)產(chǎn)生式編寫(xiě)一個(gè)語(yǔ)義子程序，當(dāng)一個(gè)產(chǎn)生式獲得匹配時(shí)，就調(diào)用相應(yīng)的語(yǔ)義子程序來(lái)實(shí)現(xiàn)語(yǔ)義檢查與翻譯 ? E→E1 + T {:=+} ? T→T1 * F {:=*} ? F →digit {:=} ? 適宜在完成歸約的時(shí)候進(jìn)行 2020/11/29 11 典型處理方法二 ? 翻譯模式 ? 通過(guò)將屬性與文法符號(hào)關(guān)聯(lián)，并將語(yǔ)義規(guī)則插入到產(chǎn)生式的右部來(lái)描述語(yǔ)言結(jié)構(gòu)的翻譯方案 ? 在產(chǎn)生式的右部的適當(dāng)位置，插入相應(yīng)的語(yǔ)義動(dòng)作，按照分析的進(jìn)程，執(zhí)行遇到的語(yǔ)義動(dòng)作 ? D → T { := } L ? T → int { := integer } ? T → real { := real } ? L → { := }L1,id{addtype(,) } ? L → id{addtype(,)} ? 適宜在進(jìn)行推導(dǎo)時(shí)完成 2020/11/29 12 語(yǔ)法制導(dǎo)定義 ? 語(yǔ)法制導(dǎo)定義是附帶有屬性和語(yǔ)義規(guī)則的上下文無(wú)關(guān)文法 ? 屬性是與文法符號(hào)相關(guān)聯(lián)的語(yǔ)義信息 ? 語(yǔ)義規(guī)則是與產(chǎn)生式相關(guān)聯(lián)的語(yǔ)義動(dòng)作 ? 語(yǔ)法制導(dǎo)定義是基于語(yǔ)言結(jié)構(gòu)的語(yǔ)義要求設(shè)計(jì)的，類似于程序設(shè)計(jì)，語(yǔ)法制導(dǎo)定義中的屬性類似于程序中用到的數(shù)據(jù)結(jié)構(gòu)，用于描述語(yǔ)義信息，語(yǔ)義規(guī)則類似于計(jì)算，用于收集、傳遞和計(jì)算語(yǔ)義信息的。 ? 屬性通常被保存在分析樹(shù)的相關(guān)節(jié)點(diǎn)中 2020/11/29 13 概念術(shù)語(yǔ) ? 綜合屬性：節(jié)點(diǎn)的屬性值是通過(guò)分析樹(shù)中該節(jié)點(diǎn)或其子節(jié)點(diǎn)的屬性值計(jì)算出來(lái)的 ? 繼承屬性：節(jié)點(diǎn)的屬性值是由該節(jié)點(diǎn)、該節(jié)點(diǎn)的兄弟節(jié)點(diǎn)或父節(jié)點(diǎn)的屬性值計(jì)算出來(lái)的 ? 固有屬性：通過(guò)詞法分析直接得到的屬性 ? 依賴圖：描述屬性之間依賴關(guān)系的圖，根據(jù)語(yǔ)義規(guī)則來(lái)構(gòu)造 ? 注釋分析樹(shù)：節(jié)點(diǎn)帶有屬性值的分析樹(shù) 2020/11/29 14 語(yǔ)法制導(dǎo)定義的形式 ? 在一個(gè) 語(yǔ)法制導(dǎo)定義 中， ?A→??P都有與之相關(guān)聯(lián)的一套語(yǔ)義規(guī)則，規(guī)則形式為 b： = f（ c1， c2， … ， ck）， f是一個(gè)函數(shù)，而且或者 1． b是 A的一個(gè)綜合屬性并且 c1， c2， … ， ck 是 ?中的 符號(hào)的屬性，或者 2． b是 ?中 某個(gè) 符號(hào)的一個(gè)繼承屬性并且 c1， c2， … ， ck是 A或 ?中的 任何文法符號(hào)的屬性。 這兩種情況下，都說(shuō)屬性 b依賴于屬性 c1， c2， … ， ck 2020/11/29 15 例 臺(tái)式計(jì)算器的語(yǔ)法制導(dǎo)定義 產(chǎn)生式 語(yǔ)義規(guī)則 L?En print(E?val)(可看作是 L的虛屬性 ) 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?lexval 2020/11/29 16 S屬性 定義 ? 只含綜合屬性的語(yǔ)法制導(dǎo)定義稱為 S屬性定義 ? 對(duì)于 S屬性定義，通常使用自底向上的分析方法，在建立每一個(gè)結(jié)點(diǎn)處使用語(yǔ)義規(guī)則來(lái)計(jì)算綜合屬性值，即在用哪個(gè)產(chǎn)生式進(jìn)行歸約后，就執(zhí)行那個(gè)產(chǎn)生式的 S屬性定義計(jì)算屬性的值，從葉結(jié)點(diǎn)到根結(jié)點(diǎn)進(jìn)行計(jì)算。 ? 沒(méi)有副作用的語(yǔ)法制導(dǎo)定義有時(shí)又稱為 屬性文法 ，屬性文法的語(yǔ)義規(guī)則單純根據(jù)常數(shù)和其它屬性的值來(lái)定義某個(gè)屬性的值 2020/11/29 17 繼承屬性 ? 當(dāng)分析樹(shù)的結(jié)構(gòu)同源代碼的抽象語(yǔ)法不“匹配”時(shí)，繼承屬性將非常有用。下面的例子可以說(shuō)明怎樣用繼承屬性來(lái)解決這種不匹配問(wèn)題，產(chǎn)生這種不匹配的原因是因?yàn)槲姆ㄍǔＪ菫檎Z(yǔ)法分析而不是為翻譯設(shè)計(jì)的。 ? 例 ? 考慮如何在自頂向下的分析過(guò)程中計(jì)算 3*5和4*8*9這樣的表達(dá)式項(xiàng) ? 消除左遞歸之后的算數(shù)表達(dá)式文法的一個(gè)子集： T→FT 39。 T 39?！?FT139。 T 39。→ε F→digit 2020/11/29 18 表 為適于自頂向下分析的文法設(shè)計(jì)的語(yǔ)法制導(dǎo)定義 產(chǎn)生式 語(yǔ)義規(guī)則 T→FT 39。 T 39。.inh := := T 39。.syn T 39?！?FT139。 T139。.inh := T 39。.inh T 39。.syn := T139。.syn T 39?！?T 39。.syn := T 39。.inh F→digit := 2020/11/29 19 4*8*9的注釋分析樹(shù) T . v a l = 2 8 8F . v a l = 4d i g i t . l e x v a l = 4*T 39。 . i n h = 4T 39。 . s y n = 2 8 8F . v a l = 8d i g i t . l e x v a l = 8T139。 . i n h = 3 2T139。 . s y n = 2 8 8⑴⑵⑶⑷⑸⑹⑺⑻⑼*F . v a l = 9εd i g i t . l e x v a l = 9T139。 . i n h = 2 8 8T139。 . s y n = 2 8 8⑽⑾⑿⒀2020/11/29 20 表 ? 如果對(duì) 4*8*9進(jìn)行自頂向下的語(yǔ)法制導(dǎo)翻譯，則 val的值的計(jì)算順序?yàn)?⑴⑵⑶⑷⑸⑹⑺⑻⑼⑽⑾⑿⒀ ? 根據(jù)上述對(duì) val值的計(jì)算順序 ， 可以將表 的語(yǔ)法制導(dǎo)定義轉(zhuǎn)換成如下的翻譯模式 ? T→F{T 39。.inh := }T 39。{:= T 39。.syn} ? T 39?！?F{T139。.inh := T 39。.inh }T139。{T 39。.syn := T139。.syn} ? T 39?！舺T 39。.syn := T