《编译原理：算符优先关系表构造》由会员分享，可在线阅读，更多相关《编译原理：算符优先关系表构造（16页珍藏版）》请在金锄头文库上搜索。
1、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 Qa注意: 在算符文法中, 一个非终结符推导出的 首个算符的位置要么是第一个, 要么是第二个LASTVT(P) = a | P a 或 P aQ2) 根据 FIRSTVT集 和 LA
2、STVT集 计算三种优先关系: 直接查看产生式右部，如有 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) 则
3、 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) PiFIRSTVTLASTVT E # # E + * ( i + * ) i T * ( i *) i F ( i ) i P ( i ) iE#E# 为对原文法的扩充 # 表示句子括号(2) 用形式化算法计算FIRSTVT集 建立一个布尔数组FP, a , 和栈STACK FP, a=TRUE , 当且仅当 aFIRSTVT(P)PROCEDUE INSERT(P, a) IF NOT FP, a THEN BEG
4、IN FP, a:=TRUE PUSH(P, a) ONTO STACK END MAINBEGIN (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)
5、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) PiFIRSTVT(T)FIRSTV
6、T(F)FIRSTVT(P)+*(iFIRSTVT(E)FIRSTVT(E)4) 构造优先关系表 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 )中的每个a
7、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) PiFIRSTVTLASTVT E # # E + * ( i + * ) i T * ( i *) i F ( i ) i P ( 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()#
