【正文】 ? 用 A→α進(jìn)行歸約表達(dá)的是什么意思？ ? 看： operand+term ? E→E1+T ? E1的值 +T的值的結(jié)果作為 E的值 —— 即：取來E1的值和 T的值做加法運(yùn)算，結(jié)果作為 E的值 ? =+ 問題 2020/11/29 4 語法制導(dǎo)翻譯概述 ? 為了提高編譯程序的可移植性，一般將編譯程序劃分為前端和后端。 ? 沒有副作用的語法制導(dǎo)定義有時(shí)又稱為 屬性文法 ，屬性文法的語義規(guī)則單純根據(jù)常數(shù)和其它屬性的值來定義某個(gè)屬性的值 2020/11/29 17 繼承屬性 ? 當(dāng)分析樹的結(jié)構(gòu)同源代碼的抽象語法不“匹配”時(shí)，繼承屬性將非常有用。→ε T 39。.syn := T139。 2020/11/29 27 計(jì)算語義規(guī)則的其他方法 ? 基于規(guī)則的方法 ? 在構(gòu)造編譯器時(shí)，用手工或?qū)ｉT的工具來分析語義規(guī)則 ,確定屬性值的計(jì)算順序。 T139。 2020/11/29 33 抽象語法樹 是表示程序?qū)哟谓Y(jié)構(gòu)的樹，它把分析樹中對(duì)語義無關(guān)緊要的成分去掉，是分析樹的抽象形式 ，也稱作語法結(jié)構(gòu)樹，或結(jié)構(gòu)樹。, p3, p4)； 圖 ，對(duì)于那些為便于進(jìn)行自頂向下分析而設(shè)計(jì)的文法來說，使用同樣的步驟照樣可以建立圖 。.inh := mknode(39。 翻譯模式 2020/11/29 42 將中綴表達(dá)式翻譯成后綴表達(dá)式： E→TR R→addop T {print()}R1|ε T→num{print()} 把語義動(dòng)作看成終結(jié)符號(hào)，輸入 3+45,其分析樹如圖 ，當(dāng)按深度優(yōu)先遍歷它，執(zhí)行遍歷中訪問的語義動(dòng)作，將輸出 3 4 + 5 它是輸入表達(dá)式 3+45的后綴式。 ⑵ B→B1 sub B2代表盒子 B1后隨下標(biāo)盒子 B2，下標(biāo)盒子 B2以較小的字體和較低的位置出現(xiàn)。} B→({:=}B1){:=。.inh := mknode(39。} E→E1+T{stack[top2].val:= stack[top2].val + stack[top].val。 轉(zhuǎn)換前后的結(jié)果是一樣的 , 為什么？ S屬性定義的左遞歸消除 A→A1Y {:=g(,)} A→X {:=f()} 引入繼承屬性 來收集應(yīng)用函數(shù) g的計(jì)算結(jié)果。 2020/11/29 68 function T 39。 node := F。 ? 遞歸子程序法將語義動(dòng)作溶入分析程序； LL(1)分析法則由語義子程序完成相應(yīng)的翻譯。 {e5} {e4} F T 39。.inh被彈出棧， T 39。于是，當(dāng)將 ε歸約為 M時(shí)， 。 := max(, ) M ? ? := B ? B1 sub NB2 :=。 ? 依據(jù)語法分析方法有自底向上的和自頂向下的，語法制導(dǎo)翻譯既可以按照自底向上的策略進(jìn)行，也可以按照自頂向下的策略進(jìn)行。 := 。不過，由于要在 LR分析棧中實(shí)現(xiàn)所有的語義動(dòng)作，所以在分析棧中 M下面的某個(gè)已知位置總能找到所需的屬性。.inh均被彈出棧，新的 T 39。 2020/11/29 76 語義棧 語法棧 3*x/y 輸入串 例 對(duì)輸入串 3*x/y的翻譯 語法分析動(dòng)作和語義操作 {e1}， ， T 39。 node := mkleaf(num, ) end return node end。 syn := syn1 end else if lookahead = ‘/’ then begin /* 匹配產(chǎn)生式 T 39。 begin node := F。 L屬性定義的自頂向下翻譯 2020/11/29 60 ? 例 考慮如下將中綴表達(dá)式翻譯為后綴表達(dá)式的翻譯模式中的兩個(gè)產(chǎn)生式： E → E1+T {print(‘+’)。 A?XYZ A?a:=f(X?x,Y?y,Z?z) A?a X?x Y?y Z?z 2020/11/29 54 top stack val ... ... X Y Z stack val ... ... A top 實(shí)現(xiàn)時(shí)，將定義式 :=f(, , ) (抽象 )變成 stack[ntop].val:=f(stack[top2].val, stack[top1].val, stack[top].val) (具體可執(zhí)行代碼 )。{T 39。用屬性 B的深度 depth，該屬性也是綜合屬性。計(jì)算這種屬性的動(dòng)作通?？煞旁诋a(chǎn)生式右端的末尾。其中屬性與文法符號(hào)相關(guān)聯(lián)，語義規(guī)則或語義動(dòng)作用花括號(hào)｛ ｝括起來，并可被插入到產(chǎn)生式右部的任何合適的位置上。.syn:= T139。, , ) ⑶ T → F := ⑷ F → (E) := ⑸ F → id := mkleaf(id, ) ⑹ F → num := mkleaf(num, ) 2020/11/29 37 圖 3*x/y的 語法樹的構(gòu)造 /* i dn u m 3i d到 y 的 表 項(xiàng)到 x 的 表 項(xiàng)T . n o d e*T . n o d e/F . n o d ei di dF . n o d eF . n o d eT . n o d en u m2020/11/29 38 3*x/y的 抽象語法樹的構(gòu)造步驟 p1:=mkleaf(num,3)； p2:=mkleaf(id, entryx)； p3:=mknode(39。 2020/11/29 32 L屬性定義中的屬性計(jì)算 visit(N) { for N的每個(gè)子節(jié)點(diǎn) M(從左到右 ) { 計(jì)算節(jié)點(diǎn) M的繼承屬性 。 T 39。 ⑽ s y n 2020/11/29 25 屬性的計(jì)算順序 ? 拓?fù)渑判? ? 一個(gè)無環(huán)有向圖的拓?fù)渑判蚴菆D中結(jié)點(diǎn)的任何順序 m1， m2， … ， mk，使得邊必須是從序列中前面的結(jié)點(diǎn)指向后面的結(jié)點(diǎn)，也就是說，如果 mi→mj是 mi到 mj的一條邊 ,那么在 序列中 mi必須出現(xiàn)在 mj的前面。→*F{T139。.inh := T 39。 2020/11/29 9 語法制導(dǎo)翻譯概述 ? 屬性值的計(jì)算和產(chǎn)生式相關(guān)聯(lián)，隨著語法分析的進(jìn)行，執(zhí)行屬性值的計(jì)算，完成語義分析和翻譯的任務(wù)。第六章 語法制導(dǎo)翻譯與屬性文法 School of Computer Science amp。 ? E→E1 + E2 :=+ ? 語法結(jié)構(gòu)具有規(guī)定的語義 ? 問題：如何根據(jù)被識(shí)別出的語法成分進(jìn)行語義處理？ ? 亦即怎樣 將屬性值的計(jì)算及翻譯工作同產(chǎn)生式相關(guān)聯(lián)？ 2020/11/29 10 典型處理方法一 ? 語法制導(dǎo)定義 ? 通過將屬性與文法符號(hào)關(guān)聯(lián)、將語義規(guī)則與產(chǎn)生式關(guān)聯(lián)來描述語言結(jié)構(gòu)的翻譯方案 ? 對(duì)應(yīng)每一個(gè)產(chǎn)生式編寫一個(gè)語義子程序，當(dāng)一個(gè)產(chǎn)生式獲得匹配時(shí)，就調(diào)用相應(yīng)的語義子程序來實(shí)現(xiàn)語義檢查與翻譯 ? E→E1 + T {:=+} ? T→T1 * F {:=*} ? F →digit {:=} ? 適宜在完成歸約的時(shí)候進(jìn)行 2020/11/29 11 典型處理方法二 ? 翻譯模式 ? 通過將屬性與文法符號(hào)關(guān)聯(lián)，并將語義規(guī)則插入到產(chǎn)生式的右部來描述語言結(jié)構(gòu)的翻譯方案 ? 在產(chǎn)生式的右部的適當(dāng)位置，插入相應(yīng)的語義動(dòng)作，按照分析的進(jìn)程，執(zhí)行遇到的語義動(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 語法制導(dǎo)定義 ? 語法制導(dǎo)定義是附帶有屬性和語義規(guī)則的上下文無關(guān)文法 ? 屬性是與文法符號(hào)相關(guān)聯(lián)的語義信息 ? 語義規(guī)則是與產(chǎn)生式相關(guān)聯(lián)的語義動(dòng)作 ? 語法制導(dǎo)定義是基于語言結(jié)構(gòu)的語義要求設(shè)計(jì)的，類似于程序設(shè)計(jì)，語法制導(dǎo)定義中的屬性類似于程序中用到的數(shù)據(jù)結(jié)構(gòu)，用于描述語義信息，語義規(guī)則類似于計(jì)算，用于收集、傳遞和計(jì)算語義信息的。.inh T 39。.inh := T 39。 ? 若依賴圖中無環(huán)，則存在一個(gè)拓?fù)渑判?，它就是屬性值的?jì)算順序。.inh := := T 39。 visit (M)。*39。.syn ⑶ T 39。 這是一種語法分析和語義動(dòng)作交錯(cuò)的表示法，它表達(dá)在按深度優(yōu)先遍歷分析樹的過程中何時(shí)執(zhí)行語義動(dòng)作。 翻譯模式的設(shè)計(jì) —— 根據(jù)語法制導(dǎo)定義 2020/11/29 46 下面的翻譯模式不滿足要求： S?A1A2 {A1?in:=1。 2020/11/29 49 表 對(duì)盒子進(jìn)行排版的語法制導(dǎo)定義 產(chǎn)生式 語義規(guī)則 ⑴ S →B :=10 := := ⑵ B → B1B2 := := := max(, ) := max(, ) ⑶ B→B1 sub B2 := := :=max(, ) :=max(, + ) ⑷ B →(B1) := := := ⑸ B →text :=getheight(,) :=getdepth(,) 2020/11/29 50 S→{:=10}B { := 。.syn := T139。 在執(zhí)行代碼段之前執(zhí)行： ntop:=topr+1 —— r是句柄的長(zhǎng)度 執(zhí)行代碼段后執(zhí)行： top:=ntop。} E → T ? E → TR R → +T {print(‘+’)。 syn := T 39。 → /FT 39。 2020/11/29 70 LL(1)翻譯法 ? 預(yù)先在源文法中的相應(yīng)位置上嵌入語義動(dòng)作符號(hào) (每個(gè)對(duì)應(yīng)一個(gè)語義子程序 )，用于提示語法分析程序，當(dāng)分析到達(dá)這些位置時(shí)應(yīng)調(diào)用相應(yīng)的語義子程序。.inh被壓入棧 {e2} {e1} T 39。.inh被壓入棧 T 39。 ? 例如，假設(shè)在某個(gè)