chpt7-2属性文法和语法制导.ppt

7.2属性文法和语法制导翻译,程序设计 语言的语义 静态语义是对程序约束的描述，这些约束无法通过抽象语法规则来妥善地描述，实质上就是语法规则的良形式条件，它可以分为类型规则和作用域/可见性规则两大类 如：类型相容性 变量先声明后引用 名称相关要求动态语义 程序单位描述的计算编译程序的语义处理工作 静态语义审查 执行动态语义（计算）生成代码.,语义形式化 语义建模,形式语义学(如指称语义学、公理语义学、操作语义学等)的研究已取得了许多重大的进展文法模型-属性文法命令式或操作式模型-操作语义学应用式模型-指称语义学公理式模型-公理语义学,属性文法和语法制导翻译,在实际应用中比较流行的语义描述和语义处理的方法1 属性文法概述2 基于属性文法的处理方法3 S-属性文法的自下而上计算L-属性文法 L-属性文法和自顶向下翻译 自下而上的分析中实现L-属性文法,7.2.1属性文法概述,表达式文法 ET+T|T or T Tn|b ET1+T2 T1.type=int T2.type=T1.type E.type:=int E T1 or T2 T1.type=bool T2.type=T1.type E.type:=bool T n T.type:=int T b T.type:=bool,input:/*empty string*/|input line;line:n|exp n printf(t%.10gn,$1);|error n;exp:NUM$=$1;|exp+exp$=$1+$3;|exp-exp$=$1-$3;|exp*exp$=$1*$3;|exp/exp$=$1/$3;|-exp%prec NEG$=-$2;|exp exp$=pow($1,$3);|(exp)$=$2;,属性文法,属性文法(attribute grammar)是一个三元组：A=(G,V,F),其中 G:是一个上下文无关文法V:有穷的属性集,每个属性与文法的一个终结符或非终结符相连,这些属性代表与文法符号相关信息，如它的类型、值、代码序列、符号表内容等等.属性与变量一样，可以进行计算和传递。属性加工的过程即是语义处理的过程。F:关于属性的属性断言或一组属性的计算规则(称为语义规则).断言或语义规则与一个产生式相联,引用该产生式左端或右端的终结符或非终结符相联的属性.,属性通常分为两类：综合属性和继承属性。简单地说，综合属性用于“自下而上”传递信息，而继承属性用于“自上而下”传递信息。,属性文法中，对应于每个产生式A都有一套与之相关联的语义规则，每条规则的形式为b:=f(c1,c2ck)f是一个函数，b和c1,c2ck是该产生式文法符号的属性.并且（1）如果b是A的一个属性,c1,c2ck是产生式右部文法符号的属性或A的其他属性,则称b是A的综合属性（2）如果 b是产生式右部某个文法符号X的一个属性,并且c1,c2ck是A或产生式右边任何文法符号的属性,则 称b是文法符号X 的继承属性在两种情况下，我们都说属性b依赖于属性c1,c2ck,一般，对出现在产生式左边的继承属性和出现在产生式右边的综合属性都必须提供一个计算规则。属性计算规则中只能使用相应产生式中的文法符号的属性，,然而，出现在产生式左边的继承属性和出现在产生式右边的综合属性不由所给定的产生式的属性计算规则进行计算，它们由其它产生式的属性规则计算或者由属性计算器的参数提供。AX1 X2 XnA的综合属性S(A)计算公式 S(A):=f(I(X1),I(Xn)Xj的继承属性T(Xj)计算公式 T(Xj):=f(I(A),.I(Xn)1)非终结符既可有综合属性也可有继承属性，但文法开始符号没有继承属性.2)终结符只有综合属性,它们由词法程序提供.,如非终结符A,B和C，其中A有一个继承属性a和一个综合属性b，B有综合属性c，C有继承属性d,对 产生式ABC可能有语义规则 C.d:=B.c+1和A.b:=A.a+B.c 而属性A.a和 B.c是在其他地方计算的。,语义规则所描述的工作可以包括属性计算、静态语义检查、符号表操作、代码（中间）生成等等。有些语义规则可能产生副作用（如产生代码），也可能是个函数，通常把这样的语义规则写成过程调用或过程段,一个属性文法和综合属性的例子 例.1 非终结符E、T及F都有一个综合属性val,符号digit有一个综合属性，它的值由词法分析器提供。与产生式LE对应的语义规则仅仅是打印由E产生的算术表达式的值的一个过程，我们可认为这条规则定义了L的一个虚属性。某些非终结符加上标是为了区分一个产生式中同一非终结符多次出现,语 义 规 则,L E,E E1+T,E T,T T1*F,T F,F(E),F digit,Print(E.val),E.val:=E1.val+T.val,E.val:=T.val,T.val:=T1.val F.val,T.val:=F.val,F.val:=E.val,F.val:=digit.lexval,产 生 式,设表达式为35+4，则语义动作打印数值19,.,L,E.val=19,E.val=15,T.val=4,T.val=15,F.val=4,T.val=3,F.val=3,F.val=5,digit.lexval=4,digit.lexval=5,digit.lexval=3,+,*,3*5+4的带注释的分析树,继承属性,一个结点的继承属性值是由此结点的父结点和/或兄弟结点的某些属性来决定的。例2 继承属性L.in,生 产 式,语 义 规 则,D TL,T int,T real,L L1,id,L id,L.in:=T.type,T.type:=integer,T.type:=real,L1.in:=L.in,addtype(id.entry,L.in),addtype(id.entry,L.in),D,L.in=real,L.in=real,L.in=real,T.type=real,real,id2,id1,id3,.,Real id1,id2,id3每个L结点都带有继承属性的语法树,，,，,例3,P DSD var V;D|S V:=e;S|V x|y|z现在使用两个属性，name和dl，每当一个新的变量声明时，就把它的name属性附给它，name属性是综合属性。将所声明的变量都放到一个变量名字清单中（用语义函数addlist实现），用属性dl收集声明块中声明的所有变量。然后这个dl属性又作为继承属性传到后面的语句部分，每个语句用到的变量都要进行审查，看它是否在变量名字清单中 P DS S.dl:=D.dlD1 var V;D2|D1.dl:=addlist(V.name,D2.dl)|D1.dl:=NULLS1 V:=e;S2|check(V.name,S1.dl);S2.dl:=S1.dlV x|y|z V.name:=x|V.name:=y|V.name:=z,var x；var y；y:=e；,P D dl=x,y Sdl=x,yvar V；D dl=y V:=e；S x var V；D dl=y y,例4：定义二进制数的CFG:,(1)NSS(2)SSB(3)SB(4)B0(5)B1,(1)NSS(2)SSB(3)SB(4)B0(5)B1 非终结符N表示整个二进制数的数值，综合属性v附加在N上：N v 非终结符B 表示一个二进制数字，它有自己的值v，但该值分配给N的值与它的位置有关，是与2成比例，比例因子f是从S继承的属性,所以：B v f 非终结符S 表示一个二进制数字串，它也有值，但该值与串的位置(f)有关,与串的长度l有关:S f v l,构造数值的属性断言可以如下:,N vS f1 v 1 l1 S f 2 v 2 l2 v:=v1+v2;f 1:=1;f2:=2-l2 S f v l S f1 v1 l 1B f 2 v2 f1:=2f;f 2:=f;v:=v 1+v2;l:=l1+1 B f v l:=1 B f v0 v:=0 1 v:=f,(1)NSS(2)SSB(3)SB(4)B0(5)B1,文法定义的二进制数的形式为dmdm-1d1d0.pk pk-1p1p0,其中dmdm-1d1d0和pk pk-1p1p0 都是二进制数字，这种形式的二进制数的数值计算公式是：dm 2m+dm-12m-1+d121+d0+pk2-1+pk-12-2+p12-k+p02-(k+1)=dm 2m+dm-12m-1+d121+d0+(pk2k+pk-12(k-1)+p121+p0)/2k+1,为了计算小数部分的值，需要知道二进制数字的个数，也即S定义的数串的长度，因此对非终结符S附加两个属性val和 length,N S1“”S2 N.val:=S1.val+2 S2.len*S2.val;S S1 B S.val:=2*S1.val+B.val;S.len:=S1.len+1 S B S.val:=B.val;S.len:=1 B“0”B.val:=0B“1”B.val:=1,N v S i1 l1“”S i2 l2 v:=i1+2-l2 i2 S i l S i1 l 1 Bi2 i:=2 i1+i2;l:=l1+1 B i l:=1 B i“0”i:=0“1”i:=1,7.2.2基于属性文法的处理过程,从概念上讲，基于属性文法的处理过程即语法制导翻译通常是这样的：对单词符号串进行语法分析，构造语法分析树，然后根据需要构造属性依赖图,遍历语法树并在语法树的各结点处按语义规则进行计算输入符号串 分析树 属性依赖图 语义规则的计算顺序,依赖图,由称为依赖图的一个有向图 描述分析树中的继承属性和属性中间的相互依赖关系。依赖图的构造算法：for分析树中每一个结点n do for 结点的文法符号的每一个属性a do 为a在依赖图中建立一个结点；for 分析树中每一个结点n do for结点n所用产生式对应的每一个语义规则 b:=f(c1,c2,ck)do for i:=1 to k do 从ci结点到b结点构造一条有向边,依赖图-例2,例2 继承属性L.in,