編譯-講義課件2中間代碼表示法5

1、5.2 中間代碼表示法5.2.1 逆波蘭表示法 逆波蘭表示法是一種在不使用括號(hào)的情況下無(wú)二義的說(shuō)明算術(shù)表達(dá)式的一種方法。 這種表示法是把運(yùn)算量 (操作數(shù)) 寫在前面，把算符寫在后面(后綴)。 例，把a(bǔ)+b寫成ab+ 把a(bǔ)+(b*c)寫成abc*+ 擴(kuò)展: 一般而言，若是一個(gè)k ( 1 ) 目算符，它對(duì)運(yùn)算量 e1, e2, , ek 作用的結(jié)果將被表示成e1e2ek。 這種表示表達(dá)式的方法稱為后綴式。 ab+ 把雙目運(yùn)算符放在兩個(gè)運(yùn)算量的中間的中綴表示法。 a+b 把運(yùn)算符放在其運(yùn)算量前面的前綴表示法。 +ab共同的特點(diǎn)是:1. 操作符的個(gè)數(shù)不變 2. 操作數(shù)的次序和個(gè)數(shù)不變 逆波蘭表示法還具

2、有兩個(gè)明顯的優(yōu)點(diǎn): 1. 無(wú)括號(hào)，形式簡(jiǎn)潔清楚 2. 操作符的順序與運(yùn)算的次序完全相同 1. 一般表達(dá)式 (中綴式) 轉(zhuǎn)化成逆波蘭式(后綴式)(1) 從整體到局部的方法 設(shè)e是給定表達(dá)式，是相應(yīng)的逆波蘭式 則 = = = a 其中: 運(yùn)算量 a 變量 (暫只考慮簡(jiǎn)單變量，常數(shù)) 例， = = *= *= a*cd*= ab*+*cd*= 例， = = *= ab*cd*= a+*cd*= abcd*+*cd*(2) 自左向右掃描的方法 將表達(dá)式中的所有變量按原順序排列。 設(shè)有子表達(dá)式e1e2，則稱e2的后繼符為(運(yùn)算符) 的分界符，把每個(gè)運(yùn)算符移到相應(yīng)的分界符處，并去掉括號(hào)；若一個(gè)符號(hào)是多個(gè)運(yùn)

3、算符的分界符，則按“后者先移”的原則進(jìn)行。 例: a * (b+c) 逆波蘭式 abc+* 例: a * (b * c d ) e 逆波蘭式 abc*d-*e- 從左向右掃描，先遇到+雙目運(yùn)算，完成a+b運(yùn)算，再遇到*雙目運(yùn)算，完成(a+b)*c運(yùn)算，從而得到分解 (a+b)*c 。 例，ab+c* =分解= (a+b)*c 從右向左掃描，先遇到*雙目運(yùn)算，它的左側(cè)應(yīng)有兩個(gè)運(yùn)算量，首先是c是一個(gè)簡(jiǎn)單變量，它是參加運(yùn)算的第二個(gè)運(yùn)算量。再向左遇到+雙目運(yùn)算，說(shuō)明參加* 運(yùn)算的第一個(gè)運(yùn)算量應(yīng)是+運(yùn)算的結(jié)果，然后再對(duì)+運(yùn)算實(shí)施分解。 使用后綴式，可以根據(jù)運(yùn)算量和運(yùn)算符出現(xiàn)的先后位置，以及每個(gè)算符的目數(shù)

4、就完全決定了一個(gè)表達(dá)式的分解。 2. 后綴式的計(jì)值 表達(dá)式的后綴表示，可以使用一個(gè)棧 來(lái)計(jì)算它的值。 計(jì)算過(guò)程: 自左向右掃描后綴式，每逢遇到運(yùn)算量就令其入棧； 遇到K目運(yùn)算符，則將它作用于棧頂?shù)腒個(gè)項(xiàng)，并用運(yùn)算結(jié)果代替這K個(gè)項(xiàng)。 例，ab+c* 的計(jì)值過(guò)程如下:1. 遇a，a入棧。 2. 遇b， b入棧。 3. 遇+，將棧頂兩項(xiàng)相加，移走b、a，把和E1置于棧頂。 4. 遇c， c入棧。 5. 遇*，將棧頂兩項(xiàng)相乘，移走c、E1，把積E2置于棧頂。棧當(dāng)前輸入符后綴式空aab+c*abb+c*ab+c*E1 cc*E1c*E23. 后綴式的推廣 我們可以將后綴式簡(jiǎn)單的推廣到比表達(dá)式更大的范圍。

5、 例，如下的條件算術(shù)表達(dá)式:e ? x : y表示若e0，則此式值為x；否則，為y。 若把e ? x : y表示成一個(gè)三目運(yùn)算exy，這種方式出現(xiàn)的問(wèn)題是: 任何情況下，第二目x和第三目y均得計(jì)算一次，會(huì)造成時(shí)間的浪費(fèi)。 克服它的一種可行辦法是引進(jìn)標(biāo)號(hào), 條件轉(zhuǎn)移和無(wú)條件轉(zhuǎn)移算符。 令后綴式存放在一維數(shù)組 POST1:n 中，每個(gè)數(shù)組元素存放一個(gè)運(yùn)算量或運(yùn)算符或標(biāo)號(hào)。 所引進(jìn)的標(biāo)號(hào)是一個(gè)下標(biāo)，指向數(shù)組的某元素。 無(wú)條件轉(zhuǎn)移 j，如 p j 表示: 轉(zhuǎn)移到 POSTp (單目算符) 。 條件轉(zhuǎn)移 j(小于轉(zhuǎn)移算符)，如 e1 e2 p j表示: 若e1小于e2，則轉(zhuǎn)移到POSTp (三目算符)。

6、 jez(0轉(zhuǎn)移算符)，如 e p jez表示: 若e等于false，則轉(zhuǎn)移到 POSTp (雙目算符)。 jnz(非0轉(zhuǎn)移算符)，如 e p jnz表示: 若e不等于false，則轉(zhuǎn)移到 POSTp (雙目算符)。 用后綴式來(lái)表示各種語(yǔ)句。 (1) 賦值語(yǔ)句的逆波蘭式 賦值語(yǔ)句 x := e 逆波蘭式 := (2) 轉(zhuǎn)移語(yǔ)句的逆波蘭式 轉(zhuǎn)移語(yǔ)句 goto L，其中L是標(biāo)號(hào)。 逆波蘭式 L j，其中 j是單目算符，轉(zhuǎn)向標(biāo)號(hào)處。 (3) 條件語(yǔ)句的逆波蘭式 條件語(yǔ)句: if e then x else y 逆波蘭式: e p1 jez x p2 j p1: y p2: 其中，后跟冒號(hào)的標(biāo)號(hào)并不真

7、正出現(xiàn)在后綴式中，它們僅僅在書面上指明有關(guān)式子的開(kāi)始位置。 在POST中出現(xiàn)的后綴式將是: ep1jezxp2jyp1p2例: if ab then x:=a+b else y:=a-b 逆波蘭式表示為: abi+j then k:=k-1；goto 10 beginendelse k:=i*i - j*j； i:=0；j:=0；beginend逆波蘭表示為:(2) k 100 := (3) k i j + jez (0轉(zhuǎn)) (4) k k 1 - := (6) k i i * j j * - := (7) i 0 := (1) block (9) blockend (8) j 0 := (3

8、) k i j + 6 jez (0轉(zhuǎn)) (5) 3 j(4) 循環(huán)語(yǔ)句的逆波蘭表示 循環(huán)語(yǔ)句:for (i=a;ib;i+) s ，先將其變成等價(jià)的條件語(yǔ)句: i:=a；10: if i=b thenbegins；i:=i+1；goto 10 end然后按條件語(yǔ)句形式轉(zhuǎn)換。 例，循環(huán)語(yǔ)句 for (i=1;i=100;i+) s=s+i; 先展成等價(jià)的條件語(yǔ)句: i:=1；10: if i=100 then begins:=s+i；i:=i+1；goto 10 end然后轉(zhuǎn)換成逆波蘭式: (1) i 1 := (4) i 100 = 21 jez (9) s s i + := (14) i

9、i 1 + := (19) 4 j (21)4. 語(yǔ)法制導(dǎo)生成后綴式 原理性描述如下: 產(chǎn)生式 語(yǔ)義動(dòng)作 (1) EE（1）op E（2） E.CODE = E（1）.CODEE（2）.CODEop (2) E( E（1）) E.CODE = E（1）.CODE (3) E i E.CODE = i 其中: E.CODE后綴式符號(hào)串 “捻接”操作 i 標(biāo)識(shí)符 (如a 或b或c ) 第(1)產(chǎn)生式語(yǔ)義動(dòng)作的意思是，E 的后綴式等于E（1） 和 E（2） 兩后綴式的捻接，而后再接上算符op。 第(2)產(chǎn)生式的語(yǔ)義動(dòng)作指出，把括號(hào)無(wú)條件地去掉。 第(3)產(chǎn)生式的語(yǔ)義動(dòng)作說(shuō)明，標(biāo)識(shí)符的語(yǔ)義值是那個(gè)標(biāo)識(shí)

10、符自身。 符號(hào)串的捻接 (并置) 運(yùn)算，對(duì)于機(jī)器實(shí)現(xiàn)來(lái)說(shuō)，這種運(yùn)算的代價(jià)是極高的，如果安排一個(gè)數(shù)組存放后綴式，那么語(yǔ)義動(dòng)作可以不涉及捻接運(yùn)算。令數(shù)組為POST，K為下標(biāo)，初值為1，則上述語(yǔ)義動(dòng)作可改寫為: 產(chǎn)生式 程序段 (1) E E（1）op E（2） POSTk = op；k=k+1 (2) E ( E（1）) (3) E i POSTk = i；k=k+1 例，(a+b) * c 其規(guī)約過(guò)程如下: (a + b ) * c (E + b ) * c (E + E) * c (E) * c E * c E * E E其后綴式的形成過(guò)程如下:POST數(shù)組 E ( a + b ) * c a

11、 k=1 ( E+ b ) * c a b k=2 ( E+ E ) * c a b + k=3 ( E ) * c a b + k=3 E * c a b + c k=4 E * E a b + c * k=5 5.2.2 三元式表示法 表達(dá)式及各種語(yǔ)句也可以表示成一組三元式。每個(gè)三元式包括三個(gè)組成部分: OP, ARG1, ARG2 , 表示形式為三元組 (OP, ARG1, ARG2 ) 。其中: OP算符。 ARG1，ARG2運(yùn)算量指示器，指向有關(guān)符號(hào)表的某一位置 (通常用標(biāo)識(shí)符表示)，或指向三元式表自身的某一項(xiàng)。 例，表達(dá)式: A + B * C 三元式表示:(1) ( * , B

12、, C ) (2) ( + , A , (1) ) 對(duì)單目運(yùn)算符，只使用ARG1 Op可以是: +，*，j，jz jez 雙目，等于0轉(zhuǎn)移jnz 雙目，非0轉(zhuǎn)移j 三目，大于轉(zhuǎn)j 單目，無(wú)條件轉(zhuǎn)移 1、表達(dá)式和賦值語(yǔ)句的三元式 例，布爾表達(dá)式：ABxy+1 (x0B) D 其中: A , B, D為布爾量；x, y為算術(shù)量用三元式表示: (1) (, y, 1 )(5) (, x, 0 )(2) (, x, (1) )(3) (, B, (2) )(4) (, A, (3) )(6) (, (5), B )(7) (, (6), D )(8) (, (4), (7) )例， 賦值語(yǔ)句: x :

13、= a * b + c / d 用三元式表示: (1) ( * , a , b )(2) ( / , c , d )(3) ( + , (1), (2)(4) ( := , * , (3)2、 轉(zhuǎn)移語(yǔ)句和條件語(yǔ)句的三元式 例，條件語(yǔ)句 if xy then z := x else z := y+1 用三元式表示:(1) ( , x , y )(2) (jez, (1), ) (jez為單目運(yùn)算，等于0轉(zhuǎn))(3) ( :=, z , x )(4) ( j , , ) (j為無(wú)條件轉(zhuǎn)至(7)，單目運(yùn)算)(5) ( + , y , 1 )(6) ( :=, z , (5)(7) 真假(2) (jez

14、, (1), (5) (jez為單目運(yùn)算，等于0轉(zhuǎn))(4) ( j , (7), ) (j為無(wú)條件轉(zhuǎn)至(7)，單目運(yùn)算)例，程序段:begink := 100；10: if k i+j thenbegink := k 1；goto 10endelse k := i * i j * j；i := 0；j := 0；end用三元式表示: (1) ( block, , ) (2)( := , k , 100 )(3)( + , i , j )(4)( , k , (3) )(5)(jez , (4), ) (6)( - , K , 1 )(7)( := , K , (6) )(8)( j , (3)

15、 , )(9)( * , i , i )(10) ( * , j , j )(11) ( - , (9), (10) )(12) ( := , k , (11) )(13) ( := , i , 0 )(14) ( := , j , 0 )(15) (blockend, , )(5)(jez , (4), (9) )3、循環(huán)語(yǔ)句的三元式 例，循環(huán)語(yǔ)句: for i := 1 to 100 do s := s + i 首先將其展開(kāi)為: i:=1；10: if i=100 then begins:=s+i；i:=i+1；goto 10 end再轉(zhuǎn)化成三元式: (1) ( := , i , 1 )(

16、2) ( =, i , 100 )(3) ( jf , (2), )(4) ( + , s , i )(5) ( := , s , (4) )(6) ( + , i , 1 )(7) ( := , i , (6)(8) ( j , (2) , )(9) (3) ( jf , (2), (9) )4. 三元式的語(yǔ)法制導(dǎo)翻譯 產(chǎn)生式 語(yǔ)義動(dòng)作 (1) E E(1) op E(2) E.VAL = TRIP ( op , E(1).VAL , E(2).VAL ) (2) E (E(1) E.VAL = E(1).VAL (3) E - E(1) E.VAL = TRIP ( , E(1).VAL

17、, ) (4) E i E.VAL = ENTRY(i) E.VAL指示器，指向有關(guān)符號(hào)表的某一項(xiàng)或指向三元式表中的某一項(xiàng)。 TRIP ( op , ARG1 , ARG2 ) 語(yǔ)義過(guò)程，產(chǎn)生新三元式。此過(guò)程將回送新產(chǎn)生的三元式放在三元式表中的位置。 單目運(yùn)算“負(fù)”。ENTRY(i)語(yǔ)義過(guò)程，查找并取得與 i相對(duì)應(yīng)的標(biāo)識(shí)符在符號(hào)表中的位置 (入口)。 5.2.3 樹(shù)結(jié)構(gòu)表示法 在語(yǔ)法樹(shù)的基礎(chǔ)上進(jìn)行簡(jiǎn)化，形成抽象的樹(shù)型數(shù)據(jù)結(jié)構(gòu)，常用來(lái)表示中間代碼。這種樹(shù)中，非葉結(jié)點(diǎn)和葉結(jié)點(diǎn)(端末結(jié))分別代表運(yùn)算符和運(yùn)算量。 如右圖: e1、e2為表達(dá)式，T1表示為e1的樹(shù)，T2表示為e2的樹(shù)，則T1+T2表示

18、e1+e2的樹(shù)T1 T2+e1+e2T1*T2表示 e1*e2的樹(shù)T1 T2*e1*e2-T1表示 -e1的樹(shù)T1 -e1雙目運(yùn)算對(duì)應(yīng)二叉子樹(shù)，多目運(yùn)算對(duì)應(yīng)多叉子樹(shù)。多叉子樹(shù)可以通過(guò)引進(jìn)新結(jié)而表示成二叉子樹(shù)。 將一個(gè)表達(dá)式翻譯成樹(shù)結(jié)構(gòu)表示:產(chǎn)生式語(yǔ)義動(dòng)作 (1) E E(1) op E(2) E.VAL = NODE ( op , E(1).VAL , E(2).VAL ) (2) E (E(1) E.VAL = E(1).VAL (3) E - E(1) E.VAL = UNARY ( , E(1).VAL ) (4) E i E.VAL = LEAF(i) E.VAL指示器，指向樹(shù)的一個(gè)結(jié)。 NODE ( op , LEFT, RIGHT )函數(shù)過(guò)程，建立二叉樹(shù)，回送的值是一個(gè)指示器，指向這新樹(shù)根。 UNARY (OP, CHILD )與NODE類似，只有一個(gè)枝。 LEAF(i)建立以i.LEXVAL指示