编译原理5：算符优先关系表构造.ppt

单击此处编辑母版标题,单击此处编辑母版文本样式,第二级,第三级,5.2.1,算符优先文法及优先表构造,1,、算符文法,2,、算符优先关系的定义,3,、算符优先文法,4,、优先关系表的构造,4,、优先关系表的构造,1),定义,FIRSTVT,集,和,LASTVT,集,2),根据,FIRSTVT,集,和,LASTVT,集,计算三种优先关系,3),计算,FIRSTVT,集,和,LASTVT,集,4),构造优先关系表,1),定义,FIRSTVT,集 和,LASTVT,集,FIRSTVT(P),=,a,|P,a,或,P,Q,a,注意,:,在算符文法中,一个非终结符推导出的首个算符的位置要么是第一个,要么是第二个,LASTVT(P),=,a,|P ,a,或,P ,a,Q,2),根据,FIRSTVT,集 和,LASTVT,集计算三种优先关系,:,直接查看产生式右部，如有,P,ab,或,PaQb,则,a b,成 立,:,假定有产生式的候选形为,aP,对任何,bFIRSTVT(P,),有,a b,成立,:,假定有产生式的候选形为,Pb,对任何,aLASTVT(P,),有,a b,成立,3),计算,FIRSTVT,集和,LASTVT,集,(1),根据定义直观计算,FIRSTVT,集,(2),用形式化算法计算,FIRSTVT,(3),由简单关系图形计算,FIRSTVT*,(1),根据定义直观计算,FIRSTVT,集,a),若有产生式,Pa,或,pQa,则,aFIRSTVT(P,),b),若有产生式,PQ ,若,aFIRSTVT(Q,),则,aFIRSTVT(P,),例,5.4 p90,(0)E#E#,(1)EE+T,(2)ET,(3)TT*F,(4)TF,(5)FPF,(6)FP,(7)P(E),(8),Pi,FIRSTVT,LASTVT,E,#,#,E,+*(i,+*)i,T,*(i,*)i,F,(i,)i,P,(i,)i,E#E#,为对原文法的扩充,#,表示句子括号,(2),用形式化算法计算,FIRSTVT,集,建立一个布尔数组,FP,a,和栈,STACK,FP,a=TRUE,当且仅当,a,FIRSTVT(P,),PROCEDUE,INSERT,(P,a),IF,NOT FP,a,THEN,BEGIN,FP,a:=TRUE,PUSH(P,a)ONTO STACK,END,MAIN,BEGIN(MAIN),FOR,每个非终结符,P,和终结符,a,DO,FP,a:=FALSE;,FOR,每个形如,Pa,或,PQ a,的产生式,DO,INSERT(P,a),WHILE,STACK,非空,DO,BEGIN,把,STACK,的顶项记为,(Q,，,a),托出去,FOR,每个形如,PQ,的产生式,DO INSERT(P,a),END,END (MAIN),例,5.4 p90,(0)E#E#,(1)EE+T,(2)ET,(3)TT*F,(4)TF,(5)FPF,(6)FP,(7)P(E),(8),Pi,用形式化算法计算,FIRSTVT,集过程见黑板,(3),由简单关系图形计算,FIRSTVT,图中的结点为非终结符的,FIRSTVT(P),和,终结符,对每个形如,Pa,或,PQ a,的产生式,由,FIRSTVT(P),结点,到,结点,a,用箭弧连接,对每个形如,PQ,的产生式，由,FIRSTVT(P),到,FIRSTVT(Q),用箭弧连接,对每个非终结符的,FIRSTVT(P),经箭弧有路径能到达的,终结符结点,a,则有,a,FIRSTVT(P),补充,(0)E#E#,(1)EE+T,(2)ET,(3)TT*F,(4)TF,(5)FPF,(6)FP,(7)P(E),(8),Pi,FIRSTVT(T),FIRSTVT(F),FIRSTVT(P),+,*,(,i,FIRSTVT(E),FIRSTVT(E),4),构造优先关系表,FOR,每个产生式,P,X,1,X,2,X,n,DO,FOR,i:=1 TO n-1,DO,IF X,i,和,X,i+1,均为终结符,THEN,置,X,i,X,i+1,IF X,i,和,X,i+2,均为终结符,X,i+1,为非终结符,i n-2,THEN,置,X,i,X,i+2,IF X,i,为终结符,但,X,i+1,为非终结符,THEN FOR FIRSTVT(X,i+1,),中的每个,a DO,置,X,i,a,IF X,i,为非终结符,但,X,i+1,为终结符,THEN FOR LASTVT(X,i,),中的每个,a DO,置,a X,i+1,例,5.4 p90,(0)E#E#,(1)EE+T,(2)ET,(3)TT*F,(4)TF,(5)FPF,(6)FP,(7)P(E),(8),Pi,FIRSTVT,LASTVT,E,#,#,E,+*(i,+*)i,T,*(i,*)i,F,(i,)i,P,(i,)i,构造算符优先关系表,P,ab,P,aQb,P,aR,P,Rb,(0)E#E#,(1)EE+T,(2)ET,(3)TT*F,(4)TF,(5)FPF,(6)FP,(7)P(E),(8),Pi,#,(),#FIRSTVT(E),+FIRSTVT(T),*FIRSTVT(F),FIRSTVT(F),(,FIRSTVT(E),LASTVT(E)#,LASTVT(E)+,LASTVT(T)*,LASTVT(P),LASTVT(E),算符优先关系表,(p90,表,5.1),+,*,i,(,),#,+,*,i,(,),#,