编译原理 语法制导翻译和中间代码生成（课堂PPT）

1,一个源程序经过词法分析、语法分析之后，表明该源程序在书写上是正确的，也就是符合程序语言所规定的语法。但是语法分析并未对程序内部的逻辑含义加以分析，因此编译程序接下来的工作是语义分析。,编译中的语义处理是指两个功能：第一，静态语义分析或静态审查。审查每个语法结构的静态语义，即验证语法结构合法的程序是否真正有意义。第二，翻译。如果静态语义正确，语义处理则要执行真正的翻译，即，或者将源程序翻译成程序的一种中间表示形式（中间代码），或者将源程序翻译成目标代码。,第8章语法制导翻译技术和中间代码生成,2,类型检查。验证程序中执行的每个操作是否遵守语言的类型系统的过程，编译程序必须报告不符合类型系统的信息。控制流检查。控制流语句必须使控制转移到合法的位置。例如，在C语言中break语句使控制跳离包括该语句的最小while、for或switch语句。如果不存在包括它的这样的语句，则就报错。一致性检查。在很多场合要求对象只能被定义一次。例如Pascal语言规定同一标识符在一个分程序中只能被说明一次，同一case语句的标号不能相同，枚举类型的元素不能重复出现等等。相关名字检查。有时，同一名字必须出现两次或多次。例如，Ada语言程序中，循环或程序块可以有一个名字，出现在这些结构的开头和结尾，编译程序必须检查这两个地方用的名字是相同的。名字的作用域分析,静态语义分析通常包括,3,中间代码,所谓中间代码，也称中间语言，是复杂性介于源程序语言和机器语言的一种表示形式。有的编译程序直接生成目标代码，有的编译程序采用中间代码。一般来说，快速编译程序直接生成目标代码，没有将中间代码翻译成目标代码的额外开销。但是为了使编译程序结构在逻辑上更为简单明确，常采用中间代码，这样可以将与机器相关的某些实现细节置于代码生成阶段仔细处理，并且可以在中间代码一级进行优化工作使得代码优化比较容易实现。,4,语义分析不像词法分析和语法分析那样可以分别用正规文法和上下文无关文法描述。由于语义是上下文有关的，因此语义的形式化描述是非常困难的。虽然语义的形式化工作已经有相当的进展，但由于语义的复杂性，使得语义分析不能像语法那样规范，到目前为止，语义的形式化描述并没有语法的形式化描述那样成熟，使得语义的描述处于一种自然语言的描述或者半形式化描述的状态。而没有基于数学抽象的形式化描述，就很难设计出基于数学模型的统一算法来实现语义分析器的自动生成。,5,目前较为常见的是用属性文法作为描述程序语言语义的工具，并采用语法制导翻译的方法完成对语法成分的翻译工作。,直观上讲，语法制导翻译法就是为每个产生式配上一个语义子程序，在语法分析过程中，在选用某个产生式的同时，执行该产生式所对应的语义子程序来进行翻译的一种办法。,6,8.1属性文法1、文法的属性,属性是指与文法符号的类型和值等有关的一些信息，在编译中用属性描述处理对象的特征。,【例】,判断变量X的类型是否匹配，要用X的数据类型来描述；判断变量X是否存在，要用X的存储位置来描述；而对变量X的运算，则要用X的值来描述；,因此，语义分析阶段引入X的属性，如X.type、X.place、X.val等来分别描述变量X的类型、存储位置以及值等不同的特征。,7,2、属性文法（属性翻译文法）,在上下文无关文法的基础上，为每个文法符号(终结符或非终结符)引入若干属性值（称为属性）。这些属性代表与文法符号相关信息，属性可以是类型、值、代码序列、符号表内容（入口）等。属性可计算或传递。属性的加工过程即是语义处理的过程。对于文法的每个产生式都配备了一组属性的计算规则，称为语义规则。,Knuth（克努特）在1968年首先提出属性文法,8,一个属性文法是一个三元组，A（G，V，F）。其中G表示一个上下文无关文法；V表示一个属性的有穷集；F表示属性的断言或谓词的有穷集,属性文法的形式定义,每个属性与某个文法符合X(终结符或非终结符)相关联，用“文法符合.属性”表示这种关联。每个断言与文法的某产生式相联。与一个文法规则相关联的断言也是这个文法规则式上定义的一组语义规则。,9,【例】一个简单表达式文法,EN(1)+N(2)|N(1)orN(2)Nnum|true|false可以得到关于类型检查的属性文法：EN(1)+N(2)N(1).type=intandN(2).type=intEN(1)orN(2)N(1).type=boolandN(2).type=boolNnumN.type=intNtrueN.type=boolNfalseN.type=bool,与每个非终结符N相连的有属性Type，要么是int，要么是bool.,与非终结符E的产生式相联的断言指明：两个N的属性必须相同。,10,输入串3+4的语法树,结点带有语义信息的语法树,11,综合属性用于“自下而上”传递信息。综合属性由相应语法分析树中结点的分枝结点(即子结点)属性计算得到，其传递方向与继承属性相反，即沿语法分析树向上传递，从分枝结点到根结点。,属性分类：继承属性与综合属性,12,设AX1X2Xn为一个产生式,这种属性叫做综合(Synthesized)属性适应：归约分析自底向上按照语义规则来计算各结点的综合属性值,A.s=f(c1,c2,ck)c1,c2,ck是X1，X2，Xn的属性A.s是从其子结点的属性值计算出来的,终结符只有综合属性，由词法分析器提供。,产生式左部符号的某些属性根据其右部符号的属性或自己的其它属性计算而得。,13,【例8.1】简单算术表达式求值的属性文法,产生式语义规则(1)SEprint(E.val)(2)EE(1)+TE.val:=E(1).val+T.val(3)ETE.val:=T.val(4)TT(1)*FT.val:=T(1).val*F.val(5)TT(1)T.val:=T(1).val(6)F(E)F.val:=E.val(7)FdigitF.val:=digit.lexval,14,上面的一组产生式中，每一个非终结符都有一个属性val来表示整型值，如E.val表示E的整型值，而digit.lexval则表示digit的整型内部值。与产生式关联的每一个语义规则的左部符号E、T、F等的属性值的计算由其各自相应的右部符号决定，这种属性也称为综合属性。与产生式SE关联的语义规则是一个函数print(E.val)，其功能是打印E产生式的值。S在语义规则中没有出现，可以理解为其属性是一个虚属性。,15,3*5+4的注释分析树,16,2.继承属性用于“自上而下”传递信息。继承属性由相应语法树中结点的父结点属性计算得到，沿语法树向下传递，由根结点到分枝(子)结点，它反映了对上下文依赖的特性。继承属性可以很方便地用来表示程序语言上下文的结构关系。,17,设AX1X2Xn为一个产生式,这种属性叫做继承(Inherited)属性,B.in=f(c1,c2,ck)B为Xi，c1,c2,ck是A，X1，X2，Xn的属性,在分析树中，一个节点的继承属性值是由该节点的父节点和(或)兄弟节点的属性决定的。非终结符可有综合属性也可有继承属性.但文法开始符号没有继承属性。根据依赖关系决定计算顺序,即文法产生式右部符号的某些属性根据其左部符号的属性和右部的其它符号的某些属性计算而得。,18,【例8.2】描述说明语句中各种变量类型信息的语义规则,产生式语义规则(1)DTLL.in=T.type(2)TintT.type=int(3)TfloatT.type=float(4)LL(1)，idL(1).in=L.in;addtype(id.entry,L.in)(5)Lidaddtype(id.entry,L.in),过程addtype的功能是把每个标识符的类型信息登录在符号表的相关项中,19,非终结符T有一个综合属性type，其值为int或float。语义规则L.in=T.type表示L.in的属性值由相应说明语句指定的类型T.type决定；属性L.in被确定后将随语法树的逐步生成而传递到下边的有关结点使用，这种结点属性称为继承属性。由此可见，标识符的类型可以通过继承属性的复写规则来传递。,20,例如，对输入串inta,b，根据上述的语义规则，可在其生成的语法树中看到用“”表示的属性传递情况，,21,8.2语法制导翻译概述,现在很多编译程序采用语法制导翻译方法。这仍不是一种形式系统，但它是比较接近形式化的。这种方法以属性文法为工具来说明程序设计语言的语义。一个属性文法包含一个上下文无关文法和一系列语义规则，这些语义规则附在文法的每个产生式上，在语法分析过程中，完成这些语义规则描述的动作，从而实现语义处理。,22,我们不对属性文法进行理论上的研究而仅仅将它做为工具描述语义分析。在编译的许多实际应用中，属性和断言以多种形式出现，也就是说，与每个文法符号相联的可以是各种属性、断言、以及语义规则，或者某种程序设计语言的程序段等等。,23,语法制导翻译技术分为自底向上和自顶向下语法制导翻译。我们重点介绍自底向上语法制导翻译。假定有一个自下而上的LR分析器，我们可以把这个LR分析器的能力加以扩大，使它能在用某个产生式进行归约的同时调用相应的语义子程序进行有关的翻译工作；每个产生式的语义子程序执行之后，某些结果(语义信息)必须作为此产生式的左部符号的语义值暂时保存下来，以便以后语义子程序引用这些信息。,24,作为一个例子，考虑下面的文法及语义动作所执行的程序：EE+E|E*E|(E)|digit,25,1、为文法的规则设计相应的语义子程序,产生式语义子程序1)EE(1)+E(2)E.val=E(1).val+E(2).val2)EE(1)*E(2)E.val=E(1).val*E(2).val3)E(E(1)E.val=E(1).val4)EdigitE.val=digit.lexval,26,产生式语义动作1)EE(1)+E(2)valTOP=valTOP+valTOP+22)EE(1)*E(2)valTOP=valTOP*valTOP+23)E(E(1)valTOP=valTOP+14)EdigitvalTOP=digit.lexval,27,2、文法的LR分析表,28,此外，原LR分析器的分析栈也加以扩充，以便能够存放与文法符号相对应的语义值。这样，分析栈可以存放三类信息：分析状态、文法符号及文法符号对应的语义值。扩充后的分析栈如图所示。,3、扩充分析栈,29,扩充分析栈工作的总控程序功能，使其在完成语法分析的同时也能完成语义分析工作(这时的语法分析栈已成为语义分析栈)；即在用某一个规则进行归约之后，调用相应的语义子程序完成与所用产生式相应的语义动作，并将每次工作后的语义值保存在扩充后的“语义值”栈中。,4、扩充总控程序的功能,30,算术表达式78*5#的语法树及各结点值,语义分析和计值过程,31,32,8.3中间语言,编译程序所使用的中间代码有多种形式。常见的有逆波兰记号、三元式、四元式和树形表示。,33,8.3.1逆波兰式（后缀式）,逆波兰记号是最简单的一种中间代码表示形式，早在编译程序出现之前，它就用于表示算术表达式，是波兰逻辑学家卢卡西维奇（Lukasiewicz）发明的。,这种表示法将运算对象写在前面，把运算符号写在后面，比如把a+b写成ab+，把a*b写成ab*，用这种表示法表示的表达式也称做后缀式。,34,后缀表示法表示表达式，其最大的优点是易于计算机处理表达式。常用的算法是使用一个栈，自左至右扫描算术表达式（后缀表示），每扫描到运算对象，就把它推进栈；扫描到运算符，若该运算符是二目的，则对栈顶部的两个运算对象实施该运算，并将运算结果代替这两个运算对象而进栈；若是一目运算符，则对栈顶元素执行该运算，并以运算结果代替该元素进栈，最后的结果留在栈顶。,35,【例】逆波兰式ab+c*的处理,a,b,+,T1,T1,c,*,T2,36,逆波兰式的形式定义,37,后缀表示中，操作数出现的顺序与原来一致，而运算符则按运算先后的顺序放入相应的操作数之后(即运算符先后的顺序发生了变化)。这种表示已不再需要用括号来规定运算的顺序了。,后缀表示中的计值用栈实现非常方便。一般的计值过程是自左至右扫描后缀表达式，每碰到运算量就把它推进栈，每碰到K目运算符就把它作用于栈顶的K个运算量，并用运算的结果(即一个运算量)来取代栈顶的K个运算量。,38,【例】,39,只要遵守运算对象后直接紧跟它们的运算符的规则即可。,逆波兰表示很容易扩充到表达式以外的范围,【比如】把转语句GOTOL写为“Ljump”，运算对象L为语句标号，运算符jump表示转到某个标号。【比如】条件语句ifEthenS1elseS2可表示为：ES1S2￥，把ifthenelse看成三目运算符，用￥来表示。【又如】数组元素A下标表达式1，下标表达式n可表示为下标表达式1下标表达式2下标表达式nAsubs，运算符Subs表示求数组的下标。,40,8.3.2三元式和树形表示1、三元式,每个三元式由三个主要部分和一个序号组成：(i)(op,arg1,arg2)其中：算符op，第一运算对象arg1和第二运算对象arg2。运算对象可能是源程序中的变量，也可能是某个三元式的结果，用三元式的编号表示。,三元式出现的先后次序与表达式的计算顺序一致。对于一目算符op，只需选用一个运算对象，不妨规定只用arg1。至于多目算符，可用若干个相继的三元式表示。,41,【例】表达式A+(-B)*c的三元式表示,(1)(,B,-)是单目运算符，使B取反(2)(*,(1),C)(3)(+,A,(2),42,【例】a:=b*c+b*d的三元式表示：,（1）（*，b，c）（2）（*，b，d）（3）（+，（1），（2）（4）（:=，（3），a）,与后缀式不同，三元式中含有对中间计算结果的显式引用，比如三元式（1）表示的是b*c的结果。三元式（3）中的（1）和（2）分别表示第一个三元式和第二个三元式的结果。,43,在三元式表示中，每个语句的位置同时有两个作用：一是可作为该三元式的结果被其它三元式引用；二是三元式位置顺序即为运算顺序。,三元式的序号,在代码优化阶段，调整三元式的运算顺序时会遇到困难，这是因为三元式中的arg1、arg2也可以是指向某些三元式位置的指针，当这些三元式的位置顺序发生变化时，含有指向这些三元式位置指针的相关三元式也需随之改变指针值。因此，变动一张三元式表是很困难的。,44,2、树形表示,抽象语法树也称图表示，是一种较为流行的中间语言表示形式。在抽象语法树表示中，每一个叶结点都表示诸如常量或变量这样的运算对象，而其它内部结点则表示运算符。,45,一个表达式中的简单变量或常量的树形表示就是该变量或常量自身。如果e1和e2的树分别为E1、E2，则-e1,e1+e2,e1*e2的树形表示如下：,-,E1,+,E1,E2,*,E1,E2,定义,46,多目运算符的树形表示,二目运算对应二叉子树，多目运算对应多叉子树，不过，为了便于安排存储空间，一棵多叉子树可以通过引进新结点而表示成一棵二叉子树。,例如，条件语句ifEthenS1elseS2可以看成一个三目运算，运算符￥定义为ifthenelse,￥,E,S2,S1,￥,E,New,S1,S2,引入一个新节点，使其转化为二叉树,47,8.3.3四元式和三地址代码,四元式是由四部分组成：(i)(op，arg1，arg2，result)其中，op为运算符；arg1、arg2为运算对象；result为运算结果。运算对象和运算结果可以是用户自己定义的变量也可以是编译程序引进的临时变量。我们约定：凡只需一个运算量的算符一律使用arg1。,48,【例】表达式c和赋值语句X=a的四元式,(i)(,C,Ti)(j)(=,a,X),49,【例】表达式X=a*b+c/d的四元式,(1)(*,a,b,T1)(2)(/,c,d,T2)(3)(+,T1,T2,T3)(4)(=,T3,X),50,如果op是一个算术或逻辑运算符，则result总是一个新引进的临时变量，它用来存放运算结果。四元式出现的顺序与表达式计值的顺序是一致的，四元式之间的联系是通过临时变量实现的。四元式由于其表示更接近程序设计的习惯而成为一种普遍采用的中间代码形式。,51,三地址代码的形式,三地址代码语句的一般形式为X=aopb其中，X、a和b为变量或编译时产生的临时变量，a、b还可以为常量；op为运算符，如浮点算符和逻辑运算符等。,三地址代码的每条语句通常包含三个地址，两个用来存放运算对象，一个用来存放运算结果。在实际实现中，用户定义的名字将由指向符号表中该名字项的指针所取代。,52,由于三地址语句只含有一个运算符，因此多个运算符组成的表达式必须用三地址语句序列来表示。,如表达式X=a*b+c/d的三地址代码为：(1)T1=a*b(2)T2=c/d(3)T3=T1+T2(4)X=T3,53,四元式：1)(-，C，D，T1)2)(*，B，T1，T2)3)(+，A，T2，T3)4)(-，C，D，T4)5)(，T4，N，T5)6)(/，E，T5，T6)7)(+，T3，T6，T7)三元式：1)(-，C，D)2)(*，B，(1)3)(+，A，(2)4)(-，C，D)5)(，(4)，N)6)(/，E，(5)7)(+，(3)，(6),举一个例子，用几种中间代码的形式来表示A+B*(C-D)+E/(C-D)N,54,8.4简单赋值语句的翻译,简单算术表达式是一种仅含简单变量的算术表达式；简单变量是指普通变量和常数，但不含数组元素及结构引用等复合型数据结构。简单算术表达式的计值顺序与四元式出现的顺序相同，因此很容易将其翻译成四元式形式，这些翻译方法稍加修改也可用于产生三元式形式。,55,翻译一般采取的步骤：,分析文法的特点。设置一系列语义变量，定义语义过程、语义函数。修改文法，写出每一规则的语义子程序。扩充LR分析栈，构造LR分析表,56,考虑以下文法GS：Sid:=EEE+EE*EE(E)id,非终结符S代表“赋值语句”。文法GS虽然是一个二义文法，但通过确定运算符的结合性及规定运算符的优先级就可避免二义性的发生。为了实现由表达式到四元式的翻译，需要给文法加上语义子程序，以便在进行归约的同时执行对应的语义子程序。语义子程序所涉及的语义变量、语义过程及函数说明如下：,57,语义子程序所涉及的语义变量、语义过程及函数说明,对非终结符E定义语义变量E.place，即用E.place表示存放E值的变量名在符号表中的入口地址或临时变量名的整数码。定义语义函数newtemp()，即每次调用newtemp()时都将回送一个代表新临时变量的整数码；临时变量名按产生的顺序可设为T1、T2、。定义语义过程emit(T=arg1oparg2),emit的功能是产生一个四元式并填入四元式表中。定义语义函数lookup()，其功能是审查是否出现在符号表中，是则返回在符号表的入口指针，否则返回nil。其中表示id代表的名字本身。,58,文法GS中的每一个产生式的语义子程序,(1)Sid:=Ep:=lookup();if(p=nil)error();elseemit(p=E.place);(2)EE(1)+E(2)E.place:=newtemp();emit(E.place:=E(1).place+E(2).place);(3)EE(1)*E(2)E.place:=newtemp();emit(E.place:=E(1).place*E(2).place);(4)EE(1)E.place:=newtemp();emit(E.place:=uminusE(1).place);(5)E(E(1)E.place:=E(1).place;(6)Eidp:=lookup();if(p!=nil)E.place:=p;elseerror();,59,【例】试分析赋值语句X=B*(C+D)的语法制导翻译过程。,60,61,算术表达式和赋值语句中的类型检查,实际上，在一个表达式中可能会出现各种不同类型的变量或常数，而不是假定为都是同一类型。也就是说，编译程序还应执行这样的语义动作：对表达式中的运算对象应进行类型检查，如不能接受不同类型的运算对象的混合运算，则应指出错误；如能接受混合运算，则应进行类型转换的语义处理。约定，当两个不同类型的量进行运算时，必须首先将整型量转换为实型量。,62,【例】设x,y为实型，i,j为整型，则表达式x=y+i*j的三地址码是：,T1=iint*jT3=inttorealT1T2=yreal+T3x=T2,为进行类型转换的语义处理，增加语义变量，用E.type表示E的类型信息，E.type的值或为int或为real；此外，为区别整型加（乘）和实型加（乘），把+分别写作int+和real+把*分别写作int*和real*用一目算符inttoreal表示将整型运算对象转换成实型。,63,EE1+E2的带语义检查的三地址码的语义动作,E.place=newtemp;ifE1.type=intandE2.type=intthenbeginemit(E.place=E1.placeint+E2.place);E.type=int;endelseifE1.type=realandE2.type=realthenbeginemit(E.place=E1.placereal+E2.place);E.type=real;endelseifE1.type=intandE2.type=realthenbeginu=newtemp;emit(u=inttorealE1.place);emit(E.place=ureal+E2.place);E.type=real;endelseifE1.type=realandE2.type=intthenbeginu=newtemp;emit(u=inttorealE2.place);emit(E.place=E1.placereal+u);E.type=real;endelseE.type=type_error;,64,8.5布尔表达式的翻译,有的语言，如PL/1，允许更通用的表达式，其中，对布尔运算、关系运算、算术运算的运算对象的类型可不区分布尔型或算术型，假定不同类型的变换工作将在需要时强制执行。,65,优先级,关系运算符的优先级相同，其运算优先级低于任何算术运算符。布尔运算符的运算顺序一般为、，且和服从左结合，布尔算符的运算优先级低于任何关系运算符(注意，此处的运算优先级约定不同于C语言)。,66,1、布尔表达式的翻译方法,布尔表达式的作用：1）计算逻辑值，2）用做改变控制流语句中的条件表达式，如在if-then，if-then-else，或是while-do语句中那样。,67,讨论下述文法GE生成的布尔表达式：EEEEEE(E)iiropi,计算布尔表达式的值一般有两种方法：,数值表示法：仿照算术表达式的计算，按照布尔表达式的运算顺序，步步计算出各部分的真假值，最后计算出整个表达式的值。假设逻辑值true用1表示，false用0表示采取某种优化措施，只计算部分表达式；例如要计算AB，若计算出A的值为1，那么B的值就无需再计算了，因为不管B的值为何结果，AB的值都为1。同理，在计算AB时若发现A值为0，则B值也无需计算，AB的值一定为0。,68,上述两种方法对于不包含布尔函数调用的表达式是没有什么差别的。但是，假若一个布尔式中含有布尔函数调用，并且这种函数调用引起副作用（如有对全局量的赋值）时，这两种方法未必等价。采用哪种方法取决于程序设计语言的语义，有些语言规定，函数过程调用应不影响这个调用处环境的计值，或者说，函数过程的工作不许产生副作用，在这种规定下，可以任选其中一种。,副作用的考虑,69,数值表示法,布尔表达式1or（0andnot0）and1的计算过程是：1or（0andnot0）and11or（0and1）and11or0and11or01,70,布尔表达式abc翻译成的四元式序列为：（1）t1=c（2）t2=bt1（3）t3=at2对于像ab这样的关系表达式，可看成等价的条件语句ifabthen1else0，它翻译成的四元式序列为：（1）ifabgoto（4）（2）t=0（3）goto（5）（4）t=1（5）其中用临时变量t存放布尔表达式ab的值，(5)为后续的四元式序号。,【例】,71,数值表示法,nextstat给出输出序列中下一四元式序号，emit过程每被调用一次，nextstat增加1。,EE1E2E.place=newtemp;emit(E.place=E1.placeE2.place);EE1E2E.place=newtemp;emit(E.place=E1.placeE2.place);EE1E.place=newtemp;emit(E.place=E1.place);E(E1)E.place=E1.place;Ei1ropi2E.place=newtemp;emit(ifi1.placeropi2.placegotonextstat+3);emit(E.place=0);emit(gotonextstat+2);emit(E.place=1);EidE.place=id.place;,72,【例】根据数值表示法对布尔表达式abcdef翻译为三地址代码.,100ifabgoto103101T1=0102goto104103T1=1104ifcdgoto107105T2=0106goto108107T2=1108ifefgoto111109T3=0110goto112111T3=1112T4=T2T3113T5=T1T4,73,采取某种优化措施,用if-then-else来解释布尔运算、AB解释为ifAthenBelsefalseAB解释为ifAthentrueelseBA解释为ifAthenfalseelsetrue,74,2、控制语句中布尔表达式的翻译,现在讨论出现在ifthen；ifthenelse和whiledo等语句中的布尔表达式E的翻译。这三种语句的语法为：SifEthenS1SifEthenS1elseS2SwhileEdoS1这时表达式不仅仅是计算值，而且值还决定了程序控制流的转向。,75,真,假,：,76,出现在语句ifEthenS1elseS2中的布尔表达式，它们的作用仅在于控制语句的选择。只要能够完成这个使命，E的值就无需最终保留在某个临时单元中。因此作为转移条件的布尔表达式E，可以赋予它两个“出口”一是“真”出口，它指向E为真时的指向，出向S1一是“假”出口，它指向E为假时的指向，出向S2,77,定义一组控制转向的四元式,(1)(ifEgotoLi)表示当E为真时，执行标号为Li的四元式，Li是布尔表达式E的“真”出口。(2)(ifE(1)ropE(2）gotoLi)表示当E(1)ropE(2）为真时，执行标号为Li的四元式，(3)(gotoLj)表示无条件转向标号为Lj的四元式，通常用来表示当E为假时程序流的转向，因此又称为“假”出口。,78,【例】语句ifabthens,(1)(ifabgotoLi)(2)(gotoLj)(3)Li:S的第一个四元式,79,分析语句ifabcthenS1elseS2,(1)ifabgoto(5)(2)goto(3)(3)ifcgoto(5)(4)goto(p+1)(5)关于S1的四元式序列.(p)goto(q)(p+1)关于S2的四元式序列.(q)后继四元式,(5)是真出口，但在生成(1)和(3)时，这个值是未知的。,(p+1)是假出口，但在生成(4)时，这个值也是未知的。,什么时候可以确定“真”出口这个值？什么时候可以确定“假”出口这个值？,处理到then处理到else,80,语句whileEdoS,(1)ifEgoto(3)(2)goto(p+1)(3)关于S的四元式序列.(p)goto(1)(p+1)后继四元式,(p+1)是假出口，但在生成(2)时，这个值是未知的。,81,在有多个因子组成的布尔表达式中，可能有多个因子的真出口和假出口的转移去向相同，但又不能立刻知道它们的具体转移位置。在这种情况下，需要把这些转移方向相同的四元式链在一起，一旦发现转移目标就可以回填。在生成用做控制条件的布尔表达式E时，就有两条链需要回填：1条是E的真出口，用E.true表示1条是E的假出口，用E.false表示,82,83,语句ifabcthenS1elseS2的回填描述,(1)ifabgoto(0)/E的一个真出口，有待回填(2)goto(3)/回填E的第一个假出口(3)ifcgoto(1)/(3)是E的真出口链头(4)goto(0)/E的一个假出口，有待回填(5)关于S1的四元式序列/此时回填真出口.(p)goto(0)/有待回填(p+1)关于S2的四元式序列/此时回填假出口.(q)后继四元式/此时回填q,(1),E.true,E.false,(1)ifabgoto(0),(3)ifcgoto(1),(4)goto(0),84,它应该有下面的代码序列：E(1).codeE(1).false:E(2).code,考虑表达式EE(1)E(2)若E(1)为真，则立即知道E也为真，因此，E(1)的真出口也就是整个E的真出口；若E(1)为假，则E(2)必须被计值，此时E(2)的第一个四元式就是E(1)的假出口。当然，E(2)的真假出口也就是整个E的真假出口。,E.true=E(1).true=E(2).trueE.false=E(2).falseE(1).false=E(2)第一个四元式,85,它应该有下面的代码序列：E(1).codeE(1).true:E(2).code,考虑表达式EE(1)E(2)若E(1)为假，则立即知道E也为假，因此，E(1)的假出口也就是整个E的假出口；若E(1)为真，则E(2)必须被计值，此时E(2)的第一个四元式就是E(1)的真出口。当然，E(2)的真假出口也就是整个E的真假出口。,E.false=E(1).false=E(2).falseE.true=E(2).trueE(1).true=E(2)第一个四元式,86,考虑表达式EE(1)若E(1)为假，则E为真，因此，E(1)的假出口是E的真出口；若E(1)为真，则E为假，因此，E(1)的真出口是E的假出口。,E.false=E(1).trueE.true=E(1).false,87,需要的公共变量、过程、函数,四元式指针nextstat：始终指向下一条将要产生的四元式的地址(序号)，其初值为1。每当执行一次emit语句后，nextstat自动增1。设置非终结符E的语义变量E.codebegin：表示非终结符E的第一个四元式标号。回填过程Backpatch(p,t)：把链首p所链接的每个四元式的第四区段(即result)都改写为地址t。链接函数merge(p1,p2)：把以p1和p2为链首的两条链合并为一条以p2为链首的链(即返回链首值p2)。,88,每个规则的语义子程序,(1)EiE.true=nextstat;E.false=nextstat+1;E.codebegin=nextstat;emit(ifi.placegoto0);emit(goto0);(2)Ei(1)ropi(2)E.true=nextstat;E.false=nextstat+1;E.codebegin=nextstat;emit(ifi(1).placeropi(2).placegoto0);emit(goto0);(3)E(E(1)E.true=E(1).true;E.false=E(1).false;E.codebegin=E(1).codebegin;(4)EE(1)E.true=E(1).false;E.false=E(1).true;E.codebegin=E(1).codebegin;,89,(5)EE(1)E(2)Backpatch(E(1).false，E(2).codebegin);E.codebegin=E(1).codebegin;E.true=merge(E(1).true，E(2).true);E.false=E(2).false;(6)EE(1)E(2)Backpatch(E(1).true，E(2).codebegin);E.codebegin=E(1).codebegin;E.true=E(2).true;E.false=merge(E(1).fasle，E(2).false);,90,EE(1)E(2)的分析,当E(1)为假时,计算E(2)，所以E(2)的第一个四元式地址E(2).codebegin回填为E(1)的假链值，Backpatch(E(1).false，E(2).codebegin);当E(1)为真时,无需计算E(2)，应该去执行S1的第一个四元式，但此时尚未扫描到then，因此，保留E(1).true；若E(2)为真，其转移地址同E(1)，所以将E(1)和E(2)回填真链E(1).true和E(2).true合并为一条链，E.true=merge(E(1).true，E(2).true);新链首作为E.true的值。,91,当E(1)为假时,计算E(2)，E(2)也为假，此时，这个布尔表达式为假，E(2).false就是E.false，尽管有两个变量E(1)和E(2)参加运算，但按扫描顺序，首先生成E(1)的四元式；因此E(1)的第一个四元式也就是整个布尔表达式的第一个四元式，所以E.codebegin=E(1).codebegin;,92,【例】表达式ABD的翻译,nextstat=1赋初值1、扫描到A，用Ei进行归约，执行相应语义子程序,E.true=nextstat;E.false=nextstat+1;E.codebegin=nextstat;emit(ifi.placegoto0);emit(goto0);,E.true=1;E.false=2;E.codebegin=1;四元式:(1)(ifAgoto0)(2)(goto0),nextstat的值为3,93,2、继续扫描，栈内符号串为EBD，栈顶形成句柄BD，用Ei(1)ropi(2)进行归约，执行相应语义子程序,E.true=nextstat;E.false=nextstat+1;E.codebegin=nextstat;emit(ifi(1).placeropi(2).placegoto0);emit(goto0);,E.true=3;E.false=4;E.codebegin=3;四元式:(3)(ifBDgoto0)(4)(goto0),nextq的值为5,94,3、继续归约，栈内符号串为EE，形成句柄，用EE(1)E(2)进行归约，执行相应语义子程序。,Backpatch(E(1).false，E(2).codebegin);E.codebegin=E(1).codebegin;E.true=merge(E(1).true，E(2).true);E.false=E(2).false;,E.bcode=3;E.true=3;E.false=4;,95,(1)(ifAgoto0)E(1).false(2)(goto0)(3)(3)(ifBDgoto0)(4)(goto0),回填操作Backpatch(E(1).false，E(2).codebegin);,E(1).true(1)(ifAgoto0)(2)(goto3)E(2).true(3)(ifBDgoto0)(1)(4)(goto0),合并操作E.true=merge(E(1).true，E(2).true);,这是翻译结果,96,8.4.3控制语句的翻译,在源程序中，控制语句用于实现程序流程的控制。一般程序流程控制可分为下面三种基本结构：(1)顺序结构，一般用复合语句实现；(2)选择结构，用if和case等语句实现；(3)循环结构，用for、while、do(即repeat)等语句实现。,97,控制语句的文法,考虑ifthen，ifthenelse和whiledo语句文法GS定义这些语句：GS:（1）SifEthenS（2）SifEthenSelseS（3）SwhileEdoS（4）SA（5）LL；S（6）LS其中各非终结符号的意义是：S-语句L-语句串A-赋值句E-布尔表达式,98,条件语句if的翻译,按下面的条件语句if的模式进行讨论：ifEthenS1elseS2布尔表达式E的作用仅在于控制对S1和S2的选择，因此可将作为转移条件的布尔式E赋予两种“出口”：一是“真”出口，出向S1；一是“假”出口，出向S2。,99,非终结符E具有两项语义值E.true和E.false，它们分别指出了尚待回填真假出口的四元式串。,E的“真”出口只有在扫描完布尔表达式E后的“then”时才能知道，E的“假”出口则需要处理过S1之后并且到else时才能明确。这就是说，必须把E.false的值传下去，以便到达相应的else时才进行回填。,S1语句执行完就意味着整个if-then-else语句也已执行完毕，因此，在S1的编码之后应产生一条无条件转移指令，这条转移指令将导致程序控制离开整个if-then-else语句。,100,但是，在完成S2的翻译之前，这条无条件转移指令的转移目标是不知道的，甚至在翻译完S2之后仍无法确定，这种情形是由语句的嵌套性所引起的。,【例如下面的语句】：ifE1thenifE2S1thenelseS2elseS3在S1代码之后的那条无条件转移指令不仅应跨越S2，而且应跨越S3。这也就是说，转移目标的确定和语句所处的环境密切相关。,因此仿照处理布尔表达式的办法，让非终结符S（和L）含有一项语义值S.CHAIN（和L.CHAIN）。也是一条链，它把所有那些四元式串在一起，这些四元式期待在翻译完S（L）之后回填转移目标。真正的回填工作将在处理S的外层环境的某一适当时候完成。,101,条件语句if的文法和语义子程序的设计,条件语句if的文法GS如下：GS：SifEthenS(1)SifEthenS(1)elseS(2)为了在扫描条件语句过程中不失时机地处理和回填有关信息，可将GS改写为如下的GS：GS：(1)SCS(1)(2)CifEthen(3)STPS(2)(4)TPCS(1)else,102,E的“真”出口的处理：首先用产生式(2)CifEthen进行归约，这时E的真出口即为E所生成四元式序列后的下一个地址。因此，将“then”后的第一个四元式地址(即nextstat)回填至E的真出口地址。E的“假”出口的处理：E的假出口地址则作为待填信息放在C的语义变量C.chain中。语义子程序CifEthenBackpatch(E.true,nextstat);C.chain=E.false;,CifEthen的翻译,103,接下来用产生式(1)SCS(1)继续向上归约。这时已经处理到SifEthenS(1)，由于归约时E的真出口已经处理，而E的假出口(即语句S的出口)同时是语句S(1)的出口，但此时语句S的出口地址未定，故将C.chain和S(1).chain一起作为S的待填信息链用函数merge链在一起保留在S的语义值S.chain中，即有SCS(1)S.chain=merge(C.chain,S(1).chain);如果此时条件语句为不含else的条件句，则在产生式(1)、(2)归约为S后即可以用下一个将要产生的四元式地址(即S的出口地址)来回填S的出口地址链(即S.chain)；如果此时条件语句为if-tnen-else形式，则继续用产生式(4)TPCS(1)else归约。,SCS(1)的翻译,104,TpCS(1)else的翻译,用TpCS(1)else归约时首先产生S(1)语句序列之后的一个无条件转移四元式(以便跳过S(2)，该四元式的地址保留在q中，以便待获知要转移的地址后再进行回填，也即：(i)(S(1)的第一个四元式)/E的真出口.(q1)(S(1)的最后一个四元式)(q)(goto0)/转移地址有待回填(q+1)(S(2)的第一个四元式)/E的假出口,105,此时q的出口也就是整个条件语句的出口，因此应将其与S.chain链接后挂入链头为Tp.chain的链中。此外，emit产生四元式q后nextstat自动加1(即为q+1)，其地址即为else后(也即S(2)的第一个四元式地址，它也是E的假出口地址，因此应将此地址回填到E.false即C.chain中，即有：TPCS(1)elseq=nextstat;emit(goto0);Backpatch(C.chain,nextstat);TP.chain=merge(S.chain,q);,106,STPS(2)的翻译,当S(2)语句序列处理完后继续翻译if语句之后的后继语句，这时就有了后继语句的四元式地址，该地址也是整个if语句的出口地址，它与S(2)语句序列的出口一致。由于S(2)的出口待填信息在S(2).chain中，故将TP.chain与S(2).chain链接后挂入链头为S.chain的链中，即STPS(2)S.chain=merge(TP.chain,S(2).chain);,107,循环语句while的文法和语义子程序设计,给出及时处理和回填的循环语句while的文法GS如下：GS：(1)SWdS(1)(2)WdWEdo(3)Wwhile,108,Wwhile的翻译,根据while语句的扫描加工顺序，首先用产生式(3)Wwhi