语法制导翻译技术 (2).ppt

第6章 语法制导翻译技术,高级语言源程序经过词法分析、语法分析之后，如果没有错误，说明该源程序在书写上是正确的，符合语言的语法规则。词法分析和语法分析只检查了源程序的拼写、结构是否正确，但是对程序内部的逻辑含义并未考虑。语法上的正确并不能保证其语义是正确的。要判断语义是否正确，就必须依靠语义分析。,这一章，我们所要介绍的是目前大多数编译程序普遍采用的一种技术，即语法制导翻译技术。在这种方法中，我们可以用一个或多个子程序(称为语义动作)来完成产生式的语义分析，并把这些语义动作插入到产生式中相应位置，从而形成翻译文法。当在语法分析过程中使用该产生式时，就可以在适当的时机调用这些动作，完成所需要的翻译；进一步，可根据产生式所包含的语义，分析文法中每个符号的语义，并将这些语义以属性的形式附加到相应的符号上；再根据产生式所包含的语义，给出符号间属性的求值规则，从而形成所谓的属性翻译文法。这样，当在语法分析中使用该产生式时，可根据属性求值规则对相应属性进行求值，从而完成翻译。,6.1 翻译文法,翻译文法是上下文无关文法的推广，是在描述语言文法规则的右部适当位置加入语义动作得到的。为了区分文法符号与语义动作，在文法的表示中，将代表语义动作的符号前面加符号来表示。如何来设计翻译文法呢？,假设我们要设计一个翻译器，它能将中缀表达式翻译成波兰后缀表达式。我们可以想象该翻译器将如何进行这种翻译。假设输入串是a+b*c，则翻译器的输入输出动作是：READ(a)PRINT(a)READ(+)READ(b)PRINT(b)READ(*)READ(C)PRINT(C)PRINT(*)PRINT(+)其中READ表示输入操作，PRINT表示输出操作。在该序列中，若用输入符号本身直接表示读操作，用表示表示输出操作，则上述序列可简化为：aa+bb*cc*+,这种带有的符号串称为活动序列。由PRINT操作所确定的输出结果是由紧跟在符号之后的各符号组成，即abc*+。我们称为动作符号标记，由符号开始的符号串称为一个动作符号。这样，上面的活动序列中就有5个动作符号，分别为：a、b、c、*和+。在这个例子中，我们可以把这些动作符号看成一些子程序的名字。这些子程序的功能就是打印动作符号中的输出符号。在有些应用中，动作符号用来表示更一般的具有特殊功能的子程序。,6.1 翻译文法,上面的活动序列只说明了如何具体处理一个中缀表达式。为了能对所有中缀表达式翻译，就必须研究中缀表达式文法，考虑能否在适当位置加入动作符号，使得能够产生含有能翻译成波兰后缀表达式的活动序列。假设中缀算术表达式文法为：为了构造能产生活动序列的文法，只需在规则右部的适当位置加入动作符号。对于该文法，为了读a之后能打印a，产生式可写成：Faa。为了在打印两个操作数之后打印加法运算符，产生式将变为：EE+T+，这个产生式可解释为：“对非终结符号E的分析可以看成是处理E，读+，再处理T并打印+”。对其他产生式作类似的改变以后可得文法为这种带有动作符号的文法就是我们称为翻译文法的一个例子。,EE+T F(E)ET Fa TT*F Fb TF Fc,EE+T+F(E)ET Faa TT*F*Fbb TF Fcc,6.1 翻译文法,从上例中我们可看到，中缀表达式文法和其翻译文法的产生式之间有对应关系，为了和翻译文法的称呼对应，现在，我们把中缀表达式文法叫做输入文法，使用中缀表达式文法通过推导可以得到终结符号串叫做输入序列，而通过翻译文法得到的符号串称为活动序列。因此通过输入文法推导能得到的输入序列，那么就能通过翻译文法得到相应的活动序列。从该活动序列中去掉所有动作符号就是输入序列，而所有动作符号组成的符号串称为动作序列。,例如，对于符号串(a+b)*b用输入文法推导输入序列(a+b)*c的过程如下:E=T=T*F=F*F=(E)*F=(E+T)*F=(T+T)*F=(F+T)*F=(a+T)*F=(a+F)*F=(a+b)*F=(a+b)*c用翻译文法推导得到活动序列(a a+b b+)*c c*的过程如下:E=T=T*F*=F*F*=(E)*F*=(E+T+)*F*=(T+T+)*F*=(F+T+)*F*=(aa+T+)*F*=(a a+F+)*F*=(a a+b b+)*F*=(a a+b b+)*c c*将活动序列(aa+bb+)*cc*中的动作符号去掉就得到输入序列：(a+b)*c，而所有动作符号组成的符号串即动作序列为：a b+c*,6.1 翻译文法,翻译文法是上下无关文法。在这个文法中，终结符号集由输入符号和动作符号组成。由翻译文法确定的语言中的符号串称为活动序列。例如，有文法G(E)=Vn,Vt,P,E，其中Vn=E,T,FVt=a,b,c,+,*,(,),+,*,a,b,c P=EE+T+,F(E),ET,Faa,TT*F*,Fbb,TF,Fcc这个文法的终结符号集由输入符号和动作符号组成，因此是翻译文法。从上面介绍得知，翻译文法就是在原有的输入文法基础上，在规则右部适当位置加入动作符号所得。在高级程序设计语言的翻译中有各种各样的翻译文法，其中的动作符号代表不同的语义动作。在翻译文法中,如果的动作就是输出其后的符号,可称为符号串翻译文法。符号串翻译文法是翻译文法中的一种特定类型。,6.2 语法制导翻译,有了翻译文法，我们就可以根据输入符号串用翻译文法得到一个活动序列。执行其中的动作符号串，就可获得一个新的符号串。这个新符号串就是翻译的结果。,例如:根据前面的算术表达式翻译文法，对于输入符号串a+b*c，我们推导出活动序列：aa+bb*cc*+其中：a+b*c 为输入序列 abc*+为动作序列如果执行该动作序列中的动作，则产生输出序列abc*+,这就是输入序列a+b*c的翻译结果。由于这种翻译结果是通过翻译文法获得的，所以就称为语法制导翻译。,所谓语法制导翻译，就是给定一输入序列，根据翻译文法获得翻译该符号串的活动序列，从活动序列中分离出动作符号串，然后执行该动作符号串所规定的动作，从而得到翻译结果。从形式上看，可以将翻译看成是对偶的集合。对偶的第一个元素是被翻译的符号串(即输入序列)，第二个元素是翻译成的新符号串。当我们是按翻译文法得到这种对偶时，则称为语法制导翻译。如果给出由输入符号和动作符号所组成的活动序列，通过从活动序列中删掉所有动作符号则可得到“输入序列，而从活动序列中删掉所有输入符号则可得到动作序列，这样就可得到对偶。而要得到活动序列，就必须借助翻译文法。,6.2 语法制导翻译,如果给定了一个翻译文法，就得到一门语言，该语言中的每个句子都是一个活动序列。通过将每个活动序列的输入序列与动作序列配对可得到对偶的集合，从而得到翻译。这种对偶集合称为由给定翻译文法所定义的翻译。例如：对偶(a+b*c,abc*+)就是算术表达式翻译文法定义的一个翻译。翻译文法的构造方法可通过对输入文法修改得到。对输入文法的产生式，在其右部的适当位置插入动作符号就形成翻译文法。因此，翻译文法产生的动作序列实际上是受输入语言的文法控制的。按语法制导翻译的方法来实现语言的翻译，就要根据输入语言的文法，分析各条产生式的语义，即分析他们要求计算机所完成的操作，分别编出完成这些操作的子程序或程序段(称为语义子程序或语义动作)，并把这些子程序或程序段的名字作为动作符号插入到输入文法各产生式右部的适当位置上，从而实现翻译文法。,6.3 自顶向下语法制导翻译,自顶向下的语法制导翻译有递归下降翻译和LL(1)翻译。6.3.1 递归下降翻译递归下降翻译器的实现思路与递归下降分析基本相同，要求也一样，即不能有左递归，头符号集不能相交，只需在适当的位置插入实现动作符号的子程序。,例如，算术表达式翻译文法如下：(为输出其后的符号串)E-E+T+E-T T-T*F*T-F F-(E)F-ii,由于文法中存在左递归，所以要修改文法，去掉左递归，修改后文法为：E-T+T+T-F*F*F-(E)|ii对应于每个非终结符号的递归下降翻译程序流程图如图6.1所示。,图6.1(a)处理E的递归下降翻译程序流程图,6.3.1 递归下降翻译,图6.1(b)处理T的递归下降翻译程序流程图,图6.1(c)处理F的递归下降翻译程序流程图,C语言翻译程序,6.3.2 LL(1)翻译器,考虑下面的输入文法：ac b c a c b,表6.1 输入文法的LL(1)分析表,如果我们在该输入文法的适当地方插入翻译所需要的动作符号，那么，可得到如下的翻译文法：v awx cyz b cr am Cn s b,6.3.2 LL(1)翻译器,假定动作符号的动作是输出动作标记后面的符号串,其翻译器的分析表构造方法与第四章介绍的相同，只不过加入了动作符号。例如，对上面翻译文法中的产生式：v awx cy其对应的输入文法的产生式为：ac原来输入文法的分析表元素为：MA，a=POP,PUSH(DcBa)则翻译文法的分析表元素为：MA，a=POP,PUSH(zDycxBwav),表6.2 翻译文法的LL(1)分析表,对于翻译文法，动作符号像其它符号一样入栈。但当动作符号处于栈顶时，无论当前的输入符号是什么，都要执行由该动作符号所规定的操作，并将该动作符号从栈顶弹出，且不移动读符号指针。,6.3.2 LL(1)翻译器,假如翻译器的分析栈的栈顶符号为A，且当前输入符号为a，那么将发生的动作是弹出A，zDycxBwAv入栈。由于此时栈顶为动作符号v，因此v出栈，并执行由该动作符号所规定的操作，对于该符号串翻译文法就是要输出v，即out(v)。紧接着，a出栈，读下一个符号。然后，动作符号w为栈顶，因此w出栈，并执行由该动作符号所规定的操作，对于该符号串翻译文法就是要输出w，即out(w)。此时栈的情况和语法语义分析动作如图6.2所示。,a,v出栈并执行，a出栈，w出栈并执行,图6.2 栈顶的动作符号出栈并执行,将LL(1)分析扩充为LL(1)语言的翻译器，只需扩充相应分析表的动作部分并具体实现完成每个动作符号的子程序，就可得到翻译文法所确定语言的翻译程序。下面对翻译文法的LL(1)翻译的总控程序总结：1）当翻译器的控制执行程序根据栈顶符号和当前输入符号查该表得到元素为空时，则转错误处理程序。2)若控制执行程序识别栈顶符号为动作符号时，不管当前输入符号是什么，将该动作符号从栈中弹出并转相应的子程序以完成所需的翻译。对于符号串翻译文法，其语义动作为输出动作符号中的符号串。,6.4 属性翻译文法,我们见到的文法的所有符号(非终结符号,终结符号,动作符号)都没有值的概念。而属性文法中的符号可以有值,这个值就叫做该符号的属性。在词法分析中,所有无符号整数这一类单词符号都用NUM作为记号,而具体的数值实际是符号NUM的属性。如对于表达式3+5，经词法分析输出为NUM3+NUM5,其中3和5就是属性的表示，意味着第一个NUM符号的值是3，第二个NUM符号的值是5。符号不但可以有属性，而且其属性还有类型。符号的属性分综合属性和继承属性两种。,6.4.1 综合属性,假设我们要设计一个语法分析程序，该语法分析程序接受算术表达式，并通过添加动作符号输出这个表达式的值。能够完成输出表达式值的符号串翻译文法如下：,SEANSWER EE+T ET TT*F TF F(E)FNUM,文法中的动作符号ANSWER的动作是输出表达式的计算结果。比如对于3+2*3，希望能得到结果9。现在的问题是如何将表达式的值传递给动作符号ANSWER呢？假设对于表达式3+2*3，词法分析后的结果如下：NUM3+NUM2*NUM3 其中NUM代表无符号整数，“数字串”是该符号的属性部分，对应于原表达式，可见词法分析将所有无符号整数用一个统一符号NUM表示，而具体的数值则在属性中体现。根据所给定的翻译文法，可画出该输入符号串的语法树如图6.3(a)所示。,6.4.1 综合属性,6.4.1 综合属性,为了计算表达式的值，我们要先分别计算各子表达式的值，然后再计算父表达式的值，直到求得整个表达式的值。语法树中非终结符E、T、F的每次出现都表示该输入表达式的一个子表达式，所以其值部分应是其子表达式的计算结果。根据这个思想，若有产生式FNUM，TF，则F的值部分应等于NUM的值部分，T的值部分应等于F的值部分。同理：若有产生式EE+T，则产生式左边的E的值部分等于产生式右边E的值部分加上T的值部分，其余类推。从语法树上看，F、T、E这些符号的属性符合自底向上的求值法则，所以用表示。最后对文法的第1个产生式，提供这样的规则，即ANSWER的值部分等于E的值部分，这不符合自底向上的求值法则，所以，我们引进一个向下的箭头表示动作符号ANSWER的属性值。这样，就可自底向上地将代表子表达式的计算结果作为属性分别加到各非终结符上，从而得到图6.3(b)所示的带有属性计算的语法树。,6.4.1 综合属性,为了形式地表示上述表达式的求值过程，必须改写每一个产生式，使得对出现在产生式中的每个属性值都给它一个不同的名字，并使用这些名字定义这个产生式中各符号的属性之间的关系即属性求值规则。上述计算表达式值的符号串翻译文法可改写为(右边为属性求值规则)：,SEqANSWERrr=q Ep Eq+Trp=q+r Ep Tq p=q Tp Tq*Frp=q*r Tp Fqp=q Fp(Eq)p=q Fp NUMq p=q,产生式中出现的p、q、r称为属性变量名，且规定属性变量名都局部于每个产生式。在图6.3(b)所示的语法树中，每个非终结符的属性值都是由它下面的那些符号来确定。这种可通过自底向上进行求值的属性，就称为综合属性，用“”来表示。对于处于语法树叶结点的终结符号，其综合属性具有初始值。如图6.3(b)中的NUM3，综合属性3由词法分析给出。,6.4.2 继承属性,在图6.3(b)所示语法树，其中动作符号ANSWER的属性来源于左边非终结符号E的属性，这不符合自底向上的求值法则，所以，我们用一个向下的箭头表示该动作符号的属性值，这就是继承属性的一个例子。,考虑下列声明语句文法 TYPE Id;，Id 其中TYPE代表类型，其值可为INT或 REAL或BOOL。假设词法分析程序在输出单词符号时，对变量名V除返回一个单词记号外，同时返回一个值部分，它就是变量名。在返回TYPE的同时还返回其类型值。,6.4.2 继承属性,语法分析程序在处理该声明语句时，假定调用SET_TYPE过程。该过程根据TYPE的属性(即具体类型)确定变量的类型，并输出变量名及类型。调用SET_TYPE的时间是语法分析程序在读到一个变量之后，该调用时间可用以下的翻译文法来描述，此文法使用动作符号SET_TYPE来表示调用SET_TYPE。(1)TYPE ID SET_TYPE;(2)，IDSET_TYPE(3)过程SET_TYPE需要两个参数：一个是变量名，另一个是变量的类型，那么，从文法上看，动作符号SET_TYPE有两个属性。因此，动作符号SET_TYPE形式为：SET_TYPE变量名，类型其中动作符号后面带有两个属性，即变量名和类型。,6.4.2 继承属性,用属性变量来表示符号的属性，对第1个产生式，TYPE和ID的属性值可由词法分析程序的返回值得到。对第二个产生式，除从词法分析程序得到V的属性值(变量名)以外，无法求得动作符号SET_TYPE和变量表的表示类型的属性值。为了解决这一问题，可令第2个产生式左边的变量表的属性值等于第1个产生式右边变量表的属性值。这样，上述翻译文法可写成(包括属性求值规则)：1)TYPEtIDnSET_TYPEn1,t1；t2=t，t1=t，n1=n 2)，IDnSET_TYPEn1,t1 t2=t，t1=t，n1=n 3),如果输入符号串为“INT a,b；”，词法分析后输出为“TYPEint Ida Idb；”，则带有属性的语法树如图6.4所示。我们把这种按自顶向下或自左向右的方式求得的属性称为继承属性。对这种属性在其前面冠以“”表示。,6.4.3 属性翻译文法,当翻译文法的符号具有属性，并带有属性求值说明时，就称为属性翻译文法。其具体定义如下：1)文法的每个终结符、非终结符和动作符号都可以有一个有穷的属性集。2)每个非终结符和动作符号属性可分为综合属性和继承属性。3)继承属性的求值规则：开始符号的继承属性具有初始值。对产生式左部的非终结符，其继承属性则继承前面产生式中该符号已有的继承属性值。右部的符号，其继承属性由产生式中其它符号属性值进行计算。4)综合属性的求值规则：对终结符号其综合属性具有指定的初始值。在具体实现中，该初始值将由词法分析程序提供。产生式右部的非终结符号的综合属性值，则取后面以该非终结符号为产生式左部时求得的综合属性值。产生式的左部的非终结符号的综合属性值，由产生式中左部或右部的某些符号的属性值进行计算。给定一动作符号，其综合属性值将用该动作符号的其它属性值进行计算。,6.4.3 属性翻译文法,在构造属性翻译文法的产生式时，我们将每个符号的属性都用一个标识符表示，并称该标识符为属性变量名。用“属性变量名”表示综合属性，用“属性变量名”表示继承属性。例如，一翻译文法有产生式 XbYZ 可写成 Xpq,rbsYyuZvw其属性求值规则为：q=sin(u+w)，r=s*u,v=s*u，y=p，w=v属性翻译文法生成带有属性的活动序列。属性活动序列又分为属性输入序列和属性动作序列。根据属性翻译文法可构造出由该文法所定义的任一属性活动序列的属性翻译树。开始符号的继承属性和终结符号的综合属性赋予给定的初始值，然后根据属性求值规则自顶向下和自底向上地计算语法树中间结点的各种属性值，并附加到语法树的相应结点上，该过程直到再不能计算时为止。如果通过上述属性求值过程，使语法树上的所有符号的属性变量都能得到赋值，则称该树是完整的；否则是不完整的。,给定一属性翻译文法，由该文法可得到由属性输入符号和动作符号所组成的属性活动序列，这个属性活动序列的动作符号序列称为对属性输入序列的翻译。从属性翻译文法得到的属性输入序列和动作序列组成的对偶称为由该属性翻译文法所定义的属性翻译。如果属性翻译文法是非二义性的，则每个属性输入序列至多有一棵语法树，并至多有一个属性翻译。,6.4.4属性翻译文法举例算术表达式的翻译,假定这个属性翻译文法的输出是四元组代码。要求翻译程序产生的四元组具有下面的性质 输出符号串中的每个双目运算都用一个四元式表示。四元组中的四元式的顺序与执行时要完成的运算顺序相同。每个四元式有三个参数，自左向右的顺序为左操作数，右操作数，运算结果。,例如，翻译器处理表达式a+b将生成如下的四元式 ADD,a,b,t1 其中t1是临时变量，保存表达式的结果。对于表达式：a+a*b，经词法分析后应为IDa*IDa+IDb，其中ID代表标识符。希望经属性翻译文法能输出：MULT,a,b,t1 ADD,a,t1,t2,6.4.4属性翻译文法举例算术表达式的翻译,下面根据上述要求进行翻译程序的设计：第一步先设计满足上述要求翻译文法：对规则E-E+T添加动作符号ADD成为：E-E+TADD；对T-T*F添加动作符号MULT成为：T-T*FMULT;得到的翻译文法如下：EE+TADDETTT*FMULTTFF(E)FID,6.4.4属性翻译文法举例算术表达式的翻译,第二步，构造属性和求值规则，把翻译文法构造成属性翻译文法。1)令每个非终结符有一个综合属性，该属性为一个临时变量，保存由它产生的表达式的结果。2)输入符号ID有一个综合属性，它是该符号的变量名。3)每个动作符号有三个继承属性，它们分别是指向左操作数、右操作数和运算结果。E为文法的开始符号，则实现这个方案的属性翻译文法如下：Ex-Eq+Tr ADDy,z,t，y=q,z=r,t=NEWV，x=tEx-Tp x=pTx-Tq*Fr MULTy,z,t，y=q,z=r,t=NEWT，x=tTx-Fp，x=pFx-(Ep)，x=pFx-IDp，x=p,其中，NEWT是一个函数，每次调用它时返回一个新的临时变量名，临时变量名按产生顺序分别为t1、t2、等等。动作符号ADDy,z,t 输出“ADD y,z,t”，动作符号MULTy,z,t 输出“MULT y,z,t”,6.4.4属性翻译文法举例算术表达式的翻译,为了说明这些动作符号与特定的语法树有关的属性，图6.5给出了对输入符号串a+a*b翻译的属性语法树。,6.5 属性文法的自顶向下翻译,属性翻译文法由翻译文法和有关的属性计算规则组成。如果属性计算规则给的不当，就不能保证所有的属性计算出来。那么如何才能保证所有属性都能计算出来呢？对于不同的分析方法有不同的要求，下面我们介绍对于自顶向下的分析方法，如何保证所有属性能计算出来，这就是L-属性翻译文法,6.5.1 L-属性翻译文法 L-属性的作用是保证可以按照自顶向下的有序方式来计算属性值，即按照自顶向下的有序方式对某个属性求值时,所需要的基本值已知。一属性翻译文法称为L-属性的，当且仅当下面三个条件成立：1)给定一产生式，其右部符号的继承属性值是以左部符号的继承属性或出现在给定符号左边的产生式右部符号的任意属性为变元的函数。2)给定一产生式，其左部符号的综合属性值是以左部符号的继承属性或某个右部符号的任意属性为变元的函数。3)给定一动作符号，其综合属性值是以该动作符号的继承属性为变元的函数。,将L-属性翻译文法与前面6.4.3小节的属性文法定义比较可以发现：1)是对继承属性求值规则第条的限制；2)是对综合属性求值规则第条的限制；3)是对综合属性求值规则第条的限制；在L属性文法中没有对初始化规则加以限制。,6.5.1 L-属性翻译文法,如果一个求值规则满足上述三个条件中的任何一个，那么称该求值规则为L-属性的。如果一产生式或动作符号的所有属性的求值规则都是L-属性的，那么称该产生式或动作符号是L-属性的。因此，如果一个属性文法的所有产生式和动作符号都是L-属性的，那么该属性文法是L-属性翻译文法。,例如，文法中有产生式为：AI1S2,S3BI4CS5DS6I7,I8EI9那么，根据L-属性的限制条件，I4=F(I1)、I4=123、I7=G(I1)合法，而I4=H(S2)、I4=K(S6,I4)则不合法。L-属性翻译文法中的条件1的重要性在于：使符号的继承属性只依赖于该符号左边的信息(“L-属性”中的“L”表示左边的意思)。这有利于自顶向下地对属性求值。因为每个符号都是在它右边的输入符号读入之前进行处理，而条件2和3是保证在求值过程中避免出现循环依赖性。综合上述，L属性的三个条件保证了当我们按自顶向下的方式进行翻译时，所有属性值都能够被计算。对于形式为ABC的产生式，A、B和C的属性可以按下面的顺序进行求值,1)A的继承属性；2)B的继承属性；3)B的综合属性；4)C的继承属性；5)C的综合属性；6)A的综合属性。,6.5.2 L-属性文法翻译的实现递归下降翻译,1)若该非终结符具有属性，那么该非终结符的分析过程就有形参，且形参的数目就是该非终结符的属性个数。2)对于继承属性，采用值形参的传参方式将继承属性值传入被调过程，即在过程调用中所对应的实在参数是继承属性的值。3)对于综合属性，采用变量形参的传参方式以便将值回传给主调过程，即所对应的实在参数是一个变量，在过程返回之前，把综合属性的值赋给这个变量。如果用C语言实现属性文法的翻译，可用指针变量代表综合属性的形参。,为了进行属性翻译的程序设计，我们采用下述约定：1)可以把属性产生式中的属性名字用作变量和参数的名字。这样可以将属性的命名和递归下降过程的实现联系起来。2)除属性翻译使用的常用记法约定以外，还必须加上一些属性命名约定。这些约定是：所有出现在左部的同名非终结符，应具有相同的属性名表。在左部同名非终结符属性名表的同一化过程中，属性名称的改动范围仅局限于产生式左部。为了保证一致性，左部属性重新命名以后，可使用新的记法约定来简化或删去某些属性求值规则。3)如果两个属性有相同的值，那么可给它们相同的名字，但对于左部符号的属性值相等时，不能改变成相同的名字。,例如，产生式 Lab-e i Rj，i,j=b,a=i+2 L xy-H zw，w=y,z=2,x=z+y 按约定的第2条，必须改成 L ab-e iiRj，i,j=b,a=j+2 L ab-H zw，w=b,z=2,a=z+b注意当x、y改成a，b后，相应的属性求值规则中涉及x、y的属性名也要进行变化。而对规则S-AaB bC c，当b，c=a时，可写成S-A a B a C a对规则La-A bf c，当a=b,c=b时，也可写成L a-A a f a但对规则Lab-aBcCd,当c,d=a时，可写成L ab-aB a C a但当b=a时，不能写成Laa-aB a C a这是因为左部非终结符号的属性将作为该非终结符号分析过程的形参，而一个过程的形参不能重名，如过程L(int a,int b)不可写成L(int a,int a)。,6.5.2 L-属性文法翻译的实现递归下降翻译,6.5.2 L-属性文法翻译的实现递归下降翻译,下面给出采用C语言编写属性翻译程序时采用的方法：1)形式参数：产生式左部非终结符的属性名表设计成相应过程的形式参数表。将继承属性的形参名说明为值形参(即简单变量)，综合属性形参名说明为指针变量。2)局部变量：在产生式中，与在左部出现的属性名不同的属性名变成相应过程的局部变量。3)非终结符的代码：对应于右部出现的每个非终结符的过程调用，该非终结符的属性作为实参。要注意：如果实参是简单变量，形参是指针变量，调用时实参应为简单变量的地址。4)输入符号的代码：对文法中出现的每个输入符号(即终结符号)，将赋值语句插入到过程中它所对应的NEXTSYM之前，把保存在读符号程序NEXTSYM中的终结符号属性(某个全局变量中)赋给输入符号属性中的每个属性变量。5)动作符号的代码：对出现在文法中的每个动作符号，插入代码便于对动作符号的综合属性进行计算，并且把结果赋给对应于该综合属性的变量，然后输出相应的符号。,6.5.2 L-属性文法翻译的实现递归下降翻译,6)属性规则的代码：与每个产生式有关的属性求值规则，插入其代码以便对属性求值规则的右部求值，并把结果赋给该规则左部的每个变量。可以把这些代码放在属性计算规则的所有自变量已知之后，且函数值被使用之前的任何地方。7)主程序：C语言都是从MAIN函数开始运行。在MAIN函数中，对文法的开始符号，其相应的每一个综合属性的名字变成主程序的局部变量，然后调用开始符号对应的过程。在调用时，如果实参对应开始符号的继承属性，则对每个继承属性以该属性的初始值作为值参传入，对每个综合属性取该属性的局部变量的地址传入。,EtTpEptEpt+Tr ADDp,r,t0 E t0t t0=NEWT Ept t=pTtFpTptTpt*Fr MULTp,r,t0 Tt0t t0=NEWT Tpt t=pFp-(Ep)|IDp,下面，以算术表达式的属性翻译文法为例，用C语言实现属性翻译器。算术表达式属性翻译文法如下：,6.5.2 L-属性文法翻译的实现递归下降翻译,主程序：C语言都是从MAIN函数开始运行。在MAIN函数中，对文法的开始符号，其相应的每一个综合属性的名字变成主程序的局部变量，然后调用开始符号对应的过程。在调用时，如果实参对应开始符号的继承属性，则对每个继承属性以该属性的初始值作为值参传入，对每个综合属性取该属性的局部变量的地址传入。EtTpEpt,/主程序main()int es=0,t;printf(请输入算术表达式(操作数只能是单个字母)：);ch=getchar();printf(输出四元式为：n);es=E(,6.5.2 L-属性文法翻译的实现递归下降翻译,/产生式EtTpEp的翻/译子程序，t为综合属性,形参/用指针变量int E(int*t)int es=0;int p;es=T(,/产生式Ept+Tr ADDp,r,t Et0t 和Ept翻译子程序/p为继承属性,形参用整型变量,t为综合属性,形参用指针变量int E1(int p,int*t)int r,es,t0;if(ch=+)ch=getchar();es=T(,/返回一个临时变量,顺序产生A、B、.、Z，/最多 产生26个临时变量int NEWT()static int i=64;/设置i为静态变量确保下/次调用时i为上次调用的结果 i=i+1;return(i);,6.5.2 L-属性文法翻译的实现递归下降翻译,/产生式TpFpTp的翻译子程序，t为综合属性,形参用指针变量int T(int*t)int es=0,p;es=F(,/产生式Tpt*Fr MULTp,r,t E 和Tpt翻译子程序/p为继承属性,形参用整型变量,t为综合属性,形参用指针变量int T1(int p,int*t)int r,es,t0;if(ch=*)ch=getchar();es=F(,6.5.2 L-属性文法翻译的实现递归下降翻译,6.5.2 L-属性文法翻译的实现递归下降翻译,/产生式Fp-(Ep)|ip的翻译子程序，p为综合属性,形参用指针变量int F(int*p)/分析F子程序 int es=0;if(ch=()ch=getchar();es=E(p);/调分析E子程序 if(ch!=)return(3);else ch=getchar();return(es);else if(isalpha(ch)/判断是否为字母*p=ch;ch=getchar();return(es);else return(4);,6.5.2 L-属性文法翻译的实现递归下降翻译,其中，NEWT是一个函数，每次调用它时返回一个新的临时变量名，为了编程方便，临时变量名按产生顺序分别为A、B、等等。动作符号ADDy,z,t 输出 ADD y,z,t，而MULTy,z,t 输出 MULT y,z,t。ID的属性p只能是一个小写字母，表示表达式中的操作数都是变量，且变量名只能是一个小写字母，如a+b、c*d都可以。这个属性翻译文法是6.4.4小节的属性翻译文法去掉左递归后得到的，由于用扩充的BNF表示无法进行属性的表示，所以，改成了右递归的形式。对于产生式EtTpEpt,左部符号E有一个综合属性，因此，子程序的形参用指针变量，形式为：int E(int*t)；而对于产生式Ept+Tr ADDp,r,t0 Et0t,左部符号E有一个综合属性p、一个继承属性t，因此，子程序有两个形参，一个用指针变量，另一个为整型变量，形式为：int E1(int p,int*t)，其它产生式的子程序也是如此。,具体实现C程序,运行这段程序，输入：a*(b+c)+b*d输出四元式序列为：其中A、B、C、D都是临时变量。,ADD b,c,AMULT a,A,BMULT b,d,CADD B,C,D,6.5.3 L-属性文法翻译的实现LL(1)法,在前面翻译文法的LL(1)翻译器的基础上，进一步对分析器扩充，就可以实现对属性翻译文法的翻译。对翻译文法，允许动作符号入栈，当栈顶是动作符号时，就执行动作，同时栈顶动作符号出栈，从而构造出翻译文法的翻译器。对于属性翻译文法，其扩充方法是：对于所有符号，不仅符号进分析栈，其属性也同时进栈。为此，对每个入栈的符号在栈中的表示(称为栈符号)要进行扩充，将栈符号设计为两部分，符号名和属性域。任何栈符号的域都是在栈内的一些存贮单元。例如，对符号串ABC，假定A有两个属性，B有一个属性而C没有任何属性。若符号名也占用一个存贮单元，则相应A的栈符号用三个存贮单元，B用二个，C用一个。压入堆栈以后的情况如图6.6所示。其中“#”为栈底符号。,考虑如下文法：SEpANSWERr r=p Ep+EqErADDA1,A2R A1=q,A2=r,R=A1+A2,p=R Ep*EqErMULTA1,A2R A1=q,A2=r,R=A1*A2,p=R EpNUMq p=q如何构造该属性翻译文法的翻译器呢？,首先，如果把属性删除，则该文法变成普通的符号串翻译文法，那么，在LL(1)分析器的基础上加进动作符号就可构造出一个LL(1)翻译器的分析表，实现由该符号串翻译文法所定义的翻译，如表6.3所示。该文法为符号串翻译文法。所以当动作符号处在栈顶时，不管输入符号是什么，翻译器将输出动作符号中的符号串,表6.3 LL(1)翻译器的分析表,1:POP,PUSH(ANSWER E)2:POP,PUSH(ADD E E+)3:POP,PUSH(MULT E E*)4:POP,PUSH(NUM)5:POP,NEXTSYM,6.5.3 L-属性文法翻译的实现LL(1)法,扩充这个机器就可得到处理属性文法的翻译器，其方法如下。,6.5.3 L-属性文法翻译的实现LL(1)法,1、栈符号设计属性文法的每个符号有属性，所以每个符号入栈时，必须连属性一起入栈，这样，栈符号就由文法符号及存放该符号属性的域所组成。由于属性类型不同，属性域存放的内容就要根据属性的类型来定。有的可能直接存放属性值，也有的存放的是指向属性值的指针。对于综合属性，其属性域不存放其属性值，而是存放一个指针，指向存贮该属性值的单元。对于继承属性，其属性域直接保存其属性值。继承属性的属性域刚入栈时为空，但是在该栈符号变成栈顶符号之前的某一时刻，它们必须接受相应的属性值，即在成为栈顶时，继承属性的属性域必须有值。对于本文法中出现的所有符号，其相应的栈符号如图6.7所示。,6.5.3 L-属性文法翻译的实现LL(1)法,S的栈符号,E的栈符号,NUM的栈符号,ANSWER的栈符号,ADD的栈符号,MULT的栈符号,图6.7 栈符号,6.5.3 L-属性文法翻译的实现LL(1)法,根据设计好的栈符号，我们可以对属性翻译文法构造分析表，如表6.4所示。,表6.4 LL(1)翻译器的分析表,1:POP,PUSH(ANSWERr Ep)2:POP,PUSH(ADDA1,A2R Er Eq+)3:POP,PUSH(MULTA1,A2R Er Eq*)4:POP,PUSH(NUMq),把NUM的属性值q放入NUM的属性域指向的单元.5:POP,NEXTSYM,6.5.3 L-属性文法翻译的实现LL(1)法,2、语义动作设计下面给出当动作符号出现在栈顶时，根据翻译的具体要求所要完成的语义动作。假定要求翻译器所要完成的工作是计算由文法定义的表达式的值并输出。那么三个动作符号的翻译动作为：1)ADD：把头两个域的内容相加，并把计算结果存贮在第三个域所指的单元中；POP；2)MULT：把头两个域的内容相乘，并把积存贮在第三个域所指的单元中；POP；3)ANSWER：输出属性域的内容结果；POP；,3、输入符号串+NUM2NUM3#的分析过程为了理解LL(1)的工作过程中对属性的处理，“+NUM2NUM3#”对应的表达式为+23，这是一种前缀表示。NUM为词法分析输出的整数记号。分析过程如下：,6.5.3 L-属性文法翻译的实现LL(1)法,1)#入栈，文法的开始符号S入栈，输入指针指向符号+，见图6.8(a)。,+NUM2NUM2#,符号栈：,图6.8(a),+NUM2NUM3#,符号栈：,图6.(b),2)查分析表S行+列，执行动作POP,PUSH(ANSWERr Ep)：因为r=p，所以，E属性域p为指向ANSWER属性r的指针，结果见图6.8(b)。,6.5.3 L-属性文法翻译的实现LL(1)法,NUM3#,符号栈：,图6.8(d),4)查分析表E行NUM列，执行动作POP,PUSH(NUMq)：E出栈前，E的属性p指向ADD的属性A1，而p等于NUM的属性值q，所以，NUMq入栈，把NUM的属性值2放入原来E出栈前的属性p指向的单元，即ADD的属性A1。然后，NUM符号出栈，读下一个符号,结果见图6.8(d)。,NUM2NUM2#,符号栈：,图6.8(c),3)查分析表E行+列，执行动作POP,PUSH(ADDA1,A2R Er Eq+)：E出栈前，属性p指向ANSWER的属性r，因为E的属性p等于ADD的属性R，所以ADD的属性R也指向ANSWE