《编译原理第18讲(第八章).ppt》由会员分享，可在线阅读，更多相关《编译原理第18讲(第八章).ppt（45页珍藏版）》请在金锄头文库上搜索。
1、第八章第八章 语义分析语义分析8.1 语义处理概述语义处理概述8.2 属性文法和语法制导翻译属性文法和语法制导翻译8.3 中间代码的形式中间代码的形式8.4 中间代码的生成中间代码的生成(典型语句的翻译典型语句的翻译)8.5 符号表符号表8.3 中间代码生成中间代码生成简单赋值语句（四元式）的翻译简单赋值语句（四元式）的翻译简单说明语句的翻译简单说明语句的翻译布尔表达式的翻译布尔表达式的翻译控制语句的翻译控制语句的翻译过程调用的翻译（四元式产生）过程调用的翻译（四元式产生）数组的翻译数组的翻译四元式形式四元式形式: result := arg1 op arg2 语义属性：语义属性：id.nam
2、e, E.place /E内容所在的地址，指针内容所在的地址，指针 函数：函数：lookup(id.name) ;/在符号表中查找指定名字的标识符，如果存在则返在符号表中查找指定名字的标识符，如果存在则返回该项指针，否则返回回该项指针，否则返回nil 过程：过程：emit(t := arg1 op arg2);/生成一个四元式（文本）生成一个四元式（文本）newtemp;/创建一个新的临时变量，并返回该临时创建一个新的临时变量，并返回该临时变量的地址变量的地址 (op , arg1, arg2, result) 或或8.3.2 简单赋值语句的翻译（四元式）简单赋值语句的翻译（四元式）(1) S
3、id:= 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.place /无须分配新空间，相当于改写指针，无须分配新空间，相当于改写指针，E.place看成一
4、个指看成一个指针针(5) Eid E.place:=newtemp; P:=lookup(id.name); if P nil 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 简单说
5、明语句的翻译简单说明语句的翻译最简单的说明句的语法：最简单的说明句的语法：integernamelistrealnamelistnamelistnamelist，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:
6、=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表示变量在本过程的数据区的相对位置表示变量在本过程的数据区的相对位置,增加的量为增加的量为数据对象的宽度数据对象的宽度,用属性用属性wid
7、th表示.8.3.4 布尔表达式的翻译布尔表达式的翻译 程序设计语言中的布尔表达式有两个作用。一是计算逻辑值，更多的情况是二，用做改变控制流语句中的条件表达式，如在if-then，if-then-else，或是while-do语句中那样。属性属性nextstatnextstat：表示下一个四元式序号：表示下一个四元式序号EE1 or E2Eplace =newtemp； emit（Eplace =E1placeorE2place）EE1 and E2Eplace =newtemp；emit（Eplace =E1place andE2place）Enot E1Eplace =newtemp：；：
8、； 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（Eplace =0）布尔表达式的属性文法布尔表达式的属性文法布尔表达式的翻译举例布尔表达式的翻译
9、举例例：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-thenif-then；if-then-elseif-then-else和和while-dowhile-do等语句中的布尔表达式等语句中的布尔表达式E E的翻译。
10、的翻译。这三种语句的语法为：这三种语句的语法为： SifSif E then S1 E then S1 if E then S1 else S2 if E then S1 else S2 while E do S1 while E do S1 这些语句的代码结构示意图如下图所示，其中使用这些语句的代码结构示意图如下图所示，其中使用. .和。两个出口分别表示和。两个出口分别表示E E为真和假时控制流向的转移。分为真和假时控制流向的转移。分别叫做别叫做真出口真出口和和假出口假出口。 8.3.5.1 控制语句的代码结构控制语句的代码结构注：此处的代码都是中间代码（比如四元式）注：此处的代码都是中间代
11、码（比如四元式）E.false 控制语句控制语句 Sif E then S1E E的代码的代码 S S1 1的代码的代码E.false: 控制语句的结构控制语句的结构(1)E.trueE.true: S12E.false控制语句控制语句if E then S else SE.truegoto S.nextE.false: S.next:控制语句的结构控制语句的结构(2)E.true:E E的代码的代码S S1 1的代码的代码S S2 2的代码的代码E.false 控制语句控制语句Swhile E do S1 goto S.beginE.false: S.begin: 控制语句的结构控制语句的结
12、构(3)E.trueE.true:E E的代码的代码S S1 1的代码的代码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) |
13、 gen(E.false:) | S2.code Swhile E do S1 . 8.3.5.2 控制语句结构控制语句结构的属性文法的属性文法控制语句中布尔表达式的翻译控制语句中布尔表达式的翻译 作为作为条件表达式的条件表达式的E E，仅把，仅把E E翻译成代码是一串翻译成代码是一串条件条件转转( (jrop,B,C,Ljrop,B,C,L) )和和无条件转无条件转( (jump,_,_,Ljump,_,_,L) )四元式。四元式。翻译的基本思路是：翻译的基本思路是： （1 1）对于）对于E E为为a a roprop b b的形式生成代码为：的形式生成代码为：if a if a ropro
14、p b b gotogoto E.trueE.true 和和gotogoto E.falseE.false。 （2 2）对于）对于E E为为E1 or E2E1 or E2的形式，若的形式，若E1E1是真，则可知道是真，则可知道E E为真即为真即E1E1的真出口和的真出口和E E的真出口一样。如果的真出口一样。如果E1E1是假，那是假，那么必须计算么必须计算E2E2，E1E1的假出口就是的假出口就是E2E2代码代码 的第一个四元式的第一个四元式标号，标号， 这时这时E2E2的真出口和假出口分别与的真出口和假出口分别与E E的真出口和假的真出口和假出口一样。出口一样。 （3 3）类似的考虑适于）
15、类似的考虑适于E E为为E1 and E2E1 and E2等情形。等情形。 例：例：布尔表达式布尔表达式 ab or cf可翻译成如下四元式：可翻译成如下四元式：（1） if abgotoE.true （2） goto （3）（3） if cf goto E.true（6） goto E.false（翻译不是最优，（翻译不是最优，（2）四元式不需要）四元式不需要）我们把该表达式放在条件语句中考虑，可翻译成如下的四元式序列我们把该表达式放在条件语句中考虑，可翻译成如下的四元式序列（1）ifabgoto（7） /（7）是整个布尔表达式的真出）是整个布尔表达式的真出口口（2）goto（3）（3）i
16、fcdgoto（5）（4）goto(p+1) /（p+1）是整个布尔表达式的假出）是整个布尔表达式的假出口口（5）ifefgoto（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 1）和（）和（5 5），（），（4 4）和（）和（6 6）的）的转移地址并不能在产生这些四元式的同时得知。
17、转移地址并不能在产生这些四元式的同时得知。例如（例如（1 1）和（）和（5 5）的转移地址是在整个布尔表达）的转移地址是在整个布尔表达式的四元式产生完毕之后才得知。通常采用拉链式的四元式产生完毕之后才得知。通常采用拉链回填的处理方法：回填的处理方法： 为了记录需回填地址的四元式，把需回填真为了记录需回填地址的四元式，把需回填真出口的四元式拉成一链，把需回填假出口的四元出口的四元式拉成一链，把需回填假出口的四元式拉成一链，分别称做式拉成一链，分别称做“真真”链和链和“假假”链。即链。即所谓所谓“拉链拉链”。 一旦真假出口确定下来之后，用顺着一旦真假出口确定下来之后，用顺着“真真”链和链和“假假”
18、链把真假出口补上。即所谓链把真假出口补上。即所谓“回填回填”。“拉链拉链”的例子的例子若有四元式序列：若有四元式序列：（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构成一个链构成一个链“回
19、填回填”的例子的例子如果在后续的语义分析确定如果在后续的语义分析确定E的真出口是的真出口是999，则回填后四元式序列变为：，则回填后四元式序列变为：（10）goto（0） （20）goto（10） （30）goto（20）（10）goto999 （20）goto999 （30）goto999回填后(1) if ab goto (7) (E.true ) (1) 和和(2) goto (3) 拉链拉链（真）（真）(3) if cd goto (5)(4) goto (p+1)(E.false) (4) 和和(6)(5) if ef goto (7)拉链拉链（假）（假）(6) goto (p+1)
20、(7)( S1的四元式的四元式 (p-1) ）(p) goto (q)(p+1) (S2的四元式的四元式(q-1) ）(q)(5)例：语句例：语句if ab or cd and ef then S1 else S2布尔表达式翻译需要的语义元素布尔表达式翻译需要的语义元素: :语义属性：语义属性： E.trueE.true 含义是含义是“真真”链链 E.falseE.false 含义是含义是“假假”链链 E.codebeginE.codebegin 含义是含义是E E所生成的四元式序列的第一个四元式序号所生成的四元式序列的第一个四元式序号 nextstatnextstat 含义是下一四元式地址含
21、义是下一四元式地址语义函数：语义函数： merge(p1, p2) merge(p1, p2) 把把p1p1的链头填在的链头填在p2p2的链尾的链尾 backpatch(pbackpatch(p, t) , t) 把把p p所链接的每个四元式的第四区段都填为所链接的每个四元式的第四区段都填为t ttrue：对于E.true而言，其含义是需要真出口的四元式序列所构成的链的链首。（注意：以前的提到的E.true是指E的真出口，含义有所不同 ）比如：（10）goto0 （20）goto10 （30）goto20若E.true为30，则说明序号为30的四元式需要真出口地址，然后需要真出口地址的四元式依
22、次是序号为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 200merge(p1,p2)新链首为p2210101 . goto 0105 . goto 101110 . goto 105200 . goto 1
23、10210 . goto 200 拉链活动主要由merge语义函数完成，该语义函数将小的链合成大的链例：例：merge(p1,p2)101 . goto 0105 . goto 101110 . goto 105200 . goto 110210 . goto 200backpatch(p,999)101 . goto 999105 . goto 999110 . goto 999200 . goto 999210 . goto 999例：例：backpatch(p,t)p为一条链的链首且为一条链的链首且p=210(1) EE1 or E2 backpatch(E1.false, E2.Cod
24、ebegin); E.Codebegin:= E1.codebegin; E.true:=merge(E1.true, E2.true) E.false:= E2.false(2) EE1 and E2 backpatch(E1.true, E2.codebegin); E.Codebegin:= E1.codebegin; E.true:= E2.true; E.false:= merge(E1.false, E2false);(3) Enot E1 E.true:= E1.false; E.Codebegin:= E1.codebegin; E.false:= E1.true8.3.5.3
25、 控制语句中布尔表达式的属性文法控制语句中布尔表达式的属性文法控制语句中布尔表达式的属性文法控制语句中布尔表达式的属性文法(续续) （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建链的方法是：建链的方法是：4若若 中的标号尚未在符号表中出现，则把中的标号尚
26、未在符号表中出现，则把填入表中，置的填入表中，置的“定义否定义否”标志为标志为“未未”，把，把填进的地址栏中填进的地址栏中 作为新链首，作为新链首，4然后，产生四元式（），其中为链尾标然后，产生四元式（），其中为链尾标志。若已在符号表中出现（但志。若已在符号表中出现（但“定义否定义否”标志为标志为“未未”），则把它的地址栏中的编号（记为）取出，把），则把它的地址栏中的编号（记为）取出，把nextstat填进该栏作新链首，填进该栏作新链首，4然后，产生四元式（）。然后，产生四元式（）。定义标号语句的产生式定义标号语句的产生式：那么，当用：进行归约时，应做如下的语义动作：1.若所指的标识符（假定为
27、）不在符号表中，则把它填入，置“类型”为“标号”，“定义否”为“已”，“地址”为nextstat。2.若已在符号表中但“类型”不为“标号”或“定义否”为“已”，则报告出错。3.若已在符号表中，则把标志“未”改为“已”，然后，把地址栏中的链首（设为）取出，同时把nextstat填在其中，最后，执行backpatch（，nextstat）。 翻译语句时，还有两点必须注意翻译语句时，还有两点必须注意第一：相同名字的标号可以在不同名字作用域中定义。如：第一：相同名字的标号可以在不同名字作用域中定义。如：（）（）（）（） ：（）（） ；/延迟使用延迟使用（）（） （）（） ：（）（） （）（）第二，转移
28、标号是非法的第二，转移标号是非法的（）（）for =to10do（）（） begin goto；（）（） for =to 20 do（）（） begin goto； （）（） L: endfor endfor i 处理到第（）行后，第（）行的处理到第（）行后，第（）行的goto目标得以解决。而第（）行目标得以解决。而第（）行的的goto是非法的，但只有当循环关闭时才能确定。是非法的，但只有当循环关闭时才能确定。8.3.6 过程调用的翻译（四元式产生）过程调用的翻译（四元式产生）4过程调用的实质是把程序控制转移到子程序(过程段)。在转子之前必须用某种办法把实在参数的信息传给被调用的子程序，并且应
29、该告诉子程序在它工作完毕后返回到什么地方。4传递实在参数 ，过程调用（，）将被翻译成：计算置于中的代码=第一个实参地址第二个实参地址转子指令如何产生反映这种模式的四元式如何产生反映这种模式的四元式过程调用语句的文法：（）（）Scall（arglist）（）（），E（）（）E在处理实在参数串的过程中记住每个实参的地址在处理实在参数串的过程中记住每个实参的地址（）（）Scall（arglist） For队列队列argulist.QUEUE 的每一项的每一项Do Gen(par _,_,p)； Gen(call,_,_，entry(i)（）（），E 把把.PLACE 排在排在arglist .QUE
30、UE 的末端；的末端； arglist.QUEUE:= arglist .QUEUE （）（）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)分别表示成逆波兰式、三元式、四元式序列1.3.
