编译原理521-4-算符优先关系表构造ppt课件

1、5.2.1 算符优先文法及优先表构造算符优先文法及优先表构造 1、算符文法、算符文法2、算符优先关系的定义、算符优先关系的定义3、算符优先文法、算符优先文法 4、优先关系表的构造、优先关系表的构造4、优先关系表的构造、优先关系表的构造1) 1) 定义定义 FIRSTVT FIRSTVT集集 和和 LASTVT LASTVT集集2) 2) 根据根据 FIRSTVT FIRSTVT集集 和和 LASTVT LASTVT集集 计算计算三种优先关系三种优先关系 3) 3) 计算计算FIRSTVTFIRSTVT集和集和 LASTVT LASTVT集集4) 4) 构造优先关系表构造优先关系表 1) 1)

2、定义定义FIRSTVTFIRSTVT集集 和和 LASTVT LASTVT集集FIRSTVT(P) = a | P a 或或 P Qa留意留意: 在算符文法中在算符文法中, 一个非终结符推导出的一个非终结符推导出的首个算符的位置要么是第一个首个算符的位置要么是第一个, 要么是第二个要么是第二个LASTVT(P) = a | P a 或或 P aQ2) 2) 根据根据 FIRSTVT FIRSTVT集集 和和 LASTVT LASTVT集集计算三种优先关系计算三种优先关系 : 直接查看产生式右部，如有直接查看产生式右部，如有 P ab 或或 PaQb , 那么那么a b 成成 立立 : 假定有产

3、生式的候选形为假定有产生式的候选形为 aP , 对任何对任何 bFIRSTVT(P) , 有有a b成立成立 : 假定有产生式的候选形为假定有产生式的候选形为 Pb , 对任何对任何 aLASTVT(P) , 有有a b成立成立3) 3) 计算计算FIRSTVTFIRSTVT集和集和 LASTVT LASTVT集集(1) (1) 根据定义直观计算根据定义直观计算FIRSTVTFIRSTVT集集(2) (2) 用方式化算法计算用方式化算法计算FIRSTVTFIRSTVT(3) (3) 由简单关系图形计算由简单关系图形计算FIRSTVTFIRSTVT* *(1) (1) 根据定义直观计算根据定义直

4、观计算FIRSTVTFIRSTVT集集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) 用方式

5、化算法计算用方式化算法计算FIRSTVTFIRSTVT集集建立一个布尔数组建立一个布尔数组FP, a , 和栈和栈STACKFP, a=TRUE , 当且仅当当且仅当 aFIRSTVT(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 非空非空 DOBEG

6、IN把把STACK的顶项记为的顶项记为(Q，a) , 托出去托出去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 图中的结点为非终结符的图中的结点为非终结符的FIRSTVT(P)和终结和终结符符对每个形如对每个形如Pa或或PQ a 的产生式

7、的产生式, 由由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)FIRSTVT(F)FIRSTVT(P)+*(iFIRSTVT(E)FIRSTVT(E

8、)4) 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 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(