編譯原理自頂向下語(yǔ)法分析法

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

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

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

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

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

6、Ac|dAa    BA CB bA C如：直接左遞歸 和 間接左遞歸AABACcBbACcSSa|bSSaSaSaSaAaAB|BbBAc|d無(wú)法確定語(yǔ)法樹(shù)的終止，清除直接左遞歸的較好方法是改改為右遞歸如：SSa|b 改為SbSSaS|一般情況下，直接左遞歸的形式可為：消除AA1|A2| Am|1|2n清除左遞歸后改寫(xiě)為：A1A1|2A1 |nA1A11A|2A1 |mmA1|對(duì)于間接左遞歸的消除，需先將間接左遞歸變?yōu)橹苯幼筮f歸，然后再接上述方法消除。條件是文法中無(wú)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（二）回溯 問(wèn)題 當(dāng)產(chǎn)生式都有多個(gè)選擇時(shí)，選那個(gè)輸入串去匹配為了避免回溯，就必須保證：對(duì)文法的任何非終結(jié)符號(hào)特別是規(guī)則都右部有多個(gè)選擇的非終結(jié)符號(hào)，當(dāng)用它去匹配輸入串時(shí)，應(yīng)是確定無(wú)疑的。即：U11|22|nn該規(guī)則右部有n個(gè)選擇,為了實(shí)現(xiàn)目的,我們對(duì)文法的要求是:F1rstIRST（i）f1rstFIRST（j）=（ij）定義1：設(shè)G=（VT，VN，S，P）是上下文無(wú)關(guān)文法FIRST（）=a| Þa，aVT，V*若Þ，則規(guī)定FIRST（）即對(duì)文法中的任意一個(gè)非終符

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

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

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

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

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

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

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

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

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

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

18、指示器向前推進(jìn)一個(gè)位置；3、若Xm=ai=#，則表明輸入串已完全得到匹配，此時(shí)即可宣告分析成功而結(jié)束分析工作。順便提及，在上述分析過(guò)程的每一步，可視需要附加相應(yīng)的的語(yǔ)義處理工作。例 考慮文法GE：ETE' E'+TE'| T'*FT'|F(E)|Ii TFT' 相應(yīng)的分析表如圖4-2-2所示（其構(gòu)造方法，在后面敘述）?，F(xiàn)以輸入符號(hào)串i+i*i為例，列出利用上述算法對(duì)此符號(hào)串的分析過(guò)程如圖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)分析算法對(duì)于不同的LL(1)文法都是相同的。也就是說(shuō)，是說(shuō)，對(duì)不同的LL(1)分析器而言，它們的總控程序都是相同的，不同的僅僅是分析表。再者總控程序十分簡(jiǎn)

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

24、W的算法，然后再給出構(gòu)造分析表的算法。（三）1、計(jì)算F1RST集根據(jù)定義計(jì)算由定義 FIRST（）=a| a aVT 、 V*,若，則規(guī)定FIRST()對(duì)每一文法符號(hào)XV計(jì)算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都時(shí)，（其中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)步直到每個(gè)符號(hào)的FIRST集合不再增大為止。求出每個(gè)文法符號(hào)的FIRST集合后也就不難求出一個(gè)符號(hào)串的FIRST集合。 (四)2、計(jì)算FOLLOW集1）根據(jù)定義計(jì)算對(duì)文法中每一AVN計(jì)算FOLLOW(A)(a) 設(shè)S為文法中開(kāi)始符號(hào)，把#加入FOLLOW (S)中(這里“#”為句子括號(hào))。(b) 若AB是一個(gè)產(chǎn)生式，則把FIRST()的非空元素加入FOLLOW（B）中。如果則把FOLLOW（A）也加入FOLLOW（B）中，因?yàn)楫?dāng)有形如：D1A1AB的產(chǎn)生式時(shí),A, B, DVN, , 11,

26、 ,V*,在推導(dǎo)過(guò)程中可能出現(xiàn)句型序列如：S1A11B11B1，由定義可知FIRST(1)FOLLOW（A）和FIRST(1)FOLLOW(B)。所以也就有FOLLOW(A)FOLLOW(B)(c) 反復(fù)使用(b)直到每個(gè)非終結(jié)符的FOLLOW集不再增大為止。使如，使用上述兩個(gè)算法為文法（4.11）GE構(gòu)造的全部非終結(jié)符號(hào)所構(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)分析表算法圖中符號(hào)說(shuō)明如下：“#”句子括號(hào)即輸入串的括號(hào)“S”文法的開(kāi)始符號(hào)“X”存放當(dāng)前輸入符號(hào)a的工作單元3、構(gòu)造分析表的算法對(duì)于任一給定的已化簡(jiǎn)文法G，所謂構(gòu)造相應(yīng)的分析表M，其實(shí)也就是定義M的各個(gè)元素。對(duì)此，我們?cè)谇懊娼榻BLL（1）分析器的邏輯結(jié)構(gòu)時(shí)已初步涉及到了。現(xiàn)在，我們假定G的每一非終結(jié)符的FOLLOW集與各候選式的FIRST集均已按上面的算法作出，為構(gòu)造G的分析表M，則只需對(duì)G中的每一產(chǎn)生式Aa，依如下的規(guī)則確定M的各個(gè)元素：（1）對(duì)FIRST（a）中的每一終結(jié)符a，置MA, a=“Aa”。（2）若FIRST（a），則對(duì)屬于FOLLOW（A）的每一符

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

29、RST（）FOLLOW（A）=。也就是，若Þ，則所能推出的串的首符不應(yīng)在FOLLOW（A）中。很清楚，文法（4-11GE）是LL（1）文法。應(yīng)當(dāng)指出，對(duì)已化簡(jiǎn)的每一個(gè)文法G，盡管都可按上述算法為它們構(gòu)造一個(gè)分析表M。然而，在某些情況下，例如G存在左遞歸或二義性等等，則在相應(yīng)的分析表中，必然會(huì)出現(xiàn)多重定義的元素。請(qǐng)看下面的文法：G=（S，A，B，C，a，b，c，P，S），其中，P由如下產(chǎn)生式組成： Sa b B, ASC,ABABA，A BA b A，CB，Cc因?yàn)镕IRST（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”?？梢?jiàn)在此文法的分析表中，元素MA，a及MA，b都是多重定義的。出現(xiàn)上述情況的原因，在于G中存在如下的問(wèn)題。 （1）G中含有左遞歸變量A和B；（2）對(duì)于G中的三個(gè)A產(chǎn)生式，有： FIRST（SC）FIRST（BAA）FIRST（BAA）FOLLOW（a）。也就是說(shuō)，G不是一個(gè)LL（1）方法。實(shí)際上，可以證明，對(duì)于任何文法G，當(dāng)且僅當(dāng)它是一個(gè)LL（1）文法時(shí)，才能的按上述算法為它構(gòu)造一個(gè)無(wú)多重定義元素的分析表，而且此分析表能分析并且僅能分析G

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

32、替入，我們得到：SaAUU|bU|aBRR|bR經(jīng)提取左因子后，得到了與原文法等價(jià)的新文法：SaS|bS，SU|RSAUU|BRR，AaAU|b，BaBR|b，Uc，Rd。Uc，Rd。顯然，它仍不是一個(gè)LL（1）文法。且不難看出，無(wú)論把上述手續(xù)重復(fù)多次，都不能把它改造為L(zhǎng)L（1）文法。（二）LL（1）分析表的構(gòu)造方法上述LL（1）方法對(duì)任何文法都是相同的，不同的是分析表，構(gòu)造兩個(gè)集合十次ST和FOLLOW。定義2 設(shè)G =（VT，VN，S，P）是上下文無(wú)關(guān)文法，AVNS是開(kāi)始符號(hào) 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）分析表見(jiàn)表4-3-1分析 雖然這個(gè)文法很簡(jiǎn)單，我們還是從求開(kāi)始符號(hào)集合和后繼符號(hào)集合開(kāi)始。 FIRST（D）=FIRST（T）=int, real FOLLOW（D）=FOLLOW（L）=#FIRST（L）=id FOLLOW（T）=idFIRST（R）=，, FOLLOW（R）=#有了上面每個(gè)非終結(jié)符的FIRST集合，填分析表時(shí)要計(jì)算一個(gè)產(chǎn)生式右部的FIRST（）就不是件難事了。填表時(shí)唯一要小心的時(shí)，是產(chǎn)生式R右部的一個(gè)開(kāi)始符號(hào)，而#在FOLLOW（R）中，

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

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

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# 又因?yàn)锳BSD和D，所以FOLLOW中還包含F(xiàn)OLLOW(A)。因?yàn)镾aAbDe和BSAc,所以FOLLOW（A）=FIRST（bDe）FIRST（c）=b,c綜合、得FOLLOW（S）=a,d,c,e,#a,b,c,d,e,#因?yàn)锳BSD，所以 FOLLOW（B）=FIRST（SD）=a,d 因?yàn)镾aAbDe | 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）文法。因?yàn)楫a(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改造成為L(zhǎng)L(1)的。 GV：VN|NE EV|V+E Ni解答案： 對(duì)文法GV提取公共左因子后得到文法： GV：VNAA|EEVBB|+ENi求出文法GV中每一個(gè)非終結(jié)符號(hào)的FI

38、RST集： FIRST(V)=iFIRST(A)=, FIRST(E)=iFIRST(B)=+, FIRST(N)=i求出文法GV中每一個(gè)非終結(jié)符號(hào)的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)=,+,#可以看到，對(duì)文法GV的產(chǎn)生式A|E，有FIRST(E)FOLLOW(A)=+,#= Ø對(duì)產(chǎn)生式B|+E，有F

39、IRST(+E)FOLLOW(B)=+= Ø而文法的其他產(chǎn)生式都只有一個(gè)不為空串（）的右部，所以文法GV是LL(1)文法。5、設(shè)有文法GS:SaABbcd|AASd|BSAh|eC|CSf|Cg|DaBD| 求每一個(gè)非終結(jié)符號(hào)的FOLLOW集合。 對(duì)每一個(gè)非終結(jié)符號(hào)的產(chǎn)生式選擇，構(gòu)造FIRST集合。 該文法是LL（1）文法嗎？解答 首先將文法壓縮，得到SaABbcd|AASd|BSAh|eC|CSf|Cg| 求每一個(gè)非終結(jié)符號(hào)的FOLLOW集合：S為開(kāi)始符號(hào)，且有產(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 對(duì)每一個(gè)非終結(jié)符號(hào)的產(chǎn)生式右部選項(xiàng)，構(gòu)造FIRST集合對(duì) S：FIRST（aABbcd）=aFIRST（ ）=對(duì) A：FIRST（ASd）=a, dFIRST（ ）=對(duì) B：FIRST（SAh）=a, d, hFIRST（eC）=e FIRST（ ）=對(duì)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)行語(yǔ)法分析，如何得到該文法的LL（1）分析表？（3）若輸入符號(hào)串“aaaa”，請(qǐng)給出語(yǔ)法分析過(guò)程。解答：（1）因?yàn)楫a(chǎn)生式AaAa| 有空產(chǎn)生式右部，而 FOLLOW(A)=#FIRST(a)=a, #造成 FIRST(A)FOLLOW(A)=A, a, #Ø所以該文法不是LL（1）文法。（2）若采用LL（1）方法進(jìn)行語(yǔ)法分析，必須修改該文法。因該文法產(chǎn)生

42、偶數(shù)（可以為0）個(gè)a，所以得到文法GA：AaaA|此時(shí)對(duì)產(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)行語(yǔ)法分析，對(duì)符號(hào)串“aaaa”的分析過(guò)程如表4.-3-43所示。 表4.3-3-4對(duì)符號(hào)串“aaaa”的分析過(guò)程步驟分析棧輸入串產(chǎn)生式/動(dòng)作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 將此文法改寫(xiě)為L(zhǎng)L（1）文法。 求文法的每一個(gè)非終結(jié)符號(hào)的FIRST集合和FOLLOW集合。 構(gòu)造相應(yīng)的LL（1）分析表。解答 改寫(xiě)文法為L(zhǎng)L（1）文法。因?yàn)镾SbA|aA有左遞歸，將其改寫(xiě)為SaAbA文法變?yōu)镚S：SaAbA&#