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,若把语义动作改为产生中间代码的动作，就能随着分析的进展逐步生成中间代码。,大部分的编译器都不直接产生目标代码，虽然这是可以实现的，但是产生的代码不是最优的。因为这涉及到寄存器的分配问题，在语义分析阶段，很难有效地分配它们。,中间代码的必要性,波兰逻辑学家卢卡西维奇（Lukasiewicz）发明的一
4、种表示法。,一般，若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 e1BC不合法。,布尔表达式(E)在语言中的用途,求值 X:=ABD 条件控制 WHILE ABD DO S IF ABD THEN S1 ELSE S2,布尔表达式的求值,1 通常算法，如同算术表达式求值一样，一步步地计算各部分的值，进而计算出整个表达式的值。,2 采用优化措施 AB if A then true else B AB if A then B else false A if A then false else true,说明 上述两种计算方法对于不包
7、含布尔函数调用的式子是没有什么差别的。仅当遇到布尔函数调用，并且这种函数调用引起副作用时，上述两种算法不等价。,对于第一种方法而言，可以如同翻译算术表达式一样来翻译布尔表达式。,ABC=D 翻译成 = C D T1 B T1 T2 A T2 T3,第二种方法是本节主要内容，下面将详细讨论。,本节内容,一.IF语句的四元式结构 二.翻译的困难和解决办法 三.E的文法和语义子程序 四.例,例 IF ABD THEN S1 ELSE S2,E的结构从整体上，E对外只能转向两个目标,E,转向E为假时的目标,转向E为真时的目标,(1) (jnz,A,_,5)(2) (j,_,_,3)(3) (j,B,D
8、,5)(4) (j,_,_,p+1),(5) (p)(p+1)(q),S1,(j,_,_,q),S2,下一语句,一.IF语句的四元式结构,1.困难,转移的目标在对它的应用之后才出现； (j,_,_,0),E可以很复杂，上面的情况可以频繁出现,二.翻译的困难和解决办法,(1) (jnz,A,_,5)(2) (j,_,_,3)(3) (jEEEE|E|(E)|i|i rop i,G2 E-EE|EE|E|(E)|i|i rop i E-E E-E,三. 布尔表达式文法定义及语义动作,2.语义动作,用自下而上语法分析方法，语法制导生成ABD的四元式,四.例,6.7 控制语句的翻译,本小节讨论无条件和
9、条件语句的翻译，只讨论四元式的产生。,本节内容 标号和转移语句 条件语句 分叉语句,6.7.1 标号和转移语句,标号的两种使用方法 L: S Goto L语言中允许标号先定义后使用，也允许先使用后定义。,(1) 先定义,遇到L1 : S1,符号表,遇到Goto L1,(2) 先使用,q1 goto L2 q2 Goto L2 q3 L2 : S2,遇到goto L2, 填符号表，“未定义”，把NXQ填入L2的地址部分，作为链头。产生( j, _, _, 0),q1 (j, _, _, 0 ),遇到goto L2, 查到未定义，取符号表中L2的地址q1填入四元式q2:(j, _, _,q1),将
10、q2填入符号表。, ,q2 (j, _, _, q1 ),q2,遇到L2:S2,就可以回填。,q3,q3,q3,一般而言，带标号语句产生式 S label S label i:Label i: 的语义动作,1. 若i所指的标识符(假定为L)不在符号表中，则把它填入，置类型为“标号”，“定义否”为“已”，地址为NXQ。,2, 若 L已在符号表中，但“类型”不为“标号”或者“定义否”为“已”，则报告出错。,3. 若L已在符号表中，则把标志“未”改为“已”，然后，把地址栏中的链头(记为q)取出，同时把NXQ填在其中，最后，执行BACKPATCH(q,NXQ)。,6.7.2 条件语句,1 较为复杂的程
11、序控制语句常常是嵌套的。,S1后有一条无条件转移指令，跳转到本语句之后。这里，与上一节不同的是，在S2翻译之后，也不能确定其跳转地址，它要跨越S2,S3。 所以，转移地址的确定与语句所处的环境有关。,if E1 THEN,if E2 then S1 else S2,ELSE S3,解决办法 令每个非终结符S(L)附带一项语义值S.CHAIN，它指出一条链的头，该链是所有期待翻译完S后回填目标的四元式组成的。,注意 回填目标可能是S得下一条四元式，也可能不是。真正的回填，要在处理完S的外层后进行。,考虑语句 WHILE E(1) DO S(1) 译为代码结构,由于语句的嵌套，WHILE翻译完了也
12、未必知道假出口的转移目标，所以作为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 |AL L; S |S (6.5) S语句 L语句串 A赋值句 E布尔表达式,为了能及时回填有关四元式的转移目标，如同处理布尔表达式一样，需要对文法(6.5)进行改写。,S C S | TP S | Wd S | begin L end | A L LS S,| SC if E thenTP CS elseWd W
13、 E doW whileLS 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).CHAINTP C S(1) else q := NXQ; GEN(j, _, _, 0); 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
14、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.CHAIN := S.CHAINLS L; BACKPATCH(L.CHAIN,NXQ) L LS S(1) L.CHAIN := S(1).CHAINS begin L end S.CHAIN := L.CHAIN S A S.CHAIN := 0 空链,IF E THEN S(1
15、) 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 THENBACKPATCH(E.TC,NXQ); C.CHAIN := E.FC ,W WHILEW.QUAD := NXQ,Wd W E(1) DOBACKPATCH(E(1).TC,NXQ); Wd.CHAIN := E(1).FC Wd.quad := W.QUAD ,S1 Wd S(1
16、)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 := MERG(TP.CH,S(2).CH) ,语句翻译完成，结果如图所示,例子,104 (+,Y, Z, T),WWHILEW.QUAD := NXQ,W.QUAD:=100,E(1) i(1) rop i(2)E(1).TC:=NXQ;E(1).FC:=NXQ+1;GEN(jrop,E
17、NTRY(i(1),ENTRY(i(2),0);GEN(j,_,_,0);,Wd W E(1) DOBACKPATCH(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:=NXQ+1;GEN(jrop,ENTRY(i(1),ENTRY(i(2),0);GEN(j,_,_,0);,C IF E(2) THENBACKPATCH(E(2).TC,NXQ); C.CHAIN :=E(2).FC,E i(1)+i(2) E.PLACE := NEWTEMP; GEN(+,E
18、NTRY(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) BACKPATCH(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中
19、出现S.Begin := newlabelE.True := newlabel,如 S while E do S1 的语义规则包含四部分：,E.CODE,S1.CODE,Goto S.begin,S.begin,E.t,E.f,2 “内部的”/可隐藏标志用S.Next及两标志表示。/S.next构成E.F := S.nextS1.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.cod
20、e和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(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,T
21、P C S1 ELSEq: (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 otherwise : Sn end,语义： E是一个表达式，称为选择子。通常是一个整型表达式或者字符(char)型变量。每个Ci的值为常数，Si是语句。 若E的值等于某个Ci,则执行Si(i= 1,2,n-1),否则执行Sn。当某个Si执行完之后，整个case语句也就执行完了。,实现方法,1 分叉只有10个左右时，翻译成
22、条件转移语句。,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;NEXT:,2 开关表,S1GOTONEXT,1. 编译程序构造上面的开关表 2. 产生将E值送到该表末项的指令组,以及一个对E值查找开关表的程序 3. 运行时，循环程序对E值查开关表，当E与某个Ci匹配就执行Si,S2GOTONEXT,SnGOTONEXT,3 如果case的分叉情况比较多，例如在10以上，最好建立杂凑表。求出H(C
23、i),在其中填入Ci和Si,H(E),Sn,编译时，对CASE构造该表，有的表项为空。运行时，求H(E)值，找对应表项(1=H(E)=M);如空白，则执行Sn,1,M,4 选择子E在基本连续的一个范围(可通过变换)内变化， 如从0到127，只有少数几个值不为Ci,则可建立一个数组B0:127,每个元素BCi中存放着Si的地址。,S1,B2,Bj,B127,Sj,B1,Sn,E,C1,C2,分叉语句的翻译,下面讨论一种便于语法分析制导实现的翻译法。,中间码形式,T := E 的中间码 Goto TESTL1: 关于S1的中间码 Goto NEXTL2: 关于S2的中间码 Goto NEXT ,L
24、n-1: 关于Sn-1的中间码 Goto NEXTLn: 关于Sn的中间码 Goto NEXTTEST: IF T=C1 GOTO L1; IF T=C2 TOTO L2; IF T=Cn-1 GOTO Ln-1 Goto LnNEXT:,问题 当产生末尾的转移语句时，Ci和Li的地址Pi无处查找！应在每一个Li出现时，将这两方面的内容存放到队列中。,产生代码过程,case,产生标号TEST,NEXT和一个临时单元T,E,产生 T:= E的四元式,OF,产生GOTO TEST四元式，设置一个空队列QUEUE,Ci,产生一个标号Li,连同NXQ填入符号表，(Ci,Pi)进入队列QUEUE,Si,
25、产生 Si 四元式 GOTO NEXT,otherwise,产生标号Ln,连同NXQ填入符号表,END,产生n个条件转移语句的四元式,TEST: (case, C1, P1, _) (case, C2, P2, _) (case, Cn-1, Pn-1, _ ) (case, T, Pn, _ ) (label, NEXT, _, _) NEXT:,注意1 末尾的多向转移目标指令组，视不同情况生成，可优 化处理。,如果Si又是一个case语句。怎么办？ 应该建立嵌套队列，要解决队列嵌套，栈嵌套的底标记问题。,3 在产生完指令之后，队列可以不要，但符号表仍然存在，这样可以灵活地优化。,6.8 数
26、组元素引用,本小节讨论数组元素的表达式和赋值句的翻译。由于数组元素较简单变量有一定的特殊性，分几个方面来介绍。,本节内容地址计算公式四元式中数组元素表达形式(数组元素引用和中间代码）赋值语句中数组元素的翻译,6.8.1 地址计算公式,简化假定 数组元素按行存放，每维下限都为1，每个元素只占一个机器字，目标机器存储器是以字编址的。,对数组元素Ai1,i2,in地址D的计算公式如下： D = CONSPART + VARPART CONSPART = a C C = d2d3dn + d3d4dn + + dn +1 VARPART = i1d2d3dn+i2d3d4dn+in-1dn+in,a,
27、addr(A1,1,1),数组首址,注意 CONSPART只依赖于数组各位的界限d和数组的首址a,与数组元素各维的下标i1,i2,in无关。因此，对确定数组而言，计算数组元素的地址时，无需独立计算CONSPART。VARPART是一个可变部分，它的值随着各维下标i1,i2, ,in的不同而不同。 计算数组元素的地址主要计算VARPART。,6.8.2 数组元素引用和中间代码,这儿只讨论确定数组(编译时可静态确定体积的数组，也称静态数组)的翻译。,简单变量可以在符号表中查到它的地址，而数组元素却不行，在符号表中只有它们的总代表数组名的入口。,因此，每个下标变量在语句中出现，如 X:=A,在目标指
28、令中要有计算A地址的指令。,下标变量的表示形式,不变部分CONSPART,在编译时，可以产生 T1 := a-C ,将其存放在临时单元T1中，在运行时计算下标变量Ai1,i2,in的可变部分，产生计算VARPART的四元式。令T:=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后跟赋值号:=和算术表达式E,如果数组元素为AB,CD,EF,G,那么，在按上面的文法归约下标表达式串时，无法获得数组的内情向量，对每一维的下标都需要保存下来。在该表达式中，就要保存B,D,F等中间结果，如果规模进一步扩大的话，要保存的中间量就会迅速增加，很是繁琐。所以，要寻求能及时计算下标的方法。,定义要点,
