1、1第六章第六章 自底向上優(yōu)先分析自底向上優(yōu)先分析4本章內(nèi)容本章內(nèi)容 6.1 自底向上優(yōu)先分析方法概述自底向上優(yōu)先分析方法概述 6.2 簡(jiǎn)單優(yōu)先分析法簡(jiǎn)單優(yōu)先分析法 6.3 算符優(yōu)先分析法算符優(yōu)先分析法4本章重點(diǎn)本章重點(diǎn) 分析優(yōu)先關(guān)系，根據(jù)優(yōu)先關(guān)系進(jìn)展歸約分析優(yōu)先關(guān)系，根據(jù)優(yōu)先關(guān)系進(jìn)展歸約 求解求解FIRSTVT、LASTVT，構(gòu)造優(yōu)先關(guān)系矩陣表，構(gòu)造優(yōu)先關(guān)系矩陣表 掌握優(yōu)先函數(shù)，構(gòu)造優(yōu)先關(guān)系表掌握優(yōu)先函數(shù)，構(gòu)造優(yōu)先關(guān)系表2引言引言其根本思其根本思想是：自左向右掃描輸入符號(hào)串，逐個(gè)字符移入一個(gè)想是：自左向右掃描輸入符號(hào)串，逐個(gè)字符移入一個(gè)后進(jìn)先出棧中，邊移入邊分析，通過(guò)重復(fù)查找當(dāng)前句后進(jìn)先出棧中

2、，邊移入邊分析，通過(guò)重復(fù)查找當(dāng)前句型的句柄最左簡(jiǎn)單短語(yǔ)，并利用有關(guān)規(guī)那么進(jìn)展型的句柄最左簡(jiǎn)單短語(yǔ)，并利用有關(guān)規(guī)那么進(jìn)展規(guī)約，假設(shè)能規(guī)約為文法的識(shí)別符號(hào)，那么表示分析規(guī)約，假設(shè)能規(guī)約為文法的識(shí)別符號(hào)，那么表示分析成功，輸入符號(hào)串是文法的合法句子，否那么有語(yǔ)法成功，輸入符號(hào)串是文法的合法句子，否那么有語(yǔ)法錯(cuò)誤。錯(cuò)誤。 核心核心：尋找當(dāng)前句型中的句柄：尋找當(dāng)前句型中的句柄要點(diǎn)要點(diǎn)：建立符號(hào)棧，用來(lái)紀(jì)錄分析的歷史和現(xiàn)狀，并根建立符號(hào)棧，用來(lái)紀(jì)錄分析的歷史和現(xiàn)狀，并根據(jù)所面臨的狀態(tài)，確定下一步動(dòng)作是移進(jìn)還是規(guī)約。據(jù)所面臨的狀態(tài)，確定下一步動(dòng)作是移進(jìn)還是規(guī)約。# #S.R.P# #符號(hào)棧符號(hào)棧輸入串輸入串

3、3引例引例分析過(guò)程分析過(guò)程: abbcde=aAbcde=aAcde=aAcBe=S45分析過(guò)程研究分析過(guò)程研究分析過(guò)程分析過(guò)程: : abbcde=aAbcde=aAcde=aAcBe=Sabbcde=aAbcde=aAcde=aAcBe=S67自底向上分析方法過(guò)程自底向上分析方法過(guò)程86.1 自底向上優(yōu)先分析方法概述自底向上優(yōu)先分析方法概述4優(yōu)先分析方法分為優(yōu)先分析方法分為簡(jiǎn)單優(yōu)先分析法簡(jiǎn)單優(yōu)先分析法和和算算符符優(yōu)先分析法優(yōu)先分析法。 簡(jiǎn)單優(yōu)先分析法簡(jiǎn)單優(yōu)先分析法的根本思想是：對(duì)一個(gè)文法按一定的根本思想是：對(duì)一個(gè)文法按一定原那么求出該原那么求出該 文法所有符號(hào)即終結(jié)符和非終結(jié)符之文法所有符

4、號(hào)即終結(jié)符和非終結(jié)符之間的優(yōu)先關(guān)系，按照這種關(guān)系確定歸約過(guò)程中的句間的優(yōu)先關(guān)系，按照這種關(guān)系確定歸約過(guò)程中的句柄，它的歸約過(guò)程實(shí)際上是一種標(biāo)準(zhǔn)歸約。柄，它的歸約過(guò)程實(shí)際上是一種標(biāo)準(zhǔn)歸約。標(biāo)標(biāo)準(zhǔn)，但效率低。準(zhǔn)，但效率低。 算符優(yōu)先分析算符優(yōu)先分析的根本思想是：只規(guī)定算符之間的優(yōu)的根本思想是：只規(guī)定算符之間的優(yōu)先關(guān)系，即只考慮終結(jié)符之間的優(yōu)先關(guān)系，不考慮先關(guān)系，即只考慮終結(jié)符之間的優(yōu)先關(guān)系，不考慮非終結(jié)符之間的優(yōu)先關(guān)系，在歸約過(guò)程中只要找到非終結(jié)符之間的優(yōu)先關(guān)系，在歸約過(guò)程中只要找到句柄就歸約。句柄就歸約。不標(biāo)準(zhǔn)，但效率高。不標(biāo)準(zhǔn)，但效率高。96.2 簡(jiǎn)單優(yōu)先分析法簡(jiǎn)單優(yōu)先分析法4簡(jiǎn)單優(yōu)先分析法是

5、按照文法符號(hào)終結(jié)符和非終結(jié)符簡(jiǎn)單優(yōu)先分析法是按照文法符號(hào)終結(jié)符和非終結(jié)符的優(yōu)先關(guān)系確定句柄，進(jìn)展歸約。的優(yōu)先關(guān)系確定句柄，進(jìn)展歸約。6.2.1 優(yōu)先關(guān)系優(yōu)先關(guān)系4X Y：表示：表示X和和Y的優(yōu)先關(guān)系相等的優(yōu)先關(guān)系相等4X Y：表示：表示X的優(yōu)先性比的優(yōu)先性比Y的優(yōu)先性大的優(yōu)先性大4X Y：表示：表示X的優(yōu)先性比的優(yōu)先性比Y的優(yōu)先性小的優(yōu)先性小1X Y：當(dāng)且僅當(dāng)存在規(guī)那么：當(dāng)且僅當(dāng)存在規(guī)那么AXY2X Y：當(dāng)且僅當(dāng)存在規(guī)那么：當(dāng)且僅當(dāng)存在規(guī)那么AXB，且，且 B=Y3X Y：當(dāng)且僅當(dāng)存在規(guī)那么：當(dāng)且僅當(dāng)存在規(guī)那么ABY，且，且 B=X+*10例：例：文法文法GS：SbAb AB|a BAa分析優(yōu)

6、先關(guān)系：分析優(yōu)先關(guān)系：1求求 關(guān)系關(guān)系 b A, A b, B, A a, a 2求求 關(guān)系關(guān)系 由由SbAb, A=B, A=a, 可得：可得：b , b a 由由AB, B=B, B=a, B=A，可得：，可得： , a, A3求求 關(guān)系關(guān)系 由由SbAb, A=, A=B, A=a, 可得：可得： b, a b, B b 由由BAa, A=, A=a, A=B，可得：，可得： a, a a, B a11例：文法GS：SbAb AB|a BAa文法的簡(jiǎn)單優(yōu)先關(guān)系矩陣文法的簡(jiǎn)單優(yōu)先關(guān)系矩陣S Sb bA AB Ba a# #S S b b= = A A= = = = = a a = = #

7、# 下一個(gè)待輸入符號(hào)下一個(gè)待輸入符號(hào)aj為止。為止。2棧頂當(dāng)前符號(hào)棧頂當(dāng)前符號(hào)ai為句柄尾，由此向左在棧中找句柄的為句柄尾，由此向左在棧中找句柄的頭符號(hào)頭符號(hào)ak ，即找到，即找到ak-1 - - * * / / = = i i # # = =196.3.2 算符優(yōu)先文法的定義算符優(yōu)先文法的定義206.3.2 算符優(yōu)先文法的定義算符優(yōu)先文法的定義216.3.2 算符優(yōu)先文法的定義算符優(yōu)先文法的定義AAAa ba=b bP a Ba b其中，其中， 為為 或非終結(jié)符或非終結(jié)符D由語(yǔ)法樹構(gòu)造決定優(yōu)先性由語(yǔ)法樹構(gòu)造決定優(yōu)先性226.3.2 算符優(yōu)先文法的定義算符優(yōu)先文法的定義定義定義3 設(shè)有一個(gè)不含

8、設(shè)有一個(gè)不含 產(chǎn)生式的算符文法產(chǎn)生式的算符文法G，假如對(duì)任意兩，假如對(duì)任意兩個(gè)終結(jié)符對(duì)個(gè)終結(jié)符對(duì)a、b之間至多只存在之間至多只存在、=三種關(guān)系中的三種關(guān)系中的一種成立，那么稱一種成立，那么稱G是一個(gè)算符優(yōu)先文法，即是一個(gè)算符優(yōu)先文法，即OGP文法。文法。例：文法例：文法EE+E|E*E|E|i不是算符優(yōu)先文法。不是算符優(yōu)先文法。結(jié)論結(jié)論：+與與*的優(yōu)先關(guān)系不唯一，文法非算符優(yōu)先文法的優(yōu)先關(guān)系不唯一，文法非算符優(yōu)先文法EEEE+EE*+*236.3.3 算符優(yōu)先關(guān)系表的構(gòu)造算符優(yōu)先關(guān)系表的構(gòu)造1. 由定義直接構(gòu)造由定義直接構(gòu)造 定義兩個(gè)集合定義兩個(gè)集合FIRSTVTB和和LASTVTB FIRS

9、TVTB=b|B=b或或B=Cb LASTVTB=a|B=a或或B=aC +240E#E# 1 EE+T 2ET 3TT*F4TF 5FPF|P 6PE 7Pi1求求=關(guān)系關(guān)系 由規(guī)那么由規(guī)那么0: E#E#和規(guī)那么和規(guī)那么6: PE 可得可得: #=#, =2計(jì)算計(jì)算FIRSTVT、LASTVT集合集合 FIRSTVTE=# FIRSTVTE=+, *, , , i FIRSTVTT=*, , , i FIRSTVTF=, , i FIRSTVTP=, i LASTVTE=# LASTVTE=+, *, , , i LASTVTT=*, , , i LASTVTF=, , i LASTVTP

10、=, i25FIRSTVTE=# FIRSTVTE=+, *, , , i FIRSTVTT=*, , , i FIRSTVTF=, , i FIRSTVTP=, i LASTVTE=# LASTVTE=+, *, , , i LASTVTT=*, , , i LASTVTF=, , i LASTVTP=, i 0E#E# 1 EE+T 2ET 3TT*F 4TF 5FPF|P 6PE 7Pi掃描所有形如掃描所有形如AaB和和ABa的規(guī)那么的規(guī)那么3求求關(guān)系關(guān)系 #E: 那么有那么有#FIRSTVTE +T: 那么有那么有+FIRSTVTT *F: 那么有那么有FIRSTVTF F:那么有那么

11、有FIRSTVTF E: 那么有那么有關(guān)系關(guān)系 E#: 那么有那么有LASTVTE# E+:那么有那么有LASTVTE+ T*: 那么有那么有LASTVTT* P:那么有那么有LASTVTP E: 那么有那么有LASTVTE 26表達(dá)式文法的算符優(yōu)先關(guān)系表表達(dá)式文法的算符優(yōu)先關(guān)系表0E#E# 1 EE+T 2ET 3TT*F 4TF 5FPF|P 6PE 7PiFIRSTVTE=# FIRSTVTE=+, *, , , i FIRSTVTT=*, , , i FIRSTVTF=, , i FIRSTVTP=, i LASTVTE=# LASTVTE=+, *, , , i LASTVTT=*,

12、 , , i LASTVTF=, , i LASTVTP=, i+ +* * i i# #+ + * * i i # # = =270E#E# 1 EE+T 2ET 3TT*F 4TF 5FPF|P 6PE 7PiFIRSTVT集合的計(jì)算集合的計(jì)算1假設(shè)有產(chǎn)生式假設(shè)有產(chǎn)生式Aa或或ABa, 那么那么aFIRSTVTA2假設(shè)假設(shè)aFIRSTVTB, 且有產(chǎn)生式且有產(chǎn)生式AB, 那么那么aFIRSTVTA因此因此, 通過(guò)布爾數(shù)組通過(guò)布爾數(shù)組F, a和棧和棧STACK求解求解FIRST集合集合掃描文法中的每個(gè)非終結(jié)符掃描文法中的每個(gè)非終結(jié)符 6 P, i FP, TF, ET 棧項(xiàng)內(nèi)容為棧項(xiàng)內(nèi)容為F

13、, i, T, i, E, i 5 P, FP, TF, ET 棧項(xiàng)內(nèi)容為棧項(xiàng)內(nèi)容為F, , T, , E, 4 F, TF, ET 棧項(xiàng)內(nèi)容為棧項(xiàng)內(nèi)容為 T, , E, 3 T, * ET 棧項(xiàng)內(nèi)容為棧項(xiàng)內(nèi)容為 E, * 2 E, + 1 E, #LASTVT集合也有類似的計(jì)算方法集合也有類似的計(jì)算方法286.3.4 算符優(yōu)先分析算法算符優(yōu)先分析算法1. 算符優(yōu)先分析句型的性質(zhì)算符優(yōu)先分析句型的性質(zhì) 算符文法中的任何一個(gè)句型形式如下算符文法中的任何一個(gè)句型形式如下: #N1a1N2a2NnanNn+1#假設(shè)假設(shè)NiaiNjajNj+1為句柄為句柄, 那么那么Ni和和Nj+1在句柄中在句柄中,

14、 因?yàn)橐驗(yàn)樗惴姆ǖ娜魏尉湫椭袩o(wú)兩個(gè)相鄰的非終結(jié)符算符文法的任何句型中無(wú)兩個(gè)相鄰的非終結(jié)符, 且終結(jié)且終結(jié)符和非終結(jié)符相鄰時(shí)含終結(jié)符的句柄符和非終結(jié)符相鄰時(shí)含終結(jié)符的句柄, 必含相鄰的非終必含相鄰的非終結(jié)符結(jié)符.該句柄中的終結(jié)符之間的關(guān)系為該句柄中的終結(jié)符之間的關(guān)系為: ai-1aj+1296.3.4 算符優(yōu)先分析算法算符優(yōu)先分析算法2. 素短語(yǔ)：文法素短語(yǔ)：文法G的句型的素短語(yǔ)是一個(gè)短語(yǔ)，它至少包的句型的素短語(yǔ)是一個(gè)短語(yǔ)，它至少包含有一個(gè)終結(jié)符號(hào)，并且除它自身以外不再包含其他素含有一個(gè)終結(jié)符號(hào)，并且除它自身以外不再包含其他素短語(yǔ)短語(yǔ). 最左邊的素短語(yǔ)稱為最左素短語(yǔ)最左邊的素短語(yǔ)稱為最左素短語(yǔ)

15、.例例: 文法文法GE: TE+T|T TT*F|F FPF|P PE|i 分析句型分析句型#T+T*F+i#的短語(yǔ)的短語(yǔ) 短語(yǔ)短語(yǔ): T, T*F, T+T*F, i , T+T*F+i都是都是 素短語(yǔ)有素短語(yǔ)有: i和和T*F. 其中其中T*F是最左素短語(yǔ)是最左素短語(yǔ), 不是句柄不是句柄,滿滿足條件足條件: ai-1aj+1EE + TE + TTT * FFPi306.3.4 算符優(yōu)先分析算法算符優(yōu)先分析算法3. 算符優(yōu)先分析歸約過(guò)程算法算符優(yōu)先分析歸約過(guò)程算法3132分析句型分析句型33對(duì)輸入串對(duì)輸入串i+i#進(jìn)展歸約進(jìn)展歸約步步驟驟棧棧優(yōu)先優(yōu)先關(guān)系關(guān)系當(dāng)前符號(hào)當(dāng)前符號(hào)剩余輸入串剩余輸

16、入串移進(jìn)或移進(jìn)或歸約歸約1 1# # + +i#i#歸約歸約3 3#F#F + +i#i#移進(jìn)移進(jìn)4 4#F+#F+ # #歸約歸約6 6#F+F#F+F # #歸約歸約7 7#F#F= =# #承受承受346.3.5 優(yōu)先函數(shù)優(yōu)先函數(shù)用優(yōu)先關(guān)系矩陣存儲(chǔ)算符之間的優(yōu)先關(guān)系，需要用優(yōu)先關(guān)系矩陣存儲(chǔ)算符之間的優(yōu)先關(guān)系，需要消耗大量的內(nèi)存空間消耗大量的內(nèi)存空間n+12。算符之間的優(yōu)先關(guān)系也可用優(yōu)先函數(shù)來(lái)表示，只算符之間的優(yōu)先關(guān)系也可用優(yōu)先函數(shù)來(lái)表示，只需占用需占用2n+1存儲(chǔ)單元。存儲(chǔ)單元。定義兩個(gè)優(yōu)先函數(shù)定義兩個(gè)優(yōu)先函數(shù)f、g，滿足如下條件：，滿足如下條件： 當(dāng)當(dāng)a=b，那么令，那么令fa=gb

17、當(dāng)當(dāng)ab，那么令，那么令fab，那么令，那么令fagb35優(yōu)先函數(shù)的構(gòu)造方法優(yōu)先函數(shù)的構(gòu)造方法1由定義直接構(gòu)造優(yōu)先函數(shù)由定義直接構(gòu)造優(yōu)先函數(shù)f、g對(duì)所有終結(jié)符對(duì)所有終結(jié)符a包括包括#令令fa=ga=1。假如假如ab，而且，而且fa gb，那么令，那么令fa = gb +1假如假如a * * i i # # * * i i # # gb 第二行要求：第二行要求：fb=ga, fb=gb 導(dǎo)致：導(dǎo)致：fa=ga=fb=gb 這與這與fagb矛盾，因此不存在優(yōu)先函數(shù)。矛盾，因此不存在優(yōu)先函數(shù)。aba=b=392. 用關(guān)系圖構(gòu)造優(yōu)先函數(shù)用關(guān)系圖構(gòu)造優(yōu)先函數(shù)構(gòu)造步驟構(gòu)造步驟1對(duì)所有終結(jié)符對(duì)所有終結(jié)符a包

18、括包括#用帶下標(biāo)的用帶下標(biāo)的fa, ga標(biāo)標(biāo)注結(jié)點(diǎn)，共注結(jié)點(diǎn)，共2n個(gè)個(gè)2假設(shè)假設(shè)aiaj，或，或ai=aj，那么從，那么從fai到到gaj畫一條箭畫一條箭弧弧 假設(shè)假設(shè)ai * * + + # # a n = = t f # = = FIRSTVTB=o, a, n, , t, f LASTVTB= o, a, n, , t, f FIRSTVTT=a, n, , t, f LASTVTT= a, n, , t, f FIRSTVTF=n, , t, f LASTVTf= n, , t, f 文法的算符優(yōu)先關(guān)系矩陣構(gòu)造如下文法的算符優(yōu)先關(guān)系矩陣構(gòu)造如下各算符之間的優(yōu)先關(guān)系是唯一的，各算符之間的優(yōu)先關(guān)系是唯一的，GB是算符優(yōu)先文法！是算符優(yōu)先文法！442. 對(duì)輸入串對(duì)輸入串ntofat#的分析過(guò)程如下：的分析過(guò)程如下：