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

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

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

一、依赖图

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

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两掺的串)。若叶子仅由终结符标记(+ 、- 、* 之类的运算符号也算是终结符),则构成一个句子。

Sa {S.h=1}

LL(1), S {L.h=L(1).h+S.h}

LS {L.h=S.h}

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

答案如下

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

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

相关文章
|
6月前
|
自然语言处理 编译器
编译原理复习五:属性文法与三地址码的生成(附题目与答案 超详细)
编译原理复习五:属性文法与三地址码的生成(附题目与答案 超详细)
463 0
|
5月前
|
C语言
C语言学习记录——操作符习题、算数转换习题,多解法&优解法&单选题
C语言学习记录——操作符习题、算数转换习题,多解法&优解法&单选题
28 1
|
算法 程序员 C语言
全排列思路解析附C语言实现
全排列思路解析附C语言实现
|
6月前
|
存储 C语言
【C语言初阶】什么操作符你还没搞懂?试试这篇文章让你彻底理解各种操作符!
【C语言初阶】什么操作符你还没搞懂?试试这篇文章让你彻底理解各种操作符!
65 1
|
C语言
《C语言初阶篇》听说你还不会for循环的变种写法?一文教你彻底搞懂循环语句!
《C语言初阶篇》听说你还不会for循环的变种写法?一文教你彻底搞懂循环语句!
213 0
|
算法 程序员 C语言
【C语言】递归实战,通过几个例子带你深入走进递归算法
【C语言】递归实战,通过几个例子带你深入走进递归算法
510 0
|
C++
C++ Primer Plus 第五章答案 循环和关系表达式
只有聪明人才能看见的摘要~( ̄▽ ̄~)~
65 0
【C语言】函数和递归的基础题目
【C语言】函数和递归的基础题目
|
存储 编译器
【C】指针——知识点大全(详细,简洁,含例题)(一)
【C】指针——知识点大全(详细,简洁,含例题)
|
存储 编译器 C语言
初阶C语言 第四章-------《操作符》 (逻辑操作符,算术操作符,逗号表达式,三目操作符)知识点+基本练习题+深入细节+通俗易懂+完整思维导图+建议收藏
初阶C语言 第四章-------《操作符》 (逻辑操作符,算术操作符,逗号表达式,三目操作符)知识点+基本练习题+深入细节+通俗易懂+完整思维导图+建议收藏