需要原卷和答案请点赞关注收藏后评论区留言私信~~~
一、依赖图
依赖图是用来描述相应语法树中属性的信息流;从一个属性的边到另一个需要通过计算第一个属性得到第二个属性。边的表达要遵循语法规则。
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}
- 根由开始符号所标记;
- 每个叶子由一个终结符、非终结符或 ε 标记;
- 每个内部节点都是非终结符;
- 若 A 是某节点的内部标记,且 X1、X2...Xn 是该节点从左到右的所有孩子的标记。则:A→X1X2...Xn 是一个产生式。若 A→ε,则标记为 A 的节点可以仅有一个标记为 ε 的孩子。若 A→ε ,则标记为 A 的节点可以仅有一个标记为 ε 的孩子。
- 每一直接推导(每个产生式),对应一颗仅有父子关系的子树,即产生式左部非终结符“长出”右部的孩子;
- 分析树的叶子,从左到右构成 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)
答案如下
箭头指向表示各个之间的依赖关系,然后节点对应属性的值标上去即可
创作不易 觉得有帮助请点赞关注收藏~~~