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

第八章 语义分析,8.1 语义处理概述 8.2 属性文法和语法制导翻译 8.3 中间代码的形式 8.4 中间代码的生成(典型语句的翻译) 8.5 符号表,8.3 中间代码生成,简单赋值语句（四元式）的翻译 简单说明语句的翻译 布尔表达式的翻译 控制语句的翻译 过程调用的翻译（四元式产生） 数组的翻译,四元式形式:,result := arg1 op arg2,语义属性：,,E.place /E内容所在的地址，指针,函数：,lookup() ; /在符号表中查找指定名字的标识符，如果存在则返回该项指针，否则返回nil,过程：,emit(t := arg1 op arg2); /生成一个四元式（文本）,newtemp; /创建一个新的临时变量，并返回该临时变量的地址,(op , arg1, arg2, result) 或,8.3.2 简单赋值语句的翻译（四元式）,(1) Sid:= E P:=lookup(); 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.place /无须分配新空间，相当于改写指针，E.place看成一个指针 (5) Eid E.place:=newtemp; P:=lookup(); 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 简单说明语句的翻译,最简单的说明句的语法： integernamelistrealnamelist namelistnamelist，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,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 E2 Eplace=newtemp； emit（Eplace=E1place orE2place） EE1 and E2 Eplace =newtemp； emit（Eplace=E1place andE2place） Enot E1 Eplace =newtemp：； emit（Eplace=notE1place） E（E1） Eplace=E1place Eid1 relop id2 Eplace=newtemp； emit（if id1.place relop id2.place gotonextstat+3）； emit（Eplace=0）； emit（gotonextstat+2）； emit（Eplace=1） Etrue Eplace=newtemp； emit（Eplace=1） Efalse Eplace=newtemp； emit（Eplace=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 while E do S1 这些语句的代码结构示意图如下图所示，其中使用.和。两个出口分别表示E为真和假时控制流向的转移。分别叫做真出口和假出口。, 控制语句的代码结构,注：此处的代码都是中间代码（比如四元式）,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.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:) | S1.code | gen(goto S.next) | gen(E.false:) | S2.code Swhile E do S1 , 控制语句结构的属性文法,控制语句中布尔表达式的翻译,作为条件表达式的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代码 的第一个四元式标号， 这时E2的真出口和假出口分别与E的真出口和假出口一样。 （3）类似的考虑适于E为E1 and E2等情形。,例：布尔表达式 af,可翻译成如下四元式： （1） if af goto E.true （6） goto E.false （翻译不是最优，（2）四元式不需要）,我们把该表达式放在条件语句中考虑，可翻译成如下的四元式序列 （1） if ab goto （7） /（7）是整个布尔表达式的真出口 （2） goto （3） （3） if cd goto （5） （4） goto (p+1) /（p+1）是整个布尔表达式的假出口 （5） if ef goto （7） （6） goto （p+1） （7） （关于S1的四元式） / (E.true ) 入口 （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）的转移地址是在整个布尔表达式的四元式产生完毕之后才得知。通常采用拉链回填的处理方法： 为了记录需回填地址的四元式，把需回填真出口的四元式拉成一链，把需回填假出口的四元式拉成一链，分别称做“真”链和“假”链。即所谓“拉链”。 一旦真假出口确定下来之后，用顺着“真”链和“假”链把真假出口补上。即所谓“回填”。,“拉链”的例子,若有四元式序列： （10） goto Etrue （20） goto Etrue （30） goto Etrue 则把需回填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） goto 999 （20） goto 999 （30） goto 999,回填后,例：语句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） goto 0 （20） goto 10 （30） goto 20 若E.true为30，则说明序号为30的四元式需要真出口地址，然后需要真出口地址的四元式依次是序号为20，10。其中10的goto部分为0（也可以写成 ），表明第10个四元式是链尾（也就是第一个需要E的真出口的四元式）。这样所有需要E的真出口的四元式被“串”在一起，E.true表示这个“真”链的链首。 false:参考true,例：true 和 false,有两个链p1和p2 P1=110 101 . goto 0 105 . goto 101 110 . goto 105 P2=210 200 . goto 0 210 . goto 200,merge(p1,p2),新链首为p2210 101 . goto 0 105 . goto 101 110 . goto 105 200 . goto 110 210 . goto 200,拉链活动主要由merge语义函数完成，该语义函数将小的链合成大的链,例：merge(p1,p2),101 . goto 0 105 . goto 101 110 . goto 105 200 . goto 110 210 . goto 200,backpatch(p,999),101 . goto 999 105 . goto 999 110 . goto 999 200 . goto 999 210 . goto 999,例：backpatch(p,t),p为一条链的链首且p=210,(1),E,E,1,or 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,(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,.codebegin;,E.false:= E,1,.true, 控制语句中布尔表达式的属性文法,控制语句中布尔表达式的属性文法(续),（,10,）,goto L,（,10,）,goto 0,链尾,（,10,）,（,20,）,goto L,（,20,）,goto 10,（,30,）,goto L,(30),goto 20,链首,30,）,（,40,）,L,：,（,40,）,L: ., GOTO语句翻译拉链返填,符号表 name type def add L label not r,(p) goto 0 (q) goto p (r) goto q,建链的方法是： 若 中的标号尚未在符号表中出现，则把填入表中，置的“定义否”标志为“未”，把填进的地址栏中 作为新链首， 然后，产生四元式（ ），其中为链尾标志。若已在符号表中出现（但“定义否”标志为“未”），则把它的地址栏中的编号（记为）取出，把nextstat填进该栏作新链首， 然后，产生四元式（ ）。,定义标号语句的产生式, ： 那么，当用：进行归约时，应做如下的语义动作： 1.若所指的标识符（假定为）不在符号表中，则把它填入，置“类型”为“标号”，“定义否”为“已”，“地址”为nextstat。 2.若已在符号表中但“类型”不为“标号”或“定义否”为“已”，则报告出错。 3.若已在符号表中，则把标志“未”改为“已”，然后，把地址栏中的链首（设为）取出，同时把nextstat填在其中，最后，执行backpatch（，nextstat）。,翻译语句时，还有两点必须注意,第一：相同名字的标号可以在不同名字作用域中定义。如： （） （） ： （） ；/延迟使用 （） （） ： （） （） 第二，转移标号是非法的 （）for = to 10 do （） begin goto； （） for = to 20 do （） begin goto ； （） L: end for end for i 处理到第（）行后，第（）行的goto目标得以解决。而第（）行的goto 是非法的，但只有当循环关闭时才能确定。,8