《编译原理第8章中间代码生成》由会员分享,可在线阅读,更多相关《编译原理第8章中间代码生成(29页珍藏版)》请在金锄头文库上搜索。
1、第八章第八章 中间代码生成中间代码生成 中间语言中间语言 简单表达式的中间代码生成简单表达式的中间代码生成 原子语句的中间代码生成原子语句的中间代码生成 结构语句的中间代码生成结构语句的中间代码生成 声明的中间代码声明的中间代码 中间语言中间语言 后缀式后缀式-逆波兰式逆波兰式 三地址中间代码(三元式、四元式)三地址中间代码(三元式、四元式) 图结构中间代码(语法树、图结构中间代码(语法树、DAG)DAG) 三地址中间代码三地址中间代码 三元式:三元式:i:(i:( ,op1,op2),op1,op2) 四元式四元式:( ,op1,op2,op1,op2,result)result) 如:a:
2、= 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) (:=, t3, a, ) 简单表达式的中间代码形式简单表达式的中间代码形式 E E C C Tuple(E)=Tuple(E)=空,空,ARG(E)= C.valARG(E)= C.val E E x x Tuple(E)=Tuple(E)=空,空,ARG(E)= x.valARG(E)= x.val E E E E1 1 E
3、 E2 2 Tuple(E)= Tuple(ETuple(E)= Tuple(E1 1)| Tuple(E)| Tuple(E2 2) ) | (| ( ,ARG(E,ARG(E1 1),ARG(E),ARG(E2 2),t),t) ) ARG(E)= t, tARG(E)= t, t是临时变量是临时变量 表达式的语义信息:表达式的语义信息: 表达式种类:表达式种类:E.kindE.kind 表达式的类型:表达式的类型:E.typeE.type 表达式的结果值表达式的结果值ARGARG:E.Arg E.Arg 或或 ARG(E)ARG(E) 标号标号L L:ARG(L)= LabelFormA
4、RG(L)= LabelForm(L)(L) 整数整数C C:ARG(C)= ValueFormARG(C)= ValueForm(C)(C) 源程序变量源程序变量X X:ARG(X)= AddrFormARG(X)= AddrForm(L,Off, Mode)(L,Off, Mode) 临时变量临时变量T T:ARG(T)= AddrFormARG(T)= AddrForm( (- -1, off, Mode)1, off, Mode) 表达式的中间代码:表达式的中间代码:E.tupleE.tuple 产生一条中间代码的子程序产生一条中间代码的子程序GenCode(GenCode( ) ):
5、 运算分量运算分量( (栈顶和次栈顶栈顶和次栈顶) )类型检查;类型检查; 如需类型转换:生成类型转换中间代码;如需类型转换:生成类型转换中间代码; 生成生成 操作的操作的中间代码中间代码; ; 从栈中删除运算分量的语义信息;从栈中删除运算分量的语义信息; 表达式结果的语义信息压栈表达式结果的语义信息压栈 简单表达式中间代码简单表达式中间代码 的的LRLR语法制导语法制导 E E T T E E E+T E+T #GenCode(+)#GenCode(+) T T P P T T T TP P # #GenCode(GenCode() ) P P C C Push(C.type,C.Arg)P
6、ush(C.type,C.Arg) P P id id Push(VarType(entry),VarArg(entry)Push(VarType(entry),VarArg(entry) P P (E) (E) 简单表达式的简单表达式的LLLL语法制导语法制导 E T Es Es +T #GenAdd Es Es T PTs Ts *P #GenMul Ts Ts P id #VPrimary P C #CPrimary P (E) GenAdd : GenCode(+) ; GenMul: GenCode() Vprimary,Cprimary: 同上。 变量中间代码结构变量中间代码结构
7、V.tuple=空 V V1.id V1.tuple (AADD,V1.Arg,offset(id),V.Arg) V V1E V1.tuple E.tuple (SUBI, E.Arg, low, t1) (MULTI, t1, size, t2) (AADD, V1.Arg, t2, V.Arg) V V1 V1.tuple (ASSIGN,V1.Arg, V.Arg) V id 变量中间代码的变量中间代码的LRLR语法制导语法制导 V V idid Push(VarType(entry),VarArg(entry)Push(VarType(entry),VarArg(entry) V V
8、 V V1 1.id.id#FieldVar#FieldVar FieldVar: FieldVar: L:= SemtopL:= Semtop- -1; R:= Semtop;1; R:= Semtop; ResultArg:= NewTemp(indir);ResultArg:= NewTemp(indir); Generate(AADD,L.Arg, R.arg,ResultArg)Generate(AADD,L.Arg, R.arg,ResultArg) Pop(2),Push(R.type, ResultArg)Pop(2),Push(R.type, ResultArg) V V V
9、 V1 1EE#IndexVar#IndexVar IndexVar:IndexVar: L:= SemtopL:= Semtop- -1; R:= Semtop;1; R:= Semtop; ResultArg:=NewTemp(indir);ResultArg:=NewTemp(indir); ResultType:= L.Type.ElemType;ResultType:= L.Type.ElemType; Low:=L.Type.Low;Size:= L.Type.ElemSize;Low:=L.Type.Low;Size:= L.Type.ElemSize; Generate(SUB
10、I, R.Arg, Low, t1);Generate(SUBI, R.Arg, Low, t1); Generate(MULI, t1, Size, t2);Generate(MULI, t1, Size, t2); Generate(AADD, L.Arg,t2, ResultArg);Generate(AADD, L.Arg,t2, ResultArg); POP(2); Push(ResultType,ResultArg);POP(2); Push(ResultType,ResultArg); V V V V1 1 #DenoVar#DenoVar DenoVar:DenoVar: R
11、esultArg:=NewTemp(indir);ResultArg:=NewTemp(indir); ResultType:= Semtop.Type.BaseType;ResultType:= Semtop.Type.BaseType; Generate(ASSIG, Semtop.Arg, ResultArg)Generate(ASSIG, Semtop.Arg, ResultArg) POP(1); Push(ResultType, ResultArg)POP(1); Push(ResultType, ResultArg) 表达式中间代码生成的例子表达式中间代码生成的例子 a5+i.x
12、 + m * za5+i.x + m * z 其中,其中,i,m:integer; z:real;i,m:integer; z:real; a:array1.100 of rt; a:array1.100 of rt; rt = record y:int;x:real endrt = record y:int;x:real end 1. (ADDI, 5, i, t1) 2. (SUBI, t1 ,1, t2) 3. (MULTI, t2, 2,t3) 4. (AADD, a , t3, t4) 5. (AADD , t4, 1, t5) 6. (FLOAT , m, t6) 7. (MULT
13、F , t6, z, t7) 8. (ADDF , t5, t7,t8) 原子语句的中间代码原子语句的中间代码 输入输出语句:输入输出语句: S Write(E) E.tuple (WRITE, E.Arg); S Read(V) V.tuple (READ, V.Arg) 语法制导: S Read(V) #READ S Write(E) #WRITE 赋值语句: 赋值语句形式: V:=E Vptr:=V1ptr f:=E Vstr:=V1str 赋值语句的中间代码形式: (ASSIGN,Arg1,Arg2,n) 或(FLOAT,Arg1,Arg2) S L:= RL.tuple R.tupl
14、e (ASSIGN, R,Arg, L.Arg, size) 或 (FLOAT, R.Arg, L.Arg) 动作文法: S L:=R#ASSIGN 过函调用语句 S id(E1,E2,En)E1.tuple En.tuple (ACT,E1.Arg) (ACT,En.Arg) (CALL,result) 或(CALL,) 传给形参 形参实参结合中间代码: (VALACT, Ei.Arg, offseti, sizei)值参 (VARACT, Ei.Arg, offseti, sizei)变参 (FUNCACT, Ei.Arg, offseti, sizei)函数参数 (PROACT, Ei.
15、Arg, offseti, sizei)过程参数 过/函调用代码: (call , true, result) 静态转向地址 (call , false, result) 动态转向地址 GOTOGOTO语句和标号语句的中间代码语句和标号语句的中间代码 LABELLABEL L L1 1,L,L2 2, ,.,L,Ln n空空 S SGOTOGOTOL Li i(JUMP,JUMP, ARG(LARG(Li i) ) ) ) S SL Li i: :S S( ( LABEL,ARG(LLABEL,ARG(Li i) ) ) ) S S. .tupletuple 结构语句的中间代码结构语句的中间代码 条件语句的中间代码条件语句的中间代码 WhileWhile语句的中间代码语句的中间代码 RepeatRepeat语句的中间代码语句的中间代码 ForFor语句的中间代码语句的中间代码 CaseCase语句的中间代码语句的中间代码 条件语句的中间代码条件语句的中间代码 IF E THEN S1ELSE S2 E.Tuple (JUMP0,E.Arg,S.ElseL) S1.Tuple (JUMP,S.OutL) (LABEL,S.ElseL) S2.Tuple (LABEL,S.OutL) S IF E THEN S1 E.Tuple (JUMP0,E.Arg