1、1,自上而下 從文法的開始符號出發(fā)，反復(fù)使用文法的產(chǎn)生式，尋找與輸入符號串匹配的推導(dǎo)（最左推導(dǎo)），若能推導(dǎo)出與輸入字串相同的句子,則表示輸入字符串是合法的； 特點(diǎn) 從文法開始符開始； 推導(dǎo)中始終使用產(chǎn)生式的右部替換左邊的非終結(jié)符； 自下而上 根據(jù)文法,對輸入符號串進(jìn)行歸約,若能正確地歸約為文法的初始符號,則表示輸入字串是合法的。 歸約：在輸入串中，尋找一條產(chǎn)生式的右部，如果找到用產(chǎn)生式的左邊的非終結(jié)符替換右部。 特點(diǎn) 從輸入串開始； 歸約中始終使用產(chǎn)生式的左部替換右邊的候選式；,2,5.1 自下而上分析的基本問題- 重點(diǎn) 自下而上分析的基本思想、歸約、規(guī)范歸約、短語、直接短語、句柄等概念， 規(guī)

2、范歸約自下而上分析法 5.2 算符優(yōu)先分析- 重點(diǎn)難點(diǎn) 算符優(yōu)先文法、算符優(yōu)先分析算法、優(yōu)先表的構(gòu)造、最左素短語、優(yōu)先函數(shù) * 5.3 LR分析法 5.4 語法分析器的自動產(chǎn)生工具 YACC-了解,自下而上語法分析：教學(xué)內(nèi)容,3,5.1 自下而上分析的基本問題,自下而上分析法的基本思想： 從輸入串出發(fā)，反復(fù)利用產(chǎn)生式逐步進(jìn)行“歸約”，如果最后能歸約到文法的開始符號，則輸入串是句子，否則輸入串有語法錯(cuò)誤。 各種不同自下而上分析法一個(gè)共同特點(diǎn)是： 邊輸入單詞符號（移進(jìn)棧），邊歸約；,4,5.1 自下而上分析的基本問題,自下而上分析的基本技術(shù)是采用歸約棧,如下圖所示: 把輸入符號依次移入棧內(nèi),當(dāng)棧頂

3、符號串形成某產(chǎn)生式的右部時(shí)，就歸約為產(chǎn)生式左部非終結(jié)符; 繼續(xù)移入輸入字串，直到棧中歸約為文法初始符號S. 這種方法也稱為“移進(jìn)歸約法”.,5,5.1 自下而上分析的基本問題,定義：棧頂形成的某產(chǎn)生式的候選稱為歸約串。 自底向上分析方法，也稱移進(jìn)歸約分析法，粗略地說它的實(shí)現(xiàn)思想是對輸入符號串自左向右進(jìn)行掃描，并將輸入符逐個(gè)移入一個(gè)后進(jìn)先出棧中，邊移入邊分析，一旦棧頂符號串形成某個(gè)歸約串時(shí)，（某產(chǎn)生式的右部），就用該產(chǎn)生式的左部非終結(jié)符代替相應(yīng)右部的文法符號串，這稱為歸約。重復(fù)這一過程直到歸約到棧頂中只剩文法的開始符號時(shí)則為分析成功，也就確認(rèn)輸入串是文法的句子。,6,例5.1 GS: SaAcB

4、e Ab|Ab Bd 分析句子 abbcde 是否為合法的句子 分析棧 動作 源串 分析棧 動作 源串,經(jīng)分析,判定該句子是G合法的句子.,7,5.1.1 歸約,歸約串分為：可歸約串、非可歸約串 在上例中,當(dāng)棧中為aAb時(shí),存在兩個(gè)歸約串:b及Ab,都可以歸約為A； 若使用b進(jìn)行歸約，棧中得到aAA,導(dǎo)致最終不能歸約為S,因此，判定輸入字符串非法； 這是一種錯(cuò)誤歸約, 原因在于棧中同時(shí)存在多個(gè)歸約串,而只有一個(gè)歸約串的選擇是正確的,如Ab； 把Ab稱為可歸約串，而b為非可歸約串,8,5.1.1 歸約,自下而上分析的核心問題：就是尋找句型中的“可歸約串”進(jìn)行歸約。 對“可歸約串”概念的不同定義，

5、就形成了不同的自下而上的分析方法。 在“規(guī)范歸約”中，則用“句柄”來刻畫“可歸約串” 在“算符優(yōu)先分析法”用“最左素短語”來刻畫”可歸約串”,9,5.1.1 歸約,語法分析樹: 一棵倒立的樹,可用于描述語法分析的過程； 自上而下分析采用的方法是推導(dǎo)，從根到葉子構(gòu)造分析樹。 或者說從文法的開始符號產(chǎn)生句子。 自下而上分析采用的方法是歸約，從葉子到根構(gòu)造分析樹。 或者說從句子開始?xì)w約出文法的開始符號。 語法樹的一個(gè)子樹：由該樹的某個(gè)結(jié)連同它的所有子孫組成。 在自下而上分析過程中，每一步歸約都可畫出一棵子樹。 例如,上例中的歸約過程可描述為如下分析樹:,例5.2：文法GS, 其4條產(chǎn)生式如下： Sa

6、ABe Ab AAbc Bd 對句子abbcde的分析 最右推導(dǎo) 最左歸約,A,aAbcde,A,aAde,B,S,aABe,S,SaABeaAdeaAbcdeabbcde,abbcde,，aAbcde,，aAde,，aABe,，S,11,一個(gè)簡單的歸約過程,a b b c d e,例5.3 設(shè)文法為： S aAcBe A b A Ab B d (5.1) 句子abbcde的分析：abbcde, S , aAcBe , aAcde , aAbcde ,12,5.1.1 歸約,歸約與推導(dǎo)關(guān)系： 推導(dǎo)與歸約互逆關(guān)系 最右推導(dǎo)稱為 最右推導(dǎo)得到的句型稱為規(guī)范句型 最左歸約稱為,規(guī)范推導(dǎo),規(guī)范歸約,1

7、3,5.1.2 規(guī)范歸約簡述,令G是一個(gè)文法，S是文法的開始符號 短語 假定是文法G的一個(gè)句型，如果有： S*A 且 A + 則稱是句型 相對于非終結(jié)符A的短語。 直接短語 如果有 S*A 且 A 則稱是句型 相對于規(guī)則 A 的直接短語。 句柄：一個(gè)句型的最左直接短語。 注意：短語的兩個(gè)條件缺一不可, A是句型，符號串可由A出發(fā)推導(dǎo)出來。,14,例5.4 求P85.(5.2)文法的另一個(gè)句型 E+T*F+i 的短語。 解：EE+TE+T+TE+T*F+TE+T*F+FE+T*F+i EE+T*F+i EE+T*F TT*F T+i Fi 短語有4個(gè)：E+T*F+i (相對于E)； E+T*F(

8、相對于E)； T*F(相對于T)；i (相對于T、F) 。 T*F 和 i 為直接短語 T*F為句柄。,15,5.1.2 規(guī)范歸約簡述,語法樹的一個(gè)子樹的所有葉結(jié)點(diǎn)的自左至右排列形成一個(gè)相對于子樹根的短語。P86 有多少棵子樹就有多少個(gè)相對于子樹根結(jié)(非終結(jié)符)的短語, 短語由某子樹的全部葉結(jié)點(diǎn)組成。 若短語是由某子樹根經(jīng)過1步推導(dǎo)得到的，則稱之為該子樹根的直接短語。,16,例5.4 求P85.(5.2)文法的另一個(gè)句型 E+T*F+i 的短語。 解：EE+TE+T+TE+T*F+TE+T*F+F E+T*F+i 短語有4個(gè)：E+T*F+i (相對于E)； E+T*F(相對于E)； T*F(相

9、對于T)； i (相對于T、F) 。 T*F 和 i 為直接短語 (相對于規(guī)則 T T*F 和 F i ) 。 T*F為句柄。,17,練習(xí),文法G(S): S (L)|aS|a L L , S |S (1) 畫出句型 (S,(a) 的語法樹。 (2) 寫出上述句型的所有短語、直接短語和句柄。,18,5.1.2 規(guī)范歸約簡述,一個(gè)句型只有一個(gè)句柄，不同句型一般有不同句柄，每次歸約都對句柄進(jìn)行歸約 - 這就是規(guī)范歸約。 規(guī)范歸約 假定是文法G的一個(gè)句子, 稱序列 n , n-1 , n-2, , 0 是的一個(gè)規(guī)范歸約，如果此序列滿足： (1) n = ; (2) 0 為文法的開始符,即 0 =S;

10、 (3) 對于任何的i，0i n, i-1 是從 i 經(jīng)把句柄替換為相應(yīng)產(chǎn)生式的左部符號而得到的。,例5.5文法GS, SaABe Ab AAbc Bd求句子abbcde的規(guī)范歸約。,abbcde,aAbcde,aAde,aABe,S,abbcde的規(guī)范歸約為： abbcde，aAbcde，aAde，aAB，S,20,5.1.2 規(guī)范歸約簡述,規(guī)范歸約是一種較常用的自下而上分析方法。 規(guī)范歸約：是關(guān)于句子的一個(gè)最右推導(dǎo)的逆過程。 也稱最左歸約。 規(guī)范歸約采用句柄來刻畫可歸約串。 每次歸約總是句型的句柄歸約。,21,5.1.2 規(guī)范歸約簡述,為加深對句柄和歸約等概念的理解，用修剪語法樹方法進(jìn)一步

11、闡明規(guī)范歸約這一自下而上分析過程。 一個(gè)句型的句柄是該句型對應(yīng)的語法樹中最左直接短語 。 可采用修剪語法樹方法實(shí)現(xiàn)歸約，即尋找當(dāng)前語法樹的句柄，將句柄中的樹葉剪去(歸約)，不斷修剪直到只剩根結(jié)點(diǎn)，完成整個(gè)規(guī)范歸約過程.,22,例5.6 文法GS, SaABe Ab AAbc Bd求對句子abbcde的規(guī)范歸約。,a,b,b,c,d,e,abbcde 4,A,aAbcde3,A,aAde 2,B,aABe 1,S 0,歸約-剪子樹,S,規(guī)范歸約為： abbcde，aAbcde，aAde，aABe，S,句型abbcde的句柄是b ，把句柄剪去（歸約）就形成了句型aAbcde的語法樹。,23,練習(xí)：

12、文法G(S): S (L) | aS | a L L , S | S （1）指出句子 (a,(a) 的規(guī)范歸約; （2）指出每次歸約用的句柄。,解：（1）規(guī)范歸約： (a,(a),(S,(a),(L,(a),(L,(S),(L,(L),(L,S),(L),S,（2）每次歸約用的句柄：,24,自下而上分析器結(jié)構(gòu),i + i i #, #,移進(jìn)歸約 控制程序,輸出,核心是分析表，如P90.表5.1；P101.圖5.5 與LL(1)分析器的體系結(jié)構(gòu)比較 - 類似,分析棧,輸入緩沖區(qū),分析表,25,移進(jìn)歸約：系統(tǒng)框架,輸入緩沖區(qū)：保存輸入符號串，設(shè)符號串以#為結(jié)束符,有一個(gè)指針,指向當(dāng)前輸入符號。 分

13、析棧(符號棧)：保存文法符號,記載分析的歷史 已經(jīng)得到的部分結(jié)果；指示分析的下一步動作 -展望未來。 控制程序：控制分析的過程，輸出分析結(jié)果。分析中，棧頂未形成可歸約串時(shí)則移進(jìn)當(dāng)前輸入符號到棧；當(dāng)棧頂形成可歸約串(是某個(gè)非終結(jié)符的某個(gè)候選式)時(shí)則歸約: 棧頂?shù)目蓺w約串出棧, 該非終結(jié)符進(jìn)棧。,26,5.1.3 符號棧的使用與語法樹的表示,符號棧的使用 自下而上分析法要使用一個(gè)符號棧(語法分析的一種基本數(shù)據(jù)結(jié)構(gòu)),分析中根據(jù)符號棧頂是否形成句柄決定是移進(jìn)還是歸約。 符號棧 輸入串 分析開始： # # 分析中： # # 分析結(jié)束時(shí)： # S # 則成功，達(dá)不到這種格局則輸入串有錯(cuò)誤。 分析中任何時(shí)

14、候： 棧中符號串+剩余輸入串 = 規(guī)范句型。,移進(jìn)歸約例(5.1):分析輸入串a(chǎn)bbcde,28,規(guī)范歸約分析算法,1. 在棧底放入# ，在輸入串尾附上#; 2. 逐個(gè)移入輸入符號,當(dāng)棧頂形成句柄時(shí)，進(jìn)行歸約; 3. 重復(fù)(2) 直到輸入串已全部進(jìn)棧，僅剩#, 4. 若棧中歸約為#S, 表示分析成功，輸入串為合法的句子,否則為非法句子.,29,5.1.3 符號棧的使用與語法樹的表示,語法分析對符號棧的使用有四類操作：P88 1) 移進(jìn)：將當(dāng)前輸入符號移入棧。 2)歸約：用產(chǎn)生式左側(cè)的非終結(jié)符替換棧頂?shù)目蓺w約串。 3) 接受：分析成功,分析結(jié)束,接受輸入串。 4) 出錯(cuò)：出錯(cuò)處理。,注意: 可歸

15、約的串在棧頂，不會在內(nèi)部,例5.7 i1*i2+i3 的規(guī)范歸約步驟(P88.),0 # i1 * i2 + i3# 預(yù)備 i1 * i2 + i3 1 #i1 * i2 + i3 # 讀入 i1 , i1進(jìn)棧 2 #F * i2 + i3 # 歸約，F(xiàn)i F * i2 + i3 3 #T * i2 + i3 # 歸約，T F T * i2 + i3 4 #T* i2 + i3 # 讀入* , *進(jìn)棧 5 #T* i2 + i3 # 讀入 i2 , i2進(jìn)棧 6 #T*F + i3# 歸約，F(xiàn) i T * F + i3 7 #T + i3 # 歸約，T T*F T + i3 8 #E + i3

16、 # 歸約，E T E + i3 9 # E+ i3 # 讀入+ , +進(jìn)棧 10 #E+ i3 # 讀入 i3 , i3進(jìn)棧 11 #E+F # 歸約, F i E + F 12 #E+T # 歸約, T F E + T 13 #E # 歸約，E E+T E 開始符號 14 #E # 接受,步驟 符號棧 輸入串 動作 句型和句柄,31,作業(yè)： P133 1 2,32,回顧：,自下而上語法分析方法 - “移進(jìn)-歸約”法 符號棧頂 沒有形成 可歸約串, 決定是 移進(jìn) 形成 歸約 定義可歸約串要解決： 1. 定義什么樣的符號串是可歸約串； 2. 在分析時(shí)怎樣判定符號棧頂出現(xiàn)了可歸約串； 3. 如何

17、歸約。,33,5.2 算符優(yōu)先分析,算符優(yōu)先分析的基本思路: (1) 解決誰先歸約: 規(guī)定算符(終結(jié)符)的優(yōu)先關(guān)系和結(jié)合性質(zhì),(2) 確定可歸約串: 采用比較相鄰運(yùn)算符(終結(jié)符)的優(yōu)先順序來確定可歸約串 - 最左素短語 (3) 進(jìn)行歸約,算符優(yōu)先文法及優(yōu)先表的構(gòu)造 (5.2.1),優(yōu)先函數(shù)及構(gòu)造 (5.2.3),34,例5.8 表達(dá)式文法GE ： EEE|E-E|E*E|E/E|EE|(E)|i 對這個(gè)二義文法可能會有好幾個(gè)規(guī)范推導(dǎo)和歸約，真正運(yùn)算時(shí)也有幾種不同結(jié)果。 如果規(guī)定算符(終結(jié)符)的優(yōu)先級從高到低為：乘冪運(yùn)算符，乘、除運(yùn)算符，加、減運(yùn)算符；同級運(yùn)算符服從左結(jié)合原則；有括號時(shí)，先括號內(nèi)

18、后括號外，那么，句子的歸約過程就是唯一的。 注：對所有的終結(jié)符定義某種優(yōu)先關(guān)系，借助這種關(guān)系找出可歸約的串，進(jìn)行歸約，達(dá)到自下而上分析的目的。,35,如： i+i-i*(i+i)歸約過程如下： 1) i+i-i*(i+i) 設(shè)算數(shù)級別最高，最先歸約； E+i-i*(i+i) E+E-i*(i+i) ，同級，先歸約左邊“” E-i*(i+i) E-E*(i+i) ，不同級，先歸約右邊“” E-E*(i+i) ，（不同級，先歸約右邊“（” E-E*(i+i) E-E*(E+E) 先算括號內(nèi)，再算括號外 E-E*(E) E-E*E 先歸約“”，再歸約“” E-E E,棧頂?shù)慕K結(jié)符跟要進(jìn)棧的終結(jié)符對比

19、優(yōu)先級,上述歸約過程是唯一的。 上述歸約過程中起決定作用的是相鄰兩個(gè)終結(jié)符之間的優(yōu)先關(guān)系。一旦確定了這種優(yōu)先關(guān)系，就可以借助這種關(guān)系去尋找可歸約串并進(jìn)行歸約。,36,什么是算符優(yōu)先分析法？ 所謂算符優(yōu)先分析法是仿效四則運(yùn)算的計(jì)算過程而構(gòu)造的一種語法分析方法。 算符優(yōu)先分析法的特點(diǎn)： 簡單直觀，特別方便于表達(dá)式分析，易于手工實(shí)現(xiàn)，是自下而上的歸約過程，但未必按照句柄歸約。 算符優(yōu)先分析法的關(guān)鍵： 規(guī)定算符（終結(jié)符）的優(yōu)先級而決定應(yīng)采用的動作。,5.2 算符優(yōu)先分析,37,5.2 算符優(yōu)先分析,要完成運(yùn)算符間優(yōu)先級的比較，可以先定義各種可能相繼出現(xiàn)的運(yùn)算符的優(yōu)先級，并表示為矩陣的形式（優(yōu)先表），使

20、得能夠在分析中通過查詢矩陣元素而得到算符之間的優(yōu)先關(guān)系。 終結(jié)符號a與b之間的優(yōu)先關(guān)系有三種： a b 表示a的優(yōu)先級低于b a b 表示a的優(yōu)先級等于b a b 表示a的優(yōu)先級高于b,這三個(gè)關(guān)系不同于數(shù)學(xué)中的 ,38,5.2.1 算符優(yōu)先文法及優(yōu)先表的構(gòu)造,算符文法 一個(gè)文法，如果它的任何產(chǎn)生式的右部都不含兩個(gè)相繼(并列)的非終結(jié)符，即不含如下形式的產(chǎn)生式右部： QR 則稱該文法為算符文法。 在后面的定義中，a、b代表任意終結(jié)符；P、Q、R代表任意非終結(jié)符；代表由終結(jié)符和非終結(jié)符組成的任意序列，包括空字。,39,例5.9：文法 GE: EEE|E-E|E*E|E/E|EE|(E)|-E|i

21、是算符文法， 例5.10: 文法 EEAE|(E)|-E|i A|*| / | 不是算符文法,因?yàn)樗娜魏萎a(chǎn)生式的右部都不含兩個(gè)相繼(并列)的非終結(jié)符,因?yàn)楫a(chǎn)生式EEAE的右部EAE具有相繼并列的非終結(jié)符號。,40,算符優(yōu)先關(guān)系的定義,假定G是一個(gè)不含產(chǎn)生式(P)的算符文法。對于任何一對終結(jié)符(a,b)，有序?qū)? a在前b在后, 定義： (1) a b 當(dāng)且僅當(dāng)文法G中含有形如 P ab或P aQb的產(chǎn)生式;,a,b在產(chǎn)生式中相鄰, 將同時(shí)被歸約,a,b在句型中相鄰, 而b將先于a被歸約,(2) ab當(dāng)且僅當(dāng)G中含有形如 P aR 的產(chǎn)生式, 而 R+ b 或 R + Qb;,(3) ab當(dāng)且

22、僅當(dāng)G中含有形如 P Rb 的產(chǎn)生式， 而 R+ a 或 R + aQ;,a,b在句型中相鄰, 而a將先于b被歸約,41,算符優(yōu)先關(guān)系的定義,說明: 終結(jié)符號對(a, b)的優(yōu)先關(guān)系是有序的, a、b在句型中相鄰，a在前而b在后。 優(yōu)先關(guān)系和代數(shù)中的大于小于關(guān)系不同，aa，終結(jié)符所處的左右位置很重要。 例如：有+ +。,42,算符優(yōu)先文法,算符優(yōu)先文法(OPG) 如果一個(gè)算符文法G中的任何終結(jié)符序偶(a, b)至多只滿足下述三種關(guān)系之一： a=b, ab 則稱G是一個(gè)算符優(yōu)先文法。 例5.4 P90.文法(5.3)是算符優(yōu)先文法, 因?yàn)?它是算符文法; 它的任何終結(jié)符號對至多只有一種優(yōu)先關(guān)系，

23、見P90.表5.1的優(yōu)先表。,43,算符優(yōu)先表,44,例5.11 試說明下述文法G是算符文法，但不是算符優(yōu)先文法。 EE+EE*E(E)i 解: 由于文法G的任一產(chǎn)生式右部都不含兩個(gè)相鄰的非終結(jié)符，故文法G是算符文法。 (1)由于存在EE+E，而E+E中第二個(gè)E可推出E*E， 故有+* 可見, 運(yùn)算符+和*之間同時(shí)存在兩種不同的優(yōu)先關(guān)系，故文法G不是算符優(yōu)先文法。,45,P 133 2 （a，（a，a）,46,算符優(yōu)先表 注：,1）在此表中，包括，*包括/，“”是一個(gè)特殊符號，用于語句的開始符號和結(jié)束符號。 2）這張表滿足通常數(shù)學(xué)上的習(xí)慣約定。值得注意的是： a、運(yùn)算量i的優(yōu)先級高于算符； b

24、、語句開始和結(jié)束符號“”與終結(jié)符a相繼出現(xiàn)時(shí)，應(yīng)該有#,以此來保證語句內(nèi)先歸約。 3）(= )表示括號是成對歸約的。 4）優(yōu)先關(guān)系和代數(shù)中的大于小于關(guān)系不同，aa，終結(jié)符所處的左右位置很重要。,47,優(yōu)先關(guān)系表的構(gòu)造,設(shè)文法G是算符優(yōu)先文法, 下面討論算符優(yōu)先表的構(gòu)造方法, 即確定文法的任意終結(jié)符號對(a, b)的優(yōu)先關(guān)系。 找出滿足關(guān)系 a=b 的符號對，只要檢查文法的每條產(chǎn)生式即可確定。 如 P90.文法(5.3), 因?yàn)橛蠩(E), 故有( = ) 。 為了找出滿足關(guān)系 ab 的符號對, 需要先定義非終結(jié)符P的FIRSTVT(P)(首終結(jié)符集)和LASTVT(P)(尾終結(jié)符集)集合。,4

25、8,FIRSTVT(P)集合與LASTVT(P)集合,非終結(jié)符P 的FIRSTVT(P)集合定義： FIRSTVT(P) =a|P+a或P +Qa, aVT而 QVN 由非終結(jié)符P能夠推出來的第一個(gè)終結(jié)符的集合。 非終結(jié)符P 的LASTVT(P)集合定義: LASTVT(P) =a|P+a或P +aQ, aVT而 Q VN 由非終結(jié)符P能夠推出來的最后一個(gè)終結(jié)符的集合。,49,構(gòu)造集合FIRSTVT(P)的算法P91,按定義, 可用下面兩條規(guī)則來構(gòu)造集合FIRSTVT(P): (1) 若有產(chǎn)生式 Pa或 P Qa, 則aFIRSTVT(P) (2) 若aFIRSTVT(Q)，且有產(chǎn)生式 P Q

26、, 則aFIRSTVT(P) 注：規(guī)則1 是求P FIRSTONE a的關(guān)系； 規(guī)則2 是求P FIRST* Q的關(guān)系。 P91.有一個(gè)形式化的構(gòu)造算法。不講。,50,同樣可用下面兩條規(guī)則來構(gòu)造集合LASTVT(P)的算法： (1) 若有產(chǎn)生式 P a或 P aQ， 則aLASTVT(P) (2) 若aLASTVT(Q),且有產(chǎn)生式P Q, 則aLASTVT(P),構(gòu)造集合LASTVT(P)的算法,51,例5.12 試構(gòu)造文法GE的FIRSTVT集。 GE: EE+TT TT*FF F(E)i 解: 根據(jù)規(guī)則(1)知： 由EE+得, FIRSTVT(E)=+； 由TT*得, FIRSTVT(T

27、)=*； 由F(和Fi得,FIRSTVT(F)=(,i 根據(jù)規(guī)則(2)知： 由TF和FIRSTVT(F)=(,i得, FIRSTVT(T)=*, (, i； 由ET和FIRSTVT(T)得, FIRSTVT(E)=+, *, (, i,52,例5.13 試構(gòu)造文法GE的LASTVT集。 GE: EE+TT TT*FF F(E)i 解: 根據(jù)規(guī)則(1)知： 由E+T得, LASTVT(E)=+ 由T*F得, LASTVT(T)=* 由F)和Fi得,LASTVT(F)=),i 根據(jù)規(guī)則(2)知： 由TF和LASTVT(F)得, LASTVT(T)=*, ), i; 由ET和LASTVT(T)得,

28、LASTVT(E)=+, *, ), i。,53,練習(xí) 求下列文法GS中每個(gè)非終結(jié)符的FIRSTVT和LASTVT集合： SSaF|F F FbP|P P c|d 解：每個(gè)非終結(jié)符的FIRSTVT集合： FIRSTVT(S) = a, b, c, d FIRSTVT(F) = b, c, d FIRSTVT(P) = c , d 每個(gè)非終結(jié)符的LASTVT集合： LASTVT(S)= a, b, c, d LASTVT(F) = b, c, d LASTVT(P) = c, d ,54,由FIRSTVT(P)和LASTVT(P)集合確定優(yōu)先關(guān)系 P91,有了FIRSTVE和LASTVT這兩個(gè)集

29、合后，就可以通過檢查每個(gè)產(chǎn)生式的候選式確定滿足關(guān)系的所有終結(jié)符對。 例如：假定有個(gè)產(chǎn)生式的一個(gè)候選式 為 aP 那么，對任何 bFIRSTVT(P)，有ab。,55,構(gòu)造優(yōu)先關(guān)系表的方法,對形如ab或aQb的產(chǎn)生式候選式,有a= b； 對形如aP的產(chǎn)生式候選式, 若 bFIRSTVT(P),則ab； 對文法開始符號S,有# #， 且對#S#，有# = #。,為了考慮語句的開始符號與結(jié)束符號“#”，對文法拓廣加一個(gè)產(chǎn)生式S#S#，,56,例5.14 構(gòu)造文法GE的算符優(yōu)先關(guān)系表。 GE:EE+TT TT*FF F(E)i 解:對每個(gè)非終結(jié)符,求出: FIRSTVT(F)= ( , i LASTV

30、T(F)= ) , i FIRSTVT(T)= * , ( , i LASTVT(T)= * , ) , i FIRSTVT(E)= + , * , ( , i LASTVT(E)= + , * , ) , i ,構(gòu)造優(yōu)先關(guān)系表 根據(jù)規(guī)則(1), 由“(E)”知, (=)。 根據(jù)規(guī)則(2), 由E+T知, + FIRSTVT(T),即 +*, +(, +i 由T*F知, * FIRSTVT(F),即*(, *i 由F(E知, ( FIRSTVT(E),即(+, (*, (,(i,57,根據(jù)規(guī)則(3)知： 由EE+知,LASTVT(E)+,即+,*+,)+，i+ 由TT*知, LASTVT(T)

31、*，即*，)*，i* 由FE)知,LASTVT(E),即+)，*)，)，i) 由#E#知, #=#；#, 即+#,*#,)#,i#,故算術(shù)表達(dá)式文法的優(yōu)先關(guān)系表如下:,58,構(gòu)造優(yōu)先表：練習(xí)(1),文法GS為算符優(yōu)先文法, 求優(yōu)先關(guān)系矩陣。 SSaF|F F FbP|P P c|d,解：每個(gè)非終結(jié)符的FIRSTVT集合 FIRSTVT(S) = a, b, c, d FIRSTVT(F) = b, c, d FIRSTVT(P) = c , d 每個(gè)非終結(jié)符的LASTVT集合 LASTVT(S)= a, b, c, d LASTVT(F) = b, c, d LASTVT(P) = c, d

32、,59,因?yàn)镾SaF 則 LASTVT(S) a 且aa, ba, ca, da; ab 且bb, c b, d b; b#, 即a#,b#,c#,d# 優(yōu)先關(guān)系表：,60,P133 3（1） （2）,61,規(guī)范歸約 嚴(yán)格按照句柄進(jìn)行歸約，終結(jié)符和非終結(jié)符一起考慮，只要棧頂形成句柄，不管句柄內(nèi)是否包含終結(jié)符都要進(jìn)行歸約。 算符優(yōu)先分析 在算符優(yōu)先分析中，僅研究終結(jié)符之間的優(yōu)先關(guān)系，而不考慮非終結(jié)符之間的優(yōu)先關(guān)系，但句柄是由終結(jié)符和非終結(jié)符一起構(gòu)成的，所以算符優(yōu)先分析相對來說是非規(guī)范的分析。,5.2.2 算符優(yōu)先分析算法,62,5.2.2 算符優(yōu)先分析算法,由于算符優(yōu)先分析法僅在終結(jié)符之間定義了

33、優(yōu)先關(guān)系而未對非終結(jié)符定義優(yōu)先關(guān)系，因此算符優(yōu)先分析法不是用句柄而是用最左素短語來刻畫“可歸約串” 。 先定義算符優(yōu)先文法句型的“最左素短語”，用來刻畫算符優(yōu)先分析法的“可歸約串” 。,63,5.2.2 算符優(yōu)先分析算法,素短語 是指這樣的一個(gè)短語， 它至少含有一個(gè)終結(jié)符， 并且除它自身外，不再含有更小的素短語。 最左素短語，是指處于句型最左邊的那個(gè)素短語。 例5-15：考慮非二義的表達(dá)式文法G(E)： E E+T|T T T*F|F F (E)|i 句型T+T*F+i#的素短語為什么？ EE+TE+T+TT+T+TT+T*F+TT+T*F+FT+T*F+i 素短語有: T*F，i,64,尋找

34、最左素短語,算符優(yōu)先文法句型的一般形式： #N1a1N2a2Nnan Nn+1# (5.4) 括在兩個(gè)#號之間的部分，其中每個(gè)ai都是終結(jié)符， Ni是可有可無的非終結(jié)符。 一個(gè)算符優(yōu)先文法G的任何句型的最左素短語是滿足如下條件的最左子串： # NjajNiaiNi+1 # aj-1ai+1 則， NjajNiaiNi+1一定能歸約為某非終結(jié)符。,aj-1,ai+1,=,65,尋找最左素短語,尋找句型的最左素短語的過程：從左到右掃描句型的各個(gè)符號，掃描過程中依次查看兩相繼終結(jié)符號之間的優(yōu)先關(guān)系，直到找到滿足ai ai+1的終結(jié)符號ai 為止，記下ai 的位置。再從ai 開始向左掃描，直到找到滿足

35、關(guān)系aj-1 aj的終結(jié)符號aj 為止，此時(shí)形如NjajNiaiNi+1的子串就是最左素短語。,i1 *( i2 + i3) # # * + ) # i1，i2，i3是素短語；i1是最左素短語。,66,例：P90.(5.3)文法,EE+T|T TT*F|F FPF|P P(E)|i 求句型 T+T*F+i 的最左素短語:,練習(xí): 文法EE+E|E*E|(E)|i 求句型i+E*i+i的最左素短語。, # + E* i+ # i是最左素短語。, # +i# T*F是最左素短語。,67,求最左素短語及歸約：例,P90.(5.3)文法 表5.1的優(yōu)先表 句型 算符優(yōu)先關(guān)系 最左素短語 歸約用規(guī)則 #

36、T+T*F+i# #+ T*F TT*F #T+N+i# #+ T+N EE+T #N+i# #+ i Pi #N+N# # N+N EE+T #N#,在查找最左素短語歸約的過程中, 全然沒有用到非終結(jié)符, 因此對歸約得到的非終結(jié)符可以任意取名(如用N), 只要該非終結(jié)符的產(chǎn)生式右部符號串與最左素短語的符號一一對應(yīng)(非終對非終, 終對終)即可。,68,算符優(yōu)先分析算法(參見P93.),根據(jù)最左素短語的定義, 可以構(gòu)造算符優(yōu)先分析算法, 設(shè)a=棧頂終結(jié)符號, b=當(dāng)前輸入符號 if (ab) or (a b) then begin /* 移進(jìn)* / 把b推入棧中； 使ip前進(jìn)到下一個(gè)符號； en

37、d if ab then /* 歸約* / repeat 從棧中彈出符號 until 棧頂終結(jié)符號最近彈出的終結(jié)符號 else error,例: i+i*i 的分析過程,# i+i*i# 初始 #i +i*i# #+, #*, +#, *#, +#, # +, 歸約NN+N,符號棧 輸入串 分析動作 .,70,算符分析算法小結(jié),非終結(jié)符對規(guī)約沒有影響，非終結(jié)符并不進(jìn)棧; 算符優(yōu)先分析并不等價(jià)于規(guī)范規(guī)約，由于算符分析未對非終結(jié)符定義優(yōu)先關(guān)系，也就無法發(fā)現(xiàn)單個(gè)非終結(jié)符構(gòu)成的可規(guī)約串: 顯然算符優(yōu)先分析要比規(guī)范規(guī)約快的多，因?yàn)樗^了所有單個(gè)非終結(jié)符對應(yīng)的規(guī)約步驟 算符優(yōu)先分析法是一種使用廣泛、行之

38、有效的方法，常常用于分析各類表達(dá)式。 缺點(diǎn)在于有些文法不滿足算符優(yōu)先文法，必須先改寫，有些甚至無法改寫。若終結(jié)符數(shù)目多，優(yōu)先表可能會占有太多空間。,71,5.2.3 優(yōu)先函數(shù),為了節(jié)約存儲空間和便于執(zhí)行比較運(yùn)算, 在實(shí)際實(shí)現(xiàn)算符優(yōu)先分析算法時(shí)，一般不用優(yōu)先表而是用兩個(gè)優(yōu)先函數(shù)f 和g。 把每個(gè)終結(jié)符號與兩個(gè)自然數(shù)f()和g() 相對應(yīng)，使得 若1 2 則 f(1) g(2) f稱為入棧優(yōu)先函數(shù)，g稱為比較優(yōu)先函數(shù)。 可以由優(yōu)先表構(gòu)造優(yōu)先函數(shù)。,72,1. aVT#, 建立兩個(gè)結(jié)點(diǎn)fa和ga; 2. a，b VT # ， 若a = b，則從fa 至 gb 畫一條箭弧； 若a = b，則從gb 至 fa 畫一條箭弧; 3. 對每個(gè)結(jié)點(diǎn)賦予一個(gè)數(shù), 此數(shù)等于從該結(jié)點(diǎn)出發(fā)沿著箭弧所能到達(dá)的結(jié)點(diǎn)