《《編譯原理》第5章語法制導(dǎo)翻譯》由會(huì)員分享，可在線閱讀，更多相關(guān)《《編譯原理》第5章語法制導(dǎo)翻譯（98頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、？？為什么進(jìn)行詞法和語法分析 ？？用A進(jìn)行歸約表達(dá)的是什么意思 看：operand+term EE1+T E1的值+T的值的結(jié)果作為E的值即：取來E1的值和T的值做加法運(yùn)算，結(jié)果作為E的值 E.val=E1.val+T.val,第五章 語法制導(dǎo)翻譯,翻譯的任務(wù) 首先是語義分析和正確性檢查，若正確，則翻譯成中間代碼或目標(biāo)代碼。 基本思想 根據(jù)翻譯的需要設(shè)置文法符號(hào)的屬性，以描述語法結(jié)構(gòu)的語義。 例如，一個(gè)變量的屬性有類型，層次，存儲(chǔ)地址等。表達(dá)式的屬性有類型，值等。 屬性值的計(jì)算和產(chǎn)生式相聯(lián)系。隨著語法分析的進(jìn)行，執(zhí)行屬性值的計(jì)算，完成語義分析和翻譯的任務(wù)。,5.1 語法制導(dǎo)翻譯概述,語法制導(dǎo)翻
2、譯的概念描述 在進(jìn)行語法分析的同時(shí)，完成相應(yīng)的語義處理 EE1 + E2E.val:=E1.val+E2.val 語法結(jié)構(gòu)具有規(guī)定的語義 問題：如何根據(jù)被識(shí)別出的語法成分進(jìn)行語義處理？,1. 語義分析的任務(wù),語義檢查 例：類型、運(yùn)算、維數(shù)、越界 語義處理 例：變量的存儲(chǔ)分配 例：表達(dá)式的求值 例：語句的翻譯（中間代碼的生成） 總目標(biāo)：生成等價(jià)的中間代碼,2. 代碼結(jié)構(gòu),計(jì)算學(xué)科：對(duì)信息（數(shù)據(jù)表示）描述和變換算法的系統(tǒng)研究 變換：源、目標(biāo)以及源與目標(biāo)的對(duì)應(yīng)關(guān)系 語句的代碼結(jié)構(gòu) 語句分類： 說明語句符號(hào)表的查填 可執(zhí)行語句指令代碼,3. 典型處理方法,對(duì)應(yīng)每一個(gè)產(chǎn)生式編制一個(gè)語義子程序，當(dāng)一個(gè)產(chǎn)生
3、式獲得匹配時(shí)，調(diào)用相應(yīng)的語義子程序?qū)崿F(xiàn)語義檢查與翻譯 EE1 + TE.val:=E1.val+T.val TT1 * FT.val:=T1.val*F.val F idF.val:=id.val 適宜在完成歸約的時(shí)候進(jìn)行,3. 典型處理方法,在產(chǎn)生式的右部的適當(dāng)位置，插入相應(yīng)的語義動(dòng)作，按照分析的進(jìn)程，執(zhí)行遇到的語義動(dòng)作 D T L.in := T.type L T int T.type := integer T real T.type := real L L1.in := L.in L1,id 語義可以看成是相應(yīng)文法符號(hào)的屬性 適宜在進(jìn)行推導(dǎo)時(shí)完成,語義翻譯的流程,輸 入 符 號(hào) 串,,
4、分 析 樹,,依 賴 圖,,語 義 規(guī) 則 的 計(jì) 算,實(shí)際上，編譯中語義翻譯的實(shí)現(xiàn)并不是按圖中的流程處理的；而是隨語法分析的進(jìn)展，識(shí)別出一個(gè)語法結(jié)構(gòu)，就對(duì)它的語義進(jìn)行分析和翻譯。,語法制導(dǎo)定義是對(duì)上下文無關(guān)文法的推廣 每個(gè)文法符號(hào)都有一個(gè)相關(guān)的屬性集。 綜合屬性:通過分析樹中其子節(jié)點(diǎn)的屬性值計(jì)算出來； 繼承屬性:由該節(jié)點(diǎn)的兄弟節(jié)點(diǎn)及父節(jié)點(diǎn)的屬性值計(jì)算出來； 依賴圖 語義規(guī)則建立了屬性之間的依賴關(guān)系，這些關(guān)系可以用圖來表示，這樣的圖稱為依賴圖。,,屬性,5.1 語法制導(dǎo)定義(Syntax-directed definitions),在一個(gè)語法制導(dǎo)定義中，AP都有與 之相關(guān)聯(lián)的一套語義
5、規(guī)則，規(guī)則形式為 b：= f（c1，c2，，ck）， f是一個(gè)函數(shù)，而且或者 1b是A的一個(gè)綜合屬性并且c1，c2，，ck 是中的符號(hào)的屬性，或者 2b是中的符號(hào)的一個(gè)繼承屬性并且c1， c2，，ck是A或中的任何文法符號(hào)的屬性。 在兩種情況下，都說屬性b依賴于屬性c1，c2，，ck。,5.1.1 語法制導(dǎo)定義的形式,例5.1 臺(tái)式計(jì)算器程序的語法制導(dǎo)定義（圖52),產(chǎn)生式 語義規(guī)則,,LEn print(Eval)(可看作是L的虛屬性) E E1+T E val := E1 val+T val E T E val := T val T T1*F
6、 T val := T1 val*F val T F T val := F val F (E) F val := E val F digit F val := digitlexval,,S-屬性定義 僅僅使用綜合屬性的語法制導(dǎo)定義。 結(jié)點(diǎn)屬性值的計(jì)算正好和自底向上分析建立分析樹結(jié)點(diǎn)同步進(jìn)行。 例 5 .2 輸入：3*5+4n,,5.1.2 綜合屬性,digitlexval:=3,Fval:=3,,,Tval:=3,digitlexval:=5,,Fval:=5,Tval:=15,,,*,,,Eval:=15,+,digitlexval:=4,,Fval:=4,
7、Tval:=4,,Eval:=19,,,,L,,n,,,,,,,,,,,,,,,綜合屬性值的計(jì)算方法 對(duì)于s-屬性定義，通常使用自底向上的分析方法，在建立每一個(gè)結(jié)點(diǎn)處使用語義規(guī)則來計(jì)算綜合屬性值，即在用哪個(gè)產(chǎn)生式進(jìn)行歸約后，就執(zhí)行那個(gè)產(chǎn)生式的s-屬性定義計(jì)算屬性的值，從葉結(jié)點(diǎn)到根結(jié)點(diǎn)進(jìn)行計(jì)算。 5.1.3 繼承屬性 繼承屬性值是由此結(jié)點(diǎn)的父結(jié)點(diǎn)和或兄弟結(jié)點(diǎn)的某些屬性值來決定的。 例5 . 3 變量說明的屬性定義 int a,b,c,,表5.2 帶有繼承屬性L.in的語法制導(dǎo)定義,,,,產(chǎn)生式 語義規(guī)則 DTL Lin:=T type T int T ty
8、pe :=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),,,T,L,L,id3,L,id2,D,id1,,,,,,,,real,,,,,,,,1 entry,2 entry,3 entry,4 type,in 5,6,in 7,8,in 9,10,,,,,,,,,,依賴圖的構(gòu)造方法 for 分析樹中的每個(gè)結(jié)點(diǎn)n do for 與結(jié)點(diǎn)n對(duì)應(yīng)的文法符號(hào)的每個(gè)屬性a do 在依賴圖中為a構(gòu)
9、造一個(gè)結(jié)點(diǎn)； for 分析樹的每個(gè)結(jié)點(diǎn)n do for 結(jié)點(diǎn)n所用產(chǎn)生式對(duì)應(yīng)的每條 語義規(guī)則 b:f（c1，c2，，ck ) do for i:=1 to k do 從結(jié)點(diǎn)ci到結(jié)點(diǎn)b構(gòu)造一條有向邊；,5.1.4 依賴圖_獲得語義規(guī)則的計(jì)算順序,例5-5 圖55分析樹的依賴圖,,拓?fù)渑判? 一個(gè)無環(huán)有向圖的拓?fù)渑判蚴菆D中 結(jié)點(diǎn)的任何順序m1，m2，，mk，使得 邊必須是從序列中前面的結(jié)點(diǎn)指向后面的 結(jié)點(diǎn)，也就是說，如果mimj是mi到mj的 一條邊,那么在 序列中mi必須出現(xiàn)在mj的 前面。 若依賴圖中無環(huán)，則存在一個(gè)拓?fù)渑判?，它就是屬性值的?jì)算順序。,5.1.5
10、 計(jì)算順序,1， 2， 3，4，5，6，7，8，9，10 a4:=real; a5:=a4; addtype(id3entry,a5); a7:=a5; addtype(id2entry,a7); a9:=a7; addtype(id1entry,a9);,例5 . 6 圖5 . 7的拓?fù)渑判蚴牵?分析樹法: 輸入串分析樹依賴圖計(jì)算次序 基于規(guī)則的方法： 在構(gòu)造編譯器時(shí)，用手工或?qū)ｉT的工具來分析語義規(guī)則,確定屬性值的計(jì)算順序。 忽略語義規(guī)則的方法：在分析過程中翻譯，那么計(jì)算順序由分析方法來確定而表面上與語義規(guī)則無關(guān)。這種方法限制了能被實(shí)現(xiàn)的語法制導(dǎo)定義的種類。 后兩
11、種方法不必顯式構(gòu)造依賴圖，因此時(shí)空效率更高。,計(jì)算語義規(guī)則的方法,抽象語法（abstract syntax） 從具體語法中抽象出語言結(jié)構(gòu)的本質(zhì)性的東西，而不考慮語言的具體符號(hào)表示，從而可簡(jiǎn)化語義的形式描述。 在不同的語言中賦值語句有不同的寫法： x=y; x:=y; yx 等等，可以用抽象形式 assignment(variable,expression) 把前面各種具體形式統(tǒng)一起來。,5.2 語法樹（syntax tree）的構(gòu)造,表示程序?qū)哟谓Y(jié)構(gòu)的樹，它把分析樹中對(duì)語義無關(guān)緊要的成分去掉，是分析樹的抽象形式 ，也稱作語法結(jié)構(gòu)樹，或結(jié)構(gòu)樹。 語法樹是常用的一種中間表示形式。 把語法分
12、析和翻譯分開。語法分析過程中完成翻譯有許多優(yōu)點(diǎn)，但也有一些不足： 1.適于語法分析的文法可能不完全反映語言成分的自然層次結(jié)構(gòu)； 2. 由于語法分析方法的限制，對(duì)分析樹結(jié)點(diǎn)的訪問順序和翻譯需要的訪問順序不一致。,語法樹,產(chǎn)生式sif B then S1 else S2的語法樹 if-then-else | B S1 S2 賦值語句的語法樹 assignment variable expression 在語法樹中，運(yùn)算符號(hào)和關(guān)鍵字都不在葉結(jié)點(diǎn)，而是在內(nèi)部結(jié)點(diǎn)中出現(xiàn)。,,,5.2.1 語法樹,構(gòu)造表達(dá)式的語法樹使用的函數(shù) 1. mknode(op,left,
13、right) 建立一個(gè)標(biāo)記為op的運(yùn)算符結(jié)點(diǎn)，兩個(gè)域left和right是指向左右運(yùn)算對(duì)象的指針。 2mkleaf(id,entry) 建立一個(gè)標(biāo)記為id的標(biāo)識(shí)符結(jié)點(diǎn),其域entry是指向該標(biāo)識(shí)符在符號(hào)表中相應(yīng)表項(xiàng)的指針。 3. mkleaf(num,val) 建立一個(gè)標(biāo)記為num的數(shù)結(jié)點(diǎn)，域val用于保存該數(shù)的值。返回指向新建立結(jié)點(diǎn)的指針。,5.2.2 構(gòu)造表達(dá)式的語法樹,id,,,to entry a,num 4,,,,,,,id,,,to entry c,+,,,,圖5-8 a-4+c的語法樹,,5.2.3 構(gòu)造語法樹的語法制導(dǎo)定義,產(chǎn)生式 語義規(guī)則 EE1+T E
14、.nptr:=mknode(+,E1.nptr,T.nptr) E E1-T E.nptr:=mknode(-,E1.nptr,T.nptr) E T E.nptr:=T.nptr T (E) T.nptr:=E.nptr T id T.nptr:=mkleaf(id,id.entry) T num T.nptr:=mkleaf(num,num.val),,,圖5-10 a-4+c的語法樹的構(gòu)造,,無環(huán)有向圖 （Directed Acyclic Graph，簡(jiǎn)稱dag) 用途：提取表達(dá)式中的公共子表達(dá)式，以取得目標(biāo)程序的局部?jī)?yōu)化。 方法：執(zhí)行mknode和mkleaf時(shí)，檢查是
15、否已有相同的結(jié)點(diǎn)，若有，則返回相應(yīng)結(jié)點(diǎn)的指針。,5.2.4 表達(dá)式的無環(huán)有向圖,例5.9 表達(dá)式 aa*(b-c)+(b-c)*d 的dag,+,*,d,+,*,a,,c,b,,,,,,,,,,在分析棧中使用一個(gè)附加的域來存放綜合屬性值。下圖為一個(gè)帶有綜合屬性值域的分析棧：,state,val,...,X,X.x,Y,...,Y.y,...,...,Z,Z.z,top,,,5.3 S-屬性定義及其自底向上的計(jì)算,A b:=f(c1,c2,,ck) b是A的綜合屬性，ci(1 ik)是中符號(hào)的屬性。綜合屬性的值是在自底向上的分析過程中，每次歸約之前進(jìn)行計(jì)算的。 AXYZ Aa:=f(X x,
16、Y y,Z z),A a,X x Y y Z z,,,,top,state,val,...,...,X,X.x,Y,Y.y,Z,Z.z,,state,val,...,...,A,A .a,,top,定義式 A .a:=f(X.x, Y.y, Z.z)（抽象）變成valntop:=f(valtop-2,valtop-1,valtop)（具體可執(zhí)行代碼）。在執(zhí)行代碼段之前執(zhí)行： ntop:=top-r+1 r是句柄的長(zhǎng)度 執(zhí)行代碼段后執(zhí)行： top:=ntop;,產(chǎn)生式 代碼段(和圖52對(duì)比） LEn printf(valntop) E E+T valntop:=valtop-2
17、+valtop E T T T*F valntop:=valtop-2*valtop T F F (E) valntop:=valtop-1 F digit,,,例5.10 用LR分析器實(shí)現(xiàn)臺(tái)式計(jì)算器(圖516）,表5.5 翻譯輸入3*5+4n所做的移動(dòng),輸入 state val 使用的產(chǎn)生式,3*5+4n - -,*5+4n 3 3,*5+4n F 3 Fdigit,*5+4n T 3 TF,5+4n T* 3-,+4n T* 5 3-5,+4n T* F 3-5 F digit,+4n T
18、 15 T T*F,+4n E 15 E T,4n E+ 15-,n E+4 15-4,n E+F 15-4 F digit,n E+T 15-4 T F,n E 19 E E+T,En 19 -,L 19 L En,采用自底向上分析，例如LR分析，首先給出S-屬性定義，然后，把S-屬性定義變成可執(zhí)行的代碼段，這就構(gòu)成了翻譯程序。象一座建筑，語法分析是構(gòu)架，歸約處有一個(gè)“掛鉤”，語義分析和翻譯的代碼段（語義子程序）就掛在這個(gè)鉤子上。這樣，隨著語法分析的進(jìn)行，歸約前調(diào)用相應(yīng)的語義子程序,
19、完成翻譯的任務(wù)。,總結(jié),在語法分析過程中進(jìn)行語義分析和翻譯，屬 性的計(jì)算順序受到語法分析建立分析樹結(jié)點(diǎn)順序的限制。 一種自然的計(jì)算屬性的順序是按深度優(yōu)先訪問分析樹結(jié)點(diǎn)的順序，它適應(yīng)多種自底向上和自頂向下的翻譯方法。 L-屬性定義 可用于按深度優(yōu)先順序計(jì)算屬性值。,5.4 L-屬性定義,procedure dfvisit(n:node); begin for n 的每個(gè)子結(jié)點(diǎn)m(從左至右) do begin 計(jì)算m的繼承屬性； dfvisit(m) end; 計(jì)算n的綜合屬性 end;,深度優(yōu)先順序計(jì)算屬性,定義 一個(gè)語法制導(dǎo)定義是
20、L-屬性定義，如果AX1X2XnP,其每一個(gè)語義規(guī)則中的每一個(gè)屬性都是一個(gè)綜合屬性，或是Xj(1j n)的一個(gè)繼承屬性，這個(gè)繼承屬性僅依賴于 1.產(chǎn)生式中Xj的左邊符號(hào)X1，X2，Xj-1的屬性； 2A的繼承屬性。 每一個(gè)S-屬性定義都是L-屬性定義。,5.4.1 L-屬性定義,圖519 非L-屬性的語法制導(dǎo)定義,產(chǎn)生式,語義規(guī)則,ALM A QR,L.i:=l(A.i) M.i:=m(L.s) A.s:=f(M.s) R.i:=r(A.i) Q.i:=q(R.s) A.s:=f(Q.s),圖519的語法制導(dǎo)定義不是L-屬性定義 文法符號(hào)Q的繼承屬性依賴于它右邊文法符號(hào)R的屬性,,定義
21、翻譯模式是語法制導(dǎo)定義的一種便于翻譯的書寫形式。其中屬性與文法符號(hào)相對(duì)應(yīng)，語義規(guī)則或語義動(dòng)作用花括號(hào) 括起來，可被插入到產(chǎn)生式右部的任何合適的位置上。 這是一種語法分析和語義動(dòng)作交錯(cuò)的表示法，它表達(dá)在按深度優(yōu)先遍歷分析樹的過程中何時(shí)執(zhí)行語義動(dòng)作。 翻譯模式給出了使用語義規(guī)則進(jìn)行計(jì)算的順序?？煽闯墒欠治鲞^程中翻譯的注釋。,5.4.2 翻譯模式,將帶有+號(hào)和-號(hào)的中綴表達(dá)式翻譯成后綴表達(dá)式： ETR Raddop T print(addop.lexeme)R1| Tnumprint(num.val) 把語義動(dòng)作看成終結(jié)符號(hào)，輸入9-5+2,其分析樹如圖520，當(dāng)按深度優(yōu)先遍歷它，
22、執(zhí)行遍歷中訪問的語義動(dòng)作，將輸出 9 5 - 2 + 它是輸入表達(dá)式9-5+2的后綴式。,例5.12 一個(gè)簡(jiǎn)單的翻譯模式,圖5.10 9-5+2的帶語義動(dòng)作的分析樹,,條件：語法制導(dǎo)定義是L-屬性定義 保證語義動(dòng)作不會(huì)引用還沒有計(jì)算的屬性值。 1. 只需要綜合屬性的情況： 為每一個(gè)語義規(guī)則建立一個(gè)包含賦值的動(dòng)作，并把這個(gè)動(dòng)作放在相應(yīng)的產(chǎn)生式右邊的末尾。 例如：TT1*F Tval:=T1 val*F val TT1*F Tval:=T1 val*F val,設(shè)計(jì)翻譯模式（根據(jù)語法制導(dǎo)定義）,2. 既有綜合屬性又有繼承屬性 產(chǎn)生式右邊的符號(hào)的繼承屬性必須在這個(gè)符號(hào)以前的動(dòng)
23、作中計(jì)算出來。 一個(gè)動(dòng)作不能引用這個(gè)動(dòng)作右邊符號(hào)的綜合屬性。 產(chǎn)生式左邊非終結(jié)符號(hào)的綜合屬性只有在它所引用的所有屬性都計(jì)算出來以后才能計(jì)算。計(jì)算這種屬性的動(dòng)作通?？煞旁诋a(chǎn)生式右端的末尾。,設(shè)計(jì)翻譯模式（根據(jù)語法制導(dǎo)定義）,下面的翻譯模式不滿足要求： SA1A2 A1in:=1; A2 in:=2 A a print(A in) 例5.13 從L-屬性制導(dǎo)定義建立一個(gè)滿足上面 要求的翻譯模式。 使用文法產(chǎn)生的語言是數(shù)學(xué)排版語言EQN E sub 1val 編排結(jié)果,E,1,val,B.ps:=10 S.ht:=B.ht B1.ps:=B.ps B2.ps:=B.ps
24、B.ht:=max(B1.ht,B2.ht) B1.ps:=B.ps B2.ps:=shrink(B.ps) B.ht:=disp(B1.ht,B2.ht) B.ht:=text.h*B.ps,SB B B1 B2 B B1 sub B2 B text,產(chǎn)生式,語義規(guī)則,圖5-22 盒子的大小和高度的語法制導(dǎo)定義,,,,B是盒子； BBB表示兩個(gè)盒子的并置； BB sub B表示第二個(gè)盒子是第一個(gè)盒子的下標(biāo)； ps是繼承屬性，影響公式的高度；正文的實(shí)際高度 等于正文的標(biāo)準(zhǔn)高度乘以B.ps； B的高度由綜合屬性ht表示 ； texth可根據(jù)text的性質(zhì)查表得到； shrink把B2的尺
25、寸縮小30%； disp把B2向下偏置。,SB.ps:=10 BS.ht:=B.ht B B1.ps:=B.ps B1 B2.ps:=B.ps B2B.ht:=max(B1.ht,B2.ht) B B1.ps:=B.ps B1 sub B2.ps:=shrink(B.ps) B2B.ht:=disp(B1.ht,B2.ht) BtextB.ht:=text.h*B.ps,從圖5-22構(gòu)造的翻譯模式,用翻譯模式構(gòu)造自頂向下翻譯。 5.5.1 從翻譯模式中消除左遞歸 對(duì)于一個(gè)翻譯模式，若采用自頂向下分析，必須消除左遞歸和提取左公因子，在改寫基本
26、文法時(shí)考慮屬性值的計(jì)算。 例5.14 圖524的帶左遞歸的文法的翻譯模式被轉(zhuǎn)換成圖525的帶右遞歸的文法的翻譯模式。,5.5 自頂向下的翻譯,EE1+T E val:=E1val+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,帶左遞歸的文法的翻譯模式,ET Ri:=T val RE val:=R s R TR1i:=R.i+T. val R1R. s:=R1 s R- TR1 i:=R i-Tval
27、 R1R s:=R1 s RR s:=R i T（ E ） T val:=E.val Tnum T val:=num val,經(jīng)過轉(zhuǎn)換的帶有右遞歸文法的翻譯模式,E val=6,Tval=9,R i=9; R s= 6,,,9,,,,T val=5,,5,,R i=4; R s= 6,+,T val=2,R i=6; R s= 6,,,,2,,,,,,,,,,,,,,,,,圖526 表達(dá)式9-5+2的計(jì)算,左遞歸翻譯模式 AA1YA.a:=g(A1.a,Y.y) AX A.a:=f(X.x) （5.2） 每一個(gè)文法符號(hào)都有一個(gè)綜合屬性，用相應(yīng)的小寫字母表示，g和
28、f是任意函數(shù)。 消除左遞歸，文法轉(zhuǎn)換成 AX R RY R| （5.3）,關(guān)于左遞歸翻譯模式更一般化的討論,再考慮語義動(dòng)作，翻譯模式變?yōu)椋? AX Ri:=f(X x) R A. a:=R. s RY R1 i:=g（R i,Y y） R1 R s:=R1 s RR s:=R i （5.4） 經(jīng)過轉(zhuǎn)換的翻譯模式與圖525中一樣,使用R的繼承屬性i和綜合屬性s。 （5.2）和（5.4）的結(jié)果是一樣的, 為什么？,關(guān)于左遞歸翻譯模式更一般化的討論,A a=g(g(f(X x),Y1 y),Y2 y),A a=g(f(X x),Y1 y)
29、,A a=f(X x),Y2,Y1,X,,,,,,,,,,,(a),,輸入：XY1Y2,A,Ri=f(X x),R i=g(f(X x),Y1 y),R i=g(g(f(X x),Y1 y),Y2 y),,Y2,Y1,X,,,,,,,,,,,,,,,,(b),EE1+T Enptr :=mknode(+,E1 nptr,T nptr) EE1-T Enptr :=mknode(-,E1 nptr,T nptr) ET Enptr :=T nptr 從翻譯模式中消除左遞歸，變成圖528的翻譯模式。,例5.15 表達(dá)式建立語法樹的翻譯模式,ET Ri:=T nptr R E n
30、ptr:=R s R T R1 i:=mknode(+,R i,T nptr) R1 R s:=R1 s R- T R1 i:=mknode(-,R i,T nptr) R1 R s:=R1 s R R s:=R i T( E ) T nptr:=E nptr Tid T nptr:=mkleaf(id, id entry) Tnum T nptr:=mkleaf(num,num val),使用繼承屬性構(gòu)造語法樹,E,i,R,s,T,id,R,-,T,num,i,R,T,,,,,,,,,+,id,,,,,,id,,num 4,,id,,-,,,+,,,to
31、entry for a,to entry for c,,,,,,,nptr,nptr,nptr,,,,,,,算法5.1 預(yù)測(cè)語法制導(dǎo)翻譯器的建立 輸入：一個(gè)帶有適合預(yù)測(cè)分析的基礎(chǔ)文法 的語法制導(dǎo)翻譯模式。 輸出：一個(gè)語法制導(dǎo)翻譯器的代碼。 方法：在預(yù)測(cè)分析器中加入語義動(dòng)作代碼。 1AVN,建立一個(gè)可遞歸調(diào)用的函數(shù)過程A。為A的每一個(gè)繼承屬性都設(shè)置一個(gè)形式參數(shù)，函數(shù)的返回值是A的綜合屬性值。 2.函數(shù)過程A的代碼（指用符號(hào)形式表示的數(shù)據(jù)和程序）要根據(jù)當(dāng)前的輸入符號(hào)來決定使用哪一個(gè)產(chǎn)生式。,5.5.2 預(yù)測(cè)翻譯器的設(shè)計(jì),,,3與每一個(gè)產(chǎn)生式有關(guān)的代碼，從左到右根椐產(chǎn)生式右部是單詞符號(hào)、非終結(jié)
32、符號(hào)還是語義動(dòng)作，分別是： （a）對(duì)于帶有綜合屬性x的單詞符號(hào)X，x存放在X.x中，Match(X)。 （b）對(duì)于BVN，編寫一個(gè)賦值語句c：= B（b1, b2, ，bk)其中， b1, b2, ，bk是繼承屬性，c是綜合屬性。 （c）對(duì)于每個(gè)動(dòng)作，動(dòng)作的代碼抄進(jìn)翻譯器中，用代表屬性的變量來代替對(duì)屬性的每一次引用。,5.5.2 預(yù)測(cè)翻譯器的設(shè)計(jì),例5.16 ： Raddop TR1i:=mknode（addop lexeme， R i， T nptr） R1R.s:=R1.s R R.s:=R.i （55） 遞歸下降構(gòu)造語法樹 function
33、R（in: syntax-tree-node）： syntaX-tree-node； var nptr,i1,s1,s： syntax-tree-node; addoplexeme:char；, IF lookahead=addop THEN /*產(chǎn)生式Raddop T R*/ addoplexeme:=lexval; match(addop); nptr:=T; i1:=mknode(addoplexeme,in,nptr); s1:=R(i1); s:=s1 ; ELSE s:=
34、in; /*產(chǎn)生式R*/ return (s); ,5.6 L屬性的自底向上計(jì)算,在自底向上分析的框架中實(shí)現(xiàn)L屬性定義的方法 它能實(shí)現(xiàn)任何基于LL(1)文法的L屬性定義 也能實(shí)現(xiàn)許多（但不是所有的）基于LR(1) 的L屬性定義,5.6 L屬性的自底向上計(jì)算,5.6.1 刪除翻譯方案中嵌入的動(dòng)作 E T R R + T print (+)R1 | T print ()R1 | T num print (num.val),5.6 L屬性的自底向上計(jì)算,5.6.1 刪除翻譯方案中嵌入的動(dòng)作 E T R R + T print (+)R1 | T print ()R1 | T num pr
35、int (num.val) 在文法中加入產(chǎn)生的標(biāo)記非終結(jié)符，讓每個(gè)嵌入動(dòng)作由不同標(biāo)記非終結(jié)符M代表，并把該動(dòng)作放在產(chǎn)生式M 的右端,5.6 L屬性的自底向上計(jì)算,5.6.1 刪除翻譯方案中嵌入的動(dòng)作 E T R R + T print (+)R1 | T print ()R1 | T num print (num.val) 在文法中加入產(chǎn)生的標(biāo)記非終結(jié)符，讓每個(gè)嵌入動(dòng)作由不同標(biāo)記非終結(jié)符M代表，并把該動(dòng)作放在產(chǎn)生式M 的右端 E T R R + T M R1 | T N R1 | T num print (num.val) M print (+) N print (),5.6 L屬性的自
36、底向上計(jì)算,5.6.2 分析棧上的繼承屬性 屬性位置能預(yù)測(cè) 例 int p, q, r D T L.in = T.type L T 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 ),5.6 L屬性的自底向上計(jì)算,,5.6 L屬性的自底向上計(jì)算,屬性的位置不能預(yù)測(cè) S aACC.i = A.s S bABCC.i = A.s C cC.s = g(C.i),5.6 L屬性的自底向上計(jì)算,屬性的
37、位置不能預(yù)測(cè) S aACC.i = A.s S bABCC.i = A.s C cC.s = g(C.i) 增加標(biāo)記非終結(jié)符 S aACC.i = A.s S bABMCM.i = A.s; C.i = M.s C cC.s = g(C.i) M M.s = M.i,5.6 L屬性的自底向上計(jì)算,5.6.3 模擬繼承屬性的計(jì)算 繼承屬性是某個(gè)綜合屬性的一個(gè)函數(shù) S aACC.i = f (A.s) C cC.s = g(C.i) 增加標(biāo)記非終結(jié)符，把f(A.s)的計(jì)算移到對(duì)標(biāo)記非終結(jié)符歸約時(shí)進(jìn)行 S aANCN.i = A.s; C.i = N.s N N.s = f (N.i) C cC.s
38、 = g(C.i),5.6 L屬性的自底向上計(jì)算,例 數(shù)學(xué)排版語言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 B1 sub B2.ps = shrink(B.ps) B2B.ht = disp (B1.ht, B2.ht ) B textB.ht = text.h B.ps ,5.6 L屬性的自底向上計(jì)算,5.6 L屬性的自底向上計(jì)算,5.6 L屬性的自底向上計(jì)算,5.6 L屬性的自底向上計(jì)算,5.6 L屬性的自底向上計(jì)算,5.
39、6 L屬性的自底向上計(jì)算,5.6 L屬性的自底向上計(jì)算,5.6 L屬性的自底向上計(jì)算,5.6 L屬性的自底向上計(jì)算,5.6 L屬性的自底向上計(jì)算,5.7 遞歸計(jì)算,回顧：語法制導(dǎo)定義的實(shí)現(xiàn) 分析樹方法 邊分析邊進(jìn)行屬性計(jì)算，只能完成L屬性計(jì)算（忽略規(guī)則的方法） 本節(jié)介紹先分析后計(jì)算的方法，不局限于L屬性計(jì)算（基于規(guī)則的方法） 為每個(gè)非終結(jié)符構(gòu)造一個(gè)屬性計(jì)算函數(shù)，但是該函數(shù)不含語法分析部分 為非終結(jié)符的不同綜合屬性構(gòu)造不同的函數(shù),5.7 遞歸計(jì)算,5.7.1 自左向右遍歷 為B構(gòu)造一個(gè)屬性計(jì)算函數(shù) S B.ps = 10 BS.ht = B.ht B B1.ps = B.ps B1B2.ps
40、 = B.ps B2B.ht = max(B1.ht, B2.ht ) B B1.ps =B.ps B1 sub B2.ps = shrink(B.ps) B2B.ht = disp (B1.ht, B2.ht ) B textB.ht = text.h B.ps ,5.7 遞歸計(jì)算,function B(n, ps); var ps1, ps2, ht1, ht2; begin case 在結(jié)點(diǎn)n的產(chǎn)生式 of B B1 B2: ps1 = ps; ht1 = B(child(n,1), ps1); ps2 = ps; ht2 = B(child(n,2), ps2); return
41、max(ht1, ht2);,B B1.ps = B.ps B1B2.ps = B.ps B2B.ht = max(B1.ht, B2.ht ) ,5.7 遞歸計(jì)算,function B(n, ps); var ps1, ps2, ht1, ht2; begin case 在結(jié)點(diǎn)n的產(chǎn)生式 of B B1 sub B2: ps1 = ps; ht1 = B(child(n,1), ps1); ps2 = shrink(ps); ht2 = B(child(n,3), ps2); return disp(ht1, ht2);,B B1.ps = B.ps B1sub B2.ps = sh
42、rink(B.ps) B2B.ht = disp (B1.ht, B2.ht ) ,5.7 遞歸計(jì)算,function B(n, ps); var ps1, ps2, ht1, ht2; begin case 在結(jié)點(diǎn)n的產(chǎn)生式 of B text: return ps text.h; default: error end,B textB.ht = text.h B.ps ,5.7 遞歸計(jì)算,5.7.2 其它遍歷方法 按所需次序訪問結(jié)點(diǎn)的子結(jié)點(diǎn)，可用于非L屬性定義 A LM L.i = l(A.i); M.i = m(L.s); A.s = f (M.s) A QR R.i = r(A.i
43、); Q.i = q(R.s); A.s = f (Q.s),5.7 遞歸計(jì)算,A LM:/* 從左到右的次序 */ li = l(ai); ls = L(child(n,1), li); mi = m(ls); ms = M(child(n,2), mi); return f (ms);,5.7 遞歸計(jì)算,A QR:/* 從右到左的次序 */ ri = r(ai); rs = R(child(n,2), ri); qi = q(rs); qs = Q(child(n,1), qi); return f (qs);,5.7 遞歸計(jì)算,5.7.3 多次遍歷 S E E.i = g(E.s);
44、S.r = E.t E E1E2 E.s = fs(E1.s, E2.s); E1.i = fi1(E.i); E2.i = fi2(E.i); E.t = ft (E1.t, E2.t) E id E.s = id.s; E.t = h(E.i),5.7 遞歸計(jì)算,綜合屬性t不可能和s在同一遍掃描中完成計(jì)算,5.7 遞歸計(jì)算,function Sr(n); begin s = Es(child(n,1)); i = g(s); t = Et(child(n,1), i); return t end;,5.7 遞歸計(jì)算,function Es(n); | function Et(n,
45、i); begin | begin case 在結(jié)點(diǎn)n的產(chǎn)生式 of | case 在結(jié)點(diǎn)n的產(chǎn)生式 of E E1 E2: |E E1 E2: s1 = Es(child(n,1));| i1= fi1(i); s2 = Es(child(n,2));| t1 = Et(child(n,1), i1); return fs(s1, s2); | i2 = fi2(i); E id: | t2 = Et(child(n,2), i2); return id.s; | return ft(t1, t2); default: |E id: error | return h(i); end |default: end; | error |end | end;,本章要點(diǎn),語義規(guī)則的兩種描述方法：語法制導(dǎo)的定義和翻譯方案 設(shè)計(jì)簡(jiǎn)單問題的語法制導(dǎo)定義和翻譯方案，這是本章的重點(diǎn)和難點(diǎn) 語義規(guī)則的三種計(jì)算方法：分析樹方法、基于規(guī)則的方法和忽略規(guī)則的方法 S屬性的自底向上計(jì)算（邊分析邊計(jì)算） L屬性的自上而下計(jì)算（邊分析邊計(jì)算） L屬性的自底向上計(jì)算（邊分析邊計(jì)算） 遞歸計(jì)算（先分析后計(jì)算）,
《編譯原理》第5章語法制導(dǎo)翻譯
