1、 簡單優先分析法是一種從左到右掃描、最左歸約分析法；它屬于自底向上分析方法。 該方法利用文法符號之間的優先關系來確定待歸約的句柄 ，即可確定當前句型的句柄。5.5 簡單優先分析法 利用一個分析表，登記選擇句柄產生式的知識； 利用一個分析棧，記錄分析過程；【分析算法】依次讀取單詞，并進行如下操作： 當棧頂出現句柄時，規約之，否則移進。 5.5.1. 簡單優先分析法基本概念 簡單優先分析法的基本要點有三：1. 什么是簡單優先分析法？ 2. 簡單優先分析過程示例 符號串： = abbeae #SaAeBSbbaG(S): SaAeB|b ASb|e BaAAe 句柄產生式 操 作 剩余串 w 分析棧

2、 移進,NEXT a e # e# a 移進,NEXT e # a# a A 移進,NEXT # e# a A e 歸約 A - e # aAe a 歸約 B - aA # aAe a A - Sb S - b 歸約 e a e # b# a 移進,NEXT b b e a e # a# 歸約 a e # e # a S 移進,NEXT e a e # b# a 移進,NEXT b e a e # b# A A a a b e e句柄(接上頁) 利用分析棧記錄行分析過程：【注】何時棧頂出現句柄？怎樣求當前句柄產生式 ？設 待分析的符號串: abbeae# S b# aAe # B句柄 S -

3、aAeB 歸約# # S OK同時歸約者為相等關系，記作 ；3. 文法符號之間的優先關系歸約過程中如何確認句柄？ 是否是句柄，還要看其所在符號串中的位置。語法樹從語法樹上，找出優先關系（指相臨符號之間）如下： S b，a A，A e，e B 如：左后歸約者為小于關系，記作； 如：ab,ae, e； 如：bb,be 當把優先關系納入待分析的符號串時，有如下關系： # a b e a # # a e a # # a A e a # # a A e # # # 結論：一個句型的句柄，位于第一次（自左至右）出現在之間的符號串！ 從文法中獲取優先關系! 設si ，sj是兩個文法符號; 如：a A，A e

4、，e B，S b； si sj ，當且僅當有Usi sj ； 優先關系的定義 G(S): SaAeB|b ASb|e BaA si +如：ae，aS，aa，ab，esj ，當且僅當有 UVsj ，且 V si； = +如：bb，Bb，Ab，eb。 (3)頭符號集合和尾符號集合 設 AVN， si ，sj是兩個文法符號;則: FIRSTVT(A)=si| A si, = +LASTVT(A) = sj|A sj。 = +【例5.12】G(S): SaAeB|b，ASb|e，BaA S A B a b e S A B a e S A BFIRSTVT a , b S,e,a,b aLASTVT B

5、,b,A,e b , e A , b , e 頭符號集合尾符號集合優先矩陣表項=空表示兩個符號不可能相臨。 +簡單優先分析器的基本組成：優先分析法要求文法應是簡單優先文法。優先矩陣分析表 優先分析控制器 分析中只查看當前符號就可確認句柄；5.5.2 簡單優先分析器設計1.簡單優先文法及其判定 文法產生式沒有相同的右部； 如A ，B ， 滿足下述特點的文法稱為簡單優先文法。例5.12 文法，就是簡單優先文法，請看：文法符號之間至多有一種優先關系！ 【算法】 si sj ， 當且僅當有Usi sj ； si sj ， 當且僅當有UVsj，且siLASTVT(V)。 2. 簡單優先分析矩陣分析表構造

6、設 W,VVN,si，sj是兩個文法符號; 簡單優先分析表是優先分析法的知識表,是文法的一種機內表示形式：終結符 +非終結符+# a Z #優先關系符號終結符+非終結符+#3. 簡單優先控制程序設計開始PUSH(#)NEXT(w)查優先分析表R(Xk,w)=? 空?nerr(#S#) 結束PUSH WPOP(sj)，POP(sj-1)，POP(si)；PUSH(A)。從sj（棧頂符）開始，往棧內查找，找到第一個使si-1?yn只考慮算符（終結符）之間的優先關系 （1）算符文法 設有一文法G，如果G中沒有形如AQR的產生式，其中Q和R為非終結符，則稱該文法為算符文法（OG文法）。 5.5.3 算

7、符優先分析(2)頭符號集合和尾符號集合 設 aVT，P,RVN， 則: FIRSTVT(P)=a| P a 或 P Ra, = +LASTVT(P) =a| P a 或 P aR。 = + = + = +設a,bVT，P,Q,RVN， a b ， 當且僅當有 Pab 或 PaQb ； (3) 算符優先關系定義 a + ab ， 當且僅當有 PRb ，且R a 或 R aQ； = +(4)算符優先文法 如果算符文法G中的任何一對終結符a和b之間，僅滿足上述一種關系，則G就是一個算符優先文法（OPG）。 = + = +習題：【習題5.13】已知下述文法：G(E): E - T | E + T | E - T