[理學]第四章2 自下而上語法分析ppt課件

1、第四章第四章2 2 自下向上語法分析自下向上語法分析本章要求本章要求:1. 掌握自下向上語法分析的根本思想和根本概念掌握自下向上語法分析的根本思想和根本概念2. 理解算符優(yōu)先語法分析；求理解算符優(yōu)先語法分析；求FIRSTVT集和集和LASTVT集，構(gòu)造算符優(yōu)先關系表；能運用算集，構(gòu)造算符優(yōu)先關系表；能運用算符優(yōu)先分析方法進展表達式分析選學符優(yōu)先分析方法進展表達式分析選學3. 掌握句柄的定義與斷定掌握句柄的定義與斷定4. 理解標準歸約的過程和理解標準歸約的過程和LRLR分析過程中的實現(xiàn)分析過程中的實現(xiàn) 5. 掌握掌握LR語法分析的實現(xiàn)過程語法分析的實現(xiàn)過程例例S aABe A Abc | bB

2、d用歸約的方法對句子用歸約的方法對句子abbcde進展語法分析。進展語法分析。例例S aABe A Abc | bB dabbcde例例S aABe A Abc | bB dabbcdeaAbcdeaAbcde例例S aABe A Abc | bB dabbcdeaAbcdeaAde例例S aABe A Abc | bB dabbcdeaAbcdeaAdeaABe例例S aABe A Abc | bB dabbcdeaAbcdeaAdeaABeS 例例S aABe A Abc | bB dabbcdeaAbcdeaAdeaABeS S rm aABe rm aAde rm aAbcde rm

3、abbcde自下而上的語法分析的一般過程自下而上的語法分析的一般過程 實現(xiàn)思想實現(xiàn)思想從輸入符號串開場，從左到右進展掃描，將輸入符號逐個移入一個棧中，邊移入邊分析，一一旦棧頂符號串形成某個產(chǎn)生式的右部時旦棧頂符號串形成某個產(chǎn)生式的右部時，就用該產(chǎn)生式的左部非終結(jié)符代替，稱為歸約歸約。重復這一過程，直到歸約到棧中只剩下文法的開場符號時，那么分析成功， 稱為“移進-歸約方法。從語法樹的角度語法樹的角度看：從語法樹的樹葉開場，逐步向上歸約構(gòu)造分析樹，直到形成根結(jié)點。是推導推導的逆過程。 最左推導最左推導Left-most Derive 每次推導都交換當前句型的最左邊的非終結(jié)符。 與最右歸約對應。 最

4、右推導最右推導Right-most Derive 每次推導都交換當前句型的最右邊的非終結(jié)符。 與最左歸約標準歸約標準歸約對應，得標準句型。例：例：設有文法GS： 1 S aABe 2 A b 3 A Abc 4 B d 使用最右推導：因為S aABe aAde aAbcde abbcde，所以abbcde是文法G的句子。)1(rm)2(rm)3(rm)4(rm 步驟步驟動作動作1S aABe2A b 3A Abc4B d最左歸約過程是最右推導的逆過程， 對輸入串a(chǎn)bbcde的移進歸約過程如下：該分析過程反復執(zhí)行該分析過程反復執(zhí)行“移進和移進和“歸約兩個動作，直到棧中只有開場符號為止。歸約兩個動

5、作，直到棧中只有開場符號為止。ab aA ab A acbA aA ad A aBA aeBA aS1移進a2移進b3歸約24移進b5移進c6歸約37移進d8歸約49移進e10歸約1“移進-歸約分析法中棧的使用 移進-歸約分析器使用了一個符號棧和一個輸入緩沖區(qū) 1、句型表示 a1 a2 a3 # X1X2X3#“移進-歸約”分析程序輸出棧(存放句型前綴)輸入串符號棧內(nèi)容符號棧內(nèi)容 + 輸入緩沖區(qū)內(nèi)容輸入緩沖區(qū)內(nèi)容 # 當前句型當前句型 #一般形式： 符號棧的內(nèi)容剩余輸入串初態(tài)：#輸入串#終態(tài)：#S#2、分析器構(gòu)造 3. 過程描繪：過程描繪：do do 將輸入串最左邊的符號移入棧內(nèi); while

6、 在棧里符號串中找到一個可歸約在棧里符號串中找到一個可歸約串串； 歸約可歸約串 while 文法開場符號出如今棧頂或者發(fā)現(xiàn)錯誤；分析成功的條件分析成功的條件：棧頂為文法符號，輸入串為空。該過程并未涉及如何在棧里找可歸約串。實際上，不同的找可歸約串的方法，構(gòu)成了不同的分析算法。分析器的四種動作分析器的四種動作 1 1 移進移進：讀入下一個輸入符號并把它下推進棧。 2 2 歸約歸約：當棧頂符號串形成一個可歸約的串如：句句柄柄時，直接進展歸約，即用產(chǎn)生式左側(cè)的非終結(jié)符交換棧頂?shù)木浔?3 3 承受承受：當棧底只有“#和開場符號，而輸入也已經(jīng)到達右端標志符號“#時，識別出符號串是句子，執(zhí)行該動作，表示

7、分析成功，是歸約的一種特殊情況。 4 4 出錯出錯：棧頂?shù)膬?nèi)容與輸入符號相悖，即當識別程序發(fā)現(xiàn)輸入符號串不是句子時，進展出錯處理。 注意：決定移進和歸約的根據(jù)是什么？注意：決定移進和歸約的根據(jù)是什么？ 棧頂是否出現(xiàn)了可歸約的符號串。棧頂是否出現(xiàn)了可歸約的符號串。 “移進歸約語法分析小結(jié)： 從輸入串的開場依次讀入單詞移進移進棧中 。 一旦發(fā)現(xiàn)可歸約串可歸約串某個產(chǎn)生式的右端就立即歸歸約約。 歸約就是將棧頂?shù)囊淮栍梦姆óa(chǎn)生式的左部代替，歸約可能重復屢次，然后繼續(xù)移進。 假設最終能歸約成文法的開場符號，那么分析成功承受承受；否那么出錯出錯。 由于總是將句型的最左邊的可歸約串交換成非終結(jié)符，該方法

8、通常得到是最右推導。 關鍵是如何識別可歸約的符號串如何識別可歸約的符號串？語法分析中問題的提出：語法分析中問題的提出： 在構(gòu)造語法樹的過程中，何時歸約？ 當可歸約串出如今棧頂時就進展歸約。 如何知道在棧頂符號串中已經(jīng)形成可歸約串？ 如何進展歸約？ 通過不同的自底向上的分析算法來解釋，不同的算法對可歸約串的定義是不同的，但分析過程都有一個共同的特點：邊移進邊歸約邊移進邊歸約。規(guī)范歸約：使用句柄句柄來定義可歸約串算符優(yōu)先：使用最左素短語最左素短語來定義可歸約串 自下而上語法分析主要有以下三種方法：自下而上語法分析主要有以下三種方法：簡單優(yōu)先分析法簡單優(yōu)先分析法標準歸約標準歸約文法按文法按一定原那么

9、規(guī)定文法符號的優(yōu)先關系一定原那么規(guī)定文法符號的優(yōu)先關系算符優(yōu)先分析法算符優(yōu)先分析法不標準歸約不標準歸約規(guī)定規(guī)定算符算符之間的優(yōu)先關系之間的優(yōu)先關系 LR分析法標準歸約分析法標準歸約 LR0、LR1、SLR1和和LALR1語法分析樹的生成演示語法分析樹的生成演示a b b c d ea b b c d eAABSAbAbAAbcAAbcBdBdSaABeSaABe1S aABe2A b 3A Abc4B dS aABe aAde aAbcde abbcde標準歸約相關概念復習 有文法G，開場符號為S, 假如有S=xy,那么xy是文法G的句型句型，x,y是任意的符號串 假如有S=xAy, 且有A=

10、,那么是句型xy相對于非終結(jié)符A的短語短語 假如有S=xAy, 且有A-,那么是句型xy相對于A-的直接短語直接短語 位于一個一個句型最左邊的直接短語稱為句柄句柄. 句型- 短語 - 直接短語 -句柄 *+*注: 每次歸約的部分就是分析為句柄句柄的字符串最右推導。在標準歸約中，關鍵問題就轉(zhuǎn)化為如何識別句柄如何識別句柄? ?回到上例用回到上例用句柄句柄對句子對句子abbcde進展歸約有：進展歸約有： 用句柄對句子進展歸約的過程與用移進-歸約過程是一致的，使用歸約的產(chǎn)生式及其順序是一致的。句型歸約規(guī)那么abbcde1S aABe2A b 3A Abc4B d2 Ab3A AbcaAbcdeaAde

11、4B d1S aABeaABeS練習：有文法如下練習：有文法如下 E-E+T|T T-T*F|F F-E|id1寫出輸入串寫出輸入串 id1+id2*id3 的標準歸約過程；的標準歸約過程；2給出該文法給出該文法“移進移進-歸約語法分析的過程。歸約語法分析的過程。E=E+T =E+T*F =E+T*id =E+F*id =E+id*id =T+id*id =F+id*id =id+id*id 動作動作 棧棧 輸入緩沖區(qū)輸入緩沖區(qū)1 1 準備準備 # id# id1 1+id+id2 2* *idid3 3# #2 2 移進移進 #id#id1 1 +id +id2 2* *idid3 3# #

12、3 3 歸約歸約 Fid #F +idFid #F +id2 2* *idid3 3# #4 4 歸約歸約 TF #T +idTF #T +id2 2* *idid3 3# # 5 5 歸約歸約 ET #E +idET #E +id2 2* *idid3 3# #6 6 移進移進 #E+ id#E+ id2 2* *idid3 3# #7 7 移進移進 #E+id#E+id2 2 * *idid3 3# #8 8 歸約歸約 Fid #E+F Fid #E+F * *idid3 3# #9 9 歸約歸約 TF #E+T TF #E+T * *idid3 3# # 1010 移進移進 #E+T#E

13、+T* * id id3 3# #1111 移進移進 #E+T#E+T* *idid3 3 # #1212 歸約歸約 Fid #E+TFid #E+T* *F #F #1313 歸約歸約 TTTT* *F #E+T #F #E+T #1414 歸約歸約 EE+T #E # EE+T #E # 1515 承受承受所得的結(jié)果是：用產(chǎn)生式序列表示語法分析樹所得的結(jié)果是：用產(chǎn)生式序列表示語法分析樹E-E+T|TT-T*F|FF-E|ididid1 1 + id + id2 2 * * id id3 3FTEFTFTE移進歸約分析中的問題移進歸約分析中的問題 1 1 移進移進- -歸約沖突歸約沖突 在分

14、析到某一步時，既可以移進，又可以歸約上例第10步可以移進*，也可以按產(chǎn)生式EE+T進展歸約。 2 2 歸約歸約- -歸約沖突歸約沖突存在兩個可選的句柄，可對棧頂符號進展歸約例如上述第13步，可以用TF進展歸約，又可以按TT*F進展歸約。 各種分析方法中處理沖突的技術不同各種分析方法中處理沖突的技術不同算符優(yōu)先分析算符優(yōu)先分析 算符優(yōu)先分析法的思想源于表達式的分析，即利用相鄰終結(jié)符號之間的關系來尋找可歸約串。 將句型中的終結(jié)符號當作“算符，借助于算符之間的優(yōu)先關系確定句柄。 顯然，在一個符號串中，任意兩個相鄰終結(jié)符號a和b之間，只可能存在以下四種優(yōu)先關系：1 a, b優(yōu)先性一樣，記作a b。2

15、a優(yōu)先性高于b， 記作a b。3 a優(yōu)先性低于b ，記作a b。4 a與b不可能相鄰，即此符號串不是句型出錯。 假如以上四種關系中的任意兩種都不會同時成立，那么可以根據(jù)終結(jié)符號之間的歸約關系進展語法分析。 1.算符文法:一個上下無關文法G,假如沒有P-,且沒有P-.QR.P,Q,R屬于非終結(jié)符,那么G是一個算符文法。算符文法。 2.算符優(yōu)先關系算符優(yōu)先關系的定義自底向上,可通過樹形構(gòu)造觀察 a b,G中有P-.ab.或P-.aQb. 在同一產(chǎn)在同一產(chǎn)生式中生式中a b,G中有P-.aR.的產(chǎn)生式,且R=b.或R=Qb. 注意注意ab相鄰相鄰a b,G中有P-.Rb.的產(chǎn)生式,且R=.a或R=.

16、aQ 注意注意ab相鄰相鄰算符優(yōu)先文法的定義+例：EE+E | E*E | E | i 證明不是算符優(yōu)先文法。因為：EE+E ， EE*E 那么有 + *又因為：EE*E, EE+E 那么有 + *所以不是算符優(yōu)先文法。 3.算符優(yōu)先文法算符優(yōu)先文法算符文法G的任何終結(jié)符a,b之間要么沒有優(yōu)先關系，假設有優(yōu)先關系,至多有 = , 中的一種成立,那么G為一算符優(yōu)先文法算符優(yōu)先文法。算符優(yōu)先關系表算符優(yōu)先關系表的構(gòu)造的構(gòu)造 用表格形式來表示各終結(jié)符號的優(yōu)先關用表格形式來表示各終結(jié)符號的優(yōu)先關系，這種表稱為優(yōu)先表。系，這種表稱為優(yōu)先表。 構(gòu)造優(yōu)先關系表的方法：構(gòu)造優(yōu)先關系表的方法： 按照定義手工計算

17、按照定義手工計算 使用算法使用算法 由F-E 得 = T = i, 得 + T*F, 得 + E, 得 + E+TE = i, 得i +E = E+T, 得+ + E = T*F, 得* + E = E, 得 + +*i#+*i#例:P:E-E+T|T T-T*F|F F-E|i 求算符優(yōu)先表。終結(jié)符+#終結(jié)符+#對于結(jié)束符#和其它終結(jié)符a有關系: # # * 在優(yōu)先表中，空白部分是一種錯誤關系 一樣的終結(jié)符之間的優(yōu)先關系不一定是 假如有a b,不一定有b a不具傳遞性，因為只定義相鄰運算符之間的優(yōu)先關系，a,b相鄰時，不一定b,a相鄰。 a,b之間未必有優(yōu)先關系 , , 算符優(yōu)先關系表的構(gòu)造

18、算法算符優(yōu)先關系表的構(gòu)造算法 1.FIRSTVT1.FIRSTVT集集定義：對每個非終結(jié)符P, FIRSTVTP=a|P=a.或P=Qa.,a為終結(jié)符,P，Q為非終結(jié)符+由優(yōu)先性低于的定義和FIRSTVT集合的定義可以得出：若存在某個產(chǎn)生式：aP，對所有：bfirstVT(P)都有：a a.或P-Qa.,那么aFIRSTVTP 假設有產(chǎn)生式P-R.,那么FIRSTVTR包含在FIRSTVTP中abcPQ所有終結(jié)符所有非終結(jié)符數(shù)組值為真假，為真的條件是c FIRSTVTQ 通過構(gòu)造一個二維數(shù)組F來實現(xiàn),該從數(shù)組F反映任何一個非終結(jié)符P的FIRSRVT集中的元素。步驟： 先用第一條規(guī)那么進展初始化

19、先用第一條規(guī)那么進展初始化 使用第二條規(guī)那么對數(shù)組使用第二條規(guī)那么對數(shù)組F F進展修改，進展修改，修改方法是： 1 用一個棧，將所有F數(shù)組中值為真的元素FP,a的符號對P,a壓入堆棧； 2 對棧施行如下操作：假設棧不空，將棧頂符號對出棧，記為Q,a，檢查所有的產(chǎn)生式，假設有形為：PQ的產(chǎn)生式，且FP,a為假，那么使FP,a為真，且將P,a壓入堆棧； 3 重復這一過程，直到?？涨笪姆ǜ鞣墙K結(jié)符的firstVT： 定義數(shù)組：+*iE1T1F11EE+T | TTT*F | FFE | i11111從而得到：從而得到：FirstVTE = +, *, IFirstVTT = *,IFirstVTF

20、= ,IBeginFor 對每個非終結(jié)符對每個非終結(jié)符P和終結(jié)符和終結(jié)符a doFP,a = falseFor 對每個形如對每個形如Pa或或PQa的產(chǎn)生式的產(chǎn)生式 doInsertP,aWhile stack 非空非空Begin把棧頂項出棧，記為把棧頂項出棧，記為Q,aFor 對每條形如對每條形如PQ的產(chǎn)生式的產(chǎn)生式 do insertP,aEnd;End.PROCEDURE insertP,a;IF not FP,a then begin fp,a = true; P,a進進棧棧 end;對數(shù)組初始化應用規(guī)那么1應用規(guī)那么2 2. 求求LASTVT集集 定義：LASTVTP=a|P = .a

21、或P =. aQ,a為終結(jié)符,P，Q為非終結(jié)符+構(gòu)造LASTVT集算法: 考慮？ 3.3.構(gòu)造優(yōu)先關系表構(gòu)造優(yōu)先關系表假如每個非終結(jié)符的FIRSTVT和LASTVT集均,那么可構(gòu)造優(yōu)先關系表。假設產(chǎn)生式右部有.aP.的形式,那么對于每個bFIRSTVTP都有a b優(yōu)先集假設產(chǎn)生式右部有.Pb的形式,那么對于每個aLASTVTP集,都有a b 假設產(chǎn)生是形如：Aab 或 AaBb形式，那么有a b 構(gòu)造優(yōu)先關系表的算法如下：For 每條形如每條形如PX1X2Xn的的產(chǎn)生式產(chǎn)生式 dofor i =1 to n-1 dobeginif Xi和和Xi+1都是終結(jié)符都是終結(jié)符 then Xi = Xi

22、+1if i= n-2 且且 xi和和Xi+2都是終結(jié)符都是終結(jié)符, Xi+1為非終結(jié)符為非終結(jié)符 then Xi = Xi+2if Xi為終結(jié)符為終結(jié)符, Xi+1為非終結(jié)符為非終結(jié)符 then for firstVT中的每個元素中的每個元素a do Xi Xi+1 ;end;構(gòu)造優(yōu)先關系表算符優(yōu)先分析算法算符優(yōu)先分析算法 通過比較終結(jié)符間的優(yōu)先關系來實現(xiàn) 根據(jù)優(yōu)先分析的原理原理：語法分析程序的任務是：不斷移進輸入符號，識別句柄并進展歸約。 分析的方法分析的方法：根據(jù)優(yōu)先性“高于來識別句柄的頭，根據(jù)優(yōu)先性“低于來識別句柄的尾。各種優(yōu)先關系已經(jīng)存于優(yōu)先關系表中。 1.不能識別只由一個非終結(jié)符組

23、成的句柄。不能保證每次對句柄進展歸約,在算符優(yōu)先分析過程中,每次歸約的符號串,是當前句型的最左素短語. 2.素短語：素短語：至少含有一個終結(jié)符,且除自身外,不再包含任何其它更小的素短語。 3.最左素短語最左素短語leftmost prime leftmost prime phrasephrase：是指位于句型最左邊的那個素短語。例：下述文法的一個句型： T * F + i 其短語、素短語、最左素短語分別是？ET | E+TTF | T*FFi | EEE + TFiTT * F短語有：i, T * F, T * F + i素短語有： i, T * F最左素短語是：T * F 一個算符文法一個算

24、符文法G的某個句型的最左素短語可描述：的某個句型的最左素短語可描述：設句型的一般形式為設句型的一般形式為(NiVVN N,ai VVT T#N1a1 N2a2 Nnan #它的它的最左素短語最左素短語是滿足下列條件的最左子串：是滿足下列條件的最左子串：Niai Ni+1ai+1 Njaj Nj+1其中：其中：ai-1ai, aiai+1.aj-1aj ， ajaj+1該定理說明了最左素短語與周圍符號之間的關系 例:文法G E-E+T|T T-T*F|F F-E|i 句型T+T*F+i的語法樹如圖：EET+E+TFTT*FPi根據(jù)語法樹可知：句型#T+T*F+i#的短語短語有：T 相對非終結(jié)符E

25、的短語T*F 相對非終結(jié)符T的短語T+T*F 相對非終結(jié)符E的短語i 相對非終結(jié)符P、F、T的短語T+T*F+i 相對非終結(jié)符E的短語根據(jù)素短語素短語的定義可知： i和T*F為素短語。其中：T+T*F 含T*F素短語、 T+T*F+i 含T*F素短語 和 T不含終結(jié)符也不是素短語T*F為最左素短語最左素短語。 3.算符優(yōu)先分析過程：根據(jù)最左素短語的定義句型句型的一般形式: #N1a1N2a2.NnanNn+1#ai為終結(jié)符,Ni為可有可無的非終結(jié)符從左向右掃描各符號,依次查看算符優(yōu)先矩陣,直至找到滿足ai ai+1的終結(jié)符為止,一直移進.再從ai開場往左掃描,直至找到滿足關系aj-1 aj的終結(jié)符為止,進展歸約。此時,形如:Nj aj Nj+1 aj+1.Ni ai Ni+1的子串即為最左素短語，應被歸約。分析過程的完畢：分析棧中為#S，輸入串為# 例: E-E+T|T T-T*F|FF-E|i 把#入棧,讀一符號i, 因為# + ,所以歸約:F-i 因# + , 所以+入棧 因+ * , 所以歸約:F-i 因+ * , 所以*入棧 因* # , 所以歸約:F-i 因* # , 所以歸約:T-F*F 因+ # , 所以歸約:E-T+F 分析成功求i+i*i的算符優(yōu)先分析過