《编译原理与技术》课件－第8章.ppt

1、编译原理与技术编译原理与技术第第8章章属性文法和语义分析属性文法和语义分析 编译原理与技术编译原理与技术2主要内容主要内容u语义分析概况语义分析概况 u属性与属性文法属性与属性文法u属性的计算属性的计算 u数据类型与类型检查数据类型与类型检查 编译原理与技术编译原理与技术38.1 语义分析概况语义分析概况 语义分析在编译程序中的位置语义分析在编译程序中的位置 程序的语义涉及两个方面，即数据结构的语程序的语义涉及两个方面，即数据结构的语义域控制结构的语义。义域控制结构的语义。数据结构的语义主要指域标识符相关联的数数据结构的语义主要指域标识符相关联的数据对象，也即量的含义。控制结构的语义是据对象，

2、也即量的含义。控制结构的语义是语言定义的。语言定义的。语法分析器语义分析器中间代码生成器语法树语法树单词记号中间代码编译原理与技术编译原理与技术48.1 语义分析概况语义分析概况量涉及类型与值，值在程序运行时刻确定，而类型则由程序的量涉及类型与值，值在程序运行时刻确定，而类型则由程序的说明部分来规定。说明部分来规定。例如，例如，int x,y;float z;char array100;把把x、y、z和和array分别与整型、整型、实型和字符数组型关联分别与整型、整型、实型和字符数组型关联起来，它们分别代表相应类型的数据对象。起来，它们分别代表相应类型的数据对象。不同类型的数据对象有不同的机器

3、内部表示，占用不同的存储不同类型的数据对象有不同的机器内部表示，占用不同的存储空间，有不同的取值范围，对它们所能进行的运算也不同。只空间，有不同的取值范围，对它们所能进行的运算也不同。只有相同类型、因而具有相同机内表示的数据对象，或符合特定有相同类型、因而具有相同机内表示的数据对象，或符合特定要求的数据对象才能进行相应的运算。要求的数据对象才能进行相应的运算。当考虑标识符的相关含义时还必须要考虑到作用域的问题。当考虑标识符的相关含义时还必须要考虑到作用域的问题。确定标识符所关联的类型、作用域等属性信息，进行类型正确确定标识符所关联的类型、作用域等属性信息，进行类型正确性的检查成为语义分析的一个

4、基本工作。性的检查成为语义分析的一个基本工作。编译原理与技术编译原理与技术58.1 语义分析概况语义分析概况例如，对于例如，对于C的的while循环语句：循环语句：while()；规定了首先计算规定了首先计算的值，如果为真的值，如果为真（或非（或非0）时，就执行）时，就执行；然后再计算然后再计算的值，并重复以上过程，的值，并重复以上过程，直到直到的值为假（或为的值为假（或为0），便结束循），便结束循环语句，执行环语句，执行while语句之后的语句。语句之后的语句。语义分析将分析各个语法结构的含义并做出语义分析将分析各个语法结构的含义并做出相应的语义处理。相应的语义处理。编译原理与技术编译原理与

5、技术68.1 语义分析概况语义分析概况u语义分析的基本功能语义分析的基本功能 确定类型确定类型 确定标识符所关联对象的数据类型。这部分工作有确定标识符所关联对象的数据类型。这部分工作有时由扫描器完成，扫描器将处理源程序的声明部分。时由扫描器完成，扫描器将处理源程序的声明部分。类型检查类型检查 按照语言的类型规则，对参加运算的运算分量进行按照语言的类型规则，对参加运算的运算分量进行类型检查，检查运算的合法性、运算分量类型的一致性（相容类型检查，检查运算的合法性、运算分量类型的一致性（相容性），对于不相容的运算对象，报告错误，必要时进行相应的性），对于不相容的运算对象，报告错误，必要时进行相应的类

6、型转换。类型转换。l例如，对于数组变量个函数变量的加法运算额出现，报告语义错例如，对于数组变量个函数变量的加法运算额出现，报告语义错误；对于整型与实型数据对象的加法，把它们转换成同一类型。误；对于整型与实型数据对象的加法，把它们转换成同一类型。控制流检查控制流检查 对于任何引起控制流离开一个结构的语句，程序对于任何引起控制流离开一个结构的语句，程序中必须由该控制转移可以转到的地方。中必须由该控制转移可以转到的地方。l例如，例如，C的的break语句引起控制离开最小包围的语句引起控制离开最小包围的while、for或或switch语句，如果这样的包围语句不存在，则是一个错误。语句，如果这样的包围

7、语句不存在，则是一个错误。编译原理与技术编译原理与技术78.1 语义分析概况语义分析概况u语义分析的基本功能语义分析的基本功能唯一性检查唯一性检查 有些场合，对象必须正好被定义一次。有些场合，对象必须正好被定义一次。例如，集合中的元素只能出现一次，对象类的名字不例如，集合中的元素只能出现一次，对象类的名字不能重复，分支语句的分情形常量必须区分能重复，分支语句的分情形常量必须区分.l在在Pascal语言中，标识符只能唯一第定义一次。语言中，标识符只能唯一第定义一次。关联名字检查关联名字检查 有时，同样的名字必须出现两次或更有时，同样的名字必须出现两次或更多次。多次。l例如，在例如，在C+语言中，

8、构造函数的名字必须和类型一致；在语言中，构造函数的名字必须和类型一致；在Ada语言中，循环或程序块可以有名字出现在其开始和结束，语言中，循环或程序块可以有名字出现在其开始和结束，编译程序必须检查两个地方的名字是否相同。编译程序必须检查两个地方的名字是否相同。识别含义识别含义 根据程序语言的形式或非形式语义规则，根据程序语言的形式或非形式语义规则，识别程序中各个构造成分组合到一起的含义，并做相识别程序中各个构造成分组合到一起的含义，并做相应的语义处理，应的语义处理，编译原理与技术编译原理与技术88.2 属性与属性文法属性与属性文法 u属性的引入属性的引入为了解释程序的语义、把程序翻译成可执行的代

9、码，需要对为了解释程序的语义、把程序翻译成可执行的代码，需要对文法符号引进一些表示程序语言结构性质的属性。文法符号引进一些表示程序语言结构性质的属性。例如变量数据类型、表达式值、存储地址、过程体代码以及例如变量数据类型、表达式值、存储地址、过程体代码以及数的有效数字个数等数的有效数字个数等.计算属性的值并把它和语言结构联系起来的过程称作属性的计算属性的值并把它和语言结构联系起来的过程称作属性的绑定。属性绑定发生在编译或运行过程的时刻叫做绑定时刻。绑定。属性绑定发生在编译或运行过程的时刻叫做绑定时刻。不同属性的绑定时刻不同，对于不同的语言，甚至同样的属不同属性的绑定时刻不同，对于不同的语言，甚至

10、同样的属性也有不同的绑定时刻。性也有不同的绑定时刻。在程序运行前绑定的属性称为静态的，只能在程序运行期间在程序运行前绑定的属性称为静态的，只能在程序运行期间才能绑定的属性是动态的。才能绑定的属性是动态的。编译原理与技术编译原理与技术98.2 属性与属性文法属性与属性文法u属性的引入属性的引入在静态类型语言诸如在静态类型语言诸如C和和Pascal中，变量或表达式的中，变量或表达式的数据类型是主要的编译时刻的属性，类型检查器就数据类型是主要的编译时刻的属性，类型检查器就是一个语义分析器，它计算语言实体的数据类型属是一个语义分析器，它计算语言实体的数据类型属性并验证这些类型符合语言的类型规则。性并验

11、证这些类型符合语言的类型规则。而而LISP或或Smalltalk中的数据类型是动态的，它们的中的数据类型是动态的，它们的编译必须产生计算类型的代码，然后在程序的运行编译必须产生计算类型的代码，然后在程序的运行过程中进行类型检查。过程中进行类型检查。表达式的值通常是动态的，编译只产生在程序运行表达式的值通常是动态的，编译只产生在程序运行期间计算表达式的值的代码。然而，有些表达式可期间计算表达式的值的代码。然而，有些表达式可能是常数，例如，能是常数，例如，3.12*5+10，语义分析器可以在编，语义分析器可以在编译的时候计算它们的值。译的时候计算它们的值。编译原理与技术编译原理与技术108.2 属

12、性与属性文法属性与属性文法u属性的引入属性的引入对于不同的语言或者变量自身的性质，变量的存储分对于不同的语言或者变量自身的性质，变量的存储分配可以是静态的、也可以是动态的。由于属性的计算配可以是静态的、也可以是动态的。由于属性的计算依赖与程序的运行环境，甚至时目标机的细节，所以依赖与程序的运行环境，甚至时目标机的细节，所以编译通常把属性的计算推迟到代码生成期间。编译通常把属性的计算推迟到代码生成期间。过程的目标码显然是静态属性。编译的代码产生器全过程的目标码显然是静态属性。编译的代码产生器全权负责这类属性的计算。权负责这类属性的计算。数的有效数字个数这个属性一般不在编译期间处理，数的有效数字个

13、数这个属性一般不在编译期间处理，它隐含在编译程序构造期间对这些数值实现的处理，它隐含在编译程序构造期间对这些数值实现的处理，通常是运行环境的一部分。然而，如果要正确地翻译通常是运行环境的一部分。然而，如果要正确地翻译常数，扫描器也需要知道允许的有效数字的个数。常数，扫描器也需要知道允许的有效数字的个数。编译原理与技术编译原理与技术118.2 属性与属性文法属性与属性文法u属性文法的定义属性文法的定义定义定义8.1 如果用如果用X表示一个文法符号，表示一个文法符号，a代表代表X的一的一个属性，那么，个属性，那么，X.a代表代表X的关联属性的关联属性a。定义定义8.2 对于一组属性对于一组属性a1

14、,a2,.,am和文法和文法G的每个产的每个产生式生式X0X1X2.Xn（X0是非终结符，其它的是非终结符，其它的Xi是是任意符号），意味着每个属性任意符号），意味着每个属性Xi.aj的值都和产生的值都和产生式中其它属性有关系，每个关系可以表示成属性等式中其它属性有关系，每个关系可以表示成属性等式或语义规则的形式：式或语义规则的形式：Xi.aj i(a1,a2,.,am)定义定义8.3 属性文法就是对于一组属性属性文法就是对于一组属性a1,a2,.,am和文和文法法G的每个产生式的所有的语义规则，其中文法的每个产生式的所有的语义规则，其中文法G称为基础文法。称为基础文法。编译原理与技术编译原理

15、与技术128.2 属性与属性文法属性与属性文法u属性文法通常写成下列表格形式：属性文法通常写成下列表格形式：语法产生式语法产生式语义规则语义规则X 关联的属性等式关联的属性等式编译原理与技术编译原理与技术138.2 属性与属性文法属性与属性文法数的最重要的属性就是它的值，命名为数的最重要的属性就是它的值，命名为val。每个数字都有一个值，可以直接从它表。每个数字都有一个值，可以直接从它表示的实际数字得到。所以，文法规则示的实际数字得到。所以，文法规则 digit 0意味着在这个情况下意味着在这个情况下digit有有0值，可值，可以表示成属性等式以表示成属性等式digit.val:=0，并把它和

16、文法规则，并把它和文法规则 digit 0关联在一起。关联在一起。如果运用规则如果运用规则number digit得到了数，那么，这个数就值包含一个数字，其值就得到了数，那么，这个数就值包含一个数字，其值就等于这个数字的值，它的属性等式可以表示成等于这个数字的值，它的属性等式可以表示成number.val=digit.val。如果数从文法规则如果数从文法规则number number digit得到，那么我们必须规则左边符号的值得到，那么我们必须规则左边符号的值和文法规则右边符号的值之间的关系。和文法规则右边符号的值之间的关系。注意，文法规则两边出现的注意，文法规则两边出现的number完全不

17、同（用下标表示），这是由于它们具有不完全不同（用下标表示），这是由于它们具有不同的值。同的值。考虑数考虑数83的最右推导：的最右推导：number number digit digit digit digit3 83在第一步使用的文法规则在第一步使用的文法规则number1 number2 digit，其中，其中number2表示数字表示数字8，而而digit对应对应3，它们的值分别是，它们的值分别是8和和3。为了得到。为了得到number1的值的值83，必须使用的下列，必须使用的下列计算：计算：838*10+3。这对应了属性等式：。这对应了属性等式：number1.val:=number2.

18、val 10+digit.val例例8.1 考虑下列无符号数的简单语法G8.1number number digit|digitdigit 0|1|2|3|4|5|6|7|8|9编译原理与技术编译原理与技术148.2 属性与属性文法属性与属性文法表8.2 例8.1的属性文法文法规则语义规则number1 number2 digitnumber1.val:=number2.val 10+digit.valnumber digitnumber.val:=digit.valdigit 0digit.val:=0digit 1digit.val:=1.digit 8digit.val:=8digit

19、9digit.val:=9number(val=81*10+3=813)number(val=8*10+1=81)digit(val=3)digit(val=1)digit(val=8)digit(val=8)83 1 图8.1 数813带属性计算的的语法分析树 编译原理与技术编译原理与技术158.2 属性与属性文法属性与属性文法u例例8.2 考虑的简单算术表达式考虑的简单算术表达式的语法的语法G5.1：E E+T|E-T|TT T F|FF (E)|num文法规则语义规则E1 E2+TE1.val:=E2.val+T.valE1 E2-TE1.val:=E2.val T.valE TE.va

20、l:=T.valT1 T2 FT1.val:=T2.val*F.valT FT.val:=F.valF (E)F.val:=E.valF numF.val:=num.val主要属性就是所有非终结符的数值，记做主要属性就是所有非终结符的数值，记做val。这些属性等式描述了表达式的语法关系以及要执行的算术运算的语义。这些属性等式描述了表达式的语法关系以及要执行的算术运算的语义。注意，这个文法没有把注意，这个文法没有把num当作非终结符，也就没有当作非终结符，也就没有num.val在等号在等号左边的属性等式，所以，使用该属性文法时左边的属性等式，所以，使用该属性文法时num.val的值必须在语义的值

21、必须在语义分析前（通常由词法分析器）得到。分析前（通常由词法分析器）得到。如果想明显地在文法中计算如果想明显地在文法中计算num的属性值，可以增加产生式规则，并的属性值，可以增加产生式规则，并对这个属性文法增加如同例子对这个属性文法增加如同例子8.1一样的属性等式。一样的属性等式。编译原理与技术编译原理与技术168.2 属性与属性文法属性与属性文法 (52 3)30的计算语义的计算语义表示在如图表示在如图8.2的语法的语法分析树中。分析树中。自底向上地遍历树就可以自底向上地遍历树就可以得到表达式的值。得到表达式的值。E(val=1470)E(val=523=49)num(val=30)T(va

22、l=1)E(val=52)E(val=49*30=1470)F(val=30)T(val=49)()F(val=3)num(val=3)F(val=53)num(val=52)T(val=52)编译原理与技术编译原理与技术178.2 属性与属性文法属性与属性文法例例8.3:考虑下面这个表示变量声明的语法G8.2：decl type var-listtype int|floatvar-list id,var-list|id我们希望为声明中标识符代表的每个变量定义一个数据类型的属性，并且构造属性等式来表达数据类型属性与声明类型的关系。定义的dtype表示数据类型属性。属性dtype的取值范围是集合

23、integer,real，对应了符号int和float。非终结符type的属性dtype由其所代表的符号给定。根据语法规则decl type var-list，这个属性dtype对应了变量表var-list的dtype。变量表中的每个标识符id都有相同的属性dtype。注意，非终结符decl没有属性定义。事实上，并非每个文法符号都需要定义属性和属性等式。文法规则语义规则decl type var-listvar-list.dtype:=type.dtypetype inttype.dtype:=integertype floattype.dtype:=realvar-list1 id,var-

24、list2id.type:=var-list1.dtypevar-list2.type:=var-list1.dtypevar-list idid.type:=var-list.dtype编译原理与技术编译原理与技术188.2 属性与属性文法属性与属性文法例例8.4 考虑下面这个对文法G8.1做了改动的文法G8.3：based-num num basecharbasechar o|dnum num digit|digitdigit 0|1|2|3|4|5|6|7|8|9定义的数可以是8进制（末尾是记号o）、也以是10进制（末尾是记号d）。在这中情况下，num和digit需要一个新的表示底数的属

25、性base，用于计算值属性val。文法规则语义规则based-num num basecharbased-num.val:=num.valnum.base:=basechar.basebasechar obasechar.base:=8basechar dbasechar.base:=10num1 num2 digitnum1.val:=if digit.val=error or num2.val=errorthen errorelse num2.val num1.base+digit.valnum2.base:=num1.basedigit.base:=num1.basenum digitn

26、um.val:=digit.valdigit 0digit.val:=0digit 1digit.val:=1.digit 7digit.val:=7digit 8digit.val:=if digit.base=8 then error else 8digit 9digit.val:=if digit.base=8 then error else 9编译原理与技术编译原理与技术198.2 属性与属性文法属性与属性文法u这个属性文法出现了两个新的特性这个属性文法出现了两个新的特性 这个文法没有排除八进制数时错误的数字这个文法没有排除八进制数时错误的数字8和和9。例如，按照语。例如，按照语法规则

27、法规则298o是个正确的符号串，但是不能赋予任何值，这就需是个正确的符号串，但是不能赋予任何值，这就需要引进一个新值要引进一个新值error，表示出错。，表示出错。属性文法必须描述对于后缀属性文法必须描述对于后缀o，一旦符号串包含了数字，一旦符号串包含了数字8或或9就出就出错这中事实。它的最简单的实现方法是在属性等式的函数中使错这中事实。它的最简单的实现方法是在属性等式的函数中使用一个用一个if-then-else表达式或类似表达式或类似C中的条件表达式运算中的条件表达式运算“?:”。例如，对应文法例如，对应文法num num digit的属性等式的属性等式num1.val:=if digit

28、.val=error or num2.val=errorthen errorelse num2.val num1.base+digit.val表达了如下的情况：如果表达了如下的情况：如果digit.val或或num2.val其中的一个是其中的一个是error，那么，那么num1.val也必须是也必须是error；否则，；否则，num1.val的值由公的值由公式式num2.val num1.base+digit.val给出。给出。编译原理与技术编译原理与技术208.2 属性与属性文法属性与属性文法u属性文法的形式化定义属性文法的形式化定义一个属性文法一个属性文法AG是一个三元组是一个三元组，其中

29、，其中G是一个上下文无关文法，称作基础文法，当同一个是一个上下文无关文法，称作基础文法，当同一个符号在产生式中多次出现时要用序号加以区别；符号在产生式中多次出现时要用序号加以区别；A是有限的属性集合，是有限的属性集合，G中的符号中的符号X关联于属性集关联于属性集A(X)，X的一个属性的一个属性a记做记做X.a；R是有限的属性等式的集合。是有限的属性等式的集合。对于一组属性对于一组属性a1,a2,.,am和文法和文法G的每个产生式的每个产生式X0X1X2.Xn（X0是非终结符，其它的是非终结符，其它的Xi是任意符是任意符号），属性等式或语义规则的形式：号），属性等式或语义规则的形式：Xi.aj

30、i(a1,a2,.,am)。i一般是表达式，可以函数甚至是子一般是表达式，可以函数甚至是子程序。程序。编译原理与技术编译原理与技术218.2 属性与属性文法属性与属性文法u属性文法的简化与扩展属性文法的简化与扩展可以在属性等式中使用这些的元语言尽量地可以在属性等式中使用这些的元语言尽量地接近实际的程序语言，以便把属性等式转换接近实际的程序语言，以便把属性等式转换成语义分析器中的工作代码成语义分析器中的工作代码。在属性等式中应用在定义好的函数在属性等式中应用在定义好的函数。使用二义性的更加简单的基础文法使用二义性的更加简单的基础文法。编译原理与技术编译原理与技术228.2 属性与属性文法属性与属

31、性文法u抽象语法树抽象语法树在参考文献中，通常把抽象语法树在参考文献中，通常把抽象语法树AST（Abstract Syntax Tree）简称为语法树，而把语法分析树）简称为语法树，而把语法分析树（parsing tree）简称为分析树。）简称为分析树。在语法树中，算符和关键字不是作为叶结点，而是作在语法树中，算符和关键字不是作为叶结点，而是作为内部结点，它们对应分析树中的这些叶结点的父结为内部结点，它们对应分析树中的这些叶结点的父结点。可按下面的步骤从分析树构造出相应的语法树：点。可按下面的步骤从分析树构造出相应的语法树：l去掉与单非产生式相关的子树，并上提相关分支上的终结符去掉与单非产生式

32、相关的子树，并上提相关分支上的终结符结点；结点；l对于直接包含运算符的多个子树，用算符取代其父结点；对于直接包含运算符的多个子树，用算符取代其父结点；l去掉括号并上提算符，让它代替父结点。去掉括号并上提算符，让它代替父结点。编译原理与技术编译原理与技术238.2 属性与属性文法属性与属性文法对于产生式对于产生式S if E then S1 else S2，可以看成是一个三元算符，可以看成是一个三元算符的式子，它的语法树如下图的式子，它的语法树如下图表达式表达式8+1*3的语法树示意在下图的语法树示意在下图S1if-then-elseS2B3+*81编译原理与技术编译原理与技术248.2 属性与

33、属性文法属性与属性文法例例8.5 对于例对于例8.2中的算术表达式的文法中的算术表达式的文法G5.1，可以用表，可以用表8.7的属性文法定义表达式的属性文法定义表达式的抽象语法树。的抽象语法树。其中其中number.lexval指出它是由扫描器构造出来的；指出它是由扫描器构造出来的；辅助函数辅助函数mknode(op,left,right)把输入的三个参数构造成一个树结点，标号是第一把输入的三个参数构造成一个树结点，标号是第一个参数，两个域个参数，两个域left和和right分别指向左子树和右子树；分别指向左子树和右子树；mkleaf(num,num.lexval)构造一个标记为构造一个标记为

34、num的叶结点，其中的一个域代表具有参的叶结点，其中的一个域代表具有参数值的数。数值的数。表表8.7 构造算术表达式抽象语法树的属性文法构造算术表达式抽象语法树的属性文法文法规则语义规则E1 E2+TE1.tree:=mknode(+,E2.tree,T.tree)E1 E2-TE1.tree:=mknode(,E2.tree,T.tree)E TE.tree:=T.treeT1 T2 FT1.tree:=mknode(*,T2.tree,F.tree)T FT.tree:=F.treeF (E)F.tree:=E.treeF numF.tree:=mkleaf(num.lexval)编译原理

35、与技术编译原理与技术258.2 属性与属性文法属性与属性文法图8.6给出了表达式(523)30根据表8.6的规则构造的抽象语法树，同时也画出了相应的分析树（虚线）。num30 num 52num 3E treeE tree E treeE tree T treenumnumnum *E treeF tree*编译原理与技术编译原理与技术268.2 属性与属性文法属性与属性文法利用属性文法说明属性的一个中心问题是：利用属性文法说明属性的一个中心问题是：如何确保一个特定的属性文法一致性和完整如何确保一个特定的属性文法一致性和完整性，即唯一地定义可给定的属性？性，即唯一地定义可给定的属性？对于这个问

36、题我们目前无法给出简单的答案。这个问对于这个问题我们目前无法给出简单的答案。这个问题类似于确定一个文法是否是二义的。题类似于确定一个文法是否是二义的。在实践中，我们使用的语法分析算法决定一个文法的在实践中，我们使用的语法分析算法决定一个文法的适应性，类似的情况出现在属性文法：计算属性的算适应性，类似的情况出现在属性文法：计算属性的算法决定一个属性文法的一致性和完整性。法决定一个属性文法的一致性和完整性。编译原理与技术编译原理与技术278.3 属性的计算属性的计算 u依赖图和计算顺序名字的访问依赖图和计算顺序名字的访问前面描述的属性等式前面描述的属性等式Xi.aj i(a1,a2,.,am)可以

37、看作是把等号右部的函数表达式的值赋给等号左部的属可以看作是把等号右部的函数表达式的值赋给等号左部的属性性Xi.aj。为了可以赋值，出现在右部函数中的所有属性的值。为了可以赋值，出现在右部函数中的所有属性的值必须已经存在。必须已经存在。实现属性文法的算法必须为属性的计算找到一个合适顺序，实现属性文法的算法必须为属性的计算找到一个合适顺序，确保在进行计算的时候每个需要的属性值都可以得到。确保在进行计算的时候每个需要的属性值都可以得到。属性等式本身已经蕴含了计算属性顺序的约束，属性计算的属性等式本身已经蕴含了计算属性顺序的约束，属性计算的首要任务是利用有向图把这些隐含的顺序约束明确地表示出首要任务是

38、利用有向图把这些隐含的顺序约束明确地表示出来，这个有向图就叫做属性依赖图。图的结点标号是一个属来，这个有向图就叫做属性依赖图。图的结点标号是一个属性，如果属性性，如果属性a的计算依赖于属性的计算依赖于属性b，那么，存在从结点，那么，存在从结点a到结到结点点b的一条有向边。的一条有向边。编译原理与技术编译原理与技术288.3 属性的计算属性的计算语法产生式语法产生式var-list id,var-list有两条关联的属性等式：有两条关联的属性等式：id.type:=var-list1.dtype var-list2.type:=var-list1.dtype对应这个候选产生式的依赖图是对应这个候

39、选产生式的依赖图是语法规则语法规则var-list id和和decl type var-list的依赖图分别的依赖图分别var-list.dtypevar-list.dtypid.dtypevar-list.dtype id.dtypetype.dtypevar-list.dtype编译原理与技术编译原理与技术298.3 属性的计算属性的计算如果依赖图和分析树同时画出，通常把树结如果依赖图和分析树同时画出，通常把树结点标记的属性省去，而把它写在结点的旁边点标记的属性省去，而把它写在结点的旁边比如，串比如，串float x,y分析树的依赖图如图分析树的依赖图如图8.7所示所示decltype d

40、type var-listid(x),var-listfloatid(y)dtypedtypedtypedtype编译原理与技术编译原理与技术308.3 属性的计算属性的计算例例8.7 下面四个产生式based-num num basecharnum num digitnum digitdigit 9和串813o构造依赖图。(1)为based-num num basechar构造依赖图：valvalbasebasebasecharnumbased-num(2)为语法产生式num num digit构造对应的依赖图 valvalbasevaldigitnumnumbasebase这个图表达了下面

41、三个属性等式的依赖关系：num1.val:=if digit.val=error or num2.val=error then error else num2.val num1.base+digit.valnum2.base:=num1.basedigit.base:=num1.base编译原理与技术编译原理与技术318.3 属性的计算属性的计算(3)语法规则num digit和digit 1的依赖图分别如下 basebasebasenumdigit val valvaldigit 9(4)为数字串813o构造的分析树的依赖图显示如下 valvalbasebasebasecharnum bas

42、ed-numvalbasevaldigitnumbasevalbasevaldigitnumbaseo3valdigitbase81编译原理与技术编译原理与技术328.3 属性的计算属性的计算定义定义8.5 对于包含了对于包含了k结点的有向图，结点的拓扑排序结点的有向图，结点的拓扑排序m1,m2,.,mk使得任何一条边使得任何一条边在这个序列中都是在这个序列中都是mi在在mj之前出现之前出现例例8.8 图图8.8的依赖图是一个有向无环图。图的依赖图是一个有向无环图。图8.9只画出了依赖图，只画出了依赖图，按照结点编号的顺序得到的结点排序就是这个依赖图的一个拓按照结点编号的顺序得到的结点排序就是

43、这个依赖图的一个拓扑排序。另外一个拓扑排序是下列结点编号的序列：扑排序。另外一个拓扑排序是下列结点编号的序列：12，6，9，1，2，11，3，8，4，5，7，10，13，14valvalbasebase113 14valbaseval1210basevalbaseval97basevalbase23456811编译原理与技术编译原理与技术338.3 属性的计算属性的计算使用依赖图的拓扑排序计算属性值的一个关键问题是，如何找使用依赖图的拓扑排序计算属性值的一个关键问题是，如何找到图的根的属性值。一个图的根是没有前驱的结点。到图的根的属性值。一个图的根是没有前驱的结点。例如，图例如，图8.9中编号

44、为中编号为1、6、9和和12的结点都没有前驱，是图的的结点都没有前驱，是图的根。这些结点上的属性值独立于其它任何属性，必须利用可以根。这些结点上的属性值独立于其它任何属性，必须利用可以直接得到的信息求值。直接得到的信息求值。而这些信息通常就是对应分析树中结点子女的终结符串的形式。而这些信息通常就是对应分析树中结点子女的终结符串的形式。例如，图例如，图8.9中结点中结点6的属性的属性val依赖于于符号依赖于于符号8，它是属性，它是属性val对对应的结点应的结点digit的子女（参见图的子女（参见图8.8）。所以，结点）。所以，结点6的属性值是的属性值是8。所有这种根的属性值都必须在其它任何属性求

45、值之前计算出来。所有这种根的属性值都必须在其它任何属性求值之前计算出来。这些计算通常由扫描器或语法分析器完成。这些计算通常由扫描器或语法分析器完成。编译原理与技术编译原理与技术348.3 属性的计算属性的计算u综合属性和综合属性和S-属性文法属性文法定义定义8.6 一个属性是综合属性，如果它的所有依赖点都是从分一个属性是综合属性，如果它的所有依赖点都是从分析树的子女到父母结点。换句话，属性析树的子女到父母结点。换句话，属性a是综合属性，如果对于是综合属性，如果对于文法文法AX1X2.Xn，a在左边的与在左边的与a关联的属性等式只有下列形关联的属性等式只有下列形式：式：A.a(X1.a1,.,X

46、1.ak,.,Xn.a1,.,Xn.ak)其中其中a1,.ak是所有的属性。其它属性叫做继承属性。所有属性是所有的属性。其它属性叫做继承属性。所有属性都是综合属性的属性文法称作都是综合属性的属性文法称作S-属性文法属性文法。按照定义可知，全部非终结符的属性都是综合属性；同一产生按照定义可知，全部非终结符的属性都是综合属性；同一产生式中相同符号的个综合属性之间没有依赖关系；如果式中相同符号的个综合属性之间没有依赖关系；如果b使某个产使某个产生式中符号生式中符号X的继承属性，那么属性的继承属性，那么属性b的值仅仅依赖于该产生式的值仅仅依赖于该产生式右部位于符号右部位于符号X的左边的符号的属性。的左

47、边的符号的属性。编译原理与技术编译原理与技术358.3 属性的计算属性的计算S-属性文法的属性计算可以用自底向上或者属性文法的属性计算可以用自底向上或者后序遍历（深度优先）分析树后序遍历（深度优先）分析树/语法树的方式语法树的方式一趟完成。这可以表达成下列的递归后序遍一趟完成。这可以表达成下列的递归后序遍历属性求值的算法：历属性求值的算法：procedure postEvaluation(T:treenode)beginfor T中的每个子女结点中的每个子女结点C dopostEvaluation(C);计算计算T的所有综合属性；的所有综合属性；end postEvaluation;编译原理与

48、技术编译原理与技术368.3 属性的计算属性的计算例例8.9 可以用C语言实现构造表达式的语法树。首先定义语法数的数据结构typedef enumPlus,Minus,Times OPKind;typedef enumOPKind,COnstKind ExpKind;typedef struct treenodeExpKind kind;OPKind op;struct treenode*lchild,*rchild;int val;Treenode;typedef Treenode*SyntaxTree;然后，把算法postEvaluation翻译成下列C代码。void postEval(S

49、yntaxTree tree)int temp;if(tree kind=OPKind)postEval(tree lchild);postEval(tree rchild);switch(tree op)case Plus:tree val=tree lchildval+tree rchildval;case Minus:tree val=tree lchildval tree rchildval;case Times:tree val=tree lchildval*tree rchildval;编译原理与技术编译原理与技术378.3 属性的计算属性的计算单纯计算继承属性可以通过前序遍历，或

50、者前序遍历单纯计算继承属性可以通过前序遍历，或者前序遍历和中序遍历分析树来完成，如下列算法所示：和中序遍历分析树来完成，如下列算法所示：procedure preEval(T:treenode)beginfor T中的每个子女结点中的每个子女结点C do计算计算T的所有继承属性；的所有继承属性；preEval(C);end for;end preEval;由于继承属性可能依赖于子女的属性，与综合属性求由于继承属性可能依赖于子女的属性，与综合属性求值不同，在计算继承属性的时候，子女继承属性的计值不同，在计算继承属性的时候，子女继承属性的计算顺序非常重要。上述代码中对于算顺序非常重要。上述代码中对