Bonky Zhu
If someone is able to show me that what I think or do is not right, I will happily change, for I seek the truth, by which no one was ever truly harmed. It is the person who continues in his self-deception and ignorance who is harmed.

编译原理 – 语法制导翻译

image-20191125003738670

基本思想

语义信息的表示

为CFG(上下文无关文法)中的文法符号设置语义属性(变量类型,存储位置等等),用来表示语法成分对应的语义信息。

语义属性的计算

对于给定的输入串x ,构建x的语法分析树,并利用与产生式(语法规则)相关联的语义规则来计算分析树中各结点对应的语义属性值。

概念

  • 语法制导定义(Syntax-Directed Definitions, SDD) 将每个文法符号对应一个语义属性集合,每个产生式对应一组语义规则,这些规则用 于计算该产生式中各文法符号的属性值。
  • image-20191125004801716
  • 语法制导翻译方案 (Syntax-Directed Translation Scheme , SDT )如下图 的第一个产生式表示当我就出 T 的时候,我就可以利用 T.type 得到 L.inh
  • image-20191125004547392

语法制导定义SDD

综合属性

在分析树结点上的非终结符的综合属性只能通过树结点的子结点或本身的属性值来定义。

image-20191125005232071

终结符可以具有综合属性。终结符的综合属性值是由词法分析器提供的词法值,因此在SDD中没有计算终结符属性值的语义规则。下图中的副作用类似一个函数调用的过程,和其他的属性没有关系。

image-20191125005611896

继承属性

在分析树结点上的非终结符的继承属性只能通过树结点的父结点、兄弟结点或本身的属性值来定义。

image-20191125005433392

终结符没有继承属性。终结符从词法分析器处获得的属性值被归为综合属性值

image-20191125005619481

属性文法

一个没有副作用的SDD有时也称为属性文法(也就是说全部都是属性之间的关系)

SDD的求值顺序

语义规则建立了属性之间的依赖关系,在对语法分析树节点的一个属性求值之前,必须首先求出这个属性值所依赖的所有属性值。

依赖图

依赖图是一个描述了分析树中结点属性间依赖关系的有向图,一般来说综合属性放在左边,继承属性放在右边。

截屏2020-03-23下午12.24.13

可以对上面进行拓扑排序(详情见数据结构教材),其中画红线的是可以调换位置的。(如果图中没有环,那么至少存在一个拓扑排序)

截屏2020-03-23下午12.24.13

S-属性与L-属性

S-属性定义

仅仅使用综合属性的SDD称为S属性的SDD,或S-属性定义、S-SDD

如果一个SDD是S属性的,可以按照语法分析树节点的任何自底向上顺序来计算它的各个属性值

也可以理解为,产生式的左部符号只依赖于右部符号。

L-属性定义

在一个产生式所关联的各属性之间, 依赖图的边可以从左到右,但不能从右到左。L-属性定义包括S-属性定义。

也可以理解为,产生式的符号中右边的总是依赖左边的,如 A->BC 那么 C 只取决于 B 和 A ,B 只取决于 A。

语法制导翻译方案SDT

将S-SDD转换为SDT

将一个S-SDD转换为SDT的方法:将每个语义动作都放在产生式的最后

image-20191125012142020

将L-SDD转换为SDT

image-20191125012742313

Share

You may also like...

发表评论