第六章 属性文法和语法制导翻译(第八周)

1、第六章 属性文法和语 法制导翻译程序语言语义的形式化描述形式语义学n1962年美国斯坦福大学麦克阿瑟（年美国斯坦福大学麦克阿瑟（Mcarthur）教）教授在国际信息加工联合会年会上作了著名的报授在国际信息加工联合会年会上作了著名的报告告“通往计算机的数学科学通往计算机的数学科学”，系统地论述了，系统地论述了程序设计语言语义形式化的重要性，以及和程序程序设计语言语义形式化的重要性，以及和程序正确性、语言的正确实施等的关系，并提出在形正确性、语言的正确实施等的关系，并提出在形式语言研究中使用抽象语法和状态向量等基本方式语言研究中使用抽象语法和状态向量等基本方法法形式语义学形式语义学 。形式语义学分

2、类n根据形式化的侧重面和所使用的数学工具的不根据形式化的侧重面和所使用的数学工具的不同，形式语义学可分成：同，形式语义学可分成：操作语义学操作语义学着重模拟数据加工过程中计算机系统着重模拟数据加工过程中计算机系统的操作。的操作。指称语义学指称语义学主要描述数据加工的结果而不是加工主要描述数据加工的结果而不是加工过程的细节。过程的细节。公理语义学公理语义学用公理化的方法描述程序对数据的加用公理化的方法描述程序对数据的加工。工。 代数语义学代数语义学把程序设计语言看作是刻划数据和加把程序设计语言看作是刻划数据和加工数据的一种抽象数据类型，使用研究抽象数据类型工数据的一种抽象数据类型，使用研究抽象数

3、据类型的代数方法，来描述程序设计语言的形式语义。的代数方法，来描述程序设计语言的形式语义。语义分析方法n丹麦的科学家曾经运用指称语义学理论成功地实丹麦的科学家曾经运用指称语义学理论成功地实现了现了Ada语言的编译系统语言的编译系统 。n形式语义学方法缺点：符号系统比较复杂，其描形式语义学方法缺点：符号系统比较复杂，其描述文本不易读，不能借助这些形式系统自动完成述文本不易读，不能借助这些形式系统自动完成语义处理任务。语义处理任务。n目前实际应用中比较流行的语义描述和语义处理目前实际应用中比较流行的语义描述和语义处理方法是方法是属性文法属性文法和和语法制导翻译语法制导翻译的方法的方法内容线索n属性

4、文法属性文法n基于属性文法的处理方法基于属性文法的处理方法 n语法制导翻译语法制导翻译 属性文法nKnuth在在1968年提出年提出n在上下文无关文法的基础上，在描述语义动作时，为在上下文无关文法的基础上，在描述语义动作时，为每个文法符号（终结符和非终结符）配备若干相关的每个文法符号（终结符和非终结符）配备若干相关的“值值”，如，如“类型类型”，“地址地址”等，称为等，称为属性属性。n对文法的每个产生式配备一组属性计算规则称为对文法的每个产生式配备一组属性计算规则称为语义语义规则规则，它的描述形式为，它的描述形式为b:=f(c1,c2,ck)，其中，其中b,c1,c2ck为文法符号的属性，为文

5、法符号的属性，f是一个函数。是一个函数。n每个文法符号联系于一组属性，且每个文法符号联系于一组属性，且对每个产生式都给对每个产生式都给出其语义规则的文法称为出其语义规则的文法称为属性文法属性文法。属性和语义规则n属性代表与文法符号相关信息，如类型、值、代码序列、符号表内容属性代表与文法符号相关信息，如类型、值、代码序列、符号表内容等等；n属性可以进行计算和传递属性可以进行计算和传递；n在一个属性文法中，对应于每个产生式在一个属性文法中，对应于每个产生式A 都有都有一组一组与之相关联的与之相关联的语义规则，每条规则的形式为：语义规则，每条规则的形式为：b:=f(c1,c2,ck)这里，这里，f是

6、一个函数是一个函数 （1）b是是A的一个属性的一个属性，并且并且c1,c2,ck是产生式右边文法符号的属是产生式右边文法符号的属性，性，则则b是是A的的综合属性综合属性； （2）b是产生式右边某个文法符号是产生式右边某个文法符号X的一个属性的一个属性，并且并且c1,c2,ck 是是A或产生式右边任何文法符号的属性或产生式右边任何文法符号的属性， b是是X的的继承属性继承属性；属性属性b依赖于属性依赖于属性c1,c2,ck。 产产 生生 式式 LEn EE1+T ETTT1*FTFF (E)Fdigit语语 义义 规规 则则print(E.val) E.val := E1.val+T.val E

7、.val :=T.val T.val :=T1.val* F.val T.val :=F.val F.val :=E.val F.val :=digit.lexval简单台式计算器的属性文法记号表示n对于某个文法符号对于某个文法符号XVT VN，用，用 X . type（X的类型），的类型），X . cat（X的种的种别），别），X .val（X的值或地址）等表示它的值或地址）等表示它的的属性属性。n用用下标下标（上角标）区分同一产生式中（上角标）区分同一产生式中相相同符号的多次出现同符号的多次出现。综合属性n在语法树中，一个结点的在语法树中，一个结点的综合属性综合属性的值由的值由其其子结点子

8、结点的属性值确定。的属性值确定。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 产产 生生 式式 语语 义义 规规 则则LEn print(E.val) EE1+T E.val := E1.v

9、al+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继承属性n在语法树中，一个结点的在语法树中，一个结点的继承属性继承属性由此结由此结点的点的父结点和父结点和/或兄弟结点或兄弟结点的某些属性确定的某些属性确定n用继承属性来表示程序设计语言结构中的用继承属性来表示程序设计语言结构中的上下文依赖关系很方便上下文依赖关系很方便产产 生生 式式 语语 义义 规规 则则 DTLL.in := T.type TintT.ty

10、pe := integer TrealT.type := real LL1, idL1.in :=L.in addtype(id.entry, L.in) Lid addtype(id.entry, L.in)带继承属性L.in的属性文法句子real id1，id2，id3的带注释的语法树 id1L,id2L,id3LrealTDT.type=realL.in=realL.in=realL.in=real产产 生生 式式 语语 义义 规规 则则 DTL L.in := T.type Tint T.type := integer Treal T.type := real LL1, id L1.i

11、n :=L.in addtype(id.entry, L.in) Lid addtype(id.entry, L.in) 说明n终结符终结符只有综合属性，由词法分析器提供只有综合属性，由词法分析器提供n非终结符非终结符既可有综合属性也可有继承属性，文法开始符号的所有继承既可有综合属性也可有继承属性，文法开始符号的所有继承属性作为属性计算前的初始值属性作为属性计算前的初始值n对出现在对出现在产生式右边的继承属性产生式右边的继承属性和出现在和出现在产生式左边的综合属性产生式左边的综合属性都必都必须提供一个计算规则。属性计算规则中只能使用相应产生式中的文法须提供一个计算规则。属性计算规则中只能使用相

12、应产生式中的文法符号的属性符号的属性n出现在出现在产生式左边的继承属性产生式左边的继承属性和出现在和出现在产生式右边的综合属性产生式右边的综合属性不由所不由所给的产生式的属性计算规则进行计算，它们由其它产生式的属性规则给的产生式的属性计算规则进行计算，它们由其它产生式的属性规则计算或者由属性计算器的参数提供计算或者由属性计算器的参数提供n语义规则所描述的工作可以包括属性计算、静态语义检查、符号表操语义规则所描述的工作可以包括属性计算、静态语义检查、符号表操作、代码生成等等。作、代码生成等等。例例. 考虑非终结符考虑非终结符A，B和和C，其中，其中， A有一个继承属性有一个继承属性a和一个综合属

13、性和一个综合属性b; B有综合属性有综合属性c; C有继承属性有继承属性d。 产生式产生式ABC可能可能有语义有语义规则规则 C.d:=B.c+1 A.b:=A.a+B.c而属性而属性A.a和和B.c在其它地方计算在其它地方计算 内容线索属性文法属性文法n基于属性文法的处理方法基于属性文法的处理方法 n语法制导翻译语法制导翻译 概述n由源程序的语法结构所驱动的处理办法就由源程序的语法结构所驱动的处理办法就是是语法制导翻译法语法制导翻译法依赖图依赖图树遍历树遍历一遍扫描一遍扫描输入串输入串语法树语法树依赖图依赖图语义规则计算次序语义规则计算次序n基于属性文法的处理过程基于属性文法的处理过程依赖图

14、n在一棵语法树中的结点的继承属性和综合属性之间的相互在一棵语法树中的结点的继承属性和综合属性之间的相互依赖关系可以由称作依赖关系可以由称作依赖图依赖图的一个有向图来描述的一个有向图来描述n为每一个包含过程调用的语义规则引入一个为每一个包含过程调用的语义规则引入一个虚综合属性虚综合属性b，这样把每一个语义规则都写成这样把每一个语义规则都写成b:=f(c1,c2,ck)的形式的形式n依赖图中为每一个属性设置一个结点，如果属性依赖图中为每一个属性设置一个结点，如果属性b依赖于依赖于属性属性c，则从属性，则从属性c的结点有一条有向边连到属性的结点有一条有向边连到属性b的结点。的结点。依赖图构造算法fo

15、r 语法树中每一结点语法树中每一结点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结点构造一条有向边；结点构造一条有向边； EE1E2 E.val:=E1.val+E2.val E1+E2Evalvalval句子句子real id1，id2，id3的的带注释的语法树的依赖图带注释的语法树的依赖图id1L,id2L,id3LrealTD4type5in6 - addtype(id.entry, L.in)7in8 addtype9in10 addtype1entry2entry3entry产产 生生 式式 语语 义义 规规 则则 DTL L.in := T.type