编译原理第6章.ppt

《编译原理第6章.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第六章属性文法和语法制导翻译介绍有关语义分析及翻译的问题。语义描述和语义处理的方法主要是属性文法和语法制导翻译方法。本章中，将首先介绍属性文法的基本概念，然后介绍基于属性文法的处理方法，讨论如何在自上而下分析和自下而上分析中实现属性的计算。本章内容概要属性文法综合属性继承属性基于属性文法的处理方法依赖图属性的计算次序树遍历的属性计算方法一遍扫描的处理方法抽象语法树S-属性文法的自下而上计算分析栈中的综合属性L属性文法和自顶向下翻译翻译模式自顶向下翻译递归下降翻译器的设计自下而上计算继承属性从翻译模式中去掉嵌入在产生式中间的动作分析栈中的继承属性模拟继

2、承属性的计算用综合属性代替继承属性属性文法属性翻译文法是在上下文无关文法的基础上，为每个文法符号（终结符或非终结符）配备若干相关的“值”（称为属性）。这些属性代表与文法符号相关信息，例如它的类型、值、代码序列、符号表内容等等。属性与变量一样，可以进行计算和传递。属性加工的过程即是语义处理的过程。对于文法的每个产生式都配备了一组属性的计算规则，称为语义规则。属性通常分为两类：综合属性和继承属性。综合属性用于“自下而上”传递信息，而继承属性用于“自上而下”传递信息。在一个属性文法中，对应于每个产生式A→α都有一套与之相关联的语义规则，每条规则的形式为b:

3、＝f(c1，c2，…，ck)这里，f是一个函数，而且或者（1）b是A的一个综合属性并且c1，c2，…，ck是产生式右边文法符号的属性；或者(2)b是产生式右边某个文法符号的一个继承属性并且c1，c2，…，ck是A或产生式右边任何文法符号的属性。在两种情况下，我们都说属性b依赖于属性c1，c2，…，ck(1)终结符只有综合属性，它们由词法分析器提供；(2）非终结符既可有综合属性也可有继承属性，文法开始符号的所有继承属性作为属性计算前的初始值。对出现在产生式右边的继承属性和出现在产生式左边的综合属性都必须提供一个计算规则。属性计算规则中只能使用相应产生式

4、中的文法符号的属性，这有助于在产生式范围内“封装”属性的依赖性。然而，出现在产生式左边的继承属性和出现在产生式右边的综合属性不由所给的产生式的属性计算规则进行计算，它们由其它产生式的属性规则计算或者由属性计算器的参数提供。语义规则所描述的工作可以包括属性计算、静态语义检查、符号表操作、代码生成等等。例如，考虑非终结符A，B和C，其中，A有一个继承属性a和一个综合属性b，B有综合属性c，C有继承属性d。产生式A→BC可能有规则C.d：=B.c＋1A.b：=A.a＋B.c而属性A.a和B.c在其它地方计算。综合属性在语法树中，一个结点的综合属性的值由其子

5、结点的属性值确定。因此，通常使用自底向上的方法在每一个结点处使用语义规则计算综合属性的值。仅仅使用综合属性的属性文法称S-属性文法继承属性在语法树中，一个结点的继承属性由此结点的父结点和／或兄弟结点的某些属性确定。用继承属性来表示程序设计语言结构中的上下文依赖关系很方便。在下面的例子中，继承属性在说明中为各种标识符提供类型信息。句子realid1，id2，id3的带注释的语法树。基于属性文法的处理方法基于属性文法的处理过程通常是:对单词符号串进行语法分析，构造语法分析树，然后根据需要遍历语法树并在语法树的各结点处按语义规则进行计算。这种由源程序的语法

6、结构所驱动的处理办法就是语法制导翻译法。语义规则的计算可能产生代码、在符号表中存放信息、给出错误信息或执行任何其他动作。对输入符号串的翻译也就是根据语义规则进行计算的结果。输入串→语法树→依赖图→语义计算次序依赖图如果在一棵语法树中一个结点的属性b依赖于属性c，那么这个结点处计算b的语义规则必须在确定c的语义规则之后使用。在一棵语法树中的结点的继承属性和综合属性之间的相互依赖关系可以由称作依赖图的一个有向图来描述。在为一棵语法树构造依赖图以前，我们为每一个包含过程调用的语义规则引入一个虚综合属性b，这样把每一个语义规则都写成b：＝f(c1，c2，…，

7、ck)的形式。依赖图中为每一个属性设置一个结点，如果属性b依赖于属性c，则从属性c的结点有一条有向边连到属性b的结点。更详细地说，对于给定的一棵语法分析树、依赖图是按下面步骤构造出来的：for语法树中每一结点ndofor结点n的文法符号的每一个属性ado为a在依赖图中建立一个结点；for语法树中每一个结点ndofor结点n所用产生式对应的每一个语义规则b:＝f(c1，c2，…，ck)dofori:=1tokdo从ci结点到b结点构造一条有向边；属性的计算次序一个有向非循环图的拓扑序是图中结点的任何顺序m1,m2,…mk,使得边必须是从序列中前面的结点

8、指向后面的结点。如果mi→mj是mi到mj的一条边，那么在序列中mi必须出现在mj之前。一个依赖图的任何拓扑