编译原理：第七章语义分析和中间代码产生.ppt

《编译原理：第七章语义分析和中间代码产生.ppt》由会员分享，可在线阅读，更多相关《编译原理：第七章语义分析和中间代码产生.ppt（104页珍藏版）》请在装配图网上搜索。

1、编译原理,第七章 语义分析和中间代码产生,第七章 语义分析和中间代码产生,静态语义检查 类型检查 控制流检查 一致性检查 相关名字检查 名字的作用域分析,语法分 析器,中间代码 产生器,静态检 查器,中间代码,优化器,中间语言(复杂性界于源语言和目标语言之间)的好处： 便于进行与机器无关的代码优化工作 易于移植 使编译程序的结构在逻辑上更为简单明确,源语言 程序,目标语 言程序,中间语 言程序,常用的中间语言： 后缀式，逆波兰表示 图表示： DAG、抽象语法树 三地址代码 三元式 四元式 间接三元式,7.1 中间语言,7.1.1 后缀式,后缀式表示法：Lukasiewicz发明的一种表示表达式

2、的方法，又称逆波兰表示法。 一个表达式E的后缀形式可以如下定义： 1. 如果E是一个变量或常量，则E的后缀式是E自身。 2. 如果E是E1 op E2形式的表达式，其中op是任何二元操作符，则E的后缀式为E1 E2 op，其中E1 和E2 分别为E1 和E2的后缀式。 3. 如果E是(E1)形式的表达式，则E1 的后缀式就是E的后缀式。,逆波兰表示法不用括号。只要知道每个算符的目数，对于后缀式，不论从哪一端进行扫描，都能对它进行唯一分解。 后缀式的计算 用一个栈实现。 一般的计算过程是：自左至右扫描后缀式，每碰到运算量就把它推进栈。每碰到k目运算符就把它作用于栈顶的k个项，并用运算结果代替这k

3、个项。,把表达式翻译成后缀式的语义规则描述,产生式 EE(1)op E(2) E (E(1) Eid,语义动作 E.code:= E(1).code | E(2).code |op E.code:= E(1).code E.code:=id,E.code表示E后缀形式 op表示任意二元操作符 “|”表示后缀形式的连接。,数组POST存放后缀式：k为下标，初值为1 上述语义动作可实现为： 产生式程序段 EE(1)op E(2)POSTk:=op;k:=k+1 E (E(1) EiPOSTk:=i;k:=k+1 例：输入串a+b+c的分析和翻译 POST： 1 2 3 4 5,EE(1)op E(

4、2) E.code:= E(1).code | E(2).code |op E (E(1)E.code:= E(1).code EidE.code:=id,a,b,+,c,+,7.1.2 图表示法,图表示法 DAG 抽象语法树,7.1.2 图表示法,无循环有向图(Directed Acyclic Graph，简称DAG) 对表达式中的每个子表达式，DAG中都有一个结点 一个内部结点代表一个操作符，它的孩子代表操作数 在一个DAG中代表公共子表达式的结点具有多个父结点,a:=b*(-c)+b*(-c)的图表示法,抽象语法树对应的代码： T1:=-c T2:=b*T1 T3:=-c T4:=b*T

5、3 T5:=T2+T4 a:=T5,DAG对应的代码： T1:=-c T2:=b*T1 T5:=T2+T2 a:=T5,抽象语法树对应的代码： T1:=-c T2:=b*T1 T3:=-c T4:=b*T3 T5:=T2+T4 a:=T5,产生赋值语句抽象语法树的属性文法,产 生 式语义规则 Sid:=ES.nptr:=mknode(assign, mkleaf(id,id.place),E.nptr) EE1+E2E.nptr:=mknode(+,E1.nptr,E2.nptr) EE1*E2E.nptr:=mknode(*,E1.nptr,E2.nptr) E-E1 E.nptr:=mkn

6、ode(uminus,E1.nptr) E (E1)E.nptr:=E1.nptr Eid E.nptr:=mkleaf(id,id.place),7.1.3 三地址代码,三地址代码 x:=y op z 三地址代码可以看成是抽象语法树或DAG的一种线性表示,a:=b*(-c)+b*(-c)的图表示法,DAG对应的代码： T1:=-c T2:=b*T1 T5:=T2+T2 a:=T5,抽象语法树对应的代码： T1:=-c T2:=b*T1 T3:=-c T4:=b*T3 T5:=T2+T4 a:=T5,三地址语句的种类,x:=y op z x:=op y x:=y goto L if x rel

7、op y goto L或if a goto L param x和call p,n，以及返回语句return y x:=yi及xi:=y的索引赋值 x:= E.code:=E1.code | E2.code | gen(E.place := E1.place + E2.place) EE1*E2E.place:=newtemp; E.code:=E1.code | E2.code | gen(E.place := E1.place * E2.place) E-E1 E.place:=newtemp; E.code:=E1.code | gen(E.place := uminus E1.place

8、) E (E1)E.place:=E1.place; E.code:=E1.code Eid E.place:=id.place; E.code= ,三地址语句,四元式 一个带有四个域的记录结构，这四个域分别称为op, arg1, arg2及result oparg1arg2result (0)uminus cT1 (1)* bT1T2 (2)uminus cT3 (3)* bT3T4 (4)+ T2T4T5 (5):= T5a,三地址语句,三元式 通过计算临时变量值的语句的位置来引用这个临时变量 三个域：op、arg1和arg2 oparg1arg2 (0)uminus c (1)* b(0

9、) (2)uminus c (3)* b(2) (4)+ (1)(3) (5)assign a(4),三地址语句,xi:=y op arg1 arg2 (0) = x i (1) assign (0) y x:=yi op arg1 arg2 (0) = y i (1) assign x (0),三地址语句,间接三元式 为了便于优化，用 三元式表+间接码表 表示中间代码 间接码表:一张指示器表，按运算的先后次序列出有关三元式在三元式表中的位置。 优点: 方便优化，节省空间,例如，语句 X:=(A+B)*C; Y:=D(A+B) 的间接三元式表示如下表所示。,7.2 说明语句,7.3 赋值语句的

10、翻译,7.3.1 简单算术表达式及赋值语句,为赋值语句生成三地址代码的S-属性文法定义,产生式语义规则 Sid:=ES.code:=E.code | gen(id.place := E.place) EE1+E2E.place:=newtemp; E.code:=E1.code | E2.code | gen(E.place := E1.place + E2.place) EE1*E2E.place:=newtemp; E.code:=E1.code | E2.code | gen(E.place := E1.place * E2.place) E-E1 E.place:=newtemp; E

11、.code:=E1.code | gen(E.place := uminus E1.place) E (E1)E.place:=E1.place; E.code:=E1.code Eid E.place:=id.place; E.code= ,产生赋值语句三地址代码的翻译模式,Sid:=E p:=lookup(id.name); if pnil then emit(p := E.place) else error EE1+E2 E.place:=newtemp; emit(E.place := E1.place + E2.place) EE1*E2 E.place:=newtemp; emit

12、(E.place := E 1.place * E 2.place),Sid:=E S.code:=E.code | gen(id.place := E.place) EE1+E2 E.place:=newtemp; E.code:=E1.code | E2.code |gen(E.place := E1.place + E2.place) EE1*E2 E.place:=newtemp; E.code:=E1.code | E2.code | gen(E.place := E1.place * E2.place),产生赋值语句三地址代码的翻译模式,E-E1 E.place:=newtemp;

13、 emit(E.place:= uminusE 1.place) E(E1) E.place:=E1.place Eid p:=lookup(id.name); if pnil then E.place:=p else error ,E-E1 E.place:=newtemp; E.code:=E1.code | gen(E.place := uminus E1.place) E (E1) E.place:=E1.place; E.code:=E1.code Eid E.place:=id.place; E.code= ,计算数组元素的地址 数组元素存储在一个连续的存储块中，根据数组元素的下标

14、可以快速地查找每个元素。 一维数组A,基址：base 域宽：w 元素个数：high-low+1,数组元素Ai的位置： base + ( i-low )w = iw + base - loww,7.3.2 数组元素的引用,二维数组A,存储方式： 按行存放 按列存放,每维的下界：low1、low2 每维的上界：high1、high2 每维的长度：n1=high1-low1+1 n2=high2-low2+1 域宽：w 基址：base,数组元素Ai,j的位置： base+(i-low1) n2+(j-low2)w =(in2+j)w+base-(low1n2+low2)w,每维的下界：low1、lo

15、w2、.、lowk 每维的长度：n1、n2、.、nk 存储方式：按行存放 数组元素Ai1,i2,.,ik的位置： ( ( (i1n2+i2)n3+i3 )nk+ik )w + base - ( ( (low1n2+low2)n3+low3 )nk+lowk )w,K维数组A,递归计算： e1=i1,e2=e1 n2+i2,e3=e2n3+i3,ek=ek-1nk+ik,S属性定义,SL:=E EE1+E2 E(E1) EL Lid | id Elist ElistElist1 , E | E,语句 X:=A i, j 的分析树,改写文法： Lid | Elist ElistElist1 , E

16、 | idE,(1) SL:=E (2) EE+E (3) E(E) (4) EL (5) LElist (6) Lid (7) Elist Elist, E (8) Elistid E,属性及函数设计,L 综合属性L.place和L.offset 简单变量： L.offset=null L.place=符号表入口指针 数组元素（下标变量）： L.offset=计算公式第一项，指存放VARPART （可变项）的临时变量的整数码 L.place=计算公式第二项，指存放CONSPART（不变项）的 临时变量的整数码 E 综合属性E.place，保存E值的变量在符号表中的位置 Elist 综合属性E

17、list.array，ndim，place Elist.array：数组名在符号表中的位置 Elist.ndim：目前已经识别出的下标表达式的个数 Elist.place：保存递推公式中em值的临时变量在符号表中的位置 函数 limit(array, j)：返回array指向的数组第j维的长度 invariant(array)：返回array指向的数组的地址计算公式中的不变项,S属性定义翻译方案,SL:=E, if (L.offset=null) /* L是简单变量 */ emit(L.place := E.place ); else emit(L.place L.offset := E.pl

18、ace); ,EE1+E2, E.place=newtemp; emit(E.place := E1.place + E2.place) ,E(E1), E.place=E1.place ,EL, if (L.offset = null) /* L是简单变量 */ E.place=L.place; else E.place=newtemp; emit(E.place := L.place L.offset ); ,Lid, L.place=id.place; L.offset=null ,ElistidE,ElistElist1,E,LElist, Elist.place=E.place; E

19、list.ndim=1; Elist.array=id.place , t=newtemp; m=Elist1.ndim+1; emit(t := Elist1.place limit(Elist1.array,m); emit(t := t + E.place); Elist.array=Elist1.array; Elist.place=t; Elist.ndim=m , L.place=newtemp; emit( L.place := Elist.array - invariant(Elist.array); L.offset=newtemp; emit(L.offset := w E

20、list.place) ,e2=e1n2+i2 e3=e2n3+i3 ek=ek-1nk+ik,e1=i1,Ai1,i2,ik (i1 n2+i2)n3+i3)nk+ik)w +base-(low1 n2+low2)n3+low3)nk+lowk)w,举例,已知： 设A为一个1020的数组，即 n1=10，n2=20； 并设域宽 w=4； 数组的第一个元素为A1,1， 则有 low1=1，low2=1 所以： (low1n2+low2)w = (120+1)4 = 84 问题： 将赋值语句 x:=Ay,z 翻译为三地址代码。,赋值语句 x:=Ay,z的分析树,A ,x,:=,y,z,.plac

21、e=x .offset=null,.place=y .offset=null,.place=y,.place=y .ndim=1 .array=A,，,.place=z .offset=null,.place=z,.place=t1 .ndim=2 .array=A,.place=t2 .offset=t3,.place=t4,t4:=t2t3,t1:=y*20 t1:=t1+z,类型转换,用E.type表示非终结符E的类型属性 对应产生式EE1 op E2的语义动作中关于E.type的语义规则可定义为： if E1.type=integer andE2.type=integer E.type

22、:=integer else E.type:=real 算符区分为整型算符int op和实型算符real op，,x:=yi*j 其中x、y为实型；i、j为整型。这个赋值句产生的三地址代码为： T1:=i int* j T3:=inttoreal T1 T2:=y real+ T3 x:=T2,关于产生式EE1 E2 的语义动作, E.place:=newtemp; if E1.type=integer and E2.type=integer then begin emit (E.place := E 1.place int+ E 2.place); E.type:=integer end e

23、lse if E1.type=real and E2.type=real then begin emit (E.place := E 1.place real+ E 2.place); E.type:=real end,else if E1.type=integer and E2.type=real then begin u:=newtemp; emit (u := inttoreal E 1.place); emit (E.place := u real+ E 2.palce); E.type:=real end else if E1.type=real and E1.type=intege

24、r then begin u:=newtemp; emit (u := inttoreal E 2.place); emit (E.place := E 1.place real+ u); E.type:=real end else E.type:=type_error,7.3.3 记录中域的引用,符号表表项之中保存记录中的域的类型和相对地址信息,7.4 布尔表达式的翻译,布尔表达式的两个基本作用: 用于逻辑演算,计算逻辑值; 用于控制语句的条件式. 产生布尔表达式的文法: EE or E | E andE | E | (E) | i rop i | i,计算布尔表达式通常采用两种方法: 1.

25、 如同计算算术表达式一样,一步步算 1 or (not 0 and 0) or 0 =1 or (1 and 0) or 0 =1 or 0 or 0 =1 or 0 =1 2. 采用某种优化措施 把A or B解释成 if A then true else B 把A and B解释成 if A then B else false 把 A解释成 if A then false else true,两种不同的翻译方法: 第一种翻译法： A or B and C=D翻译成 (1) (=, C, D, T1) (2) (and, B, T1, T2) (3) (or, A, T2, T3) 第二种翻

26、译法适合于作为条件表达式的布尔表达式使用.,7.4.1 数值表示法,a or b and not c 翻译成 T1:=not c T2:=b and T1 T3:=a or T1 ab的关系表达式可等价地写成 if ab then 1 else 0 ，翻译成 100:if ab goto 103 101:T:=0 102:goto 104 103:T:=1 104:,关于布尔表达式的数值表示法的翻译模式,过程emit将三地址代码送到输出文件中 nextstat给出输出序列中下一条三地址语句的地址索引 每产生一条三地址语句后，过程emit便把nextstat加1,关于布尔表达式的数值表示法的翻译

27、模式,EE1 or E2 E.place:=newtemp; emit(E.place := E 1.place or E2.place) EE1 and E2 E.place:=newtemp; emit(E.place := E 1.place and E2.place) Enot E1 E.place:=newtemp; emit(E.place := not E 1.place) E(E1) E.place:=E1.place,关于布尔表达式的数值表示法的翻译模式,Eid1 relop id2 E.place:=newtemp; emit(if id1.place relop. op

28、id2. place goto nextstat+3); emit(E.place := 0); emit(goto nextstat+2); emit(E.place:= 1) Eid E.place:=id.place ,ab 翻译成 100:if ab goto 103 101:T:=0 102:goto 104 103:T:=1 104:,布尔表达式ab or cd and ef的翻译结果,100:if ab goto 103 101:T1:=0 102:goto 104 103:T1:=1 104:if cd goto 107 105:T2:=0 106:goto 108 107:

29、T2:=1 108: if ef goto 111 109: T3:=0 110: goto 112 111: T3:=1 112: T4:=T2 and T3 113: T5:=T1 or T4,Eid1 relop id2 E.place:=newtemp; emit(if id1.place relop. op id2. place goto nextstat+3); emit(E.place := 0); emit(goto nextstat+2); emit(E.place:= 1) Eid E.place:=id.place EE1 or E2 E.place:=newtemp;

30、emit(E.place := E 1.place or E2.place) EE1 and E2 E.place:=newtemp; emit(E.place := E 1.place and E2.place) ,7.4.2 作为条件控制的布尔式翻译,条件语句 if E then S1 else S2 赋予 E 两种出口:一真一假,E.code,S1.code,S2.code,To E.true,To E.false,goto S.next,S.next,E.true:,E.false:,例：把语句: if ac or b c goto L2 “真”出口 goto L1 L1:if bd

31、goto L2 “真”出口 goto L3 “假”出口 L2:(关于S1的三地址代码序列) goto Lnext L3:(关于S2的三地址代码序列) Lnext:,每次调用函数newlabel后都返回一个新的符号标号 对于一个布尔表达式E，引用两个标号 E.true是E为真时控制流转向的标号 E.false是E为假时控制流转向的标号,产生布尔表达式三地址代码的语义规则,产生式语义规则 EE1 or E2 E1.true:=E.true; E1.false:=newlabel; E2.true:=E.true; E2.false:=E.false; E.code:=E1.code | gen(E

32、1.false :) | E2.code,产生布尔表达式三地址代码的语义规则,产生式语义规则 EE1 and E2 E1.true:=newlabel; E1.false:=E.false; E2.true:=E.true; E2.false:=E.fasle; E.code:=E1.code | gen(E1.true :) | E2.code,产生布尔表达式三地址代码的语义规则,产生式语义规则 Enot E1 E1.true:=E.false; E1.false:=E.true; E.code:=E1.code E (E1) E1.true:=E.true; E1.false:=E.fal

33、se; E.code:=E1.code,产生布尔表达式三地址代码的语义规则,产生式语义规则 Eid1 relop id2 E.code:=gen(if id1.place relop.op id2.place goto E.true) | gen(goto E.false) Etrue E.code:=gen(goto E.true) Efalse E.code:=gen(goto E.false),考虑如下表达式： ab or cd and ef假定整个表达式的真假出口已分别置为Ltrue和Lfalse，则按定义将生成如下的代码：,if ab goto Ltrue goto L1 L1:if

34、 cd goto L2 goto Lfalse L2:if ef goto Ltrue goto Lfalse,布尔表达式的翻译,两遍扫描 为给定的输入串构造一棵语法树； 对语法树进行深度优先遍历，进行语义规则中规定的翻译。 一遍扫描,一遍扫描实现布尔表达式的翻译,采用四元式形式 把四元式存入一个数组中，数组下标就代表四元式的标号 约定 四元式(jnz, a, -, p) 表示 if a goto p 四元式(jrop, x, y, p)表示 if x rop y goto p 四元式(j, -, -, p) 表示 goto p,有时,四元式转移地址无法立即知道,我们只好把这个未完成的四元式地

35、址作为E的语义值保存,待机回填。,为非终结符E赋予两个综合属性E.truelist和E.falselist。它们分别记录布尔表达式E所应的四元式中需回填“真”、“假”出口的四元式的标号所构成的链表 例如:假定E的四元式中需要回填真出口的p，q，r三个四元式，则E.truelist为下列链: (p) (x， x，x，0) (q) (x，x，x，p) (r) (x，x，x，q),链尾,E. truelist =r,为了处理E.truelist和E.falselist ，引入下列语义变量和过程: 变量nextquad，它指向下一条将要产生但尚未形成的四元式的地址(标号)。nextquad的初值为1，

36、每当执行一次emit之后，nextquad将自动增1。 函数makelist(i)，它将创建一个仅含i的新链表，其中i是四元式数组的一个下标(标号)；函数返回指向这个链的指针。 函数merge(p1,p2)，把以p1和p2为链首的两条链合并为一，作为函数值，回送合并后的链首。 过程backpatch(p, t)，其功能是完成“回填”，把p所链接的每个四元式的第四区段都填为t。,布尔表达式的文法,(1) EE1 or M E2 (2) | E1 and M E2 (3) | not E1 (4) | (E1) (5) | id1 relop id2 (6) | id (7)M,布尔表达式的翻译模

37、式,(7) M M.quad:=nextquad ,布尔表达式的翻译模式,(1) EE1 or M E2 backpatch(E1.falselist, M.quad); E.truelist:=merge(E1.truelist, E2.truelist); E.falselist:=E2.falselist (2) EE1 and M E2 backpatch(E1.truelist, M.quad); E.truelist:=E2.truelist; E.falselist:=merge(E1.falselist,E2.falselist) ,布尔表达式的翻译模式,(3) Enot E1

38、 E.truelist:=E1.falselist; E.falselist:=E1.truelist (4) E(E1) E.truelist:=E1.truelist; E.falselist:=E1. falselist,布尔表达式的翻译模式,(5) Eid1 relop id2 E.truelist:=makelist(nextquad); E.falselist:=makelist(nextquad+1); emit(j relop.op , id 1.place , id 2.place,0); emit(j, , , 0) (6) Eid E.truelist:=makelist

39、(nextquad); E.falselist:=makelist(nextquad+1); emit(jnz , id .place , ,0)； emit( j, -, -, 0) ,布尔表达式的翻译模式,作为整个布尔表达式的真假出口(转移目标)仍待回填.,利用翻译方案翻译布尔表达式 ab or cd and ef,E,E,E,a b,c d,e f,or,M,E,and,M,E,.t=100 .f=101,100：if ab goto 101：goto ,.q=102,.t=102 .f=103,102：if cd goto 103：goto ,.q=104,.t=104 .f=105,

40、104：if ef goto 105：goto ,104,.t=104 .f=103, 105,102,.t=100, 104 .f=103, 105,假定变量nextquad的初值为100,ab or cd and ef,100(j, a, b, 0) 101(j, -, -, 102) 102(j, c, d, 104) 103(j, -, -, 0) 104(j, e, f, 100) truelist 105(j, -, -, 103) falselist,7.5 控制语句的翻译,考虑下列产生式所定义的语句 S if E then S1 | if E then S1 else S2 |

41、 while E do S1 其中E为布尔表达式。,if-then语句 S if E then S1,E.code,S1.code,To E.true,To E.false,E.true:,E.false:,if-then语句的属性文法,产生式语义规则 Sif E then S1 E.true:=newlabel; E.flase:=S.next; S1.next:=S.next S.code:=E.code | gen(E.true :) | S1.code,if-then-else语句 S if E then S1 else S2,E.code,S1.code,S2.code,To E.t

42、rue,To E.false,goto S.next,S.next,E.true:,E.false:,if-then-else语句的属性文法,产生式 语义规则 Sif E then S1 else S2 E.true:=newlabel; E.false:=newlabel; S1.next:=S.next S2.next:=S.next; S.code:=E.code | gen(E.true :) | S1.code | gen(goto S.next) | gen(E.false :) | S2.code,while-do语句 S while E do S1,E.code,S1.code

43、,To E.true,To E.false,goto S.begin,S.begin:,E.true:,E.false:,while-do语句的属性文法,产生式语义规则 Swhile E do S1S.begin:=newlabel; E.true:=newlabel; E.false:=S.next; S1.next:=S.begin; S.code:=gen(S.begin :) | E.code | gen(E.true :) | S1.code | gen(goto S.begin),考虑如下语句 :while ab doif cd thenx:=y+z else x:=y-z,生成下

44、列代码： L1:if ab goto L2 goto Lnext L2:if cd goto L3 goto L4 L3:T1:=y+z x:=T1 goto L1 L4:T2:=y-z x:=T2 goto L1 Lnext:,一遍扫描翻译控制流语句,考虑下列产生式所定义的语句: (1) Sif E then S (2) | if E then S else S (3) | while E do S (4) | begin L end (5) | A (6) LL;S (7) | S S表示语句， L表示语句表， A为赋值语句，E为一个布尔表达式,if 语句的翻译 相关产生式 S if E

45、then S(1) | if E then S(1) else S(2) 改写后产生式 S if E then M S1 S if E then M1 S1 N else M2 S2 M N,翻译模式: 1. Sif E then M S1 backpatch(E.truelist, M.quad); S.nextlist:=merge(E.falselist, S1.nextlist) 2. Sif E then M1 S1 N else M2 S2 backpatch(E.truelist, M1.quad); backpatch(E.falselist, M2.quad); S.next

46、list:=merge(S1.nextlist, N.nextlist, S2.nextlist) 3. M M.quad:=nextquad 4. N N.nextlist:=makelist(nextquad); emit(j,) ,while 语句的翻译 相关产生式 S while E do S(1) 翻译为：,E的代码,S (1)的代码,“真”出口,“假”出口,为了便于回填，改写产生式为: Swhile M1 E do M2 S1 M,翻译模式: 1. Swhile M1 E do M2 S1 backpatch(S1.nextlist, M1.quad); backpatch(E.t

47、ruelist, M2.quad); S.nextlist:=E.falselist emit(j, M1.quad) 2. M M.quad:=nextquad ,产生式 LL;S 改写为： LL1; M S M,翻译模式: 1. LL1; M S backpatch(L1.nextlist, M.quad); L.nextlist:=S.nextlist 2. M M.quad:=nextquad ,其它几个语句的翻译 1. Sbegin L end S.nextlist:=L.nextlist 2. SA S.nextlist:=makelist( ) 3. LS L.nextlist:

48、=S.nextlist ,A1的代码,例：,if ab or cd and ef then A1 else A2; while ab do A3,if 语句的代码,while 语句的代码,E的代码,A1的代码,A2的代码,E的代码,A3的代码,100：if ab goto 101：goto 102 102：if cd goto 104 103：goto 104：if ef goto 105：goto ,127：if ab goto 128：goto ,106： . 115：,116：goto ,117： . 126：,A2的代码,106,106,117,117,129： . 138：,A3的代

49、码,129,139：goto 127,127,.n=116,翻译语句while (ab) doif (cd) then x:=y+z;,P190 (5) Eid1 relop id2 E.truelist:=makelist(nextquad); E.falselist:=makelist(nextquad+1); emit(j relop.op , id 1.place , id 2.place,0); emit(j, , , 0) ,P179 Sid:=E p:=lookup(id.name); if pnil then emit(p := E.place) else error EE1+

50、E2 E.place:=newtemp; emit(E.place := E1.place + E2.place),P195 Sif E then M S1 backpatch(E.truelist, M.quad); S.nextlist:=merge(E.falselist, S1.nextlist) M M.quad:=nextquad SA S.nextlist:=makelist( ) ,P195 Swhile M1 E do M2 S1 backpatch(S1.nextlist, M1.quad); backpatch(E.truelist, M2.quad); S.nextli

51、st:=E.falselist emit(j, M1.quad) M M.quad:=nextquad ,翻译语句while (ab) doif (cd) then x:=y+z;,100(j, a, b, 102) 101(j, -, -, 107) 102(j, c, d, 104) 103(j, -, -, 100) 104(+, y, z, T) 105(:=, T, -, x) 106 (j, -, -, 100) 107,7.5.2 标号与goto语句,标号定义形式 L: S； 标号引用 goto L； 示例：,向后转移： L1: goto L1;,向前转移： goto L1; L

52、1: ,符号表信息,(P) (j, -, -, 0) (q) (j, -, -, p) (r) (j, -, -, q),已,未,产生式Sgoto L的语义动作: 查找符号表； IF L在符号表中且定义否栏为已 THEN GEN(J，-，-，P) ELSE IF L不在符号表中 THEN BEGIN 把L填入表中； 置定义否为未，地址栏为NXQ； GEN(J，-，-，0) END ELSE BEGIN Q:=L的地址栏中的编号； 置地址栏编号为NXQ； GEN(J，-，-，Q) END ,带标号语句的产生式: Slabel S label i: label i: 对应的语义动作: 1. 若i所

53、指的标识符(假定为L)不在符号表中，则把它填入，置类型为标号，定义否为已，地址为nextquad ； 2. 若L已在符号表中但类型不为标号或定义否为已，则报告出错； 3. 若L已在符号表中，则把标号未改为已，然后，把地址栏中的链头(记为q)取出，同时把nextquad填在其中，最后，执行BACKPATCH(q，nextquad )。,7.5.3 CASE语句的翻译,语句结构 case E of C1:S1; C2:S2; Cn-1:Sn-1; otherwise:Sn end,翻译法(一): T:=E L1:if TC1 goto L2 S1的代码 goto next L2:if TC2 go

54、to L3 S2的代码 goto next L3: Ln-1:if TCn-1 goto Ln Sn-1的代码 goto next Ln:Sn的代码 next:,改进:,翻译法(二): 计算E并放入T中 goto test L1:关于S1的中间码 goto next Ln-1:关于Sn-1的中间码 goto next Ln:关于Sn的中间码 goto next test:if T=C1 goto L1 if T=C2 goto L2 if T=Cn-1 goto Ln-1 goto Ln next:,(case, C1, P1) (case, C2, P2) (case, Cn-1, Pn-1

55、) (case, T, Pn) (label, NEXT, -, -),Pi是Li在 符号表中 的位置,7.6 过程调用的处理,过程调用主要对应两种事: 传递参数 转子,传地址:把实在参数的地址传递给相应的形式参数 调用段预先把实在参数的地址传递到被调用段可以拿到的地方； 程序控制转入被调用段之后，被调用段首先把实在参数的地址抄进自己相应的形式单元中； 过程体对形式参数的引用域赋值被处理成对形式单元的间接访问。,翻译方法：把实参的地址逐一放在转子指令的前面. 例如， CALL S(A，X+Y) 翻译为: 计算X+Y置于T中的代码 par A /*第一个参数的地址*/ par T /*第二个参数

56、的地址*/ call S /*转子*/,过程调用的翻译,过程调用文法: (1) S call id (Elist) (2) Elist Elist, E (3) Elist E 参数的地址存放在一个队列中 最后对队列队列中的每一项生成一条par语句,翻译模式 3. ElistE 初始化queue仅包含E.place 2. ElistElist, E 将E.place加入到queue的队尾 1. Scall id (Elist) for 队列queue中的每一项p do emit(param p); emit(call id.place) ,作业,P217-1，3 ，4 ，5 ，6 ，7 ，12,