语义分析和中间代码产生精.ppt

《语义分析和中间代码产生精.ppt》由会员分享，可在线阅读，更多相关《语义分析和中间代码产生精.ppt（49页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、语义分析和中间代码产生第1页，本讲稿共49页第五章语法制导翻译和中间代码产生24 二月 20232语义分析的任务：语义分析的任务：根据语法成分的结构，分析其含义，并用一种内部形式（中间代码）或直接用目标语言表示出来。具体：静态语义检查和翻译包括：类型检查（操作符是否相容，例如%）控制流检查（break是否有switch和for,while）一致性检查（int a;float a;）相关名字检查、等等第2页，本讲稿共49页第五章语法制导翻译和中间代码产生24 二月 202335.1 属性文法一、属性一、属性：一、属性：一般用来描述客观存在的事物或人的特性。例如，学生的姓名、年龄、性别等；商品的颜

2、色、重量、单价等。编译技术中用属性来描述计算机处理对象的特征。例如：X.Type ,X.Place,X.val等分别描述X的类型，存储位置、值等不同的特征。属性分两类：综合属性：一般用于“自下而上”传递信息。继承属性：一般用于“自上而下”传递信息。第3页，本讲稿共49页第五章语法制导翻译和中间代码产生24 二月 20234二、属性文法对于某个压缩了的上下文无关文法，当为每个文法符号引进一组属性，且让该文法中的重写规则附加以语义规则时，称该上下文无关文法为属性文法。形式定义：形式定义：一个属性文法形式上定义为一个三元组AG,AG=(G,V,E)。其中G表示一个上下文无关文法；V表示属性的有穷集；

3、E表示属性的断言或谓词的有穷集。第4页，本讲稿共49页第五章语法制导翻译和中间代码产生24 二月 20235三、综合属性从语法分析树的角度来看，如果一个结点的某一属性，其值由子结点的属性之值来计算，则称该属性为综合属性。综合属性用于“自下而上”传递信息。第5页，本讲稿共49页第五章语法制导翻译和中间代码产生24 二月 20236例例1：算术表达式求值的属性文法。：算术表达式求值的属性文法。规则式规则式语义规则语义规则1.LEprint(E.val)2.EE1+TE.val:=E1.val+T.val3.ETE.val:=T.val4.TT1*FT.val:=T1.val*F.val5.TFT.

4、val:=F.val6.F(E)F.val:=E.val7.FdigitF.val:=digit.lexval 与规则式关与规则式关与规则式关与规则式关联的每一个语联的每一个语联的每一个语联的每一个语义规则的左部义规则的左部义规则的左部义规则的左部符号符号符号符号E,T,FE,T,F等的等的等的等的属性值的计算由属性值的计算由属性值的计算由属性值的计算由右部非终结符决右部非终结符决右部非终结符决右部非终结符决定，这种属性称定，这种属性称定，这种属性称定，这种属性称为综合属性。为综合属性。为综合属性。为综合属性。第6页，本讲稿共49页第五章语法制导翻译和中间代码产生24 二月 20237LE.v

5、al=19F.val=5+T.val=4T.val=15F.val=4digit.lexval=4E.val=15T.val=3digit.lexval=5F.val=3digit.lexval=3*n求：求：3*5+4第7页，本讲稿共49页第五章语法制导翻译和中间代码产生24 二月 20238四、继承属性语法树分析中，若一个结点的某个属性之值由该结点的兄弟结点和/或父结点的属性之值来计算，则此结点的属性称为继承属性。继承属性用于“自上而下”传递信息。第8页，本讲稿共49页第五章语法制导翻译和中间代码产生24 二月 20239例2、说明语句中简单变量类型信息的属性文法。规则式语义规则1.DTL

6、L.in:=T.type2.TintT.type:=integer3.Treal T.type:=real4.LL1,idL1.in:=L.inaddtype(id.entry,L.in)5.Lidaddtype(id.entry,L.in)过程过程过程过程addtypeaddtype把每把每把每把每一个标识符一个标识符一个标识符一个标识符idid的类的类的类的类型信息型信息型信息型信息(由由由由L.inL.in继继继继承承承承)登录在符号登录在符号登录在符号登录在符号表的相关项表的相关项表的相关项表的相关项id.entryid.entry中。中。中。中。D DT LT L int L ,id

7、 int L ,id id idT有一个综合属性有一个综合属性type，其值为，其值为integer或或real。L.in由由T.type确定确定后逐步传递到下边有关结点使用。后逐步传递到下边有关结点使用。这种属性称为继承属性。这种属性称为继承属性。第9页，本讲稿共49页第五章语法制导翻译和中间代码产生24 二月 202310五、属性的初始值属性的初始值 终结符号只有综合属性，它们由词法分析器提供。非终结符号既有综合属性也可有继承属性，文法开始符号的所有继承属性作为属性计算前的初始值。第10页，本讲稿共49页第五章语法制导翻译和中间代码产生24 二月 2023115.2 语法制导翻译法语法制导

8、翻译法语法制导翻译法的基本思想：语法制导翻译法的基本思想：对文法的每一条产生式，设计语义子程序。在语法分析的过程中，当使用一条产生式推导或归约时，调用该语义子程序进行属性计算，完成预定的翻译工作。语法制导翻译法：语法制导翻译法：在语法分析的过程中，依随分析过程，根据每个产生式添加的语义动作进行翻译的方法。第11页，本讲稿共49页第五章语法制导翻译和中间代码产生24 二月 202312语义子程序语义子程序也称为翻译子程序，语义动作。它描述了有关产生式所对应的翻译工作。语义动作一方面指出了产生式所对应的符号串的意义；另一方面又按照这种意义规定了对应的属性计算加工动作。语义动作：查填各种表格计算某变

9、量的值生成某种中间代码打印错误信息等等第12页，本讲稿共49页第五章语法制导翻译和中间代码产生24 二月 202313LR分析制导的具体实现方法1、为文法产生式设计语义子程序。2、为文法构造一张无冲突的LR分析表。3、修改总控程序，归约时调用语义子程序。4、扩充LR分析栈，用来存放各文法符号对应的语义信息。例如：(1).EE1+E2E.val=E1.val+E2.val(2).EE1*E2E.val=E1.val*E2.val(3).E(E1)E.val=E1.val(4).EdigitE.val=lex.digit第13页，本讲稿共49页第五章语法制导翻译和中间代码产生24 二月 20231

10、4#第14页，本讲稿共49页第五章语法制导翻译和中间代码产生24 二月 202315扩充的LR分析栈：S0#-状态栈状态栈文法符号栈文法符号栈语义值栈语义值栈E.val=7E.val=1 +E.val=6 1 E.val=2 *E.val=3 2 3(1).EE(1).EE1 1+E+E2 2E.val=EE.val=E1 1.val+E.val+E2 2.val.val(2).EE(2).EE1 1*E*E2 2E.val=EE.val=E1 1.val*E.val*E2 2.val.val(3).E(E(3).E(E1 1)E.val=EE.val=E1 1.val.val(4).Edig

11、it(4).EdigitE.val=lex.digitE.val=lex.digit第15页，本讲稿共49页第五章语法制导翻译和中间代码产生24 二月 202316步骤步骤步骤步骤状态栈状态栈状态栈状态栈语义栈语义栈语义栈语义栈符号栈符号栈符号栈符号栈输入符号输入符号输入符号输入符号动作动作动作动作1 10 0-#1+2*3#1+2*3#S S3 32 20303-#1#1+2*3#+2*3#r r4 43 30101-1-1#E#E+2*3#+2*3#S S4 44 4014014-1-1-#E+#E+2*3#2*3#S S3 35 501430143-1-1-#E+2#E+2*3#3#R

12、R4 46 601470147-1-2-1-2#E+E#E+E*3#3#S S5 57 70147501475-1-2-1-2#E+E*#E+E*3#3#S S3 38 8014753014753-1-2-1-2-#E+E*3#E+E*3#R R4 49 9014758014758-1-2-3-1-2-3#E+E*E#E+E*E#R R2 2101001470147-1-6-1-6#E+E#E+E#R R1 111110101-7-7#E#E#accacc第16页，本讲稿共49页第五章语法制导翻译和中间代码产生24 二月 2023175.3 中间语言常用的中间语言有常用的中间语言有:一、逆波兰

13、式二、三元式与间接三元式三、树形表示法四、四元式第17页，本讲稿共49页第五章语法制导翻译和中间代码产生24 二月 202318一、逆波兰式1、逆波兰式（后缀式）：每一运算符都置于其运算对象之后。（无括号表达式）中缀表示中缀表示后缀表示后缀表示A*BAB*A+B*CABC*+(A+B)*(C+D)AB+CD+*(a=0&b3)|(e&x!=y)a0=b3&exy!=&|第18页，本讲稿共49页第五章语法制导翻译和中间代码产生24 二月 2023192 2、LRLR分析制导生成逆波兰式分析制导生成逆波兰式文法：0 EE空1EE(1)+E(2)print+2EE(1)*E(2)print*3E(E

14、(1)空4Eiprint i步骤步骤状态栈状态栈符号栈符号栈输入符号输入符号输出区输出区10#a+b*c#203#a+b*c#301#E+b*c#a4014#E+b*c#a50143#E+b*c#a60147#E+E*c#ab701475#E+E*c#ab8014753#E+E*c#ab9014758#E+E*E#abc100147#E+E#abc*1101#E#abc*+第19页，本讲稿共49页第五章语法制导翻译和中间代码产生24 二月 202320二、三元式与间接三元式一般形式一般形式：（op，AG1，AG2）例如：a:=-b*(c+d)三元式为：（，b，）（+，c，d ）（*，）（:=，

15、a）第20页，本讲稿共49页第五章语法制导翻译和中间代码产生24 二月 202321间接三元式例如：语句X:=(A+B)*CY:=D(A+B)间接代码opAG1AG2+AB*C:=XD:=Y第21页，本讲稿共49页第五章语法制导翻译和中间代码产生24 二月 202322三、树形表示法抽象语法树：抽象语法树：在语法树中去掉那些对翻译不必要的信息，从而获得更有效的源程序中间表示。这种变换后的语法树称为抽象语法树。+*4353*5+4 的抽象语法树第22页，本讲稿共49页第五章语法制导翻译和中间代码产生24 二月 202323 树形表示 A*B+C*D+C*A*BD 末端结点表示一个运算对象,每一个

16、内结点表示一个一元或二元运算符。树形表示是三元式的翻版(3)+(1)*(2)*CABD第23页，本讲稿共49页第五章语法制导翻译和中间代码产生24 二月 202324四、四元式一般形式一般形式：(op，AG1，AG2，result)直观形式：直观形式：result:=AG1 op AG2例如：求x:=a+b*c的四元式。(*，b，c，T1 )直观式：T1:=b*c(+，a，T1，T2)T2:=a+T1(:=，T2，x )x:=T2第24页，本讲稿共49页第五章语法制导翻译和中间代码产生24 二月 202325 采用自下而上的语法制导翻译法语义 动作的设计（1）搞清楚源结构和目标结构（2）自下而

17、上的语法制导翻译特点：栈顶形成句柄，归约时执行相应语义 动作（3）给出从源结构到目标结构的变换 方法5.8 自底向上语法制导翻译第25页，本讲稿共49页第五章语法制导翻译和中间代码产生24 二月 202326例.设文法及其相应的语义动作如下:Sa print“2”SbTc print“1”TR print“3”RR/S print“4”RS print“5”采用自下而上语法制导翻译,给出输入串bR/bTc/bSc/ac的翻译结果 第26页，本讲稿共49页第五章语法制导翻译和中间代码产生24 二月 202327分析:首先对输入串 bR/bTc/bSc/ac画出语法树:ScTbRS/R/RS/Rc

18、TbaScTbRS再考虑归约时执行相应语义动作第27页，本讲稿共49页第五章语法制导翻译和中间代码产生24 二月 202328ScTbRS/R/RS/RcTbaScTbRS SbTc print“1”Sa print“2”TR print“3”RR/S print“4”RS print“5”14翻译结果为:53142431第28页，本讲稿共49页第五章语法制导翻译和中间代码产生24 二月 202329一、简单算术表达式和赋值语句的翻译一、简单算术表达式和赋值语句的翻译定义几个过程和函数：lookup(id.name)：检查id.name是否出现在符号表中，如果在，则返回其指针；否则，返回 NU

19、LL 表示没有找到。emit（result:=AG1 op AG2）：产生一个四元式，并填入四元式表中。newtemp()：该函数返回一个新的临时变量。第29页，本讲稿共49页第五章语法制导翻译和中间代码产生24 二月 202330文法：文法：P2161.S i=E p Lookup(i.name);if (p=NULL)error();else emit(pE.place 2.E E(1)E(2)E.place newtemp();emit(E.placeE(1).placeE(2).place)3.E E(1)*E(2)E.place newtemp();emit(E.placeE(1).

20、place*E(2).place)4.E（E(1)）E.place E(1).place；5.E i p Lookup(i.name);if (p!=NULL)E.place p;else error();第30页，本讲稿共49页第五章语法制导翻译和中间代码产生24 二月 202331算术表达式a+b*c翻译到三地址语句的过程：030$a01$E014$E+0143$E+baaa状态栈符号栈语义栈输入串a+b*c$+b*c$+b*c$b*c$*c$第31页，本讲稿共49页第五章语法制导翻译和中间代码产生24 二月 202332*c$c$t1=b*c t2=a+t1 状态栈符号栈语义栈输入串01

21、4750147$E+E$E+E*014753$E+E*c014758$E+E*E0147$E+E01$Eab abcat1ababt2acc第32页，本讲稿共49页第五章语法制导翻译和中间代码产生24 二月 202333二、布尔表达式的翻译1、EE E2、EE E3、E E4、E(E)5、Eid rop id6、Eid第33页，本讲稿共49页第五章语法制导翻译和中间代码产生24 二月 2023341、类似算术表达式的翻译方法（求每个因子，再求表达式的值）例如：布尔表达式：a b c三地址序列：T1:=cT2:=b T1T3:=a T2第34页，本讲稿共49页第五章语法制导翻译和中间代码产生24

22、 二月 2023351.E E(1)E(2)E.place newtemp()；emit(E.placeE(1).placeE(2).place)2.E E(1)E(2)E.place newtemp()；emit(E.placeE(1).placeE(2).place)3.E E(1)E.place newtemp()；emit(E.place E(1).place4.E(E(1)E.place E(1).place；5.E i(1)rop i(2)E.place newtemp()；emit(if i(1).place rop.op i(2).place goto next+3);emit

23、(E.place 0);emit(goto next+2);emit(E.place 1);6.E i E.place i.place；第35页，本讲稿共49页第五章语法制导翻译和中间代码产生24 二月 202336E EE E E Ea b E a b E E E cd ef cd ef第36页，本讲稿共49页第五章语法制导翻译和中间代码产生24 二月 2023372、根据布尔表达式的特殊性采取某种优化措施A Bif A then trun else BA Bif A then B else false A if A then false else true对非终结符E赋予两个出口真出口：布

24、尔表达式为真时，需转移的四元式地址。假出口：布尔表达式为假时，需转移的四元式地址。第37页，本讲稿共49页第五章语法制导翻译和中间代码产生24 二月 202338设置两个语义变量：E.ture:用来记录表达式E对应的四元式需回填真出口的四元式的地址所构成的链。E.false:用来记录表达式E对应的四元式需回填假出口的四元式的地址所构成的链。定义三个函数：第38页，本讲稿共49页第五章语法制导翻译和中间代码产生24 二月 202339链接函数链接函数merge(P1,P2)：把以P1和P2为链首的两条链合并为一，返回合并后的链首（当P2=0时，返回P1;当P20时，返回P2）。int merge

25、(int P1,int P2)int P;if(!P2)return P1;else P=P2;while(P.result 0)P=P.result;P.result=P1;return P2;第39页，本讲稿共49页第五章语法制导翻译和中间代码产生24 二月 202340回填函数回填函数回填函数回填函数backpatch(p,t)backpatch(p,t)：把p所链接的每个四元式的第四分量都回填为t。void BP(int p,int t)int q=p;while(q)int q1=q.result;q.result=t;q=q1;return;建链函数建链函数建链函数建链函数make

26、list(i)makelist(i)：创建一个仅含i的新链表。第40页，本讲稿共49页第五章语法制导翻译和中间代码产生24 二月 202341定义三种四元式：(jnz,a,-,p)if a goto p(当a为真时转向第p四元式）(jrop,x,y,p)if x rop y goto p(j,-,-,p)goto p (无条件转向第p四元式)四元式表的指针nextquad（nextq）：每执行一次emit后，nextq自动加1。E.code：为及时回填转移地址,使用语义变量 E.code 记录表达式E的第一个四元式语句序号。第41页，本讲稿共49页第五章语法制导翻译和中间代码产生24 二月 2

27、023421.E i E.tr=next;E.fa=next+1;E.code=next;emit(if i.place goto-);emit(goto _);2.E i(1)rop i(2)E.tr=next;E.code=next;E.fa=next+1;emit(if i(1).place rop.op i(2).place goto _);emit(goto _);3.E(E(1)E.code=E(1).code;E.tr=E(1).tr;E.fa=E(1).fa;4.E E(1)E.tr=E(1).fa;E.fa=E(1).tr;5.E E(1)E(2)bp(E(1).fa,E(2

28、).code)；E.code=E(1).code;E.tr=merg(E(1).tr,E(2).tr);E.fa=E(2).fa;6.E E(1)E(2)bp(E(1).tr,E(2).code)；E.code=E(1).code;E.tr=E(2).tr;E.fa=merg(E(1).fa,E(2).fa);第42页，本讲稿共49页第五章语法制导翻译和中间代码产生24 二月 202343例如布尔表达式 a bc d 的翻译过程如下:E(1)c d 100 if a b goto 0101 goto 0 E(1).tr=100;E(1).fa=101;E(1).code=100;E(1)E(2

29、)102 if c d goto 0103 goto 0 E(2).tr=102;E(2).fa=103;E(2).code=102;第43页，本讲稿共49页第五章语法制导翻译和中间代码产生24 二月 202344 E bp(E(1).fa,E(2).code)=bp(101,102);E.fa=E(2).fa=103;E.tr=merg(E(1).tr,E(2).tr)=merg(100,102)=102;E.code=E(1).code=100100 if a b goto 0101 goto 0102 if c d goto 100103 goto 0E(1)E(2)归约为E第44页，本

30、讲稿共49页第五章语法制导翻译和中间代码产生24 二月 202345102 if c d goto 100103 goto 0100 if a b goto 0101 goto 102布尔表达式 a bc d E.tr=102E.fa=103第45页，本讲稿共49页第五章语法制导翻译和中间代码产生24 二月 202346三、控制语句的翻译1.Sif E then M S N else M S2.N3.M4.Sif E then M S5.Swhile M E do M S6.Sbegin L end7.SA8.LL;MS9.LS第46页，本讲稿共49页第五章语法制导翻译和中间代码产生24 二月 202347第47页，本讲稿共49页第五章语法制导翻译和中间代码产生24 二月 202348第48页，本讲稿共49页第五章语法制导翻译和中间代码产生24 二月 202349104第49页，本讲稿共49页