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

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

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

一、依赖图

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

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月前
|
自然语言处理 编译器
编译原理复习五:属性文法与三地址码的生成(附题目与答案 超详细)
编译原理复习五:属性文法与三地址码的生成(附题目与答案 超详细)
453 0
|
存储 C语言
C语言题目的多种解法分享 2之字符串左旋和补充题
C语言题目的多种解法分享 2之字符串左旋和补充题
74 0
|
6月前
|
自然语言处理 算法 编译器
编译原理复习一:正则表达式-NFA NFA-DFA DFA最小化(附题目与答案 超详细)
编译原理复习一:正则表达式-NFA NFA-DFA DFA最小化(附题目与答案 超详细)
269 0
|
4月前
|
存储 算法 程序员
C语言编程—递归
递归是函数自我调用的编程技术,常用于解决分治问题,如计算阶乘和斐波那契数列。示例中展示了C语言的阶乘和斐波那契数列递归实现。递归需满足:问题可转化为规模更小的同类问题,存在结束条件以防止无限循环,并可能消耗大量时间和栈空间。栈用于存储函数调用信息,过多递归可能导致栈溢出。递归虽简洁,但非最优效率选择,递推算法通常是更好的替代方案。
42 0
|
5月前
|
C语言
C语言学习记录——用递归思想求第n个斐波那契数,函数递归
C语言学习记录——用递归思想求第n个斐波那契数,函数递归
26 0
|
算法 程序员 C语言
全排列思路解析附C语言实现
全排列思路解析附C语言实现
|
6月前
|
自然语言处理 算法 编译器
编译原理复习四:编译器结构 消除左递归、左公因子 最右推导 寻找句柄讲解(附题目和答案)
编译原理复习四:编译器结构 消除左递归、左公因子 最右推导 寻找句柄讲解(附题目和答案)
146 0
|
机器学习/深度学习 Java 程序员
教你精通Java语法之第十二章、递归
内层函数调用(子集处理)完成,外层函数才能算调用完成。
65 0
|
算法 程序员 C语言
【C语言】递归实战,通过几个例子带你深入走进递归算法
【C语言】递归实战,通过几个例子带你深入走进递归算法
491 0
|
C++
C++ Primer Plus 第五章答案 循环和关系表达式
只有聪明人才能看见的摘要~( ̄▽ ̄~)~
62 0