編譯原理-第6章-語法制導(dǎo)翻譯及屬性文法

1、第六章第六章 語法制導(dǎo)翻譯與語法制導(dǎo)翻譯與屬性文法屬性文法School of Computer Science & Technology Harbin Institute of Technology重點(diǎn)：重點(diǎn)：語法制導(dǎo)翻譯的基本思想，語法制導(dǎo)定義，語法制導(dǎo)翻譯的基本思想，語法制導(dǎo)定義， 翻譯模式，自頂向下翻譯，自底向上翻譯。翻譯模式，自頂向下翻譯，自底向上翻譯。 難點(diǎn)：難點(diǎn)：屬性的意義，對綜合屬性，繼承屬性，屬性的意義，對綜合屬性，繼承屬性， 固有屬性的理解，屬性計(jì)算，固有屬性的理解，屬性計(jì)算， 怎么通過屬性來表達(dá)翻譯。怎么通過屬性來表達(dá)翻譯。 2022-5-102第第6章章 語法制導(dǎo)翻譯與屬

2、性文法語法制導(dǎo)翻譯與屬性文法 6.1 語法制導(dǎo)翻譯概述語法制導(dǎo)翻譯概述6.2 語法制導(dǎo)定義語法制導(dǎo)定義6.3 屬性計(jì)算屬性計(jì)算6.4 翻譯模式翻譯模式6.5 本章小結(jié)本章小結(jié)2022-5-103n為什么進(jìn)行詞法和語法分析？為什么進(jìn)行詞法和語法分析？n用用A進(jìn)行歸約表達(dá)的是什么意思？進(jìn)行歸約表達(dá)的是什么意思？n看：看：operand+term nEE1+TnE1的值的值+T的值的結(jié)果作為的值的結(jié)果作為E的值的值即：取來即：取來E1的值和的值和T的值做加法運(yùn)算，結(jié)果作為的值做加法運(yùn)算，結(jié)果作為E的值的值E.val=E1.val+T.val問題2022-5-1046.1 語法制導(dǎo)翻譯概述語法制導(dǎo)翻譯

3、概述n為了提高編譯程序的可移植性，一般將編譯程為了提高編譯程序的可移植性，一般將編譯程序劃分為前端和后端。序劃分為前端和后端。n前端通常包括詞法分析、語法分析、語義分析、中前端通常包括詞法分析、語法分析、語義分析、中間代碼生成、符號表的建立，以及與機(jī)器無關(guān)的中間代碼生成、符號表的建立，以及與機(jī)器無關(guān)的中間代碼優(yōu)化等，它們的實(shí)現(xiàn)一般不依賴于具體的目間代碼優(yōu)化等，它們的實(shí)現(xiàn)一般不依賴于具體的目標(biāo)機(jī)器。標(biāo)機(jī)器。 n后端通常包括與機(jī)器有關(guān)的代碼優(yōu)化、目標(biāo)代碼的后端通常包括與機(jī)器有關(guān)的代碼優(yōu)化、目標(biāo)代碼的生成、相關(guān)的錯(cuò)誤處理以及符號表的訪問等。生成、相關(guān)的錯(cuò)誤處理以及符號表的訪問等。 圖圖6.1 編譯器

4、前端的邏輯結(jié)構(gòu)編譯器前端的邏輯結(jié)構(gòu)2022-5-1056.1 語法制導(dǎo)翻譯概述語法制導(dǎo)翻譯概述n語義分析器的主要任務(wù)是檢查各個(gè)語法結(jié)構(gòu)的語義分析器的主要任務(wù)是檢查各個(gè)語法結(jié)構(gòu)的靜態(tài)語義靜態(tài)語義 ，稱為靜態(tài)語義分析或靜態(tài)檢查，稱為靜態(tài)語義分析或靜態(tài)檢查 n類型檢查：操作數(shù)和操作符的類型是否相容；類型檢查：操作數(shù)和操作符的類型是否相容；n控制流檢查：控制流轉(zhuǎn)向的目標(biāo)地址是否合法；控制流檢查：控制流轉(zhuǎn)向的目標(biāo)地址是否合法；n惟一性檢查：對象是否被重復(fù)定義；惟一性檢查：對象是否被重復(fù)定義；n關(guān)聯(lián)名檢查：同一名字的多次特定出現(xiàn)是否一致。關(guān)聯(lián)名檢查：同一名字的多次特定出現(xiàn)是否一致。 n將靜態(tài)檢查和中間代碼

5、生成結(jié)合到語法分析中將靜態(tài)檢查和中間代碼生成結(jié)合到語法分析中進(jìn)行的技術(shù)稱為進(jìn)行的技術(shù)稱為語法制導(dǎo)翻譯語法制導(dǎo)翻譯 。2022-5-1066.1 語法制導(dǎo)翻譯概述語法制導(dǎo)翻譯概述n語法制導(dǎo)翻譯的基本思想語法制導(dǎo)翻譯的基本思想n在進(jìn)行語法分析的同時(shí)，完成相應(yīng)的語義處理。也在進(jìn)行語法分析的同時(shí)，完成相應(yīng)的語義處理。也就是說，一旦語法分析器識別出一個(gè)語法結(jié)構(gòu)就要就是說，一旦語法分析器識別出一個(gè)語法結(jié)構(gòu)就要立即對其進(jìn)行翻譯，翻譯是根據(jù)語言的語義進(jìn)行的，立即對其進(jìn)行翻譯，翻譯是根據(jù)語言的語義進(jìn)行的，并通過調(diào)用事先為該語法結(jié)構(gòu)編寫的語義子程序來并通過調(diào)用事先為該語法結(jié)構(gòu)編寫的語義子程序來實(shí)現(xiàn)。實(shí)現(xiàn)。 n對文

6、法中的每個(gè)產(chǎn)生式附加一個(gè)對文法中的每個(gè)產(chǎn)生式附加一個(gè)/多個(gè)語義動作多個(gè)語義動作(或或語義子程序語義子程序)，在語法分析的過程中，每當(dāng)需要使，在語法分析的過程中，每當(dāng)需要使用一個(gè)產(chǎn)生式進(jìn)行推導(dǎo)或歸約時(shí)，語法分析程序除用一個(gè)產(chǎn)生式進(jìn)行推導(dǎo)或歸約時(shí)，語法分析程序除執(zhí)行相應(yīng)的語法分析動作外，還要執(zhí)行相應(yīng)的語義執(zhí)行相應(yīng)的語法分析動作外，還要執(zhí)行相應(yīng)的語義動作動作(或調(diào)用相應(yīng)的語義子程序或調(diào)用相應(yīng)的語義子程序)。 2022-5-1076.1 語法制導(dǎo)翻譯概述語法制導(dǎo)翻譯概述n語義子程序的功能語義子程序的功能n指明相應(yīng)產(chǎn)生式中各個(gè)文法符號的具體含義，并指明相應(yīng)產(chǎn)生式中各個(gè)文法符號的具體含義，并規(guī)定了使用該產(chǎn)

7、生式進(jìn)行分析時(shí)所應(yīng)采取的語義規(guī)定了使用該產(chǎn)生式進(jìn)行分析時(shí)所應(yīng)采取的語義動作動作(如傳送或處理語義信息、查填符號表、計(jì)算如傳送或處理語義信息、查填符號表、計(jì)算值、生成中間代碼等值、生成中間代碼等)。n語義信息的獲取和加工是和語法分析同時(shí)進(jìn)行的，語義信息的獲取和加工是和語法分析同時(shí)進(jìn)行的，而且這些語義信息是通過文法符號來攜帶和傳遞而且這些語義信息是通過文法符號來攜帶和傳遞的。的。2022-5-1086.1 語法制導(dǎo)翻譯概述語法制導(dǎo)翻譯概述n一個(gè)文法符號一個(gè)文法符號X所攜帶的語義信息稱為所攜帶的語義信息稱為X的語的語義屬性，簡稱為屬性，它是根據(jù)翻譯的需要設(shè)義屬性，簡稱為屬性，它是根據(jù)翻譯的需要設(shè)置的

8、置的(對應(yīng)分析樹結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)對應(yīng)分析樹結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu))，主要用于，主要用于描述語法結(jié)構(gòu)的語義。描述語法結(jié)構(gòu)的語義。n一個(gè)變量的屬性有類型、層次、存儲地址等一個(gè)變量的屬性有類型、層次、存儲地址等n表達(dá)式的屬性有類型、值等。表達(dá)式的屬性有類型、值等。2022-5-1096.1 語法制導(dǎo)翻譯概述語法制導(dǎo)翻譯概述n屬性值的計(jì)算和產(chǎn)生式相關(guān)聯(lián)，隨著語法屬性值的計(jì)算和產(chǎn)生式相關(guān)聯(lián)，隨著語法分析的進(jìn)行，執(zhí)行屬性值的計(jì)算，完成語分析的進(jìn)行，執(zhí)行屬性值的計(jì)算，完成語義分析和翻譯的任務(wù)。義分析和翻譯的任務(wù)。nEE1 + E2E.val:=E1.val+E2.valn語法結(jié)構(gòu)具有規(guī)定的語義語法結(jié)構(gòu)具有規(guī)定的語義n

9、問題：如何根據(jù)被識別出的語法成分進(jìn)行問題：如何根據(jù)被識別出的語法成分進(jìn)行語義處理？語義處理？n亦即怎樣亦即怎樣將屬性值的計(jì)算及翻譯工作同產(chǎn)生式將屬性值的計(jì)算及翻譯工作同產(chǎn)生式相關(guān)聯(lián)？相關(guān)聯(lián)？2022-5-1010典型處理方法一典型處理方法一n語法制導(dǎo)定義語法制導(dǎo)定義n通過將屬性與文法符號關(guān)聯(lián)、將語義規(guī)則與產(chǎn)生通過將屬性與文法符號關(guān)聯(lián)、將語義規(guī)則與產(chǎn)生式關(guān)聯(lián)來描述語言結(jié)構(gòu)的翻譯方案式關(guān)聯(lián)來描述語言結(jié)構(gòu)的翻譯方案 n對應(yīng)每一個(gè)產(chǎn)生式編寫一個(gè)語義子程序，當(dāng)一個(gè)對應(yīng)每一個(gè)產(chǎn)生式編寫一個(gè)語義子程序，當(dāng)一個(gè)產(chǎn)生式獲得匹配時(shí)，就調(diào)用相應(yīng)的語義子程序來產(chǎn)生式獲得匹配時(shí)，就調(diào)用相應(yīng)的語義子程序來實(shí)現(xiàn)語義檢查與翻

10、譯實(shí)現(xiàn)語義檢查與翻譯nEE1 + TE.val:=E1.val+T.valnTT1 * FT.val:=T1.val*F.valnF digitF.val:=digit.lexvaln適宜在完成歸約的時(shí)候進(jìn)行適宜在完成歸約的時(shí)候進(jìn)行2022-5-1011典型處理方法二典型處理方法二n翻譯模式翻譯模式n通過將屬性與文法符號關(guān)聯(lián)，并將語義規(guī)則插入到產(chǎn)生式通過將屬性與文法符號關(guān)聯(lián)，并將語義規(guī)則插入到產(chǎn)生式的右部來描述語言結(jié)構(gòu)的翻譯方案的右部來描述語言結(jié)構(gòu)的翻譯方案 n在產(chǎn)生式的右部的適當(dāng)位置，插入相應(yīng)的語義動在產(chǎn)生式的右部的適當(dāng)位置，插入相應(yīng)的語義動作，按照分析的進(jìn)程，執(zhí)行遇到的語義動作作，按照分析

11、的進(jìn)程，執(zhí)行遇到的語義動作nD T L.inh := T.type LnT int T.type := integer nT real T.type := real nL L1.inh := L.inh L1,idaddtype(id.entry,L.inh) nL idaddtype(id.entry,L.inh)n 適宜在進(jìn)行推導(dǎo)時(shí)完成適宜在進(jìn)行推導(dǎo)時(shí)完成2022-5-10126.2 語法制導(dǎo)定義語法制導(dǎo)定義n語法制導(dǎo)定義是附帶有屬性和語義規(guī)則的上語法制導(dǎo)定義是附帶有屬性和語義規(guī)則的上下文無關(guān)文法下文無關(guān)文法n屬性是與文法符號相關(guān)聯(lián)的語義信息屬性是與文法符號相關(guān)聯(lián)的語義信息 n語義規(guī)則是與

12、產(chǎn)生式相關(guān)聯(lián)的語義動作語義規(guī)則是與產(chǎn)生式相關(guān)聯(lián)的語義動作 n語法制導(dǎo)定義是基于語言結(jié)構(gòu)的語義要求設(shè)語法制導(dǎo)定義是基于語言結(jié)構(gòu)的語義要求設(shè)計(jì)的，類似于程序設(shè)計(jì)，語法制導(dǎo)定義中的計(jì)的，類似于程序設(shè)計(jì)，語法制導(dǎo)定義中的屬性類似于程序中用到的數(shù)據(jù)結(jié)構(gòu)，用于描屬性類似于程序中用到的數(shù)據(jù)結(jié)構(gòu)，用于描述語義信息，語義規(guī)則類似于計(jì)算，用于收述語義信息，語義規(guī)則類似于計(jì)算，用于收集、傳遞和計(jì)算語義信息的。集、傳遞和計(jì)算語義信息的。n屬性通常被保存在分析樹的相關(guān)節(jié)點(diǎn)中屬性通常被保存在分析樹的相關(guān)節(jié)點(diǎn)中 2022-5-1013概念術(shù)語概念術(shù)語n綜合屬性：節(jié)點(diǎn)的屬性值是通過分析樹中該綜合屬性：節(jié)點(diǎn)的屬性值是通過分析樹

13、中該節(jié)點(diǎn)或其子節(jié)點(diǎn)的屬性值計(jì)算出來的節(jié)點(diǎn)或其子節(jié)點(diǎn)的屬性值計(jì)算出來的n繼承屬性：節(jié)點(diǎn)的屬性值是由該節(jié)點(diǎn)、該節(jié)繼承屬性：節(jié)點(diǎn)的屬性值是由該節(jié)點(diǎn)、該節(jié)點(diǎn)的兄弟節(jié)點(diǎn)或父節(jié)點(diǎn)的屬性值計(jì)算出來的點(diǎn)的兄弟節(jié)點(diǎn)或父節(jié)點(diǎn)的屬性值計(jì)算出來的n固有屬性：通過詞法分析直接得到的屬性固有屬性：通過詞法分析直接得到的屬性 n依賴圖：描述屬性之間依賴關(guān)系的圖，根據(jù)依賴圖：描述屬性之間依賴關(guān)系的圖，根據(jù)語義規(guī)則來構(gòu)造語義規(guī)則來構(gòu)造n注釋分析樹：節(jié)點(diǎn)帶有屬性值的分析樹注釋分析樹：節(jié)點(diǎn)帶有屬性值的分析樹2022-5-1014語法制導(dǎo)定義的形式語法制導(dǎo)定義的形式n在一個(gè)在一個(gè)語法制導(dǎo)定義語法制導(dǎo)定義中，中， A P都有與之相關(guān)聯(lián)

14、的都有與之相關(guān)聯(lián)的一套語義規(guī)則，規(guī)則形式為一套語義規(guī)則，規(guī)則形式為 b：= f（c1，c2，ck），），f是一個(gè)函數(shù)，而且或者是一個(gè)函數(shù)，而且或者 1b是是A的一個(gè)綜合屬性并且的一個(gè)綜合屬性并且c1，c2，ck是是 中的中的符號的屬性，或者符號的屬性，或者 2b是是 中中某個(gè)某個(gè)符號的一個(gè)繼承屬性并且符號的一個(gè)繼承屬性并且c1，c2，ck是是A或或 中的中的任何文法符號的屬性。任何文法符號的屬性。 這兩種情況下，都說屬性這兩種情況下，都說屬性b依賴于屬性依賴于屬性c1，c2，ck2022-5-1015例例6.1 臺式計(jì)算器的語法制導(dǎo)定義臺式計(jì)算器的語法制導(dǎo)定義產(chǎn)生式 語義規(guī)則LEn print

15、(Eval)(可看作是L的虛屬性)E E1+T Eval := E1val+TvalE T Eval := TvalT T1*F Tval := T1val+FvalT F Tval := FvalF (E) Fval := EvalF digit Fval := digitlexval2022-5-1016S-屬性屬性定義定義n只含綜合屬性的語法制導(dǎo)定義稱為只含綜合屬性的語法制導(dǎo)定義稱為S-屬性定屬性定義義n對于對于S-屬性定義，通常使用自底向上的分析屬性定義，通常使用自底向上的分析方法，在建立每一個(gè)結(jié)點(diǎn)處使用語義規(guī)則來方法，在建立每一個(gè)結(jié)點(diǎn)處使用語義規(guī)則來計(jì)算綜合屬性值，即在用哪個(gè)產(chǎn)生式進(jìn)

16、行歸計(jì)算綜合屬性值，即在用哪個(gè)產(chǎn)生式進(jìn)行歸約后，就執(zhí)行那個(gè)產(chǎn)生式的約后，就執(zhí)行那個(gè)產(chǎn)生式的S-屬性定義計(jì)算屬性定義計(jì)算屬性的值，從葉結(jié)點(diǎn)到根結(jié)點(diǎn)進(jìn)行計(jì)算。屬性的值，從葉結(jié)點(diǎn)到根結(jié)點(diǎn)進(jìn)行計(jì)算。n沒有副作用的語法制導(dǎo)定義有時(shí)又稱為沒有副作用的語法制導(dǎo)定義有時(shí)又稱為屬性屬性文法文法，屬性文法的語義規(guī)則單純根據(jù)常數(shù)和，屬性文法的語義規(guī)則單純根據(jù)常數(shù)和其它屬性的值來定義某個(gè)屬性的值其它屬性的值來定義某個(gè)屬性的值 2022-5-1017繼承屬性繼承屬性n當(dāng)分析樹的結(jié)構(gòu)同源代碼的抽象語法不當(dāng)分析樹的結(jié)構(gòu)同源代碼的抽象語法不“匹匹配配”時(shí)，繼承屬性將非常有用。下面的例子時(shí)，繼承屬性將非常有用。下面的例子可以說

17、明怎樣用繼承屬性來解決這種不匹配可以說明怎樣用繼承屬性來解決這種不匹配問題，產(chǎn)生這種不匹配的原因是因?yàn)槲姆ㄍ▎栴}，產(chǎn)生這種不匹配的原因是因?yàn)槲姆ㄍǔＪ菫檎Z法分析而不是為翻譯設(shè)計(jì)的。常是為語法分析而不是為翻譯設(shè)計(jì)的。 n例例6.2 n考慮如何在自頂向下的分析過程中計(jì)算考慮如何在自頂向下的分析過程中計(jì)算3*5和和4*8*9這樣的表達(dá)式項(xiàng)這樣的表達(dá)式項(xiàng)n消除左遞歸之后的算數(shù)表達(dá)式文法的一個(gè)子集：消除左遞歸之后的算數(shù)表達(dá)式文法的一個(gè)子集： TFT T *FT1 T Fdigit 2022-5-1018表表6.3 為適于自頂向下分析的文法設(shè)為適于自頂向下分析的文法設(shè)計(jì)的語法制導(dǎo)定義計(jì)的語法制導(dǎo)定義 產(chǎn)生

18、式產(chǎn)生式語義規(guī)則語義規(guī)則TFT T .inh := F.valT.val:= T .syn T *FT1T1.inh := T .inhF.valT .syn := T1.synT T .syn := T .inhFdigitF.val:=digit.lexval2022-5-10194*8*9的注釋分析樹的注釋分析樹 2022-5-1020表表6.3中語法制導(dǎo)定義對應(yīng)的翻譯模式中語法制導(dǎo)定義對應(yīng)的翻譯模式n如果對如果對4*8*9進(jìn)行自頂向下的語法制導(dǎo)翻譯，進(jìn)行自頂向下的語法制導(dǎo)翻譯，則則val的值的計(jì)算順序?yàn)榈闹档挠?jì)算順序?yàn)閚根據(jù)上述對根據(jù)上述對val值的計(jì)算順序值的計(jì)算順序，可以將表可以將

19、表6.3中中的語法制導(dǎo)定義轉(zhuǎn)換成如下的翻譯模式的語法制導(dǎo)定義轉(zhuǎn)換成如下的翻譯模式 nTFT .inh := F.valT T.val:= T .synnT *FT1.inh := T .inhF.valT1T .syn := T1.synnT T .syn := T .inhnFdigitF.val:=digit.lexval 2022-5-10216.3 屬性計(jì)算屬性計(jì)算n語義規(guī)則定義了屬性之間的依賴關(guān)系，這種語義規(guī)則定義了屬性之間的依賴關(guān)系，這種依賴關(guān)系將影響屬性的計(jì)算順序依賴關(guān)系將影響屬性的計(jì)算順序n為了確定分析樹中各個(gè)屬性的計(jì)算順序，我為了確定分析樹中各個(gè)屬性的計(jì)算順序，我們可以用圖來

20、表示屬性之間的依賴關(guān)系，并們可以用圖來表示屬性之間的依賴關(guān)系，并將其稱為依賴圖將其稱為依賴圖n如果依賴圖中沒有回路，則利用它可以很方如果依賴圖中沒有回路，則利用它可以很方便地求出屬性的計(jì)算順序。便地求出屬性的計(jì)算順序。n注釋分析樹只是給出了屬性的值，而依賴圖注釋分析樹只是給出了屬性的值，而依賴圖則可以幫助我們確定如何將這些屬性值計(jì)算則可以幫助我們確定如何將這些屬性值計(jì)算出來。出來。2022-5-10226.3.1 依賴圖依賴圖n所謂依賴圖其實(shí)就是一個(gè)有向圖，用于描述所謂依賴圖其實(shí)就是一個(gè)有向圖，用于描述分析樹中節(jié)點(diǎn)的屬性和屬性間的相互依賴關(guān)分析樹中節(jié)點(diǎn)的屬性和屬性間的相互依賴關(guān)系，稱為分析樹的

21、依賴圖。系，稱為分析樹的依賴圖。n每個(gè)屬性對應(yīng)依賴圖中的一個(gè)節(jié)點(diǎn)，如果屬每個(gè)屬性對應(yīng)依賴圖中的一個(gè)節(jié)點(diǎn)，如果屬性性b依賴于屬性依賴于屬性c，則從屬性，則從屬性c的節(jié)點(diǎn)有一條有的節(jié)點(diǎn)有一條有向邊指向?qū)傩韵蜻呏赶驅(qū)傩詁的節(jié)點(diǎn)。的節(jié)點(diǎn)。n屬性間的依賴關(guān)系是根據(jù)相應(yīng)的語義規(guī)則確屬性間的依賴關(guān)系是根據(jù)相應(yīng)的語義規(guī)則確定的。定的。 2022-5-1023依賴圖的構(gòu)造方法依賴圖的構(gòu)造方法for分析樹的每個(gè)節(jié)點(diǎn)分析樹的每個(gè)節(jié)點(diǎn)n dofor與節(jié)點(diǎn)與節(jié)點(diǎn)n對應(yīng)的文法符號的每個(gè)屬性對應(yīng)的文法符號的每個(gè)屬性a do在依賴圖中為在依賴圖中為a構(gòu)造一個(gè)節(jié)點(diǎn)；構(gòu)造一個(gè)節(jié)點(diǎn)；for 分析樹的每個(gè)節(jié)點(diǎn)分析樹的每個(gè)節(jié)點(diǎn)n do

22、for 節(jié)點(diǎn)節(jié)點(diǎn)n所用產(chǎn)生式對應(yīng)的每條語義規(guī)則所用產(chǎn)生式對應(yīng)的每條語義規(guī)則b := f(c1, c2 ,ck) dofor i := 1 to k do構(gòu)造一條從節(jié)點(diǎn)構(gòu)造一條從節(jié)點(diǎn)ci到節(jié)點(diǎn)到節(jié)點(diǎn)b的有向邊；的有向邊；2022-5-1024例例6.3 圖圖6.3中注釋分析樹的依賴中注釋分析樹的依賴圖圖2022-5-10256.3.2 屬性的計(jì)算順屬性的計(jì)算順序序n拓?fù)渑判蛲負(fù)渑判騨一個(gè)無環(huán)有向圖的拓?fù)渑判蚴菆D中結(jié)點(diǎn)的任何順一個(gè)無環(huán)有向圖的拓?fù)渑判蚴菆D中結(jié)點(diǎn)的任何順序序m1，m2，mk，使得邊必須是從序列中前面，使得邊必須是從序列中前面的結(jié)點(diǎn)指向后面的結(jié)點(diǎn)，也就是說，如果的結(jié)點(diǎn)指向后面的結(jié)點(diǎn)，也

23、就是說，如果mimj是是mi到到mj的一條邊的一條邊,那么在那么在 序列中序列中mi必須出現(xiàn)在必須出現(xiàn)在mj的前面。的前面。n若依賴圖中無環(huán)，則存在一個(gè)拓?fù)渑判?，它就是若依賴圖中無環(huán)，則存在一個(gè)拓?fù)渑判?，它就是屬性值的?jì)算順序。屬性值的計(jì)算順序。n例例6.4 圖圖6.4的拓?fù)渑判驗(yàn)椋旱耐負(fù)渑判驗(yàn)椋?1， 2， 3，4，5，6，7，8，9，10，11，12，132022-5-10266.3.2 屬性的計(jì)算順序?qū)傩缘挠?jì)算順序n根據(jù)拓?fù)渑判虻玫降姆g程序根據(jù)拓?fù)渑判虻玫降姆g程序na4:=4 a5:=a4 a6:=8na7:=a5a6 a8:=9 a9:=a7a8na10:=a9 a11:=a10

24、a12:=a11na13:=a12n上述屬性計(jì)算方法又稱為上述屬性計(jì)算方法又稱為分析樹法分析樹法，這種方法在編，這種方法在編譯時(shí)需要顯式地構(gòu)造分析樹和依賴圖，所以編譯的譯時(shí)需要顯式地構(gòu)造分析樹和依賴圖，所以編譯的時(shí)空效率比較低，而且如果分析樹的依賴圖中存在時(shí)空效率比較低，而且如果分析樹的依賴圖中存在回路的話，這種方法將會失效?；芈返脑?，這種方法將會失效。n這種方法的優(yōu)點(diǎn)是可以多次遍歷分析樹，從而使得這種方法的優(yōu)點(diǎn)是可以多次遍歷分析樹，從而使得屬性的計(jì)算不依賴于所采用的語法分析方法以及屬屬性的計(jì)算不依賴于所采用的語法分析方法以及屬性間嚴(yán)格的依賴關(guān)系。性間嚴(yán)格的依賴關(guān)系。 2022-5-1027計(jì)

25、算語義規(guī)則的其他方法計(jì)算語義規(guī)則的其他方法n基于規(guī)則的方法基于規(guī)則的方法n 在構(gòu)造編譯器時(shí)，用手工或?qū)ｉT的工具來分析語在構(gòu)造編譯器時(shí)，用手工或?qū)ｉT的工具來分析語義規(guī)則義規(guī)則,確定屬性值的計(jì)算順序。確定屬性值的計(jì)算順序。n 忽略語義規(guī)則的方法忽略語義規(guī)則的方法n 在分析過程中翻譯，那么計(jì)算順序由分析方法來在分析過程中翻譯，那么計(jì)算順序由分析方法來確定而表面上與語義規(guī)則無關(guān)。這種方法限制了確定而表面上與語義規(guī)則無關(guān)。這種方法限制了能被實(shí)現(xiàn)的語法制導(dǎo)定義的種類。能被實(shí)現(xiàn)的語法制導(dǎo)定義的種類。n 這兩種方法都不必顯式構(gòu)造依賴圖，因此時(shí)這兩種方法都不必顯式構(gòu)造依賴圖，因此時(shí)空效率更高?？招矢?。202

26、2-5-1028S-屬性定義屬性定義n定義定義6.1 只含綜合屬性的語法制導(dǎo)定義稱為只含綜合屬性的語法制導(dǎo)定義稱為S-屬性定屬性定義，又稱為義，又稱為S-屬性文法。屬性文法。 n如果某個(gè)語法制導(dǎo)定義是如果某個(gè)語法制導(dǎo)定義是S-屬性定義，則可以按照屬性定義，則可以按照自下而上的順序來計(jì)算分析樹中節(jié)點(diǎn)的屬性。自下而上的順序來計(jì)算分析樹中節(jié)點(diǎn)的屬性。n一種簡單的屬性計(jì)算方法是對分析樹進(jìn)行后根遍歷，一種簡單的屬性計(jì)算方法是對分析樹進(jìn)行后根遍歷，并在最后一次遍歷節(jié)點(diǎn)并在最后一次遍歷節(jié)點(diǎn)N時(shí)計(jì)算與節(jié)點(diǎn)時(shí)計(jì)算與節(jié)點(diǎn)N相關(guān)聯(lián)的屬相關(guān)聯(lián)的屬性。性。 npostorder(N) nfor N的每個(gè)子節(jié)點(diǎn)的每個(gè)子節(jié)

27、點(diǎn)M(從左到右從左到右) postorder(M);n計(jì)算與節(jié)點(diǎn)計(jì)算與節(jié)點(diǎn)N相關(guān)聯(lián)的屬性相關(guān)聯(lián)的屬性;n 2022-5-1029L-屬性定義屬性定義n定義定義6.2 一個(gè)語法制導(dǎo)定義被稱為一個(gè)語法制導(dǎo)定義被稱為L-屬性定義，屬性定義，當(dāng)且僅當(dāng)它的每個(gè)屬性或者是綜合屬性，或當(dāng)且僅當(dāng)它的每個(gè)屬性或者是綜合屬性，或者是滿足如下條件的繼承屬性：設(shè)有產(chǎn)生式者是滿足如下條件的繼承屬性：設(shè)有產(chǎn)生式AX1X2Xn，其右部符號，其右部符號Xi(1in)的繼承屬的繼承屬性只依賴于下列屬性：性只依賴于下列屬性： A的繼承屬性；的繼承屬性； 產(chǎn)生式中產(chǎn)生式中Xi左邊的符號左邊的符號X1、X2、Xi-1的綜合的綜合屬性

28、或繼承屬性；屬性或繼承屬性； Xi本身的綜合屬性或繼承屬性，但前提是本身的綜合屬性或繼承屬性，但前提是Xi的屬的屬性不能在依賴圖中形成回路。性不能在依賴圖中形成回路。nL-屬性定義又稱為屬性定義又稱為L-屬性文法。屬性文法。 2022-5-1030表表6.3 L-屬性屬性定義示例定義示例 產(chǎn)生式產(chǎn)生式語義規(guī)則語義規(guī)則TFT T .inh := F.valT.val:= T .syn T *FT1T1.inh := T .inhF.valT .syn := T1.synT T .syn := T .inhFdigitF.val:=digit.lexval2022-5-1031例例6.7 不是不是

29、L-屬性定義的語法制導(dǎo)定義屬性定義的語法制導(dǎo)定義產(chǎn)生式產(chǎn)生式語義規(guī)則語義規(guī)則ABCA.syn := B.bB.inh:=f(C.c, A.syn)語義規(guī)則語義規(guī)則B.inh:=f(C.c, A.syn)定義了一個(gè)繼承屬性，所以整個(gè)定義了一個(gè)繼承屬性，所以整個(gè)語法制導(dǎo)定義就不是語法制導(dǎo)定義就不是S-屬性定義了。此外，雖然這條語義規(guī)則屬性定義了。此外，雖然這條語義規(guī)則是合法的屬性定義規(guī)則，但不滿足是合法的屬性定義規(guī)則，但不滿足L-屬性定義的要求。這是屬性定義的要求。這是因?yàn)椋簩傩砸驗(yàn)椋簩傩訠.inh的定義中用到了屬性的定義中用到了屬性C.c，而，而C在產(chǎn)生式的右在產(chǎn)生式的右部處在部處在B的右邊。雖

30、然在的右邊。雖然在L-屬性定義中可以使用兄弟節(jié)點(diǎn)的屬屬性定義中可以使用兄弟節(jié)點(diǎn)的屬性來定義某個(gè)屬性，但這些兄弟節(jié)點(diǎn)必須是左兄弟節(jié)點(diǎn)才行。性來定義某個(gè)屬性，但這些兄弟節(jié)點(diǎn)必須是左兄弟節(jié)點(diǎn)才行。因此，該語法制導(dǎo)定義也不是因此，該語法制導(dǎo)定義也不是L-屬性定義。屬性定義。 2022-5-1032L-屬性定義中的屬性計(jì)算屬性定義中的屬性計(jì)算visit(N) for N的每個(gè)子節(jié)點(diǎn)的每個(gè)子節(jié)點(diǎn)M(從左到右從左到右) 計(jì)算節(jié)點(diǎn)計(jì)算節(jié)點(diǎn)M的繼承屬性的繼承屬性; visit (M); 計(jì)算節(jié)點(diǎn)計(jì)算節(jié)點(diǎn)N的綜合屬性的綜合屬性;2022-5-1033抽象語法樹抽象語法樹是表示程序?qū)哟谓Y(jié)構(gòu)的樹，它把分析樹中是表示程

31、序?qū)哟谓Y(jié)構(gòu)的樹，它把分析樹中對語義無關(guān)緊要的成分去掉，是分析樹的抽象形式對語義無關(guān)緊要的成分去掉，是分析樹的抽象形式 ，也稱作語法結(jié)構(gòu)樹，或結(jié)構(gòu)樹。也稱作語法結(jié)構(gòu)樹，或結(jié)構(gòu)樹。 語法樹是常用的一種語法樹是常用的一種中間表示中間表示形式。形式。 把語法分析和翻譯分開。語法分析過程中完成翻譯把語法分析和翻譯分開。語法分析過程中完成翻譯有許多優(yōu)點(diǎn)，但也有一些不足：有許多優(yōu)點(diǎn)，但也有一些不足： 1.1.適于語法分析的文法可能不完全反映語言成分的適于語法分析的文法可能不完全反映語言成分的自然層次結(jié)構(gòu)；自然層次結(jié)構(gòu)； 2. 2. 由于語法分析方法的限制，對分析樹結(jié)點(diǎn)的訪由于語法分析方法的限制，對分析樹結(jié)點(diǎn)

32、的訪問順序和翻譯需要的訪問順序不一致。問順序和翻譯需要的訪問順序不一致。 6.3.5 屬性計(jì)算示例屬性計(jì)算示例抽象語法樹的構(gòu)造抽象語法樹的構(gòu)造 2022-5-1034 產(chǎn)生式產(chǎn)生式Sif B then S1 else S2的語法樹的語法樹 if-then-else | B S1 S2 賦值語句賦值語句的語法樹的語法樹 assignment variable expression 在語法樹中，運(yùn)算符號和關(guān)鍵字都不在葉結(jié)點(diǎn)，在語法樹中，運(yùn)算符號和關(guān)鍵字都不在葉結(jié)點(diǎn)，而是在內(nèi)部結(jié)點(diǎn)中出現(xiàn)。而是在內(nèi)部結(jié)點(diǎn)中出現(xiàn)。語法樹語法樹2022-5-1035構(gòu)造表達(dá)式的語法樹使用的函數(shù)構(gòu)造表達(dá)式的語法樹使用的函數(shù)

33、 1. mknode(op, left, right) 建立一個(gè)標(biāo)記為建立一個(gè)標(biāo)記為op的運(yùn)算的運(yùn)算符結(jié)點(diǎn)，兩個(gè)域符結(jié)點(diǎn)，兩個(gè)域left和和right分別是指向左右運(yùn)算對象分別是指向左右運(yùn)算對象的指針。的指針。 2mkleaf(id, entry) 建立一個(gè)標(biāo)記為建立一個(gè)標(biāo)記為id的標(biāo)識符結(jié)的標(biāo)識符結(jié)點(diǎn)，其域點(diǎn)，其域entry是指向該標(biāo)識符在符號表中相應(yīng)表項(xiàng)的是指向該標(biāo)識符在符號表中相應(yīng)表項(xiàng)的指針。指針。 3. mkleaf(num, val) 建立一個(gè)標(biāo)記為建立一個(gè)標(biāo)記為num的數(shù)結(jié)點(diǎn)，的數(shù)結(jié)點(diǎn)，其域其域val用于保存該數(shù)的值。用于保存該數(shù)的值。構(gòu)造表達(dá)式的語法樹構(gòu)造表達(dá)式的語法樹2022-

34、5-1036構(gòu)造表達(dá)式語法樹的語法制導(dǎo)定義構(gòu)造表達(dá)式語法樹的語法制導(dǎo)定義產(chǎn)生式產(chǎn)生式語義規(guī)則語義規(guī)則 T T1 * FT.node := mknode(*, T1.node, F.node) T T1 / FT.node := mknode(/, T1.node, F.node) T FT.node := F.node F (E) F.node:= E.node F idF.node := mkleaf(id, id.entry) F numF.node := mkleaf(num, num.val)2022-5-1037圖圖6.5 3*x/y的的語法樹的構(gòu)造語法樹的構(gòu)造2022-5-1038

35、3*x/y的的抽象語法樹的構(gòu)造步驟抽象語法樹的構(gòu)造步驟 p1:=mkleaf(num,3)； p2:=mkleaf(id, entry-x)； p3:=mknode(*, p1, p2)； p4:=mkleaf(id, entry-y)； p5:=mknode(/, p3, p4)； 圖圖6.5的語法樹是自底向上構(gòu)造的，對于那些為便的語法樹是自底向上構(gòu)造的，對于那些為便于進(jìn)行自頂向下分析而設(shè)計(jì)的文法來說，使用同樣于進(jìn)行自頂向下分析而設(shè)計(jì)的文法來說，使用同樣的步驟照樣可以建立圖的步驟照樣可以建立圖6.5中的抽象語法樹。當(dāng)然，中的抽象語法樹。當(dāng)然，分析樹的結(jié)構(gòu)可能大不相同，而且可能需要引入繼分析樹

36、的結(jié)構(gòu)可能大不相同，而且可能需要引入繼承屬性來傳遞語義信息。承屬性來傳遞語義信息。2022-5-1039在自頂向下分析過程中構(gòu)造語法樹在自頂向下分析過程中構(gòu)造語法樹產(chǎn)生式產(chǎn)生式語義規(guī)則語義規(guī)則 T FT T.node := T .synT .inh := F.node T *FT1T1.inh := mknode(*, T .inh, F.node)T .syn:= T1.syn T /FT1T1.inh := mknode(/, T .inh, F.node)T .syn:= T1.syn T T .syn := T .inh F (E)F.node := E.node F idF.node

37、 := mkleaf(id, id.entry) F numF.node := mkleaf(num, num.val)2022-5-1040根據(jù)表根據(jù)表6.6的語法制導(dǎo)定義構(gòu)造的語法制導(dǎo)定義構(gòu)造的的語法樹語法樹2022-5-1041l 定義定義 翻譯模式翻譯模式是語法制導(dǎo)定義的一種便于實(shí)現(xiàn)的書寫是語法制導(dǎo)定義的一種便于實(shí)現(xiàn)的書寫形式。其中屬性與文法符號相關(guān)聯(lián)，語義規(guī)則或語義形式。其中屬性與文法符號相關(guān)聯(lián)，語義規(guī)則或語義動作用花括號動作用花括號 括起來，并可被插入到產(chǎn)生式右括起來，并可被插入到產(chǎn)生式右部的任何合適的位置上。部的任何合適的位置上。 這是一種語法分析和語義動作交錯(cuò)的表示法，它這是一

38、種語法分析和語義動作交錯(cuò)的表示法，它表達(dá)在按深度優(yōu)先遍歷分析樹的過程中何時(shí)執(zhí)行語義表達(dá)在按深度優(yōu)先遍歷分析樹的過程中何時(shí)執(zhí)行語義動作。動作。 翻譯模式給出了使用語義規(guī)則進(jìn)行計(jì)算的順序。翻譯模式給出了使用語義規(guī)則進(jìn)行計(jì)算的順序。可看成是分析過程中翻譯的注釋。可看成是分析過程中翻譯的注釋。6.4 翻譯模式翻譯模式2022-5-1042 將中綴表達(dá)式翻譯成后綴表達(dá)式：將中綴表達(dá)式翻譯成后綴表達(dá)式： ETR Raddop T print(addop.lexeme)R1| Tnumprint(num.val) 把語義動作看成終結(jié)符號，輸入把語義動作看成終結(jié)符號，輸入3+4-5,其分析樹其分析樹如圖如圖6

39、.8，當(dāng)按深度優(yōu)先遍歷它，執(zhí)行遍歷中訪問的，當(dāng)按深度優(yōu)先遍歷它，執(zhí)行遍歷中訪問的語義動作，將輸出語義動作，將輸出 3 4 + 5 -它是輸入表達(dá)式它是輸入表達(dá)式3+4-5的后綴式。的后綴式。例例6.10 一個(gè)簡單的翻譯模式一個(gè)簡單的翻譯模式2022-5-1043圖圖6.8 3+4-5的帶語義動作的分析樹的帶語義動作的分析樹2022-5-1044l 前提前提語法制導(dǎo)定義是語法制導(dǎo)定義是L-屬性定義屬性定義 保證語義動作不會引用還沒計(jì)算出來的屬性值保證語義動作不會引用還沒計(jì)算出來的屬性值1. 只需要綜合屬性的情況只需要綜合屬性的情況 為每一個(gè)語義規(guī)則建立一個(gè)包含賦值的動作，為每一個(gè)語義規(guī)則建立一個(gè)

40、包含賦值的動作，并把該動作放在相應(yīng)的產(chǎn)生式右部的末尾。并把該動作放在相應(yīng)的產(chǎn)生式右部的末尾。 例如：例如：TT1*F T val:=T1 val*F val 轉(zhuǎn)換成：轉(zhuǎn)換成： TT1*FT val:=T1 val*F val翻譯模式的設(shè)計(jì)翻譯模式的設(shè)計(jì) 根據(jù)語法制導(dǎo)定義根據(jù)語法制導(dǎo)定義2022-5-10452. 既有綜合屬性又有繼承屬性既有綜合屬性又有繼承屬性l 產(chǎn)生式右邊的符號的繼承屬性必須在這個(gè)產(chǎn)生式右邊的符號的繼承屬性必須在這個(gè)符號以前的動作中計(jì)算出來。符號以前的動作中計(jì)算出來。 l 一個(gè)動作不能引用這個(gè)動作右邊符號的綜一個(gè)動作不能引用這個(gè)動作右邊符號的綜合屬性。合屬性。 l 產(chǎn)生式左邊

41、非終結(jié)符號的綜合屬性只有在產(chǎn)生式左邊非終結(jié)符號的綜合屬性只有在它所引用的所有屬性都計(jì)算出來以后才能計(jì)它所引用的所有屬性都計(jì)算出來以后才能計(jì)算。計(jì)算這種屬性的動作通?？煞旁诋a(chǎn)生式算。計(jì)算這種屬性的動作通?？煞旁诋a(chǎn)生式右端的末尾。右端的末尾。翻譯模式的設(shè)計(jì)翻譯模式的設(shè)計(jì) 根據(jù)語法制導(dǎo)定義根據(jù)語法制導(dǎo)定義2022-5-1046 下面的翻譯模式不滿足要求：下面的翻譯模式不滿足要求： SA1A2 A1 in:=1; A2 in:=2 A a print(A in) /*A.in尚無定義尚無定義*/ 例例6.11 從從L-屬性制導(dǎo)定義建立一個(gè)滿足上面屬性制導(dǎo)定義建立一個(gè)滿足上面 要求的要求的翻譯模式。翻譯

42、模式。 使用文法產(chǎn)生的語言是數(shù)學(xué)排版語言使用文法產(chǎn)生的語言是數(shù)學(xué)排版語言EQN E sub 1 val編排結(jié)果編排結(jié)果2022-5-1047 B表示盒子表示盒子 BB1B2代表兩個(gè)相鄰盒子的并列，且代表兩個(gè)相鄰盒子的并列，且B1位于位于B2的的左邊。左邊。 BB1 sub B2代表盒子代表盒子B1后隨下標(biāo)盒子后隨下標(biāo)盒子B2，下標(biāo)盒，下標(biāo)盒子子 B2以較小的字體和較低的位置出現(xiàn)。以較小的字體和較低的位置出現(xiàn)。 B(B1)代表一個(gè)由括號括起來的盒子代表一個(gè)由括號括起來的盒子B1，主要是為，主要是為了對多個(gè)盒子或下標(biāo)進(jìn)行分組。在了對多個(gè)盒子或下標(biāo)進(jìn)行分組。在EQN中，使用花括中，使用花括號進(jìn)行分組

43、，此處使用圓括號是為了避免跟語義動作號進(jìn)行分組，此處使用圓括號是為了避免跟語義動作外面的花括號產(chǎn)生沖突。外面的花括號產(chǎn)生沖突。 Btext代表文本字符串，即任意字符組成的串。代表文本字符串，即任意字符組成的串。該文法是二義性的文法，將該文法是二義性的文法，將“并列并列”和和“下標(biāo)下標(biāo)”看成看成是左結(jié)合的，并令是左結(jié)合的，并令“下標(biāo)下標(biāo)”的優(yōu)先級高于的優(yōu)先級高于“并列并列”的的話，則可以對該文法所描述的語言進(jìn)行自底向上的語話，則可以對該文法所描述的語言進(jìn)行自底向上的語法分析。法分析。2022-5-1048 屬性設(shè)置屬性設(shè)置 point size用于表示盒子中文本的尺寸用于表示盒子中文本的尺寸(以

44、點(diǎn)來計(jì)算，以點(diǎn)來計(jì)算，也就是字號也就是字號)。如果標(biāo)準(zhǔn)盒子的尺寸為。如果標(biāo)準(zhǔn)盒子的尺寸為p，則下標(biāo)盒子，則下標(biāo)盒子的尺寸為的尺寸為0.7p。屬性。屬性B.ps表示盒子表示盒子B的尺寸，該屬性的尺寸，該屬性是繼承屬性。是繼承屬性。 每個(gè)盒子都有一個(gè)基線每個(gè)盒子都有一個(gè)基線(baseline)，用來表示每個(gè)文，用來表示每個(gè)文本底部的垂直位置。本底部的垂直位置。 height用來表示從盒子的頂部到基線的距離。屬性用來表示從盒子的頂部到基線的距離。屬性B.ht表示盒子表示盒子B的高度的高度height，該屬性是綜合屬性。，該屬性是綜合屬性。 depth用來表示從基線到盒子底部的距離。用屬性用來表示從基

45、線到盒子底部的距離。用屬性B.dp表示盒子表示盒子B的深度的深度depth，該屬性也是綜合屬性。，該屬性也是綜合屬性。2022-5-1049表表6.7 對盒子進(jìn)行排版的語法制導(dǎo)定義對盒子進(jìn)行排版的語法制導(dǎo)定義產(chǎn)生式產(chǎn)生式語義規(guī)則語義規(guī)則S BB.ps:=10S.ht := B.htS.dp:= B.dpB B1B2B1.ps := B.psB2.ps := B.psB.ht := max(B1.ht, B2.ht)B.dp := max(B1.dp, B2.dp)BB1 sub B2B1.ps:=B.psB2.ps:=0.7B.psB.ht:=max(B1.ht, B2.ht-0.25B.ps

46、)B.dp:=max(B1.dp, B2.dp+0.25B.ps)B (B1)B1.ps:=B.psB.ht:=B1.htB.dp:=B1.dpB textB.ht:=getheight(B.ps,text.lexval)B.dp:=getdepth(B.ps,text.lexval)2022-5-1050SB.ps:=10B S.ht := B.ht;S.dp:= B.dpBB1.ps:=B.psB1B2 .ps:=B.ps B2B.ht:=max(B1.ht,B2.ht)BB1.ps:=B.psB1subB2.ps:=0.7B.ps B2B.ht:=max(B1.ht,B2.ht-0.25

47、B.ps);B.dp:=max(B1.dp,B2.dp+0.25B.ps);B(B1.ps:=B.psB1)B.ht:=B1.ht; B.dp:=B1.dp;BtextB.ht:=getheight(B.ps,text.lexval); B.dp:=getdepth(B.ps,text.lexval)從表從表6.7構(gòu)造的翻譯模式構(gòu)造的翻譯模式2022-5-1051T F T .inh := F.nodeT T.node := T .synT *F T1.inh := mknode(*, T .inh,F.node) T1T .syn := T1.synT /F T1.inh := mknode

48、(/, T .inh,F.node) T1T .syn := T1.synT T .syn := T .inhF (E )F.node := E.nodeF id F.node := mkleaf(id, id.entry)F num F.node := mkleaf(num, num.val)從表從表6.6構(gòu)造的翻譯模式構(gòu)造的翻譯模式2022-5-1052在分析棧中使用一個(gè)附加的域來存放綜合屬性在分析棧中使用一個(gè)附加的域來存放綜合屬性值。下圖為一個(gè)帶有綜合屬性值域的分析棧：值。下圖為一個(gè)帶有綜合屬性值域的分析棧：stackval.XX.xY.Y.y.ZZ.ztop6.4.2 S-屬性定義的自

49、底向上計(jì)算屬性定義的自底向上計(jì)算2022-5-1053 A b:=f(c1,c2,ck) b是是A的綜合屬性，的綜合屬性，ci (1 i k)是是 中符號的屬性。中符號的屬性。綜合屬性的值是在自底向上的分析過程中，每綜合屬性的值是在自底向上的分析過程中，每次歸約之前進(jìn)行計(jì)算的。次歸約之前進(jìn)行計(jì)算的。 AXYZ A a:=f(X x,Y y,Z z)A aX x Y y Z z2022-5-1054topstackval.XX.xYY.yZZ.zstackval.AA.atop實(shí)現(xiàn)時(shí)，將定義式實(shí)現(xiàn)時(shí)，將定義式 A.a:=f(X.x, Y.y, Z.z) (抽象抽象)變變成成stackntop.v

50、al:=f(stacktop-2.val, stacktop-1.val, stacktop.val) (具體可執(zhí)行代碼具體可執(zhí)行代碼)。在執(zhí)行代碼段之前執(zhí)行：在執(zhí)行代碼段之前執(zhí)行： ntop:=top-r+1 r是句柄的長度是句柄的長度執(zhí)行代碼段后執(zhí)行：執(zhí)行代碼段后執(zhí)行： top:=ntop;2022-5-1055例例6.14 用用LR分析器實(shí)現(xiàn)分析器實(shí)現(xiàn)臺式計(jì)算器臺式計(jì)算器與表與表6.26.2對比對比LEnprint(stacktop-1.val);top:=top-1;EE1+Tstacktop-2.val:= stacktop-2.val + stacktop.val; top:=to

51、p-2;ETTT1*Fstacktop-2.val:= stacktop-2.val stacktop.val; top:=top-2;TFF(E) stacktop-2.val:= stacktop-1.val;top:=top-2;Fdigit2022-5-1056表表6.8 翻譯輸入翻譯輸入6+7*8n上的移動序列上的移動序列輸入輸入 state val 使用的產(chǎn)生式使用的產(chǎn)生式6+7*8n - - +7*8n 6 6 +7*8n F 6 Fdigit +7*8n T 6 TF +7*8n E 6 ET 7*8n E+ 6+ *8n E+7 6+72022-5-1057 *8n E+F

52、6+7 F digit *8n E+T 6+7 T F 8n E+T* 6+7* n E+T*8 6+7*8 n E+T*F 6+7*8 F digit n E+T 6+56 TT*F n E 62 E E+T En 62 L 62 L En2022-5-1058 采用自底向上分析，例如采用自底向上分析，例如LR分析，首先給分析，首先給出出S- -屬性定義，然后，把屬性定義，然后，把S- -屬性定義變成可執(zhí)屬性定義變成可執(zhí)行的代碼段，這就構(gòu)成了翻譯程序。象一座建行的代碼段，這就構(gòu)成了翻譯程序。象一座建筑，語法分析是構(gòu)架，歸約處有一個(gè)筑，語法分析是構(gòu)架，歸約處有一個(gè)“掛鉤掛鉤”，語義分析和翻譯的

53、代碼段（語義子程序）語義分析和翻譯的代碼段（語義子程序）就掛就掛在這個(gè)鉤子上。這樣，隨著語法分析的進(jìn)行，在這個(gè)鉤子上。這樣，隨著語法分析的進(jìn)行，歸約前調(diào)用相應(yīng)的語義子程序歸約前調(diào)用相應(yīng)的語義子程序, ,完成翻譯的任務(wù)。完成翻譯的任務(wù)。S-屬性定義小結(jié)屬性定義小結(jié)2022-5-1059l 用翻譯模式構(gòu)造自頂向下的翻譯。用翻譯模式構(gòu)造自頂向下的翻譯。1. 1. 從翻譯模式中消除左遞歸從翻譯模式中消除左遞歸 對于一個(gè)翻譯模式，若采用自頂向下分析，對于一個(gè)翻譯模式，若采用自頂向下分析，必須消除左遞歸和提取左公因子，在改寫基礎(chǔ)文必須消除左遞歸和提取左公因子，在改寫基礎(chǔ)文法時(shí)考慮屬性值的計(jì)算。法時(shí)考慮屬性

54、值的計(jì)算。 對于自頂向下語法分析，假設(shè)語義動作是在對于自頂向下語法分析，假設(shè)語義動作是在與之處于同一位置的文法非終結(jié)符被展開時(shí)執(zhí)行與之處于同一位置的文法非終結(jié)符被展開時(shí)執(zhí)行的，而且的，而且不考慮繼承屬性的處理（很簡單）不考慮繼承屬性的處理（很簡單）。6.4.3 L-屬性定義的自頂向下翻譯屬性定義的自頂向下翻譯2022-5-1060l 例例6.15 考慮如下將中綴表達(dá)式翻譯為后考慮如下將中綴表達(dá)式翻譯為后綴表達(dá)式的翻譯模式中的兩個(gè)產(chǎn)生式：綴表達(dá)式的翻譯模式中的兩個(gè)產(chǎn)生式：E E1+T print(+);E TE TRR +T print(+); RR 只有簡單語義動作時(shí)的左遞歸消除只有簡單語義動

55、作時(shí)的左遞歸消除2022-5-1061l 設(shè)有如下左遞歸翻譯模式：設(shè)有如下左遞歸翻譯模式： AA1YA.a:=g(A1.a,Y.y) AX A.a:=f(X.x)假設(shè)每個(gè)非終結(jié)符都有一個(gè)綜合屬性，用相應(yīng)的小假設(shè)每個(gè)非終結(jié)符都有一個(gè)綜合屬性，用相應(yīng)的小寫字母表示，寫字母表示，g和和f是任意函數(shù)。是任意函數(shù)。 l 消除左遞歸后，文法轉(zhuǎn)換成消除左遞歸后，文法轉(zhuǎn)換成 AX R RY R|S-屬性定義的左遞歸消除屬性定義的左遞歸消除2022-5-1062l 再考慮語義動作，翻譯模式變?yōu)椋涸倏紤]語義動作，翻譯模式變?yōu)椋?AX R i:=f(X x) R A a:=R s RY R1 i:=g(R i,Y

56、y) R1 R s:=R1 s R R s:=R i 經(jīng)過轉(zhuǎn)換的翻譯模式使用經(jīng)過轉(zhuǎn)換的翻譯模式使用R的繼承屬性的繼承屬性i和綜合屬性和綜合屬性s。轉(zhuǎn)換前后的結(jié)果是一樣的轉(zhuǎn)換前后的結(jié)果是一樣的,S-屬性定義的左遞歸消除屬性定義的左遞歸消除AA1Y A.a:=g(A1.a,Y.y) AX A.a:=f(X.x)引入繼承屬性引入繼承屬性R.i來收集應(yīng)用函數(shù)來收集應(yīng)用函數(shù)g的計(jì)算結(jié)果。其的計(jì)算結(jié)果。其初始值為初始值為A.a:=f(X.x）引入綜合屬性引入綜合屬性R.s在在R結(jié)束生成結(jié)束生成Y時(shí)時(shí)復(fù)制復(fù)制R.i的值。的值。2022-5-1063A a=g(g(f(X x),Y1 y),Y2 y)A a=

57、g(f(X x),Y1 y)A a=f(X x)Y2Y1X(a)輸入：輸入：XY1Y22022-5-1064AR i=f(X x)R i=g(f(X x),Y1 y)R i=g(g(f(X x),Y1 y),Y2 y)Y2Y1X(b)2022-5-1065L-屬性定義的遞歸下降翻譯器的構(gòu)造：屬性定義的遞歸下降翻譯器的構(gòu)造：1對每個(gè)非終結(jié)符對每個(gè)非終結(jié)符A構(gòu)造一個(gè)函數(shù)構(gòu)造一個(gè)函數(shù)A，將非終結(jié)符，將非終結(jié)符A的各個(gè)繼承屬性當(dāng)作函數(shù)的各個(gè)繼承屬性當(dāng)作函數(shù)A的形式參數(shù)，而將非終結(jié)的形式參數(shù)，而將非終結(jié)符符A的綜合屬性集當(dāng)作函數(shù)的綜合屬性集當(dāng)作函數(shù)A的返回值，為了便于討的返回值，為了便于討論，假設(shè)每個(gè)非

58、終結(jié)符只具有一個(gè)綜合屬性。論，假設(shè)每個(gè)非終結(jié)符只具有一個(gè)綜合屬性。2在函數(shù)在函數(shù)A的過程體中，不僅要進(jìn)行語法分析，而的過程體中，不僅要進(jìn)行語法分析，而且要處理相應(yīng)的語義屬性。函數(shù)且要處理相應(yīng)的語義屬性。函數(shù)A的代碼首先根據(jù)當(dāng)?shù)拇a首先根據(jù)當(dāng)前輸入確定用哪個(gè)產(chǎn)生式展開前輸入確定用哪個(gè)產(chǎn)生式展開A，然后按照，然后按照3中所給中所給的方法對各產(chǎn)生式進(jìn)行編碼。的方法對各產(chǎn)生式進(jìn)行編碼。2. L-屬性定義的遞歸下降翻譯法屬性定義的遞歸下降翻譯法 2022-5-10663與每個(gè)產(chǎn)生式對應(yīng)的程序代碼的工作過程為：與每個(gè)產(chǎn)生式對應(yīng)的程序代碼的工作過程為：按照從左到右的次序，依次對產(chǎn)生式右部的記號、按照從左到右

59、的次序，依次對產(chǎn)生式右部的記號、非終結(jié)符和語義動作執(zhí)行如下的動作：非終結(jié)符和語義動作執(zhí)行如下的動作：1) 對帶有綜合屬性對帶有綜合屬性x的符號的符號X，將，將x的值保存在的值保存在X.x中，中，并生成一個(gè)函數(shù)調(diào)用來匹配并生成一個(gè)函數(shù)調(diào)用來匹配X，然后繼續(xù)讀入下一個(gè)，然后繼續(xù)讀入下一個(gè)輸入符號；輸入符號；2) 對非終結(jié)符對非終結(jié)符B，生成一個(gè)右部帶有函數(shù)調(diào)用的賦值，生成一個(gè)右部帶有函數(shù)調(diào)用的賦值語句語句c:=B(b1,b2,bk)，其中，其中，b1,b2,bk是代表是代表B的的繼承屬性的變量，繼承屬性的變量，c是代表是代表B的綜合屬性的變量；的綜合屬性的變量；3) 對于語義動作，將其代碼復(fù)制到語

60、法分析器中，對于語義動作，將其代碼復(fù)制到語法分析器中，并將對屬性的引用改為對相應(yīng)變量的引用。并將對屬性的引用改為對相應(yīng)變量的引用。2. L-屬性定義的遞歸下降翻譯法屬性定義的遞歸下降翻譯法 2022-5-1067 例例 6.16 6.16 function T:syntax_tree_node; function T (inh: syntax_tree_node):syntax_tree_node; function F:syntax_tree_node; function T:syntax_tree_node;var node, syn: syntax_tree_node;beginnode