[理學(xué)]第6章自底向上優(yōu)先分析-文庫吧資料
2024-10-22 21:23本頁面
【正文】 (1) E?E+T (2)E?T (3)T?T*F (4)T?F (5)F?P^F|P (6)P?(E) (7)P?i 掃描所有形如 A?…aB… 和 A?…Ba… 的規(guī)則 (3)求 關(guān)系 E: 則有 FIRSTVT（ E） +T: 則有 +FIRSTVT(T) *F: 則有＊ FIRSTVT(F) ^F:則有 ^FIRSTVT(F) (E: 則有 (FIRSTVT(E) (4)求 關(guān)系 E: 則有 LASTVT(E) E+:則有 LASTVT(E)+ T*: 則有 LASTVT(T)* P^:則有 LASTVT(P)^ E): 則有 LASTVT(E)) 26 表達(dá)式文法的算符優(yōu)先關(guān)系表 (0)E’?E (1) E?E+T (2)E?T (3)T?T*F (4)T?F (5)F?P^F|P (6)P?(E) (7)P?i FIRSTVT(E’)={} FIRSTVT(E)={+, *, ^, (, i} FIRSTVT(T)={*, ^, (, i} FIRSTVT(F)={^, (, i} FIRSTVT(P)={(, i} LASTVT(E’)={} LASTVT(E)={+, *, ^, ), i} LASTVT(T)={*, ^, ), i} LASTVT(F)={^, ), i} LASTVT(P)={), i} + * ^ i ( ) + * ^ i ( = ) = 27 (0)E’?E (1) E?E+T (2)E?T (3)T?T*F (4)T?F (5)F?P^F|P (6)P?(E) (7)P?i FIRSTVT集合的計(jì)算 (1)若有產(chǎn)生式 A?a… 或 A?Ba…, 則 a∈ FIRSTVT(A) (2)若 a∈ FIRSTVT(B), 且有產(chǎn)生式 A?B…, 則 a∈ FIRSTVT(A) 因此 , 通過布爾數(shù)組 [F, a]和棧 STACK求解 FIRST集合 掃描文法中的每個(gè)非終結(jié)符 (6) (P, i) F?P, T?F, E?T 棧項(xiàng)內(nèi)容為 (F, i), (T, i), (E, i) (5) (P, () F?P, T?F, E?T 棧項(xiàng)內(nèi)容為 (F, (), (T, (), (E, () (4) (F, ^) T?F, E?T 棧項(xiàng)內(nèi)容為 (T, ^), (E, ^) (3) (T, *) E?T 棧項(xiàng)內(nèi)容為 (E, *) (2) (E, +) (1) (E’, ) LASTVT集合也有類似的計(jì)算方法 28 算符優(yōu)先分析算法 1. 算符優(yōu)先分析句型的性質(zhì) 算符文法中的任何一個(gè)句型形式如下 : N1a1N2a2…N nanNn+1 若 Niai……N jajNj+1為句柄 , 則 Ni和 Nj+1在句柄中 , 因?yàn)樗惴姆ǖ娜魏尉湫椭袩o兩個(gè)相鄰的非終結(jié)符 , 且終結(jié)符和非終結(jié)符相鄰時(shí)含終結(jié)符的句柄 , 必含相鄰的非終結(jié)符 . 該句柄中的終結(jié)符之間的關(guān)系為 : ai1ai ai=ai+1=……=a j ajaj+1 29 算符優(yōu)先分析算法 2. 素短語：文法 G的句型的素短語是一個(gè)短語，它至少包含有一個(gè)終結(jié)符號(hào)，并且除它自身以外不再包含其他素短語 . 最左邊的素短語稱為最左素短語 . 例 : 文法 G[E]: T?E+T|T T?T*F|F F?P^F|P P?(E)|i 分析句型 T+T*F+i的短語 短語 : T, T*F, T+T*F, i , T+T*F+i都是 素短語有 : i和 T*F. 其中 T*F是最左素短語 , 不是句柄 ,滿足條件 : ai1ai=ai+1=……=a jaj+1 E E + T E + T T T * F F P i 30 算符優(yōu)先分析算法 3. 算符優(yōu)先分析歸約過程算法 先定義優(yōu)先級(jí)，在分析過程中通過比較相鄰運(yùn)算符之間的優(yōu)先級(jí)來確定句型的“句柄”并進(jìn)行歸約 . 定理 ：一個(gè) OPG句型的最左素短語是滿足下列條件的 最左子串： aj1Njaj…N iaiNi+1ai+1 其中 aj1aj aj=aj+1, aj+1= aj+2 ,…, a i2= ai1, ai1= ai ai ai+1 最左素短語 ？ 31 算符優(yōu)先分析法的實(shí)現(xiàn)： 基本部分是找句型的最左子串（最左素短語）并進(jìn)行規(guī)約。 + + . . . + + + 21 算符優(yōu)先文法的定義 A A A … a ? b… a=b ? b… P … a B… a b … a ?
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1