第6章自底向上優(yōu)先分析法2013

1、1第六章第六章 自底向上優(yōu)先分析法自底向上優(yōu)先分析法2本章內(nèi)容本章內(nèi)容 n引子：自底向上分析的一般原理引子：自底向上分析的一般原理n6.1 自底向上優(yōu)先分析概述自底向上優(yōu)先分析概述n6.2 簡單優(yōu)先分析法（了解）簡單優(yōu)先分析法（了解）n6.3算符優(yōu)先分析法算符優(yōu)先分析法3n一、自底向上分析的一、自底向上分析的基本思想基本思想q對輸入串從左到右掃描，并逐個移入移入棧中。邊移入邊分析，一旦棧頂符號串形成某個句型的可歸約串（它對應(yīng)某產(chǎn)生式右部），就用該產(chǎn)生式左部的非終極符號代替它，完成進一步歸約歸約。q重復(fù)這一過程直到歸約到棧中，只剩下開始符號和右邊界符#，成功。否則，報錯。引子引子:自底向上分析的

2、一般原理自底向上分析的一般原理4n例.(p94) (1) S aAcBe (2) A aAcBe (2) A b (3) A b (3) A Ab (4) B Ab (4) B d, d, 對對輸入串輸入串a(chǎn)bbcde#abbcde#語法分析走一遍動作。語法分析走一遍動作。 符號棧符號棧 輸入串輸入串 0 # abbcde#0 # abbcde# 1 #a bbcde#1 #a bbcde# 2 #a 2 #ab b bcde# bcde# 用用A Ab b歸約歸約 3 #a 3 #aA A bcde# bcde# 4 #a 4 #aAb Ab cde# cde# 用用A AAbAb歸約歸約

3、5 #a5 #aA A cde# cde# 6 #aAc de# 6 #aAc de# 7 #aAc 7 #aAcd d e# e# 用用B Bd d歸約歸約 8 #aAc 8 #aAcB B e# e# 9 # 9 #aAcBe aAcBe # # 用用S SaAcBeaAcBe歸約歸約 10 #S # 10 #S #5二、自底向上分析的二、自底向上分析的關(guān)鍵關(guān)鍵n如何精確定義可歸約串并識別。如何精確定義可歸約串并識別。n對可歸約串(p23)的不同定義形成不同的自下而上分析方法：1.在規(guī)范歸約規(guī)范歸約分析中，用句柄來刻畫可歸約串 (LR, 簡單優(yōu)先)2.在算符優(yōu)先分析算符優(yōu)先分析中，是用最左

4、素短語來刻畫可歸約串。n根據(jù)識別可歸約串的不同方法，也形成不同的自下而上分析法。n簡單優(yōu)先分析法和LR分析法都是規(guī)范歸約分析法（句柄可歸約串），但它們識別句柄的方法不同：q1.LR分析法是根據(jù)歷史、現(xiàn)實、展望三者信息來確定棧頂符號串是否形成句柄q2.簡單優(yōu)先分析法是根據(jù)文法符號之間的優(yōu)先關(guān)系來確定句柄。66.1 自底向上優(yōu)先分析法概述自底向上優(yōu)先分析法概述n1.簡單優(yōu)先分析法：對一文法求出所有符號之間的優(yōu)先關(guān)系，并據(jù)此確定句柄（規(guī)范歸約）n2.算符優(yōu)先分析法：只考慮算符之間的優(yōu)先關(guān)系，不考慮VN的優(yōu)先關(guān)系。只要找到可歸約串就歸約，并不考慮歸約到哪個非終極符。76.2 簡單優(yōu)先分析法（了解）簡單

5、優(yōu)先分析法（了解）n6.2.1 優(yōu)先關(guān)系優(yōu)先關(guān)系qX=Y iff AXYqXY iff ABD且B X和D Yn例6.2 SbAb, A(B | a, BAa)(1)相等：b=A，A=b，(=B，A=a，a=)(2) : 由bA及A(B | a , BAa) ，可得，可得 b ( ， b a，( A， ( ， ( : 由 S bAb , A(B | a 及及 B Aa），），可得可得 B b ， B a a b ， a a ) b ， ) a +86.2.2 簡單優(yōu)先文法的定義簡單優(yōu)先文法的定義 一、一、定義定義簡單優(yōu)先文法滿足兩個條件簡單優(yōu)先文法滿足兩個條件（1）任意兩個文法符號之間最多只有

6、一種優(yōu)先關(guān)系成立）任意兩個文法符號之間最多只有一種優(yōu)先關(guān)系成立（2）在）在G中任意兩個產(chǎn)生式?jīng)]有相同的右部（歸約唯一）中任意兩個產(chǎn)生式?jīng)]有相同的右部（歸約唯一）分析：棧頂為分析：棧頂為aiqai ai+1 歸約（已形成句柄）歸約（已形成句柄）9二、二、簡單優(yōu)先分析法簡單優(yōu)先分析法n步驟：步驟：構(gòu)造文法的優(yōu)先關(guān)系矩陣，將構(gòu)造文法的優(yōu)先關(guān)系矩陣，將G規(guī)則保存，設(shè)規(guī)則保存，設(shè)置符號棧置符號棧S（1）將輸入串）將輸入串a(chǎn)1,a2,an #逐個移入符號棧逐個移入符號棧S中，直到棧頂符中，直到棧頂符號號ai ai+1為止。為止。（2）棧頂）棧頂ai為句柄尾，由此向左在棧中找句柄開頭符號為句柄尾，由此向左在

7、棧中找句柄開頭符號ak（找（找到到ak-1 ak為止）為止）（3）由句柄）由句柄akak+1ai在產(chǎn)生式中查找右部為在產(chǎn)生式中查找右部為akai的產(chǎn)生式，的產(chǎn)生式，若找到則用相應(yīng)左部代替句柄（歸約），否則出錯，串不是若找到則用相應(yīng)左部代替句柄（歸約），否則出錯，串不是合法句子。合法句子。6.2.2 簡單優(yōu)先文法的定義簡單優(yōu)先文法的定義106.3 6.3 算符優(yōu)先分析法算符優(yōu)先分析法n特別適合于分析程序中各類表達式且宜于手工實現(xiàn)簡單、直觀（僅適用于表達式的語法）n6.3.1 方法概述n6.3.2 算符優(yōu)先文法的定義n6.3.3 算符優(yōu)先關(guān)系表的構(gòu)造（由定義）n6.3.4 算符優(yōu)先分析算法n6.3

8、.6 算符優(yōu)先分析法的局限（p120）11n一、方法一、方法n算符優(yōu)先分析法就是依據(jù)四則運算過程而設(shè)計的一種語言分析方法。首先要規(guī)定運算符（廣義為終結(jié)符）之間的優(yōu)先關(guān)系和結(jié)合性質(zhì)，然后比較相鄰運算符的優(yōu)先級來確定句型的可歸約串并進行歸約6.3.1 算符優(yōu)先分析法概述算符優(yōu)先分析法概述12n實例分析：GE:EE+E | E*E |(E)|id（歧義文法）句子id+id*id有兩個不同的規(guī)范歸約(歸約中句柄不唯一)：第1個規(guī)范歸約: (1)id+id*id (2)E E+id*id (3)E+E E*id (4)E+E*E E (5)E+E E (6)E E第2個規(guī)范歸約過程： (1)id+id*

9、id (2)E E+id*id (3)E+E E*id (4)E E*id (5)E*E E (6)E E6.3.1 算符優(yōu)先分析法概述算符優(yōu)先分析法概述13n分析：句型E+E*id (1) id是它的句柄(2) E+E是它的句柄n原因：沒有定義+和*的優(yōu)先關(guān)系(1) 假定*優(yōu)先于+，不能立即把E+E歸約為E(2) 假定+優(yōu)先于*，因此先把E+E歸約為En決定因素：相鄰兩個終極符之間的優(yōu)先關(guān)系6.3.1 算符優(yōu)先分析法概述算符優(yōu)先分析法概述14二、算符優(yōu)先分析法的關(guān)鍵二、算符優(yōu)先分析法的關(guān)鍵n關(guān)鍵關(guān)鍵：如何定義任意兩個可能相鄰出現(xiàn)的終極符：如何定義任意兩個可能相鄰出現(xiàn)的終極符a和和b之間的優(yōu)先

10、關(guān)系。之間的優(yōu)先關(guān)系。n優(yōu)先關(guān)系符： a b a的優(yōu)先級大于bn與出現(xiàn)的左右次序有關(guān)，a a15三、適用范圍三、適用范圍n算符優(yōu)先分析法只適用于算符優(yōu)先文法， 即對文法有一定要求。166.3.2 算符優(yōu)先文法的定義算符優(yōu)先文法的定義1. 算符文法的定義（算符文法的定義（Operater Grammar） 設(shè)有文法G，若G中沒有形如ABC的產(chǎn)生式，其中B,CVN，則稱G為算符文法，也稱為OG文法。n算符文法具有兩個重要性質(zhì)：（1）在OG文法中，任何句型都不包含兩個相鄰的非終結(jié)符。（2）若Ab或bA出現(xiàn)在算符文法的句型中，A VN，b VT，則中任何含b的短語必含有A172. 定義任意兩個終結(jié)符號

11、之間的優(yōu)先關(guān)系定義任意兩個終結(jié)符號之間的優(yōu)先關(guān)系n設(shè)G是一個不含規(guī)則的OG文法，a、b是任意兩個終結(jié)符，A、B、C是非終結(jié)符，算符優(yōu)先關(guān)系=, 定義如下：(1) a =b當且僅當G中含有形如Aab或AaBb規(guī)則(2) a b當且僅當G中含有形如ABb產(chǎn)生式且 B a或 B aC+6.3.2 算符優(yōu)先文法的定義算符優(yōu)先文法的定義18圖（a）：為或為C（a，b在同一可歸約串中，同時歸約）圖（b）：a，b不在同一可歸約串中，b先歸約，所以a b）193. 算符優(yōu)先文法的定義算符優(yōu)先文法的定義(Operater Precedence G)n設(shè)有一個不含規(guī)則的算符文法G，如果任意兩個終結(jié)符對(a,b)在

12、, = 三種關(guān)系中只有一種成立，則稱G是算符優(yōu)先文法，也稱OPG文法。n判斷：GE是否是OG，是否是OPG文法。 E E+E | E*E | (E) | id20（1）GE是OG文法（2）GE不是OPG文法EE+EE*E(a) + *+,*之間優(yōu)先關(guān)系不唯一而：G E ：E E+T | TT T*F | FF (E) | id是OPG文法216.3.3 算符優(yōu)先關(guān)系表的構(gòu)造（由定義）算符優(yōu)先關(guān)系表的構(gòu)造（由定義）n根據(jù)優(yōu)先關(guān)系定義，可按如下方法直接構(gòu)造優(yōu)先關(guān)系表。首先，對G中每個非終結(jié)符A，定義兩個集合：FIRSTVT(A)=b | A b或A Bb, bVT, BVNLASTVT(A)=a

13、| A a或A aB, aVT, BVNn三種優(yōu)先關(guān)系：（1）對形如Aab, AaBb,有a = b（2）對形如AaB, 有a b, aLASTVT(B)+22n1.算法基于兩條規(guī)則算法基于兩條規(guī)則n求得每個VN的FIRSTVT(A)）(1) 若有產(chǎn)生式Aa或ABa, 則aFIRSTVT(A)(2) 若aFIRSTVT(B)，且有產(chǎn)生式AB，則 aFIRSTVT(A)n類似的方法求得每個VN的LASTVT(A)(1) 若有產(chǎn)生式A a或A aB, 則aLASTVT(A)(2) 若aLASTVT(B)，且有產(chǎn)生式A B，則a aLASTVT(A)6.3.3 算符優(yōu)先關(guān)系表的構(gòu)造算符優(yōu)先關(guān)系表的構(gòu)

14、造232. 算法描述算法描述p112 Procedure Insert(A,a); 功能：求FIRSTVT元素 IF NUT FA,a THEN Begin FA,a:=TRUE PUSH(A,a) ONTO STACK End / 當aFIRSTVT(A)時，置FA,a為真，并將符號對(A,a)下推到棧中 BEGIN (MAIN) For 每一個非終結(jié)符A和終結(jié)符a Do FA,a:=FALSE; For 每個形如Aa或ABa的產(chǎn)生式 Do Insert(A,a) WHILE STACK非空 DO Begin 把STACK的棧頂記為(B,a)彈出 For 每個形如AB的產(chǎn)生式 DO Inse

15、rt(A, a) End End (MAIN)24n例： 0 E# E # 1 E E+T | T 3 T T*F | F 5 F P | F | P 7 P (E) 8 P I對表達式求所有VN的FIRST(B) 第一次掃描后，STACK棧的初值為：6. (p, i) (F, 1) (T, i) (E, i)5. (p, () (F, 1) (T, 1) (E, 1)4. (F, ) (T, ) (E, )3. (T, *) (E, *) 2. (E, +)1. (E, #)(2) 由F P，T F, E T，棧頂(6)的內(nèi)容逐次改變?yōu)? (F, i), (T, i), (E, i)FIRS

16、TVT(E)=#FIRSTVT(E)=+, *, , i, (FIRSTVT(T)=*, , i, (FIRSTVT(F)=, i, (FIRSTVT(P)=i, (彈出25構(gòu)造G的優(yōu)先關(guān)系表算法(1) 為每一個AVN，計算FIRSTVT(A)和LASTVT(A)(2) 執(zhí)行程序 for (每個產(chǎn)生式Ax1x2xn) for (i=1; i=n-1; i+) if (xiVT且xi+1VT) 置xi=xi+1 if (i=n-2且xiVT且xi+1VT且xi+2VN) 置xi=xi+2 if (xiVT, xi+1VN) for (FIRSTVT(xi+1)中的每個變量b) 置xixi+1;

17、(3) 對FIRSTVT(S)中的所有b，置#;置#=#。（S為G的開始符號）26例：設(shè)有GE: EE+T | T, TT*F | F, F(E) | id， 構(gòu)造出算符優(yōu)先關(guān)系表FIRSTVTLASTVTE+,*,(,id+,*,),idT*,(,id*,),idF(,id),id + * ( ) id #+ ( = 空 id # 空 = + (- -)* * (滿足左結(jié)合) （右結(jié)合）優(yōu)先級最高*, / 其次+, -最低()的優(yōu)先級大于括號外的運算符276.3.4 算符優(yōu)先分析算法算符優(yōu)先分析算法n算符優(yōu)先分析算法不是一種規(guī)范歸約。因為在VT 之間定義優(yōu)先關(guān)系無法識別由單個非終結(jié)符組成的可

18、歸約串。即： 不是用句柄，而是用最左素短語刻畫可歸約串。n1. 最左素短語最左素短語（1）短語：）短語：設(shè)G=(VN, VT, P, S)，若有：S * A且A ，則稱是句型相對于A的短語。特別地，如有A ，則稱是相對于A 的直接短語。一個句型的最左直接短語稱為該句型的句柄。+28（2）句型的素短語）句型的素短語至少包含一個VT的短語，并且除自身之外不再包含其它的素短語。n最左邊的素短語稱為最左素短語n例. 考慮文法GE的句型：T+T*F+id，分析句型 T+T*F+id #其短語有： 對應(yīng)VNT+T*F+id (E)T+T*F ET ET*F EId F(T.E)其中素短語：T*F和id最左

19、素短語：T*F （T是該句型的句柄，但不是最左素短語）EE+TE+TE+TT語法樹1. 最左素短語最左素短語292. 識別最左素短語的方法識別最左素短語的方法n由算符文法的性質(zhì)可知，算符文法的任何句型沒有相鄰的VN，其句型應(yīng)為：#N1a1N2a2NnanNn+1#，其中Ni(1=i=n+1)為非終結(jié)符或空，aiVT(i=1n)n定理：一個算符優(yōu)先文法G的任何句型的最左素短語是滿足下列條件的最左子串NiaiNi+1ai+1NjajNj+1：qai-1 aj+1* 出現(xiàn)在ai左端的Ni和出現(xiàn)在aj右端的Nj+1是屬于素短語的30Why?nWhy? OG的任何句型中VT和VN相鄰時，含VT的短語必含相鄰的VNn上述句型 #T+T*F+id# 即 #N1a1N2a2N3a3a4#因有 # + + #故由定理，N2a2N3即T*F是最左素短語313. 算符優(yōu)先分析算法算符優(yōu)先分析算法n算符優(yōu)先分析時自底向上的分析，也為自左向右歸約，它不是規(guī)范歸約n算符優(yōu)先分析的關(guān)鍵：如何找最左素短語NiaiNi+1ai+1NjajNj+1，即滿足：qai-1 aj+1n在當前句型中存在