编译原理（5）：语法制导翻译

声明：本系列文章，是根据中国大学MOOC网 哈工大的编译原理 这门课学习而成的学习笔记。

一、语法制导翻译概述

什么是语法制导翻译

语法制导翻译的基本思想

两个概念

语法制导定义(SDD)

语法制导翻译方案(SDT)

SDD与SDT

SDD：

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

SDT：

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

二、语法制导定义SDD

综合属性(synthesized attribute)

继承属性(inherited attribute)

属性文法 (Attribute Grammar)

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

三、SDD的求值顺序

SDD的求值顺序

• SDD为CFG中的文法符号设置语义属性。对于给定的输入串x，应用语义规则计算分析树中各结点对应的属性值

• 按照什么顺序计算属性值？
  语义规则建立了属性之间的依赖关系，在对语法分析树节点的一个属性求值之前，必须首先求出这个属性值所依赖的所有属性值

依赖图(Dependency Graph)

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

属性值的计算顺序

四、S-属性定义与L-属性定义

S-属性定义

L-属性定义

五、语法制导翻译方案SDT

语法制导翻译方案SDT

SDT可以看作是SDD的具体实施方案
主要关注如何使用SDT来实现两类重要的SDD，因为在这两种情况下，SDT可在语法分析过程中实现

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

将S-SDD转换为SDT

将一个S-SDD转换为SDT的方法：将每个语义动作都放在产生式的最后

S-属性定义的SDT 实现

将L-SDD转换为SDT

L-属性定义的SDT 实现

L-属性定义的SDT 实现

六、在非递归的预测分析

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

扩展语法分析栈

分析栈中的每一个记录都对应着一段执行代码

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

七、在递归的预测分析过程中进行翻译

算法

八、L-属性定义的自底向上翻译

• 给定一个以LL文法为基础的L-SDD，可以 修改这个文法，并在LR语法分析过程中计 算这个新文法之上的SDD