語法分析——自頂

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

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

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

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

5、1)，將，將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 i) )，則將，則將符號加進(jìn)符號加進(jìn)FIRST()FIRST()。 例例4.1，有，有文法文法 ETE E+TE E TFT T*FT T F(E)|i求文法中非終結(jié)符號以求文法中非終結(jié)符號以及符號串的及符號串的FIRST集。集。解：首先求各符號的解：首先求各符號的FIRST集：該文法共有集：該文法共有非終結(jié)符號為非終結(jié)符號為

6、E，E，T，T，F(xiàn)FIRST(E)=FIRST(T)=FIRST(F)= ( ，i FIRST(E)= + ，F(xiàn)IRST(T)= * ，下面求文法中各產(chǎn)生式右部符號串的下面求文法中各產(chǎn)生式右部符號串的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的任何非的任何非終結(jié)符號終結(jié)符號A，則：，則： FOLL

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

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

9、FOLLOW集定義求各非終結(jié)符號的集定義求各非終結(jié)符號的FOLLOW集：集： FOLLOW(E)= )，#，F(xiàn)OLLOW(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 遞歸下降分析遞歸下降分析 遞歸下降分析的基本方法遞歸下降分析的基本方法遞歸下降分析的概念極為簡單，其方法是將文法中的每一個非終結(jié)符遞歸下降分析的概念極為

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

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

12、成分的子程序匹配輸入串成功，且正確返回時，該語法成分才算真正獲得識別。時，該語法成分才算真正獲得識別。 例例4.3，考慮文法，考慮文法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ī)則規(guī)則的識別。對于規(guī)則Z:=(U)|aUb，右部有兩個候選式，因此，右部有兩個候選式，因此，U的識別的識別過程有兩個分支，分別根據(jù)符號過程有兩個分支，分別

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

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

15、程序的右邊分支，表示選擇了子程序的右邊分支，表示選擇了Z:=aUb規(guī)則。讀下一個符號，規(guī)則。讀下一個符號，使使inputsym=d，調(diào)，調(diào)U子程序，因子程序，因INPUTSYM=e，所以，讀下一個符號，使，所以，讀下一個符號，使INPUTSYM=b，表示使用，表示使用U:=e規(guī)則，并返回調(diào)用程序規(guī)則，并返回調(diào)用程序Z子程序右邊分支子程序右邊分支U的的下方，接著判斷下方，接著判斷INPUTSYM=b，讀下一個符號，并退出，讀下一個符號，并退出Z，分析過程結(jié)束，分析過程結(jié)束，從而判定輸入串從而判定輸入串a(chǎn)eb語法分析成功。這個過程相當(dāng)于構(gòu)造了如下推導(dǎo)過程：語法分析成功。這個過程相當(dāng)于構(gòu)造了如下推導(dǎo)

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

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

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

19、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|F 可改成可改成 T:=F*F| /F修改后，我們很容易為修改后，我們很容易為E和和T設(shè)計(jì)分析程序，如圖設(shè)計(jì)分析程序，如圖4.2所示，注意所示，注意“”和和“”括起來的內(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| /FETYN出口

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

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

22、去消去Ai直接左遞歸直接左遞歸 end3) 去掉多余規(guī)則。去掉多余規(guī)則。 例例4.5，有文法有文法GS：S:=Qc|c ，Q:=Rb|b ，R:=Sa|a，消除左，消除左遞歸。遞歸。解：該文法表面上看，沒有直接左遞歸，但因?yàn)榻猓涸撐姆ū砻嫔峡矗瑳]有直接左遞歸，但因?yàn)镾=Qc=Rbc =Sabc，說明存在間接左遞歸。，說明存在間接左遞歸。首先把首先把R:=Sa|a代入代入Q:=Rb|b中得：中得：Q:=Sab|ab|b再把再把Q:=Sab|ab|b代入代入S:=Qc|c中得直接左遞歸規(guī)則：中得直接左遞歸規(guī)則： S:=Sabc|abc|bc|c按消除直接左遞歸方法，最后得到的按消除直接左遞歸方法，

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

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

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

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

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

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

29、提取公因子，提取公因子，將規(guī)則將規(guī)則 B := aA|a 改成改成 B := a(A|) 對于規(guī)則對于規(guī)則Z := AcB|Bd，為了設(shè)計(jì)分析程序，要求出每個選項(xiàng)的頭符號集，為了設(shè)計(jì)分析程序，要求出每個選項(xiàng)的頭符號集，即即FIRST(AcB)=c ，F(xiàn)IRST(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分析程序 對于規(guī)則對于規(guī)則A := caB , 分析程序如圖分析程序如圖4.3(b)所示。所示。 對于規(guī)則對于規(guī)則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語言的語法規(guī)則如下：語言的語法規(guī)則如下：

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其中，規(guī)則其中，規(guī)則1和規(guī)則和規(guī)則11中的符號中的符號、為終結(jié)符號，不是元符號，而規(guī)為終結(jié)符號，不是元符號，而規(guī)則則6、7、8中出現(xiàn)的符號中出現(xiàn)的符號(和和)也是終結(jié)符號，不是元符

32、號。也是終結(jié)符號，不是元符號。 第四章第四章 語法分析語法分析自頂向下分析自頂向下分析 分析程序設(shè)計(jì)如下：針對每一條規(guī)則，我們分別來設(shè)計(jì)其遞歸下降分析過程。TEST語言的語法規(guī)則基本符合遞歸下降的要求，但對于規(guī)則13:= ID=|因?yàn)榈氖追柨赡苁荌D，即存在首符號集相交問題，而此時，不可能將布爾表達(dá)式規(guī)則代入，所以，在程序設(shè)計(jì)時，通過超前讀一個符號來解決。方法是：如果識別出標(biāo)識符的符號ID后，再讀一個符號，如果這個符號是“=”，說明選擇的是賦值表達(dá)式；如果不是“=”，則說明選擇的是布爾表達(dá)式。其實(shí)現(xiàn)程序如下： 第四章第四章 語法分析語法分析自頂向下分析自頂向下分析 /:=|/:=ID=|in

33、t expression()int es=0,fileadd;char token220,token340;if (strcmp(token,ID)=0) fileadd=ftell(fp); /記住當(dāng)前文件位置記住當(dāng)前文件位置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); /若非若非=則文件指針回到則文件指針回到=前的標(biāo)識符前的標(biāo)識符printf(%s %sn,token,token1);es=bool_expr();if (es0) return(es);return(es);第四章第四章 語法分析語法分析自頂向下分析自頂向下分析 在語法分析程序的實(shí)現(xiàn)中，對應(yīng)每條規(guī)則的分析函數(shù)的取名與規(guī)則中的符號同名，語法分析程序的名為TESTparse（），在這個函數(shù)里，調(diào)用對應(yīng)與規(guī)則1的分析函數(shù)program()開始進(jìn)行語法分析，其它規(guī)則的分析函數(shù)會從函數(shù)program()中遞歸調(diào)用。

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

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

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

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

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

40、3 ) 若Xm=ai=#，表示輸入串完全匹配，分析成功。 考慮算術(shù)表達(dá)式文法ETE，E+TE，E，TFT，T*FT，T，F(xiàn)(E)|i，該文法的分析表如表4.1所示。表4.1 算術(shù)表達(dá)式分析表 符號 輸入符號 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 算術(shù)表達(dá)式分析表 表中元素POP為過程，功能是將棧頂元素從棧內(nèi)彈出。PUSH()為過程，其中V+ ,功能是將壓棧。NEXTSYM為讀符號過程，將讀符號指針指向下一個符號。ACCEPT表示分析成功，輸入符號串語法正確。表中空白處表示錯誤入口，應(yīng)該調(diào)用錯誤處理程序。 例4.7，根據(jù)表4.1給出的分析表，對符號串i+i*i進(jìn)行分析。解：根據(jù)分析表以及LL(1)的工作過程，對符號串i+i*i的分析過程在表4.2中列出。表4.2 符號串i+i*i的分析過程步驟分析棧余留輸入串分析表元素所用產(chǎn)生式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中輸出的產(chǎn)生式序列構(gòu)成對輸入符號串的最左推導(dǎo)。按此產(chǎn)生式序列構(gòu)造輸入符號串i+i*i的最左推導(dǎo)過程如下：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)的分析算法是相同的，不同的僅僅是分析表。顯然，如何根據(jù)文法來構(gòu)造分析表是LL(1)分析的關(guān)鍵。 對于任意給定的已化簡的文法G，為了構(gòu)造分析表，首先我們要求出每個非終結(jié)符號的FOLLOW集合和每個后選式的FIRST集合。然后對文法G中的每個產(chǎn)生式A，按下列規(guī)

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

45、RST(+TE)=+，在符號E行符號+列對應(yīng)的位置填入“POP,PUSH(ET+)” ，見表4.1的E行。對規(guī)則E：因?yàn)镕IRST()，F(xiàn)OLLOW(E)=，#，所以在符號E行符號)和#列對應(yīng)的位置填入“POP”，見表4.1的E行。對于一個文法，若按上述方法構(gòu)造的分析表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、左遞轉(zhuǎn)成右遞歸、左遞轉(zhuǎn)成右遞歸 LL(1)分析不能處理左遞歸文法，但也不能像遞歸下降分析那樣將左遞歸改為采用擴(kuò)充BNF表示。在LL(1)分析中，必須將左遞歸文法變成右遞歸文法，其變換方法如下：1） 對形如U:=x|y|z|Uv的直接左遞歸文法規(guī)則，增加一個新的非終結(jié)符號U，令U為左遞歸規(guī)則中的不含左遞歸符號的部分加上新的非終結(jié)符號U，即U:= (x|y|.|z )U。2） 新的非終結(jié)符號U有兩個侯選式，一為含左遞歸符號的部分去掉含左遞歸符號，再加上新的非終結(jié)符號U，即U:=vU。另一個為，即U:=。按上面的兩步，我們就可將左遞歸規(guī)則改成等價的右遞歸規(guī)則。 例如，對左遞歸規(guī)則EE+T|T，如果像遞歸下降分析那樣改成 ET+T無法形成逆序入棧，但可改成右遞歸：令E為新的非終結(jié)符號，則等價的右遞歸規(guī)則為：ETE，E+TE| 實(shí)際上，在遞歸下降分析方法中，也可將左遞歸規(guī)則改成右遞歸進(jìn)行處理。 2、解決分析表多重定義問題、解決分析表多重定義問題若一個LL(1)文法的分析表不出現(xiàn)多重定義，當(dāng)且僅當(dāng)對于文法G的每個非終結(jié)符A的任何兩條不同規(guī)則A| ，下面條