第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í) 重重 點(diǎn)點(diǎn) nFIRST集合和集合和FOLLOW集合的求法集合的求法n遞歸子程序的構(gòu)造方法遞歸子程序的構(gòu)造方法 nLL(1)文法及其分析表的構(gòu)造方法文法及其分析表的構(gòu)造方法 第四章第四章

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

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

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

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

6、號(hào)的FIRST集合構(gòu)造方法集合構(gòu)造方法： 對(duì)于文法中的對(duì)于文法中的符號(hào)符號(hào)XV，其，其FIRST(X)集合可反復(fù)集合可反復(fù)應(yīng)用下列規(guī)則計(jì)算，直到其應(yīng)用下列規(guī)則計(jì)算，直到其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)中的一切非中的一切非符號(hào)加進(jìn)符號(hào)加進(jìn)FIRST(X)；對(duì)于；對(duì)于一切一切2ik

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

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

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é)符號(hào)以及終結(jié)符號(hào)以及各各產(chǎn)生式右部產(chǎn)生式右部符號(hào)符號(hào)串的串的FIRST集。集。解：該文法的非終結(jié)符號(hào)有解：該文法的非終結(jié)符號(hào)有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| 求此文法的求此文法的每一個(gè)非終結(jié)符每一個(gè)非終結(jié)符號(hào)的號(hào)的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| 求此文法的求此文法的每一個(gè)非終結(jié)符每一個(gè)非終結(jié)符號(hào)的號(hào)的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是文法的開始符號(hào)，對(duì)于是文法的開始符號(hào)，對(duì)于G的任何非的任何非終結(jié)符號(hào)終結(jié)符號(hào)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é)符號(hào)或終結(jié)符號(hào)或#。注意：在。注意：在FOLLOW集合中無集合中無。 4.2 FIRST集合和集合和FOLLOW集合集合n對(duì)于文法中的符號(hào)對(duì)于文法中的符號(hào)AVn，其，其FOLLOW(A)集合集合可反復(fù)應(yīng)用

14、下列規(guī)則計(jì)算，直到其可反復(fù)應(yīng)用下列規(guī)則計(jì)算，直到其FOLLOW(A)集集合不再增大為止：合不再增大為止：1) 對(duì)于文法的對(duì)于文法的開始符號(hào)開始符號(hào)S，令，令#FOLLOW(S)2) 若若G中有形如中有形如BA 的產(chǎn)生式，且的產(chǎn)生式，且 ，則，則將將FIRST()中的一切非中的一切非符號(hào)加進(jìn)符號(hào)加進(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、一個(gè)非終結(jié)符號(hào)的求此文法的每一個(gè)非終結(jié)符號(hào)的FOLLOW集。集。解：解：1. 因?yàn)橐驗(yàn)镾為文法的開始符號(hào)，所以為文法的開始符號(hào)，所以#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é)符號(hào)的符號(hào)的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)左遞歸時(shí)（存在非終結(jié)符號(hào)當(dāng)文法中出現(xiàn)左遞歸時(shí)（存在非終結(jié)符號(hào)U，對(duì)于它有對(duì)于它有U:=U（直接左遞歸），或（直接左遞歸），或U U（間（間接左遞歸），它會(huì)使分析過程陷入無限循環(huán)。接左遞歸），它會(huì)使分析過程陷入無限循環(huán)。 n (2)回溯問題回溯問題 如果對(duì)于同一個(gè)非終結(jié)

18、符號(hào)，存在若干個(gè)產(chǎn)生如果對(duì)于同一個(gè)非終結(jié)符號(hào)，存在若干個(gè)產(chǎn)生式右部式右部(如如U:=x1|x2|xn)時(shí)，要對(duì)時(shí)，要對(duì)U展開，那么按展開，那么按哪一個(gè)產(chǎn)生式右部展開呢？即如何確定替換哪一個(gè)產(chǎn)生式右部展開呢？即如何確定替換U的的xi。如果選擇錯(cuò)誤，將導(dǎo)致回溯。如果選擇錯(cuò)誤，將導(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é)符號(hào)：引進(jìn)新的非終結(jié)符號(hào) 設(shè)有文法產(chǎn)生式設(shè)有文法產(chǎn)生式 U:= Ux1|Ux2|Uxm|y1|y2|yn其中，其中，yi(i=1,2,n)均不以符號(hào)均不以符號(hào)U為首，引進(jìn)一個(gè)新的非為首，引進(jìn)一個(gè)新的非終結(jié)符號(hào)終結(jié)符號(hào)U, 將上述產(chǎn)生式等價(jià)變換為將上述產(chǎn)生式等價(jià)變換為: 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è)計(jì)遞歸分析程序。，為其設(shè)計(jì)遞歸分析程序。方法方法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é)符號(hào)：引進(jìn)新的非終結(jié)符號(hào)E:=E+T|E-T|T 可改成可改成 E:=TE，E:=+TE|-TE|T:=T*F|T/F|F 可改成可改成 T:=FT，T:=*FT|/FT| 解：先消除文法中的直接左遞歸。解：先消除文法中的直接左遞歸。自頂向下語法分析問題的解決方法自頂向下語法分析問題的解決方法n (2)避免回溯避免回溯 為了避免回溯，對(duì)于文法中的為了避免回溯

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

22、導(dǎo)句采用自頂向下的語法分析時(shí)會(huì)引起回溯，例如推導(dǎo)句子子ac將導(dǎo)致回溯。將導(dǎo)致回溯。自頂向下語法分析問題的解決方法自頂向下語法分析問題的解決方法n (2)避免回溯避免回溯 如果如果xj ，則有可能選擇此，則有可能選擇此xj來替換來替換U,而讓句型而讓句型中中U后面的第一個(gè)終結(jié)符號(hào)與當(dāng)前輸入符號(hào)匹配，這樣后面的第一個(gè)終結(jié)符號(hào)與當(dāng)前輸入符號(hào)匹配，這樣有可能回溯。若規(guī)定文法不含有可能回溯。若規(guī)定文法不含規(guī)則規(guī)則 ，則對(duì)文法的要求，則對(duì)文法的要求太高，因此用太高，因此用 FIRST(xi)FOLLOW(U)= 來限制文法，保證只會(huì)選擇惟一的一個(gè)來限制文法，保證只會(huì)選擇惟一的一個(gè)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采用自頂向下的語法分析時(shí)會(huì)引起回溯，例如推導(dǎo)句子采用自頂向下的語法分析時(shí)會(huì)引起回溯，例如推導(dǎo)句子baa將導(dǎo)致回溯。將導(dǎo)致回溯。 SB(1 )(2 )bAaCcSBbAaBaB 自頂向下語法分析問題的解決方法自頂向下語法分析問題的解決方法n (2)避免回溯避免回溯以上避免回溯的兩個(gè)條件等價(jià)于：以上避免回溯的兩個(gè)條件等價(jià)于： 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é)符號(hào)引進(jìn)新的非終結(jié)符號(hào)V，U:= xy|xz可改寫為：可改寫為：U:=xV，V:=y|z。 根據(jù)文法的具體情況進(jìn)行等價(jià)變換。根據(jù)文法的具體情況進(jìn)行等價(jià)變換。采用自頂向下語法分析法對(duì)文法的要求采用自頂向下語法分析法對(duì)文法的要求n 采用自頂向下語法分析法要求文法滿

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

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

27、分析動(dòng)作存在不確定性。這與分析動(dòng)作存在不確定性。這與LL(1)的性質(zhì)的性質(zhì)相矛盾。所以，文法相矛盾。所以，文法G不是不是LL(1)文法。文法。采用自頂向下語法分析法對(duì)文法的要求采用自頂向下語法分析法對(duì)文法的要求n 例例 驗(yàn)證下列文法是否為驗(yàn)證下列文法是否為L(zhǎng)L(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)文法。文法。采用自頂向下語法分析法對(duì)文法的要求采用自頂向下語法分析法對(duì)文法的要求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ǎn)單：其思路極為簡(jiǎn)單：為每個(gè)非終結(jié)符號(hào)構(gòu)造一個(gè)子程為每個(gè)非終結(jié)符號(hào)構(gòu)造一個(gè)子程序，以

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

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

31、則的識(shí)別。識(shí)別。 對(duì)于規(guī)則對(duì)于規(guī)則Z:=(U)|aUb，右部有兩個(gè)候選式，因此，右部有兩個(gè)候選式，因此，U的識(shí)別過程有兩個(gè)分支，分別的識(shí)別過程有兩個(gè)分支，分別根據(jù)符號(hào)根據(jù)符號(hào)(和和a來判別。來判別。 同理對(duì)規(guī)則同理對(duì)規(guī)則U:=dZ|e設(shè)計(jì)設(shè)計(jì)的過程也分為兩個(gè)分支。的過程也分為兩個(gè)分支。Z:=(U)|aUb非終結(jié)符號(hào)非終結(jié)符號(hào)Z的分析程序的分析程序 U:=dZ|e非終結(jié)符號(hào)非終結(jié)符號(hào)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)造遞歸下降分析子程序。分析子程序。并對(duì)輸入串并對(duì)輸入串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è)計(jì)遞歸分析程序。，為其設(shè)計(jì)遞歸分析程序。解：先消除文法中的直接左遞歸：解：先消除文法中的直接左遞歸： 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è)計(jì)。括起來的內(nèi)容采用循環(huán)設(shè)計(jì)。 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)缺點(diǎn)遞歸子程序分析法的優(yōu)缺點(diǎn)主要優(yōu)點(diǎn)主要優(yōu)點(diǎn)：可以根據(jù)文法規(guī)則直接寫出相應(yīng)的可以根據(jù)文法規(guī)則直接寫出相應(yīng)的識(shí)別程序，各子程序的流程圖幾乎就是文法規(guī)則識(shí)別程序，各子程序的流程圖幾乎就是文法規(guī)則的圖解描述，簡(jiǎn)單明了，易于掌握。的圖解描述，簡(jiǎn)單明了，易于掌握。主要缺點(diǎn)主要缺點(diǎn)：大量的相互

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

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

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

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

40、析開始時(shí)狀況分析開始時(shí)狀況 p2) 假設(shè)分析的某一步，分析棧及余留的符號(hào)串，則根據(jù)假設(shè)分析的某一步，分析棧及余留的符號(hào)串，則根據(jù)棧頂?shù)姆?hào)棧頂?shù)姆?hào)Xm，采取下列動(dòng)作：，采取下列動(dòng)作： 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為空或?yàn)榭栈駿RROR，則出錯(cuò)。，則出錯(cuò)。 aiai+1 an#XmUVW(2)若若Xm=ai#，表示棧頂與掃描的符號(hào)匹配，則查分析，表示棧頂與掃描的符號(hào)匹配，則查分析表為表為POP，NEXTSYM，則棧頂符號(hào)，則棧頂符號(hào)Xm出棧，輸入指針出棧，輸入指針指向下一個(gè)符號(hào)。指向下一個(gè)符號(hào)。( 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：將括將括號(hào)內(nèi)的符號(hào)串號(hào)內(nèi)的符號(hào)串壓入棧。壓入棧。NEXTSYM：將讀：將讀符號(hào)指針指向下符號(hào)指針指向下一個(gè)符號(hào)。一個(gè)符號(hào)。ACCEPT：分析成功分析成功分析表的動(dòng)作含義：分析表的動(dòng)作含義：n例例4-7(P73) 根據(jù)表根據(jù)表4-1，對(duì)符號(hào)串對(duì)符號(hào)串i+i*i進(jìn)行分析。進(jìn)行分析。符號(hào)串符號(hào)串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對(duì)文法對(duì)文法G中的每個(gè)產(chǎn)生式中的每個(gè)產(chǎn)生式A，按下列規(guī)則確定，按下列規(guī)則確定LL(1)分析表中的元素分析表中的元素M(P74，LL(1)分析表的構(gòu)造方法分析表的構(gòu)造方法)： 1)對(duì)對(duì)FIRST()中的每個(gè)終結(jié)符中的每個(gè)終結(jié)符a（即（即 不是不是時(shí)）時(shí)），置，置MA,a=“POP，PUSH()”或或MA，a=“A” ，其中，其中為為的倒置。的倒置。2)若若FIRST()（即（即A），則對(duì)屬于，則對(duì)屬于FOLLOW(A)的每個(gè)符號(hào)的每個(gè)符號(hào)b(b為終結(jié)符或?yàn)榻K結(jié)符或#)，置，置MA,b=“POP”或或MA,b=“A” 。3)把把M中的所有中的所有Ma,a置為置為“P

44、OP，NEXTSYM”， aVt ，置，置M#,#=“ ACCEPT”。（該項(xiàng)可以不要）（該項(xiàng)可以不要）4)把把M中所有不按上述規(guī)則定義的元素均置為空或中所有不按上述規(guī)則定義的元素均置為空或“ERROR”。 4.4 LL(1)分析方法分析方法n例例有文法有文法ETE，E+TE，E，TFT，T*FT，T，F(xiàn)(E)|i 對(duì)規(guī)則對(duì)規(guī)則ETE ：FIRST(TE)= (，i)，那么在分析，那么在分析表的符號(hào)表的符號(hào)E所在的行、符號(hào)所在的行、符號(hào)(和和i所在的列對(duì)應(yīng)的位置分別所在的列對(duì)應(yīng)的位置分別填入填入“POP,PUSH(ET)”，見表，見表4-1的的E行。行。 對(duì)規(guī)則對(duì)規(guī)則E+TE：FIRST(+T

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

46、壓棧的最后一個(gè)符號(hào)是終結(jié)符時(shí)，那么下一步的分當(dāng)壓棧的最后一個(gè)符號(hào)是終結(jié)符時(shí)，那么下一步的分析動(dòng)作肯定是這個(gè)終結(jié)符號(hào)出棧。析動(dòng)作肯定是這個(gè)終結(jié)符號(hào)出棧。n簡(jiǎn)化方法簡(jiǎn)化方法 如果壓棧的最后一個(gè)符號(hào)是終結(jié)符，那么，這個(gè)終結(jié)如果壓棧的最后一個(gè)符號(hào)是終結(jié)符，那么，這個(gè)終結(jié)符不入棧，并加入讀下一個(gè)符號(hào)，這樣，分析表中所有的符不入棧，并加入讀下一個(gè)符號(hào)，這樣，分析表中所有的終結(jié)符行都可以去掉。終結(jié)符行都可以去掉。刪刪 除除對(duì)表對(duì)表4-1的分析表簡(jiǎn)化后的分析表如下表所示的分析表簡(jiǎn)化后的分析表如下表所示: 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*|(，請(qǐng)構(gòu)造文法，請(qǐng)構(gòu)造文法G的的LL(1)分析表。分析表。4.4 LL(1)分析方法分析方法n練習(xí)練習(xí) 已知文法已知文法GS: S:=(S)S|(1)該文法是該文法是LL(1)文法嗎？為什么？文法嗎？為什么？(2)請(qǐng)給出該文法的請(qǐng)給出該文法的LL(1)分析表。分析表。(3)若輸入符號(hào)串是若輸入符號(hào)串是“()”，請(qǐng)給出其，請(qǐng)給出其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)請(qǐng)給出該文法的請(qǐng)給出該文法的LL(1)分析表。分析表。(3)若輸入符號(hào)串是若輸入符號(hào)串是“()”，請(qǐng)給出其，請(qǐng)給出其LL(1)語法分析語法分析過程。過程。(2) 文法文法G的的LL(1)分析表分析表()#SS:=(S)S S:=S:=