编译原理第18讲(第八章).ppt

《编译原理第18讲(第八章).ppt》由会员分享，可在线阅读，更多相关《编译原理第18讲(第八章).ppt（45页珍藏版）》请在三一办公上搜索。

1、第八章 语义分析,8.1 语义处理概述8.2 属性文法和语法制导翻译8.3 中间代码的形式8.4 中间代码的生成(典型语句的翻译)8.5 符号表,8.3 中间代码生成,简单赋值语句（四元式）的翻译简单说明语句的翻译布尔表达式的翻译控制语句的翻译过程调用的翻译（四元式产生）数组的翻译,四元式形式:,result:=arg1 op arg2,语义属性：,id.name,E.place/E内容所在的地址，指针,函数：,lookup(id.name);/在符号表中查找指定名字的标识符，如果存在则返回该项指针，否则返回nil,过程：,emit(t:=arg1 op arg2);/生成一个四元式（文本）,

2、newtemp;/创建一个新的临时变量，并返回该临时变量的地址,(op,arg1,arg2,result)或,8.3.2 简单赋值语句的翻译（四元式）,(1)Sid:=E P:=lookup(id.name);if P nil then emit(P“:=”E.place)/引号中的部分按原样输出 else error(2)EE1+E2 E.place:=newtemp;emit(E.place“:=”E1.place“+”E2.place)(3)E-E1 E.place:=newtemp;emit(E.place“:=”“uminus”E1.place)(4)E(E1)E.place:=E1

3、.place/无须分配新空间，相当于改写指针，E.place看成一个指针(5)Eid E.place:=newtemp;P:=lookup(id.name);if Pnil then E.place:=P else error,产生式和语义描述：,简单赋值语句的属性文法,简单赋值语句的翻译举例,例：x=y*z 翻译为四元式(*,z,y,t1)(=,t1,_,x)例：a=b*c+b*d 翻译为四元式(*,b,c,t1)(*,b,d,t2)(+,t1,t2,t3)(+,t3,_,a),8.3.3 简单说明语句的翻译,最简单的说明句的语法：integernamelistrealnamelistnam

4、elistnamelist，idid用自下而上翻译，文法改写：1，id integer id real id主要语义动作是在符号表中登录名字及其性质。函数enter(id,A)表示：将id的属性A填入符号表,简单说明语句的属性文法,(1)integer identer(id,int);D.att:=int(2)real id enter(id,real);D.att:=real(3),id enter(id，.att);D.att:=.att注意：一般，变量的说明语句并不生成相应的目标代码（四元式）,过程中的说明语句的属性文法,PD offset:=0.real identer(id,real

5、,offset);D.att:=real;D.width:=8;offset:=offset+D.width用全程变量offset表示变量在本过程的数据区的相对位置,增加的量为数据对象的宽度,用属性width表示.,8.3.4 布尔表达式的翻译,程序设计语言中的布尔表达式有两个作用。一是计算逻辑值，更多的情况是二，用做改变控制流语句中的条件表达式，如在if-then，if-then-else，或是while-do语句中那样。属性nextstat：表示下一个四元式序号,EE1 or E2Eplace=newtemp；emit（Eplace=E1placeorE2place）EE1 and E2E

6、place=newtemp；emit（Eplace=E1place andE2place）Enot E1Eplace=newtemp：；emit（Eplace=notE1place）E（E1）Eplace=E1placeEid1 relop id2Eplace=newtemp；emit（if id1.place relop id2.place gotonextstat+3）；emit（Eplace=0）；emit（gotonextstat+2）；emit（Eplace=1）EtrueEplace=newtemp；emit（Eplace=1）EfalseEplace=newtemp；emit（E

7、place=0）,布尔表达式的属性文法,布尔表达式的翻译举例,例：a or b and not c 翻译成四元式序列(1)t1:=not c(2)t2:=b and t1(3)t3:=a or t2 例：a b 翻译成四元式序列，可看成等价的条件语句 if a b then 1 else 0(1)if ab goto(4)(2)t:=0(3)goto(5)(4)t:=1(5),8.3.5 控制语句的翻译,现在讨论出现在if-then；if-then-else和while-do等语句中的布尔表达式E的翻译。这三种语句的语法为：Sif E then S1 if E then S1 else S2

8、while E do S1 这些语句的代码结构示意图如下图所示，其中使用.和。两个出口分别表示E为真和假时控制流向的转移。分别叫做真出口和假出口。,8.3.5.1 控制语句的代码结构,注：此处的代码都是中间代码（比如四元式）,E.false,控制语句,S,if E then S,1,E的代码,S1的代码,E.false:,控制语句的结构(1),E.true,E.true:,S,1,2,E.false,控制语句,if E then S,else S,E.true,goto S.next,E.false:,S.next:,控制语句的结构(2),E.true:,E的代码,S1的代码,S2的代码,E.

9、false,控制语句,S,1,goto S.begin,E.false:,S.begin:,控制语句的结构(3),E.true,E.true:,E的代码,S1的代码,Sif E then S1 E.true:=nemlable;E.false:=S.next;S1.next:=S.next;S.code:=E.code|gen(E.true:)|S1.code Sif E then S1 else S2 E.true:=nemlable;E.false:=nemlable;S1.next:=S.next;S2.next:=S.next S.code:=E.code|gen(E.true:)|S

10、1.code|gen(goto S.next)|gen(E.false:)|S2.code Swhile E do S1.,8.3.5.2 控制语句结构的属性文法,控制语句中布尔表达式的翻译,作为条件表达式的E，仅把E翻译成代码是一串条件转(jrop,B,C,L)和无条件转(jump,_,_,L)四元式。翻译的基本思路是：（1）对于E为a rop b的形式生成代码为：if a rop b goto E.true 和goto E.false。（2）对于E为E1 or E2的形式，若E1是真，则可知道E为真即E1的真出口和E的真出口一样。如果E1是假，那么必须计算E2，E1的假出口就是E2代码 的

11、第一个四元式标号，这时E2的真出口和假出口分别与E的真出口和假出口一样。（3）类似的考虑适于E为E1 and E2等情形。,例：布尔表达式 af,可翻译成如下四元式：（1）if af goto E.true（6）goto E.false（翻译不是最优，（2）四元式不需要）,我们把该表达式放在条件语句中考虑，可翻译成如下的四元式序列（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的四元式）/(E.true)入口

12、（p）goto（q）（p+1）（关于S2的四元式）/(E.false)入口（q）,例：语句if ab or cd and ef then S1 else S2,“拉链”与“回填”技术,上述四元式（1）和（5），（4）和（6）的转移地址并不能在产生这些四元式的同时得知。例如（1）和（5）的转移地址是在整个布尔表达式的四元式产生完毕之后才得知。通常采用拉链回填的处理方法：为了记录需回填地址的四元式，把需回填真出口的四元式拉成一链，把需回填假出口的四元式拉成一链，分别称做“真”链和“假”链。即所谓“拉链”。一旦真假出口确定下来之后，用顺着“真”链和“假”链把真假出口补上。即所谓“回填”。,“拉链”的

13、例子,若有四元式序列：（10）gotoEtrue（20）gotoEtrue（30）gotoEtrue则把需回填Etrue（真出口）的四元式（10），（20）和（30）链成（10）goto（0）（20）goto（10）（30）goto（20）把地址（30）称作链首，0为链尾标志，即地址（10）为链尾。注：链的元素是四元式序号。即：30,20,10构成一个链,“回填”的例子,如果在后续的语义分析确定E的真出口是999，则回填后四元式序列变为：,（10）goto（0）（20）goto（10）（30）goto（20）,（10）goto999（20）goto999（30）goto999,回填后,例：语句

14、if ab or cd and ef then S1 else S2,布尔表达式翻译需要的语义元素:,语义属性：E.true 含义是“真”链 E.false 含义是“假”链 E.codebegin 含义是E所生成的四元式序列的第一个四元式序号 nextstat 含义是下一四元式地址语义函数：merge(p1,p2)把p1的链头填在p2的链尾 backpatch(p,t)把p所链接的每个四元式的第四区段都填为t,true：对于E.true而言，其含义是需要真出口的四元式序列所构成的链的链首。（注意：以前的提到的E.true是指E的真出口，含义有所不同）比如：（10）goto0（20）goto10

15、（30）goto20若E.true为30，则说明序号为30的四元式需要真出口地址，然后需要真出口地址的四元式依次是序号为20，10。其中10的goto部分为0（也可以写成），表明第10个四元式是链尾（也就是第一个需要E的真出口的四元式）。这样所有需要E的真出口的四元式被“串”在一起，E.true表示这个“真”链的链首。false:参考true,例：true 和 false,有两个链p1和p2P1=110101.goto 0105.goto 101110.goto 105P2=210200.goto 0210.goto 200,merge(p1,p2),新链首为p2210101.goto 010

16、5.goto 101110.goto 105200.goto 110210.goto 200,拉链活动主要由merge语义函数完成，该语义函数将小的链合成大的链,例：merge(p1,p2),101.goto 0105.goto 101110.goto 105200.goto 110210.goto 200,backpatch(p,999),101.goto 999105.goto 999110.goto 999200.goto 999210.goto 999,例：backpatch(p,t),p为一条链的链首且p=210,(1),E,E,1,or E,2,backpatch(E,1,.fal

17、se,E,2,.Codebegin);,E.Codebegin:=E,1,.codebegin;,E.true:=merge(E,1,.true,E,2,.true),E.false:=E,2,.false,(2),E,E,1,and E,2,backpatch(E,1,.true,E,2,.codebegin);,E.Codebegin:=E,1,.codebegin;,E.true:=E,2,.true;,E.false:=merge(E,1,.false,E,2,false);,(3)E,not E,1,E.true:=E,1,.false;,E.Codebegin:=E,1,.code

18、begin;,E.false:=E,1,.true,8.3.5.3 控制语句中布尔表达式的属性文法,控制语句中布尔表达式的属性文法(续),（,10,）,goto L,（,10,）,goto 0,链尾,（,10,）,（,20,）,goto L,（,20,）,goto 10,（,30,）,goto L,(30),goto 20,链首,30,）,（,40,）,L,：,（,40,）,L:.,8.3.5.4 GOTO语句翻译拉链返填,符号表name type def addL label not r,(p)goto 0(q)goto p(r)goto q,建链的方法是：若 中的标号尚未在符号表中出现，则

19、把填入表中，置的“定义否”标志为“未”，把填进的地址栏中 作为新链首，然后，产生四元式（），其中为链尾标志。若已在符号表中出现（但“定义否”标志为“未”），则把它的地址栏中的编号（记为）取出，把nextstat填进该栏作新链首，然后，产生四元式（）。,定义标号语句的产生式,：那么，当用：进行归约时，应做如下的语义动作：1.若所指的标识符（假定为）不在符号表中，则把它填入，置“类型”为“标号”，“定义否”为“已”，“地址”为nextstat。2.若已在符号表中但“类型”不为“标号”或“定义否”为“已”，则报告出错。3.若已在符号表中，则把标志“未”改为“已”，然后，把地址栏中的链首（设为）取出，

20、同时把nextstat填在其中，最后，执行backpatch（，nextstat）。,翻译语句时，还有两点必须注意,第一：相同名字的标号可以在不同名字作用域中定义。如：（）（）：（）；/延迟使用（）（）：（）（）第二，转移标号是非法的（）for=to10do（）begin goto；（）for=to 20 do（）begin goto；（）L:endfor endfor i 处理到第（）行后，第（）行的goto目标得以解决。而第（）行的goto是非法的，但只有当循环关闭时才能确定。,8.3.6 过程调用的翻译（四元式产生）,过程调用的实质是把程序控制转移到子程序(过程段)。在转子之前必须用某种

21、办法把实在参数的信息传给被调用的子程序，并且应该告诉子程序在它工作完毕后返回到什么地方。传递实在参数，过程调用（，）将被翻译成：计算置于中的代码=第一个实参地址第二个实参地址转子指令,如何产生反映这种模式的四元式,过程调用语句的文法：（）Scall（arglist）（），E（）E,在处理实在参数串的过程中记住每个实参的地址,（）Scall（arglist）For队列argulist.QUEUE 的每一项Do Gen(par _,_,p)；Gen(call,_,_，entry(i)（），E 把.PLACE 排在arglist.QUEUE 的末端；arglist.QUEUE:=arglist.QU

22、EUE（）E 建立一个arglist.QUEUE，它只包含一项E.PLACE?记录实在参数个数,8.3.7 数组的翻译,数组说明和数组元素的引用,将产生两组计算数组元素地址的四元式一组计算，将它放在某个临时单元中；一组计算，放在另一个临时单元T1中。同时用表示数组元素的地址。对应“数组元素引用”（引用其值）和“对数组元素赋值”有两个相应的四元式：“变址取数”和“变址存数”。“变址取数”的四元式是：（，T1 T，）相当于=T1 T“变址存数”的四元式是：（，T1 T）相当于T1 T:=x,习题,P2032.请将表达式-(a+b)*(c+b)-(a+b+c)分别表示成逆波兰式、三元式、四元式序列3.,