语法制导翻译（Syntax-Directed Translation）

本文主要是对 哈工大编译原理课件 的学习和总结。

一般将语义分析和中间代码生成两个阶段合称语义翻译；将语法分析、语义分析和中间代码生成三个阶段合称语法制导翻译（Syntax-Directed Translation）。语法制导翻译是一种面向文法的翻译技术。

语法制导翻译概述

语法制导翻译的基本思想：

• 为CFG文法符号设置语义属性，用于表示语法成分的语义信息。
• 为文法符号的产生式（语法规则）关联语义规则，用于计算文法符号的语义属性。
• 构建语法分析树的过程中，利用与产生式（语法规则）相关联的语义规则计算分析树各节点的语义属性值。

将语义规则同语法规则（产生式）联系起来要涉及两个概念：

• 语法制导定义(Syntax-Directed Definitions, SDD)
• 语法制导翻译方案 (Syntax-Directed Translation Scheme , SDT )

语法制导定义（SDD）

SDD是对CFG的推广：

• 将每个文法符号和一个语义属性集合相关联；
• 将每个产生式（语法规则）和一组语义规则相关联，这些规则用于计算该产生式中各文法符号的属性值。

语法制导翻译方案（SDT）

SDT是在产生式右部嵌入了程序片段的CFG，这些程序片段称为语义动作。按照惯例，语义动作放在花括号内。一个语义动作在产生式中的位置决定了这个动作的执行时间。

SDD 与 SDT

SDD 是语言翻译的高层次规格说明，它隐蔽了许多具体实现细节，用户不必显式地说明翻译发生的顺序。

SDT 可以看作是对 SDD 的一种补充，是 SDD 的具体实施方案，SDT 显式地指明了语义规则的计算顺序，以便说明某些实现细节。

语法制导定义（SDD）

SDD 将每个文法符号和一个语义属性集合相关联，将每个产生式和一组语义规则相关联，用来计算该产生式中各文法符号的属性值。

文法符号的属性

文法符号有如下两个属性：

• 综合属性 (synthesized attribute)
• 继承属性 (inherited attribute)

综合属性

在分析树结点 N 上的非终结符 A 的综合属性只能通过 N 的子结点或 N 本身的属性值来定义。

终结符可以具有综合属性。终结符的综合属性值是由词法分析器提供的词法值，因此在SDD中没有计算终结符属性值的语义规则。

继承属性

在分析树结点 N 上的非终结符 A 的继承属性只能通过 N 的父结点、N 的兄弟结点或 N 本身的属性值来定义。

终结符没有继承属性。终结符从词法分析器处获得的属性值被归为综合属性值。

属性文法（Attribute Grammar）

一个没有副作用的SDD有时也称为属性文法。属性文法的规则仅仅通过其它属性值和常量来定义一个属性值。

SDD 求值顺序

语义规则建立了属性之间的依赖关系，在对语法分析树节点的一个属性求值之前，必须首先求出这个属性值所依赖的所有属性值。

依赖图是一个描述了分析树中结点属性间依赖关系的有向图。分析树中每个标号为X的结点的每个属性a都对应着依赖图中的一个结点。如果属性X.a的值依赖于属性Y.b的值，则依赖图中有一条从Y.b的结点指向X.a的结点的有向边。

可行的求值顺序是满足下列条件的结点序列： $N_1,N_2,\dots ,N_k$：如果依赖图中有一条从结点$N_i$ 到 $N_j$ 的边($N_i\to N_j$), 那么 $i<j$（即：在节点序列中，$N_i$ 排在 $N_j$ 前面）。这样的排序将一个有向图变成了一个线性排序，这个排序称为这个图的拓扑排序（topological sort）。

注：1 综合属性位于节点右侧，继承属性位于节点左侧。2 L节点添加虚节点，用于表征产生式中的副作用。

对于只具有综合属性的 SDD ，可以按照任何自底向上的顺序计算它们的值。对于同时具有继承属性和综合属性的 SDD，不能保证存在一个顺序来对各个节点上的属性进行求值。

给定一个SDD，很难确定是否存在某棵语法分析树，使得SDD的属性之间存在循环依赖关系。幸运的是，存在一个SDD的有用子类，它们能够保证对每棵语法分析树都存在一个求值顺序，因为它们不允许产生带有环的依赖图。不仅如此，接下来介绍的两类SDD可以和自顶向下及自底向上的语法分析过程一起高效地实现：

• S-属性定义 (S-Attributed Definitions, S-SDD)
• L-属性定义 (L-Attributed Definitions, L-SDD)

S-SDD 和 L-SDD

S-SDD

仅仅使用综合属性的SDD称为S属性的SDD，或S-属性定义、S-SDD。例如前文介绍的算术表达式的SDD。

如果一个SDD是S属性的，可以按照语法分析树节点的任何自底向上顺序来计算它的各个属性值，S-属性定义可以在自底向上的语法分析过程中实现。

L-SDD

L-属性定义（也称为L属性的SDD或L-SDD）的直观含义：在一个产生式所关联的各属性之间，依赖图的边可以从左到右，但不能从右到左（因此称为L属性的，L是Left的首字母）。

一个SDD是L-属性定义，当且仅当它的每个属性要么是一个综合属性，要么是满足如下条件的继承属性：假设存在一个产生式$A\to X_1{X}_2\dots X_n$，其右部符号$X_i(1<=i<=n)$的继承属性仅依赖于下列属性：

• A的继承属性（如果是综合属性的话可能出现环）
• 产生式中$X_i$左边的符号 $X_1,X_2,\dots ,X_{i-1}$ 的属性
• $X_i$本身的属性，但$X_i$的全部属性不能在依赖图中形成环路

语法制导翻译方案（SDT）

语法制导翻译方案（SDT）是在产生式右部中嵌入了程序片段（称为语义动作）的CFG。SDT可在语法分析过程中实现：

• 基本文法可以使用LR分析技术，且SDD是S属性的。
• 基本文法可以使用LL分析技术，且SDD是L属性的。

S-SDD的SDT实现

对于S-SDD，需要先计算子节点的综合属性后才可以计算父节点的综合属性。因而将S-SDD转换为SDT的方法为：将每个语义动作都放到产生式的最后。

如果一个S-SDD的基本文法可以使用LR分析技术，那么它的SDT可以在LR语法分析过程中实现。因为S-SDD的语义属性都是综合属性，则相应的语义动作都在产生式的最右部，也就是说只有在产生式的右部符号都分析完成后，才能执行相应的语义动作。因而可以在LR语法分析过程中完成SDT，即当规约发生时执行相应的语义动作。

这就需要拓展LR分析栈，用于存放综合属性值：

相应地，拓展LR分析过程：当规约发生时，执行相应的语义动作。

下面通过一个桌面计算器的LR分析过程实现SDT的例子。

相应的语义动作和SLR自动机为：

SLR自动机分析过程如下：

L-SDD的SDT实现

将L-SDD转换为SDT：

• 将计算某个非终结符号A的继承属性的动作插入到产生式右部中紧靠在A的本次出现之前的位置上；
• 将计算一个产生式左部符号的综合属性的动作放置在这个产生式右部的最右端。

如果一个L-SDD的基本文法可以使用LL分析技术，那么它的SDT可以在LL或LR语法分析过程中实现：

• 在非递归的预测分析过程中进行语义翻译
• 在递归的预测分析过程中进行语义翻译
• 在LR分析过程中进行语义翻译

在非递归的预测分析过程中进行语义翻译

扩展的语法分析栈：

A的继承属性是在A即将出现的时候进行计算，A的综合属性是在A的所有子节点都分析完成后才计算。因而将A的继承属性就存放在A的本身记录当中，增加一个$A_{syn}$用于记录A的综合熟悉，并处在栈中A之下。

下面看一个例子：

• 综合记录出栈时，要将综合属性值复制给后面特定的语义动作。
• 变量展开时（即变量本身的记录出栈时），如果其含有继承属性，则要将继承属性值复制给后面特定的语义动作。

在递归的预测分析过程中进行语义翻译

在递归的预测分析的分析算法中，每个非终结符都有一个调用过程。具体算法为：

• 为每个非终结符A构造一个函数，A的每个继承属性对应该函数的一个形参，函数的返回值是A的综合属性值。对出现在A产生式中的每个文法符号的每个属性都设置一个局部变量。

• 非终结符A的代码根据当前的输入决定使用哪个产生式。

• 与每个产生式有关的代码执行如下动作：从左到右考虑产生式右部的词法单元、非终结符及语义动作：

  • 对于带有综合属性x的词法单元 X，把x的值保存在局部变量X.x中；然后产生一个匹配 X的调用，并继续输入。
  • 对于非终结符B，产生一个右部带有函数调用的赋值语句$c:=B(b_1,b_2,...,b_k)$，其中， $b_1,b_2,...,b_k$ 是代表B的继承属性的变量，c是代表B的综合属性的变量。
  • 对于每个动作，将其代码复制到语法分析器，并把对属性的引用改为对相应变量的引用。
  

  

在LR分析过程中进行语义翻译

对于S-SDD，由于所有的语义动作都位于产生式的最右端，可以在归约的时候执行语义动作，因而可以使用自底向上的语法分析方法处理。

对于LL文法的L-SDD，可以修改这个文法，并在LR语法分析过程中计算这个新文法之上的SDD。

• 首先构造SDT，在各个非终结符之前放置语义动作来计算它的继承属性，并在产生式后端放置语义动作计算综合属性
• 对每个内嵌的语义动作，向文法中引入一个标记非终结符来替换它。每个这样的位置都有一个不同的标记，并且对于任意一个标记M都有一个产生式M→ε
• 如果标记非终结符M在某个产生式A→α{a}β中替换了语义动作a，对a进行修改得到a’，并且将a’关联到M→ε 上。动作a’
  • (a) 将动作a需要的A或α中符号的任何属性作为M的继承属性进行复制
  • (b) 按照a中的方法计算各个属性,但是将计算得到的这些属性作为M的综合属性

例如：

注：由于使用LR分析，这些未出现的符号属性已处在栈中的某些已知位置。

然后，对于输入串 3*5 ，基于LR自动机对修改后的SDD进行语义制导翻译：

参考

• 哈工大编译原理课件