編譯原理及實現(xiàn)技術(shù)課件：第四章 語法分析-自頂向下分析方法

1、第四章 語法分析-自頂向下分析方法自頂向下分析概述三個重要的集合 遞歸下降語法分析LL(1)語法分析1 自頂向下的語法分析簡介21.1 自頂向下分析基本思想從文法開始符出發(fā)試圖推導(dǎo)出所給的終極符串。例 Gz :1Z aBd2 B d3 B c4 B bBZaBdbBc3 aBd # abcd # Match Bd # bcd # Derivation bBd # bcd # Match Bd # cd # Derivation cd # cd # Match d # d # Match # # Success自頂向下的語法分析過程【Sf,Rest,Action(D/M/S/E)】 Z # ab

2、cd # Derivation1.2 自頂向下分析實例4思考使用自頂向下方法進(jìn)行語法分析條件是？52 三個重要集合FirstFollowPredict62.1 First集的定義定義：設(shè)G=(VT，VN，S，P)是CFG, (VTVN)*，則字符串的First集：First()=aVT|* a|(* )P作用：可以根據(jù)當(dāng)前的輸入符號是屬于哪個產(chǎn)生式右部的首符集而決定選擇相應(yīng)產(chǎn)生式進(jìn)行推導(dǎo)。 7文法G3S: S aA | d A bAS | 輸入串W=abd。自頂向下的推導(dǎo)過程為: S aA abAS abS abd相應(yīng)的語法樹為：SaAbASd82.1.1 計算First(X)集對一文法符號X

3、計算First(X)若XVT,First(X)=X若XVN,First(X)=a| XaP,aVT若XVN,且有產(chǎn)生式X,則 First(X)若XVN,有產(chǎn)生式XY1Y2Yn，對于所有前k個字符Ym都滿足YmVN，(m=1,k;1k可能使用此產(chǎn)生式規(guī)則的當(dāng)前token集合不包括可包括#183 遞歸下降法(RECURSIVE-DESCENT PARSING)思想實例算法193.1 遞歸下降法思想對每個非終極符按其產(chǎn)生式結(jié)構(gòu)產(chǎn)生相應(yīng)語法分析子程序。遇到終極符執(zhí)行匹配命令(讀入下一token)；遇到非終極符則執(zhí)行調(diào)用命令；文法遞歸相應(yīng)子程序也遞歸，所以稱這種方法為遞歸子程序方法/遞歸下降法203.2

4、 遞歸下降法實例規(guī)則：Stm while Exp do Stm對應(yīng)產(chǎn)生式右部的語法分析程序部分如下： Match($while)； Exp()； Match($do)； Stm()； 21while xy do if xz then x:= x+y else x:= y Match($while); Exp( ); Match($do); Stm( )遞歸下降法實例續(xù)223.3 算法當(dāng)產(chǎn)生式形如:A1|2|n,則按下面的方法編寫子程序A： void A( ) if tokenPredict(A1) then (1) else if tokenPredict(A2) then (2) else

5、if tokenPredict(An) then (n) else err( ) 其中對i=X1X2Xn，(i)=(X1);(X2);(Xn);如果XVN，(X)= X(); 如果XVT，(X)= Match(X); /if(token=X)ReadToken();如果X= ，() = skip(空語句).23假設(shè)有文法Z a B aB b B | c則相應(yīng)的遞歸子程序可如下：void Z( ) if(token=a)Match(a); B( ); Match(a) ; else err( );void B ( )if(token=b)Match(b); B( );else if(token

6、=c) Match(c); else err( );主程序： ReadToken(); Z( );244 LL(1)分析方法概述LL(1)分析器LL驅(qū)動程序算法LL(1)算法執(zhí)行實例254.1 LL分析方法概述LL(1)是LL(k)的特例,其中的k則表示向前看k個符號。 LL(1)方法和遞歸下降法屬于同一級別的自頂向下分析法，但有一些區(qū)別。 遞歸下降法對每個非終極符產(chǎn)生子程序，而LL(1)方法則產(chǎn)生LL分析表；遞歸下降法能判斷每個產(chǎn)生式的結(jié)束，而LL(1)方法則不能；遞歸下降法分析法不用符號棧，而LL(1)方法則用符號棧。264.1.1 LL(1)分析法的適用條件對于任一非終極符A，其任意兩個

7、產(chǎn)生式A和A，都要滿足下面條件： Predict(A)Predict(A)= 滿足這一條件的文法稱為LL(1)文法?？捎肔L（1）分析法進(jìn)行語法分析。 274.1.2 實例文法GA: A a B c1B d 2| b B3輸入串：abbdc分析過程：(A,abbdc)1(aBc,abbdc) (Bc,bbdc) 3(bBc,bbdc) (Bc,bdc) 3 (bBc,bdc) (Bc,dc) 2 (dc,dc) (c,c) ( , )284.1.3 LL(1)分析的動作替換：當(dāng)X1VN時選相應(yīng)候選式去替換X1。匹配：當(dāng)X1VT時它與Y1進(jìn)行匹配，其結(jié)果可能成功，也可能失敗，如果成功則去掉X1和

8、Y1，否則報錯。接受：當(dāng)格局為（空，空）時報分析成功。報錯：出錯后，停止分析。294.2 LL(1)分析器組成LL(1)語法分析表，即LL(1)矩陣LL(1)語法分析驅(qū)動程序304.2.1 LL(1)分析表的構(gòu)造T：VN VT P Error A若tPredict(A)T(A,t)=Error否則 其中P表示所有產(chǎn)生式的集合 314.2.2 LL(1)分析的驅(qū)動器32StackInputa棧為空情形的處理X VT情形的處理X VN情形的處理XLL1分析表4.3 LL驅(qū)動算法初始化： Stack := #；Push(S)；讀下一個輸入符： Read(a)；若當(dāng)前格局是(#, # )，則成功結(jié)束；

9、否則轉(zhuǎn)下；設(shè)當(dāng)前格局為（ X., a.)，則若 XVT & X=a則Pop(1)；Read(a)；goto 3 若 XVT & Xa 則 Error； 若 XVN，則：if T(X,a)=XY1Y2 Ynthen Pop(1)；Push(Yn,.,Y1)；goto 3else Error334.4 LL分析實例文法G: 34 E T E1 E + T E2 | 3 T F T4 T * F T5 | 6 F id7 | ( E )8符號串 i + i * i # 的LL(1)分析過程：Predict(1) = first(TE) = id , ( Predict(2) = first(+TE)

10、 = + Predict(3) = follow(E) = ) , # Predict(4) = first(FT) = id , ( Predict(5) = first(*FT) = * Predict(6) = follow(T) = + , ) , # Predict(7) = first(id) = id Predict(8) = first(E) = ( 35分析棧S 輸入流T 矩陣元素 E # i + i * i # LL E ,i = 1 T E# i + i * i # LL T ,i = 4 F T E# i + i * i # LL F ,i = 7 i T E # i

11、+ i * i # Match T E# + i * i # LL T,+ = 6 E# +i * i # LL E,+ = 2 +T E# +i * i # Match T E# i * i # LL T,i =4 F T E# i * i # LL F,i = 7 i T E# i * i # Match T E# * i # LL T,* = 5 *FT E# * i # Match FT E# i # LLF,i = 7 iT E# i # Match T E# # LLT,# = 6 E# # LLE, # = 3# # ok36非LL(1)文法的處理BL語言 i j | i j 0

12、 不是LL文法條件語句的產(chǎn)生式是無法變換成LL(1)型產(chǎn)生式的。Sif id then S ELSEELSEelse S|處理方案：修改語法分析的驅(qū)動程序指定優(yōu)先級指定產(chǎn)生式規(guī)則37練習(xí)課后題1：設(shè)有如下文法GSSaABbcd1|2AASd3|4BSAh5|eC6|7CSf8|Cg9|10求每個產(chǎn)生式的Predict集該文法是否為LL(1)文法，為什么？38First集串可能推導(dǎo)出的首個終極符(可能為空串)First(S)=a,First(A)=a,dFirst(B)=a,d,h,eFirst(C)=a,f,gFirst(aABbcd)=aFirst(ASd)=a,dFirst(SAh)=a,

13、d,hFirst(eC)=eFirst(Sf)=a,fFirst(Cg)=a,f,g39Follow集非終極符后可能出現(xiàn)的首個終極符(不為空)Follow(S)=a,d,f,h,#Follow(A)=a,d,hFollow(B)=bFollow(C)=g,b40Predict集產(chǎn)生式所推導(dǎo)出的句型首個終極符(不為空)Predict(1)=aPredict(2)=a,d,f,h,#Predict(3)=a,dPredict(4)=a,d,e,hPredict(5)=a,d,hPredict(6)=ePredict(7)=bPredict(8)=a,fPredict(9)=a,f,gPredict

14、(10)=g,b(2)由于不同產(chǎn)生式規(guī)則的Predict集有交集，所以該文法不是LL(1)文法。41課后題2判斷下列文法那些是LL(1)文法S(SS|S)|S(S)S|SS(S)S|S(S|SS(S)|Predict(S(SS)=(Predict(S)=),#Predict(S)=)Predict(S)=),#Predict(S(S)S)=(Predict(S)=),#Predict(SS(S)S)=(Predict(S)=),(,#Predict(S(S)=(Predict(SS)=(Predict(S(S)=(Predict(S)=),#42課后題3已知文法GEEE+T|TTT*F|FFi

15、|(E)按遞歸下降法構(gòu)造此文法的語法分析程序步驟：判斷文法類型求Predict集文法變換消除左遞歸提取公共前綴設(shè)計程序43文法變換消除左遞歸對直接左遞歸形如：AA|消除左遞歸：AAAA|EE+T|TETEE+TE|TT*F|FTFTT*FT|44文法變換(2)提取公共前綴對于產(chǎn)生式：A1|2|n|，其中為不以開頭的字符串，引進(jìn)非終極符A，使產(chǎn)生式替換為：A A | A 1|2 | nEXPEXP+EXP|EXP*EXP|(EXP)|numberEXPEX|(EXP)|numberEX +EXP|*EXP45課后題4構(gòu)造LL(1)文法G以識別語言L，其中=0,1L=x|x為不包括兩個相鄰的1的非空串S0A1|1B2A0A3|1B4|5B0A6|7P(1)=0=P(3)=P(6)P(2)=1=P(4)P(5)=#=P(7)46SAB11000AB課后題5已知文法GAAaABe|aBBb|d求G的LL(1)等價文法GA構(gòu)造GA的LL(1)分