属性文法 个属性文法AG是一个四元组(G,A,RC),其中 G是已经压缩的文法。 A是有穷属性集合,对于每个文法符号Ⅹ,都有其属性集 合A(X)对应 R是有穷属性规则集合。对于规则p:X0=X1X2..Xk,有 规则Xa=(Xjb,…,Ⅹpkc)。定义了在使用这个规则进 行归约的时候,Xia的求值 C是有穷条件集合。C(Xia,…,Xja)表示规则p必须满足的 条件。只有这些条件满足的时候,输入的符号串才是有 意义的
属性文法 • 一个属性文法AG是一个四元组(G,A,R,C)，其中 – G是已经压缩的文法。 – A是有穷属性集合，对于每个文法符号X，都有其属性集 合A(X)对应。 – R是有穷属性规则集合。对于规则p：X0=X1X2…Xk，有 规则Xi.a=f(Xj.b，…，Xpk.c)。定义了在使用这个规则进 行归约的时候，Xi.a的求值。 – C是有穷条件集合。C(Xi.a, …,Xj.a)表示规则p必须满足的 条件。只有这些条件满足的时候，输入的符号串才是有 意义的
语法制导定义的分类 S属性定义:所有的文法符号的属性都是综合属性。 实际上是说:一个语法结构的属性由它的组成部分的 属性确定。 例如:对于表达式的结果类型; 基于S属性定义的语法分析树可以用自底向上的方法 得到。 规则E∷=E1+T对应的语法结构, E type的值可 以如下确定:如果E1的类型和T的类型都是int 那么结果也是int,如果有一个是rea,那么结果 类型是real
语法制导定义的分类 • S_属性定义：所有的文法符号的属性都是综合属性。 – 实际上是说：一个语法结构的属性由它的组成部分的 属性确定。 – 例如：对于表达式的结果类型； – 基于S_属性定义的语法分析树可以用自底向上的方法 得到。 – 规则E::=E1+T对应的语法结构，E.type的值可 以如下确定：如果E1的类型和T的类型都是int， 那么结果也是int, 如果有一个是real，那么结果 类型是real
继承属性 语法分析树中,一个结点的属性由其父结点和兄弟结 点确定 反映了文法结构的属性对上下文的依赖特性 比如:对于C语言中变量的申明可以是如下方式, TYPEⅵ1,V2;那么变量v,v2的属性值‘类型’是 由TYPE确定的,如果TYPE是foat,那么它们的类 型就是实数 在前面的例子6,2中,结点T的属性type是综合属性, 但是D:=L中,L的属性i就是继承属性,这个属 性的值是由T的属性type确定的
继承属性 • 语法分析树中，一个结点的属性由其父结点和兄弟结 点确定。 – 反映了文法结构的属性对上下文的依赖特性。 – 比如：对于C语言中变量的申明可以是如下方式， TYPE v1, v2; 那么变量v1, v2的属性值‘类型’是 由TYPE确定的，如果TYPE是float，那么它们的类 型就是实数。 – 在前面的例子6.2中，结点T的属性type是综合属性， 但是D::=TL中，L的属性in就是继承属性，这个属 性的值是由T的属性type确定的
依赖图 在语义规则中,假设某个属性的定义是b=fcl,c2,,cn), 那么要求得属性b的值,首先要计算出属性c1c2,,cn 的值。显然它们的计算顺序有一种依赖关系。 通常,我们可以在语法分析树中添加有向的箭头表示 这种依赖关系。(对于过程调用,可以添加虚拟的属 性) 在语法分析树中,如果属性b依赖于c,那么从c对应的 结点到b对应的结点画一个箭头
依赖图 • 在语义规则中，假设某个属性的定义是b=f(c1,c2,…,cn)， 那么要求得属性b的值，首先要计算出属性c1,c2,…cn 的值。显然它们的计算顺序有一种依赖关系。 • 通常，我们可以在语法分析树中添加有向的箭头表示 这种依赖关系。（对于过程调用，可以添加虚拟的属 性） • 在语法分析树中，如果属性b依赖于c，那么从c对应的 结点到b对应的结点画一个箭头
依赖图构造算法 步骤1:构造语法树,对于语法树中的每个结点 的每个属性,构造一个结点 步骤2:对每个树的结点n,对该结点所相关的每 个语义规则b:=f(cl,c2,,cn)都如下添加有向弧: 从clc2,cn的结点向b对应的结点画有向弧 实际上是对所有在建立语法树中所使用的 规则都建立依赖关系
依赖图构造算法 • 步骤1：构造语法树，对于语法树中的每个结点 的每个属性，构造一个结点。 • 步骤2：对每个树的结点n，对该结点所相关的每 个语义规则b:=f(c1,c2,…,cn)都如下添加有向弧： – 从c1,c2,…cn的结点向b对应的结点画有向弧。 • 实际上是对所有在建立语法树中所使用的 规则都建立依赖关系