资源描述：
《形式语义-ch 属性文法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第八章属性文法§8.1简述属性文法(AttributeGrammar)的概念首先由Knuth在1968年提出。顾名思意属性文法是带属性的一种文法。虽称是文法,但它不是用来描述文法,而是用来描述文法符号的属性关系的。因为其属性规则与产生式紧密相关,称它是面向文法的一种方法。凡是与文法的相关的问题均可试用属性文法这一工具。属性文法的最成功的应用是编译器的自动生成。有过一些成功的系统,如GAG[kastens82],HLP[Raiha78],SDCG[paulson82];一些现实程序设计语言的编译程序前端,也用属性文法生成出来，其中包括pascal[kaste
2、ns&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→N
3、D2.R→N.N5.D→0(8.1.0)3.N→D6.D→1文法本身并不含什么意义，它只说明什么样的终极符串是合法的。文法G[R]的合法终极符串(句子)为通常的二进制数,可带小数点,但至多能带一个小数点。根据定义10.1,001、111333––等都是文法G[R]的合法句子。那么它们究竟代表什么意义，可给出种种不同的定义。假设就定义它们代表的是相应的十进制实数,比如前面几个二进制表示分别代表实数2.5,1和7。若用R.V表示R串所对应的十进制数,用D.V表示D串所对应的十进制数,用N.V表示N串所对应的十进制数,用N.L表示N串的二进制长度,则显然其形式描
4、述如图8.1.1所示。上述假设说明语法符号R有一个属性,并且其属性名定为V;语法符号D有一个属性,并且其名定为V;语法符号N有两个属性,并且其属性名分别定为V和L。图8.1.1是一种基于语法的属性求值规则式。它们将构成属性文法的核心部分即规则部分。从中可看出属性文法的特点是对每个语法符号确定一些属性,并给出各属性值的计算规则。语法规则语义规则r1:R→N■R.v=N.vr2:R→N1.N2■R.v=N1.v+N2.v×2-N2.Lr3:N→D■N.v=D.v,N.L=1r4:N→N1D■N.v=N1.v×2+D.v,N.L=N1.L+1r5:D→0■D.v
5、=0r6:D→1■D.v=1图8.1.1属性文法例(8.1.1)从上述语义规则可以看出其含义是非常直观的。但很显然属性文法的表示不是可执行的程序,如何用这些语义规则来求出属性值,是不那么明显的问题,因此需要说明。下面将对此做简单介绍。属性值的求值过程333––总的问题是这样一种问题,即给了一个合法的终极符串,问其属性值如何求?这里有时间和空间问题,因此很多人对属性求值方法进行了大量的研究.并提出了一些好方法。我们暂不考虑那些特殊的方法,而是考虑最一般而容易理解的方法,因为在此只希望使读者能了解到属性值是可用语义规则来求出的。具体计算过程可分为下面两大部分：
6、■STEP1：首先构造所给句子的属性树。属性树如图8.1.2所示,其中虚线部分表示各属性节点之间的关系。在构造树时对于每个内节点标上对应产生式编号。■STEP2：利用属性的求值规则(语义规则）求属性树各结点的属性值，最终计算出根结点的属性值。每次寻找一个能计算某属性值的结点，并用它所依赖的已知属性值求出其属性值。上述结点可能很多,这时可任选其中的任何一个结点。当求出根结点的所有属性值时终止。对于属性文法(8.1.1),我们有图8.1.2所示的计算图。v2.5R22LvN111LvN21vD11LvN20vD11.01vD图8.1.2属性树333––§8.2
7、简单属性文法1968年knuth提出了属性文法概念,我们称这种属性文法为简单属性文法。简单属性文法的特点之一是,给每个语法符号的每个属性起相应的属性符号。为此引进下面符号:■A(X)...............................表示X的属性符号集■AI(X)..............................表示X的继承属性符号集■AS(X)..............................表示X的综合属性符号集其中X是语法符号,它们满足下面条件:■AI(X)∪AS(X)=A(X),AI(X)∩AS(X)={}■AI(Z)
8、={}(Z为开始符),AI(t)={}(t为终极符)属性分为继承属
