《编译原理5.2.1-4-算符优先关系表构造.ppt》由会员分享，可在线阅读，更多相关《编译原理5.2.1-4-算符优先关系表构造.ppt（16页珍藏版）》请在金锄头文库上搜索。
1、5.2.1 算符优先文法及优先表构造算符优先文法及优先表构造 1、算符文法、算符文法2、算符优先关系的定义、算符优先关系的定义3、算符优先文法、算符优先文法 4、优先关系表的构造、优先关系表的构造4、优先关系表的构造、优先关系表的构造1) 1) 定义定义 FIRSTVTFIRSTVT集集 和和 LASTVTLASTVT集集2) 2) 根据根据 FIRSTVTFIRSTVT集集 和和 LASTVTLASTVT集集 计算计算三种优先关系三种优先关系 3) 3) 计算计算FIRSTVTFIRSTVT集集和和 LASTVTLASTVT集集4) 4) 构造优先关系表构造优先关系表 1) 1) 定义定义F
2、IRSTVTFIRSTVT集集 和和 LASTVTLASTVT集集FIRSTVT(P) = a | P a 或或 P Qa注意注意: 在算符文法中在算符文法中, 一个非终结符推导出的一个非终结符推导出的首个算符的位置要么是第一个首个算符的位置要么是第一个, 要么是第二个要么是第二个LASTVT(P) = a | P a 或或 P aQ2) 2) 根据根据 FIRSTVTFIRSTVT集集 和和 LASTVTLASTVT集集计算三种优先关系计算三种优先关系 : 直接查看产生式右部，如有直接查看产生式右部，如有 P ab 或或 PaQb , 则则a b 成成 立立 : 假定有产生式的候选形为假定有
3、产生式的候选形为 aP , 对任何对任何 bFIRSTVT(P) , 有有a b成立成立 : 假定有产生式的候选形为假定有产生式的候选形为 Pb , 对任何对任何 aLASTVT(P) , 有有a b成立成立3) 3) 计算计算FIRSTVTFIRSTVT集和集和 LASTVTLASTVT集集(1) (1) 根据定义直观计算根据定义直观计算FIRSTVTFIRSTVT集集(2)(2) 用形式化算法计算用形式化算法计算FIRSTVTFIRSTVT(3)(3) 由简单关系图形计算由简单关系图形计算FIRSTVT*FIRSTVT*(1)(1) 根据定义直观计算根据定义直观计算FIRSTVTFIRST
4、VT集集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) PiFIRSTVTLASTVTE # #E + * ( i + * ) iT * ( i *) iF ( i ) iP ( i ) iE#E# 为对原文法的扩充为对原文法的扩充# 表示句子括号表示句子括号(2)(2) 用形式化算法计算用形式化算法计算FIRSTVTFIRSTV
5、T集集建立一个布尔数组建立一个布尔数组FP, a , 和栈和栈STACKFP, a=TRUE , 当且仅当当且仅当 a FIRSTVT(P)PROCEDUE INSERT(P, a)IF NOT FP, a THENBEGIN FP, a:=TRUEPUSH(P, a) ONTO STACKEND MAINBEGIN (MAIN)FOR 每个非终结符每个非终结符P和终结符和终结符aDO FP, a:= FALSE;FOR 每个形如每个形如Pa或或PQ a 的产生式的产生式DO INSERT(P, a)WHILE STACK 非空非空 DOBEGIN把把STACK的顶项记为的顶项记为(Q，a)
6、, 托出去托出去FOR 每个形如每个形如PQ 的产生式的产生式 DO INSERT(P, a)ENDEND (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)(3) 由简单关系图形计算由简单关系图形计算FIRSTVT FIRSTVT 1.图中的结点为非终结符的图中的结点为非终结符的FIRSTVT(P)和和终结符终结符2.对每个形如对每个形如Pa或或PQ a 的产生式的产生式, 由由FIRSTVT(P)结点结点
7、到到结点结点a用箭弧连接用箭弧连接3.对每个形如对每个形如PQ 的产生式，的产生式， 由由FIRSTVT(P)到到FIRSTVT(Q)用箭弧连接用箭弧连接4.对每个非终结符的对每个非终结符的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) PiFIRSTVT(T)FIRSTVT(F)FIRSTVT(P)+*(iFIRSTVT(E)FIRSTVT(E)4) 4) 构造优先关系表构造优先关系
8、表FOR 每个产生式每个产生式 PX1 X2 Xn DO FOR i:=1 TO n-1 DO IF Xi 和和 X i+1 均为终结符均为终结符THEN 置置 Xi X i+1 IF Xi 和和 X i+2 均为终结符均为终结符, X i+1 为非终结符为非终结符 , i n-2, THEN 置置 Xi X i+2 IF Xi为终结符为终结符, 但但X i+1 为非终结符为非终结符 THEN FOR FIRSTVT(X i+1 )中的每个中的每个a DO 置置 Xi a IF Xi为非终结符为非终结符, 但但X i+1 为终结符为终结符 THEN FOR LASTVT(X i )中的每个中的
9、每个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) PiFIRSTVTLASTVTE # #E + * ( i + * ) iT * ( i *) iF ( i ) iP ( i ) i构造算符优先关系表构造算符优先关系表Pab PaQb PaR PRb (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()#
