基本思想
语义信息的表示
为CFG(上下文无关文法)中的文法符号设置语义属性(变量类型,存储位置等等),用来表示语法成分对应的语义信息。
语义属性的计算
对于给定的输入串x ,构建x的语法分析树,并利用与产生式(语法规则)相关联的语义规则来计算分析树中各结点对应的语义属性值。
概念
- 语法制导定义(Syntax-Directed Definitions, SDD) 将每个文法符号对应一个语义属性集合,每个产生式对应一组语义规则,这些规则用 于计算该产生式中各文法符号的属性值。
- 语法制导翻译方案 (Syntax-Directed Translation Scheme , SDT )如下图 的第一个产生式表示当我就出 T 的时候,我就可以利用 T.type 得到 L.inh
语法制导定义SDD
综合属性
在分析树结点上的非终结符的综合属性只能通过树结点的子结点或本身的属性值来定义。
终结符可以具有综合属性。终结符的综合属性值是由词法分析器提供的词法值,因此在SDD中没有计算终结符属性值的语义规则。下图中的副作用类似一个函数调用的过程,和其他的属性没有关系。
继承属性
在分析树结点上的非终结符的继承属性只能通过树结点的父结点、兄弟结点或本身的属性值来定义。
终结符没有继承属性。终结符从词法分析器处获得的属性值被归为综合属性值
属性文法
一个没有副作用的SDD有时也称为属性文法(也就是说全部都是属性之间的关系)
SDD的求值顺序
语义规则建立了属性之间的依赖关系,在对语法分析树节点的一个属性求值之前,必须首先求出这个属性值所依赖的所有属性值。
依赖图
依赖图是一个描述了分析树中结点属性间依赖关系的有向图,一般来说综合属性放在左边,继承属性放在右边。
可以对上面进行拓扑排序(详情见数据结构教材),其中画红线的是可以调换位置的。(如果图中没有环,那么至少存在一个拓扑排序)
S-属性与L-属性
S-属性定义
仅仅使用综合属性的SDD称为S属性的SDD,或S-属性定义、S-SDD
如果一个SDD是S属性的,可以按照语法分析树节点的任何自底向上顺序来计算它的各个属性值
也可以理解为,产生式的左部符号只依赖于右部符号。
L-属性定义
在一个产生式所关联的各属性之间, 依赖图的边可以从左到右,但不能从右到左。L-属性定义包括S-属性定义。
也可以理解为,产生式的符号中右边的总是依赖左边的,如 A->BC
那么 C 只取决于 B 和 A ,B 只取决于 A。
语法制导翻译方案SDT
将S-SDD转换为SDT
将一个S-SDD转换为SDT的方法:将每个语义动作都放在产生式的最后