编译原理复习六：依赖图、注释语法树上节点的求值讲解（附题目与答案超详细）

矫情吗；* 2023-09-30 19:50 6阅读 0赞

> **需要原卷和答案请点赞关注收藏后评论区留言私信~~~**

## 一、依赖图 ##

依赖图是用来描述相应语法树中属性的信息流；从一个属性的边到另一个需要通过计算第一个属性得到第二个属性。边的表达要遵循语法规则。

1.对于每一个分析树的节点而言，假设有一个节点定义为语法符号X，依赖图就存在与X相关的每一个属性的节点。

2.假设一个与产生式P相关的语义规则根据X.c的值定义了综合属性A.b的值。然后，依赖图从X.c到A.b出现了一条边。更准确地说，在每一个节点N标记了与产生式P相关的A，在节点N生成属性b的边，从N的子节点属性b对应着产生式中符号X的实例。

3.假设一个与产生式P相关的语义规则根据X.a的值定义了继承属性B.c的值。之后，依赖图从X.a到B.c出现了一条边。对于每一个节点N标记了产生式P中的B，生成从节点N属性c到节点M属性a的边。

![8ca17026132040d8a95d3cb712c68321.png][]

![4ea949d843b44adeb4c0d54a4d10b851.png][]

> 所以我们可以明确这类题目的做题步骤
> 
> 1：根据输入串构造对应语法树
> 
> 2：根据语义规则找出各个节点的综合属性和继承属性，然后在语法树上画出依赖图
> 
> 3：根据依赖图顺序求值

## 二、注释语法树的求值 ##

**语法分析树和语法树不是一种东西**。习惯上，我们把前者叫做“具体语法树”，其能够体现推导的过程；后者叫做“抽象语法树”，其不体现过程，只关心最后的结果。

### 语法分析树 ###

语法分析树是语言推导过程的图形化表示方法。这种表示方法反映了语言的实质以及语言的推导过程。

定义：对于 CFG G 的句型，分析树被定义为具有下述性质的一棵树：

注释语法树可以简单的理解为各个节点带有属性和值的语法树

注释语法树的求值步骤如下：画出依赖图后找出各个属性间的依赖关系，求一个节点的值时需要求出这个节点所依赖的节点的值，即可以用拓扑排序来给出一种求值顺序，下面以具体题目进行讲解

Consider the attribute grammar, where h is the attribute of S and L

***S******→******(L)******\{S.h=L.h×2\}***

1.  根由开始符号所标记；
2.  每个叶子由一个终结符、非终结符或 ε 标记；
3.  每个内部节点都是非终结符；
4.  若 A 是某节点的内部标记，且 X1、X2...Xn 是该节点从左到右的所有孩子的标记。则：A→X1X2...Xn 是一个产生式。若 A→ε，则标记为 A 的节点可以仅有一个标记为 ε 的孩子。若 A→ε ，则标记为 A 的节点可以仅有一个标记为 ε 的孩子。
5.  每一直接推导（每个产生式），对应一颗仅有父子关系的子树，即产生式左部非终结符“长出”右部的孩子；
6.  分析树的叶子，从左到右构成 CFG G 的一个句型（T、N两掺的串）。若叶子仅由终结符标记（+ 、- 、\* 之类的运算符号也算是终结符），则构成一个句子。

***S******→******a******\{S.h=1\}***

***L******→******L******(1)******, S******\{L.h=L******(1)******.h+S.h\}***

***L******→******S******\{L.h=S.h\}***

Draw the dependency graph for string ***(a,a)*****.** What’s final value of ***S.h*** for string ***(a,a)***

答案如下

箭头指向表示各个之间的依赖关系，然后节点对应属性的值标上去即可

![c485d5a64da7485ba58887b0e3adbedd.png][]

**创作不易 觉得有帮助请点赞关注收藏~~~**

[8ca17026132040d8a95d3cb712c68321.png]: https://img-blog.csdnimg.cn/8ca17026132040d8a95d3cb712c68321.png
[4ea949d843b44adeb4c0d54a4d10b851.png]: https://img-blog.csdnimg.cn/4ea949d843b44adeb4c0d54a4d10b851.png
[c485d5a64da7485ba58887b0e3adbedd.png]: https://img-blog.csdnimg.cn/c485d5a64da7485ba58887b0e3adbedd.png