《语法制导翻译技术及中间代码.ppt》由会员分享，可在线阅读，更多相关《语法制导翻译技术及中间代码.ppt（85页珍藏版）》请在三一办公上搜索。
1、第七章 语法制导翻译技术及中间代码的生成,主 要 内 容1.语义翻译的方法：采用语法制导翻译技术的方法。依据的文法(描述文法的语义)：属性文法。(一般掌握)语法制导翻译过程：根据已有的属性文法，生成句子的 中间代码过程。(重点掌握)2.语义翻译结果的表示：中间代码。(重点掌握)常见：逆波兰表示四元式表示和三地址代码 三元式和树形表示,1.语义分析概述,一、语义分析的任务任务有：审查每一个语法结构的静态语义，即验证语法正确的结构是否有意义。如：赋值语句：x:=x+y,左边变量类型与右边变量类型是否一致。在语义正确的基础上生成一种中间代码或目标代码。,二、语义分析的范围1o.确定类型：确定标识符所
2、关联的数据类型。2o.类型检查：按语言的类型规则，检查运算的合法性与运算分量类型的一致性，必要时作类型转换。3o.识别含义：根据语言的语义定义（形式或非形式），识别程序中各构造成分组合到一起的含义。，并作相应的语义处理（生成中间代码或目标代码）4o.控制流检查：控制流语句必须转移到合法的地方。如：C中，break语句规定跳出最内层的循环或switch语句.5o.一致性检查：在很多场合要求对象只能被说明一次，如：pascal语言规定同一个标识符在一个分程序中只能被说明一次等。,6o.相关名字检查：如：Ada，循环或块可以有一个名字，它出现在这些结构的开头或结尾。编译程序必须检查这两个地方用的名字
3、是否相同。其它：如名字的作用域分析等也是语义分析的工作。三、语义描述工具和语义分析方法语义描述工具 目前流行：用属性文法作为描述语义的工具。语义分析方法根据描述属性文法的语义规则的方式不同，语义分析方法分为：语法制导定义方法翻译方案,2.属 性 文 法,一、属性属性常用来描述事物或人的特征。如：人的姓名，性别等，商品的颜色、重量、单位等。属性：在编译中，对文法的每一个符号，引进一些属性，用这些属性描述文法符号相关的信息，如：类型、值或存储位置等。如：A:=X，在语法推导或归约时，有时结合X的类型，位置，值,考虑语法分析的正确性，即语法分析中有语义检查。如:X的属性：Xtype，Xplace，X
4、val分别表示X的类型，位置，值等语义。,属性值：可以在语法分析过程中计算和传递。属性的加工过程就是语义的处理过程。二、属性文法语义规则在对文法符号属性处理过程中，必须遵守一定义的规则语义规则。为文法的每一产生式定义一组属性的计算规则，称为语义规则。属性文法形式定义：一个属性文法是一个三元组A，A=(G,V,F)其中：G为一个上下文无关文法；V 表示属性的有穷集合；F表示属性的断言或谓词的有穷集。,在属性文法中：每个属性与文法中某个符号相关联，用“符号属性”表示。如：Xtype,Xint,Xbool等。每个断言与文法的某产生式相关联。断言就是产生式上定义的一组语义规则。例：一个简单表达式方法：
5、E:=T1+T2|T1orT2T:=num|true|false,根据程序语言中有关类型的检验原则，可以得到关于类型检验的属性文法：E:=T1+T2 T1.type=int and T1.type=intE:=T1orT2 T1.type=bool and T1.type=boolT:=num T.type=intT:=true T.type=boolT:=false T.type=bool属性分类：综合属性 继承属性综合属性：从语法分析角度看，如果一个结点的某一属性，其值由子结点的属性的值来计算，称该属性为综合属性。,例：已知上例属性文法的输入串3+4语法树。其中：E中语义规则中的T1.ty
6、pe和T2.type中的type属性的值分别由子结点T1.type=int和T2.type=int中的int值来计算，使得E中的语义规则（断言）为真。因此：type是综合属性。综合属性用于“自下向上”传递信息。,继承属性：在语法分析树中，结点的某个属性值由该结点的兄弟结点和（或）父结点的属性值来计算，此结点的属性称为继承属性。继承属性用于“自上而下”传递信息。注意：终结符号只有综合属性，他由词法分析器提供。非终结符号既有综合属性，也可有继承属性。文法识别符号（开始符号）的所有继承属性作为属性计算前的初始值。根据处理不同的要求，属性和断言可以多种形式出现，如：语义规则或者程序段等。,例：简单表达
7、式求值的属性文法。产生式：L:=Eprint(E.val)E:=E1+TE.val:=E1.val+T.valE:=TE.val:=T.valT:=T1*FE.val:=T1.val*F.valT:=FT.val:=F.valF:=(E)F.val:=E.valF:=digitF.val:=digit.lexval,例：描述说明语句中简单变量类型信息的属性文法产生式语义规则D:=TLL.in:=T.typeT:=intT.type:=integerT:=realT.type:=real L:=L1，id L1.in:=L.inaddtype(id.entry,L.in)L:=idaddtype
8、(id.entry,L.in),文法定义了一种说明语句，该说明语句的形式是由关键字int或real开头，后跟一个标识符表，每一个标识符间用逗号隔开：real id1，id2，idn或 int id1，id2，idn属性文法中，非终结符T有综合属性type，其值由关键字int和real决定。语义规则L.in:=T.type将L的属性值置为该说明语句指定的类型。L.in将被沿着语法树传递到下边的结点使用，与L产生式相联的规则里使用了它。如：句子int id1，id2语法树：图2,一、基本思想对文法中的每个产生式都附加上一个语义动作或语义子程序，伴随着语法分析，每当使用一条产生式进行推导或归约时，就
9、执行相应产生式的语义动作（包括：查填表格，改变变量的求值，打印信息和生成中间代码等），从而完成预定的翻译工作。即在语法翻译过程中伴随部分语义的检查工作。,3.语法制导翻译概述,语法制导翻译方法：自底向上的语法制导翻译方法自顶向下的语法制导翻译方法二、语法制导翻译的步骤1、为所给文法每个产生式设计相应的语义规则。例：为一个简单表达式计值的文法：E=E+E|E*E|(E)|digit设计计值的语义规则如下：1.E=E(1)+E(2)Eval:=E(1)val+E(2)val 2.E=E(1)*E(2)Eval:=E(1)val*E(2)val 3.E=(E(1)Eval:=E(1)val4.E=d
10、igitEval:=lexdigit为文法产生式写语义规则或语义子程序是本章的难点.,2.采用LR分析方法，则构造LR分析表,3.将原LR语法分析栈扩充，增加语义值栈。,4.根据语义分析栈的工作过程设计总控程序，使语法分析与语义分析工作同时完成。例：计算表达式7+8*5的语法树，以及用LR语法制导翻译法得到该表达式的计值过程：,注：自底向上语法制导翻译的特点：当栈顶形成句柄执行归约时，调用相应的语义动作。语法分析与语义分析同步操作。,*,说明：若把计值的动作改为产生某种中间代码的子程序，那么，就能在伴随着语法分析的制导下，随着分析的进展逐步生成中间代码。问题：1.什么是中间代码？它有哪几种形式
11、表示源程序语言的句子？4.中间语言 2.在语义规则中，怎么样定义生成中间代码（主要是四元式或三地址式）的一些语义规则？5.表达式及语句的语义翻译 3.根据具有生成中间代码的属性文法，生成中间代码的过程是怎样的？,一、中间语言概述1 中间语言中间语言：它介于源程序到目标语言程序中间程序的语言中间语言程序：用中间语言表示的程序。作用：用于编译程序，将源程序翻译成等价的中间语言程序，再将中间语言程序转化成目标程序（即将语义分析和目标代码生成分开处理）源程序中间语言程序目标程序中间语言是表示语法制导翻译的结果。,等价变换,转化,4.中 间 语 言,好处：中间语言与机器无关，使采用中间语言进行翻译的编译
12、程序系统易于移植。易于优化翻译后的代码。使编译程序的结构在逻辑上更简单明确。2 中间语言的表示常见：逆波兰表示 四元式表示和三地址代码 三元式和树形表示二、逆波兰表示,由波兰逻辑学家J.Lukasiewicz(卢卡西维兹)首先提出用来表示表达式的方法，后来推广到表示程序设计语言中的其它语法成分。表达式的逆波兰表示表达式的表示：中缀表示：运算符居中，运算对象在左右两边:a+b波兰表示：前缀表示：运算符在前，运算对象在后：+ab后缀表示：运算对象在前，运算符在后：ab+(逆波兰表示),例：逆波兰表示的例子,(1)表达式逆波兰表示的定义：设E是一般表达式，则：一般表达式逆波兰表达式若E为变量或常量E
13、（E）E的逆波兰式E(1)opE(2)(二目运算)E(1)的逆波兰式E(2)的逆波兰式opopE(单目运算)E的逆波兰式op,在编译过程中，生成逆波兰表示的语义规则描述：产生式 语义规则 E:=E(1)opE(2)E.code=E(1).code|E(2).code|op E:=(E(1)E.code=E(1).code E:=i E.code=i 其中：E.code表示E的逆波兰式；|表示逆波兰式的连接。(2)逆波兰表示的特点a.标识符(运算对象)出现的顺序（从左到右）和原有顺序相同。b.运算符是按实际计算顺序（从左到右）出现的。c.运算符紧跟在运算对象的后面出现，并且没有括号。,(3)好处
14、：易于对表达式的计算处理对于中缀表达式的计算，系统需要用两个工作栈分别处理运算对象和运算符。对于逆波兰表示的表达式计算处理只用一个工作栈。例：逆波兰式ab+c*的计算处理过程,遇运算对象a,b入栈,扫描ab+c*,栈,遇运算符+,取出a,b，运算结果T入栈,c*,遇运算对象c入栈,*,遇运算法*取出c,T作运算，设结果T1,2.形成逆波兰表示怎样将一般表达式转换成逆波兰表示？基本思想:从左到右扫描表达式，每遇到：1o 表达式中的运算对象则往左去。2o 表达式中的运算符，则与运算符栈顶元素比较优先数：,逆波兰表示,表达式,运算对象,运算符,进栈,出栈,运算符栈,如果运算符栈顶元素的优先数大于或等
15、于表达式中当前的运算符优先数，则栈顶元素退栈向左去。然后当然运算符继续与栈顶的新元素比较优先数。直到栈顶元素的优先数小于表达式中当前运算符为止。此时，才将表达式中当前运算符进栈。,例：画出形成表达式a*(b+c/d)的逆波兰表示过程,a,*(b+c/d)#,#,a,(b+c/d)#,*#,a,b+c/d)#,(*#,ab,+c/d)#,(*#,ab,c/d)#,+(*#,abc,/d)#,+(*#,步骤,步骤,步骤,步骤,步骤,步骤,abc,d)#,abcd,)#,/+(*#,/+(*#,/,+(*#,Abcd/,)#,+,(*#,Abcd/+,)#,*,#,Abcd/+*,#,步骤,步骤,步
16、骤,步骤,步骤,形成逆波兰表示的过程，实质上是表达式的翻译过程。（算法不难写出）例：a/b/c+d=ab/c/d+(a+b)*(c-d/e)=ab+cde/-*3.扩充的逆波兰表示逆波兰不仅仅用来表示计算表达式，而且可以推广到其它语法成分的表示。赋值语句：a:=e(其中e是表达式)逆波兰表示：ae:=(其中e应该为逆波兰表示),例：a:=3*(b+c)的逆波兰表示：a3bc+*:=条件语句：if u then S1 else S2逆波兰表示：u l1 jumpf S1 l2 jump S2其中：u为布尔表达式的逆波兰表示S1,S2均为相应语句的逆波兰表示。jumpf 表示一个双目运算符：当u为
17、假(0)时，它引向标号 l1的分支，l1表示语句S2的开始位置。jump表示单目运算符：它无条件的引向标号为l2的分支，l2表示语句S2后的符号位置。逆波兰式表示的语义：当u=0(假)转去执行S2，否则转向执行S1，然后跳到S2之后的语句。,有下列源程序段：K:=0;if ij then K:=K+6*ai-jelse Begini:=i+1;j:=j-1;End;,逆波兰表示：K0:=ijl1 jumpf KK6ij-aSubs*+:=l2 jump l1:ii1+:=jj1-:=l2:含义：当ij为假便转向l1处执行S2;否则执行S1后无条件转到l2处即语句S2的后继部分。,三、三元式和树
18、形表示1。三元式一个三元式由三个主要部分和一个序号组成：(i)(op,arg1,arg2)其中：op是运算符，arg1和arg2是运算对象。当op为一目运算符时，只有一个运算对象。(i)表示三元式的序号，三元式的运算结果由每个三元式前序号(i)指示。序号(i)指向三元式所处的表格位置，因此引用一个三元式的计算结果是通过引用该三元式的序号实现的。三元式出现的先后顺序与表达式的计值顺序一致。,例：a:=-b*c+b*d三元式：(1)(,b,_)(2)(*,(1),c)(3)(*,b,d)(4)(+,(2),(3)(5)(:=,(4),a)2.间接三元式由于三元式的先后顺序决定了值的顺序，因此在产生
19、三元式形式的中间代码后，对其进行代码的优化时难免涉及到改变三元式的顺序(即三元式表示的中间代码不利用代码优化),这就要修改三元式表。为了最少改动三元式表，可以另设一张间接码表来表示有关三元式在三元式表的计值顺序，用这种办法处理的中间代码称为间接三元式。例：表达式x=A+B*C y=D-B*C,其间接三元式表示如下：,由于间接码表的作用，编译程序每产生一个三元式时，先查看三元式表中是否存在当前三元式，若存在就不需要重复填写三元式表，如上例中的三元式(1)(*,B,C)在间接码表中出现了两次，但三元式表中实际只有一个三元式。注：三元式表示的中间代码不利于中间代码的优化。间接三元式表示的中间代码有利
20、于中间代码的优化。,3.树形表示树形结构是三元式的另一种表示形式例如：上例a:=-b*c+b*d的树形表示(由三元式的下至上画出),树形表示法很容易表示一个表达式或语句。一个表达式中简单变量或常数的树形表示就是它们的本身。如果表达式e1和e2的树分别为T1和T2,则：e1和e2,e1*e2,-e1的树分别：,注：二目运算对应二叉树三目运算对应三叉树：如条件语句if u then S1 else S2 可看作三目运算。其三目运算符定义为:if then else 则：树表示,注：多叉树不便于存储，可以化为二叉树：,四、四元式和三地址代码四元式是一种比较普遍采用的中间代码形式。四元式由四个部分组成
21、：(i)(op,arg1,arg2,result)其中：op为运算符;arg1,arg2为运算对象。result存放结果的变量。四元式之间的联系通过变量来联系(而不用三元式中的序号联系)例：a:=b*c+b*d四元式表示：(1)(*,b,c,t1)(2)(*,b,d,t2)(3)(+,t1,t2,t3)(4)(:=,t3,_,a),注：四元式和三元式的主要不同在于：四元式之间的联系通过中间引用的变量名实现，而三元式之间的联系通过三元式序号实现。这说明要更改一张三元式表比较困难，它需要改变一序列的三元式的序号。四元式表的修改比较容易，调整四元式之间位置，不改变其中的参数。因此：四元式和三地址代码
22、表示的中间代码便于中间代码的优化。而三元式和树不便于优化。,有时将四元式表示成更直观的形式三地址代码三地址代码形式：x:=a op b(赋值形式)与赋值语句的区别：其右边最多只能有一个运算符。例：上例的四元式写成三地址代码：(1)t1:=b*c(2)t2:=b*d(3)t3:=t1+t2(4)a:=t3,三地址代码表示的好处：表示中间代码更直观，有利于中间代码的优化和目标代码的生成。四元式的生成算法与逆波兰式生成算法基本相同。扩充四元式可表示程序语言的其它语法成分。例：将表达式:A+B*(C-D)-E/F G写成逆波兰表示、三元式和四元式逆波兰表示:ABCD-*+EFG/-三元式:(1)(-,
23、C,D)(2)(*,B,(1)(3)(+,A,(2)(4)(,F,G)(5)(/,E,(4)(6)(-,(3),(5),四元式：(1)(-,C,D,T1)(2)(*,B,T1,T2)(3)(+,A,T2,T3)(4)(,F,G,T4)(5)(/,E,T4,T5)(6)(-,T3,T5,T6),三地址代码：T1:=C-D T2:=B*T1 T3:=A+T2 T4:=F G T5:=E/T4 T6:=T3-T5,例：将语句:if AVBD then i:=i+1 else i:=i-1 写成四元式。(1)(,B,D,T1)(2)(V,A,T1,T2)(3)(BMZ,T2,(7)（T2为假）(4)(
24、+,i,1,T3)(5)(:=,T3,i)(6)(JMP,(9)(7)(-,I,1,T4)(8)(:=,T4,i)(9),三地址代码：(1)T1:=BD(2)T2:=A V T1(3)if T2 goto(7)（T2为 真转）(4)T3:=i-1(5)i:=T3(6)goto(9)(7)T4:=i+1(8)i:=T4(9),注：四元式表示中间代码最大的优点是便于中间代码的优化。缺点:引用临时变量较多，占用的空间比三元式要多。三元式表示中间代码的优点：无须引用较多的临时变量、占用空间少。但不便于代码优化。四元式及三地址代码在后面的语义规则中都要使用。,5.表达式及语句的语义翻译,如何为文法写出产
25、生表达式和语句的中间代码（如：四元式或三地址式）的语义规则。以便在检查它们语法的同时，将它们生成用四元式或三地址式表示的中间代码。下面主要介绍将表达式、赋值语句、条件语句生成四元式或三地址式的语义规则设计。一、简单算术表达式和赋值语句的翻译简单算术表达式仅含有简单变量、常数和算术运算符的式子，不含有数组元素、结构等复合型数据类型。简单算术表达式的计值顺序与四元式出现的顺序相同，因此很容易将其翻译成四元式形式。例：已知文法G:A=i:=EE=E+E|E*E|-E|(E)|i,对此写出语义子程序，以便在进行归约的同时执行语义子程序。这些语义子程序中所设置的语义变量、语义过程及函数是：(1)对非终结
26、符E定义语义变量E place。E place表示存放E值的变量名在符号表中的入口地址或者临时变量名的整数码。(2)定义语义函数newtemp()，其功能是产生一个新的临时变量名字，如T1,T2等。具体实现时，每产生一个Ti,就及时送符号表；也可以不进符号表，直接将单词值用整数码表示。(3)定义过程emit(T=arg1 op arg2),emit的功能时产生一个四元式，并及时填进四元式表中。(4)定义过程lookup(i,name),其功能时审查i name是否出现在符号表中，存在则返回其指针，否则返回null利用以上定义的语义变量、过程、函数等，给文法G中每个产生式写出语义子程序：,(1)
27、A=i:=E p=lookup(i name);if(p=NULL)error();else emit(p=E place)(2)E=E(1)+E(2)E place=newtemp();emit(E place=E(1)place+E(2)place)(3)E=E(1)*E(2)E place=newtemp();emit(E place=E(1)place*E(2)place(4)E=-E(1)E place=newtemp();emit(E place=uminus E(1)place(5)E=(E(1)E place=E(1)place;(6)E=i p=lookup(i name);
28、if(p!=NULL)E place=p;else error();,若考虑表达式中变量及常数的类型之间的运算问题：如规定整型与实型运算时需将整型置换成实型量。这样需要进行类型的语义处理。增加语义变量，用E type表示E的类型信息，E type的值成为int 或real。此外，用单目运算符itr表示将整型运算对象转换成实型。为了区别整型加(乘)和实型加(乘)，把+(*)分别写成+i(*i)和+r(*r)。这样上面文法中的第(3)条产生式及语义描述：,E=E(1)*E(2)E place=newtemp();if(E(1)type=int AND E(2)type=int)emit(Eplac
29、e=E(1)place*i E(2)place);Etype=int;else if(E(1)type=real AND E(2)type=real)emit(Eplace=E(1)place*r E(2)place);Etype=real;else if(E(1)type=int AND E(2)type=real)t:=newtemp();emit(t=itr E(1)place);emit(E=t*r E(2)place);,Etype=real;else if(E(1)type=real AND E(2)type=int)t:=newtemp();emit(t=itr E(2)plac
30、e);emit(E=E(1)place*r t);Etype=real;,例：赋值语句X:=B*(C+D)+A的语法制导翻译过程如表：,逆波兰表示：XBCD+*A+:=,(2),(2),(3),(1),例子：有文法：(1)EE(1)+E(2)(2)EE(1)*E(2)(3)E(E(1)(4)Ei 其后的语义规则见上面文法对应产生式的语义规则,例：表达式B*(C+D)的语法制导翻译过程如表：,逆波兰表示：BCD+*,二、布尔表达式的翻译程序中的布尔表达式的作用：(1)计算逻辑值(2)用作语句的控制条件常用的布尔表达式可用下述文法描述：E=EE|EE|E|(E)|i rop i|i其中,为逻辑运算
31、符；rop代表关系运算符(,);i为逻辑变量或逻辑常量；i rop i为关系表达式。1.布尔表达式的翻译布尔表达式的计值方法：(1)通过逐步计算出各部分的值来计算整个表达式的值.例：假定用1表示true,0表示false，则布尔表达式：,1(0 0)1=1(0 1)1=1 0=1(2)利用逻辑运算符的性质计值如：当A=1,则AB的值(不管B为何值)一定为1。布尔表达式计值方法不同，则采用的翻译方法也不同。例：按第(1)种方法，布尔表达式A=BCD将被翻译成如下的四元式序列：(1)if A=B goto(4)(A=B为真转（4）)(2)T1=0(3)goto(5)(4)T1=1(5)T2=C D
32、(6)T3=T1 T2,例：按布尔表达式第(1)种计值法，将文法：E=EE|EE|E|(E)|i rop i|i表示的布尔表达式翻译成四元式的翻译方案。E=E(1)E(2)E place=newtemp();emit(E place=E(1)place E(2)place);E=E(1)E(2)E place=newtemp();emit(E place=E(1)place E(2)place);E=E(1)E place=newtemp();emit(E place=E(1)place);E=(E(1)E place=E(1)place;E=i(1)rop i(2)E place=newte
33、mp();emit(if i(1)place rop i(2)place goto nextq+3);emit(E place=0);emit(goto nextq+2);emit(E place=1)E=iE place=i place,2.控制语句中布尔表达式的翻译布尔表达式不仅可以计值，而且其值还决定了程序控制流的转向(如if和while中).现讨论布尔表达式E在if-then,if-then-else和while-do中翻译。三种语句的语法和代码结构为：S=if E then S(1)|if E then S(1)else S(2)|while E do S(1),为了将作为条件控制的
34、布尔表达式E正确翻译成四元式，且E翻译的代码是一串条件转移和无条件转移的四元式代码，则定义下面的一组控制转移的四元式：(1)if E goto Li 当E为真，转向Li,称Li 为E的真出口，记为E true。(2)if E(1)rop E(2)goto Li 当E(1)rop E(2)为真，转向Li,Li 为关系运算符rop的真出口。(3)goto Lj 无条件转向标号Lj，称Lj为假出口,记为：E false。例：E的布尔表达式为:af,翻译为如下四元式序列：(1)if af goto E true(6)goto E false,注：布尔表达式计值是采用第二种方式进行。描述布尔表达式控制功
35、能的语义的四元式序列都是由一串条件转移和无条件转移四元式代码组成。现把E布尔式放在条件语句中考察条件语句转移的出口问题例：有条件语句：if af then S(1)else S(2)其四元式序列为：(1)if af goto(7)(6)goto(p+1)(7)(关于S(1)的四元式序列)(p)goto(q)(p+1)(关于S(2)的四元式序列)(q)后继四元式,四元式中的地址回填问题上述if四元式序列中的(1)和(5)四元式的转移地址(7)不能在产生式(1)和(5)四元式时立即得知，至少要等到if语句的then时才能回填(7)表示的产生S(1)的第一个四元式的地址。同理(4)和(6)四元式中的
36、转移地址(p+1)也需要S(2)的第一个四元式的地址回填。采用拉链技术解决四元式序列中的地址回填为了记录需回填地址的四元式，把需回填E true 的四元式拉成一个链(为真值的链简称真链)；把需要回填E false 的四元式拉成另一个链(为假值的链简称假链)拉链的方法：若有四元式序列：(10).goto E true(20).goto E true(30).goto E true则链成：,(10).goto(0)(20).goto(10)(30).goto(20)其中，地址(30)为链头，0为链尾标志，地址(10)为链尾。最后，讨论用于if 语句和while语句中的布尔表达式的语义翻译问题。为了
37、回填四元式中地址信息，要用到公共变量，过程和函数：四元式(标号或地址)指针nextqnextq的值表示下一个即将要产生的四元式标号，初值为1，每生成一个四元式，其值自动加1。设置非终结符E的语义变量E bcodeE bcode表示非终结符E的第一个四元式标号。回填过程backpatch(p,t),功能：把p所链接的每个四元式的第四区段都回填为t。若原第四区段已有信息，应保存后再回填为t。链接函数merge(p1,p2)将p1和p2为链首的两个链合并为一条，返回合并后的链首值。根据布尔运算特性，采用自下而上的语法制导翻译方法，给出布尔表达式文法中每个产生式相应的语义子程序：(1)E=i E tr
38、ue=nextq;E fale=nextq+1;E bcode=nextq;emit(if i place goto 0);emit(goto 0);(2)E=i(1)rop i(2)E true=nextq;E bcode=nextq;E fale=nextq+1;emit(if i(1)place rop i(2)place goto 0);emit(goto 0);,(3)E=(E(1)Etrue=E(1)true;Efalse=E(1)false;Ebcode=E(1)bcode;(4)E=E(1)Etrue=E(1)false;E false=E(1)true;E bcode=E(1
39、)bcode(5)E=E(1)E(2)backpatch(E(1)false,E(2)bcode);Ebcode=E(1)bcode;Etrue=merge(E(1)true,E(2)true);Efalse=E(2)false;(6)E=E(1)E(2)backpatch(E(1)true,E(2)bcode);Ebcode=E(1)bcode;E true=E(2)true;E false=merge(E(1)false,E(2)false);,产生式(1)(同理(2),(3),(4)式一样)语义子程序中，可见用E=i归约后，E的真假链都有了具体值。这样，在用产生式(5)归约时，E(1)与
40、E（2）的真假链分别也有了具体值。根据布尔运算的特性可知：(1)当E(1)为假时，计算E(2)，所以E(2)的第一个四元式地址(这是已记录在E(2)bcode中)E(2)bcode这时回填为E(1)的假值链，因此有backpatch(E(1)false,E(2)bcode)。(2)若E(1)为真时，无须计算E(2)而去执行S(1)的第一个四元式，但此时尚未扫描到“then”,因此，保留E(1)已形成的值链首E(1)true；若E(2)为真时，其转移地址用E(1)，所以将E(1)，E(2)两个真链E(1)true，E(2)true合并为E的一个链。(3)若E(1)为假，在计算E(2)，E(2)也
41、为假，这时整个布尔式E(1)E(2)为假，可见E(2)的假出口与整个布尔式的假出口一致，此时E(2)的假出口E(2)false业已形成。因此，有E false=E(2)false。(4)尽管有E(1)，E(2)参与运算，但按扫描顺序，首先生成E(1)的四元式。因此，E(1)的第一个四元式也就是整个布尔式的第一个四元式，所以有Ebcode=E(1)bcode.同理不难分析(6)产生式的语义子程序。,下面以表达式ABD为例，按上面的翻译方案，说明将它生成四元式的过程。(1)首先指示器nextq赋初值为1，当扫描到A时，用E=i归约，根据产生式(1)的语义子程序，有：E(1)true=nextq=(
42、1),E(1)false=nextq+1=(2),Ebcode=1,生成四元式:(1)if A goto 0(2)goto 0此时nextq=3(2)继续扫描，由自底向上的语法制导翻译可知，这时应归约BD,用产生式E=E(1)rop E(2)，有：E(2)true=nextq=(3),E(2)false=nextq+1=(4),E(2)bcode=nextq=(3),生成四元式:(3)if BD goto 0(4)goto 0此时nextq=5,(3)继续向上归约，用E=E(1)E(2)归约，有：回填backpatch(E(1)false,E(2)bcode)Ebcode=E(1)bcode;
43、Etrue=merge(E(1)true,E(2)true);Efalse=E(2)false;因为E(1)ture=(1),E(2)ture=(3)所以合并后Etrue（3），将E(1)true放到E(2)的链尾。回填得:E(2)bcode=(3),将(3)填入E(1)false中，即goto(3)。合并E(1),E(2)的真链将E(2)true填到以E(1)为真链头的一个四元式区段中。最后E(2)的假链就是E的假链：Efalse=E(2)false;得到一组四元式:(1)if A goto 0(2)goto(3)(3)if BD goto(1)(4)goto 0这时，Etrue=(3),E
44、false=(4),三、控制语句的翻译在程序设计语言中，控制语句的一般形式：if-then,if-then-else,while-do这些语句由下列文法定义：GS:(1)S=if E then S(1)(2)S=if E then S(1)else S(2)(3)S=while E do S(1)(4)S=A(5)S=L(6)L=L(1);S(7)L=S其中：非终结符L表示语句串，A表示赋值语句，S为语句，E为布尔表达式。,下面着重介绍控制语句翻译过程中涉及的回填和拉链技术。1.if语句的翻译如：S=if E then S(1)else S(2)翻译此语句应明确以下几点：(1)布尔表达式E的作
45、用仅在于控制对S(1)或S(2)的选择。因此，作为转移条件的布尔式E，使用E true和E false分别指出尚待回填“真”,“假”出口的四元式串；(2)E的“真”出口只有在扫描到then时才能知道，而它的“假”出口则需要S(1)并且到达else之后才能明确。这就是说，必须把Efalse的值传下去，以便在到达相应的else时才能进行回填。(3)另外，当S(1)执行完之后意味着整个if语句也已经执行完毕，因此在S(1)的编码之后产生一条无条件转移指令(goto 0)，但在完成S(2)的翻译之前，该无条件转移的转移目标无法知道。对于语句嵌套的情况，如：if E(1)then if E(2)then
46、 S(1)else S(2)else S(3),在翻译S(2)后，S(1)后的无条件转移目标仍无法确定，因为它不仅跨越S(2)，还要跨越S(3)。,可见，转移目标的确定与if所处的环境有关。因此，对非终结符S(或L)设置一个语义变量S CHAIN(或L CHAIN),记忆所有待填信息的四元式链，知道翻译完整个语句后再回填转移目标地址。为了扫描控制语句的每一时刻不失时机地处理和回填有关信息，将文法改写，并写出if 语句各产生式相应语义子程序。(1)S=CS(1)(2)C=if E then(3)S=TpS(2)(4)Tp=CS(1)else根据程序设计语言的处理顺序，首先用产生式(2)C=if
47、E then 归约，这时在then后可产生E的真出口地址。因此将then后的第一个四元式回填至E的真出口地址。E的假出口地址作为待填信息放在C的语义变量C CHAIN中，即,C=if E then backpatch(Etrue,nextq);CCHAIN=Efalse;接着用产生式(1)S=CS(1)继续向上归约。此时已经处理到C=if E then S(1),注意到归约时E的真出口已经处理，由于E不成立时注意地址V与S(1)语句的待填转移地址相同，E的假出口地址已放在CCHAIN中，但此时转移地址仍未确定，S(1)的待填转移地址的链放在S(1)CHAIN中，所以应将CCHAIN与S(1)C
48、HAIN一并作为S的待填信息链，用函数merge链起来，链头保留在S CHAIN中，即有：S=CS(1)SCHAIN=merge(CCHAIN,S(1)CHAIN如果if语句没有后继部分，在产生式(1)(2)归约为S后，随即可产生后续第一个四元式地址，以此回填S的语义值SCHAIN。即为if E then S(1)语句的语义子程序。,如果if 语句为if-then-else 形式，用产生式Tp=CS(1)else继续归约。归约时首先产生S(1)语句序列的最后一个无条件转移四元式，它的标号保留在q中。(i)S(1)第一个四元式/*E的真出口*/。(q)goto 0/*q的第四区段有待回填*/ne
49、xtq/*else后的第一个四元式，即E的假出口*/q就是整个语句S的语义值SCHAIN.因为有待回填q第四区段的值，它与SCHAIN一样，链在以链头为TpCHAIN的链中，用merge函数实现。过程emit产生(q)四元式后，nextq自动加1，这时nextq是else后的第一个四元式地址，也是E的假出口地址，回填该值时Efalse即CCHAIN中，因此有 Tp=CS(1)else q=nextq;,emit(goto 0);backpatch(CCHAIN,nextq);TpCHAIN=merge(SCHAIN,q);最后用产生式(3)S=TpS(2)归约。当S(2)语句序列处理完后，产生
50、if的后继语句。这时就有了后继语句四元式的地址，该地址是整个if语句的出口地址，它与S(2)语句序列的出口一致。S(2)的出口待填信息在S(2)CHAIN中，因此将TpCHAIN和S(2)CHAIN链接，并以SCHAIN为链头。S=TpS(2)SCHAIN=merge(TpCHAIN,S(2)CHAIN);2.WHILE语句的翻译将产生式：S=while E do S(1)分解如下：(1)S=WdS(1)(2)Wd=WEdo(3)W=while写出文法各产生式的语义子程序如下：,观察while语句的代码结构如图，,执行到while时，首先记下E的第一条四元式地址，以便归约到do S(1)后能准
