编译程序原理与实现：第7章 中间代码生成(2)

1、第七章 中间代码生成 7.1 几种常见的中间表示 7.2 中间代码中生成的几个问题 7.3 表达式的中间代码生成 7.4 原子语句的中间代码生成 7.5 结构语句的中间代码生成 7.6 声明的中间代码生成7.2 中间代码生成中的几个问题语义信息的获取和保存目标代码阶段保留符号表，则可用标识符在符号表中的地址不保留符号表，则用FORM结构保存标识符的语义信息语义栈Sem及其操作语义栈的内容：运算分量的类型和FORM数据结构定义：typedef struct SemElem typ: ElemType; Form: FormStructtypedef SemElem SemStackMax 变量及

2、操作：SemStack Sem; /声明Sem为语义栈int top; /声明top为语义栈栈顶push(x) : 将x的类型和Form压入语义栈 pop(n) ：从Sem栈栈顶依次弹出n个元素7.2 中间代码生成中的几个问题常用的语义子程序申请临时单元new_dir(t): 在临时变量区申请一个单元t，且t是直接寻址new_indir(t): t是间接寻址存放中间代码子程序Generate(,left,right,result)将一条四元式中间代码存放到中间代码区中产生一条中间代码子程序GenCode()产生一条中间代码子程序GenCode()调用该函数时，左右操作数已进语义栈Sem;分别取

3、出左右操作数；检查类型是否相同，不同则进行转换，产生类型转换四元式；产生中间代码（ *, Semtop-1, Semtop,t）pop(2); /弹出左右分量push(t) /压入结果t的类型和FormL.typ, L.formR.typ, R.formSemtopt.typ, t.formSemtop7.3 表达式的中间代码生成表达式的中间代码就是依据原表达式的语义产生出正确计算表达式值的四元式中间代码（即将计算顺序体现出来）表达式的运算分量可以是简单变量、复杂变量和函数调用表达式的运算符可以是算术运算符，关系运算符，逻辑运算符等首先给出简单算术表达式的中间代码生成复合变量的中间代码生成表达

4、式的四元式表达式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)语法制导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 #GenCod

5、e(/)# 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 *(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 )

6、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 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

7、Es ) ) Ts Es ) Ts EsTs Es Es复合变量：下标变量 Aij, 域名变量 , 指针变量 *p复合变量的中间代码是计算复合变量地址的四元式变量的语法:V idV1 V2 EV1 V2.idV1 *V2地址: addr(V) = addr(id) addr(V1) = addr(V2)+(E-low+1)*Elesize addr(V1) = addr(V2)+offset(id) addr(V1) = content(addr(V2)复合变量的四元式生成一维下标变量 ai和多维下标变量 aijk下标变量的四元式生成Var A:array L1.U1L2.U2L

8、nUn 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，否则 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

9、)(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; person class10; person *ptr;class5.age + *ptr.age(L, 0)(L, 10)(L, 340)class5.age t1*ptr.age t2 (+, t1

10、, 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;第七章 中间代码生成 7.1 几种常见的中间表示 7.2 中间代码中生成的几个问题 7.3 表达式的中间代码生成 7.4 原子语句的中间代码生成 7.5 结构语句的中间代码生成 7.6 声明的中间代码生成7.4 原子语句的中间代码生成赋值语句: V = Exp;I/O 语句Read(

11、V);Write(Exp);Goto 语句 : Goto Label标号语句: Label: Statement;函数调用返回语句: Return Exp;函数调用: F(Exp1, , Expn)赋值语句Left = RightLeft.code(ASSIG, t.Form, n, left.Form)Right.code其中n表示 Right.typ所占空间大小.(FLOAT, Right, _, t.Form)I/O 语句Write(Exp);Read(V)V.code(READ, _, _, V.Form)Exp.code(WRITE, _, _, Exp.Form)Goto语句和La

12、bel语句L: SGoto L(JUMP, _, _, LL)(LABEL, _, _, LL)S.codeReturn语句Return EE.code(RETURN, _, _, E.Form)Return(RETURN, _, _, _ )函数调用语句f(E1, , En)从符号表中获取f 的属性Level, params, type生成中间代码E1.code函数调用形实参结合En.code(VALACT, 实参.Form, offset, size)(VARACT, 实参.Form, offset, size)(call, f, true, t)(call, f, false, t)函数

13、调用例子函数f(x+1,Y)，其中x是一般整型变量, Y是变参整型变量，假定f是实在函数，f的两个形参一个是值参一个是变参(ADDI, x, 1, t1）(VALACT, t1, offset1, 1)(VARACT, Y, offset2, 1)(CALL, f, true, t2)第七章 中间代码生成 7.1 几种常见的中间表示 7.2 中间代码中生成的几个问题 7.3 表达式的中间代码生成 7.4 原子语句的中间代码生成 7.5 结构语句的中间代码生成 7.6 声明的中间代码生成7.5 结构语句的中间代码生成条件语句If 语句Switch 语句循环语句While 语句Repeat 语句F

14、or 语句IF语句If语句有下面两种形式： If then else If then ENYS1S2ENYSIF语句If 语句的中间代码结构： If then else 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 , #上述文法仍不

15、是LL(1)文法为使文法满足LL(1)条件，为IF语句增加一个结束符endif ,则文法变为:IF语句中间代码生成的LL(1)制导 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)

16、 S ENYSE.code(JUMP0, E.Form, _, exitL)S.code(LABEL, _, _, exitL)IF语句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, _

17、, _, _)while (E) SWhile语句例子while (a0) sum = sum*a; a-While语句E.code(JUMP0, E.Form, _, ExitL)S.code(JUMP, _, _, StartL)(LABEL, _, _, ExitL)其中StartL 和 ExitL 用NewLabel()生成.ENYS(LABEL, _, _, StartL)while (E) SSwitch语句switch E of case c1: S1; break; case cn: Sn; break; default: S; break; Ec1S1Endc2S2cnSno

18、therSSwitch语句Main ideaGenerate 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

19、of E is equal to ci, then goto Li;For each branch, generate labeled codes;Generate code for “OutL”;Switch语句四元式结构E.codeswitch E of case c1: S1; break; case cn: Sn; break; default: S; break; L1: S1.code; (goto OutL)Ln: Sn.code; (goto OutL)L: S.code; (goto OutL)(JUMP1, E.arg=c1, L1)(JUMP1, E.arg=cn, Ln

20、)(JUMP, _, _, L)(LABEL, _, _, OutL)Switch语句的例子switch (a+b) of case 1: x=1; break; case 3: x=3; case 5: x=5; break; default: y=4; For语句for (E1; E2; E3) SE2YE1SE3NE3.code(JUMP0, E2.arg, _, ExitL)(LABEL, _, _, ExitL)(LABEL, _, _, StartL)E1.codeE2.code(JUMP, _, _, SL)(LABEL, _, _, EL)S.code(JUMP, _, _,

21、StartL)(LABEL, _, _, SL)(JUMP, _, _, EL)For语句for (E1; E2; E3) SE2YE1SE3NE3.code(JUMP0, E2.arg, _, ExitL)(LABEL, _, _, ExitL)(LABEL, _, _, StartL)E1.codeE2.codeS.code(JUMP, _, _, StartL)S.codeE3.codeFor语句for ( i=1 ; i10; i+ ) a= a*i;for ( ; i =0; ) i = f() ;Repeat语句Repeat S until EENYSE.code(JUMP0, E

22、.arg, _, StartL)S.code(LABEL, _, _, StartL)What about “do-while” statement?第七章 中间代码生成 7.1 几种常见的中间表示 7.2 中间代码中生成的几个问题 7.3 表达式的中间代码生成 7.4 原子语句的中间代码生成 7.5 结构语句的中间代码生成 7.6 声明的中间代码生成声明的四元式常量声明 - 不生成代码类型声明 - 不生成代码变量声明 - 动态数组时生成代码 int a 函数声明 - 顺序生成下列代码函数入口 (ENTRY, )参数声明函数体函数出口(ENDFUN,)函数声明一般形式：主要思想：在函数声明中一读到函数名 f , 为 f 分配一个新的标号 Lf ; 生成四元式 (ENTRY, Lf, size, leve