形式语义Ch8 属性文法.docx
- 文档编号:4228333
- 上传时间:2023-05-06
- 格式:DOCX
- 页数:49
- 大小:183.84KB
形式语义Ch8 属性文法.docx
《形式语义Ch8 属性文法.docx》由会员分享,可在线阅读,更多相关《形式语义Ch8 属性文法.docx(49页珍藏版)》请在冰点文库上搜索。
形式语义Ch8属性文法
第八章属性文法
§8.1简述
属性文法(AttributeGrammar)的概念首先由Knuth在1968年提出。
顾名思意属性文法是带属性的一种文法。
虽称是文法,但它不是用来描述文法,而是用来描述文法符号的属性关系的。
因为其属性规则与产生式紧密相关,称它是面向文法的一种方法。
凡是与文法的相关的问题均可试用属性文法这一工具。
属性文法的最成功的应用是编译器的自动生成。
有过一些成功的系统,如GAG[kastens82],HLP[Raiha78],SDCG[paulson82];一些现实程序设计语言的编译程序前端,也用属性文法生成出来,其中包括pascal[kastens&etal82]和Ada[Unl&etal82]。
属性文法可用来描述代码生成和优化[Ganapthi&Fisher82][Neal&Amirchachy74],程序正确性与程序变换[Gernert75],数据流分析[Farrow77][Babich&Jazayerl78]。
Reps利用AG实现了基于属性文法的语言的程序设计环境[Peps83]。
为了方便起见,将knuth所提出的属性文法称为简单属性文法并记为AG。
在给出AG的形式定义之前,首先考虑一个文法例(8.1.0),它产生二进制数。
二进制数由0,1和小数点“.”组成。
G[R]:
1.R→N4.N→ND
2.R→N.N5.D→0(8.1.0)
3.N→D6.D→1
文法本身并不含什么意义,它只说明什么样的终极符串是合法的。
文法G[R]的合法终极符串(句子)为通常的二进制数,可带小数点,但至多能带一个小数点。
根据定义10.1,001、111等都是文法G[R]的合法句子。
那么它们究竟代表什么意义,可给出种种不同的定义。
假设就定义它们代表的是相应的十进制实数,比如前面几个二进制表示分别代表实数2.5,1和7。
若用R.V表示R串所对应的十进制数,用D.V表示D串所对应的十进制数,用N.V表示N串所对应的十进制数,用N.L表示N串的二进制长度,则显然其形式描述如图8.1.1所示。
上述假设说明语法符号R有一个属性,并且其属性名定为V;语法符号D有一个属性,并且其名定为V;语法符号N有两个属性,并且其属性名分别定为V和L。
图8.1.1是一种基于语法的属性求值规则式。
它们将构成属性文法的核心部分即规则部分。
从中可看出属性文法的特点是对每个语法符号确定一些属性,并给出各属性值的计算规则。
语法规则语义规则
r1:
R→N■R.v=N.v
r2:
R→N1.N2■R.v=N1.v+N2.v×2-N2.L
r3:
N→D■N.v=D.v,N.L=1
r4:
N→N1D■N.v=N1.v×2+D.v,N.L=N1.L+1
r5:
D→0■D.v=0
r6:
D→1■D.v=1
图8.1.1属性文法例(8.1.1)
从上述语义规则可以看出其含义是非常直观的。
但很显然属性文法的表示不是可执行的程序,如何用这些语义规则来求出属性值,是不那么明显的问题,因此需要说明。
下面将对此做简单介绍。
属性值的求值过程
总的问题是这样一种问题,即给了一个合法的终极符串,问其属性值如何求?
这里有时间和空间问题,因此很多人对属性求值方法进行了大量的研究.并提出了一些好方法。
我们暂不考虑那些特殊的方法,而是考虑最一般而容易理解的方法,因为在此只希望使读者能了解到属性值是可用语义规则来求出的。
具体计算过程可分为下面两大部分:
■STEP1:
首先构造所给句子的属性树。
属性树如图8.1.2所示,其中虚线部分表示各属性节点之间的关系。
在构造树时对于每个内节点标上对应产生式编号。
■STEP2:
利用属性的求值规则(语义规则)求属性树各结点的属性值,最终计算出根结点的属性值。
每次寻找一个能计算某属性值的结点,并用它所依赖的已知属性值求出其属性值。
上述结点可能很多,这时可任选其中的任何一个结点。
当求出根结点的所有属性值时终止。
对于属性文法(8.1.1),我们有图8.1.2所示的计算图。
§8.2简单属性文法
1968年knuth提出了属性文法概念,我们称这种属性文法为简单属性文法。
简单属性文法的特点之一是,给每个语法符号的每个属性起相应的属性符号。
为此引进下面符号:
■A(X)...............................表示X的属性符号集
■AI(X)..............................表示X的继承属性符号集
■AS(X)..............................表示X的综合属性符号集
其中X是语法符号,它们满足下面条件:
■AI(X)∪AS(X)=A(X),AI(X)∩AS(X)={}
■AI(Z)={}(Z为开始符),AI(t)={}(t为终极符)
属性分为继承属性和综合属性两大类。
综合属性的一般特点是其值依赖于儿子的属性,而继承属性的一般特点是其值依赖于父亲或兄弟的属性。
但这毕竟不是精确的说法,因此在定义属性时,对每个属性都要指出是继承性还是综合性。
假设有产生式A→A...A...A,且A有属性a,则由于有四个A,如果只写成A.a,则无法识别它指的是哪个A的属性a值。
因此我们将采用带下标的办法,比如用下产生式:
A→A1...A2...A3,
表示原产生式。
为方便计,我们把上述Ai称为A的别名。
简单属性文法的重要特点之一是把语法规则和语义规则完全分开写。
正是由于这个原因,迫使我们用别名以区分一个符号的不同出现。
假设有原始的产生式
p:
X0→X1X2..........Xnp
则以后将该产生式写成别名形式,即写成下面形式(别名式产生式):
p:
X0*→X1*X2*..........Xnp*
其中Xi*表示Xi的相应的别名。
实际上如果把p产生式中的第i个符号表示为(p,i),则即可分开相同符号的不同出现,但为了简单起见将采用Xi*的表示法,尽管它没有表示是哪一条产生式的。
■定义8.2.1.属性出现
设有产生式
p:
X0*→X1*X2*..........Xnp*
并且a∈A(Xi),0≤i≤np,则称Xi*.a为P产生式的一属性出现,并用AO(P)表示P产生式的属性出现之集:
AO(P)={Xi*.a|a∈A(Xi),0≤i≤np}.
[注]可用(a,k)或k.a的形式表示属性出现Xk*.a。
例8.2.1.对于属性文法(8.1.1)有
AO(4)={N1.V,N1.L,N2.V,N2.L,D.V}
AO
(2)={R.V,N1.V,N1.L,N2.V,N2.L}
■定义8.2.2.定义型出现应用型出现
设有p:
X0*→X1*X2*..........Xnp*,a∈A(Xi),0≤i≤np,则
(1)称Xi*.a∈AO(p)是定义型的,
若a∈AI(X0),i=0,或a∈AS(Xi),i>0。
(2)称Xi*.a∈AO(p)是应用型的,
若a∈AS(X0),i=0,或a∈AI(Xi),i>0。
(3)用DEF(p)表示AO(p)中的定义型属性出现之集,用APP(p)表示AO(p)中所有应用型属性出现之集。
它们之间的关系是:
AO(p)〓DEF(p)APP(p)
■定义8.2.3.合法性
称一个语义规则为合法的,若其左部是应用型的属性出现,而右部是由常量和产生式左部的继承属性以及产生式右部的属性组成的合法属性表达式。
假设有产生式
A→BCD
并且i和s分别是A的继承属性和B的综合属性,则根据定义不能有形如下面的语义规则式:
A.i=.......;B.s=.......
定义属性文法需要有一种专门用来定义属性文法的语言(称为属性文法定义语言),其中最早出现并应用于编译器自动生成中的属性定义语言为ALDIN。
我们不准备涉及语言的细节。
■定义8.2.4.产生式的属性相关图DGp
设有产生式p:
X0→X1...Xn,则产生式p的属性相关图定义为:
DGp=(DVp,DEp)
其中DVp是产生式p的所有属性出现的集合即DVp=AOP(p),而DEp则以上述属性出现作为结点的一些边的集合,具体如下:
DEp={(ati,atj)|ati,atj∈DVp,atj值依赖于ati值}
例8.2.2.考虑下面所述的属性文法(8.2.1),其中有三个非终极符(F,M,B)和三个终极符(.,0,1)。
该文法定义二进制小数。
F只有一个综合属性(val),M和B各有一个继承属性(pos)和一个综合属性(val)。
其中pos表示一个二进位的小数点后位数。
本属性文法的属性相关图如图8.2.2所示。
AI(F)={},AI(M)={pos},AI(B)={pos},
AS(F)={val},AS(M)={val},AS(B)={val}
产生式语义规则
1.F→.M■M.pos=1;F.val=M.val
2.M→B■B.pos=M.pos;M.val=B.val
3.M→BM1■B.pos=M.pos;M1.pos=M.pos+1
M.val=M1.val+B.val
4.B→0■B.val=0
5.B→1■B.val=2↑(-B.pos)
■定义8.2.5.句子的属性相关图DG(α)
(1)设L是一个给定语言,α是L的一句子,则α的属性树是这样一棵树,即在α的语法树的每个结点上附上属性域部分而所得到的带属性的语法树,记为AT(α)。
(2)设α是一句子,则把产生式的属性依赖关系DGp应用到α的属性树AT(α)所得到的图,称之为α的属性相关图,记为ADG(α)。
■定义8.2.6.良性属性文法
称属性文法AG是良性的,如果对任一句子α∈AG,其属性相关图ADG(α)都不包含任何环路。
■定义8.2.7.简单属性文法AG
简单属性文法AG是一个四元组:
AG=(D,S,R,F),其中
D:
DOMAIN部分。
这部分是类型定义部分,它们将用来说明属性的类型。
S:
SYMBOL部分。
这是定义语法符号和属性符号的部分。
对于每个语法符号指出是终极符还是非终极符(对此还指出是不是开始符?
),指出所有属性名,还指出其类别和类型。
R:
RULE部分。
其中给出语法规则和语义规则。
F:
FUNCTION部分。
其中自定义必要的函数。
例8.2.3.下面是(8.2.1)的AG描述
□DOMAIN部分空(因下面只用到了标准类型)
□SYMBOL部分:
start:
F
nonterm:
F↑val:
REAL
M↓pos:
INT↑val:
REAL
B↓pos:
INT↑val:
REAL
term:
0,1
其中↓表示继承属性,↑表示综合属性
□RULE部分:
同于图8.2.1
□FUNCTION部分空(因为没用到自定义函数)
例8.2.4.属性域部分例。
为了书写简单,我们将属性定义语言中的类型表示为论域方程的形式。
例如:
DOMAIN
ENV〓IDE→TYPE
STAT〓IDE→VAL
TYPE〓realT+boolT
VAL〓realV(REAL)+boolV(BOOL)
END
例8.2.5.考虑顺序语句"S1;S2"的语义描述。
假定语句的功能是给环境和状态,则输出一个状态,因此对语句的语法符号S可定义三个属性,其中有两个输入属性(继承属性符:
ε,σ),有一个输出属性(综合属性符:
σ')。
这三个属性的名字和属性类别可描述如下:
S↓ε:
ENV↓σ:
STAT↑σ':
STAT
在产生式"S→S;S"中,其右部共有四个继承性属性出现,而左部则有一个综合性属性出现,故语义规则中有五个规则式:
RULE:
S1→S2;S3■S2.ε〓S1.ε;
S2.σ〓S1.σ;
S3.ε〓S1.ε;
S3.σ〓S2.σ';
S1.σ'〓S3.σ'
我们也可把属性模式取为如下:
S↓ε:
ENV↑φ:
[STAT→STAT]
这时相应的语义规则可如下:
RULE:
S1→S2;S3■S2.〓S1.;S3.ε〓S1.;
S1.φ〓(S2.φ)。
(S3.φ)
例8.2.6.考虑说明"D→D;D|varid:
T"的语义问题。
假设说明的功能是给一个环境,则输出一个环境。
这样可给语法符号D确定两个属性,其中前者是继承的,而后者是综合的:
D↓ε:
ENV↑ε':
ENV
T↓ε:
ENV↑t:
TYPE
下面是语义规则部分:
RULE:
D1→D2;D3■D2.ε〓D1.ε;
D3.ε〓D2.ε';
D1.ε'〓D3.ε';
D→varid:
T■T.ε〓D.ε;
D.ε'〓(D.ε)[id.s→T.t]
其中s是id的综合属性符,id.s则表示对应id的实际标识符。
例8.2.7.考虑赋值语句的属性文法。
在赋值语句中用到表达式,因此也要涉及到表达式的属性文法。
对于表达式和赋值语句可有以下两种属性定义(省略了类型部分):
[1]S↓ε↓σ↑σ'
E↓ε↓σ↑v
[2]S↓ε↑φ
E↓ε↑β
下面是赋值语句id:
=E的属性规则式部分:
[1]S→id:
=E■E.〓S.;E.〓S.;S.'〓(S.)[E.v/id.s]
[2]S→id:
=E■E.〓S.;S.'〓.[(E.)/id.s]
在这里我们假设了环境是标识符到值的映射,并且没考虑语义错误的检查问题。
例8.2.8.下面是条件语句的属性规则部分:
[1]S→ifEthenS1elseS2
■E.〓S.;E.〓S.;
S1.〓S.;S1.〓S.;
S2.〓S.;S2.〓S.;
S.'〓(E.v→S1.',S2.')
[2]S→ifEthenS1elseS2
■E.〓S.;S1.〓S.;S2.〓S.;
S.φ〓.((E.)→(S1.φ),(S2.φ))
例8.2.9.
考虑循环语句whileEdoS的语义描述问题。
当用上述第一属性模式时,将会遇到不可抗拒的阻力,读者不妨试一试。
下面将给出在第二种属性模式下的语义描述。
具体属性规则如下:
RULES→whileEdoS
■E.〓S.;S.〓S.;
S.φ〓μ(ψ.(.((E.)→ψ((S.φ)),)))
其中μ是最小不动点算子。
从上例可以看出,对于循环语句的动态语义来说,属性文法是不太方便的,因此说属性文法是适合于静态语义的描述,而不适合于动态语义的描述。
这一点读者应深刻地领会。
§8.3扩展属性文法EAG
简单属性文法的特点是把语法规则和语义规则区分开,这种规定使得在简单属性文法中出现大量的"复写"型语义规则,从而使AG的表示显得沉长而烦琐。
由Watt&Madsen[1977]提出的扩展属性文法EAG与AG相反,把要计算的表达式直接附到语法符号上,没有单独的语义规则式,语法符号也没有属性符号。
形式上的区别,从下面例子即可看出来:
AG表示:
D→D;D■D2.〓D1.;D3.〓D2.';D1.'〓D3.'
EAG表示:
从上例可看出,EAG表示比AG表示简短而直接得多。
在上例AG表示中,语义规则全是复写型规则,而在EAG表示中就没了这些复写动作,其次σ和ε类符号在AG中是属性符号,而在EAG中则都是变量(属性变量),即EAG没有属性符号概念。
在EAG中,同一规则式中的相同属性变量具有相同值。
上例中的EAG规则式中D有两个属性,其中前者是继承属性,而后者是综合属性。
具体说第一属性为输入环境(继承),第二属性为输出环境(综合)。
EAG方法的主要思想是:
对每个语法符号确定属性个数(但不起属性名),并指明每个属性是哪类的(继承,综合)和什么类型的(属性域);其次定义必要的属性变量,并把计算的属性表达式直接写在语法符号的相应位上(没有单独语义规则).
■定义8.3.1.属性表达式
1)常量是属性表达式。
2)属性变量是表达式。
3)由常量和属性变量以及函数调用(包括标准中缀操作)组成的合法式子是属性表达式。
■定义8.3.2.扩展属性文法EAG
扩展属性文法EAG是六元组:
EAG=(D,F,S,Z,V,R),其中
D:
属性域部分
F:
自定义函数部分
S:
语法符号及其属性部分
Z:
文法开始符
V:
属性变量部分
R:
规则部分
■语法符号及其属性部分,对每个语法符号指出有几个属性,以及每个属性的类型和类别(继承,综合),如
D↓ENV↑ENV
它表示D有两个属性,其中第一属性的类型是ENV,类别是继承型;而第二属性的类型是ENV,类别是综合型。
注意,这里没用到属性符号,,这一点和简单属性文法不一样。
■属性变量部分定义属性变量,相当于变量说明。
如:
σ,σ',σ":
STAT
ε,ε',ε":
ENV
■规则式部分给出EAG规则式,如
它表示对应的产生式为D→D;D。
在规则式中把每个语法符号均用<>括起来,其内部首先是语法符号本身,后面是属性类别符(↓或↑),接着是属性表达式,重复上述过程。
当语法符号没有属性时,我们将用语法符号本身。
同一EAG规则式中的同一变量具有相同的值。
对前面规则式来说有三个属性变量ε、ε'和ε"。
其中ε是规则式左部的继承属性,因此可视为是已知的。
第二个D的继承属性值等于第一个D的继承属性值即ε,而D的功能是只要给出继承属性值,则即可算出其综合属性值部分,因此可假设其综合属性值是什么(ε')。
对于第三个D也是类似。
例8.3.1.语法符号及其属性描述例
start:
P................................................开始符
nonterm:
P↑STAT;...........................程序
D↓ENV↑ENV;..................说明
T↑TYPE;...........................类型
E↓ENV↑STAT→EV;.......表达式
S↓ENV↑STAT→STAT.......语句
term:
id↑IDE;..............................标识符
n↑REAL;...........................常数
例8.3.2.属性变量及其类型描述例
σ,σ',σ":
STAT;
ε,ε',ε":
ENV;
t:
TYPE;
s:
IDE;
v:
REAL;
例8.3.3.表达式语义的EAG规则式例。
假设表达式的功能是:
给环境和状态则输出一个值。
其中环境是IDE到VAL映射。
类型只有实型和布尔类型。
■E↓ENV↓STAT↑EV
n↑INT
id↑IDE
■
例8.3.4.语句语义的EAG规则式例(不包括循环语句)。
我们假设语句的功能是:
给环境和状态,则输出一新的状态。
表达式的功能同前。
■S↓ENV↓STAT↑STAT
■→skip
→
=
→;
→
if
else
通俗地理解EAG属性规则的办法是,把↓理解为input参数的标志,把↑理解为output参数的标志,并把形如的单位理解为函数调用S(,;'),其中“”表示其前面是input参数。
比如上述条件语句的规则式可视为如下过程定义:
procS(,;''')〓{E(,;v);S(,;');S(,';'');
''':
=(v→','')}
例8.3.5.循环语句语义的EAG规则式例。
■S↓ENV↑[STAT→STAT]
E↓ENV↑[STAT→EV]
■:
ENV;:
STAT;:
[STAT→EV];
φ,ψ:
[STAT→STAT]
■→
while
例8.3.6.说明的语义规则例。
说明的产生式部分定义如下:
Dec→varid:
Type|procid:
Modu|Dec;Dec
Dec的功能还是给环境,则产生新的环境,Modu的功能是给环境则产生(STAT→VAL*→STAT)域上的函数,Type的功能是给环境则产生一类型值。
根据上述说明,语法符号Dec的属性定义部分可如下:
■ENV=IDE→var(TYPE)+pro(STAT→VAL*→STAT)
STAT=IDE→VAL
■Dec:
↓ENV↑ENV
Type:
↓ENV↑TYPE
Modu:
↓ENV↑(STAT→VAL*→STAT)
id:
↑IDE
下面是说明的EAG规则式部分:
§8.4属性文法的应用
前面介绍了简单属性文法和扩展属性文法,并且用属性文法描述了一些语言成分的动态语义。
但读者应清楚地知道,属性文法主要适用于静态语义的描述,而不太适用于动态语义的描述,这一点已从循环语句的语义描述中看到。
在构造编译器时,很重要的工作是构造语义分析器和中间代码生成器。
比较适用的方法之一就是用属性文法。
因此这一节将介绍属性文法在静态语义分析和中间代码生成描述中的应用。
这些内容有助于编译器构造的理解,读者应用心地去掌握所述内容。
类型是任何程序设计语言中都是最重要的静态语义部分。
类型的语义分析中的主要工作是把类型的源代码表示
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 形式语义Ch8 属性文法 形式 语义 Ch8 属性 文法