第4章語(yǔ)法分析-自頂向下的語(yǔ)法分析

1、編譯系統(tǒng)原編譯系統(tǒng)原 理理電氣與信息學(xué)院 王 艷4.1 4.1 自頂向下分析方法自頂向下分析方法4.2 FIRST4.2 FIRST集合和集合和FOLLOWFOLLOW集合集合4.3 4.3 遞歸下降分析遞歸下降分析4.4 LL(1)4.4 LL(1)分析方法分析方法第四章第四章 語(yǔ)法分析語(yǔ)法分析- -自頂向下分析自頂向下分析4.1 4.1 自頂向下分析方法自頂向下分析方法語(yǔ)法分析器語(yǔ)法樹(shù)4.1 4.1 自頂向下分析方法自頂向下分析方法語(yǔ)法分析的任務(wù)：語(yǔ)法分析的任務(wù)： 檢查源程序語(yǔ)法上是否正確，并生成相應(yīng)檢查源程序語(yǔ)法上是否正確，并生成相應(yīng)的內(nèi)部表示（如分析樹(shù)）供下一階段使用。的內(nèi)部表示（如分

2、析樹(shù)）供下一階段使用。結(jié)果輸出：結(jié)果輸出：分析樹(shù)：分析樹(shù)：產(chǎn)生式序列產(chǎn)生式序列出錯(cuò)處理要求出錯(cuò)處理要求l盡快發(fā)現(xiàn)錯(cuò)誤，準(zhǔn)確定位，盡快發(fā)現(xiàn)錯(cuò)誤，準(zhǔn)確定位，l可能時(shí)進(jìn)行恢復(fù)處理，繼續(xù)語(yǔ)法分析可能時(shí)進(jìn)行恢復(fù)處理，繼續(xù)語(yǔ)法分析4.1 4.1 自頂向下分析方法自頂向下分析方法常用的語(yǔ)法分析方法：常用的語(yǔ)法分析方法： 分析法分析法分析法分析法分析法算符優(yōu)先分析法簡(jiǎn)單優(yōu)先分析法優(yōu)先分析法自底向上帶回溯遞歸下降分析法分析法不帶回溯自頂向下語(yǔ)法分析)1()1()1()0()(LALRLRSLRLRLRKLL無(wú)論那種分析方法，語(yǔ)法分析都是自左至右的讀入字符無(wú)論那種分析方法，語(yǔ)法分析都是自左至右的讀入字符4.1 4

3、.1 自頂向下分析方法自頂向下分析方法n自頂向下的分析方法自頂向下的分析方法就是從文法的開(kāi)始符號(hào)出發(fā)，就是從文法的開(kāi)始符號(hào)出發(fā)，按最左推導(dǎo)方式向下推導(dǎo)，試圖推導(dǎo)出要分析的輸按最左推導(dǎo)方式向下推導(dǎo)，試圖推導(dǎo)出要分析的輸入串。即：入串。即： 開(kāi)始符號(hào)開(kāi)始符號(hào) 輸入符號(hào)串輸入符號(hào)串+n自底向上的分析方法自底向上的分析方法從輸入符號(hào)串開(kāi)始，按最左從輸入符號(hào)串開(kāi)始，按最左歸約方式向上歸約到文法的開(kāi)始符號(hào)。即：歸約方式向上歸約到文法的開(kāi)始符號(hào)。即： 開(kāi)始符號(hào)開(kāi)始符號(hào) 輸入符號(hào)串輸入符號(hào)串 歸約歸約4.1 4.1 自頂向下分析方法自頂向下分析方法上下文無(wú)關(guān)文法（上下文無(wú)關(guān)文法（2 2型文法）型文法）編程語(yǔ)言

4、的語(yǔ)法大都可用型文法來(lái)描述編程語(yǔ)言的語(yǔ)法大都可用型文法來(lái)描述 例例4.1： ETE E+TE E TFT T*FT T F(E)|i沒(méi)有一種方法能夠有效地分析所沒(méi)有一種方法能夠有效地分析所有上下文無(wú)關(guān)文法有上下文無(wú)關(guān)文法l存在無(wú)法處理的型文法存在無(wú)法處理的型文法每種方法能夠處理一部分上下文每種方法能夠處理一部分上下文無(wú)關(guān)文法無(wú)關(guān)文法l每種方法都有適用范圍每種方法都有適用范圍4.2 FIRST4.2 FIRST集合和集合和FOLLOWFOLLOW集合集合4.2.1 FIRST4.2.1 FIRST集合集合FIRST集合定義：集合定義：假定假定是文法是文法G的任一符號(hào)串，的任一符號(hào)串，則：則： F

5、IRST()=a | a，aVt若若 , 則規(guī)定則規(guī)定FIRST()。 * 實(shí)際上，實(shí)際上，F(xiàn)IRST()就是從就是從可能推導(dǎo)出的所有可能推導(dǎo)出的所有開(kāi)頭終結(jié)符號(hào)或開(kāi)頭終結(jié)符號(hào)或。4.2 FIRST4.2 FIRST集合和集合和FOLLOWFOLLOW集合集合文法符號(hào)的FIRST集合構(gòu)造方法： 對(duì)于文法中的對(duì)于文法中的符號(hào)符號(hào)X XVV，其，其FIRST(X)FIRST(X)集合可反復(fù)應(yīng)用下列規(guī)則集合可反復(fù)應(yīng)用下列規(guī)則計(jì)算，直到其計(jì)算，直到其FIRST(X)FIRST(X)集合不再增大為止：集合不再增大為止： 1)1)若若XVXVt t，則，則FIRST(X)=XFIRST(X)=X。2)2)

6、若若XVXVn n，且具有形如，且具有形如XXa a的產(chǎn)生式的產(chǎn)生式( (a aVVt t) )，或具有形如，或具有形如XX的產(chǎn)生式，則把的產(chǎn)生式，則把a(bǔ) a或或加進(jìn)加進(jìn)FIRST(X)FIRST(X)。3)3)設(shè)設(shè)G G中有形如中有形如XYXY1 1Y Y2 2YYk k的產(chǎn)生式，若的產(chǎn)生式，若Y Y1 1VVn n，則把，則把FIRST(YFIRST(Y1 1) )中的一切非中的一切非符號(hào)加進(jìn)符號(hào)加進(jìn)FIRST(X)FIRST(X)；對(duì)于一切；對(duì)于一切2ik2ik，若，若Y Y1 1，Y Y2 2，Y Yi-1i-1均為非終結(jié)符號(hào)，且均為非終結(jié)符號(hào)，且FIRST(YFIRST(Yj j)

7、)，1ji-11ji-1，則，則將將FIRST(YFIRST(Yi i) )中的一切非中的一切非符號(hào)加進(jìn)符號(hào)加進(jìn)FIRST(X)FIRST(X)；但若對(duì)一切；但若對(duì)一切1ik1ik，均有，均有FIRST(YFIRST(Yi i) )，則將，則將符號(hào)加進(jìn)符號(hào)加進(jìn)FIRST(X)FIRST(X)。 4.2 FIRST4.2 FIRST集合和集合和FOLLOWFOLLOW集合集合對(duì)于文法對(duì)于文法G G的任一的任一符號(hào)串符號(hào)串=X=X1 1X X2 2XXn n可按下列步驟構(gòu)造其可按下列步驟構(gòu)造其FIRST()FIRST()集合：集合：1)1)置置FIRST()=;FIRST()=;2)2)將將FIR

8、ST(XFIRST(X1 1) )中的一切非中的一切非符號(hào)加進(jìn)符號(hào)加進(jìn)FIRST()FIRST()；3)3)若若FIRST(XFIRST(X1 1) )，將，將FIRST(XFIRST(X2 2) )中的一切非中的一切非符號(hào)加進(jìn)符號(hào)加進(jìn)FIRST()FIRST()；若；若FIRST(XFIRST(X1 1) )和和FIRST(XFIRST(X2 2) )，將，將FIRST(XFIRST(X3 3) )中中的一切非的一切非符號(hào)加進(jìn)符號(hào)加進(jìn)FIRST()FIRST()；其余類(lèi)推。；其余類(lèi)推。4)4)若對(duì)于一切若對(duì)于一切1in1in，F(xiàn)IRST(XFIRST(Xi i) )，則將，則將符號(hào)加進(jìn)符號(hào)加

9、進(jìn)FIRST()FIRST()。 4.2 FIRST4.2 FIRST集合和集合和FOLLOWFOLLOW集合集合例例4-1 4-1 有文法：有文法： ETE E+TE E TFTETE E+TE E TFT T T* *FT T F(E)|iFT T F(E)|i求文法中非終結(jié)符號(hào)以及各產(chǎn)生式右部符號(hào)串的求文法中非終結(jié)符號(hào)以及各產(chǎn)生式右部符號(hào)串的FIRSTFIRST集。集。解：該文法的非終結(jié)符號(hào)有解：該文法的非終結(jié)符號(hào)有E、E、T、T和和F。FIRST(E)=FIRST(T) =FIRST(F) = ( ，i FIRST(E)= + ，F(xiàn)IRST(T)= * ，右部符號(hào)串的右部符號(hào)串的FIR

10、ST集：集：FIRST(TE) =FIRST(T)=FIRST(F) = ( ，i FIRST(+TE)= + FIRST()=FIRST(FT)=FIRST(F) = ( ，i FIRST(*FT)= * FIRST(E)= ( FIRST(i)= i 4.2 FIRST4.2 FIRST集合和集合和FOLLOWFOLLOW集合集合例例 S:=aABbcd| A:=ASd| B:=SAh|eC| C:=Sf|Cg| 求此文法的每一個(gè)非終結(jié)符號(hào)的求此文法的每一個(gè)非終結(jié)符號(hào)的FIRST集。集。解：解：FIRST(S)=FIRST(aABbcd)FIRST() =a=a,FIRST(A)=FIRS

11、T(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() =a,fa,f,g=a,f,g,4.2.1 FIRST4.2.1 FIRST集合集合4.2 FIRST4.2 FIRST集合和集合和FOLLOWFOLLOW集合集合練習(xí)練習(xí) ：S:=aAcB|Bd A:=AaB|c B:=bBcA|b| 求此文法的每一個(gè)非終結(jié)符號(hào)的求此文法的每一個(gè)非終結(jié)符號(hào)的FIRST集集解：解：FIRST(S)=FIRST(aAcB)FIRST(Bd)

12、 =ab,d =a,b,dFIRST(A)=FIRST(AaB)FIRST =cc =cFIRST(B)=FIRST(bBcA)FIRST(b) FIRST() =bb =b, 4.2.1 FIRST4.2.1 FIRST集合集合4.2 FIRST4.2 FIRST集合和集合和FOLLOWFOLLOW集合集合4.2.2 FOLLOW4.2.2 FOLLOW集合集合FOLLOW集合定義：集合定義： 假定假定S是文法的開(kāi)始符號(hào)，對(duì)于是文法的開(kāi)始符號(hào)，對(duì)于G的任何非的任何非終結(jié)符號(hào)終結(jié)符號(hào)A，則：，則： FOLLOW(A)= a | S Aa， aVt 若若S A，則規(guī)定，則規(guī)定#FOLLOW(A)

13、。 * FOLLOW(A)FOLLOW(A)就是在所有句型中出現(xiàn)在緊接就是在所有句型中出現(xiàn)在緊接A A之后的之后的終結(jié)終結(jié)符號(hào)或符號(hào)或# #。注意：在。注意：在FOLLOWFOLLOW集合中無(wú)集合中無(wú)。4.2 FIRST4.2 FIRST集合和集合和FOLLOWFOLLOW集合集合 對(duì)于文法中的符號(hào)對(duì)于文法中的符號(hào)AVAVn n，其，其FOLLOW(A)FOLLOW(A)集合可反集合可反復(fù)應(yīng)用下列規(guī)則計(jì)算，直到其復(fù)應(yīng)用下列規(guī)則計(jì)算，直到其FOLLOW(A)FOLLOW(A)集合不再增集合不再增大為止：大為止：1)1)對(duì)于文法的對(duì)于文法的開(kāi)始符號(hào)開(kāi)始符號(hào)S S，令，令#FOLLOW(S)#FOL

14、LOW(S)2)2)若若G G中有形如中有形如BA BA 的產(chǎn)生式，且的產(chǎn)生式，且 ，則，則將將FIRST()FIRST()中的一切非中的一切非符號(hào)加進(jìn)符號(hào)加進(jìn)FOLLOW(A)FOLLOW(A)。3)3)若若G G中有形如中有形如BABA或或BA BA 的產(chǎn)生式，且的產(chǎn)生式，且FIRST()FIRST()，則，則FOLLOW(B)FOLLOW(B)中的全部元素均屬于中的全部元素均屬于FOLLOW(A)FOLLOW(A)，即即FOLLOW(B) FOLLOW(A)FOLLOW(B) FOLLOW(A) 。4.2 FIRST4.2 FIRST集合和集合和FOLLOWFOLLOW集合集合例例4-2

15、 有文法有文法 ETE，E+TE，E，TFT，T*FT，T，F(xiàn)(E)|i，求各非終結(jié)符號(hào)的，求各非終結(jié)符號(hào)的FOLLOW集集。解：先求出某些符號(hào)的解：先求出某些符號(hào)的FIRST集合：集合：FIRST(E)=FIRST(T) =FIRST(F) = ( ,i FIRST(E)= + ,FIRST(T)= * ,再求再求FOLLOW集合：集合：FOLLOW(E)=) ， #FOLLOW(E)= FOLLOW(E)=) ,# FOLLOW(T)= FIRST(E) FOLLOW(E) FOLLOW(E)= + , ) , # FOLLOW(T)= FOLLOW(T)= +,) , # FOLLOW(

16、F)=FIRST(T) FOLLOW(T) FOLLOW(T) = *,+,) ,# 例例 設(shè)文法設(shè)文法GS:S:=SbA|aA A:=Bc B:=Sb求此文法的每一個(gè)非終結(jié)符號(hào)的求此文法的每一個(gè)非終結(jié)符號(hào)的FOLLOW集。集。解：解：1. 因?yàn)橐驗(yàn)镾為文法的開(kāi)始符號(hào)，所以為文法的開(kāi)始符號(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(

17、A)=b,#。3. 由由A:=Bc，有，有FIRST(c)=cFOLLOW(B)。因此，。因此，F(xiàn)OLLOW(B)=c。 4.2 FIRST4.2 FIRST集合和集合和FOLLOWFOLLOW集合集合練習(xí)練習(xí) 已知文法已知文法GS:S:=A A:=BA A:=iBA| B:=CB B:=+CB| C:=)A*|( 求求FOLLOW(C)。解：解：FOLLOW(C)=FIRST(B) FOLLOW(B)FOLLOW(B) =+,i,*,#4.2 FIRST4.2 FIRST集合和集合和FOLLOWFOLLOW集合集合4.2.2 FOLLOW4.2.2 FOLLOW集合集合4.3 4.3 遞歸下

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

19、則調(diào)用該符號(hào)的子程序。）若有非終結(jié)符號(hào)，則調(diào)用該符號(hào)的子程序。2. 若若U的右部的右部有多個(gè)候選式有多個(gè)候選式，則根據(jù)每個(gè)候選式的第一個(gè)符號(hào)確定，則根據(jù)每個(gè)候選式的第一個(gè)符號(hào)確定該候選式分支。該候選式分支。3. 只有輸入串的每一個(gè)符號(hào)全部匹配成功，且正確返回時(shí)，該語(yǔ)法只有輸入串的每一個(gè)符號(hào)全部匹配成功，且正確返回時(shí)，該語(yǔ)法成分才算真正獲得識(shí)別。成分才算真正獲得識(shí)別。4.3 4.3 遞歸下降分析法遞歸下降分析法例例4-3 考慮文法考慮文法Z:=(U)|aUb ，U:=dZ|e為其構(gòu)造遞歸下降分析子為其構(gòu)造遞歸下降分析子程序。并對(duì)輸入串程序。并對(duì)輸入串a(chǎn)eb進(jìn)進(jìn)行語(yǔ)法分析行語(yǔ)法分析 。解：文法中有

20、兩個(gè)非終結(jié)符號(hào)解：文法中有兩個(gè)非終結(jié)符號(hào)Z Z和和U U，那么我們需要分別編兩個(gè)過(guò)程來(lái)完那么我們需要分別編兩個(gè)過(guò)程來(lái)完成成Z Z和和U U規(guī)則的識(shí)別。規(guī)則的識(shí)別。 對(duì)于規(guī)則對(duì)于規(guī)則Z:=(U)|aUbZ:=(U)|aUb，右部有，右部有兩個(gè)候選式，因此，兩個(gè)候選式，因此，U U的識(shí)別過(guò)程的識(shí)別過(guò)程有兩個(gè)分支，分別根據(jù)符號(hào)有兩個(gè)分支，分別根據(jù)符號(hào)( (和和a a來(lái)來(lái)判別。判別。 同理對(duì)規(guī)則同理對(duì)規(guī)則U:=dZ|eU:=dZ|e設(shè)計(jì)的過(guò)設(shè)計(jì)的過(guò)程也分為兩個(gè)分支。程也分為兩個(gè)分支。4.3 4.3 遞歸下降分析法遞歸下降分析法Z:=(U)|aUb非終結(jié)符號(hào)非終結(jié)符號(hào)Z的分析程序的分析程序 4.3 4.

21、3 遞歸下降分析法遞歸下降分析法非終結(jié)符號(hào)非終結(jié)符號(hào)U的分析程序的分析程序U:=dZ|e4.4 LL(1)4.4 LL(1)分析法分析法LL(1)分析法的含義：分析法的含義：第一個(gè)第一個(gè)L表示自左向右順序掃描輸入符號(hào)串表示自左向右順序掃描輸入符號(hào)串第二個(gè)第二個(gè)L表示分析過(guò)程產(chǎn)生一個(gè)句子的最左推導(dǎo)表示分析過(guò)程產(chǎn)生一個(gè)句子的最左推導(dǎo)括號(hào)中的括號(hào)中的1表示每進(jìn)行一步推導(dǎo)，只需要向前查看表示每進(jìn)行一步推導(dǎo)，只需要向前查看1個(gè)輸入符號(hào)，便能確定當(dāng)前所應(yīng)選用的規(guī)則個(gè)輸入符號(hào)，便能確定當(dāng)前所應(yīng)選用的規(guī)則 LL(1)分析程序的結(jié)構(gòu)：分析程序的結(jié)構(gòu)： LL(1)分析器由一個(gè)總控程序、一張分析表和一分析器由一個(gè)總

22、控程序、一張分析表和一個(gè)分析棧組成。個(gè)分析棧組成。 4.4 LL(1)4.4 LL(1)分析法分析法是一個(gè)二維表，它概括了是一個(gè)二維表，它概括了文法的全部信息，指出了文法的全部信息，指出了分析器應(yīng)采取的動(dòng)作。分析器應(yīng)采取的動(dòng)作。存放一系列存放一系列文法符號(hào)。文法符號(hào)。分析開(kāi)始時(shí)，分析開(kāi)始時(shí)，先將先將# #入棧，入棧，然后再將文然后再將文法的開(kāi)始符法的開(kāi)始符號(hào)入棧。號(hào)入棧。分析過(guò)程中使用的產(chǎn)生式序列。分析過(guò)程中使用的產(chǎn)生式序列。要分析的輸入符號(hào)串。串的末尾放置一個(gè)特殊符號(hào)要分析的輸入符號(hào)串。串的末尾放置一個(gè)特殊符號(hào)# #，表示結(jié)束，表示結(jié)束根據(jù)棧頂符根據(jù)棧頂符號(hào)和當(dāng)前的號(hào)和當(dāng)前的輸入符號(hào)，輸入符

23、號(hào)，按照分析表按照分析表的指示來(lái)完的指示來(lái)完成分析過(guò)程。成分析過(guò)程。4.4 LL(1)4.4 LL(1)分析法分析法分析表分析表M：是一個(gè)二維表，可用一個(gè)二維數(shù)組是一個(gè)二維表，可用一個(gè)二維數(shù)組MA，a來(lái)表示，它指出了分析器來(lái)表示，它指出了分析器應(yīng)采取的動(dòng)作。應(yīng)采取的動(dòng)作。分析表中的分析表中的每一行是文每一行是文法中的一個(gè)法中的一個(gè)非終結(jié)符號(hào)、非終結(jié)符號(hào)、終結(jié)符號(hào)或終結(jié)符號(hào)或# #；分析表每一分析表每一列是文法的列是文法的一個(gè)終結(jié)符一個(gè)終結(jié)符號(hào)或號(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。1

24、) 分析開(kāi)始時(shí)，首先將符號(hào)分析開(kāi)始時(shí)，首先將符號(hào)#及文法的開(kāi)始符號(hào)及文法的開(kāi)始符號(hào)S依次置于依次置于分析棧的底部，并把各指示器調(diào)整至起始位置。然后，反復(fù)分析棧的底部，并把各指示器調(diào)整至起始位置。然后，反復(fù)執(zhí)行第二步的操作。執(zhí)行第二步的操作。 輸入符號(hào)串：輸入符號(hào)串： #ana2a1分析棧：分析棧：#S 分析開(kāi)始時(shí)狀況分析開(kāi)始時(shí)狀況 2) 假設(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)行中的狀況 (1)若若XmVn，則查分析表的，

25、則查分析表的Xm所在行和所在行和ai所在列，假設(shè)所在列，假設(shè)MXm,ai為為POP,PUSH（WVU），則將，則將Xm出棧，并將出棧，并將WVU入棧，這意味入棧，這意味著使用了規(guī)則著使用了規(guī)則XmUVW；MXm,ai為為POP，則將，則將Xm出棧，這意出棧，這意味著使用了規(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)

26、。( 3 ) 若若Xm=ai= #，表示輸入串完全匹配，分析成功。，表示輸入串完全匹配，分析成功。 #X1X2Xm-1WVU #X1X2Xm-1Xm #X1X2Xm-1 Xm例：算術(shù)表達(dá)式文法例：算術(shù)表達(dá)式文法ETE，E+TE，E，TFT,T*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)作含義：例例根據(jù)表根據(jù)表4-1，對(duì)，對(duì)符號(hào)串符號(hào)

27、串i+i*i進(jìn)行進(jìn)行分析。分析。符號(hào)串符號(hào)串i+i*i的分析過(guò)程的分析過(guò)程i+ii+i* *i i的最左推導(dǎo)：的最左推導(dǎo)：E ET TEEF FTTE E i iTTEEi iEEi i+ +T TEEi+i+F FTTEEi+i+i iTTEEi+ii+i* *F FTTEEi+ii+i* *i iTTE E i+ii+i* *i iEE i+ii+i* *i i 對(duì)文法對(duì)文法G中的每個(gè)產(chǎn)生式中的每個(gè)產(chǎn)生式A，按下列規(guī)則確定，按下列規(guī)則確定LL(1)分析分析表中的元素表中的元素M：1)對(duì)對(duì)FIRST()中的每個(gè)終結(jié)符中的每個(gè)終結(jié)符a，置，置MA,a=“POP，PUSH()” ，其中其中為為的

28、倒置；的倒置；2)若若FIRST()， 則對(duì)屬于則對(duì)屬于FOLLOW(A)的每個(gè)符號(hào)的每個(gè)符號(hào)b(b為終結(jié)為終結(jié)符或符或#)，置，置MA,b=“POP” ；3)把把M中的所有中的所有Ma,a置為置為“POP，NEXTSYM”， aVt ；4)置置M#,#=“ ACCEPT”;5)把把M中所有不按上述規(guī)則定義的元素均置為空或中所有不按上述規(guī)則定義的元素均置為空或“ERROR”。 4.4 LL(1)4.4 LL(1)分析法分析法例例:ETE，E+TE，E，TFT，T*FT，T，F(xiàn)(E)|i，構(gòu)造該文法的分析表。，構(gòu)造該文法的分析表。對(duì)規(guī)則對(duì)規(guī)則ETE ：FIRST(TE)= (，i)，那么在分析表

29、的符號(hào)，那么在分析表的符號(hào)E所在所在的行、符號(hào)的行、符號(hào)(和和i所在的列對(duì)應(yīng)的位置分別填入所在的列對(duì)應(yīng)的位置分別填入“POP,PUSH(ET)”，見(jiàn)表見(jiàn)表4-1的的E行。行。對(duì)規(guī)則對(duì)規(guī)則E+TE：FIRST(+TE)=+，在符號(hào)，在符號(hào)E行符號(hào)行符號(hào)+列對(duì)應(yīng)的位列對(duì)應(yīng)的位置填入置填入“POP,PUSH(ET+)” ，見(jiàn)表，見(jiàn)表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”，見(jiàn)表，見(jiàn)表4-1的的E行。行。 其它規(guī)則處理方法相同（略）。其它規(guī)則處理方法相同（略）。對(duì)于一個(gè)文法，若按上述方法構(gòu)造的分析表對(duì)于一個(gè)文法，若按上述方法構(gòu)造的分析表M不含多重定義，則稱不含多重定義，則稱它是一個(gè)它是一個(gè)LL(1)文法文法。 4.4 LL(1)4.4 LL(1)分析法分析法分析表的簡(jiǎn)化分析表的簡(jiǎn)化