sdd：编译原理笔记-SDD 2024-04-24 04:29:35 0 0 编译原理笔记-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自身的继承或综合属性 这些属性间的依赖关系不形成环 计算方式如下 自顶向下L_dfvisit(n){for m = 从左到右 n 的每个子节点 do { 计算m 的继承属性 L_dfvisit(m) } 计算n 的综合属性} 具有受控副作用的语义规则 一个没有副作用的SDD有时也称为属性文法,属性文法的规则仅仅通过其它属性值和常量来定义一个属性值.但如果没有副作用,标识符表就必须作为属性传递.这时候就要引入受控的副作用.一个例子如下: 副作用可以被看作与相应产生式头相关的哑综合属性的定义。 SDD的应用 略,反正后面会讲到 收藏（0）