编译原理(第四版)第4章-语义分析和中间代码生成.ppt

,第,4章语义分析和中间代码生成,第,4,章语义分析和中间代码生成,4.1 概述,4.2 属性文法,4.3 几种常见的中间语言,4.4 表达式及赋值语句的翻译,4.5 控制语句的翻译,4.6 数组元素的翻译,4.7 过程或函数调用语句的翻译,4.8 说明语句的翻译,4.9 递归下降语法制导翻译方法简介,4.1 概 述,4.1.1 语义分析的概念,一个源程序经过词法分析、语法分析之后，表明该源程序在书写上是正确的，并且符合程序语言所规定的语法。但是语法分析并未对程序内部的逻辑含义加以分析，因此编译程序接下来的工作是语义分析，即审查每个语法成分的静态语义。如果静态语义正确，则生成与该语言成分等效的中间代码，或者直接生成目标代码。直接生成机器语言或汇编语言形式的目标代码的优点是编译时间短且无需中间代码到目标代码的翻译，而中间代码的优点是使编译结构在逻辑上更为简单明确，特别是使目标代码的优化比较容易实现。,如同在进行词法分析、语法分析的同时也进行着词法检查、语法检查一样，在语义分析时也必然要进行语义检查。动态语义检查需要生成相应的目标代码，它是在运行时进行的；静态语义检查是在编译时完成的，它涉及以下几个方面：,(1)类型检查，如参与运算的操作数其类型应相容。,(2)控制流检查，用以保证控制语句有合法的转向点。如C语言中不允许goto语句转入case语句流；break语句需寻找包含它的最小switch、while或for语句方可找到转向点，否则出错。,(3)一致性检查，如在相同作用域中标识符只能说明一次，case语句的标号不能相同等。,语义分析阶段只产生中间代码而不生成目标代码的方法使编译程序的开发变得较为容易，但语义分析不像词法分析和语法分析那样可以分别用正规文法和上下文无关文法描述。由于语义是上下文有关的，因此语义的形式化描述是非常困难的，目前较为常见的是用属性文法作为描述程序语言语义的工具，并采用语法制导翻译的方法完成对语法成分的翻译工作。,假定有一个自底向上的LR分析器，我们可以把这个LR分析器的能力加以扩大，使它能在用某个产生式进行归约的同时调用相应的语义子程序进行有关的翻译工作。每个产生式的语义子程序执行之后，某些结果（语义信息）必须作为此产生式的左部符号的语义值暂时保存下来，以便以后语义子程序引用这些信息。,此外，原LR分析器的分析栈也加以扩充，以便能够存放与文法符号相对应的语义值。这样，分析栈可以存放三类信息：分析状态、文法符号及文法符号对应的语义值。扩充后的分析栈如图4-1所示。,图,41,扩充后的,LR,分析栈,作为一个例子，我们考虑下面的文法及语义动作所执行的程序：,产生式语义动作,（0）SE 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）Ei valTOP=lexval(注：lexval为i的整型内部值),这个文法的LR分析表见表3.20。,图,42 语法制导翻译计算表达式79*5#的语法树,例如，判断变量X的类型是否匹配，要用X的数据类型来描述；判断变量X是否存在，要用X的存储位置来描述；而对X的运算，则要用X的值来描述。因此，语义分析阶段引入X的属性，如X.type、X.place、X.val等来分别描述变量X的类型、存储位置以及值等不同的特征。,4.2.2 属性文法,属性文法是一种适用于定义语义的特殊文法，即在语言的文法中增加了属性的文法，它将文法符号的语义以“属性”的形式附加到各个文法的符号上（如上述与变量X相关联的属性X.type、X.place和X.val等），再根据产生式所包含的含义，给出每个文法符号属性的求值规则，从而形成一种带有语义属性的上下文无关文法，即属性文法。属性文法也是一种翻译文法，属性有助于更详细地指定文法中的代码生成动作。,例如，简单算术表达式求值的属性文法如下：,产生式语义规则,（1）SE print(E.val),（2）EE(1)+T E.val=E(1).val+T.val,（3）ET E.val=T.val,（4）TT(1)*F T.val=T(1).val*F.val,（5）TT(1)T.val=T(1).val,（6）F(E)F.val=E.val,（7）Fi F.val=i.lexval,我们再举一例说明属性文法。一简单变量类型说明的文法GD如下：,GD：Dint Lfloat L,LL,idid,其对应的属性文法为,（1）DTL L.in=T.type,（2）Tint T.type=int,（3）Tfloat T.type=float,（4）LL(1)，id L(1).in=L.in;addtype(id.entry,L.in),（5）Lid addtype(id.entry,L.in),注意到与文法GD相应的说明语句形式可为,int id1，id2，idn 或者 float id1，id2，idn,为了把扫描到的每一个标识符id都能及时地填入符号表中，而不必等到待所有标识符都扫描完后再归约为一个标识符表，可以将文法GD改写为属性文法，并在与之关联的语义规则中，用函数addtype把每个标识符id的类型信息（由L.in继承得到）登录在符号表的相关项id.entry中。,非终结符,T有一个综合属性type，其值为int或float。语义规则L.in=T.type表示L.in的属性值由相应说明语句指定的类型T.type决定。属性L.in被确定后将随语法树的逐步生成而传递到下边的有关结点使用，这种结点属性称为继承属性。由此可见，标识符的类型可以通过继承属性的复写规则来传递。例如，对输入串int a,b，根据上述的语义规则，可在其生成的语法树中看到用“”表示的属性传递情况，如图4-3所示。,图,43 属性信息传递情况示意,4.3 几种常见的中间语言,4.3.1 抽象语法树,抽象语法树也称图表示，是一种较为流行的中间语言表示形式。在抽象语法树表示中，每一个叶结点都表示诸如常量或变量这样的运算对象，而其它内部结点则表示运算符。抽象语法树不同于前述的语法树，它展示了一个操作过程并同时描述了源程序的层次结构。,注意：语法规则中包含的某些符号可能起标点符号作用也可能起解释作用。如赋值语句语法规则：,SV=e,（1）赋值语句：左部 表达式,（2）条件语句：表达式 语句1 语句2,与抽象语法相对应的语法树称为抽象语法树或抽象树，如赋值语句x=ab*c的抽象语法树如图4-4(a)所示，而图4-4(b)则是该赋值语句的普通语法树。,图,44 x=ab*c的语法树,(a)抽象语法树；(b)普通语法树图,抽象语法树的一个显著特点是结构紧凑，容易构造且结点数较少。图,44(b)所示的普通语法树的结点为14个；而图44(a)所示的抽象语法树的结点仅有7个，且每个内部结点最多只有两个分支，因此可以将每个赋值语句或表达式表示为一棵二叉树。对于含有多元运算的更为复杂的语法成分，相应的抽象语法树则为一棵多叉树，但我们总可以将其转变为一棵二叉树。,（,3）如果E为(E1)形式，则E1的后缀表示即为E的后缀表示。,上述递归定义的实质是：后缀表示中，操作数出现的顺序与原来一致，而运算符则按运算先后的顺序放入相应的操作数之后（即运算符先后的顺序发生了变化）。这种表示已不再需要用括号来规定运算的顺序了。后缀表示中的计值用栈实现非常方便。一般的计值过程是自左至右扫描后缀表达式，每碰到运算量就把它推进栈，每碰到K目运算符就把它作用于栈顶的K个运算量，并用运算的结果（即一个运算量）来取代栈顶的K个运算量。,2程序语句的逆波兰表示,为了用逆波兰式表示一些控制语句，我们定义转移操作如下：,（1）BL：转向某标号；,（2）BT：条件为真时转移；,（3）BF：条件为假时转移；,（4）BR：无条件转移。,部分程序语句的逆波兰表示如下：,（1）赋值语句。赋值语句“=”的逆波兰表示为,=,例如，赋值语句“x=a+b*c”可按逆波兰式写为“xabc*+=”。,（2）GOTO语句。转向语句“GOTO”的逆波兰表示为,BL,其中，“BL”为单目后缀运算符，“”则为BL的一个运算分量。,（3）条件语句。BR表示无条件转移单目后缀运算符。例如，“BR”表示无条件转移到“”处，这里的顺序号是BR的一个特殊运算分量，用来表示逆波兰式中单词符号的顺序号（即第几个单词），它不同于GOTO语句中的语句标号。BT和BF表示按条件转移的两个双目后缀运算符。例如：,BT,BF,分别表示当e为真或假时转移到顺序号处。其中，布尔表达式e的逆波兰式和顺序号是两个特殊的运算分量。若使用BT和BF两个运算符，则条件语句if(e)S1;else S2的逆波兰式为,BF /e为假则转到S2的第一个单词的顺序号处,/e为真则执行S1,BR /S1执行结束后无条件转出该条件语句,例如，条件语句,if(mn)k=i+1；else k=i1的逆波兰式表示为（1）（18）为单词编号）,（1）mn,（4）13BF,（6）ki1+=,（11）18BR,（13）ki1=,（18）if语句的后继语句,此逆波兰式也可写在一行上，即mn13BFki1+=18BRki1=,（4）循环语句。for循环语句为for(i=m；i=n；i+)S。其中，i为循环控制变量，m为初值，n为终值，S为循环体。循环语句不能直接用逆波兰表示，因而将其展开为等价的条件语句后再用逆波兰表示，即,i=m；,10：if(i=等。若x和y满足关系rop就转去执行标号为L的语句，否则继续按顺序执行本语句的下一条语句。,（6）过程调用语句par X和call P,n。源程序中的过程调用语句P(X1,X2,Xn)可用下列三地址代码表示：,par X1,par X2,par Xn,call P,n,其中，整数n为实参个数。,过程返回语句为return y，其中y为过程返回值。,（7）变址赋值语句x=yi，其中x、y、i均代表数据对象，表示把从地址y开始的第i个地址单元中的值赋给x。xi=y则表示把y的值赋给从地址x开始的第i个地址单元。,（8）地址和指针赋值语句 x=&y表示将y的地址赋给x，y可以是一个名字或一个临时变量，而x是指针名或临时变量；x=*y表示将y所指示的地址单元中的内容（值）赋给x，y是一个指针或临时变量；*x=y表示将x所指对象的值置为y的值。,3三地址代码的具体实现,三地址代码是中间代码的一种抽象形式。在编译程序中，三地址代码语言的具体实现通常有三种表示方法：四元式、三元式和间接三元式。,（1）四元式,四元式是具有四个域的记录（即结构体）结构，这四个域为,(op,arg1,arg2,result),其中，op为运算符；arg1、arg2及result为指针，它们可指向有关名字在符号表中的登记项或一临时变量（也可空缺）。常用的三地址语句与相应的四元式对应如下：,x=y op z 对应(op,y,z,x),x=y 对应(uminus,y,_,x),x=y 对应(=,y,_,x),par x1 对应(par,x1,_,_),call P 对应(call,_,_,P),goto L 对应(j,_,_,L),if x rop y goto L 对应(jrop,x,y,L),例如，赋值语句a=b*(c+d)相应的四元式代码为,(+,c,d,t1),(*,b,t1,t2),(=,t2,_,a),我们约定：凡只需一个运算量的算符一律使用arg1。此外，注意这样一个规则：如果op是一个算术或逻辑运算符，则result总是一个新引进的临时变量，它用来存放运算结果。由上例也可看出，四元式出现的顺序与表达式计值的顺序是一致的，四元式之间的联系是通过临时变量实现的。四元式由于其表示更接近程序设计的习惯而成为一种普遍采用的中间代码形式。,（2）三元式,三元式是具有三个域的记录结构，这三个域为,(op,arg1,arg2),其中，op为运算符；arg1、arg2既可指向有关名字在符号表中的登记项或临时变量，也可以指向三元式表中的某一个三元式。例如，相应于赋值语句a=(b+c)*(b+c)的三元式代码为,(+,b,c),(+,b,c),(*,),(=,a,),上述三元式表示的结果与的结果相乘。由上例可知，三元式出现的先后顺序和表达式各部分的计值顺序是一致的。,（3）间接三元式,在三元式代码表的基础上另设一张表，该表按运算的次序列出相应三元式在三元式表中的位置，这张表称为间接码表。三元式表只记录不同的三元式语句，而间接码表则表示由这些语句组成的运算次序。例如，赋值语句a=(b+c)*(b+c)对应的三元式表与间接码表为,三元式表：(+,b,c),(*,),(=,a,),间接码表：,在三元式表示中，每个语句的位置同时有两个作用：一是可作为该三元式的结果被其它三元式引用；二是三元式位置顺序即为运算顺序。在代码优化阶段，当需要调整三元式的运算顺序时会遇到困难，这是因为三元式中的arg1、arg2也可以是指向某些三元式位置的指针，当这些三元式的位置顺序发生变化时，含有指向这些三元式位置指针的相关三元式也需随之改变指针值。因此，变动一张三元式表是很困难的。,对四元式来说，引用另一语句的结果可以通过引用该语句的,result（通常是一个临时变量）来实现，而间接三元式则通过间接码表来描述语句的运算次序。这两种方法都不存在语句位置同时具有两种功能的现象，代码调整时要做的改动只是局部的。因此，当需要对中间代码表进行优化处理时，四元式与间接三元式都比三元式方便得多。,4.4 表达式及赋值语句的翻译,4.4.1 简单算术表达式和赋值语句的翻译,简单算术表达式是一种仅含简单变量的算术表达式。简单变量是指普通变量和常数，但不含数组元素及结构体成员引用等复合型数据结构。简单算术表达式的计值顺序与四元式出现的顺序相同，因此很容易将其翻译成四元式形式，这些翻译方法稍加修改也可用于产生三元式或间接三元式。,考虑以下文法GA：Ai=E,EE+EE*EE(E)i,在此，非终结符A代表“赋值句”。文法GA虽然是一个二义文法，但通过确定运算符的结合性及规定运算符的优先级就可避免二义性的发生。,为了实现由表达式到四元式的翻译，需要给文法加上语义子程序，以便在进行归约的同时执行对应的语义子程序。语义子程序所涉及的语义变量、语义函数说明如下：,（1）对非终结符E定义语义变量E.place，即用E.place表示存放E值的变量名在符号表中的入口地址或临时变量名的整数码。,（2）定义语义函数newtemp()，即每次调用newtemp()时都将回送一个代表新临时变量的整数码；临时变量名按产生的顺序可设为T1、T2、。,（,3）定义语义函数emit(op,arg1,arg2,result)，emit的功能是产生一个四元式并填入四元式表中。,（4）定义语义函数lookup(i.name)，其功能是审查i.name是否出现在符号表中，是则返回i.name在符号表的入口指针，否则返回NULL。,使用上述语义变量和函数，可写出文法GA中的每一个产生式的语义子程序。,（1）Ai=E p=lookup(i.name);,if(p=NULL)error();,else emit(=,E.place,_,P);,（2）EE(1)+E(2)E.place=newtemp();emit(+,E(1).place,E(2).place,E.place);,（3）EE(1)*E(2)E.place=newtemp();emit(*,E(1).place,E(2).place,E.place);,（4）EE(1)E.place=newtemp();,emit(uminus,E(1).place,_,E.place);,（5）E(E(1)E.place=E(1).place;,（6）Ei p=lookup(i.name);,if(p!=NULL)E.place=p;,/另一种表示为E.place=entry(i),else error();,例4.2 试分析赋值语句X=B*(C+D)的语法制导翻译过程。,解答 赋值语句X=B*(C+D)的语法制导翻译过程如表4.2所示（加工分析过程参考表4.1）。,4.4.2 布尔表达式的翻译,在程序语言中，布尔表达式一般由运算符与运算对象组成。布尔表达式的运算符为布尔运算符，即、，或为,not、and和or（注：C语言中为！、&和|），其运算对象为布尔变量，也可为常量或关系表达式。关系表达式的运算对象为算术表达式，其运算符为关系运算符=、等。关系运算符的优先级相同但不得结合，其运算优先级低于任何算术运算符。布尔运算符的运算顺序一般为、，且和服从左结合。布尔算符的运算优先级低于任何关系运算符（注意，此处的运算优先级约定不同于C语言）。,此外，对布尔运算、关系运算、算术运算的运算对象的类型可不区分布尔型或算术型，假定不同类型的变换工作将在需要时强制执行。为简单起见，我们遵循以上运算约定讨论下述文法,GE生成的布尔表达式：,GE：EEEEEE(E)i rop ii,注意：布尔表达式在程序语言中不仅用作计算布尔值，还作为控制语句（如,if-else、while等）的条件表达式，用以确定程序的控制流向。无论布尔表达式的作用如何，按照程序执行的顺序，都必须先计算出布尔表达式的值。此外，rop代表六个关系运算符。,计算布尔表达式的值通常有两种方法。第一种方法是仿照计算算术表达式的方法，按布尔表达式的运算顺序一步步地计算出真假值来。假定逻辑值,true用1表示、false用0表示，则布尔表达式1(00)0值的计算过程为,1(00)0,=1(10)0,=100,=10,=1,另一种方法是根据布尔运算的特点实施某种优化，即不必一步一步地计算布尔表达式中所有运算对象的值，而是省略不影响运算结果的运算。例如，在计算,AB时，若计算出的A值为1，则B值就无需再计算了；因为不管B的结果是什么，AB的值都为1。同理，在计算AB时若发现A值为0，则B值也无需计算，AB的值一定为0。,注意：上述优化措施在布尔表达式含有布尔函数调用且函数调用引起副作用(指对全局量的赋值)时就会出现问题。如下面的两个等效的C语言程序，因其布尔表达式书写的顺序不同而得到不同的结果：,（1）include“stdio.h”,int p;,int f(),p=0;,return(0);,void main(),p=1;,if(p|f()printf(“True!n”);else printf(“False!n”);,（2）include“stdio.h”,int p;int f(),p=0;,return(0);,void main(),p=1;,if(f()|p)printf(“True!n”);,else printf(“False!n”);,在后面的论述中，我们假定函数过程的工作不出现上述的副作用情况。,如何确定一个表达式的真假出口呢？考虑表达式,E(1)E(2)，若E(1)为真，则立即知道E也为真，因此，E(1)的真出口也就是整个E的真出口；若E(1)为假，则E(2)必须被计值，此时E(2)的第一个四元式就是E(1)的假出口。当然，E(2)的真假出口也就是整个E的真假出口。类似的考虑适用于对E(1)E(2)的翻译。我们将E(1)E(2)和E(1)E(2)的翻译用图4-5表示，而对形如E(1)的表达式则只需调换E(1)的真假出口就可得到该表达式E的真假出口。,图,45 E,(1),E,(2),和,E,(1),E,(2),的翻译图,(a)E,(1),E,(2),；,(b)E,(1),E,(2),在自底向上的分析过程中，一个布尔式的真假出口往往不能在产生四元式的同时就填上，我们只好把这种未完成的四元式的地址（编号）作为,E的语义值暂存起来，待整个表达式的四元式产生完毕之后，再来填写这个未填入的转移目标。,对于每个非终结符E，我们需要为它赋予两个语义值E.tc和E.fc，以分别记录E所对应的四元式需要回填“真”、“假”出口的四元式地址所构成的链。这是因为在翻译过程中，常常会出现若干转移四元式转向同一个目标但目标位置又未确定的情况，此时可用“拉链”的方法将这些四元式链接起来，待获得转移目标的四元式地址时再进行返填。例如，假定E的四元式需要回填“真”出口的有p、q、r这三个四元式，则它们可链接成如图4-6所示的一条真值链（记作tc）。,图,46 拉链法链接四元式示意,为了处理E.tc和E.fc这两项语义值，我们需要引入如下的语义变量和函数：,（1）nxq：始终指向下一条将要产生的四元式的地址（序号），其初值为1。每执行一次emit语句后，nxq自动增1。,（2）merge(p1,p2)：把以p1和p2为链首的两条链合并为一条以p2为链首的链（即返回链首值p2）。,（3）backpatch(p,t)：把链首p所链接的每个四元式的第四区段（即result）都改写为地址t。,merge()函数如下：,int merge(p1,p2),if(p2=0)return(p1);,else,p=p2;,while(四元式p的第四区段内容不为0),p=四元式p的第四区段内容；,把p1填进四元式p的第四区段；,return(p2);,Backpatch()函数如下：,void backpatch(p,t),Q=p;,while(Q!=0),q=四元式Q的第四区段内容；,把t填进四元式Q的第四区段；,Q=q;,为了便于实现布尔表达式的语法制导翻译，并在扫描到“”与“”时能及时回填一些已经确定了的待填转移目标，我们将前述文法GE改写为下面的文法GE，以利于编制相应的语义子程序：,GE：EEAEEBEE(E)i rop ii,EAE,EBE,这时，文法GE的每个产生式和相应的语义子程序如下：,（1）Ei E.tc=nxq;E.fc=nxq+1;,emit(jnz,entry(i),_,0);,emit(j,_,_,0);,（2）Ei(1)rop i(2)E.tc=nxq;E.fc=nxq+1;,emit(jrop,entry(i(1),entry(i(2),0);,emit(j,_,_,0);,（3）E(E(1)E.tc=E(1).tc;E.fc=E(1).fc;,（4）EE(1)E.tc=E(1).fc;E.fc=E(1).tc;,（5）EAE(1)backpatch(E(1).tc,nxq);,EA.fc=E(1).fc;,（6）EEAE(2)E.tc=E(2).tc;,E.fc=merge(EA.fc,E(2).fc);,（7）EBE(1)backpatch(E(1).fc,nxq);,EB.tc=E(1).tc;,（8）EEBE(2)E.fc=E(2).fc;,E.tc=merge(EB.tc,E(2).tc);,注意：根据上述语义动作，在整个布尔表达式所对应的四元式全部产生之后，作为整个表达式的真假出口（转移目标）仍尚待回填。此外，由产生式,(2)也可看出关系表达式的优先级要高于布尔表达式。,例4.3 试给出布尔表达式abcd作为控制条件的四元式中间代码。,解答 设四元式序号从100开始，则布尔表达式abcd的分析过程如图4-7所示。,图,47 表达式abcd分析示意,即：100(jnz，a，_，102),101(j，_，_，104),102(jnz，b，_，106),103(j，_，_，104),104(j，c，d，106),105(j，_，_，q),T:106,F:q,当然，我们也可以通过图4-8的分析得到上述四元式序列。,图,4,8 abcd的翻译图,由例4.3可知，每一个布尔变量a都对应一真一假两个四元式，并且格式是固定的，即,(jnz，a，_，0)/a为布尔变量,(j，_，_，0),而每一个关系表达式同样对应一真一假两个四元式，其格式也是固定的，即,(jrop，X，Y，0)/X、Y为关系运算符两侧的变量或值,(j，_，_，0),例4.4 试给出布尔表达式amncxy的四元式代码。,解答 该布尔表达式的翻译图如图4-9所示，所对应的四元式代码如下：,100(jnz，a，_，108),101(j，_，_，102),102(j，m，n，108),103(j，_，_，104),104(jnz，c，_，106),105(j，_，_，q),106(j，x，y，108),107(j，_，_，q),T:108,F:q,图,49 例4.4的翻译图,4.5 控制语句的翻译,在源程序中，控制语句用于实现程序流程的控制。一般程序流程控制可分为下面三种基本结构：,（1）顺序结构，一般用复合语句实现；,（2）选择结构，用if和case等语句实现；,（3）循环结构，用for、while、do等语句实现。,4.5.1 条件语句if的翻译,1条件语句if的代码结构,我们按下面的条件语句if的模式进行讨论：,if(E)S1;else S2;,条件语句if(E)S1;else S2;中布尔表达式E的作用仅在于控制对S1和S2的选择，因此可将作为转移条件的布尔式E赋予两种“出口”：一是“真”出口，出向S1；一是“假”出口，出向S2。于是，条件语句可以翻译成如图4-10所示的代码结构。,图,410 条件语句if(E)S,1,;else S,2,的代码结构,我们知道，非终结符E具有两项语义值E.tc和E.fc，它们分别指出了尚待回填真假出口的四元式串。E的“真”出口只有在扫描完布尔表达式E后的“)”时才能知道，而它的“假”出口则需要处理过S1之后并且到else时才能明确。这就是说，必须把E.fc的值传下去，以便到达相应的else时才进行回填。S1语句执行完就意味着整个if-else语句已执行完毕，因此，在S1的编码之后应产生一条无条件转移指令，这条转移指令将导致程序控制离开整个if-else语句。但是，在完成S2的翻译之前，这条无条件转移指令的转移目标是不知道的，甚至在翻译完S2之后仍无法确定，这种情形是由语句的嵌套性所引起的。例如下面的语句：,if(E1)if(E2)S1;else S2;else S3;,在S1代码之后的那条无条件转移指令不仅应跨越S2，而且应跨越S3。这也就是说，转移目标的确定和语句所处的环境密切相关。,不含,else,的条件语句,if(E)S,的代码结构图如图,4-11,所示。,图,4-11 if(E)S,的代码结构,2条件语句if的文法和语义子程序的设计,条件语句,if的文法GS如下：,GS：Sif(E)S(1);,Sif(E)S(1);else S(2);,为了在扫描条件语句过程中不失时机地处理和回填有关信息，可将GS改写为如下的GS：,GS：（1）SCS(1);,（2）Cif(E),（3）STPS(2);,（4）TPCS(1);else,根据程序语言的处理顺序，首先用产生式（2）Cif(E)进行归约，这时E的真出口即为E所生成四元式序列后的下一个地址。因此，将“)”后的第一个四元式地址回填至E的真出口，E的假出口地址则作为待填信息放在C的语义变量C.chain中，即,Cif(E)backpatch(E.tc,nxq);,C.chain=E.fc;,接下来用产生式（1）SCS(1);继续向上归约。这时已经处理到Sif(E)S(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-else形式，则继续用产生式（4）TPCS(1);else归约。,用TPCS(1);else 归约时首先产生S(1)语句序列之后的一个无条件转移四元式（以便跳过S(2)，见图410的结构框图），该四元式的地址（即标号）保留在q中，以便待获知要转移的地址后再进行回填，也即,(i)(S(1)的第一个四元式)/E的真出口,(q1)(S(1)的最后一个四元式),(q)(j,_,_,0)/无条件跳过S(2)，其转移地址有待回填,(q+1)(S(2)的第一个四元式)/E的假出口,此时q的出口也就是整个条件语句的出口，因此应将其与S.chain链接后挂入链头为TP.chain的链中。此外，emit 产生四元式q后nxq自动加1（即为q+1），其地址即为else后（也即S(2)）的第一个四元式地址，它也是E的假出口地址，因此应将此地址回填到E.fc即C.chain中，即有,TPCS(1);else q=nxq;,emit(j,_,_,0);,backpatch(C.chain,nxq);,TP.chain=merge(S.chain,q);,最后用产生式（3）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);,4.5.2 条件循环语句while的翻译,1条件循环语句while的代码结构,循环语句while(E)S(1);通常被翻译成如图4-12所示的代码结构。布尔表达式E的“真”出口出向S(1)代码段的第一个四元式，紧接S(1)代码段之后应产生一条转向测试E的无条件转移指令；而E的“假”出口将导致程序控制离开整个while语句而去执行while语句之后的后继语句。,图412 条件循环语句while的代码结构,注意：E的“假”出口目标即使在整个while语句翻译完之后也未必明确。例如：,if(E1)while(E2)S1;else S2;,这种情况仍是由于语句的嵌套性引起的，所以只好把E的假出口作为循环语句的语义值S.chain保留下来，以便在处理外层语句时再伺机回填。,2条件循环语句while的文法和语义子程序设计,同样，我们给出易于及时处理和回填的循环语句while的文法GS如下：,GS：（1）SWdS(1),（2）WdW(E),（3）Wwhile,根据,while语句的扫描加工顺序，首先用产生式（3）Wwhile进行归约，这时nxq即为E的第一个四元式地址，我们将其保留在W.quad中。然后继续扫描并用产生式（2）WdW(E)归约，即扫描完“)”后可以用backpatch(E.tc,nxq)回填E.tc值；而E.fc则要等到S(1)语句序列全部产生后才能回填，因此E.fc作为待填信息用Wd.chain=E.fc传下去。,当用产生式（1）SWdS(1);归约时，S(1)语句序列的全部四元式已经产生。根据图412 while语句代码结构的特点，此时应无条件返回到E的第一个四元式继续对条件E进行测试，即形成四元式(j,_,_,Wd.quad)，同时用backpatch(S(1).chain,Wd.quad)回填E的入口地址到S(1)语句序列中所有需要该信息的四元式中。,在无条件转移语句(j,_,_,Wd.quad)之后即为while语句的后继语句，而这个后继语句中的第一个四元式地址即为while语句E的假出口，保存在Wd.chain中。考虑到嵌套情况，将Wd.chain信息作为整个while语句的出口保留在S.chain中，以便适当时机回填。因此，文法GS对应的语义加工子程序如下：,（1）Wwhile W.quad=nxq;,（2）WdW(E)backpatch(E.tc,nxq);,Wd.chain=E.fc;,Wd.quad=W.quad;,（3）SWd S(1);backpatch(S(1).chain,Wd.quad);,emit(j,_,_,Wd.quad);,S.chain=Wd.chain;,3循环语句do和for的代码结构,循环语句,do S(1)while(E);通常被翻译成如图4-13所示的代码结构。首先翻译S(1)的代码，然后翻译布尔表达式E的代码；E的“真”出口出向S(1)代码段的第一个四元式，而E的“假”出口则使程序控制离开整个do语句而去执行do语句之后的后继语句。,S(1)的代码,E的代码,T,F,图,4,-,1,3,循环语句,do,的代码结构,C,语言的,for,语句不同于其他高级语言中的,for,语句，其功能更加强大，使用更加灵活。,for,循环语句的一般形式为：,for(E1;E2;E3)S(1);,for,语句圆括号中两个分号分隔的三个表达式,E1,、,E2,和,E3,的作用如下：,（,1,）,E1,：给循环控制变量赋初值，只在循环开始时执行一次。,（,2,）,E2,：作为控制循环的条件在每次循环之前进行计算；如果条件成立（非,0,）则执行循环体语句，如果条件不成立（为,0,）则结束循环。,（,3,）,E3,：用于改变循环控制变量的值，使得循环条件趋向于不成立（以便结束循环）。,for,语句的执行过程分解为如下几步：,（,1,）计算,E1,；,（,2,）求解,E2,；若值为真（非,0,）则执行循环体语句，然后转（,3,）；若值为假（,0,）则转（,5,）；,（,3,）计算,E3,；,（,4,）转（,2,）继续执行；,（,5,）结束循环。,因此，,for(E1;E2;E3)S(1);,就相当于：,E1;,while(E2),S(1);,E3;,所以，循环语句,for(E1;E2;E3)S(1);,可以依照图,4-12,翻译如图,4-14,所示的代码结构。,T,E1的代码,E2的代码,F,S(1)的代码,E3的代码,图,4,-,1,4,循环语句,for,的代码结构,当然，我们还可按同样方法得到循环语句,do S,(1),while(E);,和,for,(,E,1,;,E,2,;,E,3,),S,(1),;,的文法及语义加工子程序。,4.5.3 三种基本控制结构的翻译,1三种基本控制结构的文法,我们给出三种基本控制结构的文法GS如下：,GS：(1)SCS,(2)T,P,S,(3)W,d,S,(4)L,(5)A,/A代表赋值语句,(6)LL,S,S,(7)S,(8)Cif(E),(9)T,P,CS;else,(10)Wwhile,(11)W,d,W(E),(12)L,S,L;,GS中各产生式对应的语义子程序如下：,(1)SC S,(1),S.chain=merge(C.chain,S,(1),.chain);,(2)ST,P,S,(2),S.chain=merge(T,P,.chain,S,(2),.chain);,(3)SW,d,S,(1),Backpatch(S,(1),.chain,W,d,.quad);,emit(j,_,_,W,d,.quad);,S.chain=W,d,.chain;,(4)SL S.chain=L.chain;,(5)SA S.chain=0;/*空链*/,(6)LL,S,S,(1),L.chain=S,(1),.chain;,(7)LS L.chain=S.chain;,(8)Cif(E)Backpatch(E.tc,nxq);,C.chain=E.fc;,(9)T,P,C S,(1),;else q=nxq;,emit(j,_,_,0);,Backpatch(C.chain,nxq);,T,P,.chain=merge(S,(1),.chain,q);,(10)Wwhile W.quad=nxq;,(11)W,d,W(E)Backpatch(E.tc,nxq);,W,d,.chain=E.fc;,W,d,.quad=W.quad;,(12)L,S,L;Backpatch(