hello大家好，教妹学编译原理，没见过这么酷炫的标题吧？“语不惊人死不休”，没错，标题就是这么酷炫。
我的妹妹小埋18岁，校园中女神一般的存在，成绩优异体育万能，个性温柔正直善良。然而，只有我知道，众人眼中光芒万丈的小埋，在过去是一个披着仓鼠斗篷，满地打滚，除了吃就是睡和玩的超级宅女。而这一切的转变，是从那一天晚上开始的。从此之后，小埋经常让我帮她辅导功课。
之前她想了解语法制导翻译。由于语法制导部分内容较多所以分成了上、中、下三部分，今天学习了语法制导的第一部分：SDD（ S-属性定义与L-属性定义）与SDT。本篇教程通过我与小埋的对话的方式来谈一谈SDD与SDT。
博客还在持续更新中，想看同系列的其他博客。欢迎访问我的专栏《教妹学编译原理》希望大家能够关注我，一起学编译原理。
小埋：据说语法制导翻译的两大概念是SDD与SDT，有什么异同吗
语法制导定义SDD
- SDD: 是对CFG的推广
-
将每个文法符号和一个语义属性结合相关联
-
将每个产生式和一组语义规则相关联，这些规则用于计算该产生式中各文法符号的属性值
语法制导翻译方案（SDT）
SDT是在产生式右部嵌入了程序片段的CFG，这些程序片段称为语义动作。按照惯例，语义动作放在花括号内
一个语义动作在产生式中的位置决定了这个动作的执行时间
SDD与SDT的区别
- SDD
- 是关于语言翻译的高层次规格说明
- 隐蔽了许多具体实现细节，使用户不必显式地说明翻译发生的顺序
- SDT
- 可以看作是对SDD的一种补充，是SDD的具体实施方案
- 显式地指明了语义规则的计算顺序，以便说明某些实现细节
综合属性
-
在分析树结点 N上的非终结符A的综合属性只能通过 N的子结点或 N本身的属性值来定义
-
终结符可以具有综合属性。终结符的综合属性值是由词法分析器提供的词法值，因此在SDD中没有计算终结符属性值的语义规则
-
例子
继承属性
-
在分析树结点 N上的非终结符A的继承属性只能通过N的父结点、 N的兄弟结点或 N本身的属性值来定义
-
终结符没有继承属性。终结符从词法分析器处获得的属性值被归为综合属性值
-
例子
属性文法
- 一个没有副作用的SDD有时也称为属性文法
- 属性文法的规则仅仅通过其它属性值和常量来定义一个属性值
小埋：接下来还有SDD的求值顺序，喝完可乐再讲吧
SDD的求值顺序
- SDD为CFG中的文法符号设置语义属性。对于给定的输入串x，应用语义规则计算分析树中各结点对应的属性值
-
按照什么顺序计算属性值？
-
语义规则建立了属性之间的依赖关系，在对语法分析树节点的一个属性求值之前，必须首先求出这个属性值所依赖的所有属性值
依赖图
-
依赖图是一个描述了分析树中结点属性间依赖关系的有向图
-
分析树中每个标号为X的结点的每个属性a都对应着依赖图中的一个结点
-
如果属性X.a的值依赖于属性Y.b的值，则依赖图中有一条从Y.b的结点指向X.a的结点的有向边（即箭头执行依赖属性）
属性值的计算顺序
-
可行的求值顺序是满足下列条件的结点序列N1,N2, … , Nk ：如果依赖图中有一条从结点Ni到 Nj 的边(Ni→Nj), 那么i < j（即：在节点序列中， Ni排在Nj 前面）
-
这样的排序将一个有向图变成了一个线性排序，这个排序称为这个图的拓扑排序(topological sort)
-
对于只具有综合属性的SDD ，可以按照任何自底向上的顺序计算它们的值
-
对于同时具有继承属性和综合属性的SDD， 不能保证存在一个顺序来对各个节点上的属性进行求值
-
从计算的角度看，给定一个SDD，很难确定是否存在某棵语法分析树，使得SDD的属性之间存在循环依赖关系
-
幸运的是，存在一个SDD的有用子类，它们能够保证对每棵语法分析树都存在一个求值顺序，因为它们不允许产生带有环的依赖图
-
不仅如此，接下来介绍的两类SDD可以和自顶向下及自底向上的语法分析过程一起高效地实现
-
S-属性定义 (S-Attributed Definitions, S-SDD)
-
L-属性定义 (L-Attributed Definitions, L-SDD)
小埋：S-属性定义与L-属性定义是什么呢
S-属性定义与L-属性定义
S - 属性定义
-
仅仅使用综合属性的SDD称为S属性的SDD，或S-属性定义、S-SDD
-
如果一个SDD是S属性的，可以按照语法分析树节点的任何自底向上顺序来计算它的各个属性值
-
S-属性定义可以在自底向上的语法分析过程中实现
L-属性定义
直观含义：在一个产生式所关联的各属性之间，依赖图的边可以从左到右，但不能从右到左
- 一个SDD是L-属性定义，当且仅当它的每个属性要么是一个综合属性，要么是满足如下条件的继承属性：假设存在一个产生式A→X1X2…Xn，其右部符号Xi (1<= i <= n)的继承属性仅依赖于下列属性：
-
A的继承属性
-
产生式中Xi左边的符号 X1, X2, … , Xi-1 的属性
-
Xi本身的属性，但Xi 的全部属性不能在依赖图中形成环路
每个S-属性定义都是L-属性定义
- 例子
总结
咱们玩归玩，闹归闹，别拿学习开玩笑。
语法制导翻译使用CFG来引导对语言的翻译，是一种面向文法的翻译技术。语法制导翻译将语义规则同语法规则（产生式）联系起来要涉及两个概念SDD和SDT,要好好掌握。
如果有收获？希望老铁们来个三连，点赞、收藏、转发
创作不易，别忘点个赞，可以让更多的人看到这篇文章，顺便鼓励我写出更好的博客
转载：https://blog.csdn.net/JAck_chen0309/article/details/104941356