1、第四章第四章 語法分析語法分析自頂向下分析自頂向下分析(P61)(P61) n4.1 自頂向下分析方法自頂向下分析方法n4.2 FIRST集合和集合和FOLLOW集合集合n4.3 遞歸下降分析遞歸下降分析n4.4 LL(1)分析方法分析方法學學 習習 重重 點點 nFIRST集合和集合和FOLLOW集合的求法集合的求法n遞歸子程序的構造方法遞歸子程序的構造方法 nLL(1)文法及其分析表的構造方法文法及其分析表的構造方法 第四章第四章 語法分析語法分析自頂向下分析自頂向下分析 n語法語法：是指如何由語言基本符號組成程序中各個語法：是指如何由語言基本符號組成程序中各個語法成分（包括程序）的一組規(guī)

2、則。成分（包括程序）的一組規(guī)則。n 語法分析與詞法分析的區(qū)別語法分析與詞法分析的區(qū)別： 語法分析和詞法分析都是對輸入符號串的識別，語法分析和詞法分析都是對輸入符號串的識別，但詞法分析的輸入符號串是一個單詞，而語法分析但詞法分析的輸入符號串是一個單詞，而語法分析的輸入符號串是一個句子或者說是一個程序。的輸入符號串是一個句子或者說是一個程序。 n語法分析任務語法分析任務：檢查源程序語法上是否正確，并生成：檢查源程序語法上是否正確，并生成相應的內(nèi)部表示（如分析樹）供下一階段使用。相應的內(nèi)部表示（如分析樹）供下一階段使用。n例例 對于對于C程序語句程序語句“if (a10) b=5；”，詞法分析識，詞

3、法分析識別出了別出了if、(、a、等單詞符號，而語法分析則要檢查等單詞符號，而語法分析則要檢查這些單詞之間的搭配、結構是否正確，例如這些單詞之間的搭配、結構是否正確，例如if后面是否后面是否為為(，(后面是否為正確的表達式等等。后面是否為正確的表達式等等。 第四章第四章 語法分析語法分析自頂向下分析自頂向下分析 n語法分析方法的分類語法分析方法的分類（分類標準是按照識別句（分類標準是按照識別句子時建立語法樹的方法）：子時建立語法樹的方法）： 回溯示例回溯示例分析法分析法分析法分析法分析法算符優(yōu)先分析法簡單優(yōu)先分析法優(yōu)先分析法自底向上帶回溯遞歸下降分析法分析法不帶回溯自頂向下語法分析)1()1(

4、)1()0()(LALRLRSLRLRLRKLL4.1自頂向下的分析方法自頂向下的分析方法（P61P61） n自頂向下的分析方法自頂向下的分析方法就是從文法的開始符號出發(fā)，就是從文法的開始符號出發(fā)，按最左推導方式向下推導，試圖推導出要分析的輸按最左推導方式向下推導，試圖推導出要分析的輸入串。即：入串。即： 開始符號開始符號 輸入符號串輸入符號串+n自底向上的分析方法自底向上的分析方法從輸入符號串開始，按最左從輸入符號串開始，按最左歸約方式向上歸約到文法的開始符號。即：歸約方式向上歸約到文法的開始符號。即： 開始符號開始符號 輸入符號串輸入符號串 歸約歸約SaASaSbASaabASaabbaS

5、aabbaa自上而下自上而下自底向上自底向上輸入串輸入串開始符號開始符號圖示：圖示：自上而下分析與自底向上分析自上而下分析與自底向上分析4.2 FIRST集合和集合和FOLLOW集合集合（P62P62）nFIRST集合定義集合定義：假定假定是文法是文法G的任一符號串，的任一符號串，則：則： FIRST()=a | a，aVt若若 , 則規(guī)定則規(guī)定FIRST()。 *n實際上，實際上，F(xiàn)IRST()就是從就是從可能推導出的所有開可能推導出的所有開頭終結符號或頭終結符號或。n文法符號的文法符號的FIRST集合構造方法集合構造方法： 對于文法中的對于文法中的符號符號XV，其，其FIRST(X)集合可

6、反復集合可反復應用下列規(guī)則計算，直到其應用下列規(guī)則計算，直到其FIRST(X)集合不再增大為集合不再增大為止：止： 1)若若XVt，則，則FIRST(X)=X。2)若若XVn，且具有形如，且具有形如Xa的產(chǎn)生式的產(chǎn)生式(aVt)，或具，或具有形如有形如X的產(chǎn)生式，則把的產(chǎn)生式，則把a或或加進加進FIRST(X)。3)設設G中有形如中有形如XY1Y2Yk的產(chǎn)生式，若的產(chǎn)生式，若Y1Vn，則把則把FIRST(Y1)中的一切非中的一切非符號加進符號加進FIRST(X)；對于；對于一切一切2ik，若，若Y1，Y2，Yi-1均為非終結符號，且均為非終結符號，且FIRST(Yj)，1ji-1，則將，則將F

7、IRST(Yi)中的一切非中的一切非符符號加進號加進FIRST(X)；但若對一切；但若對一切1ik，均有，均有FIRST(Yi)，則將，則將符號加進符號加進FIRST(X)。 n文法符號的文法符號的FIRST集合構造方法集合構造方法： 對于文法中的對于文法中的符號符號XV，其，其FIRST(X)集合可反復集合可反復應用下列規(guī)則計算，直到其應用下列規(guī)則計算，直到其FIRST(X)集合不再增大為集合不再增大為止：止： 1)若若X為終結符為終結符，則將，則將X加入加入FIRST(X)集合中。集合中。2)若若X為非終結符為非終結符，且具有形如，且具有形如Xa的產(chǎn)生式的產(chǎn)生式(aVt)，或具有形如或具有

8、形如X的產(chǎn)生式，則把的產(chǎn)生式，則把a或或加進加進FIRST(X)。3)設設X為非終結符為非終結符且有形如且有形如XY1Y2Yk的產(chǎn)生式，若的產(chǎn)生式，若Y1Vn，則把，則把FIRST(Y1)中的一切非中的一切非符號加進符號加進FIRST(X)；對于一切對于一切2ik，若，若Y1，Y2，Yi-1均為非終結符號，且均為非終結符號，且FIRST(Yj)，1ji-1，則將，則將FIRST(Yi)中的一切非中的一切非符號加符號加進進FIRST(X)；但若對一切；但若對一切1ik，均有，均有FIRST(Yi)，則將，則將符號加進符號加進FIRST(X)。 n對于文法對于文法G的任一的任一符號串符號串=X1X

9、2Xn可按下列步可按下列步驟構造其驟構造其FIRST()集合：集合：1)置置FIRST()=;2)將將FIRST(X1)中的一切非中的一切非符號加進符號加進FIRST()；3)若若FIRST(X1)，將，將FIRST(X2)中的一切非中的一切非符符號加進號加進FIRST()；若若FIRST(X1)和和FIRST(X2)，將將FIRST(X3)中的一切非中的一切非符號加進符號加進FIRST()；其余；其余類推。類推。4)若對于一切若對于一切1in，F(xiàn)IRST(Xi)，則將，則將符號加符號加進進FIRST()。 4.2 FIRST集合和集合和FOLLOW集合集合n例例4-1(P62) 有有文法：文

10、法： ETE E+TE E TFT T*FT T F(E)|i 求文法中非求文法中非終結符號以及終結符號以及各各產(chǎn)生式右部產(chǎn)生式右部符號符號串的串的FIRST集。集。解：該文法的非終結符號有解：該文法的非終結符號有E、E、T、T和和F。FIRST(E)=FIRST(TE) =FIRST(FTE)= ( ，i FIRST(+TE)= + FIRST()=FIRST(E)=FIRST(+TE) FIRST()=+ ，F(xiàn)IRST(T)=FIRST(FT)= ( ，i FIRST(*FT)= * FIRST(T)=FIRST(*FT) FIRST()=* ，F(xiàn)IRST(E)= ( FIRST(i)=

11、i FIRST(F) =FIRST(E) FIRST(i)=( ，i4.2 FIRST集合和集合和FOLLOW集合集合n例例S:=aABbcd|A:=ASd|B:=SAh|eC|C:=Sf|Cg| 求此文法的求此文法的每一個非終結符每一個非終結符號的號的FIRST集。集。解：解：FIRST(S)=FIRST(aABbcd)FIRST() =a=a,FIRST(A)=FIRST(ASd)FIRST() =a,d=a,d, FIRST(B)=FIRST(SAh)FIRST(eC) FIRST() =a,d,he=a,d,h,e,FIRST(C)=FIRST(Sf)FIRST(Cg) FIRST()

12、 =a,fa,f,g=a,f,g,4.2 FIRST集合和集合和FOLLOW集合集合n練習練習 S:=aAcB|BdA:=AaB|cB:=bBcA|b| 求此文法的求此文法的每一個非終結符每一個非終結符號的號的FIRST集。集。解：解：FIRST(S)=FIRST(aAcB)FIRST(Bd)=ab,d=a,b,dFIRST(A)=FIRST(AaB)FIRST(c)=cc=cFIRST(B)=FIRST(bBcA)FIRST(b) FIRST()=bb=b, 4.2 FIRST集合和集合和FOLLOW集合集合nFOLLOW集合定義集合定義（P63）：）： 假定假定S是文法的開始符號，對于是文

13、法的開始符號，對于G的任何非的任何非終結符號終結符號A，則：，則： FOLLOW(A)= a | S Aa， aVt 若若S A，則規(guī)定，則規(guī)定#FOLLOW(A)。 *n從定義可看出，從定義可看出，F(xiàn)OLLOW(A)就是在所有句型就是在所有句型中出現(xiàn)在緊接中出現(xiàn)在緊接A之后的之后的終結符號或終結符號或#。注意：在。注意：在FOLLOW集合中無集合中無。 4.2 FIRST集合和集合和FOLLOW集合集合n對于文法中的符號對于文法中的符號AVn，其，其FOLLOW(A)集合集合可反復應用下列規(guī)則計算，直到其可反復應用下列規(guī)則計算，直到其FOLLOW(A)集集合不再增大為止：合不再增大為止：1)

14、 對于文法的對于文法的開始符號開始符號S，令，令#FOLLOW(S)2) 若若G中有形如中有形如AB 的產(chǎn)生式，且的產(chǎn)生式，且 ，則，則將將FIRST()中的一切非中的一切非符號加進符號加進FOLLOW(B)。3) 若若G中有形如中有形如AB或或AB 的產(chǎn)生式，且的產(chǎn)生式，且FIRST()，則，則FOLLOW(A)中的全部元素均屬中的全部元素均屬于于FOLLOW(B)，即即FOLLOW(A) FOLLOW(B) 。例例 設文法設文法GS:S:=SbA|aAA:=BcB:=Sb求此文法的每一個非終結符號的求此文法的每一個非終結符號的FOLLOW集。集。解：解：1. 因為因為S為文法的開始符號，所

15、以為文法的開始符號，所以#FOLLOW(S);由由S:=SbA，有，有FIRST(bA)=bFOLLOW(S); 由由B:=Sb，有，有FIRST(b)=bFOLLOW(S);因此，因此，F(xiàn)OLLOW(S)=b,#。2. 由由S:=SbA或或S:=aA，有，有FOLLOW(S) FOLLOW(A)。因此，。因此，F(xiàn)OLLOW(A)=b,#。3. 由由A:=Bc，有，有FIRST(c)=cFOLLOW(B)。因此，。因此，F(xiàn)OLLOW(B)=c。 4.2 FIRST集合和集合和FOLLOW集合集合n例例4-2（P63） 有有文法文法 ETE，E+TE，E，TFT， T*FT，T，F(xiàn)(E)|i，求

16、各非終結，求各非終結符號的符號的FOLLOW集。集。解：解：FOLLOW(E)=#FIRST()=) ， #FOLLOW(E)= FOLLOW(E)=) ，# FOLLOW(T)= (FIRST(E)-) FOLLOW(E) FOLLOW(E)= + ， ) ， # FOLLOW(T)= FOLLOW(T)= + ， ) ， # FOLLOW(F)=(FIRST(T)-) FOLLOW(T) FOLLOW(T) = *，+，) ，# 4.2 FIRST集合和集合和FOLLOW集合集合n練習練習 已知文法已知文法GS: S:=AA:=BAA:=iBA| B:=CBB:=+CB| C:=)A*|(

17、求求FOLLOW(C)。解：解：FOLLOW(C)=(FIRST(B)-)FOLLOW(B)FOLLOW(B) =+,i,*,#自頂向下語法分析遇到的問題自頂向下語法分析遇到的問題n (1)左遞歸問題左遞歸問題 當文法中出現(xiàn)左遞歸時（存在非終結符號當文法中出現(xiàn)左遞歸時（存在非終結符號U，對于它有對于它有U:=U（直接左遞歸），或（直接左遞歸），或U U（間（間接左遞歸），它會使分析過程陷入無限循環(huán)。接左遞歸），它會使分析過程陷入無限循環(huán)。 n (2)回溯問題回溯問題 如果對于同一個非終結符號，存在若干個產(chǎn)生如果對于同一個非終結符號，存在若干個產(chǎn)生式右部式右部(如如U:=x1|x2|xn)時，要

18、對時，要對U展開，那么按展開，那么按哪一個產(chǎn)生式右部展開呢？即如何確定替換哪一個產(chǎn)生式右部展開呢？即如何確定替換U的的xi。如果選擇錯誤，將導致回溯。如果選擇錯誤，將導致回溯。+回溯示例回溯示例自頂向下語法分析問題的解決方法自頂向下語法分析問題的解決方法n (1)消除消除左遞歸左遞歸 消除直接左遞歸消除直接左遞歸方法方法1：采用擴充：采用擴充BNF范式范式 設有文法產(chǎn)生式設有文法產(chǎn)生式 U:=Ux|y 可改寫為可改寫為: U:=yx方法方法2：引進新的非終結符號：引進新的非終結符號 設有文法產(chǎn)生式設有文法產(chǎn)生式 U:= Ux1|Ux2|Uxm|y1|y2|yn其中，其中，yi(i=1,2,n)

19、均不以符號均不以符號U為首，引進一個新的非為首，引進一個新的非終結符號終結符號U, 將上述產(chǎn)生式等價變換為將上述產(chǎn)生式等價變換為: U:= y1U|y2U|ynU U:= x1U|x2U|xmU|自頂向下語法分析問題的解決方法自頂向下語法分析問題的解決方法n例例4-4(P65) 有文法：有文法：E:=E+T|E-T|T ，T:=T*F|T/F|F，為其設計遞歸分析程序。，為其設計遞歸分析程序。方法方法1：采用擴充：采用擴充BNF范式范式 E:=E+T|E-T|T 可改成可改成 E:=T+T| -T T:=T*F|T/F|F 可改成可改成 T:=F*F| /F方法方法2：引進新的非終結符號：引進

20、新的非終結符號E:=E+T|E-T|T 可改成可改成 E:=TE，E:=+TE|-TE|T:=T*F|T/F|F 可改成可改成 T:=FT，T:=*FT|/FT| 解：先消除文法中的直接左遞歸。解：先消除文法中的直接左遞歸。自頂向下語法分析問題的解決方法自頂向下語法分析問題的解決方法n (2)避免回溯避免回溯 為了避免回溯，對于文法中的為了避免回溯，對于文法中的任一非終結符號任一非終結符號U，若若U:=x1|x2|xn，要求滿足以下兩個條件，要求滿足以下兩個條件： 相對于相對于x1,x2,xn的各符號串的終結首符號集總是的各符號串的終結首符號集總是兩兩互不相交的，即兩兩互不相交的，即 FIRS

21、T(xi)FIRST(xj)= (ij) 因為每一個因為每一個xi推出的第一個終結符號均不相同，推出的第一個終結符號均不相同，它能保證只會選擇惟一的一個它能保證只會選擇惟一的一個xi來替換來替換U。n例例 設文法設文法GA：A:=aB|aC，B:=b，C:=cFIRST(aB)FIRST(aC)=aa=a 采用自頂向下的語法分析時會引起回溯，例如推導句采用自頂向下的語法分析時會引起回溯，例如推導句子子ac將導致回溯。將導致回溯。自頂向下語法分析問題的解決方法自頂向下語法分析問題的解決方法n (2)避免回溯避免回溯 如果如果xj ，則有可能選擇此，則有可能選擇此xj來替換來替換U,而讓句型而讓句

22、型中中U后面的第一個終結符號與當前輸入符號匹配，這樣后面的第一個終結符號與當前輸入符號匹配，這樣有可能回溯。若規(guī)定文法不含有可能回溯。若規(guī)定文法不含規(guī)則規(guī)則 ，則對文法的要求，則對文法的要求太高，因此用太高，因此用 FIRST(xi)FOLLOW(U)= 來限制文法，保證只會選擇惟一的一個來限制文法，保證只會選擇惟一的一個xi來替換來替換U。 *ZU xiaZU xj a (1 )(2 )n例例 設文法為：設文法為：S:=bAB，A:=aC| ，B:=aB| ,C:=cFIRST(aC)FOLLOW(A)=aa,#=a采用自頂向下的語法分析時會引起回溯，例如推導句子采用自頂向下的語法分析時會引

23、起回溯，例如推導句子baa將導致回溯。將導致回溯。 SB(1 )(2 )bAaCcSBbAaBaB 自頂向下語法分析問題的解決方法自頂向下語法分析問題的解決方法n (2)避免回溯避免回溯以上避免回溯的兩個條件等價于：以上避免回溯的兩個條件等價于： SELECT(U:=xi)SELECT(U:=xj) = (ij)其中：其中：SELECT(U:= xk)定義為：定義為：(i,j,k=1,2,n)SELECT(U:=xk)自頂向下語法分析問題的解決方法自頂向下語法分析問題的解決方法n 消除文法回溯的方法：消除文法回溯的方法： 消除文法的左遞歸；消除文法的左遞歸； 提公共因子；提公共因子； 例如例如

24、U:=xy|xz，則提公共因子，有，則提公共因子，有U:=x(y|z),再再引進新的非終結符號引進新的非終結符號V，U:= xy|xz可改寫為：可改寫為：U:=xV，V:=y|z。 根據(jù)文法的具體情況進行等價變換。根據(jù)文法的具體情況進行等價變換。采用自頂向下語法分析法對文法的要求采用自頂向下語法分析法對文法的要求n 采用自頂向下語法分析法要求文法滿足采用自頂向下語法分析法要求文法滿足壓縮、無壓縮、無左遞歸、無回溯左遞歸、無回溯這三個條件，稱滿足這三個條件這三個條件，稱滿足這三個條件的文法為的文法為LL(1)文法文法。證明：因為是左遞歸文法，所以必存在左遞歸的非證明：因為是左遞歸文法，所以必存在

25、左遞歸的非終結符終結符A及形如及形如A:=A|（可為可為 ）。由于）。由于SELECT(A:=A)SELECT(A:=) ，所以左遞，所以左遞歸文法不滿足歸文法不滿足LL(1)文法條件。文法條件。推論推論1：任何左遞歸文法均不是：任何左遞歸文法均不是LL(1)文法。文法。采用自頂向下語法分析法對文法的要求采用自頂向下語法分析法對文法的要求 推論推論2：任何：任何LL(1)文法均為無二義性文法。文法均為無二義性文法。證明：證明：LL(1)文法在分析句子過程的每一步，永遠文法在分析句子過程的每一步，永遠只有惟一的分析動作可進行?，F(xiàn)在，假設文法只有惟一的分析動作可進行?，F(xiàn)在，假設文法G是是二義性文法

26、，則存在句子二義性文法，則存在句子，它有兩棵不同的語法，它有兩棵不同的語法樹，即存在著兩個不同的最左推導。從而可知，用樹，即存在著兩個不同的最左推導。從而可知，用LL(1)方法對句子方法對句子進行分析的某步，存在兩種不同進行分析的某步，存在兩種不同的產(chǎn)生式可用于推導，且均能正確進行語法分析，的產(chǎn)生式可用于推導，且均能正確進行語法分析，即即LL(1)分析動作存在不確定性。這與分析動作存在不確定性。這與LL(1)的性質(zhì)的性質(zhì)相矛盾。所以，文法相矛盾。所以，文法G不是不是LL(1)文法。文法。采用自頂向下語法分析法對文法的要求采用自頂向下語法分析法對文法的要求n 例例 驗證下列文法是否為驗證下列文法

27、是否為LL(1)文法。文法。GS: S:=AB|CDa A:=ab|c B:=dD| C:=eC| D:=fD|f解：顯然，文法解：顯然，文法G已壓縮且無左遞已壓縮且無左遞歸。下面判斷其是否有回溯。歸。下面判斷其是否有回溯。由由D:=fD|f，有：，有：SELECT(D:=fD)SELECT(D:=f)=FIRST(fD)FIRST(f)=ff=f 該文法不是該文法不是LL(1)文法。文法。采用自頂向下語法分析法對文法的要求采用自頂向下語法分析法對文法的要求n 練習練習（見（見P77習題習題4的第的第2小題）小題） 有文法有文法GA： A:=aABe| B:=Bb|b判斷該文法是判斷該文法是L

28、L(1)文法嗎？文法嗎？ 解：解：文法中存在左遞歸文法中存在左遞歸B:=Bb該文法不是該文法不是LL(1)文法。文法。4.3 遞歸下降分析遞歸下降分析(P64)(P64)n 遞歸下降分析遞歸下降分析(或或遞歸子程序分析遞歸子程序分析)的基本方法的基本方法 其思路極為簡單：其思路極為簡單：為每個非終結符號構造一個子程為每個非終結符號構造一個子程序，以完成該非終結符號所對應的語法成分的分析和序，以完成該非終結符號所對應的語法成分的分析和識別。識別。1. 若若U的右部的右部只有一個候選式只有一個候選式，則按從左向右的順序構造，則按從左向右的順序構造U的識別過程代碼。的識別過程代碼。 （1 1）若有終

29、結符號，則判斷與輸入符號是否匹配，如果）若有終結符號，則判斷與輸入符號是否匹配，如果相同，繼續(xù)讀入下一符號，否則就意味著有語法錯誤；相同，繼續(xù)讀入下一符號，否則就意味著有語法錯誤； （2 2）若有非終結符號，則調(diào)用該符號的子程序。）若有非終結符號，則調(diào)用該符號的子程序。2. 若若U的右部的右部有多個候選式有多個候選式，則根據(jù)每個候選式的第一個符，則根據(jù)每個候選式的第一個符號確定該候選式分支。號確定該候選式分支。3. 只有輸入串的每一個符號全部匹配成功，且正確返回時，只有輸入串的每一個符號全部匹配成功，且正確返回時，該語法成分才算真正獲得識別。該語法成分才算真正獲得識別。4.3 遞歸下降分析遞歸

30、下降分析n 總控程序總控程序可描述如下：可描述如下：begin READ(ch); if P(文法的開始符號文法的開始符號) then if 當前符號當前符號=# then write(valid) else write(invalid) endif else write(invalid) endifendn 遞歸下降分析算法遞歸下降分析算法 它由一個總控程序和若干個非終結符號的分析子程序它由一個總控程序和若干個非終結符號的分析子程序P(U)構成構成。其中若有。其中若有n個非終結符號就有個非終結符號就有n個分析子程序。個分析子程序。4.3 遞歸下降分析遞歸下降分析n 對滿足條件的文法按如下方法

31、構造相應的語法分析對滿足條件的文法按如下方法構造相應的語法分析子程序：子程序： 對于產(chǎn)生式對于產(chǎn)生式U:=1|2|n, iV ，P(U)按如按如下方法構造：下方法構造：if chFIRST(1) then P(1)else if chFIRST(2) then P(2) else if chFIRST(3) then P(3) else if chFIRST(n) then P(n) else error 其中，其中，ch(課本用課本用INPUTSYM)是一個全局變量，是一個全局變量，用于存放輸入符號串的當前要處理的輸入符號用于存放輸入符號串的當前要處理的輸入符號; error是出錯處理程序；

32、是出錯處理程序；P(i)見后面的說明。見后面的說明。 對于每個非終結符號對于每個非終結符號U,編寫一個相應的子程序編寫一個相應的子程序P(U)。4.3 遞歸下降分析遞歸下降分析 對于產(chǎn)生式對于產(chǎn)生式U:=1|2|n|，P(U)按如下方法構按如下方法構造：造：if chFIRST(1) then P(1)else if chFIRST(2) then P(2) else if chFIRST(3) then P(3) else if chFIRST(n) then P(n) else if chFOLLOW(U) then return else error4.3 遞歸下降分析遞歸下降分析 對于

33、產(chǎn)生式對于產(chǎn)生式U:=12n，P(U) 按如下方法構按如下方法構造：造： begin P(1); P(2); ; P(n) endn說明說明：如果：如果iVn，則，則P(i)就代表調(diào)用處理就代表調(diào)用處理i的子程序；的子程序；如果如果iVt，則，則P(i)為形如下述語句的一段程序：為形如下述語句的一段程序： if ch=i then READ(ch) else error即如果當前文法中的符號與輸入符號匹配，則繼續(xù)讀入即如果當前文法中的符號與輸入符號匹配，則繼續(xù)讀入輸入符號串的下一個符號到輸入符號串的下一個符號到ch中，否則出錯。中，否則出錯。 n 例例 設文法設文法GS:S:=(A)|aAbA

34、:=eA|dSAA:=dA| 試構造該文試構造該文法的遞歸子程序法的遞歸子程序(或遞歸下降分析或遞歸下降分析程序程序)。解：由解：由S:=(A)|aAb,則則P(S)為：為：ch = (?R E A D (ch ) ch = a?YNP (A )ch = )?R E A D (ch )YN errorR E A D (ch )YNerrorP (A )ch = b ?R E A D (ch )YN error4.3 遞歸下降分析遞歸下降分析由由A:=eA|dSA,則則P(A)為：為：n 例例 設文法設文法GS:S:=(A)|aAbA:=eA|dSAA:=dA| 試構造該文試構造該文法的遞歸子程

35、序法的遞歸子程序(或遞歸下降分析或遞歸下降分析程序程序)。c h = e ?R E A D (c h ) c h = d ?YNR E A D (c h )YNe r r o rP (S )P (A ) )4.3 遞歸下降分析遞歸下降分析由由A:=dA| ，則則P(A)為：為：n 例例 設文法設文法GS:S:=(A)|aAbA:=eA|dSAA:=dA| 試構造該文試構造該文法的遞歸子程序法的遞歸子程序(或遞歸下降分析或遞歸下降分析程序程序)。ch=d?READ(ch) ch FOLLOW (A) )?YNYNerrorP(A) )4.3 遞歸下降分析遞歸下降分析n例例4-3(P64) 考慮文

36、法考慮文法Z:=(U)|aUb ，U:=dZ|e，為其構造遞，為其構造遞歸下降分析子程序。歸下降分析子程序。并對輸入串并對輸入串a(chǎn)ebaeb進行語進行語法分析法分析 。解：文法中有兩個非終結符號解：文法中有兩個非終結符號Z和和U，那么我們需要分別編，那么我們需要分別編兩個過程來完成兩個過程來完成Z和和U規(guī)則的規(guī)則的識別。識別。 對于規(guī)則對于規(guī)則Z:=(U)|aUb，右部有兩個候選式，因此，右部有兩個候選式，因此，U的識別過程有兩個分支，分別的識別過程有兩個分支，分別根據(jù)符號根據(jù)符號(和和a來判別。來判別。 同理對規(guī)則同理對規(guī)則U:=dZ|e設計設計的過程也分為兩個分支。的過程也分為兩個分支。Z

37、:=(U)|aUb非終結符號非終結符號Z的分析程序的分析程序 U:=dZ|e非終結符號非終結符號U的分析程序的分析程序 Z:=(U)|aUbU:=dZ|e輸入串為輸入串為aeb，分析過程為：，分析過程為： ZaUbaeb aeeb#b4.3 遞歸下降分析遞歸下降分析n例例4-3(P64) 考考慮文法慮文法Z:=(U)|aUb ，U:=dZ|e，為其，為其構造遞歸下降構造遞歸下降分析子程序。分析子程序。并對輸入串并對輸入串a(chǎn)ebaeb進行語法分析進行語法分析 ?？?控 程 序P(Z ) # validabP(U )eP(Z )abP(U )eaeb遞歸下降分析過程遞歸下降分析過程aeb的語法樹的

38、語法樹4.3 遞歸下降分析遞歸下降分析n例例4-4(P65) 有文法：有文法：E:=E+T|E-T|T ，T:=T*F|T/F|F，為其設計遞歸分析程序。，為其設計遞歸分析程序。解：先消除文法中的直接左遞歸：解：先消除文法中的直接左遞歸： E:=E+T|E-T|T 可改成可改成 E:=T+T| -T T:=T*F|T/F|F 可改成可改成 T:=F*F| /F注意注意“”和和“”括起來的內(nèi)容采用循環(huán)設計。括起來的內(nèi)容采用循環(huán)設計。 E:=T|E+T|E-T改成改成E:=T+T|-TT:=F|T*F|T/F改成改成T:=F*F| /F E的分析程序的分析程序 T的分析程序的分析程序 4.3 遞歸

39、下降分析遞歸下降分析n遞歸子程序分析法的優(yōu)缺點遞歸子程序分析法的優(yōu)缺點主要優(yōu)點主要優(yōu)點：可以根據(jù)文法規(guī)則直接寫出相應的可以根據(jù)文法規(guī)則直接寫出相應的識別程序，各子程序的流程圖幾乎就是文法規(guī)則識別程序，各子程序的流程圖幾乎就是文法規(guī)則的圖解描述，簡單明了，易于掌握。的圖解描述，簡單明了，易于掌握。主要缺點主要缺點：大量的相互嵌套的遞歸子程序的頻大量的相互嵌套的遞歸子程序的頻繁調(diào)用，使分析器的運行速度相當慢。繁調(diào)用，使分析器的運行速度相當慢。 4.4 LL(1)分析方法分析方法(P70)(P70) nLL(1)分析法的含義分析法的含義：第一個第一個L表示自左向右順序掃描輸入符號串表示自左向右順序掃

40、描輸入符號串第二個第二個L表示分析過程產(chǎn)生一個句子的最左推導表示分析過程產(chǎn)生一個句子的最左推導括號中的括號中的1表示每進行一步推導，只需要表示每進行一步推導，只需要向前查向前查看看1個輸入符號個輸入符號，便能確定當前所應選用的規(guī)則，便能確定當前所應選用的規(guī)則 nLL(k)分析法的含義分析法的含義： 兩個兩個L的含義同上，括號中的的含義同上，括號中的k表示每進行一表示每進行一步推導，步推導，需要向前查看需要向前查看k個輸入符號個輸入符號才能唯一確才能唯一確定當前應選擇的規(guī)則。定當前應選擇的規(guī)則。 4.4 LL(1)分析方法分析方法 nLL(1)分析程序的結構分析程序的結構 LL(1)分析器由一個

41、總控程序、一張分析表和分析器由一個總控程序、一張分析表和一個分析棧組成。一個分析棧組成。 4.4 LL(1)分析方法分析方法輸入符號串輸入符號串：指要分析的輸入符號串。為了分析指要分析的輸入符號串。為了分析算法的統(tǒng)一，我們需要在輸入串的末尾放置一個特算法的統(tǒng)一，我們需要在輸入串的末尾放置一個特殊符號殊符號#，這個符號不屬于終結符號集。，這個符號不屬于終結符號集。分析表分析表M：是一個二維表，可用一個二維數(shù)組是一個二維表，可用一個二維數(shù)組MA，a來表示，它概括了文法的全部信息，指出來表示，它概括了文法的全部信息，指出了分析器應采取的動作。分析表中的每一行與文法了分析器應采取的動作。分析表中的每一

42、行與文法中的一個非終結符號、終結符號或中的一個非終結符號、終結符號或#關聯(lián)，即關聯(lián)，即A可以可以是文法中的一個非終結符號、終結符號或是文法中的一個非終結符號、終結符號或#；而每；而每一列則與文法的一個終結符號或一列則與文法的一個終結符號或#關聯(lián)，即關聯(lián)，即a是文法是文法的一個終結符號或的一個終結符號或#。分析表的列數(shù)是終結符號的。分析表的列數(shù)是終結符號的個數(shù)加個數(shù)加1，行數(shù)是文法中的非終結符號和終結符號，行數(shù)是文法中的非終結符號和終結符號的數(shù)目加的數(shù)目加1。4.4 LL(1)分析方法分析方法分析棧分析棧（或（或符號棧符號棧）：用來存放一系列文法符號。）：用來存放一系列文法符號。分析開始時，先將

43、分析開始時，先將#入棧，然后再將文法的開始符入棧，然后再將文法的開始符號入棧。號入棧?？偪爻绦蚩偪爻绦颍悍治銎鲗斎氪姆治隹靠偪爻绦蛲攴治銎鲗斎氪姆治隹靠偪爻绦蛲瓿伞８鶕?jù)分析棧的棧頂符號和當前的輸入符號，總成。根據(jù)分析棧的棧頂符號和當前的輸入符號，總控程序按照分析表的指示來決定分析器的動作。工控程序按照分析表的指示來決定分析器的動作。工作過程如下：作過程如下： 輸出流輸出流：分析過程中使用的產(chǎn)生式序列。分析過程中使用的產(chǎn)生式序列。 p1) 分析開始時，首先將符號分析開始時，首先將符號#及文法的開始符號及文法的開始符號S依次置于依次置于分析棧的底部，并把各指示器調(diào)整至起始位置。然后，反復分

44、析棧的底部，并把各指示器調(diào)整至起始位置。然后，反復執(zhí)行第二步的操作。執(zhí)行第二步的操作。 輸入符號串：輸入符號串： #ana2a1分析棧：分析棧：#S 分析開始時狀況分析開始時狀況 p2) 假設分析的某一步，分析棧及余留的符號串，則根據(jù)假設分析的某一步，分析棧及余留的符號串，則根據(jù)棧頂?shù)姆枟ｍ數(shù)姆朮m，采取下列動作：，采取下列動作： aiai+1 an#X1X2Xm-1Xm 分析進行中的狀況分析進行中的狀況 4.4 LL(1)分析方法分析方法(1)若若XmVn，則查分析表的，則查分析表的Xm所在行和所在行和ai所在列，假所在列，假設設MXm,ai為為POP,PUSH（WVU），則將，則將Xm

45、出棧，并將出棧，并將WVU入棧，這意味著入棧，這意味著使用了規(guī)則使用了規(guī)則XmUVW；MXm,ai為為POP，則將，則將Xm出棧，這意味著出棧，這意味著使用了規(guī)則使用了規(guī)則Xm ；若；若MXm，ai為空或為空或ERROR，則出錯。，則出錯。 aiai+1 an#XmUVW(2)若若Xm=ai#，表示棧頂與掃描的符號匹配，則查分析，表示棧頂與掃描的符號匹配，則查分析表為表為POP，NEXTSYM，則棧頂符號，則棧頂符號Xm出棧，輸入指針出棧，輸入指針指向下一個符號。指向下一個符號。( 3 ) 若若Xm=ai= #，表示輸入串完全匹配，分析成功。，表示輸入串完全匹配，分析成功。 #X1X2Xm-1

46、WVU #X1X2Xm-1Xm #X1X2Xm-1 Xmn例例(P72) 算術表達式文法算術表達式文法ETE，E+TE，E，TFT,T*FT,T,F(E)|i，該文法的，該文法的LL(1)分析表為分析表為:nLL(1)分析表中元素的說明：分析表中元素的說明：POP為過程，功能是將棧頂元素從棧內(nèi)彈出。為過程，功能是將棧頂元素從棧內(nèi)彈出。PUSH()為過程，其中為過程，其中V+ ,功能是將功能是將壓棧。壓棧。NEXTSYM為讀符號過程，將讀符號指針指向為讀符號過程，將讀符號指針指向下一個符號。下一個符號。ACCEPT表示分析成功，輸入符號串語法正確。表示分析成功，輸入符號串語法正確。表中空白處表中

47、空白處表示錯誤入口，應該調(diào)用錯誤處理表示錯誤入口，應該調(diào)用錯誤處理程序。程序。 4.4 LL(1)分析方法分析方法n例例4-7(P73) 根據(jù)表根據(jù)表4-1，對符號串對符號串i+i*i進行分析。進行分析。符號串符號串i+i*i的分析過程的分析過程i+i*i的最左推的最左推導：導：ETEFTE iTEiEi+TEi+FTEi+iTEi+i*FTEi+i*iTE i+i*iE i+i*i 4.4 LL(1)分析方法分析方法n對文法對文法G中的每個產(chǎn)生式中的每個產(chǎn)生式A，按下列規(guī)則確定，按下列規(guī)則確定LL(1)分析表中的元素分析表中的元素M(P74，LL(1)分析表的構造方法分析表的構造方法)： 1

48、)對對FIRST()中的每個終結符中的每個終結符a（即（即 不是不是時）時），置，置MA,a=“POP，PUSH()”或或MA，a=“A” ，其中，其中為為的倒置。的倒置。2)若若FIRST()（即（即A），則對屬于，則對屬于FOLLOW(A)的每個符號的每個符號b(b為終結符或為終結符或#)，置，置MA,b=“POP”或或MA,b=“A” 。3)把把M中的所有中的所有Ma,a置為置為“POP，NEXTSYM”， aVt ，置，置M#,#=“ ACCEPT”。（該項可以不要）（該項可以不要）4)把把M中所有不按上述規(guī)則定義的元素均置為空或中所有不按上述規(guī)則定義的元素均置為空或“ERROR”。

49、4.4 LL(1)分析方法分析方法n例例有文法有文法ETE，E+TE，E，TFT，T*FT，T，F(xiàn)(E)|i 對規(guī)則對規(guī)則ETE ：FIRST(TE)= (，i，那么在分析，那么在分析表的符號表的符號E所在的行、符號所在的行、符號(和和i所在的列對應的位置分別所在的列對應的位置分別填入填入“POP,PUSH(ET)”，見表，見表4-1的的E行。行。 對規(guī)則對規(guī)則E+TE：FIRST(+TE)=+，在符號，在符號E行符行符號號+列對應的位置填入列對應的位置填入“POP,PUSH(ET+)” ，見表，見表4-1的的E行。行。 對規(guī)則對規(guī)則E：因為：因為FIRST()，F(xiàn)OLLOW(E)=)，#，所

50、以在符號，所以在符號E行符號行符號)和和#列對應的位置填入列對應的位置填入“POP”，見表見表4-1的的E行。行。 其它規(guī)則處理方法相同（略）。其它規(guī)則處理方法相同（略）。n對于一個文法，若按上述方法構造的分析表對于一個文法，若按上述方法構造的分析表M不含多重不含多重定義，則稱它是一個定義，則稱它是一個LL(1)文法文法。 4.4 LL(1)分析方法分析方法n觀察表觀察表4-1的的LL(1)分析表及表分析表及表4-2的分析過的分析過程，會發(fā)現(xiàn)當壓棧的最后一個符號是終結符程，會發(fā)現(xiàn)當壓棧的最后一個符號是終結符時，那么下一步的分析動作肯定是這個終結時，那么下一步的分析動作肯定是這個終結符號出棧，因

51、此，我們可以對分析表進行簡符號出棧，因此，我們可以對分析表進行簡化。方法是當壓棧的最后一個符號是終結符化。方法是當壓棧的最后一個符號是終結符時，那么，這個終結符不入棧，并加入讀下時，那么，這個終結符不入棧，并加入讀下一個符號，這樣，分析表中所有的終結符行一個符號，這樣，分析表中所有的終結符行都可以去掉。都可以去掉。對表對表4-1的分析表簡化后的分析表如下表所示的分析表簡化后的分析表如下表所示: E +TET *FTETEETEE E TFTTFT T T T FiF(E)n例例 有文法有文法GS: S:=A，A:=BA，A:=iBA|，B:=CB，B:=+CB|，C:=)A*|(，請構造文法，

52、請構造文法G的的LL(1)分析表。分析表。4.4 LL(1)分析方法分析方法n練習練習 已知文法已知文法GS: S:=(S)S|(1)該文法是該文法是LL(1)文法嗎？為什么？文法嗎？為什么？(2)請給出該文法的請給出該文法的LL(1)分析表。分析表。(3)若輸入符號串是若輸入符號串是“()”，請給出其，請給出其LL(1)語法分析語法分析過程。過程。解：解：(1) 顯然，文法顯然，文法G是經(jīng)壓縮、無左遞歸文法。下是經(jīng)壓縮、無左遞歸文法。下面判斷它是否有回溯。面判斷它是否有回溯。由由S:=(S)S| ，有：，有：SELECT(S:= (S)S)SELECT(S:=)=FIRST(S)S)(FIRST()FOLLOW(S)=(,),#=文