編譯原理：第五章語法分析2

1、 1. 什麼是LL(1)分析法？ 5.3.1 LL(1)分析法基本概念 5.3 LL(1)分析法 LL(1) 分析法的基本要點有三： 利用一個分析表，登記如何選擇產(chǎn)生式的知識； 利用一個分析棧，記錄分析過程； 此分析法要求文法必須是 LL(1)文法。 LL(1)分析法是指從左到右掃描、最左推導(dǎo)(LL)和只查看一個當(dāng)前符號（括號中的 1）之意； LL(1)分析法又稱預(yù)測分析法，與遞歸子程序法同屬于自頂向下確定性語法分析方法; 2. LL(1)分析過程示例 G(Z)：Z-dAZ | bAc A-aA | 棧 當(dāng)前符號 剩余序列 棧操作 選擇推導(dǎo)產(chǎn)生式后，為什麼要逆序壓棧? 當(dāng)棧頂為A,當(dāng)前單詞為c

2、時，為什么選擇 A ?討論逆序壓棧# c A# c# c A# c# c A b A aba c # 選擇 ZbAcba c #匹配 bac # 選擇AaAac #匹配 a c# 選擇A c#匹配 c#正確結(jié)束 Z查分析表 對符號串： = bac # 的分析過程： d A Z # c b a分析表： 設(shè)有文法G(Z), # 棧底標(biāo)記和結(jié)束標(biāo)記;#棧結(jié)束： 若 棧頂符=a 且 當(dāng)前符為a； 則 pop,NEXT(w);# Z 開始：棧 ; NEXT(w)；當(dāng)前符 w= # 重復(fù)執(zhí)行 、 ，直到棧中只剩 # 為止： 即：棧調(diào)整：# a# 即：棧調(diào)整：# A# a 3. LL(1)分析法算法概要 若

3、 棧頂符=A 且 當(dāng)前符 w=a 且 有產(chǎn)生式： Aa， 則 POP,PUSH(a)R ; 逆序壓棧! 否則，錯誤處理！5.3.2 LL(1)文法及其判定1. 首符號集合、后繼符集合與選擇符集合 設(shè) G(Z)=(VN, VT, Z, P)，A- P，則 first() , first()follow(A), select(A-)=*【注】 (可空), (不可空)； 若 = 則 first()= ； 設(shè) #為輸入串的結(jié)束符，則 #follow(Z); =*first()= t| t，tVT =*follow(A)= t| Z At，tVT =*【注】 求 follow(A) 要點： 查所有右部含

4、有A的產(chǎn)生式: B - A 若 不空時 , 則 first()follow(A) ； 若 取空時 , 則 follow(B)follow(A) ； 若 = 時 , 則 follow(B)follow(A)。select()= first(dAZ)=d select()= first(bcA)=bselect()= first(aA)=a select()= first()follow(A)= b,d，# 即： B - AG(Z)： Z - dAZ | bcA A - aA | 【例5.4】 求文法產(chǎn)生式的選擇集合:則有： 產(chǎn)生式序號 【定義】 LL(1)文法是指文法中，具有相同左部的各產(chǎn)生式，

5、其選擇集合不相交。 select()= d ；2. LL(1)文法及其判定 LL(1)文法可確保 遞歸子程序法 和 LL(1)分析法 的正確運用?！纠?.5】 G(Z)： Z - dAZ | bcA A - aA | select()= bselect()= a ；即： db= 又 ab,d,#= select()= b,d，# G(Z) 是 LL(1)文法。 LL(1)分析法示例：【例5.6】 G(Z)：Z - Z b | a 【注】上述文法可進(jìn)行等價變換，消除左遞歸得： select()= a select()= a 選擇集合相交 具有左遞歸的文法，一定不是LL(1)文法！ G(Z)是LL

6、(1)文法，可以用 LL(1)分析法。 select()= b select()= # 選擇集合不相交G(Z)： Z - aA , A - bA | 列： 終結(jié)符 | #5.3.3 LL(1)分析器設(shè)計(實現(xiàn)) 應(yīng)用時，可用下列函數(shù)查表，獲取相應(yīng)產(chǎn)生式： L(棧頂符，當(dāng)前符）= 產(chǎn)生式序號【結(jié)構(gòu)設(shè)計】. LL(1)分析表的構(gòu)造: LL(1)控制程序+LL(1)分析表LL(1)分析表是存儲文法選擇集合的知識表。 行： 非終結(jié)符表項：產(chǎn)生式序號 Z # a A d A Z # c b a如 G(Z)：Z - aAb | AcA select()=a; 【算法設(shè)計】 A - dA | i則 L( A

7、 , a ):=A - i 求文法選擇集合，確認(rèn) LL(1)文法； 依次取產(chǎn)生式：select()=d;select()=c,d ; select()= b,c,#;是 LL(1)文法,LL(1)分析表：不相交不相交若 a select( ) i NEXT(w)ynerrnynnerr PUSH(#),PUSH(Z) POP(x)y開始結(jié)束xVTnerryxVNw = #x = wy查LL(1)分析表: L( x ,w )= ? 空？. LL(1)分析法控制程序：PUSH ( iR ）把產(chǎn)生式 i 右部逆序壓棧把棧頂符彈入到變量x中! LL(1)分析法綜合示例：【例5.7】 G(E)： E -

8、 T | E 1 T T - F | T 2 F F - i | ( E ) 此文法含左遞歸，不是LL(1)文法;經(jīng)文法變換（消除左遞歸）后可得：G(E): E - T E E- 1 T E | T - F T T- 2 F T | F - i | ( E ) 其中： 1( + ,- ) , 2 ( * ,/ ) 這是LL(1)文法嗎?select()=first(TE)= i,( 1.求G(E) 的選擇集合： 三對選擇集合兩兩不相交，G(E): E - T E E- 1 T E | T - F T T- 2 F T | F - i | ( E ) E -E-T -T-F -select()=

9、first(1TE)= 1 select()=follow(E)= ),# select()=first(FT)= i,( select()=first(2FT)= 2 select()=follow(T)= 1 ,),# select()=first(i)= i select()=first(E)= ( G(E)是 LL(1) 文法。(接上頁) 2.構(gòu)造 LL(1) 分析表： 花括號內(nèi)是求得的選擇集合！ F T T E E ) ( # 2 1 iT- 2 FT 2 | 1,),# F - i i | (E) ( E - TE i,( E- 1 TE 1| ),# T - FT i,( G(E

10、):(接上頁) 符號串 a+b# 的LL(1)分析過程：查分析表： 操 作剩余序列 w x 分析棧# ( + 匹配成功 ) b # + 1# E T 1 : PUSH(ET1) b # + E# E : PUSH ( ) + b # + T# E T : PUSH(i) + b # a F T F ( a 匹配成功 ) + b # a i i : PUSH(TF) + b # a T E T ：PUSH(ET) a + b # a E# E : PUSH(TF) b # b T# E T ok # # : PUSH ( ) # # T # E T : PUSH ( ) # E# E ( b 匹配成功) # b i i : PUSH（i） # b F T F# E# E T# E # E T練習(xí)題：【