《编译原理及实现技术:22-中间代码生成_[3]》由会员分享,可在线阅读,更多相关《编译原理及实现技术:22-中间代码生成_[3](25页珍藏版)》请在金锄头文库上搜索。
1、第五章:中间代码生成(3) 2过程调用和函数调用的中间代码l形参种类:形参种类: 值参、变量参数、函数参数值参、变量参数、函数参数l需要的信息:需要的信息: 形参的种类、传送的内容、形参的种类、传送的内容、 偏移、传送的个数、函数类型偏移、传送的个数、函数类型( (实在函数、实在函数、形式函数形式函数) )l过程调用和函数调用的语法形式过程调用和函数调用的语法形式 ProcFunCall ProcFunCall idid (E (E1 1, , , E , En n) )3过程调用和函数调用的中间代码lcall call idid(E1.En)(E1.En)的中间代码结构:的中间代码结构: E
2、 E1 1 的中间代码的中间代码. .E En n 的中间代码的中间代码 (VarACT(VarACT变参变参/ValACT/ValACT值参值参,t,t1 1,Offset,Offset1 1,Size,Size1 1) ) . . (VarACT / ValACT , t (VarACT / ValACT , tn n ,Offset ,Offsetn n ,Size ,Sizen n) ) (CALL , ,true/false ,Result) (CALL , ,true/false ,Result) 注:注:truetrue静态确定转向地址;静态确定转向地址;false:false:
3、动态确定转向地址动态确定转向地址 (idid为形参函数);为形参函数);实参的计算实参的计算结果传递到结果传递到相应的形参相应的形参变量变量 调用过程调用过程/ /函数体执行函数体执行4过程调用和函数调用的中间代码( En . typ , En 语义信息信息 )( E1 . typ , E1 语义信息)信息)( , id )要检查的语义错误:【1】id是不是函数名【2】每个实参Ei和形参Xi的类型和种类方面是否匹配【3】实参个数和形参个数是否相同例:假设有实在函数调用例:假设有实在函数调用 f f(X+1,Y),(X+1,Y),并且并且 x x 是一般是一般整型变量,整型变量,Y Y 是变参整
4、型变量,是变参整型变量,f f函数名,同时假函数名,同时假定定 f f 的两个形参第一个是值参、整数类型,第二的两个形参第一个是值参、整数类型,第二个是变参、整数类型,则对应的中间代码如下:个是变参、整数类型,则对应的中间代码如下:( ( + + ,X ,X ,1,1 ,t,t1 1 ) )( ValACT ,t( ValACT ,t1 1 ,Offset ,Offset1 1 ,1 ),1 )( VarACT ,Y ,Offset( VarACT ,Y ,Offset1 1+1 ,1 )+1 ,1 )( CALL ,( CALL ,f f ,true ,t ,true ,t2 2 ) )注:
5、其中注:其中Offset1和和Offset1+1分别示表函数分别示表函数f的第的第1、2个参数的个参数的偏移量。偏移量。6过程调用和函数调用的动作文法 M(List) #send_turnM(List) #send_turn M M id #push1 ListList E #nextlistListList List,E #nextlist#push1的语义动作:将id压入Sem栈,参数计数器i为0#nextlist的语义动作:E已经在栈中,参数计数器累加,i+7过程调用和函数调用的动作文法#send_turn的语义动作w取出id:sem(s-i-1)的所有语义信息。w依此检查形、实参个数是
6、否一致,检查形、实参类型是否相容;w产生送实参信息到形参信息的ValAct/VarAct中间代码;w根据f是实在过程(函数)名或形式过程(函数)名产生相应的CALL代码;w删除当前过程 函数调用语句所占的i+1个语义栈单元,如果f是函数,则把返回值的类型和语义信息压入Sem栈。 ( ValACT,10, ValACT,10, Offset1, , 1 ) ( CALL, H, false, t ( CALL, H, false, t1 1 ) ) ( VarACT, Y, ( VarACT, Y, Offset1,1 ,1 ) ) ( CALL, g, true, t( CALL, g, tr
7、ue, t2 2 ) ) ( ValACT, t ( ValACT, t1 1, , Offset1,1 ) ) ( ValACT, t ( ValACT, t2 2, , Offset1+1,1+1,1) ) ( CALL, f, true, t ( CALL, f, true, t3 3 ) ) ( +, x, t ( +, x, t3 3, t, t4 4 ) )注:其中注:其中Offset1表示函数表示函数H,g及及f的第的第1个参数的偏移量。个参数的偏移量。例:例:x + f (H(10), g(Y)x + f (H(10), g(Y) 其中:其中:x x是整型变量,是整型变量,H
8、H为返回值是整型的形参函数名,为返回值是整型的形参函数名,H H的的 形参为整型值参,形参为整型值参,f,gf,g为返回值是整型的实在函数名,为返回值是整型的实在函数名,f f的参的参数均为整型值参,数均为整型值参,g g的参数为变参。的参数为变参。 f()()H(10)g(Y)x + f( )9控制语句的中间代码生成uGOTOGOTO语句和标号定位的中间代码语句和标号定位的中间代码u条件语句的中间代码条件语句的中间代码uWhileWhile语句的中间代码语句的中间代码10GOTOGOTO语句和标号定位的中间代码语句和标号定位的中间代码wgoto L的中间代码(JMP,-,-,L)wL:S的中
9、间代码(Label,-,-,L)S.codew动作文法、代码生成算法:S goto L #goto S S DL: S DL L #label11GOTOGOTO语句和标号定位的中间代码语句和标号定位的中间代码w对于标号表有定义情况:对于标号表有定义情况:#goto#goto 的语义动作的语义动作L L是指向标号表中对应的位置。是指向标号表中对应的位置。Gen(goto,-,-,sem(s-1) pop(1)Gen(goto,-,-,sem(s-1) pop(1) #label #label 的语义动作的语义动作Gen(label,-,-,sem(s-1) pop(1)Gen(label,-,
10、-,sem(s-1) pop(1)12GOTOGOTO语句和标号定位的中间代码语句和标号定位的中间代码w对于标号表没有定义的情况、且标号无需声明的语言,要在过程对于标号表没有定义的情况、且标号无需声明的语言,要在过程中创建标号表中创建标号表ArrayLArrayL:#goto#goto 的语义动作的语义动作(1 1)查)查ArrayLArrayL,如果没有则产生一条缺欠(需回填)转移地址的中,如果没有则产生一条缺欠(需回填)转移地址的中间代码间代码: (JMP , : (JMP , , , , , ) ),并把标号,并把标号L Li i、该四元式的地址、该四元式的地址以及表示该标号为未定位的标
11、记,添加到以及表示该标号为未定位的标记,添加到ArrayL ArrayL 。 若有则:若有则: L Li i是已经定位的了,从是已经定位的了,从ArrayLArrayL中取出它的地址中取出它的地址LLLLi i,然后,然后产生中间代码产生中间代码 : ( JMP , ( JMP , , , , LL , LLi i ) ) ; L Li i是未定位的,则从是未定位的,则从ArrayLArrayL中取出它的地址中取出它的地址LLLLi i,然后产生需回填,然后产生需回填转移地址的中间代码转移地址的中间代码 : ( JMP , ( JMP , , , , LL , LLi i ) ) ; Arra
12、yL ArrayL( L Li i )的地址填入上述中间代码编号。)的地址填入上述中间代码编号。13GOTOGOTO语句和标号定位的中间代码语句和标号定位的中间代码w#label的语义动作: 产生中间代码产生中间代码: ( LABEL , : ( LABEL , , , , L) , L); 然后查然后查ArrayLArrayLv如果没有标号如果没有标号L L则把该标号及其相应的语义信息则把该标号及其相应的语义信息加入中加入中ArrayLArrayL,并且标记为已定位;,并且标记为已定位;v如果有标号如果有标号L Li i并标为未定位,则往对应的所有四并标为未定位,则往对应的所有四元式回填地址
13、。元式回填地址。GOTO语句和标号定位中间代码的示例:例如有下列程序:例如有下列程序:. .10 goto L10 goto L1 1; ;. .20 goto L20 goto L1 1; ;. .30 goto L30 goto L1 1; ;. .40 L40 L1 1:S;S;. .50 goto L50 goto L1 1; ;p标号名标号名定位与否标志定位与否标志地址地址/语义信息语义信息/内部标号内部标号(m) ( JMP , , , )ArrayLArrayL结构:结构:(n) ( JMP , , , m) (p) ( JMP , , , n)(q) (LABEL , , ,
14、LL1).m (p) ( JMP , , , LL1)LL1L L1 1未定位未定位已已定位定位n (n) ( JMP , , , LL1) (m) ( JMP , , , LL1) (p) ( JMP , , , LL1) (n) ( JMP , , , LL1) (m) ( JMP , , , LL1)(w) (JMP, , , LL1).15条件语句的中间代码条件语句的中间代码wS if (E) then S1 else S2(1)wS if (E) then S2(2)(1)的结构:E的四元式(then,E,-,-) 作用:产生条件转移S1的四元式(else,-,-,-) 作用:转移、
15、定位S2的四元式(endif,-,-,-) 作用:定位16条件语句的中间代码条件语句的中间代码nif E then Sif E then S1 1(2 2)中间代码结构)中间代码结构: : E E 的中间代码的中间代码( THEN , E.FORM , ( THEN , E.FORM , , , ) ) S S1 1 的中间代码的中间代码(ENDIF , (ENDIF , , , , , ) )17条件语句的动作文法条件语句的动作文法wS if (E)then M S #endifwS if(E)then M1 S else M2 S#endifwM #thenwM1 #thenwM2 #el
16、se18条件语句的动作文法条件语句的动作文法w#then的语义动作的语义动作检查检查sem(s-1)sem(s-1)是不是逻辑值是不是逻辑值Gen(THEN,sem(s-1),-,-) pop(1)Gen(THEN,sem(s-1),-,-) pop(1)#else的语义动作的语义动作Gen(ELSE,-,-,-)Gen(ELSE,-,-,-)#endif#endif的语义动作的语义动作Gen(ENDIF,-,-,-)Gen(ENDIF,-,-,-)19While语句的中间代码wWhileWhile语句形式为:语句形式为: S S while while (E E) do S do S wWh
17、ileWhile语句的中间代码结构:语句的中间代码结构:( WHILE , ( WHILE , , , , , ) ) 定位定位E E 的中间代码的中间代码( DO , E . FORM , ( DO , E . FORM , , , ) ) 转移转移S S的中间代码的中间代码(ENDWHILE , (ENDWHILE , , , , , ) ) 定位、转移定位、转移20While语句的中间代码S S WHILE WHILE(E E) DO S #Whileend DO S #WhileendWHILE WHILE while #WhileDO DO do #Do do #Dov#While动
18、作:Gen(While,-,-,-)Gen(While,-,-,-)v#Do#Do动作:动作:E E的类型检查的类型检查 Gen(DO,Sem(s-1),-,-) pop(1) Gen(DO,Sem(s-1),-,-) pop(1)v#Whileend#Whileend动作:动作:Gen(Whileend,-,-,-)Gen(Whileend,-,-,-)21过程函数声明的中间代码生成w对应过程对应过程函数函数Q Q声明的中间代码有声明的中间代码有: : ( ENTRY , Label( ENTRY , LabelQ Q , Size, SizeQ Q , Level , LevelQ Q )
19、 ) 或或(ENTRY,Q,-,-)(ENTRY,Q,-,-) Q Q函数函数/ /过程体的中间代码过程体的中间代码 ( ENDPROC , ( ENDPROC , , , , , ) ) 或或 ( ENDFUNC , ( ENDFUNC , , , , , ) )22过程函数声明的中间代码生成w过程过程函数声明的形式可定义为:函数声明的形式可定义为:ProcFunDec ProcFunDec ProcDec | FunDec ProcDec | FunDecProcDec ProcDec Procedure id ( ParamList) Procedure id ( ParamList)
20、Declaration Declaration ProgramBody ProgramBodyFunDec FunDec Function id ( ParamList) : Type Function id ( ParamList) : Type Declaration Declaration ProgramBody ProgramBody其中其中ParamListParamList对应参数声明,对应参数声明,DeclarationDeclaration对应整个对应整个声明部分,声明部分,ProgramBodyProgramBody对应程序体,而对应程序体,而TypeType对应类对应类型定
21、义。型定义。动作文法为:动作文法为:wProcFunDec ProcFunDec ProcDec | FunDec ProcDec | FunDecProcDec ProcDec Procedure id#Entry#(ParamList) ; Declaration ProgramBody Procedure id#Entry#(ParamList) ; Declaration ProgramBody #EndProc#EndProc#wFunDec FunDec Function id#Entry#(ParamList) : Type; Declaration Function id#En
22、try#(ParamList) : Type; Declaration ProgramBody#EndFunc#ProgramBody#EndFunc#wEntry:Entry: 给子程序给子程序Q Q分配新标号分配新标号L Labeabel lQ Q ,并将它填到,并将它填到Q Q的符号表项中;产生入口的符号表项中;产生入口中间代码:中间代码:( ENTRY ,Label( ENTRY ,LabelQ Q ,Size,SizeQ Q ,Level ,LevelQ Q ) ) 或或(ENTRY,Q,-,-)(ENTRY,Q,-,-)wEndProcEndProc和和EndFunc:EndFun
23、c: 产生出口中间代码产生出口中间代码: : ( ENDPROC , ( ENDPROC , , , , , ) ) 或或 ( ENDFUNC , ( ENDFUNC , , , , , ) ) 例: 过程声明的中间代码(不保存符号表)procedure Q( x: real );var u : real ;function f( k: real ):real; begin f := k +k end;begin u := f(50); y:= u * x end; (ENTRY, Label(ENTRY, LabelQ Q, Size, SizeQ Q, L, LQ Q) )(ENTRY,
24、Label(ENTRY, Labelf f, Size, Sizef f,L,Lf f) )(+, k, k, t(+, k, k, t0 0) )(=, t(=, t0 0,-,f),-,f)(ENDFUNC,_ ,_ ,_)(ENDFUNC,_ ,_ ,_)(FLOAT, 50,_, t(FLOAT, 50,_, t1 1) )(VALACT, 50,off(VALACT, 50,offx x,2),2)(CALL, Label(CALL, Labelf f,true,t,true,t2 2) )(=, t(=, t2 2,-, u),-, u)(*, u,x, t(*, u,x, t3
25、3) )(=, t(=, t3 3,-, y),-, y)(ENDPROC, _ ,_ ,_)(ENDPROC, _ ,_ ,_)P138.3 a1.10of integer;a:=1;while a=10 dobegin if ab then Aa:=Ab+2 else a:=a+1; b:=b+1; end(=, t8,t4)( ELSE , , , )(+, a , 1, t9 )(=, t9, ,a ) ( ENDIF , , , ) (+, b , 1, t10 )(=, t10, , b ) (ENDWHILE , , , )(=, 1,a)( WHILE , , , )(= ,a,10,t0)( DO , t0 , , )( ,a,b,t1)( THEN , t1 , , ) ( - ,a , 1 , t2 ) (* , t2 , 1 , t3) (, A , t3, t4 )( - ,b , 1 , t5 ) (*, t5 , 1 , t6) (, A , t6, t7 ) (+, t7 , 2, t8 )