第4章 語法分析—自頂向下分析

1、第第4 4章章 語法分析語法分析自頂向下分析自頂向下分析 Pursue breakthroughs in your life. 追求自我的突破。追求自我的突破。第四章第四章 語法分析語法分析自頂向下分析自頂向下分析(P61)(P61) n4.1 自頂向下分析方法自頂向下分析方法n4.2 FIRST集合和集合和FOLLOW集合集合n4.3 遞歸下降分析遞歸下降分析n4.4 LL(1)分析方法分析方法學(xué)學(xué) 習(xí)習(xí) 重重 點點 nFIRST集合和集合和FOLLOW集合的求法集合的求法n遞歸子程序的構(gòu)造方法遞歸子程序的構(gòu)造方法 nLL(1)文法及其分析表的構(gòu)造方法文法及其分析表的構(gòu)造方法 第四章第四章

2、語法分析語法分析自頂向下分析自頂向下分析 n語法語法：是指如何由語言基本符號組成程序中各個語法：是指如何由語言基本符號組成程序中各個語法成分（包括程序）的一組規(guī)則。成分（包括程序）的一組規(guī)則。n 語法分析與詞法分析的區(qū)別語法分析與詞法分析的區(qū)別：（1）都是對輸入符號串的識別；）都是對輸入符號串的識別；（2）詞法分析的輸入串是一個單詞；）詞法分析的輸入串是一個單詞；（3）語法分析的輸入串是一個句子或者說是一個程序。）語法分析的輸入串是一個句子或者說是一個程序。 n語法分析任務(wù)語法分析任務(wù)：檢查源程序語法上是否正確，并生成：檢查源程序語法上是否正確，并生成相應(yīng)的內(nèi)部表示（如分析樹）供下一階段使用。

3、相應(yīng)的內(nèi)部表示（如分析樹）供下一階段使用。n例例 對于對于C程序語句程序語句“if (a10) b=5；”，（1）詞法分析：識別出了）詞法分析：識別出了if、(、a、等單詞符號；等單詞符號；（2）語法分析：檢查這些單詞之間的搭配、結(jié)構(gòu)是否正）語法分析：檢查這些單詞之間的搭配、結(jié)構(gòu)是否正確，例如確，例如if后面是否為后面是否為(，(后面是否為正確的表達(dá)式等。后面是否為正確的表達(dá)式等。 第四章第四章 語法分析語法分析自頂向下分析自頂向下分析 n語法分析方法的分類語法分析方法的分類（分類標(biāo)準(zhǔn)是按照識別句（分類標(biāo)準(zhǔn)是按照識別句子時建立語法樹的方法）：子時建立語法樹的方法）： 分析法分析法分析法分析法分

4、析法算符優(yōu)先分析法簡單優(yōu)先分析法優(yōu)先分析法自底向上帶回溯遞歸下降分析法分析法不帶回溯自頂向下語法分析)1()1()1()0()(LALRLRSLRLRLRKLL4.1自頂向下的分析方法自頂向下的分析方法（P61P61） n自頂向下的分析方法自頂向下的分析方法就是從文法的開始符號出發(fā)，就是從文法的開始符號出發(fā)，按最左推導(dǎo)方式向下推導(dǎo)，試圖推導(dǎo)出要分析的輸按最左推導(dǎo)方式向下推導(dǎo)，試圖推導(dǎo)出要分析的輸入串。即：入串。即： 開始符號開始符號 輸入符號串輸入符號串+n自底向上的分析方法自底向上的分析方法從輸入符號串開始，按最左從輸入符號串開始，按最左歸約方式向上歸約到文法的開始符號。即：歸約方式向上歸約

5、到文法的開始符號。即： 開始符號開始符號 輸入符號串輸入符號串 歸約歸約SaASaAaaSbAaaSbbaaaabbaa自上而下自上而下自底向上自底向上輸入串輸入串開始符號開始符號圖示：圖示：自上而下分析與自底向上分析自上而下分析與自底向上分析4.2 FIRST集合和集合和FOLLOW集合集合（P62P62）nFIRST集合定義集合定義：假定假定是文法是文法G的任一符號串，的任一符號串，則：則： FIRST()=a | a，aVt若若 , 則規(guī)定則規(guī)定FIRST()。 *n實際上，實際上，F(xiàn)IRST()就是從就是從可能推導(dǎo)出的所有開可能推導(dǎo)出的所有開頭終結(jié)符號或頭終結(jié)符號或。n文法符號的文法符

6、號的FIRST集合構(gòu)造方法集合構(gòu)造方法： 對于文法中的對于文法中的符號符號XV，其，其FIRST(X)集合可反復(fù)集合可反復(fù)應(yīng)用下列規(guī)則計算，直到其應(yīng)用下列規(guī)則計算，直到其FIRST(X)集合不再增大為集合不再增大為止：止： 1)若若XVt，則，則FIRST(X)=X。2)若若XVn，且具有形如，且具有形如Xa的產(chǎn)生式的產(chǎn)生式(aVt)，或具，或具有形如有形如X的產(chǎn)生式，則把的產(chǎn)生式，則把a(bǔ)或或加進(jìn)加進(jìn)FIRST(X)。3)設(shè)設(shè)G中有形如中有形如XY1Y2Yk的產(chǎn)生式，若的產(chǎn)生式，若Y1Vn，則把則把FIRST(Y1)中的一切非中的一切非符號加進(jìn)符號加進(jìn)FIRST(X)；對于；對于一切一切2ik

7、，若，若Y1，Y2，Yi-1均為非終結(jié)符號，且均為非終結(jié)符號，且FIRST(Yj)，1ji-1，則將，則將FIRST(Yi)中的一切非中的一切非符符號加進(jìn)號加進(jìn)FIRST(X)；但若對一切；但若對一切1ik，均有，均有FIRST(Yi)，則將，則將符號加進(jìn)符號加進(jìn)FIRST(X)。 n文法符號的文法符號的FIRST集合構(gòu)造方法集合構(gòu)造方法： 對于文法中的對于文法中的符號符號XV，其，其FIRST(X)集合可反復(fù)集合可反復(fù)應(yīng)用下列規(guī)則計算，直到其應(yīng)用下列規(guī)則計算，直到其FIRST(X)集合不再增大為集合不再增大為止：止： 1)若若X為終結(jié)符為終結(jié)符，則將，則將X加入加入FIRST(X)集合中。集

8、合中。2)若若X為非終結(jié)符為非終結(jié)符，且具有形如，且具有形如Xa的產(chǎn)生式的產(chǎn)生式(aVt)，或具有形如或具有形如X的產(chǎn)生式，則把的產(chǎn)生式，則把a(bǔ)或或加進(jìn)加進(jìn)FIRST(X)。3)設(shè)設(shè)X為非終結(jié)符為非終結(jié)符且有形如且有形如XY1Y2Yk的產(chǎn)生式，若的產(chǎn)生式，若Y1Vn，則把，則把FIRST(Y1)中的一切非中的一切非符號加進(jìn)符號加進(jìn)FIRST(X)；對于一切對于一切2ik，若，若Y1，Y2，Yi-1均為非終結(jié)符號，且均為非終結(jié)符號，且FIRST(Yj)，1ji-1，則將，則將FIRST(Yi)中的一切非中的一切非符號加符號加進(jìn)進(jìn)FIRST(X)；但若對一切；但若對一切1ik，均有，均有FIRST

9、(Yi)，則將，則將符號加進(jìn)符號加進(jìn)FIRST(X)。 n對于文法對于文法G的任一的任一符號串符號串=X1X2Xn可按下列步可按下列步驟構(gòu)造其驟構(gòu)造其FIRST()集合：集合：1)置置FIRST()=;2)將將FIRST(X1)中的一切非中的一切非符號加進(jìn)符號加進(jìn)FIRST()；3)若若FIRST(X1)，將，將FIRST(X2)中的一切非中的一切非符符號加進(jìn)號加進(jìn)FIRST()；若若FIRST(X1)和和FIRST(X2)，將將FIRST(X3)中的一切非中的一切非符號加進(jìn)符號加進(jìn)FIRST()；其余；其余類推。類推。4)若對于一切若對于一切1in，F(xiàn)IRST(Xi)，則將，則將符號加符號加

10、進(jìn)進(jìn)FIRST()。 4.2 FIRST集合和集合和FOLLOW集合集合n例例4-1(P62) 有有文法：文法： ETE E+TE E TFT T*FT T F(E)|i 求文法中非求文法中非終結(jié)符號以及終結(jié)符號以及各各產(chǎn)生式右部產(chǎn)生式右部符號符號串的串的FIRST集。集。解：該文法的非終結(jié)符號有解：該文法的非終結(jié)符號有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)= *

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

12、() =a,d,he=a,d,h,e,FIRST(C)=FIRST(Sf)FIRST(Cg) FIRST() =a,fa,f,g=a,f,g,4.2 FIRST集合和集合和FOLLOW集合集合n練習(xí)練習(xí) S:=aAcB|BdA:=AaB|cB:=bBcA|b| 求此文法的求此文法的每一個非終結(jié)符每一個非終結(jié)符號的號的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集合和集

13、合和FOLLOW集合集合nFOLLOW集合定義集合定義（P63）：）： 假定假定S是文法的開始符號，對于是文法的開始符號，對于G的任何非的任何非終結(jié)符號終結(jié)符號A，則：，則： FOLLOW(A)= a | S Aa， aVt 若若S A，則規(guī)定，則規(guī)定#FOLLOW(A)。 *n從定義可看出，從定義可看出，F(xiàn)OLLOW(A)就是在所有句型就是在所有句型中出現(xiàn)在緊接中出現(xiàn)在緊接A之后的之后的終結(jié)符號或終結(jié)符號或#。注意：在。注意：在FOLLOW集合中無集合中無。 4.2 FIRST集合和集合和FOLLOW集合集合n對于文法中的符號對于文法中的符號AVn，其，其FOLLOW(A)集合集合可反復(fù)應(yīng)用

14、下列規(guī)則計算，直到其可反復(fù)應(yīng)用下列規(guī)則計算，直到其FOLLOW(A)集集合不再增大為止：合不再增大為止：1) 對于文法的對于文法的開始符號開始符號S，令，令#FOLLOW(S)2) 若若G中有形如中有形如BA 的產(chǎn)生式，且的產(chǎn)生式，且 ，則，則將將FIRST()中的一切非中的一切非符號加進(jìn)符號加進(jìn)FOLLOW(A)。3) 若若G中有形如中有形如BA或或BA 的產(chǎn)生式，且的產(chǎn)生式，且FIRST()，則，則FOLLOW(B)中的全部元素均屬中的全部元素均屬于于FOLLOW(A)，即即FOLLOW(B) FOLLOW(A) 。例例 設(shè)文法設(shè)文法GS:S:=SbA|aAA:=BcB:=Sb求此文法的每

15、一個非終結(jié)符號的求此文法的每一個非終結(jié)符號的FOLLOW集。集。解：解：1. 因為因為S為文法的開始符號，所以為文法的開始符號，所以#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

16、集合集合n例例4-2（P63） 有有文法文法 ETE，E+TE，E，TFT， T*FT，T，F(xiàn)(E)|i，求各非終結(jié)，求各非終結(jié)符號的符號的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練

17、習(xí)練習(xí) 已知文法已知文法GS: S:=AA:=BAA:=iBA| B:=CBB:=+CB| C:=)A*|(求求FOLLOW(C)。解：解：FOLLOW(C)=(FIRST(B)-)FOLLOW(B)FOLLOW(B) =+,i,*,#自頂向下語法分析遇到的問題自頂向下語法分析遇到的問題n (1)左遞歸問題左遞歸問題 當(dāng)文法中出現(xiàn)左遞歸時（存在非終結(jié)符號當(dāng)文法中出現(xiàn)左遞歸時（存在非終結(jié)符號U，對于它有對于它有U:=U（直接左遞歸），或（直接左遞歸），或U U（間（間接左遞歸），它會使分析過程陷入無限循環(huán)。接左遞歸），它會使分析過程陷入無限循環(huán)。 n (2)回溯問題回溯問題 如果對于同一個非終結(jié)

18、符號，存在若干個產(chǎn)生如果對于同一個非終結(jié)符號，存在若干個產(chǎn)生式右部式右部(如如U:=x1|x2|xn)時，要對時，要對U展開，那么按展開，那么按哪一個產(chǎn)生式右部展開呢？即如何確定替換哪一個產(chǎn)生式右部展開呢？即如何確定替換U的的xi。如果選擇錯誤，將導(dǎo)致回溯。如果選擇錯誤，將導(dǎo)致回溯。+回溯示例回溯示例n例例 設(shè)文法設(shè)文法GA:A:=aB|aCB:=bC:=c推導(dǎo)句子推導(dǎo)句子ac將導(dǎo)致回溯。將導(dǎo)致回溯。AaBab AaCac 回溯示例回溯示例自頂向下語法分析問題的解決方法自頂向下語法分析問題的解決方法n (1)消除消除左遞歸左遞歸 消除直接左遞歸消除直接左遞歸方法方法1：采用擴(kuò)充：采用擴(kuò)充BNF

19、范式范式 設(shè)有文法產(chǎn)生式設(shè)有文法產(chǎn)生式 U:=Ux|y 可改寫為可改寫為: U:=yx方法方法2：引進(jìn)新的非終結(jié)符號：引進(jìn)新的非終結(jié)符號 設(shè)有文法產(chǎn)生式設(shè)有文法產(chǎn)生式 U:= Ux1|Ux2|Uxm|y1|y2|yn其中，其中，yi(i=1,2,n)均不以符號均不以符號U為首，引進(jìn)一個新的非為首，引進(jìn)一個新的非終結(jié)符號終結(jié)符號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，

20、為其設(shè)計遞歸分析程序。，為其設(shè)計遞歸分析程序。方法方法1：采用擴(kuò)充：采用擴(kuò)充BNF范式范式 E:=E+T|E-T|T 可改成可改成 E:=T+T| -T T:=T*F|T/F|F 可改成可改成 T:=F*F| /F方法方法2：引進(jìn)新的非終結(jié)符號：引進(jìn)新的非終結(jié)符號E:=E+T|E-T|T 可改成可改成 E:=TE，E:=+TE|-TE|T:=T*F|T/F|F 可改成可改成 T:=FT，T:=*FT|/FT| 解：先消除文法中的直接左遞歸。解：先消除文法中的直接左遞歸。自頂向下語法分析問題的解決方法自頂向下語法分析問題的解決方法n (2)避免回溯避免回溯 為了避免回溯，對于文法中的為了避免回溯

21、，對于文法中的任一非終結(jié)符號任一非終結(jié)符號U，若若U:=x1|x2|xn，要求滿足以下兩個條件，要求滿足以下兩個條件： 相對于相對于x1,x2,xn的各符號串的終結(jié)首符號集總是的各符號串的終結(jié)首符號集總是兩兩互不相交的，即兩兩互不相交的，即 FIRST(xi)FIRST(xj)= (ij) 因為每一個因為每一個xi推出的第一個終結(jié)符號均不相同，推出的第一個終結(jié)符號均不相同，它能保證只會選擇惟一的一個它能保證只會選擇惟一的一個xi來替換來替換U。n例例 設(shè)文法設(shè)文法GA：A:=aB|aC，B:=b，C:=cFIRST(aB)FIRST(aC)=aa=a 采用自頂向下的語法分析時會引起回溯，例如推

22、導(dǎo)句采用自頂向下的語法分析時會引起回溯，例如推導(dǎo)句子子ac將導(dǎo)致回溯。將導(dǎo)致回溯。自頂向下語法分析問題的解決方法自頂向下語法分析問題的解決方法n (2)避免回溯避免回溯 如果如果xj ，則有可能選擇此，則有可能選擇此xj來替換來替換U,而讓句型而讓句型中中U后面的第一個終結(jié)符號與當(dāng)前輸入符號匹配，這樣后面的第一個終結(jié)符號與當(dāng)前輸入符號匹配，這樣有可能回溯。若規(guī)定文法不含有可能回溯。若規(guī)定文法不含規(guī)則規(guī)則 ，則對文法的要求，則對文法的要求太高，因此用太高，因此用 FIRST(xi)FOLLOW(U)= 來限制文法，保證只會選擇惟一的一個來限制文法，保證只會選擇惟一的一個xi來替換來替換U。 *Z

23、U xiaZU xj a (1 )(2 )n例例 設(shè)文法為：設(shè)文法為：S:=bAB，A:=aC| ，B:=aB| ,C:=cFIRST(aC)FOLLOW(A)=aa,#=a采用自頂向下的語法分析時會引起回溯，例如推導(dǎo)句子采用自頂向下的語法分析時會引起回溯，例如推導(dǎo)句子baa將導(dǎo)致回溯。將導(dǎo)致回溯。 SB(1 )(2 )bAaCcSBbAaBaB 自頂向下語法分析問題的解決方法自頂向下語法分析問題的解決方法n (2)避免回溯避免回溯以上避免回溯的兩個條件等價于：以上避免回溯的兩個條件等價于： SELECT(U:=xi)SELECT(U:=xj) = (ij)其中：其中：SELECT(U:= x

24、k)定義為：定義為：(i,j,k=1,2,n)SELECT(U:=xk)自頂向下語法分析問題的解決方法自頂向下語法分析問題的解決方法n 消除文法回溯的方法：消除文法回溯的方法： 消除文法的左遞歸；消除文法的左遞歸； 提公共因子；提公共因子； 例如例如U:=xy|xz，則提公共因子，有，則提公共因子，有U:=x(y|z),再再引進(jìn)新的非終結(jié)符號引進(jìn)新的非終結(jié)符號V，U:= xy|xz可改寫為：可改寫為：U:=xV，V:=y|z。 根據(jù)文法的具體情況進(jìn)行等價變換。根據(jù)文法的具體情況進(jìn)行等價變換。采用自頂向下語法分析法對文法的要求采用自頂向下語法分析法對文法的要求n 采用自頂向下語法分析法要求文法滿

25、足采用自頂向下語法分析法要求文法滿足壓縮、無壓縮、無左遞歸、無回溯左遞歸、無回溯這三個條件，稱滿足這三個條件這三個條件，稱滿足這三個條件的文法為的文法為LL(1)文法文法。證明：因為是左遞歸文法，所以必存在左遞歸的非證明：因為是左遞歸文法，所以必存在左遞歸的非終結(jié)符終結(jié)符A及形如及形如A:=A|（可為可為 ）。由于）。由于SELECT(A:=A)SELECT(A:=) ，所以左遞，所以左遞歸文法不滿足歸文法不滿足LL(1)文法條件。文法條件。推論推論1：任何左遞歸文法均不是：任何左遞歸文法均不是LL(1)文法。文法。采用自頂向下語法分析法對文法的要求采用自頂向下語法分析法對文法的要求 推論推論

26、2：任何：任何LL(1)文法均為無二義性文法。文法均為無二義性文法。證明：證明：LL(1)文法在分析句子過程的每一步，永遠(yuǎn)文法在分析句子過程的每一步，永遠(yuǎn)只有惟一的分析動作可進(jìn)行。現(xiàn)在，假設(shè)文法只有惟一的分析動作可進(jìn)行?，F(xiàn)在，假設(shè)文法G是是二義性文法，則存在句子二義性文法，則存在句子，它有兩棵不同的語法，它有兩棵不同的語法樹，即存在著兩個不同的最左推導(dǎo)。從而可知，用樹，即存在著兩個不同的最左推導(dǎo)。從而可知，用LL(1)方法對句子方法對句子進(jìn)行分析的某步，存在兩種不同進(jìn)行分析的某步，存在兩種不同的產(chǎn)生式可用于推導(dǎo)，且均能正確進(jìn)行語法分析，的產(chǎn)生式可用于推導(dǎo)，且均能正確進(jìn)行語法分析，即即LL(1)

27、分析動作存在不確定性。這與分析動作存在不確定性。這與LL(1)的性質(zhì)的性質(zhì)相矛盾。所以，文法相矛盾。所以，文法G不是不是LL(1)文法。文法。采用自頂向下語法分析法對文法的要求采用自頂向下語法分析法對文法的要求n 例例 驗證下列文法是否為驗證下列文法是否為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

28、 該文法不是該文法不是LL(1)文法。文法。采用自頂向下語法分析法對文法的要求采用自頂向下語法分析法對文法的要求n 練習(xí)練習(xí)（見（見P77習(xí)題習(xí)題4的第的第2小題）小題） 有文法有文法GA： A:=aABe| B:=Bb|b判斷該文法是判斷該文法是LL(1)文法嗎？文法嗎？ 解：解：文法中存在左遞歸文法中存在左遞歸B:=Bb該文法不是該文法不是LL(1)文法。文法。4.3 遞歸下降分析遞歸下降分析(P64)(P64)n 遞歸下降分析遞歸下降分析(或或遞歸子程序分析遞歸子程序分析)的基本方法的基本方法 其思路極為簡單：其思路極為簡單：為每個非終結(jié)符號構(gòu)造一個子程為每個非終結(jié)符號構(gòu)造一個子程序，以

29、完成該非終結(jié)符號所對應(yīng)的語法成分的分析和序，以完成該非終結(jié)符號所對應(yīng)的語法成分的分析和識別。識別。1. 若若U的右部的右部只有一個候選式只有一個候選式，則按從左向右的順序構(gòu)造，則按從左向右的順序構(gòu)造U的識別過程代碼。的識別過程代碼。 （1 1）若有終結(jié)符號，則判斷與輸入符號是否匹配，如果）若有終結(jié)符號，則判斷與輸入符號是否匹配，如果相同，繼續(xù)讀入下一符號，否則就意味著有語法錯誤；相同，繼續(xù)讀入下一符號，否則就意味著有語法錯誤； （2 2）若有非終結(jié)符號，則調(diào)用該符號的子程序。）若有非終結(jié)符號，則調(diào)用該符號的子程序。2. 若若U的右部的右部有多個候選式有多個候選式，則根據(jù)每個候選式的第一個符，則

30、根據(jù)每個候選式的第一個符號確定該候選式分支。號確定該候選式分支。3. 只有輸入串的每一個符號全部匹配成功，且正確返回時，只有輸入串的每一個符號全部匹配成功，且正確返回時，該語法成分才算真正獲得識別。該語法成分才算真正獲得識別。4.3 遞歸下降分析遞歸下降分析n例例4-3(P64) 考慮文法考慮文法Z:=(U)|aUb ，U:=dZ|e，為其構(gòu)造遞，為其構(gòu)造遞歸下降分析子程序。歸下降分析子程序。并對輸入串并對輸入串a(chǎn)ebaeb進(jìn)行語進(jìn)行語法分析法分析 。解：文法中有兩個非終結(jié)符號解：文法中有兩個非終結(jié)符號Z和和U，那么我們需要分別編，那么我們需要分別編兩個過程來完成兩個過程來完成Z和和U規(guī)則的規(guī)

31、則的識別。識別。 對于規(guī)則對于規(guī)則Z:=(U)|aUb，右部有兩個候選式，因此，右部有兩個候選式，因此，U的識別過程有兩個分支，分別的識別過程有兩個分支，分別根據(jù)符號根據(jù)符號(和和a來判別。來判別。 同理對規(guī)則同理對規(guī)則U:=dZ|e設(shè)計設(shè)計的過程也分為兩個分支。的過程也分為兩個分支。Z:=(U)|aUb非終結(jié)符號非終結(jié)符號Z的分析程序的分析程序 U:=dZ|e非終結(jié)符號非終結(jié)符號U的分析程序的分析程序 Z:=(U)|aUbU:=dZ|e輸入串為輸入串為aeb，分析過程為：，分析過程為： ZaUbaeb aeeb#b4.3 遞歸下降分析遞歸下降分析n例例4-3(P64) 考考慮文法慮文法Z:=

32、(U)|aUb ，U:=dZ|e，為其，為其構(gòu)造遞歸下降構(gòu)造遞歸下降分析子程序。分析子程序。并對輸入串并對輸入串a(chǎn)ebaeb進(jìn)行語法分析進(jìn)行語法分析 。總 控 程 序P(Z ) # validabP(U )eP(Z )abP(U )eaeb遞歸下降分析過程遞歸下降分析過程aeb的語法樹的語法樹n 例例 設(shè)文法設(shè)文法GS:S:=(A)|aAbA:=eA|dSAA:=dA| 試構(gòu)造該文試構(gòu)造該文法的遞歸子程序法的遞歸子程序(或遞歸下降分析或遞歸下降分析程序程序)。解：由解：由S:=(A)|aAb,則則P(S)為：為：ch = (?R E A D (ch ) ch = a?YNP (A )ch =

33、)?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 例例 設(shè)文法設(shè)文法GS:S:=(A)|aAbA:=eA|dSAA:=dA| 試構(gòu)造該文試構(gòu)造該文法的遞歸子程序法的遞歸子程序(或遞歸下降分析或遞歸下降分析程序程序)。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|

34、，則則P(A)為：為：n 例例 設(shè)文法設(shè)文法GS:S:=(A)|aAbA:=eA|dSAA:=dA| 試構(gòu)造該文試構(gòu)造該文法的遞歸子程序法的遞歸子程序(或遞歸下降分析或遞歸下降分析程序程序)。ch=d?READ(ch) ch FOLLOW (A) )?YNYNerrorP(A) )4.3 遞歸下降分析遞歸下降分析n例例4-4(P65) 有文法：有文法：E:=E+T|E-T|T ，T:=T*F|T/F|F，為其設(shè)計遞歸分析程序。，為其設(shè)計遞歸分析程序。解：先消除文法中的直接左遞歸：解：先消除文法中的直接左遞歸： E:=E+T|E-T|T 可改成可改成 E:=T+T| -T T:=T*F|T/F|

35、F 可改成可改成 T:=F*F| /F注意注意“”和和“”括起來的內(nèi)容采用循環(huán)設(shè)計。括起來的內(nèi)容采用循環(huán)設(shè)計。 E:=T|E+T|E-T改成改成E:=T+T|-TT:=F|T*F|T/F改成改成T:=F*F| /F E的分析程序的分析程序 T的分析程序的分析程序 4.3 遞歸下降分析遞歸下降分析n遞歸子程序分析法的優(yōu)缺點遞歸子程序分析法的優(yōu)缺點主要優(yōu)點主要優(yōu)點：可以根據(jù)文法規(guī)則直接寫出相應(yīng)的可以根據(jù)文法規(guī)則直接寫出相應(yīng)的識別程序，各子程序的流程圖幾乎就是文法規(guī)則識別程序，各子程序的流程圖幾乎就是文法規(guī)則的圖解描述，簡單明了，易于掌握。的圖解描述，簡單明了，易于掌握。主要缺點主要缺點：大量的相互

36、嵌套的遞歸子程序的頻大量的相互嵌套的遞歸子程序的頻繁調(diào)用，使分析器的運行速度相當(dāng)慢。繁調(diào)用，使分析器的運行速度相當(dāng)慢。 4.4 LL(1)分析方法分析方法(P70)(P70) nLL(1)分析法的含義分析法的含義：第一個第一個L表示自左向右順序掃描輸入符號串表示自左向右順序掃描輸入符號串第二個第二個L表示分析過程產(chǎn)生一個句子的最左推導(dǎo)表示分析過程產(chǎn)生一個句子的最左推導(dǎo)括號中的括號中的1表示每進(jìn)行一步推導(dǎo)，只需要表示每進(jìn)行一步推導(dǎo)，只需要向前查向前查看看1個輸入符號個輸入符號，便能確定當(dāng)前所應(yīng)選用的規(guī)則，便能確定當(dāng)前所應(yīng)選用的規(guī)則 nLL(k)分析法的含義分析法的含義： 兩個兩個L的含義同上，括

37、號中的的含義同上，括號中的k表示每進(jìn)行一表示每進(jìn)行一步推導(dǎo)，步推導(dǎo)，需要向前查看需要向前查看k個輸入符號個輸入符號才能唯一確才能唯一確定當(dāng)前應(yīng)選擇的規(guī)則。定當(dāng)前應(yīng)選擇的規(guī)則。 4.4 LL(1)分析方法分析方法 nLL(1)分析程序的結(jié)構(gòu)分析程序的結(jié)構(gòu) LL(1)分析器由一個總控程序、一張分析表和一個分析棧組成。分析器由一個總控程序、一張分析表和一個分析棧組成。 是一個二維表，它概是一個二維表，它概括了文法的全部信息，括了文法的全部信息，指出了分析器應(yīng)采取指出了分析器應(yīng)采取的動作。的動作。存放一系列存放一系列文法符號。文法符號。分析開始時，分析開始時，先將先將# #入棧，入棧，然后再將文然后再

38、將文法的開始符法的開始符號入棧。號入棧。分析過程中使用分析過程中使用的產(chǎn)生式序列。的產(chǎn)生式序列。要分析的輸入符號串。串的末尾放置一個要分析的輸入符號串。串的末尾放置一個特殊符號特殊符號# #，表示結(jié)束。，表示結(jié)束。# #不是終結(jié)符號。不是終結(jié)符號。根據(jù)棧頂符根據(jù)棧頂符號和當(dāng)前的號和當(dāng)前的輸入符號，輸入符號，按照分析表按照分析表的指示來完的指示來完成分析過程。成分析過程。4.4 LL(1)分析方法分析方法分析表分析表M：是一個二維表，可用一個二維數(shù)組是一個二維表，可用一個二維數(shù)組MA，a來表示，來表示，它指出了分析器應(yīng)采取的動作。它指出了分析器應(yīng)采取的動作。分析表中的每分析表中的每一行是文法中一

39、行是文法中的一個非終結(jié)的一個非終結(jié)符號、終結(jié)符符號、終結(jié)符號或號或#；分析表每一列分析表每一列是文法的一個是文法的一個終結(jié)符號或終結(jié)符號或#。因此，分析表的列數(shù)是因此，分析表的列數(shù)是終結(jié)符號的個數(shù)加終結(jié)符號的個數(shù)加1；行數(shù)是行數(shù)是非終結(jié)符號和終結(jié)符號的數(shù)目加非終結(jié)符號和終結(jié)符號的數(shù)目加1。p1) 分析開始時，首先將符號分析開始時，首先將符號#及文法的開始符號及文法的開始符號S依次置于依次置于分析棧的底部，并把各指示器調(diào)整至起始位置。然后，反復(fù)分析棧的底部，并把各指示器調(diào)整至起始位置。然后，反復(fù)執(zhí)行第二步的操作。執(zhí)行第二步的操作。 輸入符號串：輸入符號串： #ana2a1分析棧：分析棧：#S 分

40、析開始時狀況分析開始時狀況 p2) 假設(shè)分析的某一步，分析棧及余留的符號串，則根據(jù)假設(shè)分析的某一步，分析棧及余留的符號串，則根據(jù)棧頂?shù)姆枟ｍ數(shù)姆朮m，采取下列動作：，采取下列動作： aiai+1 an#X1X2Xm-1Xm 分析進(jìn)行中的狀況分析進(jìn)行中的狀況 4.4 LL(1)分析方法分析方法-工作過程工作過程(1)若若XmVn，則查分析表的，則查分析表的Xm所在行和所在行和ai所在列，假所在列，假設(shè)設(shè)MXm,ai為為POP,PUSH（WVU），則將，則將Xm出棧，并將出棧，并將WVU入棧，這意味著入棧，這意味著使用了規(guī)則使用了規(guī)則XmUVW；MXm,ai為為POP，則將，則將Xm出棧，這意

41、味著出棧，這意味著使用了規(guī)則使用了規(guī)則Xm ；若；若MXm，ai為空或為空或ERROR，則出錯。，則出錯。 aiai+1 an#XmUVW(2)若若Xm=ai#，表示棧頂與掃描的符號匹配，則查分析，表示棧頂與掃描的符號匹配，則查分析表為表為POP，NEXTSYM，則棧頂符號，則棧頂符號Xm出棧，輸入指針出棧，輸入指針指向下一個符號。指向下一個符號。( 3 ) 若若Xm=ai= #，表示輸入串完全匹配，分析成功。，表示輸入串完全匹配，分析成功。 #X1X2Xm-1WVU #X1X2Xm-1Xm #X1X2Xm-1 Xmn例例(P72) 算術(shù)表達(dá)式文法算術(shù)表達(dá)式文法ETE，E+TE，E，TFT,T

42、*FT,T,F(E)|i，該文法的，該文法的LL(1)分析表為分析表為:POP：將棧頂元將棧頂元素從棧內(nèi)彈出。素從棧內(nèi)彈出。PUSH：將括將括號內(nèi)的符號串號內(nèi)的符號串壓入棧。壓入棧。NEXTSYM：將讀：將讀符號指針指向下符號指針指向下一個符號。一個符號。ACCEPT：分析成功分析成功分析表的動作含義：分析表的動作含義：n例例4-7(P73) 根據(jù)表根據(jù)表4-1，對符號串對符號串i+i*i進(jìn)行分析。進(jìn)行分析。符號串符號串i+i*i的分析過程的分析過程i+i*i的最左推的最左推導(dǎo)：導(dǎo)：ETEFTE iTEiEi+TEi+FTEi+iTEi+i*FTEi+i*iTE i+i*iE i+i*i 4.

43、4 LL(1)分析方法分析方法n對文法對文法G中的每個產(chǎn)生式中的每個產(chǎn)生式A，按下列規(guī)則確定，按下列規(guī)則確定LL(1)分析表中的元素分析表中的元素M(P74，LL(1)分析表的構(gòu)造方法分析表的構(gòu)造方法)： 1)對對FIRST()中的每個終結(jié)符中的每個終結(jié)符a（即（即 不是不是時）時），置，置MA,a=“POP，PUSH()”或或MA，a=“A” ，其中，其中為為的倒置。的倒置。2)若若FIRST()（即（即A），則對屬于，則對屬于FOLLOW(A)的每個符號的每個符號b(b為終結(jié)符或為終結(jié)符或#)，置，置MA,b=“POP”或或MA,b=“A” 。3)把把M中的所有中的所有Ma,a置為置為“P

44、OP，NEXTSYM”， aVt ，置，置M#,#=“ ACCEPT”。（該項可以不要）（該項可以不要）4)把把M中所有不按上述規(guī)則定義的元素均置為空或中所有不按上述規(guī)則定義的元素均置為空或“ERROR”。 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所在的列對應(yīng)的位置分別所在的列對應(yīng)的位置分別填入填入“POP,PUSH(ET)”，見表，見表4-1的的E行。行。 對規(guī)則對規(guī)則E+TE：FIRST(+T

45、E)=+，在符號，在符號E行符行符號號+列對應(yīng)的位置填入列對應(yīng)的位置填入“POP,PUSH(ET+)” ，見表，見表4-1的的E行。行。 對規(guī)則對規(guī)則E：因為：因為FIRST()，F(xiàn)OLLOW(E)=)，#，所以在符號，所以在符號E行符號行符號)和和#列對應(yīng)的位置填入列對應(yīng)的位置填入“POP”，見表見表4-1的的E行。行。 其它規(guī)則處理方法相同（略）。其它規(guī)則處理方法相同（略）。n對于一個文法，若按上述方法構(gòu)造的分析表對于一個文法，若按上述方法構(gòu)造的分析表M不含多重不含多重定義，則稱它是一個定義，則稱它是一個LL(1)文法文法。 4.4 LL(1)分析方法分析方法n分析表的簡化分析表的簡化 當(dāng)

46、壓棧的最后一個符號是終結(jié)符時，那么下一步的分當(dāng)壓棧的最后一個符號是終結(jié)符時，那么下一步的分析動作肯定是這個終結(jié)符號出棧。析動作肯定是這個終結(jié)符號出棧。n簡化方法簡化方法 如果壓棧的最后一個符號是終結(jié)符，那么，這個終結(jié)如果壓棧的最后一個符號是終結(jié)符，那么，這個終結(jié)符不入棧，并加入讀下一個符號，這樣，分析表中所有的符不入棧，并加入讀下一個符號，這樣，分析表中所有的終結(jié)符行都可以去掉。終結(jié)符行都可以去掉。刪刪 除除對表對表4-1的分析表簡化后的分析表如下表所示的分析表簡化后的分析表如下表所示: E +TET *FTETEETEE E TFTTFT T T T FiF(E)n例例 有文法有文法GS:

47、S:=A，A:=BA，A:=iBA|，B:=CB，B:=+CB|，C:=)A*|(，請構(gòu)造文法，請構(gòu)造文法G的的LL(1)分析表。分析表。4.4 LL(1)分析方法分析方法n練習(xí)練習(xí) 已知文法已知文法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)=(,),#=文法文法G是是LL(1)文法。文法。4.4 LL(1)4.4 LL(1)分析方法分析方法n練習(xí)練習(xí) 已知文法已知文法GS: S:=(S)S|(1)該文法是該文法是LL(1)文法嗎？為什么？文法嗎？為什么？(2)請給出該文法的請給出該文法的LL(1)分析表。分析表。(3)若輸入符號串是若輸入符號串是“()”，請給出其，請給出其LL(1)語法分析語法分析過程。過程。(2) 文法文法G的的LL(1)分析表分析表()#SS:=(S)S S:=S:=4.4 LL(