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

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

3、先分析法算符優(yōu)先分析法 4.4.1 方法概述 1 特點(diǎn) 適合分析各類表達(dá)式; 宜于手工實(shí)現(xiàn); 規(guī)定運(yùn)算符之間的優(yōu)先順序(優(yōu)先關(guān)系，結(jié)合性質(zhì))。 通過(guò)比較算符之間的優(yōu)先關(guān)系確定可歸約串。4.4.1 方法概述 2 優(yōu)先關(guān)系 例 文法GE： E E+E|E*E|(E)|id 對(duì)輸入串id+id*id的規(guī)范歸約過(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)先關(guān)系種類 任何兩個(gè)a和b可能的優(yōu)先關(guān)系有3種： a

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

5、出現(xiàn)在算符文法的句型 中，則 中任何含b的短語(yǔ)必含有A。4.4.2 算符優(yōu)先文法的定義 2 算符優(yōu)先關(guān)系的定義 在OG中定義算符優(yōu)先關(guān)系： (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ān)系的定義 規(guī)定： 若S a或S Ca，則$ a 若S a或S aC，則a $4.4.2 算符優(yōu)先文法的定義 3 算符優(yōu)先文法的定義 設(shè)有一個(gè)不含 規(guī)則的OG文法G， 如果任意兩個(gè)終結(jié)符間至多有一種算符關(guān)系存在， 則稱G是算符優(yōu)先文法，也稱OPG

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

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

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

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

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