1、編譯原理編譯原理編譯原理編譯原理編譯原理編譯原理第第6 6章章 自底向上優先分析法自底向上優先分析法 自底向上優先分析概述 簡單優先分析 算符優先分析返回目錄編譯原理編譯原理編譯原理編譯原理編譯原理編譯原理自底向上分析方法自底向上分析方法自底向上分析方法，也稱分析法。實現思想：對輸入符號串自左向右進行掃描，并，邊移入邊分析，（該句型對應某產生式的右部），該產生式的非終結符相應右部的文法符號串，這稱為。，也就確認輸入串是文法的句子。s10） #aacbe # 歸約歸約(saacbe)文法文法gs：(1) s aacbe(2) a b(3) a ab(4) b da b b c de步驟步驟符號棧

2、符號棧輸入符號串輸入符號串動作動作 1） # abbcde# 移進移進 2） #a bbcde# 移進移進a 3） #ab bcde# 歸約歸約(ab) 4） #aa bcde# 移進移進a 5） #aab cde# 歸約歸約(aab) 6） #aa cde# 移進移進 7） #aac de# 移進移進b 8） # aacd e# 歸約歸約(bd) 9） #aacb e# 移進移進11） #s # 接受接受分析符號串分析符號串abbcdeabbcde是否為是否為gsgs的句子？的句子？對輸入串abbcde#的移進-規約分析過程saacbe aacde aabcde abbcde編譯原理編譯原理

3、編譯原理編譯原理編譯原理編譯原理算法應考慮的問題算法應考慮的問題 算法是否能夠終止？算法是否能夠終止？ 算法是否快速？算法是否快速？ 算法是否能夠處理所有的情況？算法是否能夠處理所有的情況？ 在每一步中如何選擇子串進行歸約？在每一步中如何選擇子串進行歸約？編譯原理編譯原理編譯原理編譯原理編譯原理編譯原理自下而上語法分析的策略：移進自下而上語法分析的策略：移進- -規約分析。規約分析。移進移進就是將一個終結符推進棧。就是將一個終結符推進棧。歸約歸約就是將就是將0 0個或多個符號從棧中彈出，根個或多個符號從棧中彈出，根據產生式將一個非終結符壓入棧。據產生式將一個非終結符壓入棧。移進移進- -歸約過

4、程是自頂向下最右推導的逆過歸約過程是自頂向下最右推導的逆過程（規范歸約）。程（規范歸約）。編譯原理編譯原理編譯原理編譯原理編譯原理編譯原理 簡單優先分析法 對一個文法按一定原則求出該文法所有符號（終結符和非終結符）之間的優先關系，按照這種關系確定歸約過程中的句柄，它的歸約實際上是一種規范歸約。 算符優先分析法 只規定算符（終結符）之間的優先關系。找到句柄就歸約，不是規范歸約。優先分析法優先分析法編譯原理編譯原理編譯原理編譯原理編譯原理編譯原理簡單優先分析法簡單優先分析法按照文法符號（包括終結符和非終結符） 的優先關系確定句柄。編譯原理編譯原理編譯原理編譯原理編譯原理編譯原理文法文法gsgs：(

5、1) s bab(1) s bab(2) a (b|a(2) a (b|a(3) b aa)(3) b aa)sba(ba)#sb=a=(=a=)#步驟步驟符號棧符號棧輸入符號串輸入符號串動作動作 1） # b(aa)b# #b,移進移進 2） #b (aa)b# b(,移進移進 3） #b( aa)b# (a,歸約歸約aa 5） #b(a a)b# a=a,移進移進 6） #b(aa )b# a=),移進移進 7） #b(aa) b# )b,歸約歸約baa) 8） #b(b b# bb,歸約歸約a(b 9） #ba b# a=b,移進移進10） #bab # b#,歸約歸約sbab11） #

6、s # 接受接受對輸入串b(aa)#的簡單優先分析過程簡單優先關系矩陣編譯原理編譯原理編譯原理編譯原理編譯原理編譯原理優先關系優先關系優先關系優先關系1) x=y 文法文法g中存在產生式中存在產生式a.xy.2) xy 文法文法g中存在產生式中存在產生式a.bd.，且且b .x,d y.如何確定兩個文法符號之間的優先關系？如何確定兩個文法符號之間的優先關系？*返回調用編譯原理編譯原理編譯原理編譯原理編譯原理編譯原理簡單優先文法的定義簡單優先文法的定義 滿足以下條件的文法是簡單優先文法（1）在文法符號集v中，任意兩個符號之間最多只有一種優先關系成立。（2）在文法中任意兩個產生式沒有相同的右部。（

7、3）不含空產生式。編譯原理編譯原理編譯原理編譯原理編譯原理編譯原理簡單優先分析法簡單優先分析法根據已知優先文法構造相應優先關系矩陣，并將文法的產生式保存，設置符號棧s，算法步驟如下：1. 將輸入符號串a1a2a3.an#依次逐個存入符號棧s中，直到遇到棧頂符號ai的優先性下一個待輸入符號aj時為止。2. 棧頂當前符號ai為句柄尾，由此向左在棧中找句柄的頭符號ak，即找到ak-1ak為止。3. 由句柄ak.ai在文法的產生式中查找右部為ak.ai的產生式，若找到則用相應左部代替句柄，若找不到則為出錯，這時可斷定輸入串不是該文法的句子。4. 重復上述三步，直到歸約完輸入符號串，棧中只剩文法的開始符

8、號為止。編譯原理編譯原理編譯原理編譯原理編譯原理編譯原理如何確定優先關系？如何確定優先關系？文法文法gs：(1) s bab(2) a (b|a(3) b aa)1.求求=關系：關系：由由(1)：b=a a=b由由(2)：(=b由由(3)：a=a a=)2.求求關系：關系：由由(1)(2)：b( ba由由(2)(3)：(a ( (關系：關系：由由(1)：bb ab )b由由(3)：ba aa )a4.#查看關系定義sba(ba)#sb=a=(=a=)#編譯原理編譯原理編譯原理編譯原理編譯原理編譯原理算符優先分析法算符優先分析法某些文法具有“算符”特性表達式運算符（優先級、結合性）人為地規定其算

9、符的優先順序，即給出優先級別和同一級別的結合性只考慮算符之間的優先關系來確定句柄編譯原理編譯原理編譯原理編譯原理編譯原理編譯原理文法文法ge：ee+e|e-e|e*e|e/e|e e|(e)|i步驟步驟符號棧符號棧輸入符號串輸入符號串動作動作 1） # i+i*i# #i,移進移進 2） #i +i*i# #+,規約規約 3） #e +i*i# #+,移進移進 4） #e+ i*i# +i,移進移進 5） #e+i *i# +*,規約規約 6） #e+e *i# +*,移進移進 7） #e+e* i# *i,移進移進 8） #e+e*i # *#,規約規約 9） #e+e*e # +#,規約規

10、約10） #e+e # #,規約規約11） #e # 接受接受對輸入串對輸入串i+ii+i* *i i的算符優先分析過程的算符優先分析過程+ - * / ()i #+ -* / (= i# -*/ (=i# =算符優先關系表算符優先關系表編譯原理編譯原理編譯原理編譯原理編譯原理編譯原理算符文法的定義算符文法的定義定義定義 如果不含空產生式的上下文無關文法如果不含空產生式的上下文無關文法 g g 中沒有形如中沒有形如 u uvwvw的產生式，其中的產生式，其中v,wvv,wvn n則稱則稱g g 為算符文法（為算符文法（ogog）。）。性質性質1 1：在算符文法中任何句型都不包含兩個在算符文法中

11、任何句型都不包含兩個相鄰的非終結符相鄰的非終結符.(.(數學歸納法數學歸納法) )性質性質2 2：如如 vx vx 或或 xv xv 出現在算符文法的句型出現在算符文法的句型 中，其中中，其中vvvvn n,xv,xvt t, , 則則 中任何含中任何含 x x 的短語必含有的短語必含有v.v.（反證法）（反證法）編譯原理編譯原理編譯原理編譯原理編譯原理編譯原理算符優先關系的定義算符優先關系的定義在在ogog中中 定義定義 （算符優先關系）（算符優先關系）1)1) x x = = y g y g中有形如中有形如.u.uxyxy或或u u xvy.xvy.的產的產生式。生式。2)2) x x y

12、 gy g中有形如中有形如.u .u wywy的產生式的產生式, ,而而 w w x x或或w w xv xv規定規定 若若 s xs x或或s vxs vx 則則 # x# #x #編譯原理編譯原理編譯原理編譯原理編譯原理編譯原理算符優先文法的定義算符優先文法的定義在 og文法 g 中，若任意兩個終結符間至多有一種算符優先關系存在，則稱g 為算符優先文法(opg)。 注意注意：允許bc,cb;不允許bc,bc,b=c 結論： 算符優先文法是無二義的。編譯原理編譯原理編譯原理編譯原理編譯原理編譯原理算符優先關系表的構造算符優先關系表的構造由定義直接構造由定義直接構造由關系圖法構造算符優先關系表

13、由關系圖法構造算符優先關系表編譯原理編譯原理編譯原理編譯原理編譯原理編譯原理首先引入兩個概念首先引入兩個概念firstvt(b)=b|b bfirstvt(b)=b|b b或或b cb.b cb.對于非終結符對于非終結符b b，其往下推導所可能出現的，其往下推導所可能出現的首個算符。首個算符。lastvt(b)=a|b lastvt(b)=a|b a a或或b . acb . ac對于非終結符對于非終結符b b，其往下推導所可能出現的，其往下推導所可能出現的最后一個算符。最后一個算符。編譯原理編譯原理編譯原理編譯原理編譯原理編譯原理如何計算算符優先關系如何計算算符優先關系1) =關系關系直接看

14、產生式的右部，若出現了直接看產生式的右部，若出現了a ab或或a abb,則則a=b。2)關系關系求出每個非終結符求出每個非終結符b的的firstvt(b)， 若若aab,則則 bfirstvt(b),則則a關系關系求出每個非終結符求出每個非終結符b的的lastvt(b)， 若若abb,則則 alastvt(b),則則ab。編譯原理編譯原理編譯原理編譯原理編譯原理編譯原理文法文法ge：(0) e#e#(1) ee+t(2) et(3) tt*f(4) tf(5) fp f|p(6) p(e)(7) pifirstvt(e)=#firstvt(e)=+,*, ,(,ifirstvt(t)=*,

15、,(,ifirstvt(f)= ,(,ifirstvt(p)=(,ilastvt(e)=#lastvt(e)=+,*, ,),ilastvt(t)=*, ,),ilastvt(f)= ,),ilastvt(p)=),i+-*/ ()i#+-*/ (=i#=1)=關系關系由產生式由產生式(0)和和(6),得得#=#，（，（=）2）關系關系找形如：找形如：aab的產生式的產生式#e：則：則#firstvt(e)+t: 則則+firstvt(t) *f: 則則*firstvt(f) f:則則 firstvt(f)(e: 則則 (關系關系找形如：找形如：abb的產生式的產生式e# ,則則 lastvt

16、(e)#e+ ,則則 lastvt(e)+ t* ,則則 lastvt(t)* p ,則則 lastvt(p) e) ,則則 lastvt(e)編譯原理編譯原理編譯原理編譯原理編譯原理編譯原理算符優先分析算法算符優先分析算法歸約過程中，只考慮終結符之間的優先關系來確定句柄，而與非終結符無關。這樣去掉了單非終結符的歸約，所以用算符優先分析法的規約過程與規范歸約是不同的，p110.為解決在算符優先分析過程中如何尋找句柄，引進最左素短語最左素短語的概念。編譯原理編譯原理編譯原理編譯原理編譯原理編譯原理最左素短語最左素短語算符文法的任一句型有如下形式：#n1a1n2a2.nnannn+1#,若niai

17、.njajnj+1為句柄，則有 ai-1 ai+1對于算符優先文法，如果anb(或ab)出現在句型r中若ab，則在r中必含有a而不含b的短語存在。若a=b，則在r中含有a的短語必含有b，反之亦然。定義 cfg g 的句型的素短語是一個短語，它至少包含一個終結符，且除自身外不再包含其他素短語。處于句型最左邊的素短語為最左素短語。編譯原理編譯原理編譯原理編譯原理編譯原理編譯原理文法文法gege：(1) ee+t(1) ee+t(2) et(2) et(3) tt(3) tt* *f f(4) tf(4) tf(5) fp(5) fp f|pf|p(6) p(6) p(e)(e)(7) pi(7) pi句型句型#t+t*f+i#其短語有：其短語有：t+t*f+it+t*ftt*fieet