第六章 属性文法和语法制导翻译第九周.ppt

第六章 属性文法和语  法制导翻译 程序语言语义的形式化描述——形式语义学 1962年美国斯坦福大学麦克阿瑟（Mcarthur）教授在国际信息加工联合会年会上作了著名的报告——“通往计算机的数学科学”，系统地论述了程序设计语言语义形式化的重要性，以及和程序正确性、语言的正确实施等的关系，并提出在形式语言研究中使用抽象语法和状态向量等基本方法——形式语义学 。 形式语义学分类 根据形式化的侧重面和所使用的数学工具的不同，形式语义学可分成： 操作语义学——着重模拟数据加工过程中计算机系统的操作。 指称语义学——主要描述数据加工的结果而不是加工过程的细节。 公理语义学——用公理化的方法描述程序对数据的加工。 代数语义学——把程序设计语言看作是刻划数据和加工数据的一种抽象数据类型，使用研究抽象数据类型的代数方法，来描述程序设计语言的形式语义。 语义分析方法 丹麦的科学家曾经运用指称语义学理论成功地实现了Ada语言的编译系统 。 形式语义学方法缺点：符号系统比较复杂，其描述文本不易读，不能借助这些形式系统自动完成语义处理任务。 目前实际应用中比较流行的语义描述和语义处理方法是属性文法和语法制导翻译的方法 内容线索 属性文法 基于属性文法的处理方法 语法制导翻译 属性文法 Knuth在1968年提出 在上下文无关文法的基础上，在描述语义动作时，为每个文法符号（终结符和非终结符）配备若干相关的“值”，如“类型”，“地址”等，称为属性。 对文法的每个产生式配备一组属性计算规则称为语义规则，它的描述形式为b:=f(c1,c2,…ck)，其中b,c1,c2…ck为文法符号的属性，f是一个函数。 每个文法符号联系于一组属性，且对每个产生式都给出其语义规则的文法称为属性文法。 属性和语义规则 属性代表与文法符号相关信息，如类型、值、代码序列、符号表内容等； 属性可以进行计算和传递； 在一个属性文法中，对应于每个产生式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→T T→T1*F T→F F→ (E) F→digit 记号表示 对于某个文法符号X∈VT ∪VN，用 X . type（X的类型），X . cat（X的种别），X .val（X的值或地址）等表示它的属性。 用下标（上角标）区分同一产生式中相同符号的多次出现。 综合属性 在语法树中，一个结点的综合属性的值由其子结点的属性值确定。 使用自底向上的方法在每一个结点处使用语义规则计算综合属性的值 仅仅使用综合属性的属性文法称S－属性文法 3*5+4n的带注释的语法树 产 生 式 语 义 规 则 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 继承属性 在语法树中，一个结点的继承属性由此结点的父结点和/或兄弟结点的某些属性确定 用继承属性来表示程序设计语言结构中的上下文依赖关系很方便 带继承属性L.in的属性文法 产 生 式 语 义 规 则 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) 句子real id1，id2，id3的带注释的语法树 产 生 式 语 义 规 则 D→TL L.in := T.type T→int T.type := integer T→real T.type := real L→L1, id L1.in