编译原理第七章 中间代码生成.ppt

1、第七章 中间代码生成,中间语言 语法制导方法 简单表达式的中间代码生成 原子语句的中间代码生成 结构语句的中间代码生成 声明的中间代码,中间语言,后缀式-逆波兰式 图结构中间代码（语法树、DAG) 三地址中间代码（三元式、四元式）,三地址中间代码,三元式：i:(,op1,op2) 四元式：（ ,op1,op2，result),如：a:= bc+bd,语法制导方法,语法制导方法 基于文法结构，在每个产生式的右部增加语义动作，在语法分析过程中，如遇语义动作，就完成对应的语义处理。,类型检查和类型转换,各种条件表达式的类型是否是布尔类型？ 运算符的运算分量是否相容？ 赋值语句的左、右部类型是否相容？

2、 实参与形参的类型是否相容？ 下标表达式的类型是否为所允许的类型？ 函数说明中的函数类型与返回值的类型是否一致？,中间代码生成中的几个问题,语义信息的获取与保存 语义栈及其操作 常用的语义子程序,简单表达式的LL语法制导,E T Es Es +T #GenCode(+) Es Es T PTs Ts *P #GenCode() Ts Ts P id #Push(id) P C #Push(C) P (E),下标变量中间代码生成,(1) V #Init id #PUSH(Addr(id) A (2) A E #AddNext B (3) B B E #AddNext B #Init：用来初始化下

3、标计数器 n = 0； #Push：把id首地址压入栈中； #AddNext： 1) 下标计数器加1， n := n+1； 2) 从语义栈中取出下标表达式计算结果result； 3) 生成计算第n维下标需要累加的地址偏移的四元式组： ( SUBI, result, Ln, tn+1) ( MULTI , tn+1 , Sk , tn+2 ) ( MULT, tn+2 , size, tn+3) 4) 从语义栈中取出地址累加结果ad； 5) 生成地址累加四元式( ADDI , ad , tn+3 , tn+4) 6) 把累加后的地址结果压入语义栈；,表达式中间代码生成的例子,a5+i.x + m

4、 * z 其中，i,m:integer; z:real; a:array1.100 of rt; rt = record y:int;x:real end,(ADDI, 5, i, t1) (SUBI, t1 ,1, t2) (MULTI, t2, 2,t3) (AADD, a , t3, t4),5. (AADD , t4, 1, t5) 6. (FLOAT , m, t6) 7. (MULTF , t6, z, t7) 8. (ADDF , t5, t7,t8),赋值语句的形式为：Left := Right 赋值语句的四元式结构 ： Left 的中间代码 Right 的中间代码 (FLOA

5、T , right , , t ) (ASSIG , Right（t）, n , Left ) 语法制导： S L:=R #ASSIGN #ASSIGN： 从语义栈中取出赋值号左右分量的语义信息； 比较类型是否相同，如果不同，则生成类型转换中间代码； 生成赋值四元式(ASSIG , Right （t）, n , Left )。,赋值语句中间代码,过函调用的中间代码 f(E1，E2，En): E1.tuple En.tuple (ACT,E1.Arg) (ACT,En.Arg) (CALL,，result) 或(CALL,，),传给形参,形参实参结合中间代码: (VALACT, Ei.Arg,

6、offseti, sizei)值参 (VARACT, Ei.Arg, offseti, sizei)变参 (FUNCACT, Ei.Arg, offseti, sizei)函数参数 (PROACT, Ei.Arg, offseti, sizei)过程参数,过/函调用代码： (call , true, result) 静态转向地址 (call , false, result) 动态转向地址,例：x + f (H(10), g(Y) 其中x是整型变量，H为形参函数名，H的形参为 值参，f、g为实在函数名，f的参数均为值参， g的参数为变参。 （ VALACT,10,1,1 ） ( CALL, H,

7、 false, t1 ) ( VARACT, Y,1,1 ) ( CALL, g, true, t2 ) ( VALACT, t1, 1,size1 ) ( VALACT, t2, 2,size2 ) ( CALL, f, true, t3 ) ( ADDI, x, t3, t4 ),过/函调用中间代码的生成,遇到过/函名： 在符号表中的地址压栈，实参计数器为0； 遇到实参Ei： 产生计算表达式Ei的中间代码，实参的语义 信息压栈，计数器加1。 实参结束： 根据过/函的语义信息，检查形参与实参个数 一致？类型相容？种类符合？过/函？， 产生参数传送的中间代码。产生调用的中间代码 删除语义栈中过

8、/函名及实参的内容， 如果是函数 将返回值的语义信息压入栈中。,CallHead,ActParam,CallTail,过/函调用的语法制导,ProcFunCall id #CallHead ( ParamList ) #CallTail ParamList | ExpList ExpList E #ActParam NextList NextList | , ExpList,GOTO语句和标号语句的中间代码,LABEL L1,L2,.,Ln 空 SGOTO Li （JUMP, ARG(Li) ) SLi:S ( LABEL,ARG(Li) ) S.tuple,条件语句的中间代码,条件语句的文法

9、： S if E then S ElsePart ElsePart else S ElsePart 条件语句的中间代码形式 if E then S1 else S2 if E then S,E的中间代码 (THEN, E.FORM, _) S1的中间代码 (ELSE, _, _, _) S2的中间代码 (ENDIF, _, _, _),E的中间代码 (THEN, E.FORM, _) S的中间代码 (ENDIF, _, _, _),条件语句的语法制导 S if E then #ThenIf S ElsePart #EndIf ElsePart else #ElseIf S ElsePart #

10、ThenIf 根据Sem top 的值，检查它的类型是否为boolean类型，如果是则产生中间代码 (THEN, Semtop, _, _)。 #ElseIf 产生中间代码 (ELSE, _, _, _) #EndIf 产生中间代码 (ENDIF, _, _, _),While语句的中间代码,while语句的文法： S while E do S while语句的中间代码形式,(WHILE, _, _, _) E的中间代码 (DO, E.FORM, _, _) S的中间代码 (ENDWHILE, _, _, _),while语句的语法制导 S while #StartWhile E do #Do

11、While S #EndWhile #StartWhile 产生中间代码 (WHILE, _, _, _) #DoWhile 遇 do 时（表达式E处理完，其值在Semtop）： 类型检查：检查E是否为boolean类型； 产生中间代码 (DO, E.FORM , _, _)； E弹栈：pop(1)； #EndWhile 产生中间代码 (ENDWHILE, _, _, _),过程/函数声明的中间代码,过程/函数的文法定义： ProcFunDecProcDec | FunDec ProcDecProcedure id (ParamList) Declaration ProgramBody Fun

12、DecFunction id (ParamList):Type Declaration ProgramBody,过/函声明的中间代码形式,形式： Procedure P(FormDecList) LabelDec ConstDec TypeDec VarDec ProDec1 ProDecn Body,中间代码结构： (Entry,Label,Size,Level) ProDec1.tuple ProDecn.tuple Body.Tuple (EndProc/EndFunc,-,-,-),过程声明的例子,procedure Q( x: real ); var u : real ; funct

13、ion 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, ),过程/函数声明的语法制导,ProcFunDec ProcDec | FunDec ProcDec Procedure id (ParamList) Declaration #Entry ProgramBody #EndProc FunDec Function id (ParamLis