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

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

一、依赖图

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

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的边。

所以我们可以明确这类题目的做题步骤

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)

答案如下

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

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