編譯原理5：算符優(yōu)先關(guān)系表構(gòu)造

1、5.2.1 算符優(yōu)先文法及優(yōu)先表構(gòu)造算符優(yōu)先文法及優(yōu)先表構(gòu)造 1、算符文法、算符文法2、算符優(yōu)先關(guān)系的定義、算符優(yōu)先關(guān)系的定義3、算符優(yōu)先文法、算符優(yōu)先文法 4、優(yōu)先關(guān)系表的構(gòu)造、優(yōu)先關(guān)系表的構(gòu)造4、優(yōu)先關(guān)系表的構(gòu)造、優(yōu)先關(guān)系表的構(gòu)造1) 1) 定義定義 FIRSTVTFIRSTVT集集 和和 LASTVTLASTVT集集2) 2) 根據(jù)根據(jù) FIRSTVTFIRSTVT集集 和和 LASTVTLASTVT集集 計(jì)算計(jì)算三種優(yōu)先關(guān)系三種優(yōu)先關(guān)系 3) 3) 計(jì)算計(jì)算FIRSTVTFIRSTVT集集和和 LASTVTLASTVT集集4) 4) 構(gòu)造優(yōu)先關(guān)系表構(gòu)造優(yōu)先關(guān)系表 1) 1) 定義定義F

2、IRSTVTFIRSTVT集集 和和 LASTVTLASTVT集集FIRSTVT(P) = a | P a 或或 P Qa注意注意: 在算符文法中在算符文法中, 一個(gè)非終結(jié)符推導(dǎo)出的一個(gè)非終結(jié)符推導(dǎo)出的首個(gè)算符的位置要么是第一個(gè)首個(gè)算符的位置要么是第一個(gè), 要么是第二個(gè)要么是第二個(gè)LASTVT(P) = a | P a 或或 P aQ2) 2) 根據(jù)根據(jù) FIRSTVTFIRSTVT集集 和和 LASTVTLASTVT集集計(jì)算三種優(yōu)先關(guān)系計(jì)算三種優(yōu)先關(guān)系 : 直接查看產(chǎn)生式右部，如有直接查看產(chǎn)生式右部，如有 P ab 或或 PaQb , 則則a b 成成 立立 : 假定有產(chǎn)生式的候選形為假定有

3、產(chǎn)生式的候選形為 aP , 對(duì)任何對(duì)任何 bFIRSTVT(P) , 有有a b成立成立 : 假定有產(chǎn)生式的候選形為假定有產(chǎn)生式的候選形為 Pb , 對(duì)任何對(duì)任何 aLASTVT(P) , 有有a b成立成立3) 3) 計(jì)算計(jì)算FIRSTVTFIRSTVT集和集和 LASTVTLASTVT集集(1) (1) 根據(jù)定義直觀計(jì)算根據(jù)定義直觀計(jì)算FIRSTVTFIRSTVT集集(2)(2) 用形式化算法計(jì)算用形式化算法計(jì)算FIRSTVTFIRSTVT(3)(3) 由簡(jiǎn)單關(guān)系圖形計(jì)算由簡(jiǎn)單關(guān)系圖形計(jì)算FIRSTVTFIRSTVT* *(1)(1) 根據(jù)定義直觀計(jì)算根據(jù)定義直觀計(jì)算FIRSTVTFIRS

4、TVT集集a) 若有產(chǎn)生式若有產(chǎn)生式 Pa 或或 pQa 則則 aFIRSTVT(P)b) 若有產(chǎn)生式若有產(chǎn)生式 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# 為對(duì)原文法的擴(kuò)充為對(duì)原文法的擴(kuò)充# 表示句子括號(hào)表示句子括號(hào)(2)(2) 用形式化算法計(jì)算用形式化算法計(jì)算FIRSTVTFIRST

5、VT集集建立一個(gè)布爾數(shù)組建立一個(gè)布爾數(shù)組FP, a , 和棧和棧STACKFP, a=TRUE , 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) a FIRSTVT(P)PROCEDUE INSERT(P, a)IF NOT FP, a THENBEGIN FP, a:=TRUEPUSH(P, a) ONTO STACKEND MAINBEGIN (MAIN)FOR 每個(gè)非終結(jié)符每個(gè)非終結(jié)符P和終結(jié)符和終結(jié)符aDO FP, a:= FALSE;FOR 每個(gè)形如每個(gè)形如Pa或或PQ a 的產(chǎn)生式的產(chǎn)生式DO INSERT(P, a)WHILE STACK 非空非空 DOBEGIN把把STACK的頂項(xiàng)記為的頂項(xiàng)記為(Q，a)

6、 , 托出去托出去FOR 每個(gè)形如每個(gè)形如PQ 的產(chǎn)生式的產(chǎn)生式 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用形式化算法計(jì)算用形式化算法計(jì)算FIRSTVT集集過(guò)程見(jiàn)黑板過(guò)程見(jiàn)黑板(3)(3) 由簡(jiǎn)單關(guān)系圖形計(jì)算由簡(jiǎn)單關(guān)系圖形計(jì)算FIRSTVT FIRSTVT 1.圖中的結(jié)點(diǎn)為非終結(jié)符的圖中的結(jié)點(diǎn)為非終結(jié)符的FIRSTVT(P)和和終結(jié)符終結(jié)符2.對(duì)每個(gè)形如對(duì)每個(gè)形如Pa或或PQ a 的產(chǎn)生式的產(chǎn)生式, 由由FIRSTVT(P)結(jié)點(diǎn)結(jié)

7、點(diǎn)到到結(jié)點(diǎn)結(jié)點(diǎn)a用箭弧連接用箭弧連接3.對(duì)每個(gè)形如對(duì)每個(gè)形如PQ 的產(chǎn)生式，的產(chǎn)生式， 由由FIRSTVT(P)到到FIRSTVT(Q)用箭弧連接用箭弧連接4.對(duì)每個(gè)非終結(jié)符的對(duì)每個(gè)非終結(jié)符的FIRSTVT(P) , 經(jīng)箭弧有路徑能到達(dá)的經(jīng)箭弧有路徑能到達(dá)的終結(jié)符結(jié)點(diǎn)終結(jié)符結(jié)點(diǎn)a , 則有則有a FIRSTVT(P)補(bǔ)充補(bǔ)充(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) 構(gòu)造優(yōu)先關(guān)系表構(gòu)造優(yōu)先關(guān)

8、系表FOR 每個(gè)產(chǎn)生式每個(gè)產(chǎn)生式 PX1 X2 Xn DO FOR i:=1 TO n-1 DO IF Xi 和和 X i+1 均為終結(jié)符均為終結(jié)符THEN 置置 Xi X i+1 IF Xi 和和 X i+2 均為終結(jié)符均為終結(jié)符, X i+1 為非終結(jié)符為非終結(jié)符 , i n-2, THEN 置置 Xi X i+2 IF Xi為終結(jié)符為終結(jié)符, 但但X i+1 為非終結(jié)符為非終結(jié)符 THEN FOR FIRSTVT(X i+1 )中的每個(gè)中的每個(gè)a DO 置置 Xi a IF Xi為非終結(jié)符為非終結(jié)符, 但但X i+1 為終結(jié)符為終結(jié)符 THEN FOR LASTVT(X i )中的每個(gè)中的每個(gè)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構(gòu)造算符優(yōu)先關(guān)系表構(gòu)造算符優(yōu)先關(guān)系表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