1、4.3 自下而上分析法的一般原理 1 1 自下而上語法分析概述自下而上語法分析概述 基本思想：基本思想：用一個寄存文法符號的棧棧，將一個輸入串反向歸約歸約至文法的開始符號。 特點：特點：效率高、文法限制少。1 1 自下而上語法分析概述自下而上語法分析概述 移進歸約過程實例。 例4.11 設有文法GA： (1)A aBcDe (2)B b (3)B Bb (4)D d對輸入串a(chǎn)bbcde$的移進歸約分析過程 對輸入串a(chǎn)bbcde$移進歸約分析過程： 步驟 符號棧 輸入串 動作012345678910$a$ab$aB$aBb$aB$aBc$aBcd$aBcD$aBcDe$Aabbcde$bbcde

2、$bcde$bcde$cde$cde$de$e$e$a進棧b進棧用B b歸約b進棧用B Bb歸約c進棧d進棧用D d歸約e進棧用A aBcDe歸約分析成功2 2 移進歸約的基本思想 (1)用一個棧寄存文法符號，將一個終結符推進棧; (2)是將0個或多個符號從棧中彈出，用相應產(chǎn)生式的左部一個非終結符壓入棧; 把棧頂被歸約的一串符號稱為 (3)重復這一過程直至整個輸入串分析完畢; (4)最終棧中，則所分析的輸入串是文法的正確句子;否則，出錯。可歸約串可歸約串3 分類 算符優(yōu)先分析法算符優(yōu)先分析法 規(guī)范歸約分析法 簡單優(yōu)先分析法 LR分析法分析法用 刻畫可歸約串用 刻畫可歸約串4.4 4.4 算符優(yōu)

3、先分析法算符優(yōu)先分析法 4.4.1 方法概述 1 特點 適合分析各類表達式; 宜于手工實現(xiàn); 規(guī)定運算符之間的優(yōu)先順序(優(yōu)先關系，結合性質(zhì))。 通過比較算符之間的優(yōu)先關系確定可歸約串。4.4.1 方法概述 2 優(yōu)先關系 例 文法GE： E E+E|E*E|(E)|id 對輸入串id+id*id的規(guī)范歸約過程。(1)id+id*id(2)E+id*id(3)E+E*id(4)E+E*E(5)E+E(6)E(1)id+id*id(2)E+id*id(3)E+E*id(4)E*id(5)E*E(6)E*優(yōu)先于：優(yōu)先于*：4.4.1 方法概述 3 優(yōu)先關系種類 任何兩個a和b可能的優(yōu)先關系有3種： a

4、 b: a的優(yōu)先級低于b a b: a的優(yōu)先級等于b a b: a的優(yōu)先級高于b注：優(yōu)先關系與出現(xiàn)的有關，不同于數(shù)學符號。4.4.1 方法概述 4 優(yōu)先關系矩陣(表) 矩陣的行和列都是文法的終結符; 矩陣元素是兩終結符間的優(yōu)先關系。 算符優(yōu)先分析法借助優(yōu)先關系表尋找句型的可歸約串。 算符優(yōu)先關系表實例 + * id ( ) $ + * id ( ) $棧頂?shù)谝粋€終結符當前輸入串首字符4.4.2 算符優(yōu)先文法的定義 1 算符文法的定義 設有文法G，若G中形如U VW的規(guī)則，其中V和W為，則G稱為算符文法，也稱OG文法。性質(zhì)： 1.在算符文法中任何句型都不包含兩個相鄰的非終結符。 2.如Ab或bA

5、出現(xiàn)在算符文法的句型 中，則 中任何含b的短語必含有A。4.4.2 算符優(yōu)先文法的定義 2 算符優(yōu)先關系的定義 在OG中定義算符優(yōu)先關系： (1)a b :含有P ab，或 P aQb的 規(guī)則。 (2)a b :含有P aR的規(guī)則，且R b或 R Qb (3)a b:含有P Rb的規(guī)則，且R a或 R aQ。4.4.2 算符優(yōu)先文法的定義 2 算符優(yōu)先關系的定義 規(guī)定： 若S a或S Ca，則$ a 若S a或S aC，則a $4.4.2 算符優(yōu)先文法的定義 3 算符優(yōu)先文法的定義 設有一個不含 規(guī)則的OG文法G， 如果任意兩個終結符間至多有一種算符關系存在， 則稱G是算符優(yōu)先文法，也稱OPG

6、文法。 結論：算符優(yōu)先文法是無二義的。4.4.3 算符優(yōu)先關系表的構造 1 FIRSTVT集、 LASTVT集 FIRSTVT(A)=b|A b 或 A Bb ,b VT,B VN 即：非終結符往下推導所有可能出現(xiàn)的首個算符的集合LASTVT(A)=a|A a A aB, a VT,B VN 即：非終結符往下推導所有可能出現(xiàn)的最后一個算符的集合4.4.3 算符優(yōu)先關系表的構造 2 算符優(yōu)先關系表的構造方法 (1)為每個非終結符計算FIRSTVT(A),LASTVT(A) (2)計算算符之間的優(yōu)先關系，并填表。計算方法： 關系:若Aab 或A aBb,則a b 關系:若A aB,則 b FIRS

7、TVT(B),a b 關系:若A Bb,則 a LASTVT(B),a b (3) 最后，在表中填入的優(yōu)先關系：對FIRSTVT(S)中所有b,置$ b; 對 LASTVT(S)中所有a,置a $. 置 $ $。 例4.12 文法GE: E E+T|T T T*F|F F (E)|id構造該文法的算符優(yōu)先關系表。 FIRSTVT LASTVT E T F +,*,(,id *,(,id (,id +,*,),id *,),id ),idHomework: (P105)- 4.5 (2)4.4.4 算符優(yōu)先分析算法的設計 0 算符優(yōu)先分析法與規(guī)范歸約的區(qū)別算符優(yōu)先分析法:只考慮終結符之間的優(yōu)先關

8、系來確定可歸約串，而與非終結符無關。規(guī)范歸約:自上而下最右推導的逆過程。例4.12文法GE: E E+T|T T T*F|F F (E)|id 句子id*id+id的自下向上的語法分析過程。規(guī)范歸約是最右推導的逆過程。算符優(yōu)先分析法中，去掉了單個非終結符的歸約。EE+TTT*FFididFid4.4.4 算符優(yōu)先分析算法的設計 1 最左素短語定義： 句型的素短語是 一個短語；至少包含一個終結符；除自身之外不再包含其他素短語處于句型最左邊的素短語為最左素短語求文法GE的句型T+T*F+id的素短語和最左素短語E E+T|T T T*F|F F (E)|idE+ETE+TTT*FFid短語：,T*

9、F,T+T*Fid,T+T*F+id素短語：最左素短語：T*F, idT*FHomework: (P105)-4.64.4.4 算符優(yōu)先分析算法的設計 2 識別最左素短語方法算符優(yōu)先文法的句型可以表示為：$N1a1N2a2NnanNn+1$ ,Ni為VN或空,ai為VT.句型的最左素短語是滿足下列條件的最左子串NiaiNi+1ai+1.NjajNj+1 : ai-1 ai ai ai+1 , . ,aj-1 aj aj aj+1注意:出現(xiàn)在ai左端的Ni和aj右端的Nj+1屬于素短語.求句型 $T+T*F+id$ 的最左素短語。 把該句型寫成算符優(yōu)先分析形式: $N1a1N2a2N3a3a4$

10、 由優(yōu)先表得: $ a1 a2 a3 a4 $ 故最左素短語為:N2a2N3 即:T*F4.4.4 算符優(yōu)先分析算法的設計 3 算符優(yōu)先算法過程(移進歸約) (1)使用棧存放文法符號,初始化為$。 (2)如果當前棧頂終結符和待輸入符號之間的關系是 或 ,則移進輸入符號。 (3)如果當前棧頂終結符和待輸入符號之間的優(yōu)先關系是 ,表明已找到最左素短語的尾,查找棧內(nèi)優(yōu)先關系相同的符號串,進行歸約。 (非終結符對可歸約串的識別沒有影響,在歸約時可用任意的N代替。) (4)如果出現(xiàn)兩個終結符之間沒有任何優(yōu)先關系,則出錯。 (5)當讀到句子結束符$,棧中只剩下$N時,成功。對4.12中的文法GE： E E+T|T T T*F|F F (E)|id寫出輸入串id+id$的算符優(yōu)先分析過程。 S棧優(yōu)先關系 當前符號 輸入流 動作$id$N$N+$N+id$N+N$N id + + id $ $ $+id$id$id$ 移進 歸約 移進 移進 歸約 歸約 接受 S棧優(yōu)先關系 當前符號 輸入流 動作 4.4.6 算符優(yōu)先分析法的局限性 1 一般語言的文法很難滿足算符優(yōu)先文法的條件，僅在表