自底向上優(yōu)先分析法(2)(完整版)
【正文】 b成 立 。 為了求 ＜ FIRSTVT(T) * F 則有： * ＜ ＞ ↑ E ) 則有： LASTVT(E) ＞ ＞ ＜ ＜ ＜ ＜ ＞ ＞ 表 表達(dá)式文法算符優(yōu)先關(guān)系表 ＜ FIRSTVT(F) ( E 則有： ( ＜ ＞ 關(guān)系 ， 需先由定義 FIRSTVT集合和LASTVT集合 ， 結(jié)果為： 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} 在計(jì)算每個(gè)非終結(jié)符的 FIRSTVT集合和 LASTVT集合時(shí)，可先考慮文法中含有 E→T ， T→F ， F→P 形式的產(chǎn)生式，由定義 P的 FIRSTVT集合和 LASTVT集合也屬于 F的 FIRSTVT集合和 LASTVT集合，同樣 F的也屬于 T的，T的也屬于 E的。 若有表達(dá)式文法為： (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 解：計(jì)算表達(dá)式文法的優(yōu)先關(guān)系為： a) 關(guān)系 由產(chǎn)生式 (0) E′ →E 和 (6) P→(E) ,可得 ‘ ’ ‘’， ‘ （ ’ 39。關(guān)系 : 求出每個(gè)非終結(jié)符 B的 FIRSTVT(B)， 在如下形式的產(chǎn)生式 A→ ? aB? 中 ， 對(duì)每一 b∈FIRSTVT(B), 有 a＜ 三、算符優(yōu)先文法的定義 結(jié)論：算符優(yōu)先文法是無二義性的。 二、算符優(yōu)先關(guān)系的定義 由定義 ： a) 若有產(chǎn)生式 A→a ? 或 A→Ba ? 則 a∈FIRSTVT(A) ， 其中 A、 B為非終結(jié)符 ， a為終結(jié)符 。*39。 ＞ ＜ ＞ ＞ ＞ ( ＞ ＞ ＜ 39。 ③ +， 優(yōu)先級(jí)最低。算符優(yōu)先分析的可歸約串是當(dāng)前符號(hào)棧中的符號(hào)和剩余的輸入符號(hào)構(gòu)成句型的最左素短語 。 若查不到轉(zhuǎn)出錯(cuò)處理。 簡(jiǎn)單優(yōu)先文法分析算法的主要思想是找出句柄并歸納之。還有先括號(hào)內(nèi)后括號(hào)外的規(guī)定。 歸約：把分析棧頂?shù)木浔鷼w約為一非終極符。 例：考慮文法 G(E)： E→E +T |T T→T*F | F F→i| (E) 并假定輸入串為（ i+i)*i，考察 自底向上的分析過程。 所以，任何自底向上分析方法的關(guān)鍵就是要找出當(dāng)前句型的句柄，然后根據(jù)產(chǎn)生式判別將它歸約成什么樣的非終結(jié)符號(hào)。 一、自底向上分析的一般過程： 先設(shè)置一個(gè)寄存符號(hào)的棧，稱為分析棧。作為初始狀態(tài)，先將符號(hào)串的開始標(biāo)志 “ ”壓入分析棧中，作為棧底符號(hào)，則分析過程為： 步驟 分析棧 輸入串 動(dòng)作 1 (i+i)*i 移進(jìn) 2 ( i+i)*i 移進(jìn) 3 (i +i)*i 歸約 4 (F +i)*i 歸約 5 (T +i)*i 歸約 6 (E +i)*i 移進(jìn) 7 (E+ i)*i 移進(jìn) 8 (E+i )*i 歸約 9 (E+F )*i 歸約 步驟 分析棧 輸入串 動(dòng)作 10 (E+T )*i 歸約 11 (E )*i 移進(jìn) 12 (E) *i 歸約 13 F *i 歸約 14 T *i 移進(jìn) 15 T* i 移進(jìn) 16 T*i 歸約 17 T*F 歸約 18 T 歸約 19 E 接受 分析過程圖表： 步驟 分析棧 輸入串 動(dòng)作 1 (i+i)*i 移進(jìn) 2
高考資料相關(guān)推薦
鄂ICP備17016276號(hào)-1