自下而上語法分析.ppt

《自下而上語法分析.ppt》由會員分享，可在線閱讀，更多相關(guān)《自下而上語法分析.ppt（56頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、,若文法G的任何產(chǎn)生式的右部都不含兩個相繼的非終結(jié)符， 稱文法為算符文法。 即：不含形如：UVW 的產(chǎn)生式，U、V、WVN,G1S： S E E ET | T T T*F | F F PF | P P (E)| i,G2E： E TE E +TE |,5.3 算符優(yōu)先分析法5.3.1 算符優(yōu)先文法及優(yōu)先表構(gòu)造,1. 算符文法,2. 優(yōu)先關(guān)系：設(shè)G是算符文法，不含 P產(chǎn)生式, 對于任何一對終結(jié)符 a，b a b G中存在形如：Pab 或 PaRb 的產(chǎn)生式； a. b G中存在形如：P aR 的產(chǎn)生式， 且R b 或 R Q b ； a .b G中存在形如：P 的產(chǎn)生式，

2、 且R a 或 R a Q ；,,G1S： SE EET | T TT*F | F FPF | P P(E)| i,S#E# # # P (E) ( ) 2) S#E# E=ET # T * F ET # EET E=ET ,設(shè)有算符文法G，如果其任意兩個終結(jié)符號之間，最 多只有一種算符優(yōu)先關(guān)系成立，稱G為算符優(yōu)先文法。 算符優(yōu)先文法是無二義的。,3. 算符優(yōu)先文法,4. 優(yōu)先表,二維表，行標(biāo)、列標(biāo)VT ，表項：存放優(yōu)先關(guān)系 Aa,b= a b Aa,b= a b Aa,b= a b,,,G1S： S E E ET | T T T*F | F F PF |

3、P P (E)| i,優(yōu)先表,對優(yōu)先關(guān)系： # # ( ) # # ,沒有優(yōu)先關(guān)系,FirstVT(P)= a | P a 或 P Q a a VT , P、Q VN ( P推導(dǎo)出的符號串的第一個終結(jié)符構(gòu)成的集合) LastVT(P) = a | P a 或 P a Q a VT , P、Q VN ( P推導(dǎo)出的符號串的最后一個終結(jié)符構(gòu)成的集合),6.計算FirstVT集合,若有 P a 或 PQ a ，則 aFirstVT(P) 若 aFirstVT(Q)，且 PQ ，則 aFirstVT(P),5. 定義集合,若有 P a 或 PQ a ，則 aFirstV

4、T(P) 若 aFirstVT(Q)，且 PQ ，則 aFirstVT(P),,For (PVN , a VT) do FP,a=.F. ; For (P a 或PQa ) do insert(P,a); While stack非空 do 彈出stack棧頂組對(P,a); RP do insert(R,a); ,Proc insert(P,a) if FP,a=.F. then FP,a=.T.； (P,a)入stack； ,引入： 棧stack，存放二元組對 (P,a) 布爾數(shù)組F, FP,a=.T.aFirstVT(P),,算法：,,,GS：S#E# EE

5、+T|T TT*F|F FPF|P P(E)|i,For (PVN , a VT) do FP,a=.F. ; For (P a 或PQa ) do insert(P,a); While stack非空 do 彈出stack棧頂組對(P,a); RP do insert(R,a); ,Proc insert(P,a) if FP,a=.F. then FP,a=.T.； (P,a)入stack； ,,,,For (PVN , a VT) do FP,a=.F. ; For (P a 或PQa ) do insert(P,a); While stack非空 do

6、 彈出stack棧頂組對(P,a); RP do insert(R,a); ,Proc insert(P,a) if FP,a=.F. then FP,a=.T.； (P,a)入stack； ,GS：S#E# EE+T|T TT*F|F FPF|P P(E)|i,,,GS： S#E# EE+T|T TT*F|F FPF|P P(E)|i,FirstVT(S)=# FirstVT(E)=+,*,,( ,i FirstVT(T)=*,,( ,i FirstVT(F)=,( ,i FirstVT(P)=( ,i ,求FirstVT： FP,a=.T. aFirstVT(P),布爾數(shù)組

7、F,,若有P a 或P aQ 則 aLastVT(P) 若aLastVT(Q) ,且 PQ, 則 aLastVT(P),算法： 與計算 FirstVT集合類似,GS： S#E# EE + T | T TT * F | F FPF | P P(E) | i,LastVT(S)= # LastVT(E)=+,*,,i , ) LastVT(T)=*,, i , ) LastVT(F)=, i , ) LastVT(P)= i , ) ,7.計算LastVT集合,For ( A X1 X2 XN ) do For i:=1 To N1 do if (XiVT)and(Xi+1VT ) then

8、Xi Xi+1 ; if (XiVT )and(Xi+1VN ) and (Xi+2VT ) then Xi Xi+2; if (XiVT)and(Xi+1VN ) then bFirstVT(Xi+1) Xi Xi+1 ; ,8.構(gòu)造優(yōu)先表算法,,S#E# # # ## 2) EET (aLastVT(E)) <(bFirstVT(T)) 3) ET 不影響,GS： S#E# EE + T | T TT * F | F FPF | P P(E) | i,,GS： S#E# EE + T | T TT * F | F FPF | P P(E) | i,4) TT

9、* F (aLastVT(T)) * * < (bFirstVT(F)),,7) FP 不影響 8) P( E ) ( ) () 9) Pi 不影響,GS： S#E# EE + T | T TT * F | F FPF | P P(E) | i,短語：令GS是一文法，是文法G的一個句型；如果有：S A，且 A ； 稱是句型相對于非終結(jié)符A的短語。 2. 素短語：一種短語，它至少包含一個終結(jié)符，且除自身外不再包含更小的素短語。 3.最左素短語：處于句型最左邊的素短語。 算符優(yōu)先分析法的可歸約串最左素短語。,5.3.2 算符優(yōu)先分析算法,,句型：P1*(P2)+P3,短語：P1 , P2 , (

10、P2), P1*(P2), P3 , P1*(P2)+P3 素短語：(P2) 最左素短語：(P2),,GS：S#E# EE + T | T TT * F | F FPF | P P(E) | i,語法樹,,短語：P1 , P2 , P1*P2 , P3 , P4 , P3*P4 , P1*P2+P3*P4 素短語： P1*P2 , P3*P4 最左素短語： P1*P2,句型：P1*P2+P3*P4,,語法樹,GS：S#E# EE + T | T TT * F | F FPF | P P(E) | i,若句型為：# N1 a1 N2 a2 ...Nn an Nn+1 #

11、 Ni VN , ai VT 最左素短語是滿足下列條件的最左子串 Nj aj Nj+1 aj+1 ... Ni-1 ai-1 Ni ai Ni+1 1) aj-1. aj 2) 3) ai .ai+1,aj aj+1 ... ai-1 ai,4. 定理,找出句型中的最左素短語，選擇一條合適的產(chǎn)生式， 將最左素短語歸約為該產(chǎn)生式的左部符號。重復(fù)上述 過程，直至句型中只存在一個符號，并且是非終結(jié)符 號，則輸入串是句子。 選用合適產(chǎn)生式的標(biāo)準(zhǔn)： 最左素短語 x1 x2 xn , 產(chǎn)生式右部 y1 y2 yn 若： xiVT 則 yiVT 且 xiyi 若： xiVN 則 yiVN

12、 (但可以 xiyi ） 即：終結(jié)符必須位置匹配且為同一符號； 非終結(jié)符必須位置匹配。,5.算符優(yōu)先分析算法,k=1; Sk=# ; repeat 把下一個單詞讀進(jìn) a ; if (SkVT) then j=k else j=k-1 ; while (Sj a) do /* 可歸約 */ repeat /*找最左素短語的左端終結(jié)符號*/ Q:= Sj ; if (Sj-1VT ) then j=j-1 else j=j-2; until Sj< Q; 把 Sj+1 Sj+2 Sk 歸約為某個N; K=j+1; Sk=N; if (Sj

13、en k=k+1; Sk=a else error ; Until a=#,,輸入串：i*i+i 設(shè)：x=最靠近棧頂?shù)腣T,GS：S# E # EE + T | T TT * F | F FPF | P P(E) | i,歸約序列： i*i+i <= P*i+i <= P*P+i,,歸約序列：i*i+i<=P*i+i<=P*P+i<=T+i<=T+P<=E ,輸入串：i*i+i 設(shè)：x=最靠近棧頂?shù)腣T,GS：S# E # EE + T | T TT * F | F FPF | P P(E) | i,,算符優(yōu)先分析法，語法樹分析樹 省去了Q<=P 的歸約步驟，

14、所以歸約效率高。,6. 分析樹,歸約序列：i*i+i<=P*i+i<=P*P+i<=T+i<=T+P<=E,,,,,,語法樹,用兩個離散函數(shù) f , g 來代表優(yōu)先表， f(a) , g(a) 的函數(shù)值為自然數(shù)，其中：aVT ； 要求： 若a . b 則 f(a) g(b) f(a) 入棧優(yōu)先函數(shù) (a位于左邊時的函數(shù)值) g(a) 出棧優(yōu)先函數(shù) (a位于右邊時的函數(shù)值),5.3.2 優(yōu)先函數(shù),1. 優(yōu)先函數(shù)表示方法,,GS： S# E # EE + T | T TT * F | F FPF | P P(E) | i,,,,,輸入串：i*i,GS：S# E # EE + T | T TT

15、 * F | F FPF | P P(E) | i,歸約序列： i*i<= P*i<= P*P<= T,設(shè)：a=最靠近棧頂?shù)腣T, 優(yōu)先函數(shù)比優(yōu)先表節(jié)省空間（N2 = 2*N） 運算方便，優(yōu)先關(guān)系比較 = 自然數(shù)比較,,a a f(a)=g(a) b a f(b)=g(a) a . b f(a)g(b) b b f(b)=g(b) ,f(a) g(b) f(b) g(a) f(a) 即：f(a)f(a) 矛盾 ,2. 優(yōu)先函數(shù)優(yōu)點,3. 優(yōu)先函數(shù)缺點, 優(yōu)先關(guān)系與優(yōu)先函數(shù)不是一一對應(yīng)關(guān)系。 （算符優(yōu)先文法，但不存在優(yōu)先函數(shù)）,, 信息

16、的丟失：兩個終結(jié)符號之間可能存在4種關(guān)系 (大于，小于，等于，無關(guān)），引入優(yōu)先函數(shù)后，只 有3種關(guān)系（大于，小于，等于）。使得原來不存在 優(yōu)先關(guān)系的兩個終結(jié)符，由于與自然數(shù)對應(yīng)，變得可 比較了。當(dāng)發(fā)生錯誤時不能準(zhǔn)確指出錯誤位置。,,用優(yōu)先關(guān)系： 兩個相鄰i沒有優(yōu)先關(guān)系，報錯。,,用優(yōu)先函數(shù)： f(i)=8,g(i)=7,相當(dāng)于i.i 歸約成 NN 時才發(fā)現(xiàn)錯誤。,例：i i, 結(jié)點： fa ， ga ， aVT ， 共有2n個結(jié)點。 如果a . b 或 a b，則畫從fa 到gb 的有向邊； 如果a <. b 或 a b，則畫從gb 到fa 的有向邊； f(a) = 從fa出發(fā)沿弧可到達(dá)的不重

17、復(fù)結(jié)點個數(shù) （包括自己）。 g(a) = 從ga出發(fā)沿弧可到達(dá)的不重復(fù)結(jié)點個數(shù) （包括自己）。 檢查構(gòu)造出的函數(shù)，與原來的優(yōu)先關(guān)系是否矛盾， 若不矛盾，就是所需的優(yōu)先函數(shù)； 若矛盾，不存在優(yōu)先函數(shù)。,4. 構(gòu)造優(yōu)先函數(shù) 作圖法,,例：表達(dá)式文法，取子集：VT=, i , # ,f+可達(dá)結(jié)點=f+ , g+ , f# , g# fi可達(dá)結(jié)點=fi , g+ , f# , g# f#可達(dá)結(jié)點=f# , g# g+可達(dá)結(jié)點=g+ , f# , g# gi可達(dá)結(jié)點=gi , f+ , g+ , f# , g# g#可達(dá)結(jié)點=g# , f#,,優(yōu)先函數(shù)存在， 本組函數(shù)可行。,可選函數(shù)組2：,驗

18、證：,作業(yè)： P133 第 3 題 說明：為簡單起見，不加#號,,LR分析器 = 總控程序（對所有的LR分析器，相同） + 分析表（ACTION表 + GOTO表） + 分析棧 （狀態(tài)棧 + 符號棧）,輸入串：a+b#,輸出,5.4 LR分析法介紹,不同文法、不同LR分析器，分析表不同, 動作部分ACTION 二維數(shù)組 ACTIONS,y當(dāng)狀態(tài)為S，向前看符號串y時，應(yīng)該 采取的動作。( y的長度 = 1 或 k ) si：將狀態(tài) i 以及當(dāng)前符號分別移入狀態(tài)棧、符號棧； rj：按照第 j 個產(chǎn)生式，對棧頂?shù)姆柎M(jìn)行歸約； Acc：接受輸入符號串，識別出是一個句子； 報錯：輸

19、入符號串不是句子； 狀態(tài)轉(zhuǎn)換部分GOTO 二維數(shù)組 GOTOS,P 當(dāng)前狀態(tài)S,面對非終結(jié)符號P時,轉(zhuǎn)換 到的下一個狀態(tài)。,LR分析表,,書 P101, LR分析表,GE： 1.EE+T 2.ET 3.TT*F 4.TF 5.F(E) 6.F i,,Si:移入 i=狀態(tài)棧 a=符號棧 輸入前移,0 =狀態(tài)棧，# =符號棧,LR分析器 標(biāo)準(zhǔn)分析算法,開始,S棧頂狀態(tài)號；a 輸入符號,執(zhí)行ACTIONS,a,Accept 分析 成功,空白 出錯,rj : 按第j條產(chǎn)生式歸約 L=候選式長度; P=左部符號 狀態(tài)棧彈出L個狀態(tài)； 符號棧彈出L個符號； Go新棧頂,P=狀態(tài)棧； P=符號棧,結(jié)束

20、,,GE： 1.EE+T 2.ET 3.TT*F 4.TF 5.F(E) 6.F i,,LR分析表,例：i*i+i,最右推導(dǎo)：E=E+T=E+F=E+i=T+i=T*F+i=T*i+i=F*i+i=i*i+i,LR分析法 優(yōu)點,LR分析法 缺點,1)、手工實現(xiàn)工作量大 2)、分析表占用空間大,1)、適用于大多數(shù)上下文無關(guān)文法 2)、分析效率高 3)、報錯及時 4)、可以自動生成，如：YACC,分析表種類的不同，對應(yīng)不同的LR分析器。,LR分析表種類, 字的前綴：字的任意首部。 如：abc的前綴有：，a，ab，abc。 可歸前綴：是指規(guī)范句型的一個前綴，這種前綴不 含句柄之后的任何符號

21、。 若： 是句型，為句柄，則為可歸前綴。 活前綴：可歸前綴的任意首部。 因此，只要輸入串的已掃描部分保持可規(guī)約成一個活前綴，則意味著掃描過的部分沒有錯誤。,LR(0)項目集族的構(gòu)造,,文法GS： SE EaA|bB AcA|d BcB|d 產(chǎn)生式序號 0 1 2 3 4 5 6 項目: 1. SE 2. SE （ SE ） 3. EaA 4. EaA 5. EaA （ EaA ） 6. AcA 7. AcA 8. AcA （ AcA ） 9. Ad 10. Ad （ Ad ） 11.EbB 12. EbB 13. EbB （ EbB ） 14.BcB 15. BcB 1

22、6. BcB （ BcB ） 17.Bd 18. Bd （ Bd ）, 項目：在文法G的每個產(chǎn)生式右部添加一個圓點， 就成為G的一個LR(0)項目。,根據(jù)圓點所在的位置和圓點后的符號，把項目分為四種： 移進(jìn)項目，形如 A a aVT 如：3，6，9，11 等 待約項目，形如 A B BVN 如：1，4，7，12 等 歸約項目，形如 A 如：2，5，8，10 等 接受項目，形如 SS 如：2,,項目: 1. SE 2. SE 3. EaA 4. EaA 5. EaA 6. AcA 7. AcA 8. AcA 9. Ad 10. Ad 11.EbB 12.

23、EbB 13. EbB 14.BcB 15. BcB 16. BcB 17.Bd 18. Bd, 構(gòu)造識別活前綴的NFA,1). 狀態(tài)：每一個項目對應(yīng)一個狀態(tài)； 2). 定義文法GS的拓廣文法GS，增加SS，并 令項目SS 為初態(tài)，SS 稱為接受項目； 3). 定義狀態(tài)轉(zhuǎn)換弧， 若狀態(tài)i為：XX1 Xi-1Xi Xi+1 Xn ， 狀態(tài)j為：XX1 Xi-1 XiXi+1 Xn ， 則從狀態(tài)i 畫一條標(biāo)志為Xi的有向邊到狀態(tài)j ； 若狀態(tài)i為XA ，AVN， 則從狀態(tài)i 畫一條 邊到所有狀態(tài) A 。,,識別活前綴的NFA,1.SE 2.SE 3.EaA 4.EaA 5.EaA 6.A

24、cA 7.AcA 8.AcA 9.Ad 10.Ad 11.EbB 12.EbB 13.EbB 14.BcB 15.BcB 16.BcB 17.Bd 18. Bd,狀態(tài)轉(zhuǎn)換弧 狀態(tài)i：XXi-1Xi 狀態(tài)j：XXiXi+1 從i畫標(biāo)志為Xi的有向邊到j(luò) 若狀態(tài)i為XA，AVN 從i畫邊到所有狀態(tài)A, 將NFA確定化，得到識別活前綴的DFA,,歸約項目,LR(0)分析表的構(gòu)造,假若一個文法G的拓廣文法G，識別活前綴的DFA 中，每個狀態(tài)(項目集)不存在下述情況： 1) 既含移進(jìn)項目，又含歸約項目； A a，A 移進(jìn)-歸約沖突 2) 含有多個歸約項目 A，B 歸約-歸約沖突 則稱G是一個L

25、R(0)文法。,若I是文法G的項目集，定義I的閉包CLOSURE(I)： a) I的項目都在CLOSURE(I)中b) 若A B屬于CLOSURE(I)，則每一形如B 的項目也屬于CLOSURE(I)c) 重復(fù)b)直到CLOSURE(I)不再擴(kuò)大 定義轉(zhuǎn)換函數(shù)： GO（I，X）= CLOSURE（J）其中：I為項目集，X為一文法符號 J= 任何形如AX 的項目 | A X屬于I ,分析表的ACTION和GOTO子表構(gòu)造方法： .若項目AaIk，且GO(Ik,a)Ij，aVT， 則：ACTIONk,a=“sj”。 .若項目AIk，對aVT#， ACTIONk,a=“rj” (設(shè) A 是文法

26、G的第 j 個產(chǎn)生式)。 .若項目SSIk，則：ACTIONk,#=“acc”。 .若GO(Ik,A)Ij，AVN，則：GOTOk,A=“j”。 .其他填上“報錯標(biāo)志”。,,LR(0)分析表為,產(chǎn)生式： 0.SE 1.EaA 2.EbB 3.AcA 4.Ad 5.BcB 6.Bd,在出現(xiàn)移進(jìn)-歸約沖突，或歸約-歸約沖突時，通過觀察 當(dāng)前輸入符號、非終結(jié)符的后跟符號集，來確定動作。 若LR(0)規(guī)范族中含有如下狀態(tài)： IXb，A，B， 其中，F(xiàn)OLLOW(A)FOLLOW(B)，且不包含b，,SLR(1)分析法,移進(jìn)-歸約沖突 歸約-歸約沖突,那么，當(dāng)狀態(tài)I面臨輸入符號a時， 若a=b，則移進(jìn)；

27、 若aFOLLOW(A)，用產(chǎn)生式 A 進(jìn)行歸約； 若aFOLLOW(B)，用產(chǎn)生式 B 進(jìn)行歸約； 此外，報錯。,沖突性動作的這種解決辦法叫做SLR(1)解決辦法。,,該文法的LR(0)項目集規(guī)范族為：,I0: SE EE+T ET TT*F TT*F TF F (E) Fi,I1: SE EE+T,I2: ET TT*F,I3: TF,I4: F(E) EE+T ET TT*F TF F (E) Fi,I5 : Fi,I6: EE+T TT*F TF F(E) Fi,I7: TT*F F(E) Fi,I8: F(E) EE+T,I9: EE+T

28、 TT*F,I10: TT*F,I11: F(E),例:GS (0) SE (1) EE+T (2) ET (3) TT*F (4) TF (5) F(E) (6) Fi,,I1、I2和I9都含有“移進(jìn)歸約”沖突。 FOLLOW(E) #, ), +，,I1: SE EE+T,I2: ET TT*F,I9: EE+T TT*F,,SLR分析表,I2: ET TT*F,沖突項目集:I2,FOLLOW(E) =#,),+,如果不含多重入口，則稱為：SLR分析表,規(guī)范LR分析法,定義LR(k)項目，每個項目都附帶有k個終結(jié)符， 一般形式： A , a1a2ak ， 或 A，a1a2ak 其中

29、：a1a2ak 稱為向前搜索符串。 含義：當(dāng)項目所屬的狀態(tài)出現(xiàn)在棧頂，且后續(xù)的k個輸入 符號為 a1a2ak 時，才將棧頂?shù)?歸約為A。 說明： 向前搜索符串僅對歸約項目A，a1a2ak有效。 一般只考慮k=1的情形，向前搜索(展望)一個符號， 就可以確定“移進(jìn)”或“歸約”。,,LR(1)的項目集C和函數(shù)GO,I0: SS, # SBB, # BaB, a/b B b, a/b,,S,I1: SS , #,,B,I2: SB B, # BaB, # B b, #,,a,I3: BaB, a/b BaB, a/b B b, a/b,,b,I4: B b , a/b,,B,I5: SBB, #,,a,I6: BaB, # BaB, # B b, #,,b,I7: B b , #,,B,I8: B aB, a/b,,a,,b,,a,I9: B aB, #,,B,b,,例：GS：(0) SS (1) SBB (2) BaB (3) Bb,,LR(1)分析表:,GS：(0) SS (1) SBB (2) BaB (3) Bb,