编译原理5.2.1-4-算符优先关系表构造.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|Pa或PQa,注意:在算符文法中,一个非终结符推导出的首个算符的位置要么是第一个,要么是第二个,LASTVT(P)=a|Pa或PaQ,2)根据FIRSTVT集和LASTVT集计算三种优先关系,:直接查看产生式右部，如有Pab或PaQb,则ab成立,:假定有产生式的候选形为aP,对任何bFIRSTVT(P),有ab成立,:假定有产生式的候选形为Pb,对任何aLASTVT(P),有ab成立,3)计算FIRSTVT集和LASTVT集,(1)根据定义直观计算FIRSTVT集(2)用形式化算法计算FIRSTVT(3)由简单关系图形计算FIRSTVT*,(1)根据定义直观计算FIRSTVT集,a)若有产生式Pa或pQa则aFIRSTVT(P)b)若有产生式PQ,若aFIRSTVT(Q)则aFIRSTVT(P),例5.4p90,(0)E#E#(1)EE+T(2)ET(3)TT*F(4)TF(5)FPF(6)FP(7)P(E)(8)Pi,E#E#为对原文法的扩充#表示句子括号,(2)用形式化算法计算FIRSTVT集,建立一个布尔数组FP,a,和栈STACKFP,a=TRUE,当且仅当aFIRSTVT(P),PROCEDUEINSERT(P,a)IFNOTFP,aTHENBEGINFP,a:=TRUEPUSH(P,a)ONTOSTACKEND,MAIN,BEGIN(MAIN)FOR每个非终结符P和终结符aDOFP,a:=FALSE;FOR每个形如Pa或PQa的产生式DOINSERT(P,a)WHILESTACK非空DOBEGIN把STACK的顶项记为(Q，a),托出去FOR每个形如PQ的产生式DOINSERT(P,a)ENDEND(MAIN),例5.4p90,(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或PQa的产生式,由FIRSTVT(P)结点到结点a用箭弧连接对每个形如PQ的产生式，由FIRSTVT(P)到FIRSTVT(Q)用箭弧连接对每个非终结符的FIRSTVT(P),经箭弧有路径能到达的终结符结点a,则有aFIRSTVT(P),补充,(0)E#E#(1)EE+T(2)ET(3)TT*F(4)TF(5)FPF(6)FP(7)P(E)(8)Pi,4)构造优先关系表,FOR每个产生式PX1X2XnDOFORi:=1TOn-1DOIFXi和Xi+1均为终结符THEN置XiXi+1IFXi和Xi+2均为终结符,Xi+1为非终结符,in-2,THEN置XiXi+2IFXi为终结符,但Xi+1为非终结符THENFORFIRSTVT(Xi+1)中的每个aDO置XiaIFXi为非终结符,但Xi+1为终结符THENFORLASTVT(Xi)中的每个aDO置aXi+1,例5.4p90,(0)E#E#