属性文法与语法制导翻译 一

这部分为语义分析与中间代码生成部分。

属性文法

给产生式配上语义规则得到属性文法。 能够得到句子的语法结构,还能得到语法树中每个节点的属性值,实现了语义的分析

  1. 为每个文法配备了值(属性),如语义规则中的val,代表与文法符号相关的信息,用来存放非终结符对应的表达式(子表达式 项 因子 等) 除了存放具体数值,还可以用来记录类型,代码序列,符号表内容等。
  2. 对于文法得每个产生式配备了一组属性的语义规则(有些属性文法中一个产生式可以配备多个于异规则),说明了语法规则/产生式 涉及的语法单位之间的关系。 如 E的val 是由 右边的E1 与 T的val相加得到。凡是能用程序实现的信息处理都可以成为语义规则

image-20201108102215262

属性包括综合属性和继承属性两类

综合属性

用来自下而上传递信息。

有一些节点的属性可以根据自身属性进行计算。 子节点和本身的属性计算得到。

image-20201108102703278

继承属性

自上而下的传递信息

addtype函数,在符号表中找到id对应的入口,并把入口的类新信息设置成L.in.

语法树上看,是根据父节点和兄弟节点的属性计算子节点的继承属性。

image-20201108103910930

属性依赖

c1 c2 ck是某些符号的某些属性,b是要设置的属性。

image-20201108104345671

如 右部的L.in依赖于兄弟节点T.type,终结符只有综合属性。并且由于没有子节点,所以不能从子节点计算,需要有词法分析器提供。

开始符号如果有继承属性,所有属性都应该事先设置好

image-20201108104730821

语义规则

描述产生式中出现的语法符号的属性之间的相互关系。 通过函数计算体现。

语义规则扩充了上下文无关文法。用于说明产生式中出现的语法符号对应的属性的计算方法。

image-20201108105431222

image-20201108110059909

产生式右边的符号的综合属性不应该由这个产生式的语义规则来描述。

带注释的语法树

对语法树中的节点标注上对应属性值

image-20201108112042886

综合属性语法树 自下而上

image-20201108113845077

语法树构造过程和属性计算过程可以合并,构造完语法树的时候,每个结点的综合属性也计算完了。 归约时按照语义规则来计算父节点的属性

image-20201108125714713

继承属性语法树 自上而下

类型信息可以传递到每个标识符上

image-20201108125953044

image-20201108130558887

real属性从左到右传递到了变量的每个标识符上。

属性计算

属性文法在上下文无关文法的基础上扩充了语义与语义计算规则。

由源程序的语法结构驱动的处理办法就是语法制导翻译法

image-20201108132057847

image-20201108132221935

三种按照语义规则进行属性计算的方法。

  • 依赖图
  • 树遍历
  • 一遍扫描

依赖图方法

通过寻找属性之间的依赖关系来确定属性计算的先后顺序,选择相应的语义规则完成属性计算。

image-20201108132850252

image-20201108133124462

image-20201108133236696

建立依赖图的节点

image-20201108133631644

image-20201108134007106

虚线部分语法图,实线部分依赖图

image-20201108134121170

image-20201108134220294

需要多遍扫描

计算顺序示例

image-20201108134658483

实现了变量声明语句的语法和语义分析(包含对符号表的操作)

树遍历

不构造依赖图直接以某种方法遍历(多次扫描)语法树。

image-20201108135610759

image-20201108140320854

递归实现深度优先,递归前先计算继承属性,完成一个节点访问后,再计算该节点的综合属性。

树遍历示例

image-20201108141335717

注意开始符号的继承属性和终结符的综合属性都是一开始给出的(不是算出来的)

递归遍历子树,进一步递归(VistNode)前先计算继承属性(算不出来就不算先),直到所有属性都被计算出来

  • 第一次扫描(注意最后还要计算S的继承属性,不过第一次什么都算不出来)

    image-20201108142334364

  • 第二次扫描

    image-20201108142800580

  • 第三次扫描

    image-20201108142933323

之后整棵树所有属性计算完毕,算法结束。

一遍扫描

前面两种方法都需要先对输入串进行一遍扫描,建立语法树。效率偏低

而一遍扫描方法只需要进行一遍扫描,语法分析同时计算属性值,语法分析结束,语法树构造完毕,所有结点的属性也计算完毕。

image-20201108144439917

以S-属性文法与自下而上语法分析程序,一遍扫描进行属性计算为例

抽象语法树

AST中没有非终结符,直接用运算符代表运算符作用在子节点对应值之后的结果。

作为源程序的中间代码表示。

设计中缀表达式翻译抽象语法树的属性文法

image-20201108150526215

nptr指的是“子树”(指向节点的指针) 注意这些属性全部都是综合属性 可以配合自底向上的语法分析器工作。

image-20201108151301165

分析示例

根节点E.nptr指向的节点就是抽象语法树的根。 自下而上的语法分析,和属性计算一起运行,只扫描了一次。归约的时候进行属性计算。

image-20201108152158515

文章目录