【人工智能_编译new】第六章语法制导翻译和中间代码生成4.0.ppt

《【人工智能_编译new】第六章语法制导翻译和中间代码生成4.0.ppt》由会员分享，可在线阅读，更多相关《【人工智能_编译new】第六章语法制导翻译和中间代码生成4.0.ppt（119页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第6章 本章内容,语法制导翻译 逆波兰表示法 三元式和树 四元式 简单算术表达式和赋值句到四元式的翻译 布尔表达式到四元式的翻译 控制语句的翻译 数组元素的引用 过程调用 说明语句的翻译 自上而下分析制导翻译概说,在语法分析过程中，随着分析的步步进展，根据每个产生式所对应的语义子程序（语义动作）进行翻译（产生中间代码）的办法。,概念,6.1 语法制导翻译概说,标记说明,描述语义动作时，需要赋予每个文法符号X（终结符或者 非终结符）以种种不同方面的值，如X.TYPE(类型），X.VAL(值）等。 一个产生式中同一符号多次出现，用上角标来区分。 E E + E 表示为 E E(1) + E(2)

2、每个产生式的语义动作，写在该产生式之后的花括号 内。,文法符号，无须进栈，让其进栈只是为了醒目。,需要保存的某些语义信息。,实际上为一个指示器，指向分析表的某一行。,语法制导的一个具体实现,先对LR分析器的栈作一些改进，加入语义值。,STATE,VAL,SYM,TOP,文法及其语义动作,(0)S E print E.VAL (1)EE(1)+E(2) E.VAL:=E(1).VAL+E(2).VAL (2)EE(1)*E(2) E.VAL:=E(1).VAL*E(2).VAL (3)E(E(1) E.VAL:=E(1).VAL (4)En E.VAL:=LEXVAL,上述的语义动作等于给出了计

3、算由、*组成的整数算术式的过程。其相应的程序段如下：,(0)S E print VALTOP (1)EE(1)+E(2) VALTOP:=VALTOP+VALTOP+2 (2)EE(1)*E(2) VALTOP:=VALTOP*VALTOP+2 (3)E(E(1) VALTOP:=VALTOP+1 (4)En VALTOP:=LEXVAL,若把语义动作改为产生中间代码的动作，就能随着分析的进展逐步生成中间代码。,大部分的编译器都不直接产生目标代码，虽然这是可以实现的，但是产生的代码不是最优的。因为这涉及到寄存器的分配问题，在语义分析阶段，很难有效地分配它们。,中间代码的必要性,波兰逻辑学家卢卡

4、西维奇（Lukasiewicz）发明的一种表示法。,一般，若e1,e2为任意的后缀表达式， 为任意双目运算符，则用作用于e1和e2所代表的结果用后缀式e1e2 表示。 推而广之， 为k目运算符，则作用于e1e2ek的结果用e1e2ek 来表示。,概念,6.2 逆波兰表示法,a * ( b + c ) abc+* (a + b)*(c + d) ab + cd +* 若用？表示if-then-else,则 If a then if c-d then a+c else a*c else a+b a cd- ac+ ac*? ab+?,示例,后缀式求值,使用一个栈（软件栈或者硬件栈）来求值。 求值过

5、程： 从左到右扫描后缀式，每碰到运算量就把它推进栈，每碰到k目运算符就把它作用于栈顶的k个项，并用运算结果来代替这k个项。,ab+c*的求值（a=1,b=3,c=5),a进栈,1,3,+,5,*,b进栈,ab相加，移去两项，和置于栈顶,4,3+1=,c进栈,栈顶两项相乘，移去两项，积置于栈顶,5*4=,20,计算完毕，结果为20,后缀式的控制流,前面讲到，if-then-else运算符的实现”exy?” e不等于0，取x，否则取y. 这种表示法要求在任何情况下都要把x,y都计算出来，尽管只用到其中一个。而且，如果运算量无定义或者有副作用，则后缀表示法不仅无效，而且可能是错误的。,解决方案,引入

6、标号，在后缀式中加入条件转移，无条件转移算符。,存储方式 后缀式存放在一维数组POST1.N中，每个元素是运算符或者分量（指向符号表）。,p jump 转到POSTp e1e2pjlt e1e2时，转到POSTp e p jez 若e=0,转到POSTp,If e then x else y e p1 jez x p2 jump p1:y p2:,转移算符,在数组POST中出现的后缀式,e,p1,jez,x,p2,jump,y,p1,p2,下标,数组,符号表,e,x,y,后跟冒号的p1,p2实际上并不存储,语法制导生成后缀式,产生式所带的语义动作，由以下模式描述。,E E(1)op E(2)

7、E.CODE:= E(1).CODE|E(2).CODE|op/print op E (E(1) E.CODE := E(1).CODE / E id E.CODE := id /print id,Ea,a+b*c的翻译,a,+,b,*,c,a,b,c,*,+,移进a,输出,输入,用Eid归约，print a,移进+,移进b,用Eid归约， print b,Eb,移进*,移进c,用Eid归约，print c,Ec,用EE op E归约，print *,E1,用EE op E归约，print +,结束，结果为abc*+,E,三元式的构成： OP ARG1 ARG2 ARG1和ARG2都是指示器，

8、指向符号表的某项，或者三元式表自身的某项。OP通常用整数编码。,X := A + B * C的三元式 (1） * B C + A (1) := X (2),6.3 三元式和树,语法制导生成三元式的语义动作,EE(1) op E(2) := TRIP(op,E(1).VAL,E(2).VAL (2) E(E(1) E.VAL:= E(1).VAL (3) E-E(1) E.VAL:= (,E(1).VAL,- (4) Eid E.VAL:= (id),指示器，指向符号表中某一项，或者三元式表中某一项,语义过程，产生新的三元式，回送新三元式在三元式表中的位置,对id代表的标示符查找符号表以获知在表

9、中的位置的函数过程。,E.VAL,TRIP,ENTRY,两个语义过程,LOOKUP(NAME):对NAME查符号表。查到则返回入口值，否则返回NULL.(出错处理，调用FILLSYM) FILLSYM(NAME):在符号表中开辟新项目，返回入口值。,问题,三元式中指示器连接，不能更动，不利于优化。,间接三元式,用一张间接码表辅以三元式表来表示中间代码。,X:=(A+B)*C Y:=D(A+B),(1) (2) (3) (1) (4) (5),间接码表,间接码表体现了顺序次序。在代码优化需要调整顺序的时候，只需要重新安排间接码表，无需改动三元式表。同时，相同的三元式无需重复填入三元式表。,语义动

10、作,对于间接三元式表示，产生三元式表时，应增添产生间接码表的语义动作。并且，在向三元式表填进一个三元式之前，必须先查看一下此式是否已在其中，如已在其中，就无需再填如。,树,用树形结构来表示一个表达式或者语句。,简单变量或者常数的树就是该变量或者常数自身。一般叶子表示运算量，内结点表示OP。如e1和e2的树为T1和T2,那么，e1+e2、e1*e2和-e1的树分别为：,例,A*(B+C)/D,A,*,(,B,+,C,),/,D,E,E,E,E,E,E,规约过程,树,B,A,C,*,+,/,D,E,语法制导产生树,E E(1) OP E(2) E.VAL:= (OP,E(1).VAL,E(2).V

11、AL) (2)E(E(1) E.VAL:= E(1).VAL (3)E-E(1) E.VAL := (,E(1).VAL) (4)Ei E.VAL:= (i) ,函数过程，建立一个以OP为结点，E(1).VAL和E(2).VAL为左右枝的子树，回送新子树根的指针,NODE,UNARY,LEAF,与NODE相仿，但是它只有一个分枝。,函数过程，建立一个以i.LEXVAL为标志的结，并回送此结的地址，该结是个端末结（叶结）。,OP ARG1 ARG2 RESULT 运算量和运算结果有时指用户自定义的变量，有时指编译程序引进的临时变量。如果OP是算术或者逻辑算符，则RESULT总是一个新引进的临时变

12、量，存放中间结果。不加限制地使用临时变量，在优化时压缩。,OP:算符的整数码 ARG和RESULT:符号表入口或者临时变量的整数码 RESULT为Ti时的处理：可以填入符号表，通过符号表入口进行引用，也可以不填，用某种整数编码代表它们。,6.4 四元式,A:=-B*(C+D)的四元式 B _ T1 + C D T2 * T1 T2 T3 := T3 _ A,三元式和四元式的差异是表示式中有多少间接表示的问题。 三元式对于结果用指示器指向式子表示。 四元式使用临时变量，计算和使用的联系不那么直接了，允许重排顺序，利于优化。,下面要讨论的是只含整型变量的简单赋值句的翻译。它的文法描述： Ai:=E

13、 EE+E|E*E|-E|(E)|i (6.1) 非终结符A代表“赋值句”。该文法是一二义性文法，但接受通常对于算符的结合性和优先级的规定，可以克服。,6.5 简单算数表达式和赋值句到四元式的翻译,NEWTEMP: 函数过程。每次调用时，它都回送一个代表新临时变量名的整数码作为函数值。 ENTRY(i）：函数过程 E.PLACE: 和非终结符E相联系的语义变量，表示存放E值的变量名在符号表的入口或者整数码（若为临时变量）。 GEN(OP,ARG1,ARG2,RESULT): 语义过程，把四元式（OP,ARG1,ARG2,RESULT)填入四元式表。,几个语义变量和过程,翻译算法的语义动作描述,

14、Ai:=E GEN(:=, E.PLACE, _, ENTRY(i) EE(1)+E(2) E.PLACE:=NEWTEMP; GEN(+, E(1).PLACE, E(2).PLACE, E.PLACE) (3) EE(1)*E(2) E.PLACE:=NEWTEMP; GEN(*, E(1).PLACE, E(2).PLACE, E.PLACE) (4)E-E(1) E.PLACE:=NEWTEMP; GEN(, E(1).PLACE, _, E.PLACE) (5)E(E(1) E.PLACE:=E(1).PLACE (6)Ei E.PLACE:= ENTRY(i) ,示例,输入,栈,P

15、LACE,四元式,A:=-B*(C+D),-B*(C+D),B*(C+D),*(C+D),*(C+D),i:=,i:=-,i:=-i,i:=-E,i:=E,i:=E*,i:=E*(,i:=E*(i,i:=E*(E,i:=E*(E+,i:=E*(E+i,i:=E*(E+E,*(C+D),(C+D),C+D),+D),+D),D),),),),i:=E*(E,i:=E*(E),i:=E*E,i:=E,A,A_,A_,A_B,A_B,A_T1,A_T1_,A_T1_,A_T1_C,A_T1_C,A_T1_C_,A_T1_C_D,A_T1_C_D,A_T1_T2,A_T_T2_,A_T1_T2,A_T

16、3,(, B, _, T1),(+, C, D, T2),(*, T1, T2, T3),(:=, T3, _, A),类型转换,前面假定了所有i都是整型，实际上，在一个表达式中可能出现各种不同类型的变量和常数。编译程序后者拒绝混合运算，或者产生有关类型转换的指令。,例如：令文法5.1允许混合类型。 那么，在进行混合运算时，首先要将整型量转换为实型量。而要进行转换，其前提是对每一VN，必须有类型信息语义量E.MODE。 因此，对应的产生式要附加关于E.MODE的语义规则。,语义规则： IF E(1).MODE = int AND E(2).MODE = int THEN E.MODE := i

17、nt ELSE E.MODE := r,语义动作的增加，意味着语义子程序的修改，必要时能够产生对运算量进行类型转换的四元式。 ( itr, A1, _, T) 将整型量A1转换成实型量。,示例,输入串为 X := Y + I * J X,Y为实型，I,J 为整型。,四元式： ( *i, I , J , T1) ( itr , T1, _ , T2) ( +r, Y , T2 , T3) ( :=, T3 , _ , X),运算符要指出相称的类型，说明是定点还是浮点运算,*i,关于产生式 E E(1) op E(2),在上述语法规则中，非终结符E的语义值E.MODE必须保存在翻译栈中。 如果运算

18、量类型增多，语义子程序必须区别的情形很快增多，从而使语义子程序累赘不堪。,6.6 布尔表达式到四元式的翻译,布尔表达式(E)是由布尔算符(,)作用于布尔变量或关系表达式而形成的。,形式 E1 rop E2,rop是关系符，E1和E2是算术式。,文法： EEE|EE|E|(E)|i|i rop i,设定 布尔算符的优先顺序：，。 ，服从左结合。所有关系符的优先级相同，高于任何布尔算符，低于任何算术算符。,关系符不得结合，如 ABC不合法。,布尔表达式(E)在语言中的用途,求值 X:=ABD 条件控制 WHILE ABD DO S IF ABD THEN S1 ELSE S2,布尔表达式的求值,1

19、 通常算法，如同算术表达式求值一样，一步步地计算各部分的值，进而计算出整个表达式的值。,2 采用优化措施 AB if A then true else B AB if A then B else false A if A then false else true,说明 上述两种计算方法对于不包含布尔函数调用的式子是没有什么差别的。仅当遇到布尔函数调用，并且这种函数调用引起副作用时，上述两种算法不等价。,对于第一种方法而言，可以如同翻译算术表达式一样来翻译布尔表达式。,ABC=D 翻译成 = C D T1 B T1 T2 A T2 T3,第二种方法是本节主要内容，下面将详细讨论。,本节内容,一.

20、IF语句的四元式结构 二.翻译的困难和解决办法 三.E的文法和语义子程序 四.例,例 IF ABD THEN S1 ELSE S2,E的结构 从整体上，E对外只能转向两个目标,E,转向E为假时的目标,转向E为真时的目标,(1) (jnz,A,_,5) (2) (j,_,_,3) (3) (j,B,D,5) (4) (j,_,_,p+1),(5) (p) (p+1) (q),S1,(j,_,_,q),S2,下一语句,一.IF语句的四元式结构,1.困难,转移的目标在对它的应用之后才出现； (j,_,_,0),E可以很复杂，上面的情况可以频繁出现,二.翻译的困难和解决办法,(1) (jnz,A,_,

21、5) (2) (j,_,_,3) (3) (j,B,D,5) (4) (j,_,_,p+1),(5) (p) (p+1) (q),S1,(j,_,_,q),S2,下一语句,二.翻译的困难和解决办法,p( ) . . . q( ) . . . r( ) . . . t( ),p,q,r,Q.front,2.解决办法,一般地讨论：凡是先有目标应用的出现，后有目 标的定义，如何处理？,设p、q、r三条四元式均要转向t四元式,(1)队列法,Q.rear,p,(2)拉链-返填法,p(_,_,_,0),. . q(_,_,_,_),q,. . q(_,_,_,p),. . r(_,_,_,_),r,. .

22、 r(_,_,_,q),. . t(_,_,_,_),(2)拉链-返填法,p(_,_,_,0),. . q(_,_,_,p),. . q(_,_,_,t),. . r(_,_,_,q),r,. . r(_,_,_,t),. . t(_,_,_,_),q,p,p(_,_,_,t),q,p,拉链法应用到布尔表达式翻译,L1( ( L2( L3( . . L4( . . L5( . . Li( . . Lj( . . Ln(,Li,E.TC,Ln,E.FC,) ) ) ) ) ) ) ) ),0,0,0,0,0,0,0,0,L5,L2,L1,Lj,L4,L3,0,0,1.文法定义 G1 E-EEEE

23、|E|(E)|i|i rop i,G2 E-EE|EE|E|(E)|i|i rop i E-E E-E,三. 布尔表达式文法定义及语义动作,2.语义动作,用自下而上语法分析方法，语法制导生成ABD的四元式,四.例,6.7 控制语句的翻译,本小节讨论无条件和条件语句的翻译，只讨论四元式的产生。,本节内容 标号和转移语句 条件语句 分叉语句,6.7.1 标号和转移语句,标号的两种使用方法 L: S Goto L 语言中允许标号先定义后使用，也允许先使用后定义。,(1) 先定义,遇到L1 : S1,符号表,遇到Goto L1,(2) 先使用,q1 goto L2 q2 Goto L2 q3 L2 :

24、 S2,遇到goto L2, 填符号表，“未定义”，把NXQ填入L2的地址部分，作为链头。产生( j, _, _, 0),q1 (j, _, _, 0 ),遇到goto L2, 查到未定义，取符号表中L2的地址q1填入四元式q2:(j, _, _,q1),将q2填入符号表。, ,q2 (j, _, _, q1 ),q2,遇到L2:S2,就可以回填。,q3,q3,q3,一般而言，带标号语句产生式 S label S label i: Label i: 的语义动作,1. 若i所指的标识符(假定为L)不在符号表中，则把它填入，置类型为“标号”，“定义否”为“已”，地址为NXQ。,2, 若 L已在符号

25、表中，但“类型”不为“标号”或者“定义否”为“已”，则报告出错。,3. 若L已在符号表中，则把标志“未”改为“已”，然后，把地址栏中的链头(记为q)取出，同时把NXQ填在其中，最后，执行BACKPATCH(q,NXQ)。,6.7.2 条件语句,1 较为复杂的程序控制语句常常是嵌套的。,S1后有一条无条件转移指令，跳转到本语句之后。这里，与上一节不同的是，在S2翻译之后，也不能确定其跳转地址，它要跨越S2,S3。 所以，转移地址的确定与语句所处的环境有关。,if E1 THEN,if E2 then S1 else S2,ELSE S3,解决办法 令每个非终结符S(L)附带一项语义值S.CHAI

26、N，它指出一条链的头，该链是所有期待翻译完S后回填目标的四元式组成的。,注意 回填目标可能是S得下一条四元式，也可能不是。真正的回填，要在处理完S的外层后进行。,考虑语句 WHILE E(1) DO S(1) 译为代码结构,由于语句的嵌套，WHILE翻译完了也未必知道假出口的转移目标，所以作为S(1).CHAIN保留下来,以便伺机回填。,While E(1) do S(1),IF E THEN,ELSE S,示例,文法,S if E then S |if E the S else S |while E do S |begin L end |A L L; S |S (6.5) S语句 L语句串

27、A赋值句 E布尔表达式,为了能及时回填有关四元式的转移目标，如同处理布尔表达式一样，需要对文法(6.5)进行改写。,S C S | TP S | Wd S | begin L end | A L LS S,| S C if E then TP CS else Wd W E do W while LS L; (6.6),语义动作,C if E then BACKPATCH (E.TC, NXQ); C.CHAIN := E.FC S C S(1) S.CHAIN := MERG(C.CHAIN, S(1).CHAIN TP C S(1) else q := NXQ; GEN(j, _, _, 0

28、); BACKPATCH(C.CHAIN,NXQ); TP.CHAIN := MERGE(S(1).CHAIN,q) S TP S(2) S.CHIAN := MERG(TP.CHIAN, S(2).CHIAN,语义动作,W while W.QUAD := NXQ Wd W E do BACKPATCH (E.TC,NXQ); Wd.CHAIN := E.FC; Wd.QUAD := W.QUAD S Wd S(1) BACHPATCH(S(1).CHAIN,Wd.QUAD); GEN(j, _, _, Wd.QUAD); S.CHAIN := Wd.CHAIN,语义动作,L S L.CHAI

29、N := S.CHAIN LS L; BACKPATCH(L.CHAIN,NXQ) L LS S(1) L.CHAIN := S(1).CHAIN S begin L end S.CHAIN := L.CHAIN S A S.CHAIN := 0 空链,IF E THEN S(1) ELSE S(2),C,TP,S,示例,E,S(1)的代码,S(2)的代码,S(2).CHAIN,C IF E THEN,TP C S(1) ELSE,S TP S(2),IF E THEN WHILE E(1) DO S(1) ELSE S(2) 的示意图,IF,THEN,WHILE,C IF E THEN BA

30、CKPATCH(E.TC,NXQ); C.CHAIN := E.FC ,W WHILE W.QUAD := NXQ,Wd W E(1) DO BACKPATCH(E(1).TC,NXQ); Wd.CHAIN := E(1).FC Wd.quad := W.QUAD ,S1 Wd S(1) BACKPATCH(S(1).C,Wd.Q); GEN(j,_,_,Wd.Q); S1.C := Wd.C ,TP C S1 ELSE q := NXQ; GEN(j,_,_,0); BACKPATCH(C.CH,NXQ); TP.C:=MERG(S1.C,q); ,ELSE,S TP S(2) S.CH :

31、= MERG(TP.CH,S(2).CH) ,语句翻译完成，结果如图所示,例子,104 (+,Y, Z, T),WWHILE W.QUAD := NXQ,W.QUAD:=100,E(1) i(1) rop i(2) E(1).TC:=NXQ;E(1).FC:=NXQ+1; GEN(jrop,ENTRY(i(1),ENTRY(i(2),0); GEN(j,_,_,0);,Wd W E(1) DO BACKPATCH(E(1).TC,NXQ); Wd.CHAIN := E(1).FC; Wd.QUAD :=W.QUAD,E(2)i(1) rop i(2) E(2).TC:=NXQ;E(2).FC:

32、=NXQ+1; GEN(jrop,ENTRY(i(1),ENTRY(i(2),0); GEN(j,_,_,0);,C IF E(2) THEN BACKPATCH(E(2).TC,NXQ); C.CHAIN :=E(2).FC,E i(1)+i(2) E.PLACE := NEWTEMP; GEN(+,ENTRY(i(1),ENTRY(i(2),E.PALCE),A i:=E GEN(:=,E.PALCE,_,ENTRY(i),105 (:=,T,_, X),S(2) C S(1) S(2).CHAIN := MERG(C.CHAIN,S(1).CHAIN) ,S Wd S(2) BACKPA

33、TCH(S(2).CHAIN,Wd.QUAD); GEN(j,_,_,Wd.QUAD); S.CHAIN := Wd.CHAIN ,While AB DO if CD then X:= Y+Z 语句翻译完成,控制语句的翻译,1 设计属性文法，讨论翻译的一般语义规则。,1 产生标志，被转目标，在S.code中出现 S.Begin := newlabel E.True := newlabel,如 S while E do S1 的语义规则包含四部分：,E.CODE,S1.CODE,Goto S.begin,S.begin,E.t,E.f,2 “内部的”/可隐藏标志用 S.Next及两标志表示。 /

34、S.next构成 E.F := S.next S1.next := S.begin,3 S.code 的组成 S.code := gen(S.begin :)| E.code| gen(S.true :)| S1.code | gen (goto S.begin),4 对1，2归纳，可知转移目标有两类：一类在S.code和S.next中；另一类是可隐藏的，内部的。,2 一遍扫描产生代码，翻译模式。,S while M1 E do M2 S2,M M.quad := nextquad ,S if E then M1 S1 N else M2 S2, b(E.truelist, M1.q); b(

35、E.falselist,M2.q); S.nextlist := merg(S1.nextlist,N.nextlist, S2.nextlist),N N.n := nakelist(nextquad); M M.q := nextquad C if E then b(e.tc, NXQ) C.C := E.FC,TP C S1 ELSE q: (j, _,_,_) b(c.c,NXQ) TP.C := merg(S1.c,q);,S TP S2 S.C := merg(TP.C, S2.C),6.7.3 分叉语句,形式: case E of C1: S1 C2: S2 Cn-1: Sn-1

36、 otherwise : Sn end,语义： E是一个表达式，称为选择子。通常是一个整型表达式或者字符(char)型变量。每个Ci的值为常数，Si是语句。 若E的值等于某个Ci,则执行Si(i= 1,2,n-1),否则执行Sn。当某个Si执行完之后，整个case语句也就执行完了。,实现方法,1 分叉只有10个左右时，翻译成条件转移语句。,T := E; L1: IF TC1 GOTO L2 S1; GOTO NEXT L2: IF TC2 GOTO L3 S2;,GOTO NEXT; L3: . Ln-1: IF TCn-1 GOTO Ln Sn-1; GOTO NEXT; Ln: Sn;

37、NEXT:,2 开关表,S1 GOTO NEXT,1. 编译程序构造上面的开关表 2. 产生将E值送到该表末项的指令组,以及一个对E值查找开关表的程序 3. 运行时，循环程序对E值查开关表，当E与某个Ci匹配就执行Si,S2 GOTO NEXT,Sn GOTO NEXT,3 如果case的分叉情况比较多，例如在10以上，最好建立杂凑表。求出H(Ci),在其中填入Ci和Si,H(E),Sn,编译时，对CASE构造该表，有的表项为空。运行时，求H(E)值，找对应表项(1=H(E)=M);如空白，则执行Sn,1,M,4 选择子E在基本连续的一个范围(可通过变换)内变化， 如从0到127，只有少数几个

38、值不为Ci,则可建立一个数组B0:127,每个元素BCi中存放着Si的地址。,S1,B2,Bj,B127,Sj,B1,Sn,E,C1,C2,分叉语句的翻译,下面讨论一种便于语法分析制导实现的翻译法。,中间码形式,T := E 的中间码 Goto TEST L1: 关于S1的中间码 Goto NEXT L2: 关于S2的中间码 Goto NEXT ,Ln-1: 关于Sn-1的中间码 Goto NEXT Ln: 关于Sn的中间码 Goto NEXT TEST: IF T=C1 GOTO L1; IF T=C2 TOTO L2; IF T=Cn-1 GOTO Ln-1 Goto Ln NEXT:,问

39、题 当产生末尾的转移语句时，Ci和Li的地址Pi无处查找！ 应在每一个Li出现时，将这两方面的内容存放到队列中。,产生代码过程,case,产生标号TEST,NEXT和一个临时单元T,E,产生 T:= E的四元式,OF,产生GOTO TEST四元式，设置一个空队列QUEUE,Ci,产生一个标号Li,连同NXQ填入符号表，(Ci,Pi)进入队列QUEUE,Si,产生 Si 四元式 GOTO NEXT,otherwise,产生标号Ln,连同NXQ填入符号表,END,产生n个条件转移语句的四元式,TEST: (case, C1, P1, _) (case, C2, P2, _) (case, Cn-1

40、, Pn-1, _ ) (case, T, Pn, _ ) (label, NEXT, _, _) NEXT:,注意 1 末尾的多向转移目标指令组，视不同情况生成，可优 化处理。,如果Si又是一个case语句。怎么办？ 应该建立嵌套队列，要解决队列嵌套，栈嵌套的底标记问题。,3 在产生完指令之后，队列可以不要，但符号表仍然存在，这样可以灵活地优化。,6.8 数组元素引用,本小节讨论数组元素的表达式和赋值句的翻译。由于数组元素较简单变量有一定的特殊性，分几个方面来介绍。,本节内容 地址计算公式 四元式中数组元素表达形式(数组元素引用和中间代码） 赋值语句中数组元素的翻译,6.8.1 地址计算公式

41、,简化假定 数组元素按行存放，每维下限都为1，每个元素只占一个机器字，目标机器存储器是以字编址的。,对数组元素Ai1,i2,in地址D的计算公式如下： D = CONSPART + VARPART CONSPART = a C C = d2d3dn + d3d4dn + + dn +1 VARPART = i1d2d3dn+i2d3d4dn+in-1dn+in,a,addr(A1,1,1),数组首址,注意 CONSPART只依赖于数组各位的界限d和数组的首址a,与数组元素各维的下标i1,i2,in无关。因此，对确定数组而言，计算数组元素的地址时，无需独立计算CONSPART。 VARPART是

42、一个可变部分，它的值随着各维下标i1,i2, ,in的不同而不同。 计算数组元素的地址主要计算VARPART。,6.8.2 数组元素引用和中间代码,这儿只讨论确定数组(编译时可静态确定体积的数组，也称静态数组)的翻译。,简单变量可以在符号表中查到它的地址，而数组元素却不行，在符号表中只有它们的总代表数组名的入口。,因此，每个下标变量在语句中出现，如 X:=A,在目标指令中要有计算A地址的指令。,下标变量的表示形式,不变部分CONSPART,在编译时，可以产生 T1 := a-C ,将其存放在临时单元T1中，在运行时计算下标变量Ai1,i2,in的可变部分，产生计算VARPART的四元式。令T:

43、=VARPART,所以addr(Ai1,in) = T + T1,这样，四元式有如下形式： :=, T+T1, _ , X ,在四元式中出现T+T1不够理想，不够简洁。,参照计算机的变址指令，考虑使用T1T,如此，四元式的形式如下： 变址取数 X:= T1T ( =, T1T, _, X) 变址存书 T1T := X ( =, X, _, T1T),6.8.3 赋值语句中的数组元素翻译,关键问题是下标表达式的计算，进而计算可变部分T。,文法,A V:= E V ielist|i elist elist,E | E E E + E |(E) |V 所定义的赋值句A就是变量V后跟赋值号:=和算术表

44、达式E,如果数组元素为AB,CD,EF,G,那么，在按上面的文法归约下标表达式串时，无法获得数组的内情向量，对每一维的下标都需要保存下来。在该表达式中，就要保存B,D,F等中间结果，如果规模进一步扩大的话，要保存的中间量就会迅速增加，很是繁琐。所以，要寻求能及时计算下标的方法。,定义要点,1 文法允许数组元素嵌套定义 ，AB,C2+1。,2 为了在归约时完成VARPART的计算，需要修改V的文法。,这样能够在整个下标串elist的翻译过程中随时知道数组名i的入口，获取登记在符号表中的数组信息。,回顾一下VARPART的计算公式，它是一个乘加式。 (i1*d2+i2)d3+i3)+in-1)dn

45、+in,语义变量和过程 Elist.ARRAY 数组名的符号表入口 Elist.DIM 数组维数计数器 Elist.PLACE 记存业已形成的VARPART的中间结果名字在符号表中的位置，或者是一个临时变量的整数码。 Limit(ARRAY,k) 函数过程，数组ARRAY的第k维长度dk,现在要考虑的变量有两类，每个变量V有两项语义值。,V.PLACE 简单变量 变量名的符号表入口 下标变量 保存CONSPART的临时变量的整数码 V.OFFSET 简单变量 NULL(用于区分简单变量和下标变量） 下标变量 保存VARPART的临时变量的整数码,语义动作,1 AV:=E IF (V.OFFSE

46、T=NULL) THEN GEN(:=,E.PLACE,_,V.PLACE) ELSE GEN(=,E.PLACE,_,V.PLACEV.OFFSET),2 EE(1)+E(2) T:=NEWTEMP; GEN(+,E(1).PLACE,E(2).PLACE,T); E.PLACE := T ,3 E (E(1) E.PLACE := E(1).PLACE ,4 EV IF (V.OFFSET=NULL) THEN E.PLACE := V.PLACE; ELSE BEGIN T:=NEWTEMP; GEN (=,V.PLACEOFFSET,_,T); E.PLACE:=T; END ,5 V

47、elist T:=NEWTEMP; GEN(-,elist.ARRAY,C,T); V.PLACE:=T; V.OFFSET := elist.PLACE; ,6 V i V.PLACE:= ENTRY(i); V.OFFSET:= NULL; ,7 elistelist(1),E T:=NEWTEMP; k:= elist(1).DIM + 1; dk:=LIMIT(elist(1).ARRAY,k); GEN(*,elist(1).PLACE,dk,T);GEN(+,E.PLACE,T,T); elist.ARRAY := elist(1).ARRAY; elist.PLACE := T;

48、 elist.DIM := k; ,8 elist iE elist.PLACE := E.PLACE; elist.DIM := 1; elist.ARRAY := ENTRY(i) ,A是一个10*20的数组，AI+2,J+1:= M+N的翻译,(+, I, 2, T1),(+, J, 1, T2),(-, A, 21, T4),(+, M, N, T5),(=, T5, _,T4T3),EI+2 T1:=TEMP; GEN(+,I,2,T1); E.PLACE:= T1 ,elist AE elist.PLACE:=E.PLACE; elist.DIM :=1; elist.ARRAY:=ENTRY(A) ,EJ+1 T2:=TEMP; GEN(+, J, 1, T2); E.PLACE:= T2 ,elistelist(1),E T3:=NEWTEMP; k:= elist(1).DIM+1; dk:=limit(elist(1).ARRAY,k); GEN(*,elist(1).PLACE,dk,T3);GEN(+,E.PLACE,T3,T3