《《自下而上語法分析》PPT課件.ppt》由會員分享，可在線閱讀，更多相關(guān)《《自下而上語法分析》PPT課件.ppt（52頁珍藏版）》請在裝配圖網(wǎng)上搜索。
1、第四章(2) 自下向上語法分析,本章要求: 1. 掌握自下向上語法分析的基本思想和基本概念 2. 了解算符優(yōu)先語法分析；求FIRSTVT集和LASTVT集，構(gòu)造算符優(yōu)先關(guān)系表；能運用算符優(yōu)先分析方法進(jìn)行表達(dá)式分析（選學(xué)） 3. 掌握句柄的定義與判定 4. 理解規(guī)范歸約的過程和LR分析過程中的實現(xiàn) 5. 掌握LR語法分析的實現(xiàn)過程,回顧: 歸約和推導(dǎo)的概念 例S aABe A Abc | b B d 用歸約的方法對句子abbcde進(jìn)行語法分析。,例S aABe A Abc | b B d abbcde,例S aABe A Abc | b B d abbcde aAbcde aAbcde,例S a
2、ABe A Abc | b B d abbcde aAbcde aAde,例S aABe A Abc | b B d abbcde aAbcde aAde aABe,例S aABe A Abc | b B d abbcde aAbcde aAde aABe S,例S aABe A Abc | b B d abbcde aAbcde aAde aABe S S rm aABe rm aAde rm aAbcde rm abbcde,自下而上的語法分析的一般過程,實現(xiàn)思想 從輸入符號串開始，從左到右進(jìn)行掃描，將輸入符號逐個移入一個棧中，邊移入邊分析，一旦棧頂符號串形成某個產(chǎn)生式的右部時，就用該產(chǎn)生
3、式的左部非終結(jié)符代替，稱為歸約。重復(fù)這一過程，直到歸約到棧中只剩下文法的開始符號時，則分析成功， 稱為“移進(jìn)-歸約”方法。 從語法樹的角度看：從語法樹的樹葉開始，逐步向上歸約構(gòu)造分析樹，直到形成根結(jié)點。是推導(dǎo)的逆過程。,最左推導(dǎo)(Left-most Derive) 每次推導(dǎo)都替換當(dāng)前句型的最左邊的非終結(jié)符。 與最右歸約對應(yīng)。 最右推導(dǎo)(Right-most Derive) 每次推導(dǎo)都替換當(dāng)前句型的最右邊的非終結(jié)符。 與最左歸約(規(guī)范歸約)對應(yīng)，得規(guī)范句型。,例：設(shè)有文法GS： (1) S aABe (2) A b (3) A A
4、bc (4) B d 使用最右推導(dǎo)： 因為S aABe aAde aAbcde abbcde，所以 abbcde是文法G的句子。,步驟 動作,(1)S aABe(2)A b (3)A Abc(4)B d,最左歸約過程是最右推導(dǎo)的逆過程， 對輸入串a(chǎn)bbcde的移進(jìn)歸約過程如下：,該分析過程反復(fù)執(zhí)行“移進(jìn)”和“歸約”兩個動作，直到棧中只有開始符號為止。,a,b a,A a,b A a,c b A a,A a,d A a,B A a,e B A a,S,“移進(jìn)-歸約”分析法中棧的使用,移進(jìn)-歸約分析器使用了一個符號棧和一個輸入緩沖區(qū) 1、句型表示,符號棧內(nèi)容 + 輸入
5、緩沖區(qū)內(nèi)容 # 當(dāng)前句型 #,2、分析器結(jié)構(gòu),3. 過程描述：do do 將輸入串最左邊的符號移入棧內(nèi); while (在棧里符號串中找到一個可歸約串)； 歸約可歸約串 while （文法開始符號出現(xiàn)在棧頂或者發(fā)現(xiàn)錯誤）；,分析成功的條件：棧頂為文法符號，輸入串為空。 注意：該過程并未涉及如何在棧里找可歸約串。實際上，不同的找可歸約串的方法，構(gòu)成了不同的分析算法。,分析器的四種動作,1) 移進(jìn)：讀入下一個輸入符號并把它下推進(jìn)棧。 2) 歸約：當(dāng)棧頂符號串形成一個可歸約的串（如：句柄）時，直接進(jìn)行歸約，即用產(chǎn)生式左側(cè)的非終結(jié)符替換棧頂?shù)木浔?3) 接受：當(dāng)棧底只有“#”和開始符號，而輸
6、入也已經(jīng)到達(dá)右端標(biāo)志符號“#”時，識別出符號串是句子，執(zhí)行該動作，表示分析成功，是歸約的一種特殊情況。 4) 出錯：棧頂?shù)膬?nèi)容與輸入符號相悖，即當(dāng)識別程序發(fā)現(xiàn)輸入符號串不是句子時，進(jìn)行出錯處理。 注意：決定移進(jìn)和歸約的依據(jù)是什么？ 棧頂是否出現(xiàn)了可歸約的符號串。,“移進(jìn)歸約”語法分析小結(jié)： 從輸入串的開始依次讀入單詞(移進(jìn)棧中) 。 一旦發(fā)現(xiàn)可歸約串(某個產(chǎn)生式的右端)就立即歸約。 歸約就是將棧頂?shù)囊淮栍梦姆óa(chǎn)生式的左部代替，歸約可能重復(fù)多次，然后繼續(xù)移進(jìn)。 若最終能歸約成文法的開始符號，則分析成功（接受）；否則出錯。 由于總是將句型的最左邊的可歸約串替換成非終結(jié)符，該方法通常得到是最右推
7、導(dǎo)。 關(guān)鍵是如何識別可歸約的符號串？,語法分析中問題的提出： 在構(gòu)造語法樹的過程中，何時歸約？ 當(dāng)可歸約串出現(xiàn)在棧頂時就進(jìn)行歸約。 如何知道在棧頂符號串中已經(jīng)形成可歸約串？ 如何進(jìn)行歸約？ 通過不同的自底向上的分析算法來解釋，不同的算法對可歸約串的定義是不同的，但分析過程都有一個共同的特點：邊移進(jìn)邊歸約。,自下而上語法分析主要有以下三種方法： 簡單優(yōu)先分析法(規(guī)范歸約)文法按 一定原則規(guī)定文法符號的優(yōu)先關(guān)系 算符優(yōu)先分析法(不規(guī)范歸約)規(guī)定 算符之間的優(yōu)先關(guān)系 LR分析法（規(guī)范歸約） LR(0)、LR(1)、SLR(1)和LALR(1),語法分析樹的生成演示,a b b c d e
8、,A,A,B,S,,,,,,,,,Ab,AAbc,Bd,SaABe,(1)S aABe(2)A b (3)A Abc(4)B d,,S aABe aAde aAbcde abbcde,規(guī)范歸約相關(guān)概念復(fù)習(xí),有文法G，開始符號為S, 如果有S=xy,則xy是文法G的句型，x,y是任意的符號串 如果有S=xAy, 且有A=,則是句型xy相對于非終結(jié)符A的短語 如果有S=xAy, 且有A-,則是句型xy相對于A-的直接短語 位于一個句型最左邊的直接短語稱為句柄. 句型--- 短語 --- 直接短語 ---句柄,注: 每次歸約的部分就是分析為句柄的字符串(最右推導(dǎo))。 在規(guī)范歸約中，關(guān)鍵問題就轉(zhuǎn)化為如
9、何識別句柄?,回到上例用句柄對句子abbcde進(jìn)行歸約有：,用句柄對句子進(jìn)行歸約的過程與用移進(jìn)-歸約過程是一致的，使用歸約的產(chǎn)生式及其順序是一致的。,(1)S aABe(2)A b (3)A Abc(4)B d,(2) Ab,(3)A Abc,aAbcde,aAde,(4)B d,(1)S aABe,aABe,S,,,,,練習(xí)：有文法如下 E-E+T|T T-T*F|F F-(E)|id 1）寫出輸入串 id1+id2*id3 的規(guī)范歸約過程； 2）給出該文法“移進(jìn)-歸約”語法分析的過程。,E=E+T =E+T*F =E+T*id =E+F*id =E+id*id =T+id*id =F+id
10、*id =id+id*id,動作 棧 輸入緩沖區(qū) 1) 準(zhǔn)備 # id1+id2*id3# 2) 移進(jìn) #id1 +id2*id3# 3) 歸約 Fid #F +id2*id3# 4) 歸約 TF #T +id2*id3# 5) 歸約 ET #E +id2*id3# 6) 移進(jìn) #E+ id2*id3# 7) 移進(jìn) #E+id2 *id3# 8) 歸約 Fid #E+F *id3# 9) 歸約 TF #E+T *id3# 10) 移進(jìn) #E+T* id3# 11) 移進(jìn) #E+T*id3 # 12) 歸約 Fid #E+T*F
11、 # 13) 歸約 TT*F #E+T # 14) 歸約 EE+T #E # 15) 接受,,,,,,,,,,所得的結(jié)果是：用產(chǎn)生式序列表示語法分析樹,E-E+T|T T-T*F|F F-(E)|id,id1 + id2 * id3,F,,T,,E,F,,T,F,T,E,移進(jìn)歸約分析中的問題,1) 移進(jìn)-歸約沖突 在分析到某一步時，既可以移進(jìn)，又可以歸約 上例第10)步可以移進(jìn)*，也可以按產(chǎn)生式EE+T進(jìn)行歸約。 2) 歸約-歸約沖突 存在兩個可選的句柄，可對棧頂符號進(jìn)行歸約 例如上述第13)步，可以用TF進(jìn)行歸約，又可以按TT*F進(jìn)行歸約。 各種分析方法中處理沖突的技術(shù)不同,
12、算符優(yōu)先分析,算符優(yōu)先分析法的思想源于表達(dá)式的分析，即利用相鄰終結(jié)符號之間的關(guān)系來尋找可歸約串。 將句型中的終結(jié)符號當(dāng)作“算符”，借助于算符之間的優(yōu)先關(guān)系確定句柄。 顯然，在一個符號串中，任意兩個相鄰終結(jié)符號a和b之間，只可能存在以下四種優(yōu)先關(guān)系：(1) a, b優(yōu)先性相同，記作a b。(2) a優(yōu)先性高于b， 記作a b。(3) a優(yōu)先性低于b ，記作a b。(4) a與b不可能相鄰，即此符號串不是句型(出錯)。 如果以上四種關(guān)系中的任意兩種都不會同時成立，則可以根據(jù)終結(jié)符號之間的歸約關(guān)系進(jìn)行語法分析。,1.算符文法:一個上下無關(guān)文法G,如果沒有P-,且沒有P-...QR...(
13、P,Q,R屬于非終結(jié)符),則G是一個算符文法。 2.算符優(yōu)先關(guān)系的定義(自底向上,可通過樹形結(jié)構(gòu)觀察) a b,G中有P-...ab...或P-...aQb... (在同一產(chǎn)生式中)a b,G中有P-...aR...的產(chǎn)生式,且R=b...或R=Qb... (注意ab相鄰)a b,G中有P-...Rb...的產(chǎn)生式,且R=...a或R=...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)先文法
14、 算符文法G的任何終結(jié)符a,b之間要么沒有優(yōu)先關(guān)系，若有優(yōu)先關(guān)系,至多有 = , 中的一種成立,則G為一算符優(yōu)先文法。,算符優(yōu)先關(guān)系表的構(gòu)造,用表格形式來表示各終結(jié)符號的優(yōu)先關(guān)系，這種表稱為優(yōu)先表。 構(gòu)造優(yōu)先關(guān)系表的方法： 按照定義手工計算 使用算法,由F-(E) 得 ( = ),例:P:E-E+T|T T-T*F|F F-(E)|i 求算符優(yōu)先表。,終結(jié)符+#,終結(jié)符+#,對于結(jié)束符#和其它終結(jié)符a有關(guān)系: # #,在優(yōu)先表中，空白部分是一種錯誤關(guān)系 相同的終結(jié)符之間的優(yōu)先關(guān)系不一定是 如果有a b,不一定有b a(不具傳遞性)，因為只定義相鄰運算符之間的優(yōu)先關(guān)系，a,b相鄰時，不一定b,a
15、相鄰。 a,b之間未必有優(yōu)先關(guān)系( , , ),算符優(yōu)先關(guān)系表的構(gòu)造算法,1.FIRSTVT集 定義：對每個非終結(jié)符P, FIRSTVT(P)=a|P=a...或P=Qa...,a為終結(jié)符,P，Q為非終結(jié)符,由優(yōu)先性低于的定義和FIRSTVT集合的定義可以得出： 若存在某個產(chǎn)生式：aP，對所有：bfirstVT(P) 都有：a < b。,構(gòu)造FIRSTVT集算法:,按照下面兩條規(guī)則來構(gòu)造FIRSTVT集： 若有產(chǎn)生式P-a...或P-Qa...,則aFIRSTVT(P) 若有產(chǎn)生式P-R...,則FIRSTVT(R)包含在FIRSTVT(P)中,所有終結(jié)符,所有非終結(jié)符,數(shù)組值為真假，為真的
16、條件是c FIRSTVT(Q),通過構(gòu)造一個二維數(shù)組F來實現(xiàn),該從數(shù)組F反映任何一個非終結(jié)符P的FIRSRVT集中的元素。步驟：,先用第一條規(guī)則進(jìn)行初始化,使用第二條規(guī)則對數(shù)組F進(jìn)行修改，修改方法是： (1) 用一個棧，將所有F數(shù)組中值為真的元素FP,a的符號對(P,a)壓入堆棧； (2) 對棧施行如下操作：若棧不空，將棧頂符號對出棧，記為(Q,a)，檢查所有的產(chǎn)生式，若有形為：PQ的產(chǎn)生式，且FP,a為假，則使FP,a為真，且將(P,a)壓入堆棧； (3) 重復(fù)這一過程，直到?？?求文法各非終結(jié)符的firstVT：,定義數(shù)組：,EE+T | TTT*F | FF(E) | i,從而得到： F
17、irstVT(E) = +, *,(, I FirstVT(T) = *,(,I FirstVT(F) = (,I,Begin For 對每個非終結(jié)符P和終結(jié)符a do FP,a = false For 對每個形如Pa或PQa的產(chǎn)生式 do Insert(P,a) While stack 非空 Begin 把棧頂項出棧，記為(Q,a) For 對每條形如PQ的產(chǎn)生式 do insert(P,a) End; End.,PROCEDURE insert(P,a); IF not FP,a then begin fp,a = true; (P,a)進(jìn)棧 end;,對數(shù)組初始化,應(yīng)用規(guī)則1,應(yīng)用規(guī)
18、則2,2. 求LASTVT集 定義：LASTVT(P)=a|P = ...a或P =... aQ,a為終結(jié)符,P，Q為非終結(jié)符,+,+,構(gòu)造LASTVT集算法: (思考？),3.構(gòu)造優(yōu)先關(guān)系表 如果每個非終結(jié)符的FIRSTVT和LASTVT集均已知,則可構(gòu)造優(yōu)先關(guān)系表。 若產(chǎn)生式右部有...aP...的形式,則對于每個bFIRSTVT(P)都有a b(優(yōu)先集) 若產(chǎn)生式右部有...Pb的形式,則對于每個aLASTVT(P)集,都有a b 若產(chǎn)生是形如：Aab 或 AaBb形式，則有a b 構(gòu)造優(yōu)先關(guān)系表的算法如下：,For 每條形如PX1X2Xn的產(chǎn)生式 do for i =1 to n-1
19、 do begin if Xi和Xi+1都是終結(jié)符 then Xi = Xi+1 if i Xi+1 ; end;,構(gòu)造優(yōu)先關(guān)系表,算符優(yōu)先分析算法,通過比較終結(jié)符間的優(yōu)先關(guān)系來實現(xiàn) 根據(jù)優(yōu)先分析的原理：語法分析程序的任務(wù)是：不斷移進(jìn)輸入符號，識別句柄并進(jìn)行歸約。 分析的方法：根據(jù)優(yōu)先性“高于”來識別句柄的頭，根據(jù)優(yōu)先性“低于”來識別句柄的尾。各種優(yōu)先關(guān)系已經(jīng)存于優(yōu)先關(guān)系表中。,1.不能識別只由一個非終結(jié)符組成的句柄。不能保證每次對句柄進(jìn)行歸約,在算符優(yōu)先分析過程中,每次歸約的符號串,是當(dāng)前句型的最左素短語. 2.素短語：至少含有一個終結(jié)符,且除自身外,不再包含任何其它更小的素短語。 3.最左
20、素短語(leftmost prime phrase)：是指位于句型最左邊的那個素短語。,例：下述文法的一個句型： T * F + i 其短語、素短語、最左素短語分別是？,ET | E+T TF | T*F Fi | (E),短語有：i, T * F, T * F + i 素短語有： i, T * F 最左素短語是：T * F,,一個算符文法G的某個句型的最左素短語可描述： 設(shè)句型的一般形式為(NiVN,ai VT #N1a1 N2a2 Nnan # 它的最左素短語是滿足下列條件的最左子串： Niai Ni+1ai+1 Njaj Nj+1 其中：ai-1ai,, aiai+1..aj-1aj
21、， ajaj+1,該定理說明了最左素短語與周圍符號之間的關(guān)系,例:文法G E-E+T|T T-T*F|F F-(E)|i 句型T+T*F+i的語法樹如圖：,根據(jù)語法樹可知： 句型#T+T*F+i#的短語有： T 相對非終結(jié)符E的短語 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ù)最左素短語
22、的定義) 句型的一般形式: #N1a1N2a2...NnanNn+1#(ai為終結(jié)符,Ni為可有可無的非終結(jié)符) 從左向右掃描各符號,依次查看算符優(yōu)先矩陣,直至找到滿足ai ai+1的終結(jié)符為止,一直移進(jìn).再從ai開始往左掃描,直至找到滿足關(guān)系aj-1 aj的終結(jié)符為止,進(jìn)行歸約。 此時,形如:Nj aj Nj+1 aj+1.....Ni ai Ni+1的子串即為最左素短語，應(yīng)被歸約。 分析過程的結(jié)束：分析棧中為#S，輸入串為#,例: E-E+T|T T-T*F|FF-(E)|i 把#入棧,讀一符號i, 因為# + ,所以歸約:F-i 因# * , 所以歸約:F-i 因+ # , 所以歸約:
23、F-i 因* # , 所以歸約:T-F*F 因+ # , 所以歸約:E-T+F 分析成功,求i+i*i的算符優(yōu)先分析過程,棧 輸入緩沖區(qū) # i+i*i# #i +i*i# #F +i*i# #F+ i*i# #F+i *i# #F+F *i# #F+F* i# #F+F*i # #F+F*F # #F+T # #E #,k:=1;sk = #; Repeat a := 下一個輸入符號; If sk Vt THEN j:=k ELSE j:=k-1; WHILE sj a DO BEGIN repeat q:=sj;
24、if sj-1 Vt THEN j:=j-1 else j:=j-2; UNTIL sj < q; 把sj+1.sk歸約為某個N； k:=j+1; sk := N; END If sj < a or sj = a THEN begin k:=k+1; sk:=a; end; else error; UNTIL a=#;,算符優(yōu)先分析一般并不等價于規(guī)范規(guī)約 并不對文法的非終結(jié)符定義優(yōu)先關(guān)系，無法發(fā)現(xiàn)由單個非終結(jié)符組成的“可歸約串”。即無法使用單非產(chǎn)生式(如：TF)進(jìn)行歸約。 算符優(yōu)先分析比規(guī)范歸約過程要快，跳過了所有的單非產(chǎn)生式。 可能將本來不是句子的輸入串誤認(rèn)為是句子。,總結(jié)歸約的策略: 在文法中尋找這樣的產(chǎn)生式:它的右部形如:uj aj uj+1 aj+1... ui ai ui+1,其中每個終結(jié)符號與最左素短語對應(yīng)位置上的終結(jié)符號完全相同,而每一個非終結(jié)符號uk應(yīng)與相應(yīng)位置上的非終結(jié)符號Nk相對應(yīng),不必完全相同。,算符優(yōu)先分析法小結(jié),優(yōu)點 簡單、效率高 能夠處理部分二義性文法 缺點 文法書寫限制大 占用內(nèi)存空間大 不規(guī)范、存在查不到的語法錯誤,設(shè)文法為： E#E# TF EE+T FPF|P ET P（E ） TT*F PI 求算符優(yōu)先關(guān)系表。(分析過程見呂映芝課本),練習(xí),
《自下而上語法分析》PPT課件.ppt
