编译原理课件 第6章 属性文法和语法制导翻译.pptVIP

Ch6.属性文法和语法制导翻译 本章在编译程序中的地位 教学要求 掌握： 两种属性: 综合属性，继承属性 基于属性文法的处理方法---语法制导翻译方法 教学内容 6.1 属性文法 综合属性，继承属性，语义规则，属性文法 6.2 基于属性文法的处理方法 语法制导翻译，依赖图法计算属性，树遍历计算属性，一遍扫描的处理方法，抽象语法树 CH.6 属性文法和语法制导翻译 在分析-综合模式的编译器中,语义分析是分析过程的最后一个步骤，只有在这一步才真正开始考虑程序语言的意义，并着手把它们翻译成某种中间代码。这一过程通常采用的方法是属性文法和语法制导翻译方法。 语法制导翻译方法的基本思想是，根据翻译的需要设置文法符号的属性，用属性描述语法结构的语义，用属性的计算完成翻译。 属性文法使文法符号属性值的计算和产生式相联系。随着语法分析的进行，执行属性值的计算，从而完成语义分析和翻译的任务。 6.1 属性文法 属性文法, 也称属性翻译文法或语法制导定义,是Knuth在1968年首先提出来的。 属性：在上下文无关文法的基础上为每个文法符号X(终结符或非终结符)配备若干个相关的“值”---这些“值”就称为文法符号X的属性。 属性值的设置和语法结构的语义以及翻译程序的需要有关。 属性代表与文法符号相关语义信息，如类型、值、代码序列、符号表内容等 属性、语义规则、属性文法 属性一般分为两类：综合属性和继承属性。 属性和变量一样，可以在语法分析过程中进行计算和传递。 语义规则：属性的计算规则。属性的加工和计算的过程即是语义处理的过程。 属性文法：以一个上下文无关文法为基础, 为每个文法符号引进一组属性，对文法的每个产生式都配备一组与之相关联的属性的计算规则(语义规则), 这样得到的文法。 属性文法是对上下文无关文法的推广。 属性文法、语义规则(1) 属性文法的形式： 产生式 语义规则 . A?? b:=f(c1,c2,…,ck) 这里, f 是一个函数, 表示属性 b 依赖于属性 c1,c2,…,ck，而且规定b: (1) b是A的一个综合属性并且c1,c2,…,ck是产生式右部文法符号的属性； 或者 (2) b是产生式右边某个文法符号的一个继承属性并且 c1,c2,…,ck 是A或产生式右部任何文法符号的属性 。 属性文法的说明(1) P136 属性文法的说明(2) 属性文法、语义规则(2) 属性文法的形式： 产生式 语义规则 . A?? b:=f(c1,c2,…,ck) 例如 P137.表6.1的属性文法: E?E1+ T E.val := E1.val+ T.val 例如 P139.表6.2的属性文法: D?TL L.in := T.type L?L1 , id L1.in := L.in 例, P137. 假设： 产生式 语义规则 A?BC A.b:=A.a+B.c C.d:=B.c+1 语义规则所描述的工作 语义规则所描述的工作可以是任何希望的翻译工作，如: 属性计算、静态语义检查、符号表操作、中间代码生成、报告出错， 等等。 语义规则可能产生副作用(如产生代码)，也可能不是变元的严格函数 b:=f(c1,c2,…,ck) ，如某个规则给出可用的下一个数据单元的地址。这样的语义规则通常写成过程调用或过程段--- 这时认为定义了一个虚属性。 属性文法举例：P137.表6.1 一个简单的台式计算器的属性文法。输入一个含+、*、(、)和数字的算术表达式(文法的句子), 计算并输出其值, 输入行以 n 结束。 两种属性：综合属性 综合属性用于“自下而上”传递信息。 综合属性：在语法树中，一个结点的综合属性的值由其子结点的属性值确定。 通常结合使用自下而上的分析方法在每一个结点处使用语义规则计算综合属性的值 --- 由下层子结点的属性值计算上层父结点的综合属性值，随着自下而上语法分析的进行，最终可计算出开始符号的综合属性值。 综合属性举例：例6.1 综合属性的使用及其自下而上的计算过程 P137.表6.1台式计算器的属性文法，输入一个表达式(以n结尾)，计算并打印其值。 例如：输入表达式 3*5+4n，输出数值19。 P138.图6.1给出了输入串3*5+4n的带注释的语法树 – 属性化的语法树。 综合属性X.val值随着自下而上语法分析的进行，自下而上的