编译器设计 - 语义分析

简述

我们已经了解了解析器如何在语法分析阶段构建解析树。在该阶段构建的普通解析树通常对编译器没有用处，因为它不携带任何有关如何评估树的信息。制定语言规则的上下文无关语法的产生不适应如何解释它们。

例如


E → E + T

上面的 CFG 产生式没有与之相关的语义规则，它无助于理解这个产生式。

一种语言的语义为其结构提供了意义，例如标记和语法结构。语义有助于解释符号、它们的类型以及它们之间的关系。语义分析判断源程序中构造的语法结构是否具有任何意义。


CFG + semantic rules = Syntax Directed Definitions

例如：


int a = “value”;

不应该在词法和句法分析阶段发出错误，因为它在词法和结构上是正确的，但它应该产生语义错误，因为赋值的类型不同。这些规则由语言的语法设置并在语义分析中进行评估。在语义分析中应完成以下任务：

我们已经提到了语义分析器应该识别的一些语义错误：

属性文法是上下文无关文法的一种特殊形式，其中一些附加信息（属性）附加到其一个或多个非终结符以提供上下文相关信息。每个属性都有明确定义的值域，例如整数、浮点数、字符、字符串和表达式。

属性语法是为上下文无关语法提供语义的媒介，它可以帮助指定编程语言的语法和语义。属性语法（当被视为解析树时）可以在树的节点之间传递值或信息。

Example:


E → E + T { E.value = E.value + T.value }

CFG 的右侧部分包含指定如何解释语法的语义规则。这里，非终结符 E 和 T 的值相加，结果被复制到非终结符 E。

语义属性可以在解析时从其域中分配给它们的值，并在分配或条件时进行评估。根据属性获取值的方式，可以大致分为两类：合成属性和继承属性。

这些属性从其子节点的属性值中获取值。为了说明，假设以下产生式：


S → ABC

如果 S 从其子节点 (A,B,C) 中获取值，则称它是合成属性，因为 ABC 的值被合成到 S。

和我们之前的例子（E → E + T）一样，父节点 E 从它的子节点获取它的值。合成属性从不从其父节点或任何兄弟节点获取值。

与合成属性相比，继承属性可以从父级和/或兄弟级获取值。如以下制作，


S → ABC

A 可以从 S、B 和 C 中获取值。B 可以从 S、A 和 C 中获取值。同样，C 可以从 S、A 和 B 中获取值。

Expansion：根据语法规则将非终结符扩展为终结符时

Reduction: 当一个终结符根据语法规则被简化为它对应的非终结符时。语法树是自上而下和从左到右解析的。每当减少发生时，我们都会应用其相应的语义规则（动作）。

语义分析使用语法定向翻译来执行上述任务。

语义分析器从其前一阶段（语法分析）接收 AST（抽象语法树）。

语义分析器将属性信息附加到 AST 中，称为 Attributed AST。

属性是两个元组值，<属性名，属性值>

例如：


int value  = 5;
<type, “integer”>
<presentvalue, “5”>

对于每个产生式，我们附加一个语义规则。

如果 SDT 仅使用合成属性，则称为 S-attributed SDT。这些属性是使用 S 属性的 SDT 评估的，这些 SDT 的语义动作是在产生之后编写的（右侧）。

如上所述，S 属性 SDT 中的属性在自下而上的解析中进行评估，因为父节点的值取决于子节点的值。

这种形式的 SDT 使用合成属性和继承属性，并限制不从右兄弟中获取值。

在 L 属性的 SDT 中，非终端可以从其父节点、子节点和兄弟节点获取值。如以下制作


S → ABC

S 可以从 A、B 和 C（综合）中获取值。A 只能从 S 中获取值。B 可以从 S 和 A 中获取值。C 可以从 S、A 和 B 中获取值。没有非终结符可以从其右侧的兄弟中获取值。

L 属性 SDT 中的属性通过深度优先和从左到右的解析方式进行评估。

我们可以得出结论，如果一个定义是 S 属性的，那么它也是 L 属性的，因为 L 属性的定义包含了 S 属性的定义。