编译原理 chapter5 语法制导翻译学习课件.pptx

语法制导翻译;编译的阶段

词法分析

语法分析

语义分析

中间代码生成

代码优化

目标代码生成;如何表示语义信息？

为CFG中的文法符号设置语义属性，用来表示语法成分对应的语义信息

如何计算语义属性？

文法符号的语义属性值是用与文法符号所在产生式（语法规则）相关联的语义规则来计算的

对于给定的输入串x，构建x的语法分析树，并利用与产生式（语法规则）相关联的语义规则来计算分析树中各结点对应的语义属性值

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

语法制导定义(Syntax-DirectedDefinitions,SDD)

语法制导翻译方案(SDT,Syntax-DirectedTranslationScheme)

;SDD是对CFG的推广

将每个文法符号和一个语义属性集合相关联

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

如果X是一个文法符号，a是X的一个属性，则用X.a表示属性a在某个标号为X的分析树结点上的值

例

;SDT是在产生式右部嵌入了程序片段的CFG，这些程序片段称为语义动作。按照惯例，语义动作放在花括号内

例

;SDD

是关于语言翻译的高层次规格说明

隐蔽了许多具体实现细节，使用户不必显式地说明翻译发生的顺序

SDT

可以看作是对SDD的一种补充，是SDD的具体实施方案

显式地指明了语义规则的计算顺序，以便说明某些实现细节;;语法制导定义SDD是对CFG的推广

将每个文法符号和一个语义属性集合相关联

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

文法符号的属性

综合属性（synthesizedattribute）

继承属性（inheritedattribute）;综合属性（synthesizedattribute）;继承属性(inheritedattribute);digit.lexval=3;;一个没有副作用的SDD有时也称为属性文法

属性文法的规则仅仅通过其它属性值和常量来定义一个属性值

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

按照什么顺序计算属性值？

语义规则建立了属性之间的依赖关系，在对语法分析树结点的一个属性求值之前，必须首先求出这个属性值所依赖的所有属性值;依赖图是一个描述了分析树中结点属性间依赖???系的有向图

分析树中每个标号为X的结点的每个属性a都对应着依赖图中的一个结点

如果属性X.a的值依赖于属性Y.b的值，则依赖图中有一条从Y.b的结点指向X.a的结点的有向边;type;for分析树中的每个结点ndo

for与结点n对应的文法符号的每个属性ado

在依赖图中为a构造一个结点；

for分析树的每个结点ndo

for结点n所用产生式对应的每条语义规则b:＝f(c1,c2,…,ck)do

fori:=1tokdo

从结点ci到结点b构造一条有向边；;type;可行的求值顺序是满足下列条件的结点序列N1,N2,…,Nk：如果依赖图中有一条从结点Ni到Nj的边(Ni→Nj),那么ij（即：在节点序列中，Ni排在Nj前面）

这样的排序将一个有向图变成了一个线性排序，这个排序称为这个图的拓扑排序(topologicalsort);;例;从计算的角度看，给定一个SDD，很难确定是否存在某棵语法分析树，使得SDD的属性之间存在循环依赖关系

幸运的是，存在一个SDD的有用子类，它们能够保证对每棵语法分析树都存在一个求值顺序，因为它们不允许产生带有环的依赖图

不仅如此，接下来介绍的两类SDD可以和自顶向下及自底向上的语法分析过程一起高效地实现

S-属性定义(S-AttributedDefinitions,S-SDD)

L-属性定义(L-AttributedDefinitions,L-SDD);;S-属性定义

仅仅使用综合属性的SDD称为S属性的SDD，或S-属性定义、S-SDD

例

如果一个SDD是S属性的，可以按照语法分析树节点的任何自底向上顺序来计算它的各个属性值

S-属性定义可以在自底向上语法分析的过程中实现;L-属性定义（也称为L属性的SDD或L-SDD）的直观含义：在一个产生式所关联的各属性之间，依赖图的边可以从左到右，但不能从右到左（因此称为L属性的，L是Left的首字母）;一个SDD是L-属性定义，当且仅当它的每个属性要么是一个综合属性，要么是满足如下条件的继承属性：假设存在一个产生式A→X1X2…Xn，其右部符号X