编译原理笔记-SDD

编译原理笔记-SDD编译原理笔记-SDDSDD与SDT的定义与区别见SDD与SDT的区别语法制导定义语法制导定义(Syntax-DirectedDefinition,SOD)是一个上下文无关文法和属性及规则的结合

编译原理笔记-SDD

SDD与SDT的定义与区别见SDD与SDT的区别

语法制导定义

语法制导定义(Syntax-Directed Definition, SOD) 是一个上下文无关文法和属性及规则的结合。属性和文法符号相关联,而规则和产生式相关联。例子如下

编译原理笔记-SDD

属性分为综合属性和继承属性.

综合属性:结点N 上的综合属性只能通过N 的子结点或N 本身的属性值来定义。

编译原理笔记-SDD

继承属性:在分析树结点N上的非终结符A的继承属性只能通过N的父结点、N的兄弟结点或N本身的属性值来定义.

有些继承属性有其特殊作用,具体见继承属性inh和综合属性syn的作用;

编译原理笔记-SDD

终结符号:终结符号可以具有综合属性,但是不能有继承属性。终结符号的属性值是由词法分析器提供的词法值.

例如3对应的终结符号为digit,其综合属性为词法值整数3.

SDD的求值顺序

一个显示了它的各个属性的值的语法分析树称为注释语法分析树.示例如下

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-nPmf630i-1633614546196)(E:\编译原理\编译原理笔记-SDD.assets\image-20211007194243818.png)]

语义规则建立了属性之间的依赖关系,在对语法分析树节点的一个属性求值之前,必须首先求出
这个属性值所依赖的所有属性值.

编译原理笔记-SDD

例如要计算E.val就要先计算 E 1 . v a l E_1.val E1.val T . v a l T.val T.val

这种依赖关系很容易联想到拓扑排序和依赖图.

依赖图

依赖图定义如下

  1. 依赖图是一个描述了分析树中结点属性间依赖关系的有向图
  2. 分析树中每个标号为X的结点的每个属性a都对应着依赖图中的一个结点
  3. 如果属性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,它的每个属性

  1. 是综合属性,或
  2. 是继承属性,且 A → X 1 X 2 … X n A \rightarrow X_{1} X_{2} \ldots X_{n} AX1X2Xn中计算 X i . a X_i.a Xi.a的规则只能用
    1. 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

副作用可以被看作与相应产生式头相关的哑综合属性的定义。

SDD的应用

略,反正后面会讲到

今天的文章编译原理笔记-SDD分享到此就结束了,感谢您的阅读。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/68581.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注