04第4章 語法分析01

《04第4章 語法分析01》由會員分享，可在線閱讀，更多相關《04第4章 語法分析01（32頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、第四章第四章 語法分析語法分析語法分析是編譯過程的核心部分，它以詞法分析輸出的單詞串形式的源程序作語法分析是編譯過程的核心部分，它以詞法分析輸出的單詞串形式的源程序作為輸入和分析的對象為輸入和分析的對象,它的主要任務是按照程序語言的語法規(guī)則，分析源程序它的主要任務是按照程序語言的語法規(guī)則，分析源程序的語法結構，即分析如何由這些單詞組成各種語法成分，同時進行語法檢查，的語法結構，即分析如何由這些單詞組成各種語法成分，同時進行語法檢查，為語義分析和代碼生成作準備。執(zhí)行語法分析任務的程序叫語法分析程序或語為語義分析和代碼生成作準備。執(zhí)行語法分析任務的程序叫語法分析程序或語法分析器。法分析器。語法分析

2、程序以詞法分析輸出的符號串作為輸入，在分析過程中檢查這個符號語法分析程序以詞法分析輸出的符號串作為輸入，在分析過程中檢查這個符號串是否為該程序語言的句子。若是，輸出該句子的分析樹；若不是，則表示源串是否為該程序語言的句子。若是，輸出該句子的分析樹；若不是，則表示源程序存在語法錯誤，需要報告錯誤的性質和位置。例如，對于程序存在語法錯誤，需要報告錯誤的性質和位置。例如，對于C程序語句程序語句“IF(aT=F=(E)錯誤錯誤,退回到退回到F,選用其他候選式選用其他候選式E=T=F=i錯誤錯誤,退回到退回到T,選用其他候選式選用其他候選式E=T=TMF錯誤錯誤,退回到退回到E,選用其他候選式選用其他候

3、選式E=EAT4.14.1自頂向下的分析方法自頂向下的分析方法 上述自頂向下的分析過程有如下基本特點上述自頂向下的分析過程有如下基本特點:1.由于采用了最左推導由于采用了最左推導,故如果文法是左遞歸的故如果文法是左遞歸的,便會使語法便會使語法分析過程陷入循環(huán)不已的狀態(tài)。例如分析過程陷入循環(huán)不已的狀態(tài)。例如E=EAT=EATAT=EATATAT=2.采用最左推導以實現(xiàn)對符號串采用最左推導以實現(xiàn)對符號串w的匹配的匹配,實際上是用文法產(chǎn)實際上是用文法產(chǎn)生式的諸候選式反復進行試探的過程生式的諸候選式反復進行試探的過程,這勢必會出現(xiàn)大量的這勢必會出現(xiàn)大量的回溯回溯,從而導致語法分析效率的大幅下降。從而導

4、致語法分析效率的大幅下降。3.當報告分析失敗時當報告分析失敗時,分析程序一般僅能給出輸入串分析程序一般僅能給出輸入串w不是句不是句子這一結論子這一結論,而難于指出出錯的具體情況而難于指出出錯的具體情況(錯誤性質和出錯錯誤性質和出錯位置等位置等)。4.因此因此,欲實現(xiàn)自頂向下的語法分析欲實現(xiàn)自頂向下的語法分析,其首要任務是改造其首要任務是改造程序設計語言的文法程序設計語言的文法,以消除其中的左遞歸和避免回溯的出以消除其中的左遞歸和避免回溯的出現(xiàn)?，F(xiàn)。4.1.14.1.1消除文法的左遞歸消除文法的左遞歸 另一種方法是對另一種方法是對A引入一個新的非終結符號引入一個新的非終結符號A,改寫為改寫為A

5、AA A|例如，前面文法的規(guī)則：EEAT|T，TTMF|F，消除左遞歸：方法一：ETATTFMF方法二:ETETFTEATE|TMFT|一般的一般的,設文法中全部設文法中全部A-產(chǎn)生式為產(chǎn)生式為A A 1|A 2|A n|1|2|m 改寫為改寫為A1A|2A|m A A 1A|2A|n A|對于左遞歸問題，我們用等價文法來解決，即將文法中的左遞歸對于左遞歸問題，我們用等價文法來解決，即將文法中的左遞歸去掉。去掉。（1）消除直接左遞歸：消除直接左遞歸：對形如對形如A A|的直接左遞歸文法規(guī)則，用擴充的直接左遞歸文法規(guī)則，用擴充BNF表示來改寫表示來改寫規(guī)則，即利用元符號規(guī)則，即利用元符號“”和和

6、“”來改寫規(guī)則，將規(guī)則改寫成來改寫規(guī)則，將規(guī)則改寫成A 4.1.14.1.1消除文法的左遞歸消除文法的左遞歸 下面，再給出一種通過將文法下面，再給出一種通過將文法G=(Vn,Vt,P,S)表示成矩陣形式而一次消除表示成矩陣形式而一次消除G的全部左遞歸的方法。的全部左遞歸的方法。首先首先,令令Vn=X1,X2,X n,且對且對G中的每個產(chǎn)生式中的每個產(chǎn)生式 Xiy1|y2|y m將將y1,y2,y m分成兩類，可將其寫成分成兩類，可將其寫成 Xi=X11i+X22i+X n n i+i于是于是,文法文法G便可寫成如下的矩陣方程便可寫成如下的矩陣方程(X1 X2 X n)=(X1 X2 X n)1

7、1 12 1n +(1,2,n)2122 2n n1n2 n n(2)消除一般左遞歸：消除一般左遞歸：如果一個非終結符號如果一個非終結符號A是經(jīng)兩步或多步推導而出現(xiàn)的左遞歸是經(jīng)兩步或多步推導而出現(xiàn)的左遞歸,則可對相關產(chǎn)生式則可對相關產(chǎn)生式作代入操作，將作代入操作，將A-產(chǎn)生式化成直接左遞歸的，再按上面的方法將左遞歸消除。產(chǎn)生式化成直接左遞歸的，再按上面的方法將左遞歸消除。例如，對于文法例如，對于文法 S A|y A S 代入后得到代入后得到(見引理見引理2.1)S S|y消除直接左遞歸得到消除直接左遞歸得到 S y S S S|4.1.14.1.1消除文法的左遞歸消除文法的左遞歸 或或 X=X

8、A+B此方程有形如此方程有形如X=BA*的最小解的最小解,由于由于A*=I+AA*其中其中 I=若設若設 A*=Z=z11 z12 z1n z21 z22 z2n zn1 zn2 z n n則有則有 X=BZ Z=I+AZ將上述兩矩陣式寫成分量式將上述兩矩陣式寫成分量式,便得到了一組等價的新的產(chǎn)生式便得到了一組等價的新的產(chǎn)生式,且消除了原文法且消除了原文法的一切左遞歸。但若新文法中含有無用產(chǎn)生式，則應予以刪除。的一切左遞歸。但若新文法中含有無用產(chǎn)生式，則應予以刪除。4.1.14.1.1消除文法的左遞歸消除文法的左遞歸 例例4.1 考慮文法考慮文法 S S a|A b|a A Sc顯然顯然,S,

9、A都是左遞歸的非終結符。都是左遞歸的非終結符。首先寫出文法的矩陣表示首先寫出文法的矩陣表示 (S A)=(S A)a c +(a)b 設設 a c *=Z=z11 z12 b z21 z22 則有則有 (S A)=(a)z11z12z21z22 z11 z12 =+a c z11 z12 z21 z22 b z21 z22 于是得到新的等價文法于是得到新的等價文法 Saz11 Aaz12 z11az11|cz21|z12az12|cz22 z21bz11 z22bz12|刪除無用產(chǎn)生式得刪除無用產(chǎn)生式得 Saz11 z11az11|cz21|z21bz114.1.2 4.1.2 回溯的消除及回

10、溯的消除及LL(1)LL(1)文法文法下面我們討論如何消除自頂向下分析過程中的回溯。此問題的解決將導致定義下面我們討論如何消除自頂向下分析過程中的回溯。此問題的解決將導致定義一類很重要的文法一類很重要的文法-LL(1)文法。文法。對于給定的文法對于給定的文法GS=(V n,V t,P,S)和給定的輸入符號串和給定的輸入符號串w=a1a2a n(a i V t)，為判斷，為判斷w是否為是否為L(G)中的句子中的句子，現(xiàn)試圖為，現(xiàn)試圖為w w建立一個從建立一個從S S出發(fā)的最左出發(fā)的最左推導推導，設經(jīng)過若干步推導后得到設經(jīng)過若干步推導后得到 S=*w1A A V n，(V n V t)*其中其中w

11、1=a1a2a i-1(1in)，即，即w的一個前綴的一個前綴w1已從上面的推導得到匹配，已從上面的推導得到匹配，現(xiàn)須對現(xiàn)須對A 繼續(xù)進行推導，現(xiàn)設繼續(xù)進行推導，現(xiàn)設G中的全部中的全部A-產(chǎn)生式為產(chǎn)生式為 A y1|y2|y m且對這且對這m個候選式個候選式y(tǒng) k(1km)，要么全部，要么全部y k 均不能推導出以均不能推導出以a i打頭的符號串打頭的符號串(此時此時w不是句子不是句子)，要么存在唯一的一個，要么存在唯一的一個y y j，能使，能使y y j 推導出以推導出以a i打頭的符號串打頭的符號串，而其余的而其余的y y k 則不能推出則不能推出，這樣上述推導過程在產(chǎn)生式選擇上的試探將

12、可避免。，這樣上述推導過程在產(chǎn)生式選擇上的試探將可避免。如果文法如果文法G G中的全部產(chǎn)生式均滿足上述要求中的全部產(chǎn)生式均滿足上述要求,則消除回溯的問題自然就解決了則消除回溯的問題自然就解決了。4.1.2 4.1.2 回溯的消除及回溯的消除及LL(1)LL(1)文法文法可見可見,要實現(xiàn)無回溯的自頂向下分析要實現(xiàn)無回溯的自頂向下分析,對相應文法須有一定的要求。為導出文法對相應文法須有一定的要求。為導出文法應滿足的條件應滿足的條件,需定義候選式需定義候選式y(tǒng)的終結首符集和非終結符號的終結首符集和非終結符號A的后繼終結符號集的后繼終結符號集如下如下:FIRST(y)=a|y=*a，a V t 當當y

13、=*時時,約定約定 FIRST(y)FIRST(y)就是從就是從y可能推導出的句型的所有開頭的終結符和可能的可能推導出的句型的所有開頭的終結符和可能的。FOLLOW(A)=a|S#=*A a,a V t 當當S=*A,約定約定#FOLLOW(A)FOLLOW(A)就是在所有的句型中緊接在就是在所有的句型中緊接在A之后的終結符或之后的終結符或#。于是于是,對于一個已化簡的非左遞歸文法對于一個已化簡的非左遞歸文法G,在進行自頂向下語法分析時在進行自頂向下語法分析時,不出現(xiàn)回不出現(xiàn)回溯的充分條件是對于溯的充分條件是對于G中的每個產(chǎn)生式中的每個產(chǎn)生式A y1|y2|y m,其各候選式均應滿足其各候選式

14、均應滿足:(1)不同的候選式不能推出以同一終結符號打頭的符號串不同的候選式不能推出以同一終結符號打頭的符號串,即即 FIRST(y i)FIRST(y j)=1i,jm;i j(2)若有若有y j=,則其余候選式則其余候選式y(tǒng) i所能推導出的符號串不能以所能推導出的符號串不能以FOLLOW(A)中的終中的終結符號開頭結符號開頭,即即 FIRST(y i)FOLLOW(A)=i1,2,m;i j通常通常,我們將滿足上述條件的文法稱為我們將滿足上述條件的文法稱為LL(1)文法。對于此種文法文法。對于此種文法,可采用從左可采用從左到右掃視源程序到右掃視源程序P,并按最左推導的方式求得與并按最左推導的

15、方式求得與P中各符號的匹配中各符號的匹配,而且每步推導而且每步推導只需向前查看一個輸入符號只需向前查看一個輸入符號,就可準確的選擇所用的產(chǎn)生式。就可準確的選擇所用的產(chǎn)生式。4.1.2 4.1.2 回溯的消除及回溯的消除及LL(1)LL(1)文法文法下面下面,給出對給定文法給出對給定文法G求各個求各個FIRST集集FOLLOW集的算法。由于每個產(chǎn)生式集的算法。由于每個產(chǎn)生式的各個候選式均是一個由文法符號所組成的符號串的各個候選式均是一個由文法符號所組成的符號串,因此僅須給出對單個文法因此僅須給出對單個文法符號求這兩個集合的方法即可。符號求這兩個集合的方法即可。文法符號的文法符號的FIRST集構造

16、方法：集構造方法：對于文法中的符號對于文法中的符號XVnVt，其，其FIRST(X)(X)集合可反復應用下列規(guī)則計算，集合可反復應用下列規(guī)則計算，直到其直到其FIRST(X)FIRST(X)集合不再增大為止：集合不再增大為止：1)若若XVt，則，則FIRST(X)=X2)若若XVn，且具有形如且具有形如Xa的產(chǎn)生式的產(chǎn)生式(aVt)，或具有形如或具有形如X的產(chǎn)生式，的產(chǎn)生式，則把則把a或或加進加進FIRST(X)。3)若若XVn，且，且X Y1 Y2 Y kP,且且Y1Vn,則把則把FIRST(Y1)加進加進FIRST(X);若若FIRST(Y1),則把則把FIRST(Y2)加進加進FIRST

17、(X);若若FIRST(Y1)和和FIRST(Y2),則把則把FIRST(Y3)加進加進FIRST(X)以此類推以此類推;但若對一切但若對一切1ik,均有均有FIRST(Yi),則把則把加進加進FIRST(X)4.1.2 4.1.2 回溯的消除及回溯的消除及LL(1)LL(1)文法文法例4.2設有文法SabBASC|BAbACB|c求所有非終結符和符號串AABcab的FIRST集合。解:FIRST(S)=aFIRST(A)=FIRST(SC)=FIRST(S)=a,FIRST(B)=FIRST(AbA)=FIRST(A)FIRST(bA)=a,bFIRST(C)=FIRST(B)c=a,b,c

18、FIRST(AABcab)=FIRST(A)FIRST(A)FIRST(Bcab)=aFIRST(B)=a,b4.1.2 4.1.2 回溯的消除及回溯的消除及LL(1)LL(1)文法文法對于文法中的符號對于文法中的符號BVn，其其FOLLOW(B)集合可反復應用下列集合可反復應用下列規(guī)則計算，直到集合不再增大為止：規(guī)則計算，直到集合不再增大為止：1)對于文法的開始符號，令對于文法的開始符號，令#FOLLOW(S)2)若若G中有形如中有形如AB 的產(chǎn)生式，且的產(chǎn)生式，且，則將則將FIRST()符符號加進號加進FOLLOW(B)。3)若若G中有形如中有形如AB或或AB 的產(chǎn)生式，且的產(chǎn)生式，且FI

19、RST()，則則FOLLOW(A)中的全部元素均屬于中的全部元素均屬于FOLLOW(B)。注意：在注意：在FOLLOW集合中無集合中無。4.1.2 4.1.2 回溯的消除及回溯的消除及LL(1)LL(1)文法文法例例4.3，有，有文法文法 ETE，E+TE，E，TFT，T*FT，T，F(xiàn)(E)|i，求各非終結符號的求各非終結符號的FOLLOW集。集。解：首先，我們需要求出某些符號的解：首先，我們需要求出某些符號的FIRST集集：FIRST(E)=FIRST(T)=FIRST(F)=(，i FIRST(E)=+，F(xiàn)IRST(T)=*，接下來，按接下來，按FOLLOW集定義求各非終結符號的集定義求各

20、非終結符號的FOLLOW集：集：FOLLOW(E)=)，#，F(xiàn)OLLOW(E)=FOLLOW(E)=)，#FOLLOW(T)=FIRST(E)FOLLOW(E)FOLLOW(E)=+，)，#FOLLOW(T)=FOLLOW(T)=+，)，#FOLLOW(F)=FIRST(T)FOLLOW(T)FOLLOW(T)=*，+，)，#前進4.1.3 4.1.3 遞歸下降分析法遞歸下降分析法 4.3.1 遞歸下降分析的基本方法遞歸下降分析的基本方法遞歸下降分析的概念極為簡單，其方法是將文法中的遞歸下降分析的概念極為簡單，其方法是將文法中的每一個非終結符每一個非終結符每一個非終結符每一個非終結符U U的文

21、的文的文的文法規(guī)則看作是識別法規(guī)則看作是識別法規(guī)則看作是識別法規(guī)則看作是識別U U的一個過程定義的一個過程定義的一個過程定義的一個過程定義，為每個非終結符號構造一個子程序，為每個非終結符號構造一個子程序，以完成該非終結符號所對應的語法成分的分析和識別任務。以完成該非終結符號所對應的語法成分的分析和識別任務。當當U U的規(guī)則的右部只有一個侯選式，則按從左向右的順序依次構造規(guī)則的規(guī)則的右部只有一個侯選式，則按從左向右的順序依次構造規(guī)則U U的識的識別過程代碼。如果有終結符號，判斷能否與輸入的符號相等，如果相等，表別過程代碼。如果有終結符號，判斷能否與輸入的符號相等，如果相等，表示識別成功，讀入指針

22、指向下一個輸入符號；如果不等，則意味著輸入串此示識別成功，讀入指針指向下一個輸入符號；如果不等，則意味著輸入串此時有語法錯誤。如果是非終結符號，則簡單調(diào)用這個非終結符號的子程序，時有語法錯誤。如果是非終結符號，則簡單調(diào)用這個非終結符號的子程序，由這個子程序完成該非終結符號所對應的語法成分的分析和識別任務。由這個子程序完成該非終結符號所對應的語法成分的分析和識別任務。當當U U的規(guī)則右部有多個侯選式時，則根據(jù)每個侯選式的第一個符號確定該侯選的規(guī)則右部有多個侯選式時，則根據(jù)每個侯選式的第一個符號確定該侯選式分支。式分支。例例4.4，考慮文法，考慮文法Z:=(U)|aUb，U:=dZ|e，為其構造遞

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

24、降分析法遞歸下降分析法Z:=(U)|aUb過程過程ZINPUTSYM=下一個符號下一個符號U出口出口語法錯誤：語法錯誤：輸入串少輸入串少)INPUTSYM=aYNNNNYY語法錯誤：語法錯誤：輸入串少輸入串少(、a語法錯誤：語法錯誤：輸入串少輸入串少bINPUTSYM=(INPUTSYM=)INPUTSYM=bINPUTSYM=下一個符號下一個符號INPUTSYM=下一個符號下一個符號UY圖4.1(a)非終結符號Z的分析程序過程過程UINPUTSYM=下一個符號下一個符號Z出口出口INPUTSYM=eYNNY語法錯誤：語法錯誤：輸入串少輸入串少d、eINPUTSYM=dINPUTSYM=下一個

25、符號下一個符號YU:=dZ|e圖4.1(b)非終結符號U的分析程序4.1.3 4.1.3 遞歸下降分析法遞歸下降分析法每個非終結符號的子程序設計好后，就可以對輸入串進行語法分析。假設輸每個非終結符號的子程序設計好后，就可以對輸入串進行語法分析。假設輸入串為入串為aeb,從從Z子程序開始識別，子程序開始識別，INPUTSYM=a,由于由于INPUTSYM不等于不等于(，等于等于a，所以選擇所以選擇Z子程序的右邊分支，表示選擇了子程序的右邊分支，表示選擇了Z:=aUb規(guī)則。讀下一個規(guī)則。讀下一個符號，使符號，使INPUTSYM=e，調(diào)調(diào)U子程序，因子程序，因INPUTSYM=e，所以，讀下一個符所

26、以，讀下一個符號，使號，使INPUTSYM=b，表示使用表示使用U:=e規(guī)則，并返回調(diào)用程序規(guī)則，并返回調(diào)用程序Z子程序右邊分子程序右邊分支支U的下方，接著判斷的下方，接著判斷INPUTSYM=b，讀下一個符號，并退出讀下一個符號，并退出Z，分析過程分析過程結束，從而判定輸入串結束，從而判定輸入串a(chǎn)eb語法分析成功。這個過程相當于構造了如下推導過語法分析成功。這個過程相當于構造了如下推導過程：程：Z=aUb=aeb 4.1.3 4.1.3 遞歸下降分析法遞歸下降分析法ET|E+T|E-T ET+T|-TTF|T*F|T/F TF*F|/FETYN出口出口INPUTSYM=下一個符號下一個符號I

27、NPUTSYM=+INPUTSYM=-NYTFYN出口出口INPUTSYM=下一個符號下一個符號INPUTSYM=*INPUTSYM=/NY圖4.2 E和T的分析程序4.1.4 4.1.4 預測分析法預測分析法 LL(1)分析方法也是常見的自頂向下分析，LL(1)分析使用一個下推棧而不是遞歸調(diào)用來完成分析。名稱中第一個L表示自左向右順序掃描輸入符號串，第二個L表示分析過程產(chǎn)生一個句子的最左推導。括號中的1表示每進行一步推導，只需要向前查看一個輸入符號，便能確定當前所應選用的規(guī)則。LL(1)分析的基本方法分析的基本方法LL(1)分析器由一個總控程序、一張分析表和一個分析棧組成，如圖4.4所示。輸

28、入符號串：分析棧a1a2an#XZS#LL（1）總控程序分析表輸出流圖4.4LL(1)分析器模型4.1.4 4.1.4 預測分析法預測分析法 輸入符號串輸入符號串:指要分析的輸入符號串。為了分析算法的統(tǒng)一，我們需要在輸指要分析的輸入符號串。為了分析算法的統(tǒng)一，我們需要在輸入串的末尾放置一個特殊符號入串的末尾放置一個特殊符號#，這個符號不屬于終結符號集。，這個符號不屬于終結符號集。分析表分析表M:是一個二維表，可用一個二維數(shù)組是一個二維表，可用一個二維數(shù)組MA，a來表示，它概括了文法來表示，它概括了文法的全部信息。分析表中的每一行與文法的一個非終結符號關聯(lián)，即的全部信息。分析表中的每一行與文法的

29、一個非終結符號關聯(lián)，即A可以是文可以是文法中的一個非終結符號；而每一列則與文法的一個終結符號或法中的一個非終結符號；而每一列則與文法的一個終結符號或#關聯(lián)，即關聯(lián)，即a是文是文法的一個終結符號或法的一個終結符號或#。分析表元素。分析表元素MA，a，指出了分析器應采取的動作指出了分析器應采取的動作:或或是指出當前推導應使用的產(chǎn)生式是指出當前推導應使用的產(chǎn)生式,或是指出輸入符號串存在語法錯誤?；蚴侵赋鲚斎敕柎嬖谡Z法錯誤。對于不同的對于不同的LL(1)文法，文法，LL(1)的分析算法是相同的，不同的僅僅是分析表。顯的分析算法是相同的，不同的僅僅是分析表。顯然，如何根據(jù)文法來構造分析表是然，如何根

30、據(jù)文法來構造分析表是LL(1)分析的關鍵。分析的關鍵。對于任意給定的已化簡的文法對于任意給定的已化簡的文法G，為了構造分析表，首先我們要求出每個非終，為了構造分析表，首先我們要求出每個非終結符號的結符號的FOLLOW集合和每個后選式的集合和每個后選式的FIRST集合。然后對文法集合。然后對文法G中的每個產(chǎn)中的每個產(chǎn)生式生式A y1|y2|y m，按下列規(guī)則確定分析表中的元素，按下列規(guī)則確定分析表中的元素M：1)若若a FIRST(y i)，則置，則置MA，a=“y i”。2)若若 FIRST(y j)，且，且a FOLLOW(A)，則置，則置MA，a=“y j”。3)除上述兩種情況外其余一切表

31、元素均置為除上述兩種情況外其余一切表元素均置為“ERROR”。分析棧分析棧：用來存放一系列文法符號。分析開始時，先將：用來存放一系列文法符號。分析開始時，先將#入棧，然后再將文入棧，然后再將文法的開始符號入棧。法的開始符號入棧。輸出流輸出流：分析過程中使用的產(chǎn)生式序列。：分析過程中使用的產(chǎn)生式序列?？偪爻绦蚩偪爻绦颍悍治銎鲗斎氪姆治隹靠偪爻绦蛲瓿桑悍治銎鲗斎氪姆治隹靠偪爻绦蛲瓿?根據(jù)分析棧的棧頂符號根據(jù)分析棧的棧頂符號X和當前的輸入符號和當前的輸入符號a，總控程序按照分析表的指示來決定分析器的動作，總控程序按照分析表的指示來決定分析器的動作.工工作過程如下：作過程如下：第一步初始化:分

32、析開始時，首先將符號#及文法的開始符號S依次置于分析棧的底部，并把各指示器調(diào)整至起始位置，如圖4.5所示。然后，反復執(zhí)行第二步的操作。輸入符號串：a1a2an#分析棧：S#圖4.5分析開始時的狀況第二步假設分析的某一步，分析棧及余留的符號串如圖4.6，則根據(jù)棧頂?shù)姆朮m，采取下列動作：aiai+1 an#X1X2Xm-1Xm圖4.6分析進行中的狀況4.1.4 4.1.4 預測分析法預測分析法(1)若若X m V n，表示棧頂要推導出掃描的符號，則查分析表的，表示棧頂要推導出掃描的符號，則查分析表的X m行行a i列，假設列，假設M X m，a i為產(chǎn)生式為產(chǎn)生式X m Y1Y2Y k，則將，

33、則將X m出棧，并將出棧，并將Y1Y2Y k反序入棧，如圖反序入棧，如圖4.7；若若M X m，a i為為ERROR，則出錯。則出錯。aiai+1 an#X1X2Xm-1YkYk-1Y1圖4.7反序入棧(2)若若X m=a i#，表表示示棧棧頂頂與與掃掃描描的的符符號號匹匹配配，則則棧棧頂頂符符號號X m出出棧棧，輸輸入指示器指向下一個符號，入指示器指向下一個符號，否則否則(即即X m a i)出錯。出錯。(3)若若X m=a a i=#=#，表示輸入串完全匹配，分析成功。表示輸入串完全匹配，分析成功。4.1.4 4.1.4 預測分析法預測分析法4.1.4 4.1.4 預測分析法預測分析法例4

34、.5考慮算術表達式文法ETE，E+TE，E，TFT，T*FT，T，F(xiàn)(E)|i對規(guī)則ETE：FIRST(TE)=(，i，那么在分析表的符號E所在的行、符號(和i所在的列對應的位置分別填入TE,見表4.1的E行。對規(guī)則E+TE：FIRST(+TE)=+，所以在分析表E行+列對應的位置填入+TE，見表4.1的E行。對規(guī)則E：FOLLOW(E)=)，#，所以在分析表E行)和#列對應的位置填入，見表4.1的E行。對于一個文法，若按上述方法構造的分析表M不含多重定義，則稱它是一個LL(1)文法。返回表4.1算術表達式分析表符號輸入符號i+*()#EETTFTEFTi+TE*FTTEFT(E)表4.1算術

35、表達式分析表4.1.4 4.1.4 預測分析法預測分析法根據(jù)表4.1給出的分析表，對符號串i+i*i進行分析。表4.2符號串i+i*i的分析過程步驟分析棧余留輸入串所用產(chǎn)生式1234567891011121314151617#E#ET#ETF#ETi#ET#E#ET+#ET#ETF#ETi#ET#ETF*#ETF#ETi#ET#E#i+i*i#i+i*i#i+i*i#i+i*i#+i*i#+i*i#+i*i#i*i#i*i#i*i#*i#*i#i#i#ETETFTFiTE+TETFTFiT*FTFiTE表表4.2中輸出的產(chǎn)生式序列構成對輸中輸出的產(chǎn)生式序列構成對輸入符號串的最左推導。按此產(chǎn)生式

36、入符號串的最左推導。按此產(chǎn)生式序列構造輸入符號串序列構造輸入符號串i+i*i的最左推的最左推導過程如下：導過程如下：E E=TETE =FTE FTE =iTEiTE =iEiE =i+TEi+TE =i+FTEi+FTE=i+iTEi+iTE i+ii+i*FT*FTE E i+ii+i*iTiTE E i+ii+i*iEiE i+i*ii+i*i 4.1.4 4.1.4 預測分析法預測分析法4.1.5 4.1.5 某些非某些非LL(1)LL(1)文法的改造文法的改造 對于任何LL(1)文法G,我們總能按上述方法為G構造一個預測分析表,且構造出的分析表決不會含有多重定義的元素.然而,對于非L

37、L(1)文法,或因為它們含有左遞歸,或因為它們存在二義性,歸根結底因為它們不滿足無回溯條件,則構造出的分析表必然會出現(xiàn)多重定義的元素.例如,SabBASC|BAA|BAbACB|cFIRST(S)=aFOLLOW(S)=a,b,c,#FIRST(A)=a,b,FOLLOW(A)=a,b,c,#FIRST(B)=a,bFOLLOW(B)=a,b,c,#FIRST(C)=a,b,cFOLLOW(C)=a,b,c,#MA,a=ASC,ABAAMA,b=ABAA,A可見分析表含有多重定義元素,2、解決二義性問題、解決二義性問題這個問題有時可通過反復提取公因子解決。對形如A1|2|m的產(chǎn)生式,可改寫為A

38、AA1|2|m例如，規(guī)則：T(E)|a(E)|a可改成：T(E)|aT，T(E)|4.1.5 4.1.5 某些非某些非LL(1)LL(1)文法的改造文法的改造1、左遞歸轉成右遞歸、左遞歸轉成右遞歸LL(1)分析不能處理左遞歸文法，但也不能像遞歸下降分析那樣將左遞歸改為采用擴充BNF表示。在LL(1)分析中，必須將左遞歸文法變成右遞歸文法。例如，對左遞歸規(guī)則EE+T|T，如果像遞歸下降分析那樣改成ET+T無法形成逆序入棧，但可改成右遞歸：令E為新的非終結符號，則等價的右遞歸規(guī)則為：ETE，E+TE|實際上，在遞歸下降分析方法中，也可將左遞歸規(guī)則改成右遞歸進行處理。4.1.5 4.1.5 某些非某

39、些非LL(1)LL(1)文法的改造文法的改造但并非所有的文法都可用此法解決分析表的多重定義。考慮有文法GS：SAU|BR,AaAU|b,BaBR|b,Uc,Rd對于規(guī)則SAU|BR，因為FIRST(AU)FIRST(BR)，故該文法不是LL(1)文法。為了能夠提取公因子，必須將非終結符號A、B的產(chǎn)生式帶入S的產(chǎn)生式中，得到：SaAUU|bU|aBRR|bR經(jīng)提取公因子后，得到Sa(AUU|BRR)|b(U|R),令S、S”分別代替括號中的左右部分，得如下等價文法：SaS|bS”,SAUU|BRR,S”U|R,AaAU|b,BaBR|b,Uc,Rd顯然，對于規(guī)則SAUU|BRR，因為FIRST(

40、AUU)FIRST(BRR)，故它仍然不是LL(1)文法。且無論重復多少次提取公因子，都不能把它變成LL(1)文法。由于遞歸下降分析法也存在這類問題，所以，自頂向下分析方法無法對這類文法進行語法分析。4.1.5 4.1.5 某些非某些非LL(1)LL(1)文法的改造文法的改造我們把能由某一LL(1)文法產(chǎn)生的語言稱為LL(1)語言。LL(1)文法具有下列性質：1)任何LL(1)文法都是無二義的。2)若文法中有左遞歸，肯定不是LL(1)文法。但有些左遞歸文法可轉換成右遞歸文法，從而滿足LL(1)文法的要求。3)存在一種算法，能判定文法是否為LL(1)文法。4)存在一種算法，能判定任意兩個LL(1

41、)文法是否產(chǎn)生相同的語言。5)不存在這樣的算法，判定任意上下文無關語言能否由LL(1)文法產(chǎn)生。6)非LL(1)語言是存在的。在LL系列分析方法中，若每一步推導不是向前看一個字符，而是看K個字符才能確定要選用的產(chǎn)生式，則稱為LL(K)分析，能滿足LL(K)分析條件的文法叫LL(K)文法。習題習題 4.1對下面文法，設計遞歸下降分析程序。SaAS|(A),AAb|c4.2設有文法GZ：Z=(A),A=a|Bb,B=Aab若采用遞歸下降分析方法，對此文法來說，在分析過程中，能否避免回溯？為什么？4.3若有文法如下，設計遞歸下降分析程序。|Id=；|+|-|*|/ID|NUM|()4.4有文法GA：

42、A:=aABe|B:=Bb|b1)求每個非終結符號的FOLLOW集。2)該文法是LL(1)文法嗎？3)構造LL(1)分析表。4.5若有文法A(A)A|，1)為非終結符A構造First集合和Follow集合。2)說明該文法是LL(1)的文法。4.6利用分析表4.1識別以下算術表達式，請寫出分析過程：1)i+i*i+i2)i*(i+i+i)習題習題 4.7考慮下面簡化了的C聲明文法：；int|float|charID,|ID1）在該文法中提取左因子。2）為所得的文法的非終結符構造First集合和Follow集合。3）說明所得的文法是LL(1)文法。4）為所得的文法構造LL(1)分析表。5）假設有輸入串為:charx,y,z，寫出相對應的LL(1)分析過程。習題習題 4.8修改語法分析程序，使該程序能分析do語句和邏輯表達式,有關文法規(guī)則如下：:=if_stat|:=dowhile;:=ID=|:=(&|)|!|&、|、!為邏輯運算符。習題習題