【教学课件】第8章语法制导翻译和中间代码生成.ppt

《【教学课件】第8章语法制导翻译和中间代码生成.ppt》由会员分享，可在线阅读，更多相关《【教学课件】第8章语法制导翻译和中间代码生成.ppt（87页珍藏版）》请在三一办公上搜索。

1、第8章 语法制导翻译和中间代码生成,8.1概述一、语义处理的任务：,编译中的语义处理是指两个功能：第一 静态语义分析或静态审查。,静态语义分析通常包括：类型检查。控制流检查。控制流语句必须使控制转移到合法 的地方。一致性检查。相关名字检查。有时，同一名字必须出现两次或 多次。例如，Ada 语言程序中，循环或程序块可 以有一个名字，出现在这些结构的开头和结尾，编译程序必须检查这两个地方用 的名字是相同的。名字的作用域分析,第二 动态语义处理：如果静态语义正确，语义处理则要执行真正的翻译，即，或者将源程序翻译成程序的一种中间表示形式（中间代码），或者将源程序翻译成目标代码。,二、属性文法：1、属性

2、：所谓属性，其涉及的概念比较广泛，常用以描述事物或人的特征、性质，品质等等。比如，谈到一个 物体，可以用“颜色”描述它，谈起某人，可以使用“有幽默感“来形容他。对编译程序使用的语法树的结点，可以用类型、值或存储位置来描述它。,2、属性文法(也称属性翻译文法)它是在上下文无关文法的基础上，为每个文法符号(终结符或非终结符)配备若干相关的值（称为属性）。这些属性代表与文法符号相关信息，例如它的类型、值、代码序列、符号表内容等等。,属性与变量一样，可以进行计算和传递。属性加工的过程即是语义处理的过程。,对于文法的每个产生式都配备了一组属性的计算规则，称为语义规则。,假如语法分析方法是自下而上的。在用

3、某一产生式进行归约的同时就执行相应的语义动作，在分析出一个句子时，这个句子的值也就同时产生了,一个属性文法是一个三元组：A（G，V，F），G:是一个上下文无关文法 V:有穷的属性集,每个属性与文法的一终结符 或非终 结符相连。F:关于属性的属性断言或谓词集.每个断言与一个 产生式相 联。一个断言就是一个语义规则，描 述各属性的关系。,用法：针对语义：为每个符号设置一个属性，终结符号用单词属性。为每个产生式设置语义规则描述各属性的关系。,3、属性文法的定义：,例如：定义表达式的文法如下：EE+E E(E)En 给出定义表达式值的属性文法。,我们为文法符号E引进属性符号val,用E.val表示E的

4、值，属性计算规则以赋值语句的形式给出，附在每个产生式后，并用大括号括起来。为了明确E的不同出现位置，用上角标区别。终结符n的值是词法分析程序提供的，这里用n.lex表示。下面给出属性文法：EE1+E2 E.val:=E1.val+E2.val E(E1)E.val:=E1.val En E.val:=n.lex属性文法的主要思想有两点：首先对于每个文法符号引进相关的属性符号；其次对于每个产生式写出属性值计算的规则。,属性分为两种:继承属性和综合属性.综合属性：在语法树中，一个结点的综合属性由该结点 的子结点的属性值确定。它的计算规则由底 向上.继承属性:在语法树中，一个结点的继承属性由该结点的

5、 父结点/兄弟结点的属性确定。即它 的计算规 则由顶向下。,例如定义表达式值的属性文法，E.val是一个综合属性的例子：EE1+E2 E.val:=E1.val+E2.val E(E1)E.val:=E1.val En E.val:=n.lex考虑句子2（31）的求值顺序，将2（31）的语法树结点改为有附加属性的结点（这样的树称为带注释的语法树）：E.val=6 E.val=2+E.val=4 n.lex=2(E.val=4)E.val=3+E.val=1 n.lex=3 n.lex=1,又例：一个简单台式计算器的定义 综合属性val,语 义 规 则,L E,E E1+T,E T,T T1*F

6、,T F,F(E),F digit,Print(E.val),E.val:=E1.val+T.val,E.val:=T.val,T.val:=T1.val F.val,T.val:=F.val,F.val:=E.val,F.val:=digit.lexval,产 生 式,3*5+4的带注释的分析树,只使用综合属性.,L,E.val=19,E.val=15,T.val=4,T.val=15,F.val=4,T.val=3,F.val=3,F.val=5,digit.lexval=4,digit.lexval=5,digit.lexval=3,+,*,3*5+4的带注释的分析树,继承属性,一个结点

7、的继承属性值是由此结点的父结点和/或兄弟结点的某些属性来决定的。例，添加标识符类型的语义描述：继承属性type,L1.in:=L.in,与L产生式相联的语义规则中有一个过程调用addtype，过程addtype的功能是把每个标识符的类型信息登录在符号表的相关项中。,句子 int id1,id2 的语法树，使用 表示属性的传递情况。,三、中间代码,是源程序的一种内部表示复杂性介于源语言和目标机语言之间中间代码的形式：逆波兰式、四元式、三元式、间接三元式、树,1 逆波兰记号,逆波兰记号是最简单的一种中间代码表示形式。,这种表示法将运算对象写在前面，把运算符号写在后面，比如把a+b写成ab+，把a*

8、b写成ab*，用这种表示法表示的表达式也称做后缀式。,后缀表示法表示表达式，其最大的优点是易于计算机处理表达式。常用的算法是使用一个栈，自左至右扫描算术表达式（后缀表示），每扫描到运算对象，就把它推进栈；扫描到运算符，若该运算符是二目的，则对栈顶部的两个运算对象实施该运算，并将运算结果代替这两个运算对象而进栈；若是一目运算符，则对栈顶元素执行该运算，并以运算结果代替该元素进栈，最后的结果留在栈顶。,例如 BCD*+（它的中缀表示为B+C*D，使用表示一目减）的计值过程为：1.B进栈；2.对栈顶元素施行一目减运算，并将结果代替栈顶，即B置于栈顶；3.C进栈；4.D进栈；5.栈顶两元素相乘，两元素

9、退栈，相乘结果置栈顶；6.栈顶两元素相加，两元素退栈，相加结果进栈，现在栈顶存放的是整个表达式的值。,逆波兰表示很容易扩充到表达式以外的范围。,只要遵守运算对象后直接紧跟它们的运算符的规 则即可。比如把转语句GOTO L写为“L jump，运算对象L为语句标号，运算符jump表示转到 某个标号。再比如条件语句if E then S1 else S2 可表示为：ES1S2￥，把if then else看成三目运 算符，用￥来表示。,生成后缀式的属性文法,注释：|表示代码序列的连接,例:给出下列表达式的逆波兰式:(1)a*(-b+c)(2)a+b*(c+d/e),解(1)abc+*(2)abcde

10、/+*+,练习:P188 1,2 三元式和树形表示另一类中间代码形式是三元式。把表达式及各种语句表示成一组三元式。每个三元式由三个部分组成，分别是：算符op，第一运算对象ARG1和第二运算对象ARG2。运算对象可能是源程序中的变量，也可能是某个三元式的结果，用三元式的编号表示。例如a=b*c+b*d的表示为：（1）（*，b，c）（2）（*，b，d）（3）（+（1），（2）（4）（3），a）,树形表示是三元式表示的翻版。例:a=b*c+b*d可表示成下面的树表示：,例 表达式(A-12)*B+6 的语法结构树,将赋值语句变换为语法结构树,基本函数结点构造Mknode(op,left,right)

11、建标记为op的算符结点,结点有两个域，分别为left和right.Mkleaf(id,entry)建标记为id的叶结点，有一个entry域，它是指向符号表的入口。Mkleaf(num,val)建标记为id的叶结点,有一个val域，是表示该数的值。,构造 a-4+c的语法树：,(1)p1:=mkleaf(id,entry a);(2)p2:=mkleaf(num,4);(3)p3:=mknode(-，p1,p2)(4)p4:=mkleaf(id,entry c)(5)p5:=mknode(+,p3,p4),语法制导定义(属性文法),E.p 是语法结构树指针,四元式和三元式的主要不同在于，四元式对

12、中间结果的引用必须通过给定的名字，而三元式是通过产生中间结果的三元式编号。也就是说，四元式之间的联系是通过临时变量实现的。,有时，为了更直观，也把四元式的形式写成简单赋值形式或更易理解的形式。比如把上述四元式序列写成：（1）t1=b*c（2）t2=b*d（3）t3=t1+t2（4）a=t3把（jump，L）写成goto L 把（jrop，B，C，L）写成if B rop C goto L,请将表达式-(a+b)*(c+d)-(a+b)分别表示成三元式、间接三元式和四元式序列。,三元式(1)(+a,b)(2)(+c,d)(3)(*(1),(2)(4)(-(3),/)(5)(+a,b)(6)(-(

13、4),(5),间接三元式间接三元式序列 间接码表(1)(+a,b)(1)(2)(+c,d)(2)(3)(*(1),(2)(3)(4)(-(3),/)(4)(5)(-(4),(1)(1)(5),四元式(1)(+,a,b,t1)(2)(+,c,d,t2)(3)(*,t1,t2,t3)(4)(-,t3,/,t4)(5)(+,a,b,t5)(6)(-,t4,t5,t6),实际上，在一个表达式中可能出现各种不同类型的变量，而不象前面假定为同一类型。因此，上例应改为P163 图8.10 的形式。,采用语法制导翻译思想，表达式E的值的描述如下：产生式 语义动作(0)SE print E.VAL(1)EE1+

14、E2 E.VAL=E1.VAL+E2.VAL(2)EE1*E2 E.VAL=E1.VAL*E2.VAL(3)E(E1)E.VAL=E1.VAL(4)En E.VAL=n.LEXVAL假如终结符n可以是整数或实数，算符+和*的运算对象类型一致，语义处理增加类型匹配检查，请给出相应的语义描述。,(0)SE if error1 then print E.VAL EE1+E2 if E1.TYPE=int AND E2.TYPE=int thenbeginE.VAL:=E1.VAL+E2.VAL;E.YTPE:=int;end else if E1.TYPE=real AND E2.TYPE=real

15、 then begin E.VAL:=E1.VAL+E2.VAL;E.YTPE:=real;end else error=1,(2)EE1*E2 if E1.TYPE=int AND E2.TYPE=int then beginE.VAL:=E1.VAL*E2.VAL;E.YTPE:=int;end else if E1.TYPE=real AND E2.TYPE=real thenbeginE.VAL:=E1.VAL*E2.VAL;E.YTPE:=real;end else error=1,(3)E(E1)E.VAL:=E1.VAL;E.TYPE:=E1.TYPE(4)En E.VAL:=n

16、.LEXVAL;E.TYPE:=n.LEXTYPE,8.3 布尔表达式的翻译,程序设计语言中的布尔表达式有两个作用。一是计算逻辑值更多的情况是二:用做改变控制流语句中的条件表达式，如在if-then，if-then-else，或是while-do语句中那样。,布尔表达式是由布尔算符and，or和not施于布尔变量或关系表达式而成。即布尔表达式的形式为E1 rop E2，其中E1和E2都是算术表达式，rop是关系符，如，等等。,布尔表达式的翻译方法,通常，计算布尔表达式的值有两种办法:第一种办法，如同计算算术表达式一样，步步计算出各部分的真假值，最后计算出整个表达式的值。,那么布尔表达式1 or

17、（not 0 and 0）or 0的计算过程是：1 or（not 0 and 0）or 01 or（1 and 0）or 01 or 0 or 01 or 01,用数值1表示true，用0表示false。,另一种计算方法是采取某种优化措施，只计算部分表达式.例如要计算A or B，若计算出A的值为1，那么B的值就无需再计算了，因为不管B的值为何结果，A or B的值都为1。,控制语句中布尔表达式的翻译现在讨论出现在 if then；if then else和while do等语句中的布尔表达式E的翻译。这三种语句的语法为：Sif E then S1|if E then S1 else S2|w

18、hile E do S1,控制语句的代码结构,(a)if E then S1,(b)|if E then S1 else S2,(c)while E do S1,翻译的基本思路：对于E为a rop b,形成代码为：If a rop b goto E.true goto E.false对于E为 E1 or E2 的形式：1、E1为真，则E为真，即E的真出口为E1的真 出口。2、E1为假，计算E2，即E1的假出口应 为E2的第一个四元式标号，E2的真、假出 口与E的真、假出口一样。,我们使用Etrue和Efalse分别表示整个表达式ab or cd and ef的真、假出口，而Etrue和Efal

19、se的值并不能在产生四元式的同时就知道。为了看清这一点，我们把该表达式放在条件语句中考虑，如语句 If(ab or cd and ef)then S1 else S2 的四元式序列见下页：,（p）goto（q）（p+1）（关于S2的四元式）（q）,If(ab or cd and ef)then S1 else S2 的四元式序列为（1）ifabgoto（7）/*（7）是整个布尔表达式的真出口*/（2）goto（3）（3）ifcdgoto（5）（4）goto(p+1)/*（p+1）是整个布尔表达式的假出口*/（5）ifefgoto（7）（6）goto（p+1）（7）（关于S1的四元式）,如：E1

20、 or E2 E1有一个真出口，E2也有一个真 出口，将两个链合并为一条链。,（7）E true E.true:=nextstat;E.codebegin:=nextstat;emit(goto _)(8)E false E.false:=nextstat;E.codebegin:=nextstat;emit(goto _),以表达式 ab or cd and ef 为例，将分析产生语法树时的语义动作结果“真”“假”链情况注释在相应结点处，见P168 图8.14,控制语句的翻译,条件转移考虑if then，if then else和while do语句，在图8.12中已给出了它们的代码结构。这

21、里我们使用下面文法GS定义这些语句：GS（1）Sif E then S（2）|if E then S else S（3）|while E do S（4）|begin L end（5）|A（6）LL；S（7）|S其中各非终结符号的意义是：S-语句L-语句串A-赋值句E-布尔表达式,为了能及时回填有关四元式串的转移目标,对G(S)进行修改为G(S):,(1)SCS1(8)Cif E then(2)STpS2(9)TpCS else(3)SWdS3(10)Wd W E do(4)S begin L end(11)Wwhile(5)S A(6)S Ls S1(12)Ls L;(7)L S,(1)SCS

22、1 S.Chain:=merge(C.Chain,S1.Chain),(8)Cif E then backpatch(E.true,nextstat)C.chain:=E.false,(2)STpS2 S.chain:=merge(Tp.Chain,S2.Chain),(9)TpCS else q:=nextstat emit(goto _)backpatch(C.Chain,nextstat)Tp.Chain:=merge(S.chain,q),(11)Wwhile W.codebegin:=nextstat,(10)Wd W E do backpatch(E.true,nextstat)W

23、d.chain:=E.false Wd.codebegin:=W.codebegin,SWdS3 backpatch(S3.chain,Wd.codebegin)emit(goto Wd.codebegin S.chain:=Wd.chain,(4)S begin L end S.chain:=L.chain,(5)S A S.chain:=0/*空链*/,L S L.chain:=S.chain,(12)Ls L;backpatch(L.chain,nextstat),(6)L Ls S1 L.chain:=S1.chain,按照上述文法产生式相应的语义动作，加上前述关于赋值句和布尔表达式的

24、翻译法，语句while（AB）do if（CD）then X=Y+Z,将被翻译成如下的一串四元式：100if AB goto 102101goto107102ifCD goto 104103goto 100104T=Y+Z105X=T106goto 100107,while（AB）do if（CD）then X=Y+Z,for循环语句,for i=E1 step E2 until E3 do S1为了简单起见，假定E2总是正的。在这种假定下，上述循环句的意义等价于：i=E1；goto OVER；AGAIN：i=i+E2；OVER：if iE3 thenbegin S1；goto AGAIN e

25、nd；翻译见P173-P174,开关语句,开关语句（case语句或switch语句）,switch E ofcase V1：S1case V2：S2case Vn-1：Sn-1default：Snend,如果分叉不太多，case语句翻译成如下的一连串条件转移语句。t=E；L1：if tV1 goto L2；S1；goto next；L2：if tV2 goto L3；S2goto next；Ln-1：if tVn-1 goto Ln；Sn-1；goto next；Ln：Sn；next：,另一种方法:P172 图8.15,goto语句,多数程序语言中的转移是通过标号和goto语句实现的。带标号语

26、句的形式是LS；goto语句的形式是goto L。,当LS；语句被处理之后，标号L是定义了的。即在符号表中，将登记L的项的地址栏中登上语句S的第一个四元式的地址。,如果goto L是一个向上转移的语句，那么，当编译程序碰到这个语句时，L必是已定义了的。通过对L查找符号表获得它的定义地址p，编译程序可立即产生出相应于这个goto L的四元式如（j，p）。,如果goto L是一个向下转移的语句，也就是说，标号L尚未定义，那么，若L是第一次出现，则把它填进符号表中并标志上“未定义”。由于L尚未定义，对goto L只能产生一个不完全的四元式（goto），它的转移目标须待L定义时再回填进去。在这种情况下

27、，必须把所有那些以L为转移目标的四元式的地址全都记录下来，以便一旦L定义时就可对这些四元式进行回填。,我们将采用如图8.13所示的拉链办法，把所有以L为转移目标的四元式串在一起。链的首地址放在符号表中L的地址栏中,建链的方法是：若goto L中的标号L尚未在符号表中出现，则把L填入表中，置L的“定义否”标志为“未”，把nextstat填进L的地址栏中作为新链首，然后，产生四元式(p)（goto 0），其中0为链尾标志。若L已在符号表中出现（但“定义否”标志为“未”），则把它的地址栏中的编号（记为p）取出，把nextstat填进该栏作新链首，然后，产生四元式(q)（goto p）。,一旦标号L定

28、义时，我们将根据这条链回填那些待填转移目标的四元式。一般而言，假定用下面的产生式来定义标号语句,Slabel Slabeli：,1.若i所指的标识符（假定为L）不在符号表中，则把它填入，置类型为标号，定义否为已，地址为nextstat。2.若L已在符号表中但类型不为标号或定义否为已，则报告出错。3.若L已在符号表中，则把标志未改为已，然后，把地址栏中的链首（记为q）取出，同时把nextstat填在其中，最后，执行回填。,过程调用的四元式产生,过程调用的实质是把程序控制转移到子程序,在转子之前,必须用某种办法把实参的信息传给调用的子程序。传递实参信息方面有种种不同的方法,我们这里只讨论一种,即传

29、实参地址的方式。若实参是一个变量或数组，则直接传递地址。若实参是表达式，如：A+B或2，则把它们的值计算出来，并存放在一个临时变量T中，然后传递T的地址。,传递实参地址的一个简单办法是：把实参地址逐一放在转指令的前面；,例：过程调用：Call S(A+B,Z)译为：计算AB的值置于T中/*T:=A+B*/Par T/*第一个实参的地址*/Par Z/*第二个实参的地址*/Call S/*转指令*/,为了处理在实参时记住每个实参的地址，以便最后把它们排在Call指令之前，我们需要把这些地址存放起来，我们可用队列来存放。,例：一个描述过程调用语句的文法如下：(1)S call i()(2)1,E(

30、3)E,它的语法制导翻译见P178,例：写一个翻译过程调用语句的语义子程序。要求生 成的四元式序列在转指令之前的参数四元式par 按反序出现（与实在参数的顺序相反）。,过程调用语句的文法如下：(1)S call i()(2)1,E(3)E,(1)E 建一个arglist.Stack栈，它仅包含一项E.Place(2)1,E 将E.Palce压入arglist.Stack栈，arglist.Stack:=arglist1.Stack(3)S call i()While arglist.Stacknull do begin 将arglist.Stack栈顶弹出生成 Gen(par,_,_,p)en

31、d;Gen(call,_,_,Entry(i),简单说明语句的翻译,程序设计语言中的说明语句旨在定义各种形式的有名实体，如常量、变量、数组、记录(结构)、过程、子程序等等，说明语句的种类也多，对象说明、变量说明、类型说明、过程说明等等。编译程序把说明语句中定义的名字和性质登记在符号表中，用以检查名字的引用和说明是否一致。,简单说明句的翻译程序设计语言中最简单的说明句的语法描述为：Dintegernamelist|realnamelistnamelisenamelist，id|id即使用关键字integer和real定义一串名字的性质。对这种说明句的翻译是指在符号表中登录该名和性质。用上述文法来

32、制导翻译(自下而上)存在着这样一个问题，我们只能在把所有的名字都归约成namelist后才能把它们的性质登记进符号表,我们可以把上述的文法改写成：DD1,id|integer id|realid这样,就能把所说明的性质及时地告诉每个名字id，或者说，每当读进一个标识符时，就可以把它的性质登记在符号表中，不用把它们集中起来最后再成批登记了。,现在来定义这些产生式所对应的语义动作，给非终结符D一个语义变量D.ATT，用以记录说明句所引入的名字的性质(int还是real)，使用过程enter(id,A)把名字id和性质A登录在名表中。(1)Dintegerid enter(id,int);D.ATT

33、=int(2)Drealid enter(id,real);D.ATT=real(3)DD1,id enter(id,D1.ATT);D.ATT=D1.ATT,过程中的说明,现在主要讨论过程中的局部变量的说明。我们要为过程的局部名字安排存储，对这些名字建符号表时，要记录名字，类型和相对地址。为了记录相对地址，可以使用一个变量offset。记录当前可用的空间的开始地址，每次分配一个变量，将offset增加相应的值，offset增加的值由名字的类型决定，即由数据对象的宽度决定，宽度用Width来表示。例：产生式 语义动作 D real id enter(id,real,offset);D.ATT:=real;D.Width:=8;offset:=offset+D.Width;,数组的翻译：,一般编译程序对数组的处理是把数组的相关信息汇集在一个叫做“内情向量”的表格中，“内情向量”，包括数组的类型，维数，各维的上、下界，每维的长度以及数组的首地址。,其中：li表示每维的下界，ui表示每维的上界,di为 每维的长度,di=ui-li+1 C为Conspart=a-C 的第二项,a为数组的首地址，n为数组的维数,type 为数组的类型,X:=ai,j 翻译成四元式的结构：T1:=VARPART;T2:=CONSPART;T3:=T2T1;X:=T3;,