自下而上語法分析課件

1、1第五章 語法分析自下而上分析 5.1 自下而上分析基本問題5.2 算符優(yōu)先分析5.3 LR分析法5.4 語法分析器的自動產(chǎn)生工具YACC（略）25.1 自下而上分析基本問題一、歸約1.“移進規(guī)約”的思想： 用一個寄存符號的先進后出棧，把輸入符號一個一個地移進棧里，當(dāng)棧頂形成某個產(chǎn)生式的一個候選式時，即把棧頂?shù)倪@一部分替換成（歸約為）該產(chǎn)生式的左部符號。3舉例：已知文法G為(1)SaAcBe (2)Ab (3)AAb (4)Bd 及輸入串a(chǎn)bbcde歸約過程如下:eBcAa進9BcAa歸8dcAa進7cAa進6bAa進4Aa歸5Aa歸3ba進2S歸10a進1動作:步驟:5.1 自下而上分析基本

2、問題42.自下而上分析的關(guān)鍵:“可歸約串”如何精確定義？“可歸約串”的不同定義，形成了不同的自下而上的分析方法。從上例的步驟（）可發(fā)現(xiàn)5.1 自下而上分析基本問題“算符優(yōu)先分析”中：“最左素短語”“可歸約串”“規(guī)范歸約分析”中：“句柄”“可歸約串”例：5.自下而上分析的中心問題： 怎樣判斷棧頂?shù)姆柎目蓺w約性以及如何歸約。5.1 自下而上分析基本問題各種自下而上分析法的共同特點： 邊輸入單詞符號（移進符號棧），邊歸約。即：在從左到右移進輸入串的過程中，一旦發(fā)現(xiàn)棧頂呈現(xiàn)可歸約串就立即進行歸約。6二.規(guī)范歸約簡述5.1 自下而上分析基本問題(1)短語:若且,則稱是句型相對于 非終結(jié)符的短語。*

3、+(2)直接短語:若，則稱是句型相對于規(guī)則 的直接短語。(3)句柄：一個句型的最左直接短語成為該句型的句柄。.定義：令是一個文法，是的開始符號， 假定是文法的一個句型， 即 *75.1 自下而上分析基本問題規(guī)范規(guī)約中的概念短語：直接短語：句柄：是句型的短語僅當(dāng) S A 且A S.A.A =最左直接短語8例1：EE+T | TTT*F | FF(E) | i i1*i2+i3短語：直接短語：句柄： i1，i2，i3，i1*i2，i1*i2+i3 i1，i2，i3i19練習(xí)：EE+T | TTT*F | FF(E) | i E+T*F+i 短語：直接短語：句柄： E+T*F+i, E+T*F, T

4、*F, i T*F, i T*FEETETTFFi+*10例2：利用句柄對句子進行歸約5.1 自下而上分析基本問題句型歸約規(guī)則aAbcdeaAcdeaAcBeS對文法(1)SaAcBe; (2)Ab; (3)AAb; (4)Bd 的句子abbcde進行歸約。 abbcde(2)Ab(3)AAb(4)Bd(1)SaAcBe112.規(guī)范歸約規(guī)范歸約是關(guān)于的一個最右推導(dǎo)的逆過程.5.1 自下而上分析基本問題例: S aAcBe aAcde aAbcde abbcde (1) (2) (3) (4)(1)定義:設(shè)是文法G的一個句子,我們稱序列n, n-1,0 是的一個規(guī)范歸約,若此序列滿足:n=;0=

5、S，S為文法開始符號;對任何i,0in, i-1是經(jīng)把i的句柄替換為相應(yīng)產(chǎn)生式的左部符號而得到的.12(2)規(guī)范推導(dǎo):即最右推導(dǎo).5.1 自下而上分析基本問題 規(guī)范句型:由規(guī)范推導(dǎo)所得到的句型,稱為規(guī)范句型. 若文法G是無二義的,則規(guī)范推導(dǎo)(最右推導(dǎo))的逆過程必是規(guī)范歸約(最左歸約)。(3)規(guī)范歸約的實質(zhì):在移進過程中，當(dāng)發(fā)現(xiàn)棧頂呈現(xiàn)句柄時， 就用相應(yīng)產(chǎn)生式的左部符號進行替換。2.規(guī)范歸約規(guī)范歸約的中心問題：如何尋找或確定一個句型的句柄。給出了尋找句柄的不同算法就給出了不同的規(guī)范歸約方法。13三、符號棧的使用1.與LL(1)方法區(qū)別：符號棧輸入串開始#W#分析成功#S#符號棧輸入串開始#SW#

6、分析成功#LL(1)分析:5.1 自下而上分析基本問題142.舉例：規(guī)范歸約（課本88頁例5.3） 語法分析對符號棧的使用有四類操作：5.1 自下而上分析基本問題“移進”指把輸入串的一個符號移進棧.“歸約”指發(fā)現(xiàn)棧頂呈可規(guī)約串,并用適當(dāng)?shù)南鄳?yīng)符號去 替換這個串.“接受”指宣布最終分析成功.“出錯處理” 指發(fā)現(xiàn)棧頂?shù)膬?nèi)容與輸入串相悖,分析工 作無法正常進行,此時需調(diào)用出錯處理程序.15例2：有文法：E-E+T|TT-T*F|FF-(E)|i對輸入串 i1+i2*i3 的規(guī)范規(guī)約過程：16 動作 棧 輸入緩沖區(qū)1) 準(zhǔn)備 # i1+i2*i3#2) 移進 #i1 +i2*i3#3) 歸約 Fi #

7、F +i2*i3#4) 歸約 TF #T +i2*i3# 5) 歸約 ET #E +i2*i3#6) 移進 #E+ i2*i3#7) 移進 #E+i2 *i3#8) 歸約 Fi #E+F *i3#9) 歸約 TF #E+T *i3# 10) 移進 #E+T* i3#11) 移進 #E+T*i3 #12) 歸約 Fi #E+T*F #13) 歸約 TT*F #E+T #14) 歸約 EE+T #E # 15) 接受所得的結(jié)果是：用產(chǎn)生式序列表示語法分析樹E-E+T|TT-T*F|FF-(E)|ii1 + i2 * i3FTEFTFTE175.2 算符優(yōu)先分析算符優(yōu)先分析： 不是一種規(guī)范歸約法，是

8、一種自下而上的語法分析法，關(guān)鍵在于規(guī)定算符（即終結(jié)符）之間的優(yōu)先順序和結(jié)合性質(zhì)，借助這種優(yōu)先關(guān)系尋找“可歸約串”進行歸約。特點：有利于表達式分析，宜于手工實現(xiàn)。18一、算符優(yōu)先文法及優(yōu)先表構(gòu)造1.算符優(yōu)先文法算符文法:一個文法，如果它的任一產(chǎn)生式的右部都不含 兩個相繼（并列）的非終結(jié)符，即不含如下形 式的產(chǎn)生式右部：則我們稱該文法為算符文法。5.2 算符優(yōu)先分析19算符優(yōu)先文法:如果一個算符文法G中的任何終結(jié)符對(a,b) 至多只滿足下述三關(guān)系之一: a b，a b，a b 則稱G是一個算符優(yōu)先文法。 假定是一個不含-產(chǎn)生式的算符文法。對于任何一對終結(jié)符a、b，我們說： a b當(dāng)且僅當(dāng) 文法G

9、中含有形如 Pab或aQb的產(chǎn)生式；5.2 算符優(yōu)先分析+ (2) a b當(dāng)且僅當(dāng) G中含有形如 PaR 的產(chǎn)生式, 而Rb或R Qb;+ (3) a b當(dāng)且僅當(dāng) G中含有形如 PRb的產(chǎn)生式, 而R a或R aQ 。+ + FIRSTVT(R)LASTVT(R)20按定義,我們用以下兩條規(guī)則構(gòu)造集合FIRSTVT(P):(1)若有產(chǎn)生式Pa或PQa, 則aFIRSTVT(P);(2)若aFIRSTVT(Q), 且有產(chǎn)生式PQ, 則aFIRSTVT(P)。返回 5.2 算符優(yōu)先分析構(gòu)造集合FIRSTVT(P):構(gòu)造集合LASTVT(P):按定義,我們用以下兩條規(guī)則構(gòu)造集合LASTVT(P):(

10、1)若有產(chǎn)生式Pa或PaQ, 則aLASTVT(P);(2)若aLASTVT(Q), 且有產(chǎn)生式PQ, 則aLASTVT(P)。215.2 算符優(yōu)先分析文法G：(1)EE+T|T (2)TT*F|F (3)FPF|P (4)P(E)|iFIRSTVT(E)=FIRSTVT(T)=FIRSTVT(F)=FIRSTVT(P)=+, *, , (,i (,i ,(,i *,(,i LASTVT(E)=LASTVT(T)=LASTVT(F)=LASTVT(P)= ),i +, *, , ),i ,),i *,),i 22（1）a b：找出滿足“ ”的所有終結(jié)符對。(借助于FIRSTVT(P)和LAST

11、VT(P)實現(xiàn))5.2 算符優(yōu)先分析2.構(gòu)造優(yōu)先表（3）構(gòu)造出優(yōu)先表（2）ab，ab：找出滿足“”和“”的所有終結(jié)符對。ab: 有形如aP的候選,且bFIRSTVT(P)；ab: 有形如Pb的候選,且aLASTVT(P)。23另:“”是作為語句的起始和結(jié)束標(biāo)記,認(rèn)為存在候選式： #開始符號#（1）#=#（2）#5.2 算符優(yōu)先分析24例:優(yōu)先關(guān)系和優(yōu)先表考慮文法G：(1)EE+T|T (2)TT*F|F (3)FPF|P (4)P(E)|i5.2 算符優(yōu)先分析FIRSTVT(E)=FIRSTVT(T)=FIRSTVT(F)=FIRSTVT(P)=+, *, , (,i (,i ,(,i *,(

12、,i LASTVT(E)=LASTVT(T)=LASTVT(F)=LASTVT(P)= ),i +, *, , ),i ,),i *,),i 25按定義,我們可得文法G終結(jié)符對的優(yōu)先關(guān)系表,如下所示:+*i()#+*i()# (1)EE+T|T (2)TT*F|F (3)FPF|P (4)P(E)|i26返回按定義,我們可得文法G終結(jié)符對的優(yōu)先關(guān)系表,如下所示:+*i()#+*i()#對于G的任何終結(jié)對(a,b),至多只有一種關(guān)系成立。 因此，G是一個算符優(yōu)先文法。27二、算符優(yōu)先分析算法1.最左素短語 素短語:是指這樣的一個短語,它至少含有一個終結(jié)符,并且, 除它自身之外不再含任何更小的素短

13、語。 最左素短語：指處于句型最左邊的那個素短語。5.2 算符優(yōu)先分析28練習(xí)：EE+T | TTT*F | FF(E) | i 練習(xí)：(1)EE+T|T(2)TT*F|F(3)FPF|P(4)P(E)|i29一個算符優(yōu)先文法G的任何句型的最左素短語是滿足 如下條件的最左子串：NjajNiaiNi+15.2 算符優(yōu)先分析aj-1 ajaj aj+1, ,ai-1 aiai ai+1句型的一般形式：#N1a1N2a2 aj-1 NjajNiaiNi+1ai+1 NnanNn+1#N1a1N2a2 aj-1 ai+1 NnanNn+1#302.算法 過程：讀入一個輸入符號a, 然后比較棧頂終結(jié)符a。

14、Si存放“文法符號”的分析棧始終指向VT符號始終指向棧頂存放“輸入符號”的字符變量用于存放待比較的終結(jié)符號：j5.2 算符優(yōu)先分析31K:=1; SK:=#; REPEAT 把下一個輸入符號讀進a中； IF SkVT THEN j:=k ELSE j:=k-1;WHILE Sja DO BEGIN REPEAT Q:=Sj; IF Sj-1VT THEN j:=j-1 ELSE j:=j-2 UNTIL Sj Q; 把 Sj+1Sk歸約為某個N； k:=j+1; Sk:=N END OF WHILE; IF Sj a OR Sja THEN BEGIN k:=k+1; Sk:=a END EL

15、SE ERROR;UNTIL a=#aj-1 aj aj+1,ai-1 ai ai+1Sj Q Sk=Q a32REPEATQ:=S j;IF Sj-1 VT THEN j:=j-1 ELSE j:=j-2UNTIL Sj Q使得Q不斷向左移,指向新終結(jié)符使得j指向VT左符號Sj與右符號Q之間還可能滿足:Sj Q 不可能出現(xiàn),若成立則前面已經(jīng)歸約過了;Sj Q 此時,符合“最左素短語” 定義,一直repeat;S j與Q無優(yōu)先關(guān)系不可能出現(xiàn), 若成立則前面已經(jīng)報告“Error”5.2 算符優(yōu)先分析335.2 算符優(yōu)先分析+*i()#+*i()#步驟分析棧剩余輸入串動作 1 # i+i*ii #

16、 2 #i +i*ii # 移進 #*R=RS A a B a=*R=RbFirst( a)b, a71(2)GO(I,X) = CLOSURE(J)AX, a IAX, a J72例：(0)SS(1)SBB (2)BaB(3)BbLR(1)項目集規(guī)范族：I0:SS, # S BB , B aB, B b,#a/ba/bI1:SS , #I2:S BB ,# B aB, B b,#I3: Ba B,a/b B aB, B b,a/ba/bI4: B b , a/bI5:S BB ,#I6: Ba B,# B aB, B b,#I7: B b , #I8: Ba B ,a/bI9: Ba B ,

17、#73狀態(tài)ACTIONGOTOab#SB012345678974練習(xí)：若有文法GS:SS;M|MMMbD|DDD(S)|（1）證明GS是SLR文法，并構(gòu)造它的分析表；（2）給出GS的LR(1)項目集規(guī)范族中的I0。75五、LALR分析表的構(gòu)造同心集的合并：76同心集的合并 不會產(chǎn)生新的移進-歸約沖突 但會產(chǎn)生新的歸約-歸約沖突A , aB , bA , bB , aA , a/bB , b/b77五、LALR分析表的構(gòu)造1、SLRLR(1)LALR(1)之間的關(guān)系LALR(1)一種折衷的方法對于同一個文法,LALR分析表永遠具有相同數(shù)目的狀態(tài)5.3 L分析法782、同義集合并 (1)同心集:若

18、兩個LR(1)項目集,除去搜索符外,這兩 個集合相同,則稱它們是同心集 (2)引出的問題 A.同心集合并不會產(chǎn)生“移進歸約”沖突 證明:(反證)假設(shè)合并后才存在“移進歸約”沖突,則:對當(dāng)前輸入符號a,項目A ,a要求歸約 項目Ba ,b要求移進既然兩項目處于合并后的一個集合中,則:合并前,必c、d,使得A ,a與Ba ,b 已同處于某一集合中。即合并前,已有LR(1)項目集 存在“移進歸約”沖突故同心集合并不會產(chǎn)生“移進歸約”沖突 B.同心集合并會產(chǎn)生“歸約歸約”沖突5.3 L分析法79例:考慮文法(0)SS(1)SaAd|bBd|aBe|bAe(2)Ac(3)Bc項目集:Ac ,d,Bc ,e Ac ,e,Bc ,d(合并)Ac ,d/e,Bc ,d/e問題:面臨a=d/e時,采用哪一個歸約?5.3 L分析法803、構(gòu)造LALR(1)分析表的步驟:(1)文法拓廣: