阅读更多
1 语法制导翻译概述
1.1 语法制导翻译的概念
首先，来回顾一下编译的各个阶段
- 词法分析
- 语法分析
- 语义分析
- 中间代码生成
- 代码优化
- 目标代码生成
语义分析和中间代码生成可以同时进行，称为语义翻译语法分析、语义分析、中间代码生成可以同时进行，称为语法制导翻译
语法制导翻译使用CFG来引导对语言的翻译，是一种面向文法的翻译技术
1.2 语法制导翻译的基本思想
如何表示语义信息？
- 为CFG中的文法符号设置语义属性，用来表示语法成分对应的语义信息
如何计算语义属性？
- 文法符号的语义属性值是用与文法符号所在产生式（语法规则）相关联的语义规则来计算的
- 对于给定的输入串$x$ ，构建$x$的语法分析树，并利用与产生式（语法规则）相关联的语义规则来计算分析树中各结点对应的语义属性值
1.3 两个概念
将语义规则同语法规则（产生式）联系起来要涉及两个概念
- 语法制导定义(Syntax-Directed Definitions, SDD)
- 语法制导翻译方案(Syntax-Directed Translation Scheme, SDT)
1.3.1 语法制导定义(SDD)
SDD是对CFG的推广
- 将每个文法符号和一个语义属性集合相关联
- 将每个产生式和一组语义规则相关联，这些规则用于计算该产生式中各文法符号的属性值
如果$X$是一个文法符号，$a$是$X$的一个属性，则用$X.a$表示属性$a$在某个标号为$X$的分析树结点上的值
语
1.3.2 语法制导翻译方案(SDT)
SDT是在产生式右部嵌入了程序片段的CFG，这些程序片段称为语义动作。按照惯例，语义动作放在花括号内
一个语义动作在产生式中的位置决定了这个动作的执行时间
1.3.3 SDD与SDT
SDD
- 是关于语言翻译的高层次规格说明
- 隐蔽了许多具体实现细节，使用户不必显式地说明翻译发生的顺序
SDT
- 可以看作是对SDD的一种补充，是SDD的具体实施方案
- 显式地指明了语义规则的计算顺序，以便说明某些实现细节
2 语法制导定义SDD
语法制导定义SDD是对CFG的推广
- 将每个文法符号和一个语义属性集合相关联
- 将每个产生式和一组语义规则相关联，用来计算该产生式中各文法符号的属性值
文法符号的属性
- 综合属性(synthesized attribute)
- 继承属性(inherited attribute)
2.1 综合属性(synthesized attribute)
在分析树结点N上的非终结符A的综合属性只能通过N的子结点或N本身的属性值来定义
终结符可以具有综合属性。终结符的综合属性值是由词法分析器提供的词法值，因此在SDD中没有计算终结符属性值的语义规则
2.2 继承属性(inherited attribute)
在分析树结点N上的非终结符A的继承属性只能通过N的父结点、N的兄弟结点或N本身的属性值来定义
终结符没有继承属性。终结符从词法分析器处获得的属性值被归为综合属性值
2.3 两个例子
2.4 属性文法(Attribute Grammar)
一个没有副作用的SDD有时也称为属性文法
- 属性文法的规则仅仅通过其它属性值和常量来定义一个属性值
3 SDD的求值顺序
SDD为CFG中的文法符号设置语义属性。对于给定的输入串x，应用语义规则计算分析树中各结点对应的属性值
按照什么顺序计算属性值？
- 语义规则建立了属性之间的依赖关系，在对语法分析树节点的一个属性求值之前，必须首先求出这个属性值所依赖的所有属性值
3.1 依赖图(Dependency Graph)
依赖图是一个描述了分析树中结点属性间依赖关系的有向图
分析树中每个标号为$X$的结点的每个属性a都对应着依赖图中的一个结点
如果属性$X.a$的值依赖于属性$Y.b$的值，则依赖图中有一条从$Y.b$的结点指向$X.a$的结点的有向边
注意到，副作用$addtype(id.lexeme,L.in)$会产生一个虚属性节点
3.2 属性值的计算顺序
可行的求值顺序是满足下列条件的结点序列$N_1, N_2, ..., N_k$：如果依赖图中有一条从结点$N_i$到$N_j$的边($N_i \to N_j$)，那么$i \lt j$（即：在节点序列中，$N_i$排在$N_j$前面）
这样的排序将一个有向图变成了一个线性排序，这个排序称为这个图的拓扑排序(topological sort)
说白了，就是如何遍历有向图，BFS、DFS均可
对于只具有综合属性的SDD ，可以按照任何自底向上的顺序计算它们的值
对于同时具有继承属性和综合属性的SDD，不能保证存在一个顺序来对各个节点上的属性进行求值。如果图中没有环，那么至少存在一个拓扑排序
从计算的角度看，给定一个SDD，很难确定是否存在某棵语法分析树，使得SDD的属性之间存在循环依赖关系。幸运的是，存在一个SDD的有用子类，它们能够保证对每棵语法分析树都存在一个求值顺序，因为它们不允许产生带有环的依赖图。不仅如此，接下来介绍的两类SDD可以和自顶向下及自底向上的语法分析过程一起高效地实现
- S-属性定义(S-Attributed Definitions, S-SDD)
- L-属性定义(L-Attributed Definitions, L-SDD)
4 S-属性定义与L-属性定义
4.1 S-属性定义
仅仅使用综合属性的SDD称为S属性的SDD，或S-属性定义、S-SDD
- 如果一个SDD是S属性的，可以按照语法分析树节点的任何自底向上顺序来计算它的各个属性值
- S-属性定义可以在自底向上的语法分析过程中实现
4.2 L-属性定义
L-属性定义(也称为L属性的SDD或L-SDD)的直观含义：在一个产生式所关联的各属性之间，依赖图的边可以从左到右，但不能从右到左(因此称为L属性的，L是Left的首字母)
4.3 L-SDD的正式定义
一个SDD是L-属性定义，当且仅当它的每个属性要么是一个综合属性，要么是满足如下条件的继承属性：假设存在一个产生式$A \to X_1X_2...X_n$，其右部符号$X_i(1 \le i \le n)$的继承属性仅依赖于下列属性：
- $A$的继承属性（只能依赖$A$的继承属性。如果依赖$A$的综合属性，由于A的综合属性可能依赖$X_i$的属性，包括$X_i$的综合属性和继承属性，因此可能形成环路）
- 产生式中$X_i$左边的符号$X_1, X_2, ..., X_{i-1}$的属性
- $X_i$本身的属性，但$X_i$的全部属性不能在依赖图中形成环路
每个S-属性定义都是L-属性定义。因为S-属性没有关于继承属性的限制
5 参考
- 《MOOC-编译原理-陈鄞》