【文章內(nèi)容簡介】 的 語法樹 T ⒀ n o d e F ⑵ n o d e n u m ⑴ v a l * i n h ⑶ T 39。 ⑿ s y n F ⑸ n o d e i d ⑺ e n t r y i d ⑷ e n t r yi n h ⑹ T 39。 ⑾ s y n /F ⑻ n o d e i n h ⑼ T 39。 ⑽ s y n ε2020/11/29 41 ? 定義 翻譯模式 是語法制導(dǎo)定義的一種便于實現(xiàn)的書寫形式。其中屬性與文法符號相關(guān)聯(lián)，語義規(guī)則或語義動作用花括號｛ ｝括起來，并可被插入到產(chǎn)生式右部的任何合適的位置上。 這是一種語法分析和語義動作交錯的表示法，它表達(dá)在按深度優(yōu)先遍歷分析樹的過程中何時執(zhí)行語義動作。 翻譯模式給出了使用語義規(guī)則進(jìn)行計算的順序?？煽闯墒欠治鲞^程中翻譯的注釋。 翻譯模式 2020/11/29 42 將中綴表達(dá)式翻譯成后綴表達(dá)式： E→TR R→addop T {print()}R1|ε T→num{print()} 把語義動作看成終結(jié)符號，輸入 3+45,其分析樹如圖 ，當(dāng)按深度優(yōu)先遍歷它，執(zhí)行遍歷中訪問的語義動作，將輸出 3 4 + 5 它是輸入表達(dá)式 3+45的后綴式。 例 一個簡單的翻譯模式 2020/11/29 43 圖 3+45的帶語義動作的分析樹 RTRRεET4{ p r i n t ( ‘ 4 39。 ) }{ p r i n t ( ‘ 3 39。 ) }T { p r i n t ( 39。 39。 ) }5{ p r i n t ( ‘ 5 39。 ) }{ p r i n t ( 39。 + 39。 ) }3+2020/11/29 44 ? 前提 —— 語法制導(dǎo)定義是 L屬性定義 保證語義動作不會引用還沒計算出來的屬性值 1. 只需要綜合屬性的情況 為每一個語義規(guī)則建立一個包含賦值的動作，并把該動作放在相應(yīng)的產(chǎn)生式右部的末尾。 例如： T?T1*F T?val:=T1?val*F?val 轉(zhuǎn)換成： T?T1*F{T?val:=T1?val*F?val} 翻譯模式的設(shè)計 —— 根據(jù)語法制導(dǎo)定義 2020/11/29 45 2. 既有綜合屬性又有繼承屬性 ? 產(chǎn)生式右邊的符號的繼承屬性必須在這個符號以前的動作中計算出來。 ? 一個動作不能引用這個動作右邊符號的綜合屬性。 ? 產(chǎn)生式左邊非終結(jié)符號的綜合屬性只有在它所引用的所有屬性都計算出來以后才能計算。計算這種屬性的動作通常可放在產(chǎn)生式右端的末尾。 翻譯模式的設(shè)計 —— 根據(jù)語法制導(dǎo)定義 2020/11/29 46 下面的翻譯模式不滿足要求： S?A1A2 {A1?in:=1。 A2?in:=2} A ?a { print(A?in) } /* */ 例 從 L屬性制導(dǎo)定義建立一個滿足上面 要求的 翻譯模式。 使用文法產(chǎn)生的語言是數(shù)學(xué)排版語言 EQN E sub 1?val 編排結(jié)果 E1. v a lh e i g h td e p t h2020/11/29 47 B表示盒子 ⑴ B→B1B2代表兩個相鄰盒子的并列，且 B1位于 B2的左邊。 ⑵ B→B1 sub B2代表盒子 B1后隨下標(biāo)盒子 B2，下標(biāo)盒子 B2以較小的字體和較低的位置出現(xiàn)。 ⑶ B→(B1)代表一個由括號括起來的盒子 B1，主要是為了對多個盒子或下標(biāo)進(jìn)行分組。在 EQN中，使用花括號進(jìn)行分組，此處使用圓括號是為了避免跟語義動作外面的花括號產(chǎn)生沖突。 ⑷ B→text代表文本字符串，即任意字符組成的串。 該文法是二義性的文法，將“并列”和“下標(biāo)”看成是左結(jié)合的，并令“下標(biāo)”的優(yōu)先級高于“并列”的話，則可以對該文法所描述的語言進(jìn)行自底向上的語法分析。 2020/11/29 48 屬性設(shè)置 ⑴ point size用于表示盒子中文本的尺寸 (以點來計算，也就是字號 )。如果標(biāo)準(zhǔn)盒子的尺寸為 p，則下標(biāo)盒子的尺寸為 p。屬性 B的尺寸，該屬性是繼承屬性。 ⑵ 每個盒子都有一個基線 (baseline)，用來表示每個文本底部的垂直位置。 ⑶ height用來表示從盒子的頂部到基線的距離。屬性 B的高度 height，該屬性是綜合屬性。 ⑷ depth用來表示從基線到盒子底部的距離。用屬性 B的深度 depth，該屬性也是綜合屬性。 2020/11/29 49 表 對盒子進(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 { := 。:= } B→{:=}B1{B2 .ps:=} B2{:=max(,)} B→{:=}B1sub{:= } B2{:=max(, )。 :=max(,+ )。} B→({:=}B1){:=。 :=。} B→text{:=getheight(,)。 :=getdepth(,)} 從表 2020/11/29 51 T → F {T 39。.inh := }T 39。{ := T 39。.syn} T 39。 → *F {T139。.inh := mknode(39。*39。, T 39。.inh,)} T139。{T 39。.syn := T139。.syn} T 39。 → /F {T139。.inh := mknode(39。/39。, T 39。.inh,)} T139。{T 39。.syn := T139。.syn} T 39。 →ε {T 39。.syn := T 39。.inh} F → (E ){ := } F→ id { := mkleaf(id, )} F→ num { := mkleaf(num, )} 從表 2020/11/29 52 在分析棧中使用一個附加的域來存放綜合屬性值。下圖為一個帶有綜合屬性值域的分析棧： stack val ... X Y ... ... ... Z top S屬性定義的自底向上計算 2020/11/29 53 ?A?? b:=f(c1,c2,…, ck) b是 A的綜合屬性， ci (1? i?k)是 ?中符號的屬性。綜合屬性的值是在自底向上的分析過程中，每次歸約之前進(jìn)行計算的。 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 實現(xiàn)時，將定義式 :=f(, , ) (抽象 )變成 stack[ntop].val:=f(stack[top2].val, stack[top1].val, stack[top].val) (具體可執(zhí)行代碼 )。 在執(zhí)行代碼段之前執(zhí)行： ntop:=topr+1 —— r是句柄的長度 執(zhí)行代碼段后執(zhí)行： top:=ntop。 2020/11/29 55 例 用 LR分析器實現(xiàn) 臺式計算器 —— 與表 L→En{print(stack[top1].val)。top:=top1。} E→E1+T{stack[top2].val:= stack[top2].val + stack[top].val。 top:=top2。} E→T T→T1*F{stack[top2].val:= stack[top2].val stack[top].val。 top:=top2。} T→F F→(E){ stack[top2].val:= stack[top1].val。top:=top2。} F→digit 2020/11/29 56 表 翻譯輸入 6+7*8n上的移動序列 輸入 state val 使用的產(chǎn)生式 6+7*8n +7*8n 6 6 +7*8n F 6 F?digit +7*8n T 6 T?F +7*8n E 6 E?T 7*8n E+ 6+ *8n E+7 6+7 2020/11/29 57 *8n E+F 6+7 F ?digit *8n E+T 6+7 T? F