1、第四章第四章 語法分析語法分析自頂向下分析自頂向下分析 語法分析是編譯過程的核心部分，它的主要任務是按照程序語言的語法規則，語法分析是編譯過程的核心部分，它的主要任務是按照程序語言的語法規則，從由詞法分析輸出的源程序符號串中識別出各類語法成分，同時進行語法檢從由詞法分析輸出的源程序符號串中識別出各類語法成分，同時進行語法檢查，為語義分析和代碼生成作準備。執行語法分析任務的程序叫語法分析程查，為語義分析和代碼生成作準備。執行語法分析任務的程序叫語法分析程序或語法分析器。序或語法分析器。語法分析程序以詞法分析輸出的符號串作為輸入，在分析過程中檢查這個符語法分析程序以詞法分析輸出的符號串作為輸入，在

2、分析過程中檢查這個符號串是否為該程序語言的句子。若是，輸出該句子的分析樹；若不是，則表號串是否為該程序語言的句子。若是，輸出該句子的分析樹；若不是，則表示源程序存在語法錯誤，需要報告錯誤的性質和位置。例如，對于示源程序存在語法錯誤，需要報告錯誤的性質和位置。例如，對于C程序語句程序語句“IF (aa, aVt若若=*, 則規定則規定FIRST()實際上，實際上，FIRST()就是從就是從可能推導出的所有開頭終結符號和可能推導出的所有開頭終結符號和可能的可能的。文法符號的文法符號的FIRST集合構造方法：集合構造方法：對于文法中的符號對于文法中的符號XVnVt，其，其FIRST(X)(X)集合可

3、反復應用下列集合可反復應用下列規則計算，直到其規則計算，直到其FIRST(X)FIRST(X)集合不再增大為止：集合不再增大為止： 1)若若XVt，則，則FIRST(X)=X2)若若XVn，且具有形如，且具有形如Xa的產生式的產生式(aVt)，或具有形如，或具有形如X的產生式，則把的產生式，則把a或或加進加進FIRST(X)。3)設設G中有形如中有形如XY1Y Y2YYk的產生式，若的產生式，若Y Y1VVn，則把，則把FIRST(YFIRST(Y1) )中的一切非中的一切非符號加進符號加進FIRST(X)FIRST(X)；對于一切；對于一切2ik2ik，若，若Y Y1，Y Y2，Y Yi-1

4、均為非終結符號，且均為非終結符號，且FIRST(YFIRST(Yj) )，1ji-11ji-1，則，則將將FIRST(YFIRST(Yi) )中的一切非中的一切非符號加進符號加進FIRST(X)FIRST(X)；但若對一切；但若對一切1ik1ik，均有，均有FIRST(YFIRST(Yj) )，則將，則將符號加進符號加進FIRST(X)FIRST(X)。 對于文法對于文法G的任一符號串的任一符號串=X1X2Xn可按下列步驟構造其可按下列步驟構造其FIRST()集合：集合：1)置置FIRST()=2)將將FIRST(X1)中的一切非中的一切非符號加進符號加進FIRST()；3)若若FIRST(X

5、1)，將，將FIRST(X2)中的一切非中的一切非符號加進符號加進FIRST()；若若FIRST(X1)和和FIRST(X2)，將，將FIRST(X3)中中的一切非的一切非符號加進符號加進FIRST()；余類推。；余類推。4)若對于一切若對于一切1in，FIRST(Xi i) )，則將，則將符號加進符號加進FIRST()FIRST()。 例例4.1，有，有文法文法 ETE E+TE E TFT T*FT T F(E)|i求文法中非終結符號以求文法中非終結符號以及符號串的及符號串的FIRST集。集。解：首先求各符號的解：首先求各符號的FIRST集：該文法共有集：該文法共有非終結符號為非終結符號為

6、E，E，T，T，FFIRST(E)=FIRST(T)=FIRST(F)= ( ，i FIRST(E)= + ，FIRST(T)= * ，下面求文法中各產生式右部符號串的下面求文法中各產生式右部符號串的FIRST集：集：FIRST(TE)=FIRST(T)=FIRST(F)= ( ，i FIRST(+TE)= + FIRST()=FIRST(FT)=FIRST(F)= ( ，i FIRST(*FT)= * FIRST(E)= ( FIRST(i)= i FOLLOW集合定義：假定集合定義：假定S是文法的開始符號，對于是文法的開始符號，對于G的任何非的任何非終結符號終結符號A，則：，則： FOLL

7、OW(A)= a | S=Aa, aVt 若若S=*A，則規定，則規定#FOLLOW(A)從定義可看出，從定義可看出，FOLLOW(A)就是在所有句型中出現在緊接就是在所有句型中出現在緊接A之之后的終結符號或后的終結符號或#。對于文法中的符號對于文法中的符號AVn，其，其FOLLOW(A)集合可反復應用下列集合可反復應用下列規則計算，直到其規則計算，直到其FOLLOW(A)集合不再增大為止：集合不再增大為止：1) 對于文法的開始符號，令對于文法的開始符號，令#FOLLOW(S)2) 若若G中有形如中有形如AB 的產生式，且的產生式，且 ，則將，則將FIRST()中的一切非中的一切非符號符號加進

8、加進FOLLOW(B)。3) 若若G中有形如中有形如AB或或AB 的產生式，且的產生式，且FIRST()，則，則FOLLOW(A)中的全部元素均屬于中的全部元素均屬于FOLLOW(B)。注意：在注意：在FOLLOW集合中無集合中無。 例例4.2，有，有文法文法 ETE，E+TE，E， TFT， T*FT，T，F(E)|i，求各非終結符號的求各非終結符號的FOLLOW集。集。解：首先，我們需要求出某些符號的解：首先，我們需要求出某些符號的FIRST集：集： FIRST(E)=FIRST(T)=FIRST(F)= ( ，i FIRST(E)= + ，FIRST(T)= * ， 接下來，按接下來，按

9、FOLLOW集定義求各非終結符號的集定義求各非終結符號的FOLLOW集：集： FOLLOW(E)= )，#，FOLLOW(E)= FOLLOW(E)= ) ，# FOLLOW(T)= FIRST(E) FOLLOW(E) FOLLOW(E) = + ， ) ， # FOLLOW(F)= FIRST(T) FOLLOW(T) FOLLOW(T) = +，*，) ，# FOLLOW(T)= FOLLOW(T)= + ， ) ， # 4.3 4.3 遞歸下降分析遞歸下降分析 遞歸下降分析的基本方法遞歸下降分析的基本方法遞歸下降分析的概念極為簡單，其方法是將文法中的每一個非終結符遞歸下降分析的概念極為

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

11、個輸入符號；如果不等，則意味著輸入串此時有語成功，讀入指針指向下一個輸入符號；如果不等，則意味著輸入串此時有語法錯誤。如果是非終結符號，則簡單調用這個非終結符號的子程序，由這個法錯誤。如果是非終結符號，則簡單調用這個非終結符號的子程序，由這個子程序完成該非終結符號所對應的語法成分的分析和識別任務。當一條規則子程序完成該非終結符號所對應的語法成分的分析和識別任務。當一條規則右部有多個侯選式時，則根據每個侯選式的第一個符號確定該侯選式分支。右部有多個侯選式時，則根據每個侯選式的第一個符號確定該侯選式分支。只有被調用的分析和識別某語法成分的子程序匹配輸入串成功，且正確返回只有被調用的分析和識別某語法

12、成分的子程序匹配輸入串成功，且正確返回時，該語法成分才算真正獲得識別。時，該語法成分才算真正獲得識別。 例例4.3，考慮文法，考慮文法Z:=(U)|aUb ，U:=dZ|e，為其構造遞歸下降分析子程序。并，為其構造遞歸下降分析子程序。并對輸入串對輸入串aebaeb進行語法分析進行語法分析 。解：文法中有兩個非終結符號解：文法中有兩個非終結符號Z和和U，那么我們需要分別編兩個過程來完成，那么我們需要分別編兩個過程來完成Z和和U規則的識別。對于規則規則的識別。對于規則Z:=(U)|aUb，右部有兩個候選式，因此，右部有兩個候選式，因此，U的識別的識別過程有兩個分支，分別根據符號過程有兩個分支，分別

13、根據符號(和和a來判別。同理對規則來判別。同理對規則U:=dZ|e設計的過程設計的過程也分為兩個分支。見圖也分為兩個分支。見圖4.1(a)和和(b)所示。所示。遞歸下降分析的基本方法遞歸下降分析的基本方法Z:=(U)|aUb過程過程ZINPUTSYM=下一個符號下一個符號U出口出口語法錯誤：語法錯誤：輸入串少輸入串少)INPUTSYM =aYNNNNYY語法錯誤：語法錯誤：輸入串少輸入串少(、a語法錯誤：語法錯誤：輸入串少輸入串少bINPUTSYM =(INPUTSYM =)INPUTSYM =bINPUTSYM=下一個符號下一個符號INPUTSYM=下一個符號下一個符號UY圖4.1(a) 非

14、終結符號Z的分析程序 過程過程UINPUTSYM=下一個符號下一個符號Z出口出口INPUTSYM =eYNNY語法錯誤：語法錯誤：輸入串少輸入串少d、eINPUTSYM =dINPUTSYM=下一個符號下一個符號YU:=dZ|e圖4.1(b) 非終結符號U的分析程序 遞歸下降分析的基本方法遞歸下降分析的基本方法每個非終結符號的子程序設計好后，就可以對輸入串進行語法分析。假設輸每個非終結符號的子程序設計好后，就可以對輸入串進行語法分析。假設輸入串為入串為aeb,從從Z子程序開始識別，子程序開始識別，inputsym=a,由于由于INPUTSYM不等于不等于(，等于，等于a，所以選擇，所以選擇Z子

15、程序的右邊分支，表示選擇了子程序的右邊分支，表示選擇了Z:=aUb規則。讀下一個符號，規則。讀下一個符號，使使inputsym=d，調，調U子程序，因子程序，因INPUTSYM=e，所以，讀下一個符號，使，所以，讀下一個符號，使INPUTSYM=b，表示使用，表示使用U:=e規則，并返回調用程序規則，并返回調用程序Z子程序右邊分支子程序右邊分支U的的下方，接著判斷下方，接著判斷INPUTSYM=b，讀下一個符號，并退出，讀下一個符號，并退出Z，分析過程結束，分析過程結束，從而判定輸入串從而判定輸入串aeb語法分析成功。這個過程相當于構造了如下推導過程：語法分析成功。這個過程相當于構造了如下推導

16、過程： Z=aUb=aeb 通過上面的例子，可看出遞歸下降分析的概念極為簡單，但這通過上面的例子，可看出遞歸下降分析的概念極為簡單，但這里面還存在下面里面還存在下面幾個問題幾個問題：1) 左遞歸問題左遞歸問題，例如文法，例如文法EE+T|T，如果按前面介紹的方法，如果按前面介紹的方法為為E設計分析程序，那么你會發現，這將是一個無窮遞歸的程設計分析程序，那么你會發現，這將是一個無窮遞歸的程序。實際上，當文法含有直接或間接左遞歸時，都會出現無窮序。實際上，當文法含有直接或間接左遞歸時，都會出現無窮遞歸。遞歸。2) 右部多個侯選式的第一個符號相同問題右部多個侯選式的第一個符號相同問題，即局部二義性問

17、，即局部二義性問題。例如對題。例如對Aab|a，對，對A進行分析程序設計時，根據進行分析程序設計時，根據a無法區無法區分應該選擇哪個分支，即出現局部二義性。分應該選擇哪個分支，即出現局部二義性。3) 右部侯選式的第一個符號是非終結符號右部侯選式的第一個符號是非終結符號，如，如A|時，如時，如果果和和均以非終結符開始，那么就很難決定何時使用均以非終結符開始，那么就很難決定何時使用A選選項，何時又使用項，何時又使用A選項。選項。如果右部某個侯選式為如果右部某個侯選式為或能推導或能推導出出，分析程序該如何設計。，分析程序該如何設計。 1、 左遞歸問題左遞歸問題 我們在第二章提到，不同的文法可描述相同

18、的語言，這些文法稱為等價我們在第二章提到，不同的文法可描述相同的語言，這些文法稱為等價文法。對于左遞歸問題，我們就是用等價文法來解決，即將文法中的左遞歸文法。對于左遞歸問題，我們就是用等價文法來解決，即將文法中的左遞歸去掉，改成用擴充去掉，改成用擴充BNF表示。消除直接左遞歸的方法如下：表示。消除直接左遞歸的方法如下：對形如對形如U:=x|y|.|z|Uv的直接左遞歸文法規則，用擴充的直接左遞歸文法規則，用擴充BNF表示來改寫規則表示來改寫規則，即利用元符號，即利用元符號“”和和“”來改寫規則，將規則改寫成來改寫規則，將規則改寫成U:=(x|y|.|z)v。例例4.4，有文法：，有文法：E:=

19、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修改后，我們很容易為修改后，我們很容易為E和和T設計分析程序，如圖設計分析程序，如圖4.2所示，注意所示，注意“”和和“”括起來的內容采用循環設計。括起來的內容采用循環設計。 E:=T|E+T|E-T E:=T+T|-TT:=F|T*F|T/F T:=F*F| /FETYN出口

20、出口INPUTSYM=下一個符號下一個符號INPUTSYM =+INPUTSYM =-NYTFYN出口出口INPUTSYM=下一個符號下一個符號INPUTSYM =*INPUTSYM =/NY圖4.2 E和T的分析程序 對于直接左遞歸規則的變換方法是將不含左遞歸的各選式用圓括號括起來，放對于直接左遞歸規則的變換方法是將不含左遞歸的各選式用圓括號括起來，放置在規則右部的最左端，然后將含有遞歸的侯選式中的左遞歸符號去掉，剩余置在規則右部的最左端，然后將含有遞歸的侯選式中的左遞歸符號去掉，剩余部分用花括號括起來放置在規則右部的最右端，這樣，就可將直接左遞歸規則部分用花括號括起來放置在規則右部的最右端

21、，這樣，就可將直接左遞歸規則轉變成用擴充轉變成用擴充BNF表示的等價文法。表示的等價文法。對于一般的間接左遞歸，首先要變成直接左遞歸，其消除左遞歸的算法如下：對于一般的間接左遞歸，首先要變成直接左遞歸，其消除左遞歸的算法如下：1) 把文法把文法G的非終結符號整理成某種順序：的非終結符號整理成某種順序：A1,A2,An。2) For i:=1 to n begin for j:=1 to n-1 把每個形如把每個形如Ai:=Ajr的規則用的規則用Aj的右部帶入，直到變成直接左遞歸的右部帶入，直到變成直接左遞歸假設假設Aj:= 1|2| k 帶入帶入Ai中，得中，得Ai:= 1r|2r| kr 消

22、去消去Ai直接左遞歸直接左遞歸 end3) 去掉多余規則。去掉多余規則。 例例4.5，有文法有文法GS：S:=Qc|c ，Q:=Rb|b ，R:=Sa|a，消除左，消除左遞歸。遞歸。解：該文法表面上看，沒有直接左遞歸，但因為解：該文法表面上看，沒有直接左遞歸，但因為S=Qc=Rbc =Sabc，說明存在間接左遞歸。，說明存在間接左遞歸。首先把首先把R:=Sa|a代入代入Q:=Rb|b中得：中得：Q:=Sab|ab|b再把再把Q:=Sab|ab|b代入代入S:=Qc|c中得直接左遞歸規則：中得直接左遞歸規則： S:=Sabc|abc|bc|c按消除直接左遞歸方法，最后得到的按消除直接左遞歸方法，

23、最后得到的S規則為：規則為： S:=(abc|bc|c)abc由于由于S規則中不再含有符號規則中不再含有符號Q和和R，所以，所以，Q和和R規則為多余規則，規則為多余規則，應刪除。注意：對非終結符號的排序不同，最后得到的文法在形應刪除。注意：對非終結符號的排序不同，最后得到的文法在形式上可能不同，但它們都是等價文法。消去左遞歸過程中，要注式上可能不同，但它們都是等價文法。消去左遞歸過程中，要注意保證文法的識別符號不變。意保證文法的識別符號不變。 2、解決局部二義性問題、解決局部二義性問題對于局部二義性問題，即右部多個侯選式的第一個符號相同時，對于局部二義性問題，即右部多個侯選式的第一個符號相同時

24、，可通過提取公因子、加入新的非終結符號來實現。可通過提取公因子、加入新的非終結符號來實現。假設文法中有規則為：假設文法中有規則為：U:=xV|xW ，解決辦法如下：，解決辦法如下：1) 提取公因子，將規則變成：提取公因子，將規則變成：U:=x(V|W)2）加入一個新的非終結符號加入一個新的非終結符號A，令，令A=V|W，則將規則改為：，則將規則改為： U:=xA ，A:=V|W 3、右部侯選式的第一個符號是非終結符號、右部侯選式的第一個符號是非終結符號對于這種問題，我們首先要求出每個侯選式的首符號集，然后根據各侯選對于這種問題，我們首先要求出每個侯選式的首符號集，然后根據各侯選式的首符號集內容

25、來選擇侯選式，因此，我們先看看如何確定各侯選式的式的首符號集內容來選擇侯選式，因此，我們先看看如何確定各侯選式的首符號集。首符號集。設文法設文法G是沒有左遞歸的文法，規則形式為：是沒有左遞歸的文法，規則形式為： U =|，首先求出每個侯選，首先求出每個侯選式的首符號集，即式的首符號集，即FIRST()和和FIRST()，為保證在設計子程序時能明確地，為保證在設計子程序時能明確地選擇某個侯選式，就要保證選擇某個侯選式，就要保證FIRST()FIRST()=即各個侯選式的首符號即各個侯選式的首符號集要相互不相交。集要相互不相交。若若 FIRST()，那么，那么，FIRST()FOLLOW(U)=。

26、 求出首符號集后，并保證滿足上述的不相交條件，那么，對于規則求出首符號集后，并保證滿足上述的不相交條件，那么，對于規則U =|，就可以根據下列規則來選擇侯選式：就可以根據下列規則來選擇侯選式： 設當前的輸入符號是設當前的輸入符號是a ，aVt 若若aFIRST() 或或FIRST()且且aFOLLOW(U)，則用，則用侯選式。侯選式。 若若aFIRST() 或或FIRST()且且aFOLLOW(U)，則用，則用侯選式。侯選式。1. 若若aFIRST() 且且aFIRST() ，則語法錯，轉出錯處理。，則語法錯，轉出錯處理。 如果文法中的某條規則，其侯選式的首符號集有相交時，可通如果文法中的某條

27、規則，其侯選式的首符號集有相交時，可通過改寫文法使其滿足條件。方法是通過規則帶入使侯選式的第過改寫文法使其滿足條件。方法是通過規則帶入使侯選式的第一個符號相同，然后提取公因子，并對剩余部分用新非終結符一個符號相同，然后提取公因子，并對剩余部分用新非終結符號代替。這一過程可能需要反復進行，直到規則的各侯選式的號代替。這一過程可能需要反復進行，直到規則的各侯選式的首符號集不相交。但并不是所有的規則都能用這種方法解決首首符號集不相交。但并不是所有的規則都能用這種方法解決首符號集相交問題，所以，不是所有的文法都可以采用遞歸下降符號集相交問題，所以，不是所有的文法都可以采用遞歸下降分析方法進行分析。分析

28、方法進行分析。總之，要實現沒有回溯的自頂向下分析，文法必須滿足兩個條總之，要實現沒有回溯的自頂向下分析，文法必須滿足兩個條件：件：文法是非左遞歸的。文法是非左遞歸的。1.對文法的任一非終結符號，若其規則右部有多項選擇，那么對文法的任一非終結符號，若其規則右部有多項選擇，那么各選項所推出的終結符號串的頭符號集合要兩兩不相交各選項所推出的終結符號串的頭符號集合要兩兩不相交 例例4.6，有文法，有文法GZ： Z:=AcB|Bd A:=AaB|c B:=aA|a設計遞歸下降分析程序。設計遞歸下降分析程序。解解:首先將左遞歸去掉，首先將左遞歸去掉，將規則將規則 A:=AaB|c 改成改成 A:=caB

29、提取公因子，提取公因子，將規則將規則 B := aA|a 改成改成 B := a(A|) 對于規則對于規則Z := AcB|Bd，為了設計分析程序，要求出每個選項的頭符號集，為了設計分析程序，要求出每個選項的頭符號集，即即FIRST(AcB)=c ，FIRST(Bd)=a ，分析程序如圖，分析程序如圖4.3(a)所示。所示。 改后的文法為：改后的文法為：Z := AcB|Bd , A := caB , B := a(A|)INPUTSYM=cAINPUTSYM=cINPUTSYM=下一個符號下一個符號INPUTSYM=dERRINPUTSYM=aERRINPUTSYM=下一個符號下一個符號z出

30、口出口BBNYYYYNNN圖4.3(a)Z分析程序 對于規則對于規則A := caB , 分析程序如圖分析程序如圖4.3(b)所示。所示。 對于規則對于規則B := a(A|) , FIRST(A)=c，分析程序，分析程序如圖如圖4.3(c)所示。所示。INPUTSYM=cINPUTSYM=aINPUTSYM=下一個符號下一個符號ERRINPUTSYM=下一個符號下一個符號A出口出口BYYNNINPUTSYM=aINPUTSYM=cERRINPUTSYM=下一個符號下一個符號B出口出口aYYNN圖4.3(c)B分析程序 圖4.3(b)A分析程序 TEST語言的語法規則如下：語言的語法規則如下：

31、1):=2):= | 3):=int ID;4):=| 5):= | | |6):= if () else 7):= while () 8):= for(;)第四章第四章 語法分析語法分析自頂向下分析自頂向下分析 9):=write ;10):=read ID;11):=12):=;|;13):= ID=|14):= |(|=|=|=|!=) 15):=(+|-) 16):=(*| /) 17):=()|ID|NUM其中，規則其中，規則1和規則和規則11中的符號中的符號、為終結符號，不是元符號，而規為終結符號，不是元符號，而規則則6、7、8中出現的符號中出現的符號(和和)也是終結符號，不是元符

32、號。也是終結符號，不是元符號。 第四章第四章 語法分析語法分析自頂向下分析自頂向下分析 分析程序設計如下：針對每一條規則，我們分別來設計其遞歸下降分析過程。TEST語言的語法規則基本符合遞歸下降的要求，但對于規則13:= ID=|因為的首符號可能是ID，即存在首符號集相交問題，而此時，不可能將布爾表達式規則代入，所以，在程序設計時，通過超前讀一個符號來解決。方法是：如果識別出標識符的符號ID后，再讀一個符號，如果這個符號是“=”，說明選擇的是賦值表達式；如果不是“=”，則說明選擇的是布爾表達式。其實現程序如下： 第四章第四章 語法分析語法分析自頂向下分析自頂向下分析 /:=|/:=ID=|in

33、t expression()int es=0,fileadd;char token220,token340;if (strcmp(token,ID)=0) fileadd=ftell(fp); /記住當前文件位置記住當前文件位置fscanf(fp,%s %sn, &token2,&token3);printf(%s %sn,token2,token3);if (es0) return(es);if (strcmp(token2,=)=0) /=fscanf(fp,%s %sn,&token,&token1);printf(%s %sn,token,token1)

34、; es=bool_expr(); else fseek(fp,fileadd,0); /若非若非=則文件指針回到則文件指針回到=前的標識符前的標識符printf(%s %sn,token,token1);es=bool_expr();if (es0) return(es);return(es);第四章第四章 語法分析語法分析自頂向下分析自頂向下分析 在語法分析程序的實現中，對應每條規則的分析函數的取名與規則中的符號同名，語法分析程序的名為TESTparse（），在這個函數里，調用對應與規則1的分析函數program()開始進行語法分析，其它規則的分析函數會從函數program()中遞歸調用。

35、每個分析函數都有返回值，當返回值為0時，表示這個函數的分析沒發現錯誤，如果大于0，則有錯誤。該語法分析程序沒有進行錯誤處理，一旦發現錯誤立即返回，并報告錯誤信息。完整的語法分析程序見附錄C。 4.4 LL(1)4.4 LL(1)分析方法分析方法 LL(1)分析方法也是常見的自頂向下分析，LL(1)分析使用一個下推棧而不是遞歸調用來完成分析。名稱中第一個L表示自左向右順序掃描輸入符號串，第二個L表示分析過程產生一個句子的最左推導。括號中的1表示每進行一步推導，只需要向前查看一個輸入符號，便能確定當前所應選用的規則。 LL(1)分析器由一個總控程序、一張分析表和一個分析棧組成，如圖4.4所示。 輸

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

37、關聯，即關聯，即A可以是文法中的一個非終結符號、終結符號或可以是文法中的一個非終結符號、終結符號或#；而每一列則與文；而每一列則與文法的一個終結符號或法的一個終結符號或#關聯，即關聯，即a是文法的一個終結符號或是文法的一個終結符號或#。分析表的列數是。分析表的列數是終結符號的個數加終結符號的個數加1，行數是文法中的非終結符號和終結符號的數目加，行數是文法中的非終結符號和終結符號的數目加1；分；分析表元素析表元素MA，a，指出了分析器應采取的動作。，指出了分析器應采取的動作。 分析棧分析棧：用來存放一系列文法符號。分析開始時，先將：用來存放一系列文法符號。分析開始時，先將#入棧，然后再將入棧，然

38、后再將文法的開始符號入棧。文法的開始符號入棧。 輸出流輸出流：分析過程中使用的產生式序列。：分析過程中使用的產生式序列。 總控程序總控程序：分析器對輸入串的分析靠總控程序完成分析器對輸入串的分析靠總控程序完成. .根據分析棧的棧頂符根據分析棧的棧頂符號號X X和當前的輸入符號，總控程序按照分析表的指示來決定分析器的動作和當前的輸入符號，總控程序按照分析表的指示來決定分析器的動作. .工工作過程如下：作過程如下： 1) 分析開始時，首先將符號#及文法的開始符號S依次置于分析棧的底部，并把各指示器調整至起始位置，如圖4.5所示。然后，反復執行第二步的操作。 輸入符號串： a1a2an#分析棧： S

39、#圖4.5分析開始時狀況 2) 假設分析的某一步，分析棧及余留的符號串如圖4.6，則根據棧頂的符號Xm，采取下列動作： aiAi+1 an#X1X2Xm-1Xm 圖4.6分析進行中的狀況 (1)若XmVn，則查分析表的Xm行ai列，假設MXm，ai為POP，PUSH（WVU），則將Xm出棧，并將WVU反序入棧，這意味著使用了規則XmUVW，如圖4.7；若MXm，ai為空或ERROR，則出錯。 aiAi+1 an#X1X2Xm-1WUV 圖4.7 UVW反序入棧 (2)若Xm=ai#，表示棧頂與掃描的符號匹配，則查分析表為POP，NEXTSYM，則棧頂符號Xm出棧，輸入指針指向下一個符號。 (

40、3 ) 若Xm=ai=#，表示輸入串完全匹配，分析成功。 考慮算術表達式文法ETE，E+TE，E，TFT，T*FT，T，F(E)|i，該文法的分析表如表4.1所示。表4.1 算術表達式分析表 符號 輸入符號 i+*()#EETTFi+*()#POP,PUSH(ET) POP,PUSH(TF) POP,PUSH( i )POP,NEXTSYM POP,PUSH(ET+) POP POP,NEXTSYM POP,PUSH( TF* ) POP,NEXTSYM POP,PUSH(ET) POP,PUSH(TF) POP,PUSH( )E( ) POP,NEXTSYM POP POP POP,NEXT

41、SYM POP POP ACCEPT 表4.1 算術表達式分析表 表中元素POP為過程，功能是將棧頂元素從棧內彈出。PUSH()為過程，其中V+ ,功能是將壓棧。NEXTSYM為讀符號過程，將讀符號指針指向下一個符號。ACCEPT表示分析成功，輸入符號串語法正確。表中空白處表示錯誤入口，應該調用錯誤處理程序。 例4.7，根據表4.1給出的分析表，對符號串i+i*i進行分析。解：根據分析表以及LL(1)的工作過程，對符號串i+i*i的分析過程在表4.2中列出。表4.2 符號串i+i*i的分析過程步驟分析棧余留輸入串分析表元素所用產生式1234567891011121314151617 #E#ET

42、#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# # POP,PUSH(ET)POP,PUSH(TF)POP,PUSH(i)POP,NEXTSYMPOPPOP,PUSH(ET+)POP,NEXTSYMPOP,PUSH(TF)POP,PUSH(i)POP ,NEXTSYMPOP,PUSH(TF*)POP ,NEXTSYMPOP,PUSH(i)POP ,NEXTSYMPOPPOPaccept ETETFTFi TE+TE T

43、FTFi T*FT Fi TE表4.2中輸出的產生式序列構成對輸入符號串的最左推導。按此產生式序列構造輸入符號串i+i*i的最左推導過程如下：E = TE = FTE = iTE = iE = i+TE = i+FTE= i+iTE = i+i*FTE = i+i*iTE = i+i*iE = i+i*i 對于不同的LL(1)文法，LL(1)的分析算法是相同的，不同的僅僅是分析表。顯然，如何根據文法來構造分析表是LL(1)分析的關鍵。 對于任意給定的已化簡的文法G，為了構造分析表，首先我們要求出每個非終結符號的FOLLOW集合和每個后選式的FIRST集合。然后對文法G中的每個產生式A，按下列規

44、則確定分析表中的元素M： 1) 對FIRST()中的每個終結符a，置MA，a=“POP，PUSH()”，其中為的倒置。2) 若FIRST()，則對屬于FOLLOW(A)的每個符號b(b為終結符或#)，置MA，b=“POP”。3) 把M中的所有Ma，a置為“POP，NEXTSYM”。4) 把M中所有不按規則1、2定義的元素均置為空或“ERROR”。 例如，有文法ETE，E+TE，E，TFT，T*FT，T，F(E)|i，對規則ETE：FIRST(TE)= (，i)，那么在分析表的符號E所在的行、符號(和i所在的列對應的位置分別填入“POP,PUSH(ET)”,見表4.1的E行。對規則E+TE：FI

45、RST(+TE)=+，在符號E行符號+列對應的位置填入“POP,PUSH(ET+)” ，見表4.1的E行。對規則E：因為FIRST()，FOLLOW(E)=，#，所以在符號E行符號)和#列對應的位置填入“POP”，見表4.1的E行。對于一個文法，若按上述方法構造的分析表M不含多重定義，則稱它是一個LL(1)文法。 符號 輸入符號 i+*()#EETTFPOP,PUSH(ET) POP,PUSH(TF) POP,NEXTSYM POP,PUSH(ET),NEXTSYM POP POP,PUSH( TF ),NEXTSYM POP,PUSH(ET) POP,PUSH(TF) POP,PUSH( )

46、E ),NEXTSYM POP POP POP POP 1、左遞轉成右遞歸、左遞轉成右遞歸 LL(1)分析不能處理左遞歸文法，但也不能像遞歸下降分析那樣將左遞歸改為采用擴充BNF表示。在LL(1)分析中，必須將左遞歸文法變成右遞歸文法，其變換方法如下：1） 對形如U:=x|y|z|Uv的直接左遞歸文法規則，增加一個新的非終結符號U，令U為左遞歸規則中的不含左遞歸符號的部分加上新的非終結符號U，即U:= (x|y|.|z )U。2） 新的非終結符號U有兩個侯選式，一為含左遞歸符號的部分去掉含左遞歸符號，再加上新的非終結符號U，即U:=vU。另一個為，即U:=。按上面的兩步，我們就可將左遞歸規則改成等價的右遞歸規則。 例如，對左遞歸規則EE+T|T，如果像遞歸下降分析那樣改成 ET+T無法形成逆序入棧，但可改成右遞歸：令E為新的非終結符號，則等價的右遞歸規則為：ETE，E+TE| 實際上，在遞歸下降分析方法中，也可將左遞歸規則改成右遞歸進行處理。 2、解決分析表多重定義問題、解決分析表多重定義問題若一個LL(1)文法的分析表不出現多重定義，當且僅當對于文法G的每個非終結符A的任何兩條不同規則A| ，下面條