综合属性和继承属性课件.ppt

《综合属性和继承属性课件.ppt》由会员分享，可在线阅读，更多相关《综合属性和继承属性课件.ppt（66页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、编译原理编译原理第第1 1页页属性文法和语法制导翻译属性文法和语法制导翻译属性文法和语法制导翻译属性文法和语法制导翻译介绍有关语义分析及翻译的问题。介绍有关语义分析及翻译的问题。介绍有关语义分析及翻译的问题。介绍有关语义分析及翻译的问题。语义描述和语义处理的方法主要是属性文法和语语义描述和语义处理的方法主要是属性文法和语语义描述和语义处理的方法主要是属性文法和语语义描述和语义处理的方法主要是属性文法和语法制导翻译方法。法制导翻译方法。法制导翻译方法。法制导翻译方法。本章中，将首先介绍属性文法的基本概念，然后本章中，将首先介绍属性文法的基本概念，然后本章中，将首先介绍属性文法的基本概念，然后本章

2、中，将首先介绍属性文法的基本概念，然后介绍基于属性文法的处理方法，讨论如何在自上介绍基于属性文法的处理方法，讨论如何在自上介绍基于属性文法的处理方法，讨论如何在自上介绍基于属性文法的处理方法，讨论如何在自上而下分析和自下而上分析中实现属性的计算。而下分析和自下而上分析中实现属性的计算。而下分析和自下而上分析中实现属性的计算。而下分析和自下而上分析中实现属性的计算。编译原理编译原理第第2 2页页属性文法和语法制导翻译属性文法和语法制导翻译属性文法和语法制导翻译属性文法和语法制导翻译本章内容概要本章内容概要本章内容概要本章内容概要属性文法属性文法属性文法属性文法综合属性综合属性综合属性综合属性继承

3、属性继承属性继承属性继承属性基于属性文法的处理方法基于属性文法的处理方法基于属性文法的处理方法基于属性文法的处理方法依赖图依赖图依赖图依赖图属性的计算次序属性的计算次序属性的计算次序属性的计算次序树遍历的属性计算方法树遍历的属性计算方法树遍历的属性计算方法树遍历的属性计算方法一遍扫描的处理方法一遍扫描的处理方法一遍扫描的处理方法一遍扫描的处理方法抽象语法树抽象语法树抽象语法树抽象语法树S-S-S-S-属性文法的自下而上计算属性文法的自下而上计算属性文法的自下而上计算属性文法的自下而上计算分析栈中的综合属性分析栈中的综合属性分析栈中的综合属性分析栈中的综合属性编译原理编译原理第第3 3页页属性文

4、法和语法制导翻译属性文法和语法制导翻译属性文法和语法制导翻译属性文法和语法制导翻译L L L L属性文法和自顶向下翻译属性文法和自顶向下翻译属性文法和自顶向下翻译属性文法和自顶向下翻译翻译模式翻译模式翻译模式翻译模式自顶向下翻译自顶向下翻译自顶向下翻译自顶向下翻译递归下降翻译器的设计递归下降翻译器的设计递归下降翻译器的设计递归下降翻译器的设计自下而上计算继承属性自下而上计算继承属性自下而上计算继承属性自下而上计算继承属性从翻译模式中去掉嵌入在产生式中间的动作从翻译模式中去掉嵌入在产生式中间的动作从翻译模式中去掉嵌入在产生式中间的动作从翻译模式中去掉嵌入在产生式中间的动作分析栈中的继承属性分析栈

5、中的继承属性分析栈中的继承属性分析栈中的继承属性模拟继承属性的计算模拟继承属性的计算模拟继承属性的计算模拟继承属性的计算用综合属性代替继承属性用综合属性代替继承属性用综合属性代替继承属性用综合属性代替继承属性编译原理编译原理第第4 4页页属性文法和语法制导翻译属性文法和语法制导翻译属性文法和语法制导翻译属性文法和语法制导翻译属性文法属性文法属性文法属性文法 属性翻译文法是在上下文无关文法的基础上，为每个属性翻译文法是在上下文无关文法的基础上，为每个属性翻译文法是在上下文无关文法的基础上，为每个属性翻译文法是在上下文无关文法的基础上，为每个文法符号（终结符或非终结符）配备若干相关的文法符号（终结

6、符或非终结符）配备若干相关的文法符号（终结符或非终结符）配备若干相关的文法符号（终结符或非终结符）配备若干相关的“值值值值”（称为属性）。（称为属性）。（称为属性）。（称为属性）。这些属性代表与文法符号相关信息，例如它的类型、这些属性代表与文法符号相关信息，例如它的类型、这些属性代表与文法符号相关信息，例如它的类型、这些属性代表与文法符号相关信息，例如它的类型、值、代码序列、符号表内容等等。值、代码序列、符号表内容等等。值、代码序列、符号表内容等等。值、代码序列、符号表内容等等。属性与变量一样，可以进行计算和传递。属性与变量一样，可以进行计算和传递。属性与变量一样，可以进行计算和传递。属性与变

7、量一样，可以进行计算和传递。属性加工的过程即是语义处理的过程。对于文法的每属性加工的过程即是语义处理的过程。对于文法的每属性加工的过程即是语义处理的过程。对于文法的每属性加工的过程即是语义处理的过程。对于文法的每个产生式都配备了一组属性的计算规则，称为语义规个产生式都配备了一组属性的计算规则，称为语义规个产生式都配备了一组属性的计算规则，称为语义规个产生式都配备了一组属性的计算规则，称为语义规则。则。则。则。编译原理编译原理第第5 5页页属性文法和语法制导翻译属性文法和语法制导翻译属性文法和语法制导翻译属性文法和语法制导翻译属性通常分为两类：属性通常分为两类：属性通常分为两类：属性通常分为两类

8、：综合属性和继承属性。综合属性和继承属性。综合属性和继承属性。综合属性和继承属性。综合属性用于综合属性用于综合属性用于综合属性用于“自下而上自下而上自下而上自下而上”传递信息，而继承属性用于传递信息，而继承属性用于传递信息，而继承属性用于传递信息，而继承属性用于“自上自上自上自上而下而下而下而下”传递信息。传递信息。传递信息。传递信息。在一个属性文法中，对应于每个产生式在一个属性文法中，对应于每个产生式在一个属性文法中，对应于每个产生式在一个属性文法中，对应于每个产生式A A 都有一套与之相都有一套与之相都有一套与之相都有一套与之相关联的语义规则，每条规则的形式为关联的语义规则，每条规则的形式

9、为关联的语义规则，每条规则的形式为关联的语义规则，每条规则的形式为 b:b:f(c1f(c1，c2c2，ck)ck)这里，这里，这里，这里，f f是一个函数，而且或者是一个函数，而且或者是一个函数，而且或者是一个函数，而且或者（1 1）b b是是是是A A的一个综合属性并且的一个综合属性并且的一个综合属性并且的一个综合属性并且c1c1，c2c2，ckck 是产生式右边是产生式右边是产生式右边是产生式右边文法符号的属性；或者文法符号的属性；或者文法符号的属性；或者文法符号的属性；或者 (2)b (2)b是产生式右边某个文法符号的一个继承属性并且是产生式右边某个文法符号的一个继承属性并且是产生式右

10、边某个文法符号的一个继承属性并且是产生式右边某个文法符号的一个继承属性并且c1c1，c2c2，ckck 是是是是A A或产生式右边任何文法符号的属性。或产生式右边任何文法符号的属性。或产生式右边任何文法符号的属性。或产生式右边任何文法符号的属性。在两种情况下，我们都说属性在两种情况下，我们都说属性在两种情况下，我们都说属性在两种情况下，我们都说属性b b依赖于属性依赖于属性依赖于属性依赖于属性 c1c1，c2c2，ckck 编译原理编译原理第第6 6页页属性文法和语法制导翻译属性文法和语法制导翻译属性文法和语法制导翻译属性文法和语法制导翻译(1)(1)终结符只有综合属性，它们由词法分析器提供；

11、终结符只有综合属性，它们由词法分析器提供；终结符只有综合属性，它们由词法分析器提供；终结符只有综合属性，它们由词法分析器提供；(2(2）非终结符既可有综合属性也可有继承属性，文法开始符）非终结符既可有综合属性也可有继承属性，文法开始符）非终结符既可有综合属性也可有继承属性，文法开始符）非终结符既可有综合属性也可有继承属性，文法开始符号的所有继承属性作为属性计算前的初始值。号的所有继承属性作为属性计算前的初始值。号的所有继承属性作为属性计算前的初始值。号的所有继承属性作为属性计算前的初始值。对出现在产生式右边的继承属性和出现在产生式左边的综合对出现在产生式右边的继承属性和出现在产生式左边的综合对

12、出现在产生式右边的继承属性和出现在产生式左边的综合对出现在产生式右边的继承属性和出现在产生式左边的综合属性都必须提供一个计算规则。属性都必须提供一个计算规则。属性都必须提供一个计算规则。属性都必须提供一个计算规则。属性计算规则中只能使用相应产生式中的文法符号的属性，属性计算规则中只能使用相应产生式中的文法符号的属性，属性计算规则中只能使用相应产生式中的文法符号的属性，属性计算规则中只能使用相应产生式中的文法符号的属性，这有助于在产生式范围内这有助于在产生式范围内这有助于在产生式范围内这有助于在产生式范围内“封装封装封装封装”属性的依赖性。然而，出属性的依赖性。然而，出属性的依赖性。然而，出属性

13、的依赖性。然而，出现在产生式左边的继承属性和出现在产生式右边的综合属性现在产生式左边的继承属性和出现在产生式右边的综合属性现在产生式左边的继承属性和出现在产生式右边的综合属性现在产生式左边的继承属性和出现在产生式右边的综合属性不由所给的产生式的属性计算规则进行计算，它们由其它产不由所给的产生式的属性计算规则进行计算，它们由其它产不由所给的产生式的属性计算规则进行计算，它们由其它产不由所给的产生式的属性计算规则进行计算，它们由其它产生式的属性规则计算或者由属性计算器的参数提供。生式的属性规则计算或者由属性计算器的参数提供。生式的属性规则计算或者由属性计算器的参数提供。生式的属性规则计算或者由属性

14、计算器的参数提供。编译原理编译原理第第7 7页页属性文法和语法制导翻译属性文法和语法制导翻译属性文法和语法制导翻译属性文法和语法制导翻译语义规则所描述的工作可以包括属性计算、静态语义检查、语义规则所描述的工作可以包括属性计算、静态语义检查、语义规则所描述的工作可以包括属性计算、静态语义检查、语义规则所描述的工作可以包括属性计算、静态语义检查、符号表操作、代码生成等等。符号表操作、代码生成等等。符号表操作、代码生成等等。符号表操作、代码生成等等。编译原理编译原理第第8 8页页属性文法和语法制导翻译属性文法和语法制导翻译属性文法和语法制导翻译属性文法和语法制导翻译例如，考虑非终结符例如，考虑非终结

15、符例如，考虑非终结符例如，考虑非终结符A A，B B和和和和C C，其中，其中，其中，其中，A A有一个继承有一个继承有一个继承有一个继承属性属性属性属性a a和一个综合属性和一个综合属性和一个综合属性和一个综合属性b b，B B有综合属性有综合属性有综合属性有综合属性c c，C C有继承属有继承属有继承属有继承属性性性性d d。产生式。产生式。产生式。产生式A ABCBC可能有规则可能有规则可能有规则可能有规则 C.d C.d：=B.cB.c1 1 A.b A.b：=A.aA.aB.cB.c而属性而属性而属性而属性A.aA.a和和和和B.cB.c在其它地方计算。在其它地方计算。在其它地方计算

16、。在其它地方计算。编译原理编译原理第第9 9页页属性文法和语法制导翻译属性文法和语法制导翻译属性文法和语法制导翻译属性文法和语法制导翻译编译原理编译原理第第1010页页属性文法和语法制导翻译属性文法和语法制导翻译属性文法和语法制导翻译属性文法和语法制导翻译综合属性综合属性综合属性综合属性在语法树中，一个结点的综合属性的值由其子结点的在语法树中，一个结点的综合属性的值由其子结点的在语法树中，一个结点的综合属性的值由其子结点的在语法树中，一个结点的综合属性的值由其子结点的属性值确定。因此，通常使用自底向上的方法在每一属性值确定。因此，通常使用自底向上的方法在每一属性值确定。因此，通常使用自底向上的

17、方法在每一属性值确定。因此，通常使用自底向上的方法在每一个结点处使用语义规则计算综合属性的值。仅仅使用个结点处使用语义规则计算综合属性的值。仅仅使用个结点处使用语义规则计算综合属性的值。仅仅使用个结点处使用语义规则计算综合属性的值。仅仅使用综合属性的属性文法称综合属性的属性文法称综合属性的属性文法称综合属性的属性文法称S-S-属性文法属性文法属性文法属性文法 编译原理编译原理第第1111页页属性文法和语法制导翻译属性文法和语法制导翻译属性文法和语法制导翻译属性文法和语法制导翻译编译原理编译原理第第1212页页属性文法和语法制导翻译属性文法和语法制导翻译属性文法和语法制导翻译属性文法和语法制导翻

18、译继承属性继承属性继承属性继承属性在语法树中，一个结点的继承属性由此结点的父结点在语法树中，一个结点的继承属性由此结点的父结点在语法树中，一个结点的继承属性由此结点的父结点在语法树中，一个结点的继承属性由此结点的父结点和或兄弟结点的某些属性确定。和或兄弟结点的某些属性确定。和或兄弟结点的某些属性确定。和或兄弟结点的某些属性确定。用继承属性来表示程序设计语言结构中的上下文依赖用继承属性来表示程序设计语言结构中的上下文依赖用继承属性来表示程序设计语言结构中的上下文依赖用继承属性来表示程序设计语言结构中的上下文依赖关系很方便。在下面的例子中，继承属性在说明中为关系很方便。在下面的例子中，继承属性在说

19、明中为关系很方便。在下面的例子中，继承属性在说明中为关系很方便。在下面的例子中，继承属性在说明中为各种标识符提供类型信息。各种标识符提供类型信息。各种标识符提供类型信息。各种标识符提供类型信息。编译原理编译原理第第1313页页属性文法和语法制导翻译属性文法和语法制导翻译属性文法和语法制导翻译属性文法和语法制导翻译编译原理编译原理第第1414页页属性文法和语法制导翻译属性文法和语法制导翻译属性文法和语法制导翻译属性文法和语法制导翻译句子句子句子句子real id1real id1，id2id2，id3id3的带注释的语法树。的带注释的语法树。的带注释的语法树。的带注释的语法树。编译原理编译原理第

20、第1515页页属性文法和语法制导翻译属性文法和语法制导翻译属性文法和语法制导翻译属性文法和语法制导翻译基于属性文法的处理方法基于属性文法的处理方法基于属性文法的处理方法基于属性文法的处理方法 l l基于属性文法的处理过程通常是基于属性文法的处理过程通常是基于属性文法的处理过程通常是基于属性文法的处理过程通常是:l l对单词符号串进行语法分析，构造语法分析树，对单词符号串进行语法分析，构造语法分析树，对单词符号串进行语法分析，构造语法分析树，对单词符号串进行语法分析，构造语法分析树，然后根据需要遍历语法树并在语法树的各结点处然后根据需要遍历语法树并在语法树的各结点处然后根据需要遍历语法树并在语法

21、树的各结点处然后根据需要遍历语法树并在语法树的各结点处按语义规则进行计算。按语义规则进行计算。按语义规则进行计算。按语义规则进行计算。l l这种由源程序的语法结构所驱动的处理办法就是这种由源程序的语法结构所驱动的处理办法就是这种由源程序的语法结构所驱动的处理办法就是这种由源程序的语法结构所驱动的处理办法就是语法制导翻译法。语法制导翻译法。语法制导翻译法。语法制导翻译法。l l语义规则的计算可能产生代码、在符号表中存放语义规则的计算可能产生代码、在符号表中存放语义规则的计算可能产生代码、在符号表中存放语义规则的计算可能产生代码、在符号表中存放信息、给出错误信息或执行任何其他动作。对输信息、给出错

22、误信息或执行任何其他动作。对输信息、给出错误信息或执行任何其他动作。对输信息、给出错误信息或执行任何其他动作。对输入符号串的翻译也就是根据语义规则进行计算的入符号串的翻译也就是根据语义规则进行计算的入符号串的翻译也就是根据语义规则进行计算的入符号串的翻译也就是根据语义规则进行计算的结果。结果。结果。结果。输入串输入串输入串输入串 语法树语法树语法树语法树 依赖图依赖图依赖图依赖图 语义计算次序语义计算次序语义计算次序语义计算次序编译原理编译原理第第1616页页属性文法和语法制导翻译属性文法和语法制导翻译属性文法和语法制导翻译属性文法和语法制导翻译依赖图依赖图依赖图依赖图如果在一棵语法树中一个结

23、点的属性如果在一棵语法树中一个结点的属性如果在一棵语法树中一个结点的属性如果在一棵语法树中一个结点的属性b b依赖于属性依赖于属性依赖于属性依赖于属性c c，那，那，那，那么这个结点处计算么这个结点处计算么这个结点处计算么这个结点处计算b b的语义规则必须在确定的语义规则必须在确定的语义规则必须在确定的语义规则必须在确定c c的语义规则的语义规则的语义规则的语义规则之后使用。之后使用。之后使用。之后使用。在一棵语法树中的结点的继承属性和综合属性之间的相在一棵语法树中的结点的继承属性和综合属性之间的相在一棵语法树中的结点的继承属性和综合属性之间的相在一棵语法树中的结点的继承属性和综合属性之间的相

24、互依赖关系可以由称作依赖图的一个有向图来描述。互依赖关系可以由称作依赖图的一个有向图来描述。互依赖关系可以由称作依赖图的一个有向图来描述。互依赖关系可以由称作依赖图的一个有向图来描述。编译原理编译原理第第1717页页属性文法和语法制导翻译属性文法和语法制导翻译属性文法和语法制导翻译属性文法和语法制导翻译在为一棵语法树构造依赖图以前，我们为每一个包含过在为一棵语法树构造依赖图以前，我们为每一个包含过在为一棵语法树构造依赖图以前，我们为每一个包含过在为一棵语法树构造依赖图以前，我们为每一个包含过程调用的语义规则引入一个虚综合属性程调用的语义规则引入一个虚综合属性程调用的语义规则引入一个虚综合属性程

25、调用的语义规则引入一个虚综合属性b b，这样把每一，这样把每一，这样把每一，这样把每一个语义规则都写成个语义规则都写成个语义规则都写成个语义规则都写成 b b：f(c1f(c1，c2c2，ck)ck)的形式。依赖图中为每一个属性设置一个结点，如果属的形式。依赖图中为每一个属性设置一个结点，如果属的形式。依赖图中为每一个属性设置一个结点，如果属的形式。依赖图中为每一个属性设置一个结点，如果属性性性性b b依赖于属性依赖于属性依赖于属性依赖于属性c c，则从属性，则从属性，则从属性，则从属性c c的结点有一条有向边连到的结点有一条有向边连到的结点有一条有向边连到的结点有一条有向边连到属性属性属性属

26、性b b的结点。更详细地说，对于给定的一棵语法分析的结点。更详细地说，对于给定的一棵语法分析的结点。更详细地说，对于给定的一棵语法分析的结点。更详细地说，对于给定的一棵语法分析树、依赖图是按下面步骤构造出来的：树、依赖图是按下面步骤构造出来的：树、依赖图是按下面步骤构造出来的：树、依赖图是按下面步骤构造出来的：编译原理编译原理第第1818页页属性文法和语法制导翻译属性文法和语法制导翻译属性文法和语法制导翻译属性文法和语法制导翻译 for for 语法树中每一结点语法树中每一结点语法树中每一结点语法树中每一结点n don do for for 结点结点结点结点n n的文法符号的每一个属性的文法符

27、号的每一个属性的文法符号的每一个属性的文法符号的每一个属性a doa do 为为为为a a在依赖图中建立一个结点；在依赖图中建立一个结点；在依赖图中建立一个结点；在依赖图中建立一个结点；for for 语法树中每一个结点语法树中每一个结点语法树中每一个结点语法树中每一个结点n don do for for 结点结点结点结点n n所用产生式对应的每一个语义规则所用产生式对应的每一个语义规则所用产生式对应的每一个语义规则所用产生式对应的每一个语义规则 b:b:f(c1f(c1，c2c2，ck)dock)do for i:=1 to k do for i:=1 to k do 从从从从cici结点到

28、结点到结点到结点到b b结点构造一条有向边；结点构造一条有向边；结点构造一条有向边；结点构造一条有向边；编译原理编译原理第第1919页页属性文法和语法制导翻译属性文法和语法制导翻译属性文法和语法制导翻译属性文法和语法制导翻译编译原理编译原理第第2020页页属性文法和语法制导翻译属性文法和语法制导翻译属性文法和语法制导翻译属性文法和语法制导翻译属性的计算次序属性的计算次序属性的计算次序属性的计算次序一个有向非循环图的拓扑序是图中结点的任何顺序一个有向非循环图的拓扑序是图中结点的任何顺序一个有向非循环图的拓扑序是图中结点的任何顺序一个有向非循环图的拓扑序是图中结点的任何顺序m1,m2,m1,m2,

29、mkmk,使得边必须是从序列中前面的结点指向使得边必须是从序列中前面的结点指向使得边必须是从序列中前面的结点指向使得边必须是从序列中前面的结点指向后面的结点。后面的结点。后面的结点。后面的结点。如果如果如果如果mimimjmjmjmj是是是是mimi到到到到mjmj的一条边，那么在序列中的一条边，那么在序列中的一条边，那么在序列中的一条边，那么在序列中mimi必必必必须出现在须出现在须出现在须出现在mjmj之前。之前。之前。之前。编译原理编译原理第第2121页页属性文法和语法制导翻译属性文法和语法制导翻译属性文法和语法制导翻译属性文法和语法制导翻译一个依赖图的任何拓扑排序都给出一个语法树中结点

30、的语一个依赖图的任何拓扑排序都给出一个语法树中结点的语一个依赖图的任何拓扑排序都给出一个语法树中结点的语一个依赖图的任何拓扑排序都给出一个语法树中结点的语义规则计算的有效顺序。义规则计算的有效顺序。义规则计算的有效顺序。义规则计算的有效顺序。在拓扑排序中，在一个结点上，语义规则在拓扑排序中，在一个结点上，语义规则在拓扑排序中，在一个结点上，语义规则在拓扑排序中，在一个结点上，语义规则 b:=f(c1b:=f(c1，c2c2，ckck）中的属性中的属性中的属性中的属性 clcl，c2c2,ck,ck 在计算在计算在计算在计算b b以前都是可用的。以前都是可用的。以前都是可用的。以前都是可用的。属

31、性文法说明的翻译是很精确的。基础文法用于建立输入属性文法说明的翻译是很精确的。基础文法用于建立输入属性文法说明的翻译是很精确的。基础文法用于建立输入属性文法说明的翻译是很精确的。基础文法用于建立输入符号串的语法分析树。依赖图如上面讨论的那样建立。从符号串的语法分析树。依赖图如上面讨论的那样建立。从符号串的语法分析树。依赖图如上面讨论的那样建立。从符号串的语法分析树。依赖图如上面讨论的那样建立。从依赖图的拓扑排序中，我们可以得到计算语义规则的顺序。依赖图的拓扑排序中，我们可以得到计算语义规则的顺序。依赖图的拓扑排序中，我们可以得到计算语义规则的顺序。依赖图的拓扑排序中，我们可以得到计算语义规则的

32、顺序。用这个顺序来计算语义规则就得到输入符号串的翻译。用这个顺序来计算语义规则就得到输入符号串的翻译。用这个顺序来计算语义规则就得到输入符号串的翻译。用这个顺序来计算语义规则就得到输入符号串的翻译。编译原理编译原理第第2222页页属性文法和语法制导翻译属性文法和语法制导翻译属性文法和语法制导翻译属性文法和语法制导翻译在上图的依赖图中，每一条边都是从序号较低的结点在上图的依赖图中，每一条边都是从序号较低的结点在上图的依赖图中，每一条边都是从序号较低的结点在上图的依赖图中，每一条边都是从序号较低的结点指向序号较高的结点。因此，指向序号较高的结点。因此，指向序号较高的结点。因此，指向序号较高的结点。

33、因此，依赖图的一个拓扑排序依赖图的一个拓扑排序可以从低序号到高序号顺序写出。可以从低序号到高序号顺序写出。从这个拓扑排序中从这个拓扑排序中从这个拓扑排序中从这个拓扑排序中我们可以得到下列程序，用我们可以得到下列程序，用我们可以得到下列程序，用我们可以得到下列程序，用anan来代表依赖图中与序号来代表依赖图中与序号来代表依赖图中与序号来代表依赖图中与序号n n的结点有关的属性的结点有关的属性的结点有关的属性的结点有关的属性.这些语法规则的计算将把这些语法规则的计算将把这些语法规则的计算将把这些语法规则的计算将把realreal类类类类型填入到每个标识符对应的符号表项中。型填入到每个标识符对应的符

34、号表项中。型填入到每个标识符对应的符号表项中。型填入到每个标识符对应的符号表项中。a4:=reala4:=real a5:=a4 a5:=a4 addtype(id3.entry,a5)addtype(id3.entry,a5)a7:=a5 a7:=a5 addtype(id2.entry,a7)addtype(id2.entry,a7)a9:=a7 a9:=a7 addtype(id1.entry,a9)addtype(id1.entry,a9)编译原理编译原理第第2323页页属性文法和语法制导翻译属性文法和语法制导翻译属性文法和语法制导翻译属性文法和语法制导翻译树遍历的属性计算方法树遍历的

35、属性计算方法树遍历的属性计算方法树遍历的属性计算方法 假设语法树已经建立好了，并且树中已带有开始符号的继假设语法树已经建立好了，并且树中已带有开始符号的继假设语法树已经建立好了，并且树中已带有开始符号的继假设语法树已经建立好了，并且树中已带有开始符号的继承属性和终结符的综合属性。承属性和终结符的综合属性。承属性和终结符的综合属性。承属性和终结符的综合属性。然后以某种次序遍历语法树，直至计算出所有属性。最常然后以某种次序遍历语法树，直至计算出所有属性。最常然后以某种次序遍历语法树，直至计算出所有属性。最常然后以某种次序遍历语法树，直至计算出所有属性。最常用的遍历方法是深度优先，从左到右的遍历方法

36、。如果需用的遍历方法是深度优先，从左到右的遍历方法。如果需用的遍历方法是深度优先，从左到右的遍历方法。如果需用的遍历方法是深度优先，从左到右的遍历方法。如果需要的话，可使用多次遍历（或称遍）。要的话，可使用多次遍历（或称遍）。要的话，可使用多次遍历（或称遍）。要的话，可使用多次遍历（或称遍）。编译原理编译原理第第2424页页属性文法和语法制导翻译属性文法和语法制导翻译属性文法和语法制导翻译属性文法和语法制导翻译下面算法可对任何无循环的属性文法进行计算下面算法可对任何无循环的属性文法进行计算下面算法可对任何无循环的属性文法进行计算下面算法可对任何无循环的属性文法进行计算 While While

37、还有未被计算的属性还有未被计算的属性还有未被计算的属性还有未被计算的属性 dodo VisittNode(SVisittNode(S)*S S是开始符号是开始符号是开始符号是开始符号*procedure procedure VisitNodeVisitNode（N:NodeN:Node）；）；）；）；begin begin if N if N是一个非终结符是一个非终结符是一个非终结符是一个非终结符 thenthen *假设它的产生式为假设它的产生式为假设它的产生式为假设它的产生式为N NX1,X2,X1,X2,XmXm *for i:=1 to m do for i:=1 to m do if

38、 not if not XiXiVtVt then then*即即即即Xi Xi 是非终结符是非终结符是非终结符是非终结符 *begin begin 计算计算计算计算 Xi Xi 的所有能够计算的继承属性；的所有能够计算的继承属性；的所有能够计算的继承属性；的所有能够计算的继承属性；VisitNodeVisitNode(X;)(X;)endend；计算计算计算计算 N N 的所有能够计算的综合属性的所有能够计算的综合属性的所有能够计算的综合属性的所有能够计算的综合属性 endend编译原理编译原理第第2525页页属性文法和语法制导翻译属性文法和语法制导翻译属性文法和语法制导翻译属性文法和语法制

39、导翻译只要文法的属性是非循环定义的，则每一次扫描至少只要文法的属性是非循环定义的，则每一次扫描至少只要文法的属性是非循环定义的，则每一次扫描至少只要文法的属性是非循环定义的，则每一次扫描至少有一个属性值被计算出来。有一个属性值被计算出来。有一个属性值被计算出来。有一个属性值被计算出来。如果语法树有如果语法树有如果语法树有如果语法树有n n个结点（因此最多有个结点（因此最多有个结点（因此最多有个结点（因此最多有O(nO(n)个属性），个属性），个属性），个属性），最坏的情况整个遍历需最坏的情况整个遍历需最坏的情况整个遍历需最坏的情况整个遍历需O(nO(n)时间。时间。时间。时间。编译原理编译原理

40、第第2626页页属性文法和语法制导翻译属性文法和语法制导翻译属性文法和语法制导翻译属性文法和语法制导翻译例：例：例：例：S S有继承属性有继承属性有继承属性有继承属性a a，综合属性，综合属性，综合属性，综合属性b b；X X有继承属性有继承属性有继承属性有继承属性c,c,综合属性综合属性综合属性综合属性d d；Y Y有继承属性有继承属性有继承属性有继承属性e e、综合属性、综合属性、综合属性、综合属性f f；z z有继承属性有继承属性有继承属性有继承属性h h、综合属性、综合属性、综合属性、综合属性g g。编译原理编译原理第第2727页页属性文法和语法制导翻译属性文法和语法制导翻译属性文法和

41、语法制导翻译属性文法和语法制导翻译编译原理编译原理第第2828页页属性文法和语法制导翻译属性文法和语法制导翻译属性文法和语法制导翻译属性文法和语法制导翻译一遍扫描的处理方法一遍扫描的处理方法一遍扫描的处理方法一遍扫描的处理方法 一遍扫描的处理方法是在语法分析的同时计算属性值，而一遍扫描的处理方法是在语法分析的同时计算属性值，而一遍扫描的处理方法是在语法分析的同时计算属性值，而一遍扫描的处理方法是在语法分析的同时计算属性值，而不是语法分析构造语法树之后进行属性的计算，而且无需不是语法分析构造语法树之后进行属性的计算，而且无需不是语法分析构造语法树之后进行属性的计算，而且无需不是语法分析构造语法树

42、之后进行属性的计算，而且无需构造实际的语法树（如果有必须，当然也可以实际构造）。构造实际的语法树（如果有必须，当然也可以实际构造）。构造实际的语法树（如果有必须，当然也可以实际构造）。构造实际的语法树（如果有必须，当然也可以实际构造）。编译原理编译原理第第2929页页属性文法和语法制导翻译属性文法和语法制导翻译属性文法和语法制导翻译属性文法和语法制导翻译因为一遍扫描的处理方法与语法分析器的相互作用，它与下因为一遍扫描的处理方法与语法分析器的相互作用，它与下因为一遍扫描的处理方法与语法分析器的相互作用，它与下因为一遍扫描的处理方法与语法分析器的相互作用，它与下面两个因素密切相关：面两个因素密切相

43、关：面两个因素密切相关：面两个因素密切相关：（1)1)所采用的语法分析方法；所采用的语法分析方法；所采用的语法分析方法；所采用的语法分析方法；(2)(2)属性的计算次序。属性的计算次序。属性的计算次序。属性的计算次序。L-L-属性文法可用于一遍扫描的自上而下分析，而属性文法可用于一遍扫描的自上而下分析，而属性文法可用于一遍扫描的自上而下分析，而属性文法可用于一遍扫描的自上而下分析，而S-S-属性文法属性文法属性文法属性文法适合于一遍扫描的自下而上分析。适合于一遍扫描的自下而上分析。适合于一遍扫描的自下而上分析。适合于一遍扫描的自下而上分析。编译原理编译原理第第3030页页属性文法和语法制导翻译

44、属性文法和语法制导翻译属性文法和语法制导翻译属性文法和语法制导翻译如果按这种一遍扫描的编译程序模型来理解语法制导翻译如果按这种一遍扫描的编译程序模型来理解语法制导翻译如果按这种一遍扫描的编译程序模型来理解语法制导翻译如果按这种一遍扫描的编译程序模型来理解语法制导翻译方法的话，方法的话，方法的话，方法的话，语法制导翻译就是为文法中每个产生式配上一组语义规则，语法制导翻译就是为文法中每个产生式配上一组语义规则，语法制导翻译就是为文法中每个产生式配上一组语义规则，语法制导翻译就是为文法中每个产生式配上一组语义规则，并且在语法分析的同时执行这些语义规则。并且在语法分析的同时执行这些语义规则。并且在语法

45、分析的同时执行这些语义规则。并且在语法分析的同时执行这些语义规则。在自上而下语法分析中，若一个产生式匹配输入串成功，在自上而下语法分析中，若一个产生式匹配输入串成功，在自上而下语法分析中，若一个产生式匹配输入串成功，在自上而下语法分析中，若一个产生式匹配输入串成功，或者，在自下而上分析中，当一个产生式被用于进行归约或者，在自下而上分析中，当一个产生式被用于进行归约或者，在自下而上分析中，当一个产生式被用于进行归约或者，在自下而上分析中，当一个产生式被用于进行归约时，此产生式相应的语义规则就被计算，完成有关的语义时，此产生式相应的语义规则就被计算，完成有关的语义时，此产生式相应的语义规则就被计算

46、，完成有关的语义时，此产生式相应的语义规则就被计算，完成有关的语义分析和代码产生的工作。分析和代码产生的工作。分析和代码产生的工作。分析和代码产生的工作。在这种情况下，语法分析工作和语义规则的计算是穿插进在这种情况下，语法分析工作和语义规则的计算是穿插进在这种情况下，语法分析工作和语义规则的计算是穿插进在这种情况下，语法分析工作和语义规则的计算是穿插进行的。行的。行的。行的。编译原理编译原理第第3131页页属性文法和语法制导翻译属性文法和语法制导翻译属性文法和语法制导翻译属性文法和语法制导翻译抽象语法树抽象语法树抽象语法树抽象语法树 通过语法分析可以很容易构造出语法分析树，然后对语法通过语法分

47、析可以很容易构造出语法分析树，然后对语法通过语法分析可以很容易构造出语法分析树，然后对语法通过语法分析可以很容易构造出语法分析树，然后对语法树进行遍历完成属性的计算。树进行遍历完成属性的计算。树进行遍历完成属性的计算。树进行遍历完成属性的计算。因此，语法树可以作为一种合适的中间语言形式。因此，语法树可以作为一种合适的中间语言形式。因此，语法树可以作为一种合适的中间语言形式。因此，语法树可以作为一种合适的中间语言形式。在语法树中去掉那些对翻译不必要的信息，从而获得更有在语法树中去掉那些对翻译不必要的信息，从而获得更有在语法树中去掉那些对翻译不必要的信息，从而获得更有在语法树中去掉那些对翻译不必要

48、的信息，从而获得更有效的源程序中间表示。这种经变换后的语法树称之为抽象效的源程序中间表示。这种经变换后的语法树称之为抽象效的源程序中间表示。这种经变换后的语法树称之为抽象效的源程序中间表示。这种经变换后的语法树称之为抽象语法树语法树语法树语法树 编译原理编译原理第第3232页页属性文法和语法制导翻译属性文法和语法制导翻译属性文法和语法制导翻译属性文法和语法制导翻译在抽象语法树中，操作符和关键字都不作为叶结点出现，而在抽象语法树中，操作符和关键字都不作为叶结点出现，而在抽象语法树中，操作符和关键字都不作为叶结点出现，而在抽象语法树中，操作符和关键字都不作为叶结点出现，而是把它们作为内部结点，即这

49、些叶结点的父结点。是把它们作为内部结点，即这些叶结点的父结点。是把它们作为内部结点，即这些叶结点的父结点。是把它们作为内部结点，即这些叶结点的父结点。如产生式如产生式如产生式如产生式S S if B then S1 else S2 if B then S1 else S2 If_then_elseBS1S2编译原理编译原理第第3333页页属性文法和语法制导翻译属性文法和语法制导翻译属性文法和语法制导翻译属性文法和语法制导翻译下面是表达式下面是表达式下面是表达式下面是表达式3 35 54 4的抽象语法树：的抽象语法树：的抽象语法树：的抽象语法树：+*435编译原理编译原理第第3434页页属性文法

50、和语法制导翻译属性文法和语法制导翻译属性文法和语法制导翻译属性文法和语法制导翻译语法制导翻译既可以基于语法分析树，也可以基于抽象语语法制导翻译既可以基于语法分析树，也可以基于抽象语语法制导翻译既可以基于语法分析树，也可以基于抽象语语法制导翻译既可以基于语法分析树，也可以基于抽象语法树进行。法树进行。法树进行。法树进行。两种情况所采用的基本方法是一样的。像在语法分析树一两种情况所采用的基本方法是一样的。像在语法分析树一两种情况所采用的基本方法是一样的。像在语法分析树一两种情况所采用的基本方法是一样的。像在语法分析树一样，在抽象语法树的每个结点上都可带上一定的属性。样，在抽象语法树的每个结点上都可