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












