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

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

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

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

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

5、出符號串w的過程中，由于出現在符號串中的非終結符號只有一個，因此，未明顯地表現出最左推導的性質。根據以上分析，不難編出程序來實現這種分析的算法。但是，上述這種自頂向下的分析算法存在著一定的困難和缺點。困難表現在不能為左遞歸文法構造自頂向下的語法分析器（上述所舉例子的文法Gs是不具有在遞歸性的）。缺點主要表現在存在著回溯問題。當然，應用帶回溯的自頂向下的分析算法還必須將文法規(guī)則存放于內存。下面將具體介紹這種分析算法所存在的問題及其解決辦法。二、存在問題及解決辦法（一）左遞歸問題自頂向下分析法只有規(guī)則排列得合適時，才能正確工作。該法的一個基本缺點是不能處理具有左遞歸的文法。如下所示。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的空產生式算法：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（二）回溯 問題 當產生式都有多個選擇時，選那個輸入串去匹配為了避免回溯，就必須保證：對文法的任何非終結符號特別是規(guī)則都右部有多個選擇的非終結符號，當用它去匹配輸入串時，應是確定無疑的。即：U11|22|nn該規(guī)則右部有n個選擇,為了實現目的,我們對文法的要求是:F1rstIRST（i）f1rstFIRST（j）=（ij）定義1：設G=（VT，VN，S，P）是上下文無關文法FIRST（）=a| Þa，aVT，V*若Þ，則規(guī)定FIRST（）即對文法中的任意一個非終符

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

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

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

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

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

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

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

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

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

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，設MXm, ai為一產生式，譬如說XmUVW，此時將Xm從分析棧中退出，并將UVW按反序推入棧中（即用該產生式推導一步），從而得到新的格局但若MXm, ai=“ERROR”，則調用出錯處理程序進行處理；2、若Xm=ai#，則表明棧頂符號已與當前正掃視的輸入符號得到匹配，此時應將Xm（即ai）從棧中退出，并將輸入符號

18、指示器向前推進一個位置；3、若Xm=ai=#，則表明輸入串已完全得到匹配，此時即可宣告分析成功而結束分析工作。順便提及，在上述分析過程的每一步，可視需要附加相應的的語義處理工作。例 考慮文法GE：ETE' E'+TE'| T'*FT'|F(E)|Ii TFT' 相應的分析表如圖4-2-2所示（其構造方法，在后面敘述）。現以輸入符號串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步驟 分析棧 余留輸入串所用產生式 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步驟 分析棧 余留輸入串所用產生式 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)分析表的構造方法 上述LL(1)分析算法對于不同的LL(1)文法都是相同的。也就是說，是說，對不同的LL(1)分析器而言，它們的總控程序都是相同的，不同的僅僅是分析表。再者總控程序十分簡

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

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

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

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

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

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

29、RST（）FOLLOW（A）=。也就是，若Þ，則所能推出的串的首符不應在FOLLOW（A）中。很清楚，文法（4-11GE）是LL（1）文法。應當指出，對已化簡的每一個文法G，盡管都可按上述算法為它們構造一個分析表M。然而，在某些情況下，例如G存在左遞歸或二義性等等，則在相應的分析表中，必然會出現多重定義的元素。請看下面的文法：G=（S，A，B，C，a，b，c，P，S），其中，P由如下產生式組成： 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中含有的產生式A，且bFOLLOW（A），故由規(guī)則2可知，MA，b中也含有產生式“A”?？梢娫诖宋姆ǖ姆治霰碇校豈A，a及MA，b都是多重定義的。出現上述情況的原因，在于G中存在如下的問題。 （1）G中含有左遞歸變量A和B；（2）對于G中的三個A產生式，有： FIRST（SC）FIRST（BAA）FIRST（BAA）FOLLOW（a）。也就是說，G不是一個LL（1）方法。實際上，可以證明，對于任何文法G，當且僅當它是一個LL（1）文法時，才能的按上述算法為它構造一個無多重定義元素的分析表，而且此分析表能分析并且僅能分析G

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

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

33、十三節(jié) 習題1、 構造下面文法的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）=#有了上面每個非終結符的FIRST集合，填分析表時要計算一個產生式右部的FIRST（）就不是件難事了。填表時唯一要小心的時，是產生式R右部的一個開始符號，而#在FOLLOW（R）中，

34、所以R填在輸入符號#的欄目中。表2.4-3-1 LL（1）分析表非終結符輸入符號int realid，#DDTLDTLTTintTrealLLid RRR,id RR 有了上面每個非終結符的FIRST集合，填分析表時要計算一個產生式右部的FIRST（）就不是件難事了。填表時唯一要小心的時，是產生式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、文法，見下面分析中的說明。分析 只有三個非終結符有兩個選擇。 1、P的兩個右部d P 和 的開始符號肯定不相交。2、Q的兩個右部a Q 和 的開始符號肯定不相交。3、對S來說，由于x FIRST(A B)，同時也有x FIRST(P Q x)（因為P和Q都可能為空）。所以該文法不是LL（1）文法。3、 設有以下文法： GS：SaAbDe|d ABSD|e BSAc| cD| DSe| （1）求出該文法的每一個非終結符U的FOLLOW集。（2）該文法是LL（1）文法嗎？（3）構造CS的LL（1）分析表。解答案： （1）求文法的每一個非終結符U的FOLLOW集的過程如下：因為： S是識別符號，且有

36、ABSD、BSAc、DSe，所以FOLLOW（S）應包含FIRST(D)FIRST(Ac) FIRST(e) #=a,da,d,c,ee#=a,c,d,e# 又因為ABSD和D，所以FOLLOW中還包含FOLLOW(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）文法。因為產生式BSAc|cD| 中 FIRST（SAc）FOLLOW（B）=a,dØ（3）構造GS的LL（1）分析表。按照LL（1）分析表的構造算法構造方法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中每一個非終結符號的FI

38、RST集： FIRST(V)=iFIRST(A)=, FIRST(E)=iFIRST(B)=+, FIRST(N)=i求出文法GV中每一個非終結符號的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的產生式A|E，有FIRST(E)FOLLOW(A)=+,#= Ø對產生式B|+E，有F

39、IRST(+E)FOLLOW(B)=+= Ø而文法的其他產生式都只有一個不為空串（）的右部，所以文法GV是LL(1)文法。5、設有文法GS:SaABbcd|AASd|BSAh|eC|CSf|Cg|DaBD| 求每一個非終結符號的FOLLOW集合。 對每一個非終結符號的產生式選擇，構造FIRST集合。 該文法是LL（1）文法嗎？解答 首先將文法壓縮，得到SaABbcd|AASd|BSAh|eC|CSf|Cg| 求每一個非終結符號的FOLLOW集合：S為開始符號，且有產生式 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 對每一個非終結符號的產生式右部選項，構造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、= 由于存在產生式CSf|Cg|FIRST（Sf）FIRST（Cg）=a, fa, f, gØ所以該文法不是LL（1）文法。65、已知文法：GA：AaAa|（1）該文法是LL（1）文法嗎？為什么？（2）若采用LL（1）方法進行語法分析，如何得到該文法的LL（1）分析表？（3）若輸入符號串“aaaa”，請給出語法分析過程。解答：（1）因為產生式AaAa| 有空產生式右部，而 FOLLOW(A)=#FIRST(a)=a, #造成 FIRST(A)FOLLOW(A)=A, a, #Ø所以該文法不是LL（1）文法。（2）若采用LL（1）方法進行語法分析，必須修改該文法。因該文法產生

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