編譯原理自頂向下語法分析法

1、第四章 自頂向下語法分析方法語法分析是編譯過程的核心部分。語法分析的任務(wù)是：按照文法，從源程序符號串中識別出各類語法成份，同時進(jìn)行語法檢查，為語義分析和代碼生成作準(zhǔn)備。執(zhí)行語法分析任務(wù)的程序稱為分析程序。也稱為語法分析器，它是編譯程序的主要子程序之一。在第二章中我們已經(jīng)介紹過。通過語法分析可建立起相應(yīng)的語法樹。按語法樹的建立方法，我們將語法分析方法分成兩大類，即自頂向下分析和自底向上分析。下面，我們先介紹自頂向下分析。本章重點(diǎn)：自頂向下分析、LL（1）分析，然后再介紹自底向上分析。第一節(jié) 自頂向下分析方法一、帶回溯的自頂向下分析算法這是自頂向下分析的一般方法，即對任一輸入符號串，試圖用一切可能

2、的方法，從識別符號出發(fā)，根據(jù)文法自上而下地為輸入串建立一棵語法樹。下面用一個簡單例子來說明這種過程：假定有文法GS：Scd Aab|a 以及輸入串w=cad為了自上而下地構(gòu)造w的語法樹，我們首先按文法的識別符號產(chǎn)生根結(jié)點(diǎn)S，并讓指示器IP指adcASbadcASdcAS向輸入串的第一符號c。然后，用S的規(guī)則（此處左部為S的規(guī)則僅有一條）把這棵樹發(fā)展為 （ a） （b） （c） 圖3-1-1圖3-1-1a圖。我們希望用S的子結(jié)從左至右匹配整個輸入串w。首先，此樹的最左子結(jié)是終結(jié)符c為標(biāo)志的子結(jié)，它和輸入串的第一個符號相匹配。于是，我們就把IP調(diào)整為指向下一輸入符號a，并讓第二個子結(jié)A去進(jìn)行匹配，

3、非終結(jié)符A有二個選擇，我們試著用它的第一個選擇去匹配輸入串，于是把語法樹發(fā)展為圖3-1-1b圖。子樹A的最左子結(jié)和IP所指的符號相符，然后我們再把IP調(diào)為指向下一符號d并讓A的第二個子結(jié)進(jìn)入工作。但A的第二個子結(jié)為終結(jié)符號b，與IP當(dāng)前指的符號d不一致。因此，A宣告失敗。這意味著A的第一個選擇此刻不適用于構(gòu)造w的語法樹。這時，我們應(yīng)該回頭（回溯）看A是否還有別的選擇。為了實現(xiàn)回溯，我們一方面應(yīng)把A的第一個選擇所生長的子樹注銷掉；另一方面，應(yīng)把IP恢復(fù)為進(jìn)入A時的原值，也就是讓它重新指向第二輸入符號a?，F(xiàn)在我們試探用A的第二個選擇，即考慮生成圖3-1-1c的語法樹。由于子樹A只有一個子結(jié)a，而且

4、，它和IP所指的符號相一致，于是，A完成了匹配任務(wù)。在A獲得匹配后，指示器指向下一個未被觸及的符號d。在S的第二子結(jié)A完成匹配后，接著就輪到第三個子結(jié)d進(jìn)行工作。由于這個子結(jié)和最后一個輸入符號相符，于是，我們完成了構(gòu)造語法樹的任務(wù)，證明了w是文法G s的一個句子。上述自頂向下地為輸入符號w建立語法樹的過程，實際上也是設(shè)法建立一個最左推導(dǎo)序列，以便通過一步步推導(dǎo)將輸入串推導(dǎo)出來。很明顯，對于輸入串w可以通過如下的推導(dǎo)過程將其推導(dǎo)出來：Sc A da bW：cad 2p指示口SCAdcad所以用最左推導(dǎo)，是因為我們對輸入串是自左向右掃描的，只有使用最左推導(dǎo)，才能保證按掃描順序去匹配輸入串。在上述推

5、出符號串w的過程中，由于出現(xiàn)在符號串中的非終結(jié)符號只有一個，因此，未明顯地表現(xiàn)出最左推導(dǎo)的性質(zhì)。根據(jù)以上分析，不難編出程序來實現(xiàn)這種分析的算法。但是，上述這種自頂向下的分析算法存在著一定的困難和缺點(diǎn)。困難表現(xiàn)在不能為左遞歸文法構(gòu)造自頂向下的語法分析器（上述所舉例子的文法Gs是不具有在遞歸性的）。缺點(diǎn)主要表現(xiàn)在存在著回溯問題。當(dāng)然，應(yīng)用帶回溯的自頂向下的分析算法還必須將文法規(guī)則存放于內(nèi)存。下面將具體介紹這種分析算法所存在的問題及其解決辦法。二、存在問題及解決辦法（一）左遞歸問題自頂向下分析法只有規(guī)則排列得合適時，才能正確工作。該法的一個基本缺點(diǎn)是不能處理具有左遞歸的文法。如下所示。AAB|BbB

6、Ac|dAa    BA CB bA C如：直接左遞歸 和 間接左遞歸AABACcBbACcSSa|bSSaSaSaSaAaAB|BbBAc|d無法確定語法樹的終止，清除直接左遞歸的較好方法是改改為右遞歸如：SSa|b 改為SbSSaS|一般情況下，直接左遞歸的形式可為：消除AA1|A2| Am|1|2n清除左遞歸后改寫為：A1A1|2A1 |nA1A11A|2A1 |mmA1|對于間接左遞歸的消除，需先將間接左遞歸變?yōu)橹苯幼筮f歸，然后再接上述方法消除。條件是文法中無AA的有害規(guī)則和 或A的空產(chǎn)生式算法：SQc|cQRb|b SSabc 排列R、Q、SR代入Q，Q

7、Sab|ab|bQ代入S，SSabc|abc|bc|cS（abc|bc|c）SSabc S|QRb|bRSa|a（二）回溯 問題 當(dāng)產(chǎn)生式都有多個選擇時，選那個輸入串去匹配為了避免回溯，就必須保證：對文法的任何非終結(jié)符號特別是規(guī)則都右部有多個選擇的非終結(jié)符號，當(dāng)用它去匹配輸入串時，應(yīng)是確定無疑的。即：U11|22|nn該規(guī)則右部有n個選擇,為了實現(xiàn)目的,我們對文法的要求是:F1rstIRST（i）f1rstFIRST（j）=（ij）定義1：設(shè)G=（VT，VN，S，P）是上下文無關(guān)文法FIRST（）=a| Þa，aVT，V*若Þ，則規(guī)定FIRST（）即對文法中的任意一個非終符

8、號，其規(guī)則右部有多個選擇時，那么，由各個選擇所推出的終結(jié)符號串的頭符號集合要兩兩不相交。這樣，就可能根據(jù)當(dāng)時讀進(jìn)的符號是屬于哪個選擇的FIRST（），來唯一地確定應(yīng)該選用哪個選擇來匹配輸入串。如當(dāng)前的輸入符號為b(bVT)，若bFIRST（i），則用第i個選擇；若b不FIRST（i），其中i=1n，則語法錯，轉(zhuǎn)出錯處理。這樣就避免了分析過程的回溯。若文法的任一非終結(jié)符號，其規(guī)則右部的各個選擇所能推出的終結(jié)符號串的頭符號集合不滿足兩兩相交的條件時，那么，要構(gòu)造一個不帶回溯的自頂向下的語法分析程序，需要采取什么措施呢？一般可采取改寫文法的辦法來解決。定義1：設(shè)G=（VT，VN，S，P）是上下文無關(guān)

9、文法F1RST（）=|Þ，VT，V*若Þ，則規(guī)定F1RST（）（三）改寫文法， 當(dāng)文法不滿足，可改寫文法提因子a1a2aian#  X 分析棧  #圖4-2-1總控程序分析表mUxv|xw Ux(vx|w)提因子三、遞歸子程序法此方法的主要做法是：對文法中每個非終結(jié)符號U（它們都分別代表一種語法成分）,都編出一個子程序，以完成該非終結(jié)符號所對應(yīng)的語法成分的分析和識別任務(wù)。某個非終結(jié)符號的語法分析子程序的功能是：用該非終結(jié)符號的規(guī)則的右部符號串去匹配輸入串。分析過程是按文法規(guī)則自頂向下一級一級地分配任務(wù)，即調(diào)用有關(guān)的子程序來完成。當(dāng)編譯程序根據(jù)文法和當(dāng)前輸

10、入符號預(yù)測到下一個語法成分為U時，即預(yù)測到待匹配的輸入符號串可以為從U出發(fā)所推導(dǎo)出的符號串相匹配時，就確定U為目標(biāo)，并調(diào)用分析和識別U的子程序。在分析和識別U的過程中，有可能還要確立其他子目標(biāo)并調(diào)用相應(yīng)的子程序，只有在被調(diào)用的分析和識別某語法成分的子程序匹配輸入串成功并正確返回時，該語法成分才算真正的獲得了識別，并確定輸入串無語法錯誤。由于這種分析方法的特點(diǎn)是帶有預(yù)測性的，并在分析過程中對著一個目標(biāo)，所以，稱為預(yù)測的和面向目標(biāo)的。下面，我們簡單討論一下，為什么針對某些非終結(jié)符號所編出的分析程序要編成遞歸子程序??；卮鸷芎唵?，因為文法具有遞歸性。前面已講過，自頂向下分析不能處理左遞歸文法，若有左

11、遞歸，則應(yīng)改寫文法予以消除。但是，消除了左遞歸不等于消除了文法的所有遞歸性質(zhì)，此時，文法仍可以有右遞歸性或自嵌入性。如在文法中有規(guī)則UU或UU此仍為遞歸規(guī)則，故分析U的子程序要編成遞歸子程序。因為該子程序在用規(guī)則右部符號串去匹配輸入串的過程中，又要調(diào)用U自己。即在通過該子程序正常出口返回調(diào)用程序以前，又要重新直接進(jìn)入該子程序，這就是直接遞歸。此外，還有間接遞歸，如在文法中有規(guī)則：UV VUW那么UÞVÞUW即UUW在該情況下，在分析U的子程序中要調(diào)用分析V的子程序；而在分析U的子程序中又要調(diào)用分析V的子程序。這樣，對U的分析程序就要編成遞歸子程序，因在進(jìn)入U的分析程序以后，

12、在返回調(diào)用程序以前，又可能間接地進(jìn)入自己。下面，我們舉兩個例子，說明如何根據(jù)文法來構(gòu)造該文法的語法分析程序。例1 文法GZZ（U）|aUbUdZ|Ud|e（4-7）文法有左遞歸，所以，首先要改寫文法：Z（U）|aUbU（dZ|e）d（4-8）由分析可知，經(jīng)改寫之后的文法左遞歸；上述兩條規(guī)則，其右部均各有兩個選擇，但兩個選擇各自所推出的終結(jié)符號串的頭符號集合不相交，即：（a=de=所以，文法滿足構(gòu)造一個不帶回溯的自頂向下分析器的條件。故我們可對文法中的兩個非終結(jié)符號分別編出其分析子程序。且由于有：Z Z 和 U U所以，都要編成遞歸子程序。我們以框圖形式給出這兩個子程序，見圖4.2SSFSSFF

13、F遞歸入口(SYM)=（？讀符號U(SYM)=（？出錯讀符號遞歸出口(SYM)=a？讀符號U(SYM)=b？出錯(a) 非終結(jié)符Z的分析程序SSSFF遞歸入口(SYM)=d？讀符號Z(SYM)=d？讀符號遞歸出口(SYM)=e讀符號出錯(b) 非終結(jié)符U的分析程序圖4.2圖中，除要調(diào)用遞歸入口和遞歸出口兩個子程序（這兩個子程序后面介紹）此外，還要調(diào)用讀符號和出錯處理子程序。讀符號子程序的功能是：掃描下一個符號，并把它放在全程單元SYM中。出錯處理子程序：當(dāng)分析過程中發(fā)現(xiàn)有語法錯誤時，就調(diào)用出錯處理程序，用它打印錯誤信息和跳過一段源程序。關(guān)于錯誤處理，我們將在第九章中專門討論。當(dāng)子程序調(diào)用時，在

14、讀下一個符號方面，要注意銜接的正確性。我們約定：當(dāng)調(diào)用某個子程序時，它所要分析的第一個符號已經(jīng)讀進(jìn)單元SYM中；同樣地，在從子程序返回報告成功之前，已經(jīng)把跟在分析過的子符號串之后的那個符號讀進(jìn)SYM中了。上述兩個子程序的框圖就是按此約定畫出的。第二節(jié) LL(1)分析方法a1a2aian#  X 分析棧  #圖4-2-1圖4-2-1總控程序分析表m本節(jié)，我們將介紹實現(xiàn)自頂向下分析的另一種方法，即所謂LL(1)分析方法。如此命名該分析方法的原因在于相應(yīng)的語法分析將按自左至右的順序掃描輸入符號串，并在此過程中產(chǎn)生一個句子的最左推導(dǎo)。至于括號中的“1”，則表示在分析過程中，每進(jìn)行一

15、步推導(dǎo)，只要向前查看一個輸入符號，便能確定當(dāng)前所應(yīng)選用的產(chǎn)生式（規(guī)則）。因此，我們通常把按上述方法執(zhí)行語法分析任務(wù)的程序稱為LL(1)分析程序或LL(1)分析器，使用這種方法進(jìn)行語法分析，可借助于一張分析表及一個語法分析棧，在一個總控程序控制下很方便地實現(xiàn)。下面，我們將首先介紹LL(1)分析器的邏輯結(jié)構(gòu)和工作過程，然后再介紹LL(1)分析器的構(gòu)造方法。（一）LL(1)分析器的邏輯結(jié)構(gòu)及工作過程在邏輯上，一個LL(1)分析器由一個總控程序、一張分析表和一個分析棧組成，如圖4-2-1所示。其中：1、“輸入”即待分析的符號串（注意，#VT，我們之所以在輸入串的末尾放置一個#，僅為了分析算法格式的統(tǒng)一

16、）。2、分析表M可用一個矩陣（或二維數(shù)組）來表示，它概括了相應(yīng)文法的全部信息。矩陣的每一行與文法的一個非終結(jié)符號A相關(guān)聯(lián)，而每一列則與文法的一個終結(jié)符號或#相關(guān)聯(lián)。分析表元素MA, a或者指示了當(dāng)前推導(dǎo)所應(yīng)使用的產(chǎn)生式，或者指出了輸入串中含有語法錯誤。分析器對每一輸入串的分析在總控程序控制下進(jìn)行。其算法如下（為書寫方便。在下面的敘述中，我們將分析棧按順時鐘旋轉(zhuǎn)九十度）：第一步 分析開始時，首先將符號#及文法的開始符號S依次置于分析棧底部，并把各指示器調(diào)整至起始位置，即初始格局為 # S a1a2an#分析棧 輸入串然后，反復(fù)執(zhí)行第二步所列的工作。第二步 設(shè)在分析的某一步，分析棧及余留的輸入符號

17、串處于如下的格局 aiai+1 # X1 X2Xm-1 Xm其中，X1，X2，Xm為分析過程中所得的文法符號，此時，可視棧頂符號Xm的不同情況，分別做如下的動作： ai ai+1 # X1 X2Xm-1 Xm WVU1、若XmVN，則以Xm及ai組成符號對（Xm, ai）查分析表M，設(shè)MXm, ai為一產(chǎn)生式，譬如說XmUVW，此時將Xm從分析棧中退出，并將UVW按反序推入棧中（即用該產(chǎn)生式推導(dǎo)一步），從而得到新的格局但若MXm, ai=“ERROR”，則調(diào)用出錯處理程序進(jìn)行處理；2、若Xm=ai#，則表明棧頂符號已與當(dāng)前正掃視的輸入符號得到匹配，此時應(yīng)將Xm（即ai）從棧中退出，并將輸入符號

18、指示器向前推進(jìn)一個位置；3、若Xm=ai=#，則表明輸入串已完全得到匹配，此時即可宣告分析成功而結(jié)束分析工作。順便提及，在上述分析過程的每一步，可視需要附加相應(yīng)的的語義處理工作。例 考慮文法GE：ETE' E'+TE'| T'*FT'|F(E)|Ii TFT' 相應(yīng)的分析表如圖4-2-2所示（其構(gòu)造方法，在后面敘述）?，F(xiàn)以輸入符號串i+i*i為例，列出利用上述算法對此符號串的分析過程如圖4-2-3所示。i+*()#EETE'ETE'E'E'+TE'E'E'TTFT'TFT'T

19、'T'T'*FT'T'T'F FiF(E)圖4-2-2步驟 分析棧 余留輸入串所用產(chǎn)生式 1 # E i+i*i# ETE' 2 # E'T i+i*i# TFT' 3 # E'T'F i+i*i# Fi 4 # E'T'i i+i*i# 5 # E'T'  +i*i# T' 6 # E'  +i*i# E'+TE' 7 # E'T+  +i*i# 8 # E'T  i*i# T'

20、FT' 9 # E'T'F  i*i# Fi 10 # E'T'i i*i# 11 # E'T' *i# T'*FT' 12 # E'T'F* *i# 13 # E'T'F  i# Fi 14 # E'T'i  i# 15 # E'T'  # T' 16 # E'  # E' 17 #  # 成功圖4-2-3步驟 分析棧 余留輸入串所用產(chǎn)生式 1 # E i

21、+i*i# ETE' 2 # E'T i+i*i# TFT' 3 # E'T'F i+i*i# Fi 4 # E'T'i i+i*i# 5 # E'T'  +i*i# T' 6 # E'  +i*i# E'+TE' 7 # E'T+  +i*i# 8 # E'T  i*i# T'FT' 9 # E'T'F  i*i# Fi 10 # E'T'i i*i# 11 # E&

22、#39;T' *i# T'*FT' 12 # E'T'F* *i# 13 # E'T'F  i# Fi 14 # E'T'i  i# 15 # E'T'  # T' 16 # E'  # E' 17 #  # 成功圖4-2-3（二）LL(1)分析表的構(gòu)造方法 上述LL(1)分析算法對于不同的LL(1)文法都是相同的。也就是說，是說，對不同的LL(1)分析器而言，它們的總控程序都是相同的，不同的僅僅是分析表。再者總控程序十分簡

23、單，非常容易實現(xiàn)，所以我們只著重討論構(gòu)造分析表的問題。為了構(gòu)造分析表，我們需要預(yù)先定義和構(gòu)造兩個與文法有關(guān)的集合FIRST和FOLLOW。假定是文法G的任一符號串，或者說(VTUTN)*，我們定義：FIRST()= a | a, aVT特別是，若 ，則規(guī)定FIRST()，換句話說，F(xiàn)IRST()是從可能推導(dǎo)出的所有開頭終結(jié)符號或可能的。假定S是文法的開始符號，對于G的任何非終結(jié)符A，我們定義：FOLLOW(A)=a|SA a，aVT特別是，若SA，則規(guī)定#FOLLOW(A)。換句話說，F(xiàn)OLLOW(A)是所有句型中出現(xiàn)在緊接A之后的終結(jié)符或#。下面，我們將首先給出構(gòu)造集合FIRST及FOLLO

24、W的算法，然后再給出構(gòu)造分析表的算法。（三）1、計算F1RST集根據(jù)定義計算由定義 FIRST（）=a| a aVT 、 V*,若，則規(guī)定FIRST()對每一文法符號XV計算FIRST(X)。（a）若XVT,則FIRST(X)=x（b）若XVN,且有產(chǎn)生式Xa,aFIRST(X)。（c）若XVN,X,則FIRST(X)。（d）若XVN,Y1,Y2,，Yi都VN,而有產(chǎn)生式XY1Y2Yn。當(dāng)Y1,Y2,，Yi-1都時，（其中1in），則FIRST(Y1),FIRST(Y2),，F(xiàn)IRST(Yi-1),FIRST(Yi)都包含在FIRST(X)中。（e）當(dāng)（d）中所有Yi，(i=1,2,n)則FI

25、RST(X)=FIRST(Y1)FIRST(Y2)FIRST(Yn)。反復(fù)使用上述(b)(e)步直到每個符號的FIRST集合不再增大為止。求出每個文法符號的FIRST集合后也就不難求出一個符號串的FIRST集合。 (四)2、計算FOLLOW集1）根據(jù)定義計算對文法中每一AVN計算FOLLOW(A)(a) 設(shè)S為文法中開始符號，把#加入FOLLOW (S)中(這里“#”為句子括號)。(b) 若AB是一個產(chǎn)生式，則把FIRST()的非空元素加入FOLLOW（B）中。如果則把FOLLOW（A）也加入FOLLOW（B）中，因為當(dāng)有形如：D1A1AB的產(chǎn)生式時,A, B, DVN, , 11,

26、 ,V*,在推導(dǎo)過程中可能出現(xiàn)句型序列如：S1A11B11B1，由定義可知FIRST(1)FOLLOW（A）和FIRST(1)FOLLOW(B)。所以也就有FOLLOW(A)FOLLOW(B)(c) 反復(fù)使用(b)直到每個非終結(jié)符的FOLLOW集不再增大為止。使如，使用上述兩個算法為文法（4.11）GE構(gòu)造的全部非終結(jié)符號所構(gòu)造的FIRST集及FOLLOW集如下：FIRST（E）=FIRST（T）=FIRST（F）=(，i，F(xiàn)IRST（E）=+，F(xiàn)IRST（T）=*，F(xiàn)OLLOW（E）=FOLLOW（E）=)，#，F(xiàn)OLLOW（T）=FOLLOW（T）=+，)，#，F(xiàn)OLLOW（F）=+，*，

27、），#。3、 構(gòu)造LL(1)分析表算法圖中符號說明如下：“#”句子括號即輸入串的括號“S”文法的開始符號“X”存放當(dāng)前輸入符號a的工作單元3、構(gòu)造分析表的算法對于任一給定的已化簡文法G，所謂構(gòu)造相應(yīng)的分析表M，其實也就是定義M的各個元素。對此，我們在前面介紹LL（1）分析器的邏輯結(jié)構(gòu)時已初步涉及到了?，F(xiàn)在，我們假定G的每一非終結(jié)符的FOLLOW集與各候選式的FIRST集均已按上面的算法作出，為構(gòu)造G的分析表M，則只需對G中的每一產(chǎn)生式Aa，依如下的規(guī)則確定M的各個元素：（1）對FIRST（a）中的每一終結(jié)符a，置MA, a=“Aa”。（2）若FIRST（a），則對屬于FOLLOW（A）的每一符

28、號b（b為終結(jié)符或#），置MA，b=“Aa”。（3）把M中所有不能按規(guī)則1、2定義的元素均置為ERROR（出錯）。例如，按上述算法為文法（4.11）GE所構(gòu)造的分析表如圖4-.12-2所示。一個文法G，若它的分析表M不含多重元素，則稱它是一個LL（1）文法。一個LL（1）文法是無二義的，它所定義的語言恰好就是它的分析表M所能識別的全部名句子?？梢宰C明，一個文法G是LL（1）的，當(dāng)且僅當(dāng)對于G的每一個非終結(jié)符A的任何兩條不同規(guī)則A=|，下面的條件成立：（1）FIRST（）FIRST（）=，也就是由和推導(dǎo)不出以某個同一終結(jié)符a為首的符號串；它們不應(yīng)該都能推出空字。（2）假若Þ，那么，F(xiàn)I

29、RST（）FOLLOW（A）=。也就是，若Þ，則所能推出的串的首符不應(yīng)在FOLLOW（A）中。很清楚，文法（4-11GE）是LL（1）文法。應(yīng)當(dāng)指出，對已化簡的每一個文法G，盡管都可按上述算法為它們構(gòu)造一個分析表M。然而，在某些情況下，例如G存在左遞歸或二義性等等，則在相應(yīng)的分析表中，必然會出現(xiàn)多重定義的元素。請看下面的文法：G=（S，A，B，C，a，b，c，P，S），其中，P由如下產(chǎn)生式組成： Sa b B, ASC,ABABA，A BA b A，CB，Cc因為FIRST（S）=aFIRST（A）=FIRST（B）=,a,bFIRST（C）=a，b，c故由上述算法的規(guī)則1可知：MA

30、，a中含有“ASC”及“ABAA”，MA，b中含有“ABAA”。再由A中含有的產(chǎn)生式A，且bFOLLOW（A），故由規(guī)則2可知，MA，b中也含有產(chǎn)生式“A”?？梢娫诖宋姆ǖ姆治霰碇校豈A，a及MA，b都是多重定義的。出現(xiàn)上述情況的原因，在于G中存在如下的問題。 （1）G中含有左遞歸變量A和B；（2）對于G中的三個A產(chǎn)生式，有： FIRST（SC）FIRST（BAA）FIRST（BAA）FOLLOW（a）。也就是說，G不是一個LL（1）方法。實際上，可以證明，對于任何文法G，當(dāng)且僅當(dāng)它是一個LL（1）文法時，才能的按上述算法為它構(gòu)造一個無多重定義元素的分析表，而且此分析表能分析并且僅能分析G

31、中的全部句子。然而，盡管如此，對某些非LL（1）文法而言，通過消除左遞歸和提取左因子，有可能把它們改造為LL（1）文法。例如，對于非LL（1）文法EE+T|T，T（E）|a（E）|a，經(jīng)消除其中的左遞歸并對T-產(chǎn)生式提取左因子之后，我們就把它改造為如下的LL（1）文法：ET+T，EE+TE|TaT|（E），T（E）|，但是，并非所有的非LL（1）文法都能改造為LL（1）文法。例如，對于文法SAU|BR，AaAU|b，BaBR|b，Uc，Rd，因?qū)τ赟-產(chǎn)生式，有FIRST（AU）FIRST（BR），故它不是一個LL（1）文法。為了對S-產(chǎn)生式提取左因子，將其中的非終結(jié)符號A，B分別以其各候選式

32、替入，我們得到：SaAUU|bU|aBRR|bR經(jīng)提取左因子后，得到了與原文法等價的新文法：SaS|bS，SU|RSAUU|BRR，AaAU|b，BaBR|b，Uc，Rd。Uc，Rd。顯然，它仍不是一個LL（1）文法。且不難看出，無論把上述手續(xù)重復(fù)多次，都不能把它改造為LL（1）文法。（二）LL（1）分析表的構(gòu)造方法上述LL（1）方法對任何文法都是相同的，不同的是分析表，構(gòu)造兩個集合十次ST和FOLLOW。定義2 設(shè)G =（VT，VN，S，P）是上下文無關(guān)文法，AVNS是開始符號 FOLLOW（A）=|SAUUG VT若有S*A，則規(guī)定 #G FOLLOW（A）#作為輸入半結(jié)束符，#輸入半#第

33、十三節(jié) 習(xí)題1、 構(gòu)造下面文法的LL（1）分析表。D TLT int | realL id RR , id R | 解答案： LL（1）分析表見表4-3-1分析 雖然這個文法很簡單，我們還是從求開始符號集合和后繼符號集合開始。 FIRST（D）=FIRST（T）=int, real FOLLOW（D）=FOLLOW（L）=#FIRST（L）=id FOLLOW（T）=idFIRST（R）=，, FOLLOW（R）=#有了上面每個非終結(jié)符的FIRST集合，填分析表時要計算一個產(chǎn)生式右部的FIRST（）就不是件難事了。填表時唯一要小心的時，是產(chǎn)生式R右部的一個開始符號，而#在FOLLOW（R）中，

34、所以R填在輸入符號#的欄目中。表2.4-3-1 LL（1）分析表非終結(jié)符輸入符號int realid，#DDTLDTLTTintTrealLLid RRR,id RR 有了上面每個非終結(jié)符的FIRST集合，填分析表時要計算一個產(chǎn)生式右部的FIRST（）就不是件難事了。填表時唯一要小心的時，是產(chǎn)生式R右部的一個開始符號，而#在FOLLOW（R）中，所以R填在輸入符號#的欄目中。2、 下面文法GS是否為LL（1）文法？說明理由。S  A B | P Q x A  x y B  b cP  d P | Q  a Q | 解答案： 該文法不是LL（1）

35、文法，見下面分析中的說明。分析 只有三個非終結(jié)符有兩個選擇。 1、P的兩個右部d P 和 的開始符號肯定不相交。2、Q的兩個右部a Q 和 的開始符號肯定不相交。3、對S來說，由于x FIRST(A B)，同時也有x FIRST(P Q x)（因為P和Q都可能為空）。所以該文法不是LL（1）文法。3、 設(shè)有以下文法： GS：SaAbDe|d ABSD|e BSAc| cD| DSe| （1）求出該文法的每一個非終結(jié)符U的FOLLOW集。（2）該文法是LL（1）文法嗎？（3）構(gòu)造CS的LL（1）分析表。解答案： （1）求文法的每一個非終結(jié)符U的FOLLOW集的過程如下：因為： S是識別符號，且有

36、ABSD、BSAc、DSe，所以FOLLOW（S）應(yīng)包含F(xiàn)IRST(D)FIRST(Ac) FIRST(e) #=a,da,d,c,ee#=a,c,d,e# 又因為ABSD和D，所以FOLLOW中還包含F(xiàn)OLLOW(A)。因為SaAbDe和BSAc,所以FOLLOW（A）=FIRST（bDe）FIRST（c）=b,c綜合、得FOLLOW（S）=a,d,c,e,#a,b,c,d,e,#因為ABSD，所以 FOLLOW（B）=FIRST（SD）=a,d 因為SaAbDe | d、ABSD| e和BSAc | cD，所以FOLLOW（D）=FIRST（e）FOLLOW（A）FOLLOW（B）

37、60;=eb,ca,d=a,b,c,d,e（2）GS不是LL（1）文法。因為產(chǎn)生式BSAc|cD| 中 FIRST（SAc）FOLLOW（B）=a,dØ（3）構(gòu)造GS的LL（1）分析表。按照LL（1）分析表的構(gòu)造算法構(gòu)造方法GS的LL（1）分析表如表4-.13-2所示。表4.1-3-2 GS的LL（1）分析表abcde#SaAbDedABSDBSDBSDeBSac/cDSac/DSe/Se/4、 將文法GV改造成為LL(1)的。 GV：VN|NE EV|V+E Ni解答案： 對文法GV提取公共左因子后得到文法： GV：VNAA|EEVBB|+ENi求出文法GV中每一個非終結(jié)符號的FI

38、RST集： FIRST(V)=iFIRST(A)=, FIRST(E)=iFIRST(B)=+, FIRST(N)=i求出文法GV中每一個非終結(jié)符號的FOLLOW集：FOLLOW(V)=#FIRST(B)FOLLOW(E)=#,+,FOLLOW(A)= FOLLOW(V)=+,#FOLLOW(E)= FIRST()FOLLOW(B)= FIRST()FOLLOW(E)=FOLLOW(B)= FOLLOW(E)= FOLLOW(N)= FIRST(A)FOLLOW(V)=,+,#可以看到，對文法GV的產(chǎn)生式A|E，有FIRST(E)FOLLOW(A)=+,#= Ø對產(chǎn)生式B|+E，有F

39、IRST(+E)FOLLOW(B)=+= Ø而文法的其他產(chǎn)生式都只有一個不為空串（）的右部，所以文法GV是LL(1)文法。5、設(shè)有文法GS:SaABbcd|AASd|BSAh|eC|CSf|Cg|DaBD| 求每一個非終結(jié)符號的FOLLOW集合。 對每一個非終結(jié)符號的產(chǎn)生式選擇，構(gòu)造FIRST集合。 該文法是LL（1）文法嗎？解答 首先將文法壓縮，得到SaABbcd|AASd|BSAh|eC|CSf|Cg| 求每一個非終結(jié)符號的FOLLOW集合：S為開始符號，且有產(chǎn)生式 AASd, BSAh, CSfFOLLOW（S）=#FIRST(d) FIRST(Ah)FIRST(f)=#,d,

40、a,h,fSaABbcd,AASd,BSAhFOLLOW（A）=FIRSTBbcdFIRSTSdFIRSTh=b,a,d,h,eSaABbcdFOLLOW（B）=FIRSTbcd=bBeC,CCgFIRST（C）=FOLLOW（B）FIRST(g)=b, g 對每一個非終結(jié)符號的產(chǎn)生式右部選項，構(gòu)造FIRST集合對 S：FIRST（aABbcd）=aFIRST（ ）=對 A：FIRST（ASd）=a, dFIRST（ ）=對 B：FIRST（SAh）=a, d, hFIRST（eC）=e FIRST（ ）=對C：FIRST（Sf）=a, f FIRST（Cg）=a, f, g FIRST（ ）

41、= 由于存在產(chǎn)生式CSf|Cg|FIRST（Sf）FIRST（Cg）=a, fa, f, gØ所以該文法不是LL（1）文法。65、已知文法：GA：AaAa|（1）該文法是LL（1）文法嗎？為什么？（2）若采用LL（1）方法進(jìn)行語法分析，如何得到該文法的LL（1）分析表？（3）若輸入符號串“aaaa”，請給出語法分析過程。解答：（1）因為產(chǎn)生式AaAa| 有空產(chǎn)生式右部，而 FOLLOW(A)=#FIRST(a)=a, #造成 FIRST(A)FOLLOW(A)=A, a, #Ø所以該文法不是LL（1）文法。（2）若采用LL（1）方法進(jìn)行語法分析，必須修改該文法。因該文法產(chǎn)生

42、偶數(shù)（可以為0）個a，所以得到文法GA：AaaA|此時對產(chǎn)生式AaaA|， 有 FOLLOW(A)=#FOLLOW(A)=#，因而FIRST(A)FOLLOW(A)=a, #=Ø所以文法GA是LL（1）文法，按LL（1）分析表構(gòu)造算法構(gòu)造該文法的LL（1）分析表如表4.2-3-3所示。表4.2-3-3 文法GA的LL(1)分析表A#AAaaAA（3）若采用LL(1)方法進(jìn)行語法分析，對符號串“aaaa”的分析過程如表4.-3-43所示。 表4.3-3-4對符號串“aaaa”的分析過程步驟分析棧輸入串產(chǎn)生式/動作1#Aa a a a #AaaA2#A a aa a a a #匹配3#A aa a a #匹配4#Aa a #AaaA5#A a aa a #匹配6#A aa#匹配7#A#A8#接受 7、設(shè)文法GS： SSbA|aABSbABc 將此文法改寫為LL（1）文法。 求文法的每一個非終結(jié)符號的FIRST集合和FOLLOW集合。 構(gòu)造相應(yīng)的LL（1）分析表。解答 改寫文法為LL（1）文法。因為SSbA|aA有左遞歸，將其改寫為SaAbA文法變?yōu)镚S：SaAbA&#