Arya

第五章 语法制导翻译 note
[+] 出门和好朋友一起吃饭就很开心~然后又去抓了娃娃,我竟然抓到了两个,第一次玩抓娃娃机啊[+] 又逢烟雨又逢君...
扫描右侧二维码阅读全文
02
2019/02

第五章 语法制导翻译 note

[+] 出门和好朋友一起吃饭就很开心~然后又去抓了娃娃,我竟然抓到了两个,第一次玩抓娃娃机啊
[+] 又逢烟雨又逢君
[+] 明天要抓紧学习了啊,希望年前可以看完编译原理

第五章 语法制导翻译 note

语法制导翻译概述

编译的阶段

  • 词法分析
  • 语法分析
  • 语义分析
  • 中间代码生成
  • 代码优化
  • 目标代码生成

语义分析阶段通常和中间代码生成阶段放在一起,称为语义翻译。
语义翻译阶段和语法分析阶段放在一起,称为语法制导翻译(Syntax-Directed Translation)

语法制导翻译使用CFG来引导对语言的翻译,是一种面向文法的翻译技术。

语法制导翻译的基本思想
语义信息的表示方法:

  • 在语法制导翻译中,为CFG中的文法符号设置语义属性,用来表示语法成分对应的语义信息

语义属性的表示方法:

  • 文法符号的语义属性值是用与文法符号所在产生式(语法规则)相关联的语义规则来计算的
  • 对于给定的输入串x,构建x的语法分析书,并利用与产生式(语法规则)相关联的予以规则来计算分析树中各节点对应的语义属性值

语义规则语法规则(产生式)联系起来涉及两个概念

  • 语法制导定义(Syntax-Directed Definitions,SDD)
  • 语法制导翻译方案(Syntax-Directed Translation Scheme,SDT)

语法制导翻译(SDD)
SDD是对CFG的推广

  • 将每个文法符号和一个语义属性集合相关联
  • 将每个产生式和一组语义规则相关联,这些规则用于计算该产生式种各文法符号的属性值

如果X是一个文法符号,a是X的一个属性,则用X.a表示属性a在某个标号为X的分析树结点上的值

接下来举了一个例子

产生式语义规则
D->TL
T->int
T->real
L->L1,id
L.inh=T.type
T.type=int
T.type=real
L1.inh=L.inh

语法制导翻译方案(SDT)
SDT是在产生式右部嵌入了程序片段的CFG,这
些程序片段称为语义动作。按照惯例,语义动作
放在花括号内
例:

D → T { L.inh = T.type } L #1
T → int { T.type = int } #2
T → real { T.type = real } #3
L → { L1.inh = L.inh }L1, id #4

1表示,当分析出T以后,我们可以利用T的type值来计算出L的inh属性值;
2、3表示,当我们计算出右边的符号都分析出来以后,我们就可以来计算产生式左部T的属性值type
4表示在分析L1的inh属性值之前,我们就可以根据L的inh属性值得知L1的inh属性值

可见一个语义动作在产生式中的位置决定了这个动作的执行时间。

接下来对比一下SDD与SDT
SDD

  • 是关于语言翻译的高层次规格说明
  • 隐蔽了许多具体实现细节,使用户不必显式地说明翻译发生的顺序

SDT

  • 可以看作是对SDD的一种补充,是SDD的具体实施方案
  • 显式地指明了语义规则的计算顺序,以便说明某些实现

语法制导定义SDD

语法指导定义SDD
语法指导定义SDD是对CFG的推广

  • 将每个文法符号和一个语义属性集合相关联
  • 将每个产生式和一组语义规则相关联,用来计算该产生式中个文法符号的属性值

文法符号的属性

  • 综合属性(synthesized attribute)
  • 继承属性(inherited attribute)

接下来分别解释这两种属性

综合属性(synthesized attribute)
在分析树节点N上的非终结符A的综合属性只能通过N的子结点N本身的属性值来定义

接下来举了一个例子

Image5-3.png

终结符可以具有综合属性。终结符的综合属性值
由词法分析器提供的词法值,因此在SDD中没有计
算终结符属性值的语义规则

继承属性(inherited attribute)
在分析树结点 N上的非终结符A的继承属性只能通过
N的父结点N的兄弟结点N本身的属性值来定义

接下来举了一个例子

Image5-4.png

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

接下来举了一个带有综合属性的SDD例子

Image5-5.png

这里的digit是一个终结符,它的综合属性值是由词法分析器提供的词法值lexvalETF分别表示expresstermfactor,我们分别给ETF设置了属性val。通过第三个产生式的语义规则,我们可以看出Eval属性值是由它的子结点定义的,因此valE的一个综合属性,TF也是如此。

语义规则也可以写成过程调用的形式,为了产生一个副作用,比如打印一个运算结果,这时候可以把它看成是用来定义产生式左部的文法符号的综合属性的规则,因为它用到了子结点的属性值

例如我们现在输入

3*5+4n

这就是它的语法分析树

Image5-6.png

又举了一个带有继承属性L.in的SDD的例子

Image5-7.png

这里可以看出Linh属性,是由它的兄弟结点属性或者是它的父结点的属性值(L1.inh=L.inh)来定义的,因此inhL的继承属性

属性文法(Attribute Grammar)
一个没有副作用的SDD有时也称为属性文法

  • 属性文法的规则仅仅通过其它属性值和常量来定义一个属性值

SDD的求值顺序

SDD为CFG中的文法符号设置语义属性。对于给定的输入串x,应用语义规则计算分析树中各结点对应的属性值

那么我们按照什么顺序计算属性值?

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

依赖图(Dependency Graph)

  • 依赖图是一个描述了分析树中结点属性间依赖关系的有向图
  • 分析树中每个标号为X的结点的每个属性a都对应着依赖图中的一个节点
  • 如果属性X.a的值依赖于属性Y.b的值,则依赖图中有一条从Y.b的结点指向X.a的结点的有向边

接下来举了一个例子

Image5-8.png

右侧是这个句子的注释分析树对应的依赖图(语法分析树),在这个依赖图中,注释分析树中的每一个属性,都对应着依赖图中的一个结点,为了区别起见,我们将继承属性放在语法分析树中对应结点的左边,将综合属性放在对应结点的右边

属性值的可计算顺序

  • 可行的求值顺序是满足下列条件的结点序列N1,N2, … , Nk :如果依赖图中有一条从结点Ni到 Nj
    的边(Ni→Nj), 那么i < j(即:在节点序列中,Ni

排在Nj 前面)

  • 这样的排序将一个有向图变成了一个线性排序,
    这个排序称为这个图的拓扑排序

接下来我们用1~10为上面的依赖图进行编码

Image5-9.png

其中依赖者的属性序号大于被依赖者的属性序号

  • 对于只具有综合属性的SDD ,可以按照任何自底向上的顺序计算它们的值
  • 对于同时具有继承属性综合属性的SDD,不能保证存在一个顺序来对各个节点上的属性进
    行求值

接下来举了一个例子

产生式语义规则
A->BA.s=B.i
B.i=A.s+1

可以看出A的属性s,是A综合属性;同样地,我们可以看出iB继承属性

可以得出依赖图

Image5-10.png

可以看出形成了循环依赖,也即形成了环,我们就无法看出是先计算As属性,还是Bi属性

如果图中没有环,那么至少存在一个拓扑排序

  • 从计算的角度看,给定一个SDD,很难确定是否在某棵语法分析树,使得SDD的属性之间存在循环依关系
  • 幸运的是,存在一个SDD的有用子类,它们能够证对每棵语法分析树都存在一个求值顺序,因为它们不允许产生带有环的依赖图
  • 不仅如此,接下来介绍的两类SDD可以和自顶向下及自底向上的语法分析过程一起高效地实现
    S-属性定义 (S-Attributed Definitions, S-SDD)
    L-属性定义 (L-Attributed Definitions, L-SDD)

S-属性定义与L-属性定义

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

接下来举了一个例子

产生式语义规则
(1) L->EnL.val = E.val
(2) E->E1 + TE.val = E1.val + T.val
(3) E->TE.val = T.val
(4) T->T1 * FT.val = T1.val × F.val
(5) T->FT.val = F.val
(6) F->( E )F.val = E.val
(7) F->digitF.val = digit.lexval
  • 如果一个SDD是S属性的,可以按照语法分析树节点的任何自底向上顺序来计算它的各个属性值
  • S-属性定义可以在自底向上的语法分析过程中实现

L-属性定义

L-属性定义(也称为L属性的SDDL-SDD
直观含义:在一个产生式所关联的各属性之间,依赖图的边可以从左到右,但不能从右到左,(因此称为L属性的,L是Left的首字母)

正式定义

  • 一个SDD是L-属性定义,当且仅当它的每个属性要么是一个综合属性,要么是满足如下条件的继承属性:假设存在一个产生式A→X1X2…Xn,其右部符号Xi (1≤i≤n)的继承属性仅依赖于下列属性:
    A的继承属性
    产生式中Xi左边的符号 X1, X2, … , Xi-1 的属性
    Xi本身的属性,但Xi的全部属性不能在依赖图中形成环路

由上也可以看出:每个S-属性定义也都是L-属性定义

当然有个小问题,为什么子节点Xi的继承属性只能依赖于A的继承属性,而不是A的综合属性呢?

这是因为父节点的综合属性可以依赖于子节点的属性, 当然就包括子节点的继承属性,如果子节点的继承属性再依赖于父节点的综合属性就会造成循环依赖

如下图

Image5-11.png

接下来举了一个L-SDD的例子

Image5-12.png

以及一个非L属性的SDD

Image5-13.png

在这里Q的继承属性,依赖于右部兄弟节点R的属性,违反了L属性的限制

语法制导翻译方案SDT

语法制导翻译方案(SDT)是在产生式右部中嵌入了程序片段(称为语义动作)的CFG

例如

D → T { L.inh = T.type } L
T →  int { T.type = int }
T →  real { T.type = real }
L → { L1inh = L.inh }L1 

SDT可以看作是SDD的具体实施方案

而本节主要关注如何使用SDT来实现两类重要的SDD,因为在这两种情况下,SDT可在语法分析过程中实现

  • 基本文法可以使用LR分析技术,且SDD是S属性的
  • 基本文法可以使用LL分析技术,且SDD是L属性的

将S-SDD转换为SDT

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

例如

Image5-14.png

S-属性定义的SDT实现
如果一个S-SDD的基本文法可以使用LR分析技术,那么它的SDT可以在LR语法分析过程中实现

Image5-15.png

为了在LR语法分析的同时进行语义分析,我们就要将LR的语法分析站进行扩展,即,在分析站中使用一个附加的域来存放综合属性值

Image5-16.png

如果希望这个栈支持多个属性,那么我们需要

  • 使站记录变得足够大
  • 在栈记录中存放指针

而且我们需要将语义动作中的抽象定义改写成具体可执行的栈操作

Image5-17.png

接下来举了一个在自底向上语法分析栈中实现桌面计算器的例子

Image5-18.png

假设我们输入的是

3*5+4

这里直接给出结果

Image5-19.png

过程老师讲的十分详细,写出来又要写好久(反正我记在脑子里了~)

将L-SDD转换为SDT

将L-SDD转换为SDT的规则

  • 将计算某个非终结符号A的继承属性的动作插入到产生式右部中紧靠在A的本次出现之前的位置上
  • 将计算一个产生式左部符号的综合属性的动作放置在这个产生式右部的最右端

接下来是一个例子

Image5-20.png

(不难~)

L-属性定义的SDT实现
如果一个L-SDD的基本文法可以使用LL分析技术,那么它的SDT可以在LL或LR语法分析过程中实现

接下来是个例子

Image5-21.png

其中判断一个文法是不是LL文法,关键在于含有相同左部的产生式的SELECT集是否互不相交

LL分析具体又分为两种情况

  • 在非递归的预测分析过程中进行语义翻译
  • 在递归的预测分析过程中进行语义翻译

下面会一一介绍

在非递归的预测分析过程中进行翻译

要在非递归的预测分析中进行翻译,我们也需要对语法分析栈进行扩展

Image5-22.png

接下来举个例子演示如何实现语法制导翻译方案

1) T → F { T′.inh = F.val } T′ { T.val = T′.syn }
2) T′ → *F { T1′.inh = T′.inh×F.val } T1′ { T′.syn = T1′.syn }
3) T′ → ε { T′.syn = T′.inh }
4) F → digit { F.val = digit.lexval }

我们需要将上面的产生式改写

Image5-23.png

在上面的产生式中有6个语义动作,那么我们分别用a1~a6这些符号(称为动作符号)来替换原来的语义动作

接下来通过一个输入的例子来解释

Image5-24.png

这例子老师解释的也很好
推荐看视频

分析占中的每一个记录都对应着一段执行代码

  • 综合记录出栈时,要将综合属性值复制给后面特定的语义动作
  • 变量展开时(即变量本身的记录出栈时),如果其含有继承属性,则要将继承属性值复制给后面特定的语义动作

一个SDT确定下来以后,这个SDT各个符号对应的执行代码也就确定下来了

接下来举了一个例子

Image5-25.png

我们先看第一条产生式

 T → F {a1:T′.inh=F.val} T′ {a2:T.val=T′.syn}

在这个产生式右部有四个符号Fa1T'a2,由于FT'具有综合属性,这四个符号实际上对应6个记录,分别是FFsyna1T'T'syna2,接下来我们开始分析

符号属性执行代码
F
Fsynvalstack[top-1].Fval = stack[top].val;top=top-1;
a1Fvalstack[top-1].inh = stack[top].Fval;top=top-1;
T′inh根据当前输入符号选择产生式进行推导
若选 2): stack[top+3].T′inh =stack[top].inh; top=top+6;
若选 3): stack[top].T′inh =stack[top].inh;
T′synsynstack[top-1].T′syn = stack[top].syn;top=top-1;
a2T′synstack[top-1].val = stack[top].T′syn;top=top-1;

分析第二个产生式

T′ → *F{a3:T1′.inh=T′.inh×F.val}T1′{a4:T′.syn=T1′.syn}
符号属性执行代码
*
F
Fsynval stack[top-1].Fval = stack[top].val;top=top-1;
a3T΄inh; Fvalstack[top-1].inh = stack[top].T′inh× stack[top].Fval;top=top-1;
T1′inh根据当前输入符号选择产生式进行推导
若选2): stack[top+3].T′inh = stack[top].inh; top=top+6;
若选3): stack[top].T′inh = stack[top].inh;
T1′synsynstack[top-1].T1′syn = stack[top].syn;top=top-1;
a4T1′synstack[top-1].syn = stack[top].T1′syn;top=top-1;

分析第三个产生式

T′ → ε {a5:T′.syn = T′.inh
符号属性执行代码
a5T′inhstack[top-1].syn = stack[top].T′inhtop=top-1;

以及第四个产生式

4)  F →  digit {a:F.val = digit.lexval
符号属性执行代码
digitlexvalstack[top-1].digitlexval = stack[top].lexval; top=top-1;
a6digitlexvalstack[top-1].val = stack[top].digitlexval; top=top-1;

详细讲解可以参考视频

在递归的预测分析中进行翻译

递归的预测分析中,每一个非终结符都对应着一个过程,那么在语义翻译中,我们要继承非终结符的继承属性和综合属性,因此我们将非终结符对应的过程扩展成为一个函数,这个函数的参数就是该非终结符的继承属性值返回值则是该属性的综合属性值

接下来举了一个例子

Image5-26.png

其中黑色字体表示原有的语法分析器中T'对应的过程,蓝色字体部分是扩展的部分

T'的继承属性inh为该函数的形参部分,综合属性syn为该函数的返回值

接下来构造非终结符T对应的函数

Image5-27.png

非终结符F对应的函数

Image5-28.png

最后是分析其对应的主函数

Desent(){
    D:Tval;
    Getnext(token);
    Tval = T(token);
    if token ≠ “$” then Error;
    return ;
}

总结一下算法

  • 为每个非终结符A构造一个函数,A的每个继承属性对应该函数的一个形参,函数的返回值是A的综合属性值。对出现在A产生式中的每个文法符号的每个属性都设置一个局部变量
  • 非终结符A的代码根据当前的输入决定使用哪个产生式
    与每个产生式有关的代码执行如下动作:从左到右考虑
  • 产生式右部的词法单元、非终结符及语义动作
    对于带有综合属性x的词法单元 X,把x的值保存在局部变量X.x中;然后产生一个匹配 X的调用,并继续输入
    对于非终结符B,产生一个右部带有函数调用的赋值语句c := B(b1 , b2 , …, bk),其中, b1 , b2 , …, bk是代表B的继承属性的变量,c是代表B的综合属性的变量
    对于每个动作,将其代码复制到语法分析器,并把对属性的引用

在递归的预测分析过程中进行翻译

L-属性定义的自底向上翻译
给定一个以LL文法为基础的L-SDD,可以修改这个文法,并在LR语法分析过程中计算这个新文法之上的SDD

举个例子

Image5-29.png

在这个SDT中有两个内嵌的语义动作,导致无法实现自底向上的语义翻译,我们使用标记非终结符MN分别表示这两个语义动作

Image5-30.png

N的空产生式对应的动作中,我们使用N.i1表示T'.inhN.i2表示E.val,并用N.s获取二者乘积,实现原来的语义动作T1′.inh = T′.inh×F.val,M也是同理

那么此时,修改后的SDT中,所有语义动作都位于产生式末尾。

接下来,具体实现修改后的SDT

Image5-32.png

在将语义动作改写为可执行的栈操作

Image5-31.png

小结
给定一个以LL文法为基础的L-属性定义,可以修改这个文法,并在LR语法分析过程中计算这个新文法之上的SDD

  • 首先构造SDT,在各个非终结符之前放置语义动作来计算它的继承属性,并在产生式后端放置语义动作计算综合属性
  • 对每个内嵌的语义动作,向文法中引入一个标记非终结符来替换它。每个这样的位置都有一个不同的标记,并且对于任意一个标记M都有一个产生式M→ε
  • 如果标记非终结符M在某个产生式A→α{a}β中替换了语义动作a,对a进行修改得到a' ,并且将a'关联到M→ε 上。动作a'
    (a) 将动作a需要的A或α中符号的任何属性作为M的继承属性进行复制
    (b) 按照a中的方法计算各个属性,但是将计算得到的这些属性作为M的
    综合属性
Last modification:February 2nd, 2019 at 11:29 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment