备案 网站语言宿州百度seo排名软件
编译原理笔记-SDD
SDD与SDT的定义与区别见SDD与SDT的区别
语法制导定义
语法制导定义(Syntax-Directed Definition, SOD) 是一个上下文无关文法和属性及规则的结合。属性和文法符号相关联，而规则和产生式相关联。例子如下
属性分为综合属性和继承属性.
综合属性:结点N 上的综合属性只能通过N 的子结点或N 本身的属性值来定义。
继承属性:在分析树结点N上的非终结符A的继承属性只能通过N的父结点、N的兄弟结点或N本身的属性值来定义.
有些继承属性有其特殊作用,具体见继承属性inh和综合属性syn的作用;
终结符号:终结符号可以具有综合属性，但是不能有继承属性。终结符号的属性值是由词法分析器提供的词法值.
例如3对应的终结符号为digit,其综合属性为词法值整数3.
SDD的求值顺序
一个显示了它的各个属性的值的语法分析树称为注释语法分析树.示例如下
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-nPmf630i-1633614546196)(E:\编译原理\编译原理笔记-SDD.assets\image-20211007194243818.png)]
语义规则建立了属性之间的依赖关系，在对语法分析树节点的一个属性求值之前，必须首先求出
这个属性值所依赖的所有属性值.
例如要计算E.val就要先计算 E 1 . v a l E_1.val E1.val和 T . v a l T.val T.val
这种依赖关系很容易联想到拓扑排序和依赖图.
依赖图
依赖图定义如下
- 依赖图是一个描述了分析树中结点属性间依赖关系的有向图
- 分析树中每个标号为X的结点的每个属性a都对应着依赖图中的一个结点
- 如果属性X.a的值依赖于属性Y.b的值，则依赖图中有一条从Y.b的结点指向X.a的结点的有向边
示例如下
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-z4Oda8RY-1633614546200)(E:\编译原理\编译原理笔记-SDD.assets\image-20211007194052364.png)]
学过拓扑排序的都知道,如果图中存在环则会导致不存在合法的求值顺序.示例如下
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-sW1oRjT9-1633614546202)(E:\编译原理\编译原理笔记-SDD.assets\image-20211007195204124.png)]
给定一个SDD，很难确定是否存在某棵语法分析树，使得SDD的属性之间存在循环依赖关系.
但幸运的是,存在一个SDD的有用子类，它们能够保证对每棵语法分析树都存在一个求值顺序，因为它们不允许产生带有环的依赖图.
下面介绍其中的S-属性定义和L-属性定义.
S-属性定义
S-属性定义:仅仅使用综合属性的SDD称为S属性的SDD
S-属性的计算方法如下.
自顶向下分析:在递归子程序法中，在过程 A 的最后计算 A 的属性 (此时 A 调用的其他过程 对应于其子结构 已经调用完毕)
自底向上分析:在构造分析树结点的同时计算相关的属性 (此时其子结点的属性必然已经计算完毕)
语法分析树:按照 后序遍历的顺序计算属性值即可
L-属性的定义
直观含义：在一个产生式所关联的各属性之间，依赖图的边可以从左到右，但不能从右到左
正式定义:L属性的SDD,它的每个属性
- 是综合属性，或
- 是继承属性,且 A → X 1 X 2 … X n A \rightarrow X_{1} X_{2} \ldots X_{n} A→X1X2…Xn中计算 X i . a X_i.a Xi.a的规则只能用
- A 的继承属性，或
2. X i X_i Xi左边 的文法符号 X j X_j Xj的 继承属性或综合属性 ，或
3. X i X_i Xi自身的继承或综合属性 这些属性间的依赖关系不形成环
- A 的继承属性，或
计算方式如下
自顶向下
L_dfvisit(n)
{for m = 从左到右 n 的每个子节点 do{计算m 的继承属性L_dfvisit(m)}计算n 的综合属性
}
具有受控副作用的语义规则
一个没有副作用的SDD有时也称为属性文法,属性文法的规则仅仅通过其它属性值和常量来定义一个属性值.但如果没有副作用,标识符表就必须作为属性传递.这时候就要引入受控的副作用.一个例子如下:
副作用可以被看作与相应产生式头相关的哑综合属性的定义。
SDD的应用
略,反正后面会讲到