语义分析和语法制导翻译.ppt-得力文库

资源描述

《语义分析和语法制导翻译.ppt》由会员分享，可在线阅读，更多相关《语义分析和语法制导翻译.ppt（49页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、语义分析和语法制导翻译现在学习的是第1页，共49页第六章第六章语义分析和语法语义分析和语法制导翻译制导翻译n n语义分析的任务：检查语义错误语义分析的任务：检查语义错误uu类型检查：类型检查：运算数类型运算数类型uu一致性检查：一致性检查：名字声明与引用名字声明与引用uu控制流检查：控制流检查：转移目标转移目标uu名字检查：名字检查：作用域作用域n n翻译的任务：建立等价的目标程序翻译的任务：建立等价的目标程序uu生成中间语言的指令序列生成中间语言的指令序列uu名字绑定：名字绑定：变量名、过程名变量名、过程名uu建立运行环境建立运行环境现在学习的是第2页，共49页6.1 6.1 属性文法属性

2、文法语义分析与语法制导翻译的描述方法语义分析与语法制导翻译的描述方法n n属性文法的定义：属性文法的定义：n n（，）（，）uu 是上下文无关文法是上下文无关文法uu 属性的有穷集属性的有穷集uu 关于属性的断言和谓词关于属性的断言和谓词现在学习的是第3页，共49页用法用法n n针对语义，为文法符号设置属性针对语义，为文法符号设置属性uu终结符使用单词的属性终结符使用单词的属性n n为每个产生式设置语义规则为每个产生式设置语义规则uu通过描述各属性的关系通过描述各属性的关系uu将语义分析和翻译步骤定义为产生式的断言将语义分析和翻译步骤定义为产生式的断言和谓词和谓词现在学习的是第4页，共49页例

3、例6-1:6-1:计算器的算法设计计算器的算法设计n n需求：算术表达式的求值需求：算术表达式的求值n n设计：设计：uu编制算术表达式的文法编制算术表达式的文法uu引入属性表示语义信息引入属性表示语义信息FF将值将值将值将值 val val val val 作为表达式作为表达式作为表达式作为表达式 E E E E、项、项、项、项 T T T T 和因子和因子和因子和因子 F F F F 的属的属的属的属性性性性uu用语义规则描述表达式的求值用语义规则描述表达式的求值现在学习的是第5页，共49页属性文法（语法制导定义）属性文法（语法制导定义）uuattr attr attr attr 是单词是

4、单词是单词是单词 digit digit digit digit 的属性的属性的属性的属性uuprint(val)print(val)print(val)print(val)是输出函数是输出函数是输出函数是输出函数产生式产生式语义规则语义规则L EL Eprint(E.val)print(E.val)E EE E1 1+T+TE.val:=EE.val:=E1 1.val+T.val.val+T.valE TE TE.val:=T.valE.val:=T.valT TT T1 1*F*FT.val:=TT.val:=T1 1.val*F.val.val*F.valT FT FT.val:=F.

5、valT.val:=F.valF (E)F (E)F.val:=E.valF.val:=E.valF digitF digitF.val:=digit.attrF.val:=digit.attr现在学习的是第6页，共49页例例6-26-2：说明语句的类型信息统计说明语句的类型信息统计n n说明语句的作用说明语句的作用uu支持语义分析，提供语义检查的依据支持语义分析，提供语义检查的依据n n设计设计uu编写说明语句的文法编写说明语句的文法uu将类型信息作为类型描述将类型信息作为类型描述 T T 的属性的属性 type type 和变量表和变量表 L L 的属性的属性 inin。n n目的目的uu

6、分析说明语句分析说明语句 D D，获取变量的类型信息，获取变量的类型信息现在学习的是第7页，共49页描述类型信息提取的属性文法描述类型信息提取的属性文法uuentry entry 单词单词 id id 的的属性属性(符号表入口符号表入口)uuaddtype addtype 在符号表中为变量填加类型信息在符号表中为变量填加类型信息产生式产生式语义规则语义规则D T LD T LL.in:=T.typeL.in:=T.typeT intT intT.type:=T.type:=integerintegerT realT realT.type:=T.type:=realrealL LL L1 1,i

7、d,idL L1 1.in:=L.in.in:=L.inaddtype(id.entry,L.in)addtype(id.entry,L.in)L idL idaddtype(id.entry,L.in)addtype(id.entry,L.in)现在学习的是第8页，共49页属性文法的作用属性文法的作用n n抽象描述语义处理的要求抽象描述语义处理的要求uu语义信息及其计算关系语义信息及其计算关系uu适用于各种语义处理（分析、翻译、计算）适用于各种语义处理（分析、翻译、计算）n n语义处理的步骤语义处理的步骤uu属性求值计算、断言检查属性求值计算、断言检查n n语义处理算法的描述方法语义处理算法

8、的描述方法uu一种通用的语义处理算法设计方法一种通用的语义处理算法设计方法现在学习的是第9页，共49页属性分类：属性分类：n n综合属性综合属性uu从其子结点的属性值计算出来的；从其子结点的属性值计算出来的；uu如：如：E.valE.val、T.typeT.typen继承属性继承属性uu从其兄弟结点和父结点的属性值计算出来的从其兄弟结点和父结点的属性值计算出来的uu如：如：L.inL.inn n固有属性（单词属性）固有属性（单词属性）现在学习的是第10页，共49页属性的计算属性的计算n n构造语法分析树，填加响应的语义规则构造语法分析树，填加响应的语义规则n n综合属性综合属性uu自底向上自底

9、向上按照语义规则来计算各结点的综按照语义规则来计算各结点的综合属性值合属性值n n继承属性继承属性uu需要探讨计算次序需要探讨计算次序现在学习的是第11页，共49页例例6-36-3：3*5+4 3*5+4 的的语法树与属性计算语法树与属性计算现在学习的是第12页，共49页例例6-46-4：real id1,id2,id3 real id1,id2,id3 的的分析树和属性计算分析树和属性计算addtypeaddtypeaddtypeaddtypeaddtypeaddtype现在学习的是第13页，共49页n n仅包括综合属性仅包括综合属性uu对于所有对于所有 1 1 2 2 n n，uu的属性计

10、算仅用的属性计算仅用1 1n n 的属性的属性n n如：算术表达式求值的属性文法如：算术表达式求值的属性文法-属性定义：属性定义：现在学习的是第14页，共49页-属性定义：属性定义：n n其属性可用深度优先的顺序从左至其属性可用深度优先的顺序从左至右计算右计算uu对于所有对于所有 1 1 2 2 n nuui i 属性计算仅使用属性计算仅使用 1 1 2 2 i-i-1 1 的属性的属性n n如：说明语句的属性文法如：说明语句的属性文法现在学习的是第15页，共49页翻译模式翻译模式（Translation SchemesTranslation Schemes）n n特征特征uu规定在语法分析中

11、使用语义规则进行计算规定在语法分析中使用语义规则进行计算的次序的次序uu保证当动作使用某属性时，该属性必须是保证当动作使用某属性时，该属性必须是可用的可用的n n实现方法实现方法uu将语义动作插入到产生式中的某个位置将语义动作插入到产生式中的某个位置现在学习的是第16页，共49页例例6-56-5：建立说明语句的翻译方案建立说明语句的翻译方案产生式产生式语义规则语义规则D T LD T LL.in:=T.typeL.in:=T.typeT intT intT.type:=T.type:=integerintegerT realT realT.type:=T.type:=realrealL LL

12、L1 1,id,idL L1 1.in:=L.in.in:=L.inaddtype(id.entry,L.in)addtype(id.entry,L.in)L idL idaddtype(id.entry,L.in)addtype(id.entry,L.in)n n将语义动作中的计算向前移，使继承属性的计算出现将语义动作中的计算向前移，使继承属性的计算出现将语义动作中的计算向前移，使继承属性的计算出现将语义动作中的计算向前移，使继承属性的计算出现在其文法符号之前在其文法符号之前在其文法符号之前在其文法符号之前现在学习的是第17页，共49页翻译模式的设计翻译模式的设计D T L.in:=T.ty

13、pe LD T L.in:=T.type LD T L.in:=T.type LD T L.in:=T.type LT int T.type:=integer T int T.type:=integer T int T.type:=integer T int T.type:=integer T real T.type:=real T real T.type:=real L LL LL LL L1 1 1 1.in:=L.in.in:=L.in L L1 1 1 1,id addtype(id.entry,L.in),id addtype(id.entry,L.in)L id addtype(i

14、d.entry,L.in)L id addtype(id.entry,L.in)L id addtype(id.entry,L.in)L id addtype(id.entry,L.in)现在学习的是第18页，共49页习题习题1.1.下列文法是一个下列文法是一个二进制数的文法。试根据二进制数的文法。试根据该文法，编写一个语法制导定义，描述由该文法，编写一个语法制导定义，描述由 S S 生成的生成的二进制数的数值计算。二进制数的数值计算。S-L.LS-L.L L-L B|B L-L B|B B-0|1 B-0|12.2.参照下列表达式文法编写语法制导定义，参照下列表达式文法编写语法制导定义，描述

15、表达式的类型计算。要求在不同精度的描述表达式的类型计算。要求在不同精度的数的计算中，结果取精度高的类型。数的计算中，结果取精度高的类型。E-E+T|TE-E+T|T T-n.n|n T-n.n|n现在学习的是第19页，共49页6.2 6.2 中间语言中间语言n用于编译程序用于编译程序uu源程序经过语义分析被译成中间代码序列源程序经过语义分析被译成中间代码序列uu（中间语言的语句）（中间语言的语句）n n用中间语言过渡的好处：用中间语言过渡的好处：uu便于编译系统的实现、移植、代码优化便于编译系统的实现、移植、代码优化现在学习的是第20页，共49页常用的中间语言常用的中间语言n n三地址代码（四

16、元式）三地址代码（四元式）n n语法结构树（三元式）语法结构树（三元式）n n后缀式后缀式特点特点n n形式简单、语义明确、便于翻译形式简单、语义明确、便于翻译n n独立于目标语言独立于目标语言现在学习的是第21页，共49页语法制导编译语法制导编译描述方法描述方法n n利用属性文法描述如何将各种语句和表利用属性文法描述如何将各种语句和表达式翻译成中间代码达式翻译成中间代码工作方式工作方式n n分析与综合并行进行分析与综合并行进行uu每识别出一个语言结构时，每识别出一个语言结构时，uu完成相应的语义检查与中间代码生成完成相应的语义检查与中间代码生成现在学习的是第22页，共49页语法结构树语法结构

17、树n n例例 6-5：表达式：表达式 (A-12)*B+6 的的语法结构树语法结构树现在学习的是第23页，共49页将赋值语句变换为语法结构树将赋值语句变换为语法结构树n设置属性：设置属性：uuE.p E.p 是语法结构树指针是语法结构树指针uuid.entry id.entry 是名字的表项入口是名字的表项入口uunum.val num.val 是数值是数值n树构造函数树构造函数uumknode 建中间结点建中间结点uumkleaf 建叶结点建叶结点现在学习的是第24页，共49页生成语法树的属性文法生成语法树的属性文法现在学习的是第25页，共49页例例6-66-6：a:=b*(-c)+b*a:

18、=b*(-c)+b*(-34)(-34)的语法结构树的语法结构树:=*-0+*-0idbnum 34idbidcidarootroot现在学习的是第26页，共49页语法结构树的语法结构树的三元式表示三元式表示地址地址地址地址算符算符算符算符操作数操作数操作数操作数操作数操作数操作数操作数0 0 0 01 1 1 12 2 2 23 3 3 34 4 4 45 5 5 56 6 6 67 7 7 78 8 8 89 9 9 910101010现在学习的是第27页，共49页三地址代码三地址代码一般形式一般形式 x:=y op zx:=y op zuu其中其中 x,y,z x,y,z 为变量

19、名、常数或编译产生为变量名、常数或编译产生的临时变量的临时变量uu四元式（四元式（op,x,y,zop,x,y,z）种类：种类：种类：种类：x:=y op z x:=y op z x:=y op z x:=y op z 双目运算双目运算双目运算双目运算 x:=op y x:=op y x:=op y x:=op y 单目运算单目运算 x:=y x:=y x:=y x:=y 赋值赋值 if x relop y goto l if x relop y goto l if x relop y goto l if x relop y goto l 条件转移条件转移现在学习的是第28页，共49页其他三地

20、址代码其他三地址代码goto l goto l goto l goto l 无条件转移无条件转移param x param x param x param x 实在参数实在参数实在参数实在参数call p,n(ncall p,n(ncall p,n(ncall p,n(n是参数个数是参数个数)过程调用过程调用过程调用过程调用return x return x return x return x 过程返回过程返回过程返回过程返回x:=yix:=yi数组运算数组运算数组运算数组运算 xi:=yxi:=yxi:=yxi:=yx:=&yx:=&yx:=&yx:=&y指针运算指针运算指针运算指针运算x:

21、=*yx:=*yx:=*yx:=*y*x=y*x=y*x=y*x=y 现在学习的是第29页，共49页6.36.3 赋值语句的翻译赋值语句的翻译翻译的需求翻译的需求n n充分了解各种语言现象的语义充分了解各种语言现象的语义uu包括：控制结构、数据结构、单词包括：控制结构、数据结构、单词uu充分了解它们的实现方法充分了解它们的实现方法n n目标语言的语义目标语言的语义uu了解中间代码的语义了解中间代码的语义uu了解运行环境了解运行环境现在学习的是第30页，共49页实现赋值语句的翻译实现赋值语句的翻译语义过程语义过程uu产生一条中间代码产生一条中间代码 gen(code)gen(code)uu产生新

22、的临时变量产生新的临时变量 newtempnewtemp属性设置属性设置uu中间代码序列中间代码序列 codecodeuu存储位置存储位置 placeplace现在学习的是第31页，共49页赋值语句的四元式翻译赋值语句的四元式翻译S id:=E S.code:=E.code|gen(id.place:=E.place)S id:=E S.code:=E.code|gen(id.place:=E.place)E EE E1 1+E+E2 2 E.place:=newtemp;E.place:=newtemp;E.code:=E E.code:=E1 1.code|E.code|E2 2.code

24、1 E.place:=newtemp;E.place:=newtemp;E.code:=E E.code:=E1 1.code|gen(E.place:=0-E1 1.place).place)E (EE (E1)E.place:=E)E.place:=E1 1.place;E.code:=E.place;E.code:=E1 1.code.code E id E.place:=id.place;E.code:=E id E.place:=id.place;E.code:=E num E.place:=num.valE num E.place:=num.val；E.code:=E.code:=

25、现在学习的是第33页，共49页例例 6-76-7：翻译翻译 a:=-c+b*34 a:=-c+b*34 现在学习的是第34页，共49页结果：开始符号的属性结果：开始符号的属性 S.codeS.coden n1)1)找出分析树中使用的产生式规则找出分析树中使用的产生式规则n n2)2)根据产生式的语义规则，代换公式中的根据产生式的语义规则，代换公式中的各属性各属性n n3)3)反复使用反复使用 1)1)和和 2)2)改写公式，最后得改写公式，最后得到代码生成语句组成的公式到代码生成语句组成的公式uu组成语句的翻译结果（中间代码序列）组成语句的翻译结果（中间代码序列）现在学习的是第35页，共49页

26、中间代码的生成过程中间代码的生成过程S.code S.code=E.code|gen(a:=E.place)=E.code|gen(a:=E.place)/*a=id.place */=E=E1 1.code|E.code|E2 2.code.code|gen(t1:=E1 1.place+E2 2.place).place)|gen(a:=t1)/*newtemp=t1=E.place */*newtemp=t1=E.place */=E=E1111.code|gen(t2:=0-E1111.place).place)/*newtemp=t2=E/*newtemp=t2=E1 1.place

27、 */现在学习的是第36页，共49页|E2121.code|E.code|E22.code.code|gen(t3:=E21.place*E.place*E2222.place)/*newtemp=t3=E/*newtemp=t3=E2 2.place */|gen(t1:=t2+t3)|gen(a:=t1)|gen(t1:=t2+t3)|gen(a:=t1)=gen(t2:=0-c)|gen(t3:=b*34)=gen(t2:=0-c)|gen(t3:=b*34)/*c=E/*c=E1111.place */*b=E/*b=E2121.place */.place */*34=E/*34=E

28、2222.place */.place */|gen(t1:=t2+t3)|gen(a:=t1)|gen(t1:=t2+t3)|gen(a:=t1)/*=E/*=E2121.code=E.code=E22.code */.code */现在学习的是第37页，共49页表达式翻译中的其他问题表达式翻译中的其他问题n n运算类型检查运算类型检查uu利用符号表保存的名字类型利用符号表保存的名字类型n n类型自动转换类型自动转换uu填加专用指令填加专用指令n n临时变量空间的统计临时变量空间的统计uu了解需求、及时释放了解需求、及时释放现在学习的是第38页，共49页6.4 6.4 控制结构的翻译控制结构

29、的翻译n n高级语言的控制结构高级语言的控制结构uu顺序顺序 begin begin 语句语句;语句语句 end enduu条件条件 if_then_else if_thenif_then_else if_then switch case switch caseuu循环循环 while_do do_while while_do do_while for repeat_util for repeat_utiln n三地址代码的控制结构三地址代码的控制结构uugoto lgoto luuif x relop y goto lif x relop y goto l现在学习的是第39页，共49页S w

30、hile C do S1 的翻译的翻译n n属性设置属性设置属性设置属性设置布尔式布尔式布尔式布尔式 C Cuu真出口真出口真出口真出口 true true uu假出口假出口假出口假出口 falsefalse语句语句语句语句 S S uu入口入口入口入口 beginbeginuu后续段入口后续段入口后续段入口后续段入口 nextnextC.codeC.code to to to to C.true C.true C.true C.true to to to to C.false=S.nextC.false=S.nextC.false=S.nextC.false=S.nextS.beginS.b

31、eginS.beginS.begingoto S.begingoto S.begingoto S.begingoto S.beginS.nextS.nextS.nextS.nextS.codeS.codeS S S S1 1.code.code.code.codeC.trueC.trueC.trueC.true to S to S1 1.next=S.begin.next=S.begin现在学习的是第40页，共49页 S while C do S1 代码生成的语义规则代码生成的语义规则C.false:=S.next;C.true:=newlabel;S.begin:=SS.begin:=S1

33、if C then S1 else S2 的翻译的翻译C.codeC.code to to to to C.true C.true C.true C.true nto to to to C.falseC.falseC.falseC.falseS S S S1 1.code.code.code.codeC.trueC.trueC.trueC.true to S to S1 1.next=S.next.next=S.nextS S S S2 2.code.code.code.codeC.falseC.falseC.falseC.false to S to S2 2.next=S.next.next

34、=S.nextgoto S.nextgoto S.nextgoto S.nextgoto S.nextS.nextS.nextS.nextS.nextS.beginS.begin现在学习的是第42页，共49页S if C then S1 else S2 代码生成的语义规则代码生成的语义规则C.true:=newlabel;C.false:=newlabel;S1.next:=S2.next:=S.next;S.code:=C.code|gen(C.true:)|S1.code|gen(goto S.next)|gen(C.false:)|S2.code现在学习的是第43页，共49页简单布尔表达

35、式的翻译简单布尔表达式的翻译C E1 relop E2语义规则语义规则C.code:=E1.code|E2.code|gen(if E1.place relop.op E2.place gotoC.true)|gen(gotoC.false)现在学习的是第44页，共49页例例 6-86-8：翻译下列语句：翻译下列语句while a b dowhile a b do if c 5 then if c y do while x y do z:=x+1;z:=x+1;现在学习的是第45页，共49页生生成成的的三三地地址址代代码码序序列列L1:if a b goto L2L1:if a b goto

36、L2L1:if a b goto L2L1:if a b goto L2 goto Lnext goto Lnext goto Lnext goto LnextL2:if c 5 goto L3L2:if c 5 goto L3L2:if c 5 goto L3L2:if c y goto L6 if x y goto L6 if x y goto L6 if x y goto L6 goto L1 goto L1 goto L1 goto L1L6:t1:=x+1L6:t1:=x+1L6:t1:=x+1L6:t1:=x+1 z:=t1 z:=t1 z:=t1 z:=t1 goto L5 go

37、to L5 goto L5 goto L5 goto L1 goto L1 goto L1 goto L1Lnext:Lnext:Lnext:Lnext:C.codeC.codeC C1 1.code.codeS S1111.code.codeS1212.codeS S1 1.code.code现在学习的是第46页，共49页控制结构翻译中的其他问题控制结构翻译中的其他问题n n分层结构的记录分层结构的记录uu涉及变量的作用域涉及变量的作用域n n转移目标的先引用后定义转移目标的先引用后定义uu使用回填技术使用回填技术uu涉及循环语句、条件语句、转移标号涉及循环语句、条件语句、转移标号现在学习的

38、是第47页，共49页6.5 6.5 属性文法的实现属性文法的实现n n分析分析uu属性属于文法符号属性属于文法符号uu局限于产生式局限于产生式n递归子程序的改进递归子程序的改进uu为每个文法符号设置结构或对象类为每个文法符号设置结构或对象类uu以每个属性为分量以每个属性为分量uu每个函数设置一个结构（或对象类）指每个函数设置一个结构（或对象类）指针针现在学习的是第48页，共49页例例 6-9：条件语句的翻译实现：条件语句的翻译实现n nS 的结构的结构struct S_Attr char pCodeMAX;int iNext;n nC 的结构的结构struct C_Attr char pCodeMAX;int iFalse;int iTrue;现在学习的是第49页，共49页

展开阅读全文