第七章 中间代码生成(2).ppt

《第七章 中间代码生成(2).ppt》由会员分享，可在线阅读，更多相关《第七章 中间代码生成(2).ppt（50页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第七七章章 中中间间代代码码生成生成l 7.1 几种常几种常见的中的中间表示表示l 7.2 中中间代代码中生成的几个中生成的几个问题l 7.3 表达式的中表达式的中间代代码生成生成l 7.4 原子原子语句的中句的中间代代码生成生成l 7.5 结构构语句的中句的中间代代码生成生成l 7.6 声明的中声明的中间代代码生成生成7.2 7.2 中中间间代代码码生成生成中的中的几几个问题个问题1.1.语义信息的信息的获取和保存取和保存目目标代代码阶段保留符号表，段保留符号表，则可用可用标识符在符号表中的符在符号表中的地址地址不保留符号表，不保留符号表，则用用FORM结构构保存保存标识符的符的语义信息信

2、息2.2.语义栈Sem及其操作及其操作语义栈的内容：运算分量的的内容：运算分量的类型和型和FORM数据数据结构定构定义：typedef struct SemElem typ:ElemType;Form:FormStructtypedefSemElem SemStackMax 变量及操作：量及操作：SemStack Sem;/声明声明Sem为语义栈int top;/声明声明top为语义栈栈顶push(x):将将x的的类型和型和Form压入入语义栈pop(n)：从：从Sem栈栈顶依次依次弹出出n个元素个元素7.2 7.2 中中间间代代码码生成生成中的中的几几个问题个问题3.3.常用的常用的语义子程

3、序子程序l申申请临时单元元new_dir(t):在在临时变量区申量区申请一个一个单元元t，且，且t是直接是直接寻址址new_indir(t):t是是间接接寻址址l存放中存放中间代代码子程序子程序Generate(,left,right,result)将一条四元式中将一条四元式中间代代码存放到中存放到中间代代码区中区中l产生一条中生一条中间代代码子程序子程序GenCode()l产生一条中生一条中间代代码子程序子程序GenCode()调用用该函数函数时，左右操作数已，左右操作数已进语义栈Sem;分分别取出左右操作数；取出左右操作数；检查类型是否相同，不同型是否相同，不同则进行行转换，产生生类型型转

4、换四元式；四元式；产生中生中间代代码（*,Semtop-1,Semtop,t）pop(2);/弹出左右分量出左右分量push(t)/压入入结果果t的的类型和型和FormL.typ,L.formL.typ,L.formR.typ,R.formR.typ,R.formSemSemtoptopt.typ,t.formt.typ,t.formSemSemtoptop7.3 7.3 表表达达式的中式的中间间代代码码生成生成表达式的中表达式的中间代代码就是依据原表达式的就是依据原表达式的语义产生出正生出正确确计算表达式算表达式值的四元式中的四元式中间代代码（即将（即将计算算顺序体序体现出来）出来）表达式的

5、运算分量可以是表达式的运算分量可以是简单变量、复量、复杂变量和函数量和函数调用用表达式的运算符可以是算表达式的运算符可以是算术运算符，关系运算符，运算符，关系运算符，逻辑运算符等运算符等首先首先给出出简单算算术表达式的中表达式的中间代代码生成生成复合复合变量的中量的中间代代码生成生成表表达达式的式的四元四元式式表达式表达式E a*（3.5+i*b）假假设a,b为实型型变量，量，i为整型整型变量量 E生成的四元式如下：生成的四元式如下：(FLOAT,i,-,t1)(MULTF,t1,b,t2)(ADDF,3.5,t2,t3)(MULTF,a,t3,t4)表表达达式式四元四元式式生成生成LL(1)

6、LL(1)语语法法制制导导E T EsEs Es +T EsEs -T EsT P TsTs Ts*P TsTs/PTsP CP idP(E)E T EsEs Es +T#GenCode(+)#EsEs -T#GenCode(-)#EsT P TsTs Ts*P#GenCode(*)#TsTs/P#GenCode(/)#TsP C#Push(C)#P id#Push(id)#P(E)E a*(3.5+i*b)T Es a*(3.5+i*b)P Ts Es a*(3.5+i*b)id Ts Es a*(3.5+i*b)Ts Es *(3.5+i*b)Ts Es *(3.5+i*b)*PTs Es

7、 *(3.5+i*b)P Ts Es (3.5+i*b)(E)Ts Es (3.5+i*b)E)Ts Es 3.5+i*b)T Es)GenCode(*)Ts Es 3.5+i*b)P Ts Es)Ts Es 3.5+i*b)C Ts Es)Ts Es 3.5+i*b)Ts Es)Ts Es +i*b)Ts Es)Ts Es +i*b)Ts Es)Ts Es +i*b)Es)Ts Es +i*b)+T Es)Ts Es+i*b)T Es)Ts Es i*b)PTs Es)Ts Es i*b)id Ts Es)Ts Es i*b)Ts Es)Ts Es *b)Ts Es)Ts Es *b)*P

8、Ts Es)Ts Es *b)P Ts Es)Ts Es b)id Ts Es)Ts Es b)Ts Es)Ts Es )Ts Es)Ts Es )Ts Es)Ts Es )Es)Ts Es )Es)Ts Es )Ts Es )Ts EsTs Es Es复合复合变量：下量：下标变量量 Aij,域名域名变量量 st.name,指指针变量量*p复合复合变量的中量的中间代代码是是计算复合算复合变量地址的四元式量地址的四元式变量的语法:V idV1 V2 EV1 V2.idV1 *V2地址:addr(V)=addr(id)addr(V1)=addr(V2)+(E-low+1)*Elesize addr

9、(V1)=addr(V2)+offset(id)addr(V1)=content(addr(V2)复复合合变变量量的的四元四元式式生成生成一一维下下标变量量 ai和多和多维下下标变量量 aijk下下标变标变量量的的四元四元式式生成生成Var A:array L1.U1L2.U2LnUn of T;(n=1)数组第1行的宽度是 D1=U1-L1+1;数组第i行的宽度是 Di=Ui-Li+1；设类型T所占单元数为，则数组A占单元数为size(A)=D1*D2*Dn*下标变量AE1E2Ek地址为：Addr(A)+(E1-L1)*S1+(Ek-Lk)*Sk)*size(T)其中 当 i=1时，s1=1

10、，否则 si=Di+1*Di+2*Dn sn=1AE1E2Ek(k=n)(ASSIG,size(T),-,tsize)E1 t1(SUBI,t1,L1,t2)(MULTI,t2,s1,t3)(MULTI,t3,tsize,t4)(AADD,addr(A),t4,ad)(SUBI,tn,Lk,tn+1)(MULTI,tn+1,sk,tn+2)(MULTI,tn+2,tsize,tn+3)(AADD,ad,tn+3,tn+4)Ek tn表表达达式式代代码码生成生成的例子的例子typedef struct char name30;int age;float height;person;int x10

11、;person class10;person *ptr;class5.age+*ptr.age(L,0)(L,10)(L,340)class5.age t1*ptr.age t2 (+,t1,t2,t3)class5 t4 (AADD,t4,30,t1)(-,5,0,t5)(*,t5,33,t6)(AADD,class,t6,t4)*ptr t7 (AADD,t7,30,t2)(Assig,ptr,_,t7)t1,t2,t4和t7的mode是indir;第第七七章章 中中间间代代码码生成生成l 7.1 几种常几种常见的中的中间表示表示l 7.2 中中间代代码中生成的几个中生成的几个问题l 7.

12、3 表达式的中表达式的中间代代码生成生成l 7.4 原子原子语句的中句的中间代代码生成生成l 7.5 结构构语句的中句的中间代代码生成生成l 7.6 声明的中声明的中间代代码生成生成7.4 原原子子语语句的中句的中间间代代码码生成生成赋值语句句:V=Exp;I/O 语句句Read(V);Write(Exp);Goto 语句句:Goto Label标号号语句句:Label:Statement;函数函数调用返回用返回语句句:Return Exp;函数函数调用用:F(Exp1,Expn)赋值语句lLeft=RightLeft.code(ASSIG,t.Form,n,left.Form)Right.c

13、ode其中n表示 Right.typ所占空间大小.(FLOAT,Right,_,t.Form)I/O 语句Write(Exp);lRead(V)V.code(READ,_,_,V.Form)Exp.code(WRITE,_,_,Exp.Form)Goto语句和Label语句L:SlGoto L(JUMP,_,_,LL)(LABEL,_,_,LL)S.codeReturn语句lReturn EE.code(RETURN,_,_,E.Form)Return(RETURN,_,_,_)函数调用语句lf(E1,En)l从符号表中获取f 的属性Level,params,typel生成中间代码E1.cod

14、e函数调用形实参结合En.code(VALACT,实参.Form,offset,size)(VARACT,实参.Form,offset,size)(call,f,true,t)(call,f,false,t)函数调用例子函数f(x+1,Y)，其中x是一般整型是一般整型变量量,Y是是变参整型参整型变量，假定量，假定f是是实在函数，在函数，f的两个形参一个是的两个形参一个是值参一个是参一个是变参参(ADDI,x,1,t1）(VALACT,t1,offset1,1)(VARACT,Y,offset2,1)(CALL,f,true,t2)第第七七章章 中中间间代代码码生成生成l 7.1 几种常几种常见

15、的中的中间表示表示l 7.2 中中间代代码中生成的几个中生成的几个问题l 7.3 表达式的中表达式的中间代代码生成生成l 7.4 原子原子语句的中句的中间代代码生成生成l 7.5 结构构语句的中句的中间代代码生成生成l 7.6 声明的中声明的中间代代码生成生成7.5 结构语结构语句的中句的中间间代代码码生成生成条件条件语句句If 语句句Switch 语句句循循环语句句While 语句句Repeat 语句句For 语句句IF语句If语句有下面两种形式：句有下面两种形式：If then else If then ENYS1S2ENYSIF语句If 语句的中句的中间代代码结构：构：If then e

16、lse E.code(THEN,E.Form,_,_)S1.code(ELSE,_,_,_)S2.code(ENDIF,_,_,_)If then E.code(THEN,E.Form,_,_)S1.code(ENDIF,_,_,_)IF语句中间代码生成的LL(1)制导 If then else If then 提取左公共前提取左公共前缀后，文法后，文法变为 If then else else else,#上述文法仍不是上述文法仍不是LL(1)文法文法为使文法使文法满足足LL(1)条件，条件，为IF语句增加一个句增加一个结束符束符endif,则文法文法变为:IF语句中间代码生成的LL(1)制导

17、 If then else endif If then endif提取左公共前提取左公共前缀后，文法后，文法变为 If then else endif else endif endif文法文法满足足LL(1)文法条件，文法条件，语法制法制导：If then#ThenIf#else#ElseIf#endif#EndIf#endif#EndIf#IF语句的例子if (ab)then mark=true;c=a;else mark=false;c=b;endifIF语句If (E)S ENYSE.code(JUMP0,E.Form,_,exitL)S.code(LABEL,_,_,exitL)IF语

18、句If (E)S1 else S2ENYS1S2E.code(JUMP0,E.arg,_,ElseL)S1.code(LABEL,_,_,ElseL)(JUMP,_,_,ExitL)S2.code(LABEL,_,_,ExitL)其中 ElseL 和 ExitL 是通过调用 NewLabel()生成的.While语句E.code(DO,E.Form,_,_)S.code(ENDWHILE,_,_,_)ENYS(WHILE,_,_,_)while (E)SWhile语句例子while(a0)sum=sum*a;a-While语句E.code(JUMP0,E.Form,_,ExitL)S.code

19、(JUMP,_,_,StartL)(LABEL,_,_,ExitL)其中StartL 和 ExitL 用NewLabel()生成.ENYS(LABEL,_,_,StartL)while (E)SSwitch语句switch E ofswitch E of case c1:S1;break;case c1:S1;break;case cn:Sn;break;case cn:Sn;break;default:S;break;default:S;break;E Ec1c1S1S1EndEndc2c2S2S2cncnSnSnotherotherS SSwitch语句Main ideaGenerate

20、following labels with the function NewLabel()L1,Ln,L:correspond to the entry to S1,Sn,S;OutL:corresponds to the end of the switch statement;The process of executing switch statementCalculate E at first;Comparing the result of E with c1,cn,if the result of E is equal to ci,then goto Li;For each branc

21、h,generate labeled codes;Generate code for“OutL”;Switch语句四元式结构四元式结构E.codeE.codeswitch E ofswitch E of case c1:S1;break;case c1:S1;break;case cn:Sn;break;case cn:Sn;break;default:S;break;default:S;break;L1:S1.code;(goto OutL)L1:S1.code;(goto OutL)Ln:Sn.code;(goto OutL)Ln:Sn.code;(goto OutL)L:S.code;(

22、goto OutL)L:S.code;(goto OutL)(JUMP1,E.arg=c1,L1)(JUMP1,E.arg=c1,L1)(JUMP1,E.arg=cn,Ln)(JUMP1,E.arg=cn,Ln)(JUMP,_,_,L)(JUMP,_,_,L)(LABEL,_,_,OutL)(LABEL,_,_,OutL)Switch语句的例子switch(a+b)ofswitch(a+b)of case 1:x=1;break;case 1:x=1;break;case 3:x=3;case 3:x=3;case 5:x=5;break;case 5:x=5;break;default:y=

23、4;default:y=4;For语句for(E1;E2;E3)Sfor(E1;E2;E3)SE2E2Y YE1E1S SE3E3N NE3.codeE3.code(JUMP0,E2.arg,_,ExitL)(JUMP0,E2.arg,_,ExitL)(LABEL,_,_,ExitL)(LABEL,_,_,ExitL)(LABEL,_,_,StartL)(LABEL,_,_,StartL)E1.codeE1.codeE2.codeE2.code(JUMP,_,_,SL)(JUMP,_,_,SL)(LABEL,_,_,EL)(LABEL,_,_,EL)S.codeS.code(JUMP,_,_,

24、StartL)(JUMP,_,_,StartL)(LABEL,_,_,SL)(LABEL,_,_,SL)(JUMP,_,_,EL)(JUMP,_,_,EL)For语句for(E1;E2;E3)Sfor(E1;E2;E3)SE2E2Y YE1E1S SE3E3N NE3.codeE3.code(JUMP0,E2.arg,_,ExitL)(JUMP0,E2.arg,_,ExitL)(LABEL,_,_,ExitL)(LABEL,_,_,ExitL)(LABEL,_,_,StartL)(LABEL,_,_,StartL)E1.codeE1.codeE2.codeE2.codeS.codeS.code

25、(JUMP,_,_,StartL)(JUMP,_,_,StartL)S.codeS.codeE3.codeE3.codeFor语句for(i=1;i10;i+)a=a*i;for (;i=0;)i=f();Repeat语句Repeat S until ERepeat S until EE EN NY YS SE.codeE.code(JUMP0,E.arg,_,StartL)(JUMP0,E.arg,_,StartL)S.codeS.code(LABEL,_,_,StartL)(LABEL,_,_,StartL)What about“do-while”statement?What about“

26、do-while”statement?第第七七章章 中中间间代代码码生成生成l 7.1 几种常几种常见的中的中间表示表示l 7.2 中中间代代码中生成的几个中生成的几个问题l 7.3 表达式的中表达式的中间代代码生成生成l 7.4 原子原子语句的中句的中间代代码生成生成l 7.5 结构构语句的中句的中间代代码生成生成l 7.6 声明的中声明的中间代代码生成生成声声明的明的四元四元式式常量声明常量声明-不生成代不生成代码类型声明型声明-不生成代不生成代码变量声明量声明-动态数数组时生成代生成代码int a 函数声明函数声明-顺序生成下列代序生成下列代码函数入口函数入口(ENTRY,)参数声明参数

27、声明函数体函数体函数出口函数出口(ENDFUN,)函数声明一般形式：一般形式：主要思想：主要思想：在函数声明中一在函数声明中一读到函数名到函数名 f,为 f 分配一个新的分配一个新的标号号 Lf;生成四元式生成四元式(ENTRY,Lf,size,level)参数声明参数声明:按按变量声明量声明处理理;函数体函数体:顺序生成四元式序生成四元式;函数声明函数声明结束束:生成四元式生成四元式(ENDFUNC,_,_,_)type f (parameters)body 函数声明type f (parameters)body (ENTRY,Lf,size,level)Parameters.codebod

28、y.code(ENDFUNC,_,_,_)函函数声数声明的例子明的例子int f(int num)if(num=0)return(1);if(num 0)return(-1);else num-;return(num+1)*f(num);第七章 总结中中间代代码的表示形式：后的表示形式：后缀式和四元式式和四元式表达式的代表达式的代码生成；生成；变量的代量的代码生成；生成；语句的代句的代码生成；生成；声明的代声明的代码生成；生成；知识关系图中间代码生成(1)可移植性(2)优化whywhat将源程序翻译成中间表示中间语言define(1)表达式(2)原子语句(3)结构语句(4)声明语句genera

29、te后缀式三地址代码AST,DAGhow(1)语法制导翻译方法(属性文法或者动作文法);(2)基于语法分析树的翻译;作业请写出下列程序的四元式中写出下列程序的四元式中间代代码.#define m 100typedef struct char name10;int age;int number;student;student class100;int FindAge(int id)int i=0;while(i100)do if(classi.number=id)then return(classi.age);endif;i=i+1;endwhile return-1;void main()FindAge(5);