《属性文法和语法制导翻译第八周.ppt》由会员分享，可在线阅读，更多相关《属性文法和语法制导翻译第八周.ppt（23页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、属性文法和语法制导翻译第八周现在学习的是第1页，共23页程序语言语义的形式化描述形式语义学n1962年美国斯坦福大学麦克阿瑟（年美国斯坦福大学麦克阿瑟（Mcarthur）教授在）教授在国际信息加工联合会年会上作了著名的报告国际信息加工联合会年会上作了著名的报告“通往计通往计算机的数学科学算机的数学科学”，系统地论述了程序设计语言语义，系统地论述了程序设计语言语义形式化的重要性，以及和程序正确性、语言的正确形式化的重要性，以及和程序正确性、语言的正确实施等的关系，并提出在形式语言研究中使用抽象实施等的关系，并提出在形式语言研究中使用抽象语法和状态向量等基本方法语法和状态向量等基本方法形式语义学形
2、式语义学。现在学习的是第2页，共23页形式语义学分类n根据形式化的侧重面和所使用的数学工具的不同，根据形式化的侧重面和所使用的数学工具的不同，形式语义学可分成：形式语义学可分成：操作语义学操作语义学着重模拟数据加工过程中计算机系统的操作。着重模拟数据加工过程中计算机系统的操作。指称语义学指称语义学主要描述数据加工的结果而不是加工过程主要描述数据加工的结果而不是加工过程的细节。的细节。公理语义学公理语义学用公理化的方法描述程序对数据的加工。用公理化的方法描述程序对数据的加工。代数语义学代数语义学把程序设计语言看作是刻划数据和加工数把程序设计语言看作是刻划数据和加工数据的一种抽象数据类型，使用研究
3、抽象数据类型的代数方据的一种抽象数据类型，使用研究抽象数据类型的代数方法，来描述程序设计语言的形式语义。法，来描述程序设计语言的形式语义。现在学习的是第3页，共23页语义分析方法n丹麦的科学家曾经运用指称语义学理论成功地实现丹麦的科学家曾经运用指称语义学理论成功地实现了了Ada语言的编译系统语言的编译系统。n形式语义学方法缺点：符号系统比较复杂，其描述形式语义学方法缺点：符号系统比较复杂，其描述文本不易读，不能借助这些形式系统自动完成语义文本不易读，不能借助这些形式系统自动完成语义处理任务。处理任务。n目前实际应用中比较流行的语义描述和语义处理方目前实际应用中比较流行的语义描述和语义处理方法是
4、法是属性文法属性文法和和语法制导翻译语法制导翻译的方法的方法现在学习的是第4页，共23页内容线索n属性文法属性文法n基于属性文法的处理方法基于属性文法的处理方法 n语法制导翻译语法制导翻译 现在学习的是第5页，共23页属性文法nKnuth在在1968年提出年提出n在上下文无关文法的基础上，在描述语义动作时，为每个文法在上下文无关文法的基础上，在描述语义动作时，为每个文法符号（终结符和非终结符）配备若干相关的符号（终结符和非终结符）配备若干相关的“值值”，如，如“类类型型”，“地址地址”等，称为等，称为属性属性。n对文法的每个产生式配备一组属性计算规则称为对文法的每个产生式配备一组属性计算规则称
5、为语义规语义规则则，它的描述形式为，它的描述形式为b:=f(c1,c2,ck)，其中，其中b,c1,c2ck为为文法符号的属性，文法符号的属性，f是一个函数。是一个函数。n每个文法符号联系于一组属性，且对每个产生式都给出每个文法符号联系于一组属性，且对每个产生式都给出其语义规则的文法称为其语义规则的文法称为属性文法属性文法。现在学习的是第6页，共23页属性和语义规则n属性代表与文法符号相关信息，如类型、值、代码序列、符号表内容等；属性代表与文法符号相关信息，如类型、值、代码序列、符号表内容等；n属性可以进行计算和传递；属性可以进行计算和传递；n在一个属性文法中，对应于每个产生式在一个属性文法中
6、，对应于每个产生式A 都有一组与之相关联的语义规则，都有一组与之相关联的语义规则，每条规则的形式为：每条规则的形式为：b:=f(c1,c2,ck)这里，这里，f是一个函数是一个函数 （1）b是是A的一个属性，并且的一个属性，并且c1,c2,ck是产生式右边文法符号的属性，则是产生式右边文法符号的属性，则b是是A的的综合属性综合属性；（2）b是产生式右边某个文法符号是产生式右边某个文法符号X的一个属性，并且的一个属性，并且c1,c2,ck 是是A或产生式或产生式右边任何文法符号的属性，右边任何文法符号的属性，b是是X的的继承属性继承属性；属性属性b依赖于属性依赖于属性c1,c2,ck。现在学习的
7、是第7页，共23页 产产 生生 式式 LEn EE1+T ETTT1*FTFF(E)Fdigit语 义 规 则print(E.val)E.val:=E1.val+T.val E.val:=T.val T.val:=T1.val*F.val T.val:=F.val F.val:=E.val F.val:=digit.lexval简单台式计算器的属性文法现在学习的是第8页，共23页记号表示n对于某个文法符号对于某个文法符号XVT VN，用，用 X.type（X的类型），的类型），X.cat（X的种的种别），别），X.val（X的值或地址）等表示它的值或地址）等表示它的的属性属性。n用用下标下标（
8、上角标）区分同一产生式中（上角标）区分同一产生式中相相同符号的多次出现同符号的多次出现。现在学习的是第9页，共23页综合属性n在语法树中，一个结点的在语法树中，一个结点的综合属性综合属性的值由的值由其其子结点子结点的属性值确定。的属性值确定。n使用自底向上的方法在每一个结点处使用使用自底向上的方法在每一个结点处使用语义规则计算综合属性的值语义规则计算综合属性的值n仅仅使用综合属性的属性文法称仅仅使用综合属性的属性文法称S属性文属性文法法现在学习的是第10页，共23页3*5+4n的带注释的语法树的带注释的语法树 digit.lexval=3F.val=3T.val=3*digit.lexval=
9、5F.val=5T.val=15E.val=15+digit.lexval=4F.val=4T.val=4E.val=19nL 产产 生生 式式 语语 义义 规规 则则LEn print(E.val)EE1+T E.val:=E1.val+T.val ET E.val:=T.val TT1*F T.val:=T1.val*F.val TF T.val:=F.val F(E)F.val:=E.val Fdigit F.val:=digit.lexval现在学习的是第11页，共23页继承属性n在语法树中，一个结点的在语法树中，一个结点的继承属性继承属性由此结由此结点的点的父结点和父结点和/或兄弟结
10、点或兄弟结点的某些属性确定的某些属性确定n用继承属性来表示程序设计语言结构中的用继承属性来表示程序设计语言结构中的上下文依赖关系很方便上下文依赖关系很方便现在学习的是第12页，共23页产产 生生 式式 语语 义义 规规 则则 DTLL.in:=T.type TintT.type:=integer TrealT.type:=real LL1,idL1.in:=L.in addtype(id.entry,L.in)Lid addtype(id.entry,L.in)带继承属性L.in的属性文法现在学习的是第13页，共23页句子real id1，id2，id3的带注释的语法树 id1L,id2L,i
11、d3LrealTDT.type=realL.in=realL.in=realL.in=real产产 生生 式式 语语 义义 规规 则则 DTL L.in:=T.type Tint T.type:=integer Treal T.type:=real LL1,id L1.in:=L.in addtype(id.entry,L.in)Lid addtype(id.entry,L.in)现在学习的是第14页，共23页说明n终结符终结符只有综合属性，由词法分析器提供只有综合属性，由词法分析器提供n非终结符非终结符既可有综合属性也可有继承属性，文法开始符号的所有继承属性作为属既可有综合属性也可有继承属性
12、，文法开始符号的所有继承属性作为属性计算前的初始值性计算前的初始值n对出现在对出现在产生式右边的继承属性产生式右边的继承属性和出现在和出现在产生式左边的综合属性产生式左边的综合属性都必须提供一个计都必须提供一个计算规则。属性计算规则中只能使用相应产生式中的文法符号的属性算规则。属性计算规则中只能使用相应产生式中的文法符号的属性n出现在出现在产生式左边的继承属性产生式左边的继承属性和出现在和出现在产生式右边的综合属性产生式右边的综合属性不由所给的产生不由所给的产生式的属性计算规则进行计算，它们由其它产生式的属性规则计算或者由属式的属性计算规则进行计算，它们由其它产生式的属性规则计算或者由属性计算
13、器的参数提供性计算器的参数提供n语义规则所描述的工作可以包括属性计算、静态语义检查、符号表操作、代码生成等等。语义规则所描述的工作可以包括属性计算、静态语义检查、符号表操作、代码生成等等。现在学习的是第15页，共23页例例.考虑非终结符考虑非终结符A，B和和C，其中，其中，A有一个继承属性有一个继承属性a和一个综合属性和一个综合属性b;B有综合属性有综合属性c;C有继承属性有继承属性d。产生式产生式ABC可能有语义规则可能有语义规则 C.d:=B.c+1 A.b:=A.a+B.c而属性而属性A.a和和B.c在其它地方计算在其它地方计算 现在学习的是第16页，共23页内容线索属性文法属性文法基于
14、属性文法的处理方法基于属性文法的处理方法 语法制导翻译语法制导翻译 现在学习的是第17页，共23页概述n由源程序的语法结构所驱动的处理办法就由源程序的语法结构所驱动的处理办法就是是语法制导翻译法语法制导翻译法依赖图依赖图树遍历树遍历一遍扫描一遍扫描输入串输入串语法树语法树依赖图依赖图语义规则计算次序语义规则计算次序n基于属性文法的处理过程现在学习的是第18页，共23页依赖图n在一棵语法树中的结点的继承属性和综合属性之间的相互依赖关系可在一棵语法树中的结点的继承属性和综合属性之间的相互依赖关系可以由称作以由称作依赖图依赖图的一个有向图来描述的一个有向图来描述n为每一个包含过程调用的语义规则引入一
15、个为每一个包含过程调用的语义规则引入一个虚综合属性虚综合属性b，这样把每，这样把每一个语义规则都写成一个语义规则都写成b:=f(c1,c2,ck)的形式的形式n依赖图中为每一个属性设置一个结点，如果属性依赖图中为每一个属性设置一个结点，如果属性b依赖于属性依赖于属性c，则从属性则从属性c的结点有一条有向边连到属性的结点有一条有向边连到属性b的结点。的结点。现在学习的是第19页，共23页依赖图构造算法for 语法树中每一结点语法树中每一结点n do for 结点结点n的文法符号的每一个属性的文法符号的每一个属性a do 为为a在依赖图中建立一个结点；在依赖图中建立一个结点；for 语法树中每一个
16、结点语法树中每一个结点n do for 结点结点n所用产生式对应的每一个语义规则所用产生式对应的每一个语义规则b:=f(c1,c2,ck)dofor i:=1 to k do 从从ci结点到结点到b结点构造一条有向边；结点构造一条有向边；现在学习的是第20页，共23页 EE1E2 E.val:=E1.val+E2.val E1+E2Evalvalval现在学习的是第21页，共23页句子句子real id1，id2，id3的带的带注释的语法树的依赖图注释的语法树的依赖图id1L,id2L,id3LrealTD4type5in6-addtype(id.entry,L.in)7in8 addtype
17、9in10 addtype1entry2entry3entry产产 生生 式式 语语 义义 规规 则则 DTL L.in:=T.type Tint T.type:=integer Treal T.type:=real LL1,id L1.in:=L.in addtype(id.entry,L.in)Lid addtype(id.entry,L.in)现在学习的是第22页，共23页说明n一条求值规则只有在其各变元值均已求得一条求值规则只有在其各变元值均已求得的情况下才可以使用；的情况下才可以使用；n如果一属性文法不存在属性之间的循环依如果一属性文法不存在属性之间的循环依赖关系，那么称该文法为良定义的赖关系，那么称该文法为良定义的 现在学习的是第23页，共23页