【導(dǎo)讀】語法制導(dǎo)定義與翻譯模式。形式簡單、語義明確、獨立于目標(biāo)語言。便于編譯系統(tǒng)的實現(xiàn)、移植、代碼優(yōu)化。逆波蘭表示、三地址碼、DAG圖表示。中綴表達式的計算順序不是運算符出現(xiàn)的自。碼一般比較麻煩。波蘭邏輯學(xué)家J.Lukasiewicz于1929年提出了。來指示運算順序。例下面給出的是一些表達式的中綴、前綴。名字、常量、編譯器生成的臨時變量。1．形如x:=yopz的賦值指令；4．無條件跳轉(zhuǎn)指令gotoL；6．形如ifxrelopygotoL的條件跳轉(zhuǎn)指令；paramx用來指明參數(shù)；callp,n和y=callp,n用來表示過程調(diào)用和函數(shù)調(diào)用；returny表示過程返回；8．形如x:=y[i]和x[i]:=y的變址復(fù)制指令；組成，分別稱為op、arg1、arg2和result。量，運算結(jié)果則放入result中。三元式的三個域分別稱為op，arg1和。類似于表達式的抽象語法樹一樣，在dag(directedacyclic. 利用dag可以很容易地消除公共子表達式

　　

【正文】 效率較低 2020/11/17 93 回填 ? 一遍掃描 ? 問題：生成跳轉(zhuǎn)語句時可能不知道要轉(zhuǎn)向指令的標(biāo)號 ? 先產(chǎn)生暫時沒有填寫目標(biāo)標(biāo)號的轉(zhuǎn)移指令 ? 對于每一條這樣的指令作適當(dāng)?shù)挠涗洠ㄒ粋€鏈表 ? 一旦確定了目標(biāo)標(biāo)號 ,再將它“ 回填 ”到相應(yīng)的指令中 ? ? 2020/11/17 94 回填 翻譯模式用到如下三個函數(shù)： 1． makelist(i)： 創(chuàng)建一個只包含 i的新表， i 是四元式數(shù)組的一個索引 (下標(biāo) )，或者說 i是四元式代碼序列的一個標(biāo)號。 2． merge(p1, p2)： 合并由指針 p1和 p2指向 的兩個表并且返回一個指向合并后的表的 指針。 3． backpatch(p， i)： 把 i作為目標(biāo)標(biāo)號回填到 p所指向的表中的每一個轉(zhuǎn)移指令中去。 此處的“表”都是為“回填”所拉的鏈 2020/11/17 95 布爾表達式的回填式翻譯 B ? B1 or M B2 {backpatch(, )。 :=merge(, )。 := } M ? ε {:=nextquad} B1的代碼 B2的代碼 or 2020/11/17 96 布爾表達式的回填式翻譯 B ? B1 and M B2 {backpatch(, )。 := 。 :=merge(, )。} B1的代碼 B2的代碼 and 2020/11/17 97 布爾表達式的回填式翻譯 B ? not B1 { := 。 := 。} B ? (B1 ) { := 。 := 。} 2020/11/17 98 布爾表達式的回填式翻譯 B ? E1 relop E2 { :=makelist(nextquad)。 :=makelist(nextquad+1)。 gencode(‘if’ relop ‘goto’)。 gencode(‘goto’) } 2020/11/17 99 布爾表達式的回填式翻譯 B ? true { := makelist(nextquad)。 gencode(‘goto’)} B ? false { := makelist(nextquad)。 gencode(‘goto’)} 2020/11/17 100 例 = {100, 104} = {103,105} :={102} := {100} := {101} = {104} = {103,105} = {102} = {103} = {104} = {105} 圖 ab or cd and ef的注釋分析樹 a b or ε :={104} and ε c d e f 100: if ab goto – 101: goto 102: if cd goto 104 103: goto – 104: if ef goto – 105: goto 100: if ab goto – 101: goto 102: if cd goto – 103: goto 104: if ef goto – 105: goto 100: if ab goto – 101: goto 102 102: if cd goto 104 103: goto – 104: if ef goto – 105: goto 2020/11/17 101 常見控制結(jié)構(gòu)的回填式翻譯 S ? if B then M S1 | if B then M1 S1 N else M2 S2 | while M1 B do M2 S1 | S1。M S2 M ? ε { := nextquad} N ? ε {:=makelist(nextquad)。 gencode(‘goto )} 2020/11/17 102 ifthen語句的回填式翻譯 S ? if B then M S1 {backpatch(, ) :=merge(, )} B的代碼 S⑴ 的代碼 if S⑴ .nextlist then 2020/11/17 103 ifthenelse語句 的回填式翻譯 S ? if B then M1 S1 N else M2 S2 {backpatch(, )。 backpatch(, )。 := merge(,merge(,))} B的代碼 S⑴ 的代碼 if S⑴ .nextlist then S⑵ .nextlist S⑵ 的代碼 jmp else M 2020/11/17 104 while語句的 回填式翻譯 S ? while M1 B do M2 S1 {backpatch(,)。 backpatch(,)。 :=。 gencode(‘goto’)} B的代碼 S⑴ 的代碼 while S⑴ .nextlist do jmp 2020/11/17 105 語句序列的回填式翻譯 S ? S1。M S2 {backpatch(, )。 :=} S⑴ 的代碼 S⑴ .nextlist S⑵ .nextlist S⑵ 的代碼 2020/11/17 106 例 翻譯下列語句 while a b do B1 if c 5 then B2 S1 while x y do z := x + 1。 else S2 x := y S3 2020/11/17 107 例 while ab do if c5 then while xy do z:=x+1 else x:=y的注釋分析樹 :={101} while :={100} ε := {100} := {101} a b do :={102} ε :={105,109} if := {102} := {103} c 5 then :={104} ε :={105} :={109} ε else :={110} ε :=nil := x y while :={104} ε := {104} := {105} x y do :={106} ε := z =t1 + x 1 S .n:=nil 2020/11/17 108 生成的四元式序列 100: （ j,a,b,102） 101： （ j,,,112） 102： （ j,c,5,104） 103： （ j,,,110） 104： （ j,x,y,106） 105： （ j,,,100） 106： （ +,x,1,t1） 107： （ :=, t1,,z） 108： （ j,,,104） 109： （ j,,,100） 110： （ :=,y,,x） 111： （ j,,,100） 112: while ab do if c5 then while xy do z:=x+1 else x:=y 2020/11/17 109 for循環(huán)語句的回填式翻譯 E1. c o d eM . a g a i n :o v e r :f o rS . n e x t l i s tE2. c o d ei d : = E1. a d d rT1: = E2. a d d rJ M P o v e ri d : = i d + T2i f i d T1 g o t o 0 S1. c o d eJ M P M . a g a i nS1. n e x t l i s tM . q u a dd oM . n e x t l i s tE3. c o d eT2: = E3. a d d rfor循環(huán)語句的目標(biāo)結(jié)構(gòu) 2020/11/17 110 for循環(huán)語句的回填式翻譯 S → for id := E1 to E2 step E3 do M S1 {backpatch(, ,)。 gencode(‘goto’, , , )。 := 。} 2020/11/17 111 for循環(huán)語句的回填式翻譯 M→ε { := entry(id)。 gencode(‘:=’, , , )。 T1:=newtemp。 gencode(‘:=’, , , T1)。 T2:=newtemp。 gencode(‘:=’, , , T2)。 q:=nextquad。 gencode(‘goto’, , , q+2)。 :=q+1。 gencode(‘+’, , T2, )。 :=nextquad。 gencode(‘if’ ‘’T1‘goto –’)。} 2020/11/17 112 repeat語句的回填式翻譯 S→repeat M S1until N B {backpatch(,)。 :=} M→ε { := nextquad} N→ε {backpatch(, nextquad)} S1. c o d er e p e a tS . n e x t l i s tB . c o d eu n t i lM . q u a dS1. n e x t l i s tB . t r u e l i s tB . f a l s e l i s t2020/11/17 113 switch語句的翻譯 E . c o d es w i t c hS1. c o d eJ M P 0c a s e V1: E . a d d r ≠ V1 g o t o V2S2. c o d eJ M P 0c a s e V2: E . a d d r ≠ V2 g o t o V3? ? c a s e V3: E . a d d r ≠ V3 g o t o V4Sn. c o d ec a s e Vn 1: E . a d d r ≠ Vn 1 g o t o d e f a u l t? ? S . n e x t l i s tS1. n e x t l i s tS2. n e x t l i s tSn. n e x t l i s td e f a u l t :2020/11/17 114 switch語句的語法制導(dǎo)翻譯 S→switch (E){i:=0。 :=0。 push 。 push 。 push i。 q:=0。 push q} Clist{pop q。pop i。pop 。pop 。:=merge(, q)。 push } 2020/11/17 115 switch語句的語法制導(dǎo)翻譯 Clist→case V :{pop q。 pop i。 i:=i+1。 pop 。 if nextquad ≠0 then backpatch(q, nextquad)。 q:=nextquad。 gencode(‘if’ ‘≠’ Vi ‘goto’ Li)。 push 。 push i。 push q}S{pop q。 pop i。 pop 。 pop 。 p:=nextquad。 gencode(‘goto ’)。 gencode(Li‘:’)。 :=merge(, p)。 :=merge(, )。 push 。 push 。 push i。 push q}Clist 2020/11/17 116 switch語句的語法制導(dǎo)翻譯 Clist→default