編譯原理及實現(xiàn)技術(shù)課件：第七章 中間代碼生成

1、第七章 中間代碼生成 中間語言 語法制導(dǎo)方法 簡單表達(dá)式的中間代碼生成 原子語句的中間代碼生成 結(jié)構(gòu)語句的中間代碼生成 聲明的中間代碼7.1中間語言后綴式-逆波蘭式特別是表達(dá)式的內(nèi)部表示圖結(jié)構(gòu)中間代碼抽象語法樹有向不循環(huán)圖三地址中間代碼三元式四元式7.1.1后綴表達(dá)式相關(guān)中綴變后綴算法初始化一個空堆棧，將結(jié)果字符串變量置空。從左到右讀入中綴表達(dá)式，每次一個字符。如果字符是操作數(shù)，將它添加到結(jié)果字符串。如果字符是個操作符，彈出操作符，直至遇見開括號、優(yōu)先級較低的操作符或者同一優(yōu)先級的右結(jié)合符號。把這個操作符壓入棧。如果字符是個開括號，把它壓入堆棧。如果字符是個閉括號，在遇見開括號前，彈出所有操作

2、符，然后把它們添加到結(jié)果字符串。如果到達(dá)輸入字符串的末尾，彈出所有操作符并添加到結(jié)果字符串。后綴計算算法7.1.2抽象語法樹AGT和有向不循環(huán)圖DAG抽象語法樹表達(dá)式的AGT中間節(jié)點：運算符葉節(jié)點：操作數(shù)推廣到程序有向不循環(huán)圖共享子樹7.1.3三地址中間代碼 三元式：i:(,op1,op2) 四元式：（,op1,op2，result)如：a:= bc+bd 三元式 四元式(1) (, b, c)(1) (, b, c, t1)(2) (, b, d)(2) (, b, d, t2)(3) (+, (1), (2)(3) (+, t1, t2, t3)(4) (:=, (3), a)(4) (:

3、=, t3, a, )四元式操作符分類算術(shù)、邏輯、關(guān)系運算符IO操作類型轉(zhuǎn)換賦值(ASSIG,id1,n,id2)地址加(AADD,id1,id2,id3)標(biāo)號(LABEL,-,-,label)轉(zhuǎn)移過程調(diào)用傳送參數(shù)7.2語法制導(dǎo)方法語法制導(dǎo)方法 基于文法結(jié)構(gòu)，在每個產(chǎn)生式的右部增加語義動作，在語法分析過程中，如遇語義動作，就完成對應(yīng)的語義處理。屬性文法屬性直接與文法的符號相聯(lián)系若X為一文法符號，a為X的一個屬性，用X.a表示與X關(guān)聯(lián)的a的值對于每個文法規(guī)則X0-X1Xn,Xi的屬性Xi.aj與規(guī)則的其他符號的屬性a1,ak有關(guān)Xi.aj =fij(X0.a1, , Xn.ak)動作文法文法規(guī)則

4、與語義函數(shù)相聯(lián)系每個產(chǎn)生式的右部附著相應(yīng)的語義動作每個動作對應(yīng)一個函數(shù)動作文法的定義由語法分析的實現(xiàn)方式?jīng)Q定實例VT = 0, 1, aVN = Z, LS = ZP: Z L L 0 L L 1 L L a VT = 0, 1, aVN = Z,D,LS = ZP: Z L L DL D 1 D 0 L ainit()sum0 = 0; sum1 =0;add1()sum1+;print()printf(sum0, sum1);add0()sum0+;類型檢查和類型轉(zhuǎn)換各種條件表達(dá)式的類型是否是布爾類型？運算符的運算分量是否相容？賦值語句的左、右部類型是否相容？實參與形參的類型是否相容？下標(biāo)

5、表達(dá)式的類型是否為所允許的類型？函數(shù)說明中的函數(shù)類型與返回值的類型是否一致？中間代碼生成中的幾個問題語義信息的獲取與保存標(biāo)識符的語義信息類型檢查、轉(zhuǎn)換目標(biāo)代碼生成保留相關(guān)運算分量和結(jié)果的語義信息地址表示語義棧及其操作用途：變量和表達(dá)式的處理時存放運算分量和結(jié)果的類型和語言信息(層數(shù)、偏移、訪問方式等，用一個記錄FORM表示)top、push(x)、pop(n)常用的語義子程序申請存儲單元New_dir(t)New_indir(t)存放中間代碼Generate（,op1,op2，result）生成中間代碼GenCode（）類型轉(zhuǎn)換？生成中間代碼清理語義棧7.3簡單表達(dá)式的中間代碼生成E T Es

6、/Es是一個符號Es +T $GenCode(+) Es Es T PTsTs *P $GenCode() TsTs P id $Push(id)P C $Push(C)/C表示常量P (E)7.4下標(biāo)變量中間代碼生成(1) V $Init id $PUSH(Addr(id) A (2) A E $AddNext B(3) B B E $AddNext B $Init：用來初始化下標(biāo)計數(shù)器 n = 0；$Push：把id首地址壓入棧中；$AddNext：1) 下標(biāo)計數(shù)器加1，即 n := n+1；2) 從語義棧中取出下標(biāo)表達(dá)式計算結(jié)果r；3) 生成計算第n維下標(biāo)需要累加的地址偏移的四元式組：(

7、 SUBI, r, Ln, tn+1) ( MULTI , tn+1 , Sk , tn+2 )( MULT, tn+2 , ele_size, tn+3)4) 從語義棧中取出地址累加結(jié)果ad；5) 生成地址累加四元式( ADDI , ad , tn+3, tn+4)6) 把累加后的地址結(jié)果tn+4壓入語義棧； 中間代碼生成實例int i,m; float z;struct rt int y; float x;rt a100;a5+i.x + m * z (ADDI, 5, i, t1) (SUBI, t1 ,0, t2) (MULTI, t2, 6,t3)(AADD, a , t3, t4)

8、5. (AADD , t4, 2, t5) 6. (FLOAT , m, t6) 7. (MULTF , t6, z, t7) 8. (ADDF , t5, t7,t8)賦值語句的形式為：Left := Right 賦值語句的四元式結(jié)構(gòu) ：Left 的中間代碼 Right 的中間代碼 (FLOAT , right , , t )(ASSIG , Right（即t）, n , Left ) 語法制導(dǎo)： S L:=R$ASSIGN$ASSIGN：從語義棧中取出賦值號左右分量的語義信息；比較類型是否相同，如果不同，則生成類型轉(zhuǎn)換中間代碼；生成賦值四元式(ASSIG , Right （t）, n ,

9、Left )。 賦值語句中間代碼過函調(diào)用的中間代碼 f(E1，E2，En): E1.tuple En.tuple(ACT,E1.Arg)(ACT,En.Arg)(CALL,，result) 或(CALL,，) 傳給形參形參實參結(jié)合中間代碼:(VALACT, Ei.Arg, offseti, sizei)值參(VARACT, Ei.Arg, offseti, sizei)變參(FUNCACT, Ei.Arg, offseti, sizei)函數(shù)參數(shù)(PROACT, Ei.Arg, offseti, sizei)過程參數(shù)過/函調(diào)用代碼：(call , true, result) 靜態(tài)轉(zhuǎn)向地址(ca

10、ll , false, result) 動態(tài)轉(zhuǎn)向地址例：x + f (H(10), g(Y)其中x是整型變量，H為返回值為整型的形式函數(shù)名，H的形參為整型值參，f、g為實在函數(shù)名，f的參數(shù)均為整型值參，g的參數(shù)為字符型變參。約定整型和指針型（變參）存儲占2字節(jié)，字符型占1字節(jié)，布爾型占1字節(jié)，實型占4字節(jié)。 （ VALACT,10,0,2） ( CALL, H, false, t1 ) ( VARACT,Y,0,2) ( CALL, g, true, t2 ) ( VALACT, t1, 0,2 ) ( VALACT, t2, 2,2 ) ( CALL, f, true, t3 ) ( ADD

11、I, x, t3, t4 )過/函調(diào)用中間代碼的生成遇到過/函名：在符號表中的地址壓棧，實參計數(shù)器為0；遇到實參Ei：產(chǎn)生計算表達(dá)式Ei的中間代碼，實參的語義信息壓棧，計數(shù)器加1。實參結(jié)束：根據(jù)過/函的語義信息，檢查形參與實參個數(shù)一致？類型相容？種類符合？過/函？產(chǎn)生參數(shù)傳送的中間代碼；產(chǎn)生調(diào)用的中間代碼；刪除語義棧中過/函名及實參的內(nèi)容，如果是函數(shù)將返回值的語義信息壓入棧中。CallHeadActParamCallTail過/函調(diào)用的語法制導(dǎo)ProcFunCall id $CallHead ( ParamList ) $CallTailParamList | ExpListExpList E

12、 $ActParam NextListNextList | , ExpList LABEL L1,L2,.,Ln 空SGOTO Li （JUMP,-,-,ARG(Li)SLi:S ( LABEL,-,-,ARG(Li)S.tupleGOTO語句和標(biāo)號語句的中間代碼條件語句的中間代碼條件語句的文法： Sif E then S ElsePart ElsePartelse S|條件語句的中間代碼形式if E then S1 else S2 if E then S E的中間代碼(THEN, E.FORM, _)S1的中間代碼(ELSE, _, _, _)S2的中間代碼(ENDIF, _, _, _)E

13、的中間代碼(THEN, E.FORM, _)S的中間代碼(ENDIF, _, _, _)條件語句中間代碼的語法制導(dǎo)生成方法S if E then $ThenIf S ElsePart $EndIfElsePart else $ElseIf SElsePart $ThenIf檢查Semtop的值的類型是否為boolean類型，如果是則產(chǎn)生中間代碼(THEN,Semtop,_,_)。$ElseIf產(chǎn)生中間代碼 (ELSE,_,_,_) $EndIf產(chǎn)生中間代碼 (ENDIF,_,_,_) 條件語句的中間代碼2IF E THEN S1 ELSE S2E.Tuple(JUMP0,E.Arg,-,S.E

14、lseL)S1.Tuple(JUMP,-,-,S.OutL)(LABEL,-,-,S.ElseL)S2.Tuple(LABEL,-,-,S.OutL)S IF E THEN S1E.Tuple(JUMP0,E.Arg,-,S.OutL)S1.Tuple(LABEL,-,-,S.OutL)條件語句代碼生成2(LL文法)Sif #StartIF E then #TestIF S1 ElsePart #EndIFElsePart else #GenJump #GenElseL S2 #GenOutLElsePart #GenOutL#StartIF:PUSH(S.ElseL);PUSH(S.OutL

15、);#TestIF:Generate(JUMP0,Semtop.Arg,Semtop-2);POP(1)#GenJump:Generate(JUMP,Semtop.Arg )#GenElseL: Generate(LABEL,Semtop-1.Arg)#GenOutL: Generate(LABEL, Semtop.Arg)#EndIF: POP(2)While語句的中間代碼while語句的文法：S while E do S while語句的中間代碼形式(WHILE, _, _, _)E的中間代碼(DO, E.FORM, _, _)S的中間代碼(ENDWHILE, _, _, _)while語

16、句的中間代碼的語法制導(dǎo)生成方法Swhile$StartWhileE do $DoWhileS$EndWhile$StartWhile產(chǎn)生中間代碼 (WHILE, _, _, _)$DoWhile遇do時（表達(dá)式E已經(jīng)處理完，值在Semtop中）：類型檢查：檢查E是否為boolean類型；產(chǎn)生中間代碼 (DO, E.FORM , _, _)；E彈棧：pop(1)； $EndWhile產(chǎn)生中間代碼 (ENDWHILE, _, _, _) 過程/函數(shù)聲明的中間代碼過程/函數(shù)的文法定義：ProcFunDecProcDec | FunDecProcDecProcedure id (ParamList)

17、Declaration ProgramBodyFunDecFunction id (ParamList):Type Declaration ProgramBody 過/函聲明的中間代碼形式形式：Procedure P(FormDecList) LabelDec ConstDec TypeDec VarDec ProDec1 ProDecn Body中間代碼結(jié)構(gòu)：(Entry,Label,Size,Level) ProDec1.tuple ProDecn.tuple Body.Tuple(EndProc/EndFunc,-,-,-)函數(shù)聲明中間代碼生成實例procedure Q( x: real

18、 );var u : real ;function f(k:real):real; begin f := k +k end;begin u := f(50); y:= u * x end； (EntryQ,LabelQ,SizeQ,LQ)(Entryf,Labelf,Sizef,Lf)(ADDF, k, k, t0)(ASSIG, t0,f)(ENDFUNC,)(VALACT, 50,1,1)(CALL, Labelf,true,t1)(ASSIG, t1, u)(MULTF, u,x, t2)(ASSIG, t2, y)(ENDPROC, )函數(shù)聲明的中間代碼的語法制導(dǎo)生成方法ProcFunDec ProcDec | FunDecProcD