China-pub.Com 下载 第6章语义分析 本章要点 ·属性和属性文法 ·数据类型和类型检查 ·属性计算算法 ·TNY语言的语义分析 ·符号表 本章要研究的编译程序阶段是计算编译过程所需的附加信息。这个阶段称作语义分析， 因为它包括计算上下文无关文法和标准分析算法以外的信息，因此，它不被看成是语法⊙。信 息的计算也与被翻译过程的最终含义或语义密切相关。因为编译器完成的分析是静态（它在执 行之前发生)定义的，这样，语义分析也可称作静态语义分析(static semantic analysis)。在 个典型的静态类型的语言（如℃语言）中，语义分析包括构造符号表、记录声明中建立的名字的 含义、在表达式和语句中进行类型推断和类型检查以及在语言的类型规则作用域内判断它们 的正确性。 语义分析可以分为两类。第1类是程序的分析，要求根据编程语言的规则建立其正确性， 并保证其正确执行。对于不同的语言来说，语言定义所要求的这一类分析的总量变化很大。在 LISP和Smalltalki这类动态制导的语言中，可能完全没有静态语义分析：而在Ada这类语言中就 有很强的需求，程序必须提交执行。其他的语言介于这两种极端情况之间（例如Pascal语言，不 像Ada和C对静态语义分析的要求那样严格，也不像LISP那样完全设有要求)。 语义分析的第2类是由编译程序执行的分析，用以提高翻译程序执行的效率。这一类分析 通常包括对“最优化”或代码改进技术的讨论。第8章“代码生成”中将研究一些这样的方法， 而本章则集中讨论语言定义对正确性要求的一般分析。读者应该注意到，这里研究的技术对两 类情况都适用。这两类分析也不是相互排斥的，因为与没有正确性要求的语言相比，如静态类 型检查这样的正确性要求能使编译程序产生更加有效的代码。另外，值得注意的是，这里讨论 的正确性要求永远不能建立程序的完全正确性，正确性仅仅是部分的。但这样的要求仍然是有 用的，可以给编程人员提供一些信息，提高程序的安全性和有效性。 静态语义分析包括执行分析的描述(description)和使用合适的算法对分析的实现 (implementation)。在这里，它和词法及语法分析相类似。例如，在语法分析中，我们使用 Backus-.Naus范式(BNF)中的上下文无关文法描述语法结构，并用各种自顶向下和自底向上的分 析算法实现语法结构。在语义分析中，情形不是那么清晰，其部分原因是没有用标准的方法 (如BNF)来说明语言的静态语义：另一个原因是对于各种语言，静态语义分析的种类和总量的 变化范围很大。编译程序编写者过去常用的且实现得很好的一种描述语义分析方法是：确定语 言实体的属性(attribute))或特性，它们必须进行计算并写成属性等式(attribute equation)或语义规 则(semantic rule),并描述这些属性的计算如何与语言的文法规则相关。这样的一组属性和等 式称作属性文法(attribute grammar)。属性文法对遵循语法制导语义(syntax--directed semantic)原 日这一点在第3章的3.6.3节进行了较为详细的时论
下载 第6章 语 义 分 析 本章要点 • 属性和属性文法 • 数据类型和类型检查 • 属性计算算法 • TINY语言的语义分析 • 符号表 本章要研究的编译程序阶段是计算编译过程所需的附加信息。这个阶段称作语义分析， 因为它包括计算上下文无关文法和标准分析算法以外的信息，因此，它不被看成是语法 。信 息的计算也与被翻译过程的最终含义或语义密切相关。因为编译器完成的分析是静态 (它在执 行之前发生)定义的，这样，语义分析也可称作静态语义分析 (static semantic analysis)。在一 个典型的静态类型的语言 (如C语言)中，语义分析包括构造符号表、记录声明中建立的名字的 含义、在表达式和语句中进行类型推断和类型检查以及在语言的类型规则作用域内判断它们 的正确性。 语义分析可以分为两类。第 1类是程序的分析，要求根据编程语言的规则建立其正确性， 并保证其正确执行。对于不同的语言来说，语言定义所要求的这一类分析的总量变化很大。在 L I S P和S m a l l t a l k这类动态制导的语言中，可能完全没有静态语义分析；而在 A d a这类语言中就 有很强的需求，程序必须提交执行。其他的语言介于这两种极端情况之间 (例如P a s c a l语言，不 像A d a和C对静态语义分析的要求那样严格，也不像L I S P那样完全没有要求)。 语义分析的第2类是由编译程序执行的分析，用以提高翻译程序执行的效率。这一类分析 通常包括对“最优化”或代码改进技术的讨论。第 8章“代码生成”中将研究一些这样的方法， 而本章则集中讨论语言定义对正确性要求的一般分析。读者应该注意到，这里研究的技术对两 类情况都适用。这两类分析也不是相互排斥的，因为与没有正确性要求的语言相比，如静态类 型检查这样的正确性要求能使编译程序产生更加有效的代码。另外，值得注意的是，这里讨论 的正确性要求永远不能建立程序的完全正确性，正确性仅仅是部分的。但这样的要求仍然是有 用的，可以给编程人员提供一些信息，提高程序的安全性和有效性。 静态语义分析包括执行分析的描述 ( d e s c r i p t i o n )和使用合适的算法对分析的实现 ( i m p l e m e n t a t i o n )。在这里，它和词法及语法分析相类似。例如，在语法分析中，我们使用 B a c k u s - N a u s范式( B N F )中的上下文无关文法描述语法结构，并用各种自顶向下和自底向上的分 析算法实现语法结构。在语义分析中，情形不是那么清晰，其部分原因是没有用标准的方法 (如B N F )来说明语言的静态语义；另一个原因是对于各种语言，静态语义分析的种类和总量的 变化范围很大。编译程序编写者过去常用的且实现得很好的一种描述语义分析方法是：确定语 言实体的属性( a t t r i b u t e )或特性，它们必须进行计算并写成属性等式(attribute equation)或语义规 则(semantic rule)，并描述这些属性的计算如何与语言的文法规则相关。这样的一组属性和等 式称作属性文法(attribute grammar)。属性文法对遵循语法制导语义(syntax-directed semantic)原 这一点在第3章的3 . 6 . 3节进行了较为详细的讨论
China-pub.com 第6章语义分析 199 下载 理的语言最有用，它表明程序的语义内容与它的语法密切相关。所有的现代语言都有这个特性。 然而，编译程序的编写者通常必须根据语言手册手工构造属性文法，因为语言设计者很少为之 提供。更糟糕的是，由于坚持语言清晰的语法结构，属性文法的构造会有不必要的复杂性。语 义计算表达式的一种更好标准是抽象语法，就像抽象语法树表示的那样。但是抽象语法树的说 明通常也由语言设计者留给了编译程序编写者。 语义分析实现的算法也不像语法分析算法那样能洁晰地表达。这部分原因也是因为在考虑 语义分析说明时，出现了刚刚提及的同样的问题。还有另外一个问题，它是由编译过程中分析 的时间选择引起的。如果语义分析可以推迟到所有的语法分析（以及抽象语法树的构造）完成之 后进行，那么实现语义分析的任务就相当容易，其本质上由指定对语法树遍历的一个顺序组成， 同时在遍历中每次遇到节点时进行计算。这就意味着编译程序必须是多遍的。另 一方面，如乐 必须要求绵译程序在一遍中完成所有的操作（包括代码生成），那么语义分析的实现就更加会变 成寻找计算语义信息的正确顺序和方法的特别的过程（假定这样的顺序实际存在）。当然，现代 的惯例越来越允许编译程序编写者使用多遍扫描简化语义分析和代码生成的过程。 尽管有点扰乱语义分析的状态，研究属性文法和规范发布仍是特别有用的，因为这能从写 出更加清晰、简练、不易出错的语义分析代码中得到补偿，同时代码也更加易懂 因此，本章从研究属性和属性文法开始。接下来是通过属性文法说明实现计算的技术，包 括推断与树的遍历相连的计算顺序。随后的两节集中于语义分析的两个主要方面：符号表和类 型检查。最后一节讲述前一章介绍的TNY编程语言的语义分析程序。 与第5章不同，本章没有包含对语义分析程序生成器(semantic analyzer generator)或构造语 义分析程序的通用工具的描述。尽管已经构造了许多这样的工具，但没有 个能得到广泛的使 用且能用于Lex或Yacc。在本章最后的“注意与参考”一节中，我们提及了几个这样的工具， 并为感兴趣的读者提供了参考文款。 6.1属性和属性文法 届性(attribute)是编程语言结构的任意特性。属性在其包含的信息和复杂性等方面变化很大， 特别是当它们能确定时翻译/执行过程的时间。属性的典型例子有： ·变量的数据类型。 ·表达式的值。 ·存储器中变量的位置 ·程序的目标代码。 ·数的有效位数。 可以在复杂的处理（甚至编译程序的构造）之前确定属性。例如，一个数的有效位数可以根 据语言的定义确定（或者至少给出一个最小值）。属性也可以在程序执行期间才确定，如（非常 数)表达式的值，或者动态分配的数据结构的位置。属性的计算及将计算值与正在讨论的语言 结构联系的过程称作属性的联编(binding)。联编属性发生时编译/快行过程的时间称作联编时间 (binding time)。不同的属性变化，甚至不同语言的相同属性都可能有完全不同的联编时间。在 执行之前联编的属性称作静态的(static),而只在执行期间联编的属性是动态的(dynamic)。对于 编译程序编写者而言，当然对那些在翻译时联编的动态属性感兴趣。 考虑先前给出的属性表的示例。我们时论表中每个属性在编译时的联编时间和重要性 ·在如C或Pascali这样的静态类型的语言中，变量或表达式的数据类型是一个重要的编译时 属性。类型检查器(type checker)是一个语义分析程序，它计算定义数据类型的所有语言
理的语言最有用，它表明程序的语义内容与它的语法密切相关。所有的现代语言都有这个特性。 然而，编译程序的编写者通常必须根据语言手册手工构造属性文法，因为语言设计者很少为之 提供。更糟糕的是，由于坚持语言清晰的语法结构，属性文法的构造会有不必要的复杂性。语 义计算表达式的一种更好标准是抽象语法，就像抽象语法树表示的那样。但是抽象语法树的说 明通常也由语言设计者留给了编译程序编写者。 语义分析实现的算法也不像语法分析算法那样能清晰地表达。这部分原因也是因为在考虑 语义分析说明时，出现了刚刚提及的同样的问题。还有另外一个问题，它是由编译过程中分析 的时间选择引起的。如果语义分析可以推迟到所有的语法分析 (以及抽象语法树的构造)完成之 后进行，那么实现语义分析的任务就相当容易，其本质上由指定对语法树遍历的一个顺序组成， 同时在遍历中每次遇到节点时进行计算。这就意味着编译程序必须是多遍的。另一方面，如果 必须要求编译程序在一遍中完成所有的操作 (包括代码生成)，那么语义分析的实现就更加会变 成寻找计算语义信息的正确顺序和方法的特别的过程 (假定这样的顺序实际存在 )。当然，现代 的惯例越来越允许编译程序编写者使用多遍扫描简化语义分析和代码生成的过程。 尽管有点扰乱语义分析的状态，研究属性文法和规范发布仍是特别有用的，因为这能从写 出更加清晰、简练、不易出错的语义分析代码中得到补偿，同时代码也更加易懂。 因此，本章从研究属性和属性文法开始。接下来是通过属性文法说明实现计算的技术，包 括推断与树的遍历相连的计算顺序。随后的两节集中于语义分析的两个主要方面：符号表和类 型检查。最后一节讲述前一章介绍的T I N Y编程语言的语义分析程序。 与第5章不同，本章没有包含对语义分析程序生成器 (semantic analyzer generator)或构造语 义分析程序的通用工具的描述。尽管已经构造了许多这样的工具，但没有一个能得到广泛的使 用且能用于L e x或Ya c c。在本章最后的“注意与参考”一节中，我们提及了几个这样的工具， 并为感兴趣的读者提供了参考文献。 6.1 属性和属性文法 属性( a t t r i b u t e )是编程语言结构的任意特性。属性在其包含的信息和复杂性等方面变化很大， 特别是当它们能确定时翻译/执行过程的时间。属性的典型例子有： • 变量的数据类型。 • 表达式的值。 • 存储器中变量的位置。 • 程序的目标代码。 • 数的有效位数。 可以在复杂的处理(甚至编译程序的构造)之前确定属性。例如，一个数的有效位数可以根 据语言的定义确定 (或者至少给出一个最小值 )。属性也可以在程序执行期间才确定，如 (非常 数)表达式的值，或者动态分配的数据结构的位置。属性的计算及将计算值与正在讨论的语言 结构联系的过程称作属性的联编( b i n d i n g )。联编属性发生时编译/执行过程的时间称作联编时间 (binding time)。不同的属性变化，甚至不同语言的相同属性都可能有完全不同的联编时间。在 执行之前联编的属性称作静态的( s t a t i c )，而只在执行期间联编的属性是动态的( d y n a m i c )。对于 编译程序编写者而言，当然对那些在翻译时联编的动态属性感兴趣。 考虑先前给出的属性表的示例。我们讨论表中每个属性在编译时的联编时间和重要性。 • 在如C或P a s c a l这样的静态类型的语言中，变量或表达式的数据类型是一个重要的编译时 属性。类型检查器(type checker)是一个语义分析程序，它计算定义数据类型的所有语言 第 6章 语 义 分 析 1 9 9 下载
200 编译原理及实践 China-pub.co 下载 实体的数据类型属性，并验证这些类型符合语言的类型规则。在如C或Pascali这样的语言 中，类型检查是语义分析的一个重要部分。而在LISP这样的语言中，数据类型是动态的， LSP编译程序必须生成代码来计算类型，并在程序执行期间完成类型检查。 ·表达式的值通常是动态的，编译程序要在执行时生成代码来计算这些值。然而事实上 一些表达式可能是常量（例如3+4*5），语义分析程序可以选择在编译时求出它们的值（这 FORTRAN77中所有的变量都是静态分配的，而在LISP中所有的变量是动态分配的。C和 Pascali语言混合了静态和动态的两种变量分配。因为编译程序与变量分配联系的计算依 赖于运行时环境，有时还依赖于具体的目标机器，所以这些计算会一直推迟到代码生成 (第7章将更详细地探讨这一问题)。 ·程序的目标代码无疑是一个静态属性。编译程序的代码生成器专门用于这个属性的计算。 ·数的有效位数在编译期间是一个不被明确探讨的属性。编译程序编写者实现值的表示是 不言而喻的，这通常被视为运行时环境的一部分，这将在第7章中讨论。 然而，甚至扫描 器也需要知道允许的有效位数并判断是否正确转换了常量。 正如从这些例子中看到的，届性计算变化极大。当它们在绵译程序中显式出现时，可能在 编译过程的任意时刻发生：即使语义分析阶段与属性计算的联系最紧密，扫描器和语法分析程 序也都需要对它们有用的属性信息，在语法分析的同时也需要进行一些语义分析。在本章中， 我们集中讨论在代码生成前及语法分析后的典型计算（语法分析期间的语义分析信息见6.2.5 节)。直接应用于代码生成的属性分析在第8章中讨论。 6.1.1属性文法 在语法制导语义(syntax--directed semantics))中，属性直接与语言的文法符号相联系（终结符 号或非终结符号)⊙。如果X是一个文法符号，a是X的一个属性，那么我们把与X关联的的值 记作X.a。这个记号让人回忆起Pascali语言的记录字段表示符或（等价于）C语言中的结构成员操 作符。实际上，实现属性计算的一种典型方法是使用记录字段（或结构成员）将属性值放到语法 树的节点中去。下一节将更详细地讨论这一点。 若有一个性的集合a ,,语法制导语义的原理应用于每个文法规则X。一XX (这里X是一个非终结符号，其他的X都是任意符号)，每个文法符号X的属性X.口的值与规则 中其他符号的属性值有关。如果同一个符号X在文法规则中出现不止一次，那么每次必须用合 适的下标与在其他地方出现的符号区分开来。每个关系用属性等式()或语义规 则(semantics rule)e表示，形式如下 Xa=f(X。a,,X。ayXa,,Xa,,Xa,,Xa) 这里的f是一个数学函数。属性a,,,a,的属性文法(attribute grammar)是对语言的所有文法 规则的所有这类等式的集合。 在这个一般性情况中，属性文法显得相当复杂。在实际情况下，函数通常非常简单。属 性也很少依赖于大量的其他属性，因此可以将相互依赖的属性分割为较小的独立属性集，并对 语法制导酒义可以简单地称作语义制导语法(semantics-direeted syntax)),因为在大多数语言中语法是用已经 在头脑中建立的（最终）语义设 。后面我们将看到语义规则比属性等式更加通用一些。这里读者可以先把它们看成是等效的
实体的数据类型属性，并验证这些类型符合语言的类型规则。在如 C或P a s c a l这样的语言 中，类型检查是语义分析的一个重要部分。而在 L I S P这样的语言中，数据类型是动态的， L I S P编译程序必须生成代码来计算类型，并在程序执行期间完成类型检查。 • 表达式的值通常是动态的，编译程序要在执行时生成代码来计算这些值。然而事实上， 一些表达式可能是常量 (例如3 + 4 * 5 )，语义分析程序可以选择在编译时求出它们的值 (这 个过程称作常量合并(constant folding))。 • 变量的分配可以是静态的也可以是动态的，这依赖于语言和变量自身的特性。例如，在 F O RT R A N 7 7中所有的变量都是静态分配的，而在 L I S P中所有的变量是动态分配的。C和 P a s c a l语言混合了静态和动态的两种变量分配。因为编译程序与变量分配联系的计算依 赖于运行时环境，有时还依赖于具体的目标机器，所以这些计算会一直推迟到代码生成 (第7章将更详细地探讨这一问题)。 • 程序的目标代码无疑是一个静态属性。编译程序的代码生成器专门用于这个属性的计算。 • 数的有效位数在编译期间是一个不被明确探讨的属性。编译程序编写者实现值的表示是 不言而喻的，这通常被视为运行时环境的一部分，这将在第 7章中讨论。然而，甚至扫描 器也需要知道允许的有效位数并判断是否正确转换了常量。 正如从这些例子中看到的，属性计算变化极大。当它们在编译程序中显式出现时，可能在 编译过程的任意时刻发生：即使语义分析阶段与属性计算的联系最紧密，扫描器和语法分析程 序也都需要对它们有用的属性信息，在语法分析的同时也需要进行一些语义分析。在本章中， 我们集中讨论在代码生成前及语法分析后的典型计算 (语法分析期间的语义分析信息见 6 . 2 . 5 节)。直接应用于代码生成的属性分析在第8章中讨论。 6.1.1 属性文法 在语法制导语义(syntax-directed semantics)中，属性直接与语言的文法符号相联系 (终结符 号或非终结符号) 。如果X是一个文法符号，a 是X的一个属性，那么我们把与 X关联的a的值 记作X.a。这个记号让人回忆起 P a s c a l语言的记录字段表示符或 (等价于) C语言中的结构成员操 作符。实际上，实现属性计算的一种典型方法是使用记录字段 (或结构成员)将属性值放到语法 树的节点中去。下一节将更详细地讨论这一点。 若有一个属性的集合a1 , . . . , ak ，语法制导语义的原理应用于每个文法规则X0→X1 X2 . . . X n (这里X0 是一个非终结符号，其他的Xi 都是任意符号)，每个文法符号Xi 的属性Xi .aj 的值与规则 中其他符号的属性值有关。如果同一个符号 Xi 在文法规则中出现不止一次，那么每次必须用合 适的下标与在其他地方出现的符号区分开来。每个关系用属性等式 (attribute equation)或语义规 则(semantics rule) 表示，形式如下 Xi .aj = f i j (X0 .a1 , . . . , X0 .ak ，X1 .a1 , . . . , X1 .ak , . . . , Xn .a1 , . . . , Xn .ak ) 这里的f i j 是一个数学函数。属性a1 , . . . , ak 的属性文法(attribute grammar)是对语言的所有文法 规则的所有这类等式的集合。 在这个一般性情况中，属性文法显得相当复杂。在实际情况下，函数 f i j 通常非常简单。属 性也很少依赖于大量的其他属性，因此可以将相互依赖的属性分割为较小的独立属性集，并对 2 0 0 编译原理及实践 下载 语法制导语义可以简单地称作语义制导语法 (semantics-directed syntax)，因为在大多数语言中语法是用已经 在头脑中建立的(最终)语义设计的。 后面我们将看到语义规则比属性等式更加通用一些。这里读者可以先把它们看成是等效的
China-pub.com 下载 第6章语义分析 201 每个属性集单独写出一个属性文法。 一般地，将属性文法写成表格形式，每个文法规则用属性等式的集合或者相应规则的语义 规则列出，如下所示⊙ 文法规则 语义规则 规则1 相关的属性等式 规则n 相关的属性等式 接下来继续看几个例子。 例6.1考虑下面简单的无符号数文法 number-number digit digit digt→0111213141516171819 一个数最重要的属性是它的值，我们将其命名为vl。每个数字都有一个值，可以用它表示的 实际数直接计算。因此，例如，文法规则dg1一0表明在这个情况下dgt的值为0。这可以用 属性等式digit.val=0表示，我们将这个等式和规则digi一0联系在一起。此外，每个数都有 个基于它所包含的数字的值。如果一个数使用了下面的规则推导 mber→digit 那么这个数就只包含了一个数字，其值就是这个数字的值。用属性等式表示为 number.val =digit.val 如果一个数包含的数字多于1个，可以使用下列文法规则推导 mumber→number digit 我们必须表示出这个文法规则左边符号的值和右边符号的值之间的关系。请读者注意，在这个 文法规则中对number的两次出现必须进行区分，因为右边的number和左边的numbere的值不相 同。我们使用下标进行区分，将这个文法写成如下形式： number,→umber,digit 现在考虑一个数，如34。这个数的（最左）推导如下：mumber一number digit→digit digit→3 digit一34。考虑在这个推导的第一步文法规则number,→number:digit的使用。非终结符号 mumber,对应于数字3，digit对应于数字4。每个符号的值分别是3和4。为了获得number的值 (它为34)，必须用nmbe,的值乘以10，再加上dg的值：34=3*10+4.换句话说，是把3左 移一个十进制位再加上4。相应的属性等式是 number,val number,val*10+digit.val 完整的ral属性文法在表6-1中给出。 使用字符串的语法树可以形象化地表示特殊字符串的属性等式的意义。例如，图6-1给出 了数345的语法树。在这个图中相应合适的属性等式的计算显示在每个内部节点的下面。在语 日这些表中通常用表头“语义规则”代替“属性等式”，以便后面对语义规则进行更通用的解释
每个属性集单独写出一个属性文法。 一般地，将属性文法写成表格形式，每个文法规则用属性等式的集合或者相应规则的语义 规则列出，如下所示 ： 文 法 规 则 语 义 规 则 规则1 相关的属性等式 . . . . . . 规则n 相关的属性等式 接下来继续看几个例子。 例6.1 考虑下面简单的无符号数文法： number → number digit | d i g i t digit →0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 一个数最重要的属性是它的值，我们将其命名为 v a l。每个数字都有一个值，可以用它表示的 实际数直接计算。因此，例如，文法规则 d i g i t→0 表明在这个情况下digit 的值为0。这可以用 属性等式digit.val = 0 表示，我们将这个等式和规则d i g i t→0 联系在一起。此外，每个数都有一 个基于它所包含的数字的值。如果一个数使用了下面的规则推导 number → d i g i t 那么这个数就只包含了一个数字，其值就是这个数字的值。用属性等式表示为 n u m b e r.val = d i g i t . v a l 如果一个数包含的数字多于1个，可以使用下列文法规则推导 number → number digit 我们必须表示出这个文法规则左边符号的值和右边符号的值之间的关系。请读者注意，在这个 文法规则中对number 的两次出现必须进行区分，因为右边的 number 和左边的n u m b e r的值不相 同。我们使用下标进行区分，将这个文法写成如下形式： n u m b e r1 →n u m b e r2 d i g i t 现在考虑一个数，如3 4。这个数的(最左)推导如下：number Þ number digit Þ digit digit Þ 3 digit Þ 3 4。考虑在这个推导的第一步文法规则 n u m b e r 1 →n u m b e r 2 digit 的使用。非终结符号 n u m b e r2 对应于数字3，digit 对应于数字4。每个符号的值分别是3和4。为了获得n u m b e r1 的值 (它为3 4 )，必须用n u m b e r2 的值乘以1 0，再加上digit 的值：34 = 3*10+4。换句话说，是把3左 移一个十进制位再加上4。相应的属性等式是 n u m b e r1 .val = n u m b e r2 .v a l * 10 + d i g i t . v a l 完整的val 属性文法在表6 - 1中给出。 使用字符串的语法树可以形象化地表示特殊字符串的属性等式的意义。例如，图 6 - 1给出 了数3 4 5的语法树。在这个图中相应合适的属性等式的计算显示在每个内部节点的下面。在语 第 6章 语 义 分 析 2 0 1 下载 这些表中通常用表头“语义规则”代替“属性等式”，以便后面对语义规则进行更通用的解释
202 编译原理及实践 China-pub.co 下载 法树中计算时观察属性等式对于计算属性值的算法是重要的，就像在下一节将看到的那样⊙。 在表6-1和图6-1中，通过使用不同的字体，我们强调了数字和值的语法表示或者数字语义 内容之间的不同。例如在文法规则dig1一0中，数字0是一个记号或特性，而digit.val=0的含 义是数字的数值为0。 表6-1例6.1的属性文法 文法规则 语义规则 Number,→number,digit number..val numberval 10+digit.val Number-一digit numberval digit.val -0 digit.val-0 digit -2 digit.val =2 digit-3 digit.val =3 dhgi→4 digit.val =4 digit.val -5 -6 digit.val-6 digit.val -7 igr→8 digit.val =8 gt→g digit.val=9 0a1-3407095=345 0al-30r4=30 (val =5) (l 3) ( (val =3) 图6-1显示例6.1中属性计算的语法树 例6.2考虑下列简单的整数算术表达式文法： exp exp term exp -term term term-term factor|factor factor→(ep number 这个文法对第5章广泛讨论的简单表达式文法稍微作了一些改动。 exp(或iem或factor)的基本属 性是它的数字值，写作ral。val属性的届性等式在表6-2中给出。 日事实上，扫描器通常认为数是标记，它们的数值也很容易计算。在此期间，扫指器很可能隐含地使用这里定 义的属性等式
法树中计算时观察属性等式对于计算属性值的算法是重要的，就像在下一节将看到的那样 。 在表6 - 1和图6 - 1中，通过使用不同的字体，我们强调了数字和值的语法表示或者数字语义 内容之间的不同。例如在文法规则 d i g i t→0 中，数字0是一个记号或特性，而d i g i t . v a l = 0的含 义是数字的数值为0。 表6-1 例6 . 1的属性文法 文 法 规 则 语 义 规 则 N u m b e r1 → n u m b e r2 d i g i t n u m b e r1 .val = n u m b e r 2 .val * 10 + d i g i t.v a l Number → d i g i t n u m b e r.val = d i g i t . v a l digit → 0 digit.val = 0 digit → 1 digit.val = 1 digit → 2 digit.val = 2 digit → 3 digit.val = 3 digit → 4 digit.val = 4 digit → 5 digit.val = 5 digit → 6 digit.val = 6 digit → 7 digit.val = 7 digit → 8 digit.val = 8 digit → 9 digit.val = 9 图6-1 显示例6 . 1中属性计算的语法树 例6.2 考虑下列简单的整数算术表达式文法： exp → exp + t e r m | exp - t e r m | t e r m t e r m → t e r m * f a c t o r | f a c t o r f a c t o r →(e x p)| n u m b e r 这个文法对第5章广泛讨论的简单表达式文法稍微作了一些改动。 e x p(或t e r m或f a c t o r)的基本属 性是它的数字值，写作v a l。val 属性的属性等式在表6 - 2中给出。 2 0 2 编译原理及实践 下载 事实上，扫描器通常认为数是标记，它们的数值也很容易计算。在此期间，扫描器很可能隐含地使用这里定 义的属性等式
China-pub.com 下载 第6京语义分析203 表6-2例6.2的属性文法 文法规则 语义规则 exp,→ep:+ierm ep一exp-lerm ep→lerm exp.val-term.val term,→ierl,*factor term,val -term,val factor.val term→factor term.val -factor.val factor→(exp) factoryal exp val factor→number factor.val =number.val 这些等式表示了表达式的语法和它所进行的算术运算的语义之间的关系。注意，在文法 规则 xp,一ep,+term 中语义符号+（记号）和等式 exp,val exp,val term.val 中执行的算术加运算符+的不同。还要注意aumber.val不会在等式的左边。就像在下一节将看 到的，这意味着必须在任意一个使用这个属性文法（例如扫描器）的语义分析之前计算 number.val。换句话说，如果想在属性文法中明确这个值，就必须在属性文法中加进文法规 则和属性等式（例如，例6.1中的等式）。 如例6.1一样，也可以通过在语法树的节点上附加等式来表示属性文法包含的计算。例如， 给定表达式(34-3)*42，可以用在其语法树上值的语义来表达，如图6-2所示。 0al3302 0al=3到2=130z 3) () facte 31) a5 (d 331) () 234 036 图6-2(34-3)*42的语法树，显示例6,2中属性文法的val属性计算
表6-2 例6 . 2的属性文法 文 法 规 则 语 义 规 则 e x p1 → e x p2 + t e r m e x p1 .val = e x p2 .val + t e r m.v a l e x p1 → e x p2 - t e r m e x p1 .val = e x p2 .v a l - t e r m.v a l exp → t e r m e x p.v a l = t e r m.v a l t e r m1 → t e r m2 * f a c t o r t e r m1 .val = t e r m2 .val * f a c t o r.v a l t e r m → f a c t o r term.val = f a c t o r.v a l f a c t o r → (e x p) f a c t o r.val = exp.val f a c t o r → n u m b e r f a c t o r.val = n u m b e r.val 这些等式表示了表达式的语法和它所进行的算术运算的语义之间的关系。注意，在文法 规则 e x p1→ e x p2 + t e r m 中语义符号 +(记号)和等式 e x p1 .val = e x p2 .val + t e r m.v a l 中执行的算术加运算符 + 的不同。还要注意n u m b e r. v a l不会在等式的左边。就像在下一节将看 到的，这意味着必须在任意一个使用这个属性文法 (例如扫描器 )的语义分析之前计算 n u m b e r. v a l。换句话说，如果想在属性文法中明确这个值，就必须在属性文法中加进文法规 则和属性等式(例如，例6 . 1中的等式)。 如例6 . 1一样，也可以通过在语法树的节点上附加等式来表示属性文法包含的计算。例如， 给定表达式( 3 4 - 3 ) * 4 2，可以用在其语法树上值的语义来表达，如图 6 - 2所示。 图6-2 ( 3 4 - 3 ) * 4 2 的语法树，显示例6 . 2中属性文法的v a l属性计算 第 6章 语 义 分 析 2 0 3 下载
204编形服理及实我 China-pub.c 下载 例6.3考虑下列类似C语法中变量声明的简单文法 decl type var-list pe→int|float var-list -id var-list id 我们要为在声明中标识符给出的变量定义一个数据类型属性，并写出一个等式来表示数据 类型属性是如何与声明的类型相关的。通过构造dp属性的一个属性文法可以实现这一点（使 用名字dpe和非终结符p的属性进行区分)。dpe的属性文法在表6-3中给出。在图中关于属 性等式我们做了以下标记。 首先，从{integer,real集合中得出dpe的值，相应的记号为int和E1oat。非终结符pe 有一个它表示的记号给定的dpe。通过decl文法规则的等式，这个dpe对应于全体var-lis的 dpe。通过var-list的等式，表中的每个id都有相同的dpe。注意，没有等式包含非终结符 dcl的dpe。实际上decl并不需要dpe,一个属性的值没有必要为所有的文法符号指定。 同前面一样，可以在一个语法树上显示属性等式。图6-3给出了一个例子。 表6-3例6.3的属性文法 文法规则 语义规则 var-lisopeype.dype type.drype intege 0pe→f1oat pe.drype real ran-lil.→主d,ar-isl id dnype var-list drype var-list drype=var-list,drype var-list-id id -var-list.drype 图6-3字符串foat x.y的语法树，显示表6-3冲属性文法指定的dypc属性 到目前为止，所有的例子都只有一个属性，但属性文法可能会包含几个独立的属性。下一 个例子是一个有几个相互联系属性的简单情形。 例6.4考虑对例6.1中数文法进行修改，数可以是八进制或十进制的。假设这通过一个字符的 后缀o(八进制)或（什进制）来表示。这样就有下面的文法 based-num-num basechar basechar→old mum→num digit digit digt→0111213141516171819
例6.3 考虑下列类似C语法中变量声明的简单文法： decl → type var-l i s t type → i n t | f l o a t v a r-list → i d, v a r-list | i d 我们要为在声明中标识符给出的变量定义一个数据类型属性，并写出一个等式来表示数据 类型属性是如何与声明的类型相关的。通过构造 d t y p e属性的一个属性文法可以实现这一点 (使 用名字d t y p e和非终结符t y p e的属性进行区分)。d t y p e的属性文法在表6 - 3中给出。在图中关于属 性等式我们做了以下标记。 首先，从{integer , re a l}集合中得出d t y p e的值，相应的记号为i n t和f l o a t。非终结符t y p e 有一个它表示的记号给定的 d t y p e。通过d e c l文法规则的等式，这个 d t y p e对应于全体v a r- l i s t的 d t y p e。通过v a r- l i s t的等式，表中的每个 i d都有相同的d t y p e。注意，没有等式包含非终结符 decl 的d t y p e。实际上d e c l并不需要d t y p e，一个属性的值没有必要为所有的文法符号指定。 同前面一样，可以在一个语法树上显示属性等式。图 6 - 3给出了一个例子。 表6-3 例6 . 3的属性文法 文 法 规 则 语 义 规 则 decl → type var- l i s t v a r-list.dtype = t y p e . d t y p e type → i n t type.dtype = i n t e g e r type → f l o a t type.dtype = re a l v a r- l i s t 1 → i d ,v a r- l i s t 2 i d.dtype = v a r- l i s t 1 . d t y p e v a r- l i s t 2 .dtype = v a r- l i s t 1 .d t y p e v a r-list → i d i d.dtype = v a r- l i s t . d t y p e 图6-3 字符串float x,y的语法树，显示表6 - 3中属性文法指定的d t y p e属性 到目前为止，所有的例子都只有一个属性，但属性文法可能会包含几个独立的属性。下一 个例子是一个有几个相互联系属性的简单情形。 例6.4 考虑对例6 . 1中数文法进行修改，数可以是八进制或十进制的。假设这通过一个字符的 后缀o (八进制)或d (十进制)来表示。这样就有下面的文法： based-num → num basechar basechar → o | d num → num digit | d i g i t digit → 0|1|2|3|4|5|6|7|8|9 2 0 4 编译原理及实践 下载
China-pub.com 第6章语义分析 205 下载 在这种情况中，nm和digit均需要一个新的属性base用来计算属性val。base和val的属性文法在 表6-4中给出。 表6-4例6.4的属性文法 文法规则 语义规则 based-num Based-num.val =num.val num basechar num.base basechar base basechar-o basechar base =8 basechar-d basechar.base =10 um,一um,dign ifdigit.valerrormal-ero then erro else num,valmum,base+digit.val nunt,.base num,base digit base =num.base num一dign nunyal digitval digit.base num.base digit.val-0 dig7 digit.val=7 dign→g digit.val= if digit.base=8 then error else8 dign→9 digit.val= if digit.base-8 then error else 9 在这个属性文法中必须注意两个新的特性。首先，这个BNF文法在后缀为。时自己不能排 除错误的（非八进制）数字8和9的组合。例如，按照上面的BNF文法，字符串1890在语法上是 (val29 a=288+5=29 (s) (base 8) (val 图64例6.4中属性计算的语法树
在这种情况中，n u m和d i g i t均需要一个新的属性b a s e用来计算属性v a l。b a s e和v a l的属性文法在 表6 - 4中给出。 表6-4 例6 . 4的属性文法 文 法 规 则 语 义 规 则 based-num → Based-num.val = n u m . v a l num basechar n u m.b a s e = b a s e c h a r.b a s e b a s e c h a r → o b a s e c h a r.b a s e = 8 b a s e c h a r → d b a s e c h a r.b a s e = 10 n u m1 →n u m2 d i g i t n u m1 .v a l = i f d i g i t.v a l = e rro r o r n u m2 .v a l = e rro r t h e n e rro r e l s e n u m2 .v a l * n u m1 .b a s e + d i g i t.v a l n u m2 .b a s e = n u m1 .b a s e d i g i t.b a s e = n u m1 .b a s e n u m → d i g i t n u m . v a l = d i g i t.v a l d i g i t.b a s e = n u m.b a s e d i g i t →0 d i g i t.v a l = 0 d i g i t →1 d i g i t.v a l = 1 . . . . . . d i g i t →7 d i g i t.v a l = 7 d i g i t →8 d i g i t.v a l = i f d i g i t.b a s e = 8 t h e n e rro r e l s e 8 d i g i t →9 d i g i t.v a l = i f d i g i t.b a s e = 8 t h e n e rro r e l s e 9 在这个属性文法中必须注意两个新的特性。首先，这个 B N F文法在后缀为o时自己不能排 除错误的(非八进制)数字8和9的组合。例如，按照上面的 B N F文法，字符串1 8 9 o在语法上是 第 6章 语 义 分 析 2 0 5 下载 图6-4 例6 . 4中属性计算的语法树
206 编译原理及实践 China-pub.Co 下载 正确的，但不能赋予任何值。因此，对于这些情况需要一个新的r值。另外，这个属性文法 必须能表示这样的事实，一个带有后缀o的数中包括数字8或9时将导致值为ror。最简单的方 法是在合适的属性等式函数中使用if.then-else表达式。例如，等式 num .val if digit.val=error or num,val=error then error else num,val*num,base +digit.val 对应于文法规则nm,一nm,digit,表示如果um,.val或digit.val为eor,那么num,-ral也必须为 error,除此之外只有一种情况：m,ra的值由公式um,ral*um,base+digit.val给出。 总结这个例子，再在一个语法树上表示属性计算。图6-4给出了数3450的语法树，同时根 据表64的属性文法计算出属性值。 6.1.2属性文法的简化和扩充 if-then-else表达式的使用扩充了表达式的种类，它们可以通过有用的途径出现在属性等式 中，在属性等式中，允许出现的表达式的集合称作属性文法的元语言(metalanguage)。通常我 们希塑元语言的内酒尽可能清晰，不致于引起其自身语义的混淆。我们还希望元语言接近于 种实际使用的编程语言，因为就像我们即将看到的一样，在语义分析程序中需要把属性等式转 换成执行代码。在本书中，我们使用的元语言局限于算术式、逻辑式以及一些其他种类的表达 式，再加上if-then-else表达式，偶尔还有case或switch表达式。 定义属性等式的另一个有用的特征是在元语言中加入了函数的使用，函数的定义可以在别 处给出。例如，在数的文法中，我们对g的每个选择都写出了属性等式。可以采用一个更简 洁的惯例来代替，为dig1写一个文法规则digi→D(这里D是数字中的一个)，相应的属性等式是 digit.al=nval(D） 这里umyal是函数，必须在别处说明其作为属性文法的补充的定义。例如，我们可以用C代码 给出nmva的定义： int numval char D) return (int)D-(int)'0':】 在说明属性文法时更简化的有用方法是使用原始文法二义性的但简单的形式。事实上，因 为假定已经构造了分析程序，所有二义性在那个阶段都己经处理过了，属性文法可以自由地基 于二义性概念，而无须在结果属性中说明任何二义性，例如，例62的算术表达式文法有以下 简单的但二义性的形式： exp-exp+expl exp-exp l exp exp exp number 使用这个文法，属性a可以通过表6-5中的表定义（与表6-2相比较）。 表6-5使用二义性文法定义表达式的va属性 文法规则 语义规则 p,→p,+p exp val exp,val exp.val cxp,→ep-ep, exp,val-exp,val-exp,vat ep,一ep*cp, expval -exp,val*exp val exp.(ep) exp,val=exp,val cp number exp.val-number.val
正确的，但不能赋予任何值。因此，对于这些情况需要一个新的 e rro r值。另外，这个属性文法 必须能表示这样的事实，一个带有后缀 o的数中包括数字8或9时将导致值为e rro r。最简单的方 法是在合适的属性等式函数中使用i f - t h e n - e l s e表达式。例如，等式 n u m1 .val = i f d i g i t . v a l = e rro r o r n u m2 .v a l = e rro r then e rro r e l s e n u m2 .v a l * n u m1 .b a s e + d i g i t . v a l 对应于文法规则n u m1 →n u m2 d i g i t，表示如果n u m2 .v a l或d i g i t . v a l为e rro r，那么n u m1 .v a l也必须为 e rro r，除此之外只有一种情况：n u m1 .v a l的值由公式n u m2 .val * n u m1 .base + d i g i t . v a l给出。 总结这个例子，再在一个语法树上表示属性计算。图 6 - 4给出了数3 4 5 o的语法树，同时根 据表6 - 4的属性文法计算出属性值。 6.1.2 属性文法的简化和扩充 i f - t h e n - e l s e表达式的使用扩充了表达式的种类，它们可以通过有用的途径出现在属性等式 中，在属性等式中，允许出现的表达式的集合称作属性文法的元语言 ( m e t a l a n g u a g e )。通常我 们希望元语言的内涵尽可能清晰，不致于引起其自身语义的混淆。我们还希望元语言接近于一 种实际使用的编程语言，因为就像我们即将看到的一样，在语义分析程序中需要把属性等式转 换成执行代码。在本书中，我们使用的元语言局限于算术式、逻辑式以及一些其他种类的表达 式，再加上i f - t h e n - e l s e表达式，偶尔还有c a s e或s w i t c h表达式。 定义属性等式的另一个有用的特征是在元语言中加入了函数的使用，函数的定义可以在别 处给出。例如，在数的文法中，我们对digit 的每个选择都写出了属性等式。可以采用一个更简 洁的惯例来代替，为digit 写一个文法规则d i g i t →D (这里D是数字中的一个)，相应的属性等式是 d i g i t . v a l = numval (D) 这里n u m v a l是函数，必须在别处说明其作为属性文法的补充的定义。例如，我们可以用 C代码 给出n u m v a l的定义： int numval ( char D) { return (int)D-(int)'0';} 在说明属性文法时更简化的有用方法是使用原始文法二义性的但简单的形式。事实上，因 为假定已经构造了分析程序，所有二义性在那个阶段都已经处理过了，属性文法可以自由地基 于二义性概念，而无须在结果属性中说明任何二义性，例如，例 6 . 2的算术表达式文法有以下 简单的但二义性的形式： exp → exp + exp | exp - exp | exp * exp | ( exp ) | n u m b e r 使用这个文法，属性v a l可以通过表6 - 5中的表定义(与表6 - 2相比较)。 表6-5 使用二义性文法定义表达式的 v a l属性 文 法 规 则 语 义 规 则 e x p1 → e x p2 + e x p3 e x p1 .v a l = e x p2 .v a l + e x p3 .v a l e x p1 → e x p2 - e x p3 e x p1 .v a l = e x p2 .v a l - e x p3 .v a l e x p1 → e x p2 * e x p3 e x p1 .v a l = e x p2 .v a l * e x p3 .v a l e x p1 → ( e x p2 ) e x p1 .v a l = e x p2 .v a l exp → n u m b e r e x p.v a l = n u m b e r.val 2 0 6 编译原理及实践 下载
China-pub.com 第6章语义分析 207 下载 在显示属性值时，也可以通过使用抽象语法树代替分析树进行简化。抽象语法树通常必须 用足够的结构来表达属性文法定义的语义。例如表达式(34-3)*42，其分析树和属性在图 6-2中已给出，通过图6-5的抽象语法树也能完全表达它的语义。 如下一个例子所示，语法树自身也可以用属性文法指定，这并不奇怪。 (6al=31*42=1302 (al=343=3) 0a兰3yoa3 图6-534-3)*42的抽象语法树，显示表6-2或表6-5中属性文法的val属性计算 例6.5给定例6.2的简单整数表达式文法，通过表6-6给出的属性文法可以定义表达式的抽象语 法树。在这个属性文法中，我们使用了两个辅助函数mkOpNode和mkNumNode。mkOpNode函 数有3个参数（一个操作符记号和两个语法树）并构成一个新的树节点，其操作符记号是第1个参 数，子节点是第2个和第3个参数。mkNumNode函数有一个参数（数字值）并构成一个叶子节点， 它表示具有这个值的一个数。在表6-6中我们把数字值写作number.lexval,表示它是由扫描器 构成的。事实上，根据不同的实现，这可以是实际的数字值，或用它的字符串表示（比较表66 中的等式和附录B中TINY语法树递归下降构造)。 表66简单整型算术表达式的抽象语法树的属性文法 文法规则 语义规则 ep,一ep,+tem exp,tree- mkOpNode (+exptree,term.tree) ep,一ep,-term exp tree mkOpNode (-exp,tree,term.tree) exp→erm exp.tree term.tree 1erm→erm,*factor mkOpNode (term,treefactor ee erm一factor factor.tree exp.tree jactor.tree= mkNumNode (number.lexval) 如何确保一个特定的属性文法是一致的和完整的，是使用属性文法的属性说明的一个主要 问题，也就是说，它能唯一定义给定的属性。简单的答案是到目前为止还不能做到。这个问题 与确定一个文法是否是二义的类似。实际上，这是用来确定一个文法充分性的分析算法，类似 的情形发生在属性文法的情况中。因此，下一节将研究属性计算的算法规则方法，确定一个属 性文法是否足够能定义属性值。 6.2属性计算算法 这一节将以属性文法为基础，研究编译程序中如何计算和使用由属性文法的等式定义的属
在显示属性值时，也可以通过使用抽象语法树代替分析树进行简化。抽象语法树通常必须 用足够的结构来表达属性文法定义的语义。例如表达式 ( 3 4 - 3 ) * 4 2，其分析树和v a l属性在图 6 - 2中已给出，通过图6 - 5的抽象语法树也能完全表达它的语义。 如下一个例子所示，语法树自身也可以用属性文法指定，这并不奇怪。 图6-5 ( 3 4 - 3 ) * 4 2 的抽象语法树，显示表6 - 2或表6 - 5中属性文法的v a l属性计算 例6.5 给定例6 . 2的简单整数表达式文法，通过表6 - 6给出的属性文法可以定义表达式的抽象语 法树。在这个属性文法中，我们使用了两个辅助函数 m k O p N o d e和m k N u m N o d e。m k O p N o d e函 数有3个参数(一个操作符记号和两个语法树 )并构成一个新的树节点，其操作符记号是第 1个参 数，子节点是第2个和第3个参数。m k N u m N o d e函数有一个参数(数字值)并构成一个叶子节点， 它表示具有这个值的一个数。在表 6 - 6中我们把数字值写作n u m b e r.l e x v a l，表示它是由扫描器 构成的。事实上，根据不同的实现，这可以是实际的数字值，或用它的字符串表示 (比较表6 - 6 中的等式和附录B中T I N Y语法树递归下降构造)。 表6-6 简单整型算术表达式的抽象语法树的属性文法 文 法 规 则 语 义 规 则 e x p1 → e x p2 + t e r m e x p1 .t re e = m k O p N o d e (+, e x p2 .t re e, t e r m. t re e) e x p1 → e x p2 - t e r m e x p1 .t re e = m k O p N o d e (-, e x p2 .t re e,t e r m. t re e) exp → t e r m e x p.t ree = t e r m.t re e t e r m1 → t e r m2 * f a c t o r t e r m1 .t ree = m k O p N o d e (*, t e r m2 .t re e,f a c t o r .t re e) t e r m → f a c t o r t e r m.t ree = f a c t o r. t re e f a c t o r → ( exp ) f a c t o r.t re e = e x P. t re e f a c t o r → n u m b e r f a c t o r.t ree = m k N u m N o d e (n u m b e r.l e x v a l) 如何确保一个特定的属性文法是一致的和完整的，是使用属性文法的属性说明的一个主要 问题，也就是说，它能唯一定义给定的属性。简单的答案是到目前为止还不能做到。这个问题 与确定一个文法是否是二义的类似。实际上，这是用来确定一个文法充分性的分析算法，类似 的情形发生在属性文法的情况中。因此，下一节将研究属性计算的算法规则方法，确定一个属 性文法是否足够能定义属性值。 6.2 属性计算算法 这一节将以属性文法为基础，研究编译程序中如何计算和使用由属性文法的等式定义的属 第 6章 语 义 分 析 2 0 7 下载