自動(dòng)構(gòu)造分析表的自頂而下的語(yǔ)法分析

1、自頂而下語(yǔ)法分析（PT）前言對(duì)于國(guó)內(nèi)的計(jì)算機(jī)教材，我一直是有巨大看法的，以至于寫了讀優(yōu)秀的計(jì)算機(jī)教材來泄憤( Techniques中關(guān)于表驅(qū)動(dòng)的自頂而下語(yǔ)法分析部分做了中文翻譯，它正好對(duì)應(yīng)合肥工業(yè)大學(xué)同門課程的實(shí)驗(yàn)二，提前說明，全文近7000漢字卻沒有一行代碼，按這本書的說法是照顧斯坦福大學(xué)人文藝術(shù)學(xué)院的學(xué)生。良好的講述就是藝術(shù)，不是么？當(dāng)然，我的英語(yǔ)和漢語(yǔ)水平都不是很理想，所以在表意上定會(huì)有所折損，如果你對(duì)英文更有興趣，請(qǐng)自行檢索PT的電子版，這段內(nèi)容在第九章，如果你發(fā)現(xiàn)有所錯(cuò)漏或表意不明之處，希望能幫助修訂，感謝。下面，我們開始。查表法首先我們要考慮一個(gè)簡(jiǎn)單的語(yǔ)法格式來限制搜索情況，在這種

2、語(yǔ)法格式內(nèi)，推導(dǎo)式的右部都由一個(gè)終結(jié)符開始。在這種語(yǔ)法格式下，預(yù)測(cè)步驟后面總是緊跟著一個(gè)匹配步驟，匹配步驟嘗試匹配下一個(gè)輸入的標(biāo)示符與我們?cè)陬A(yù)測(cè)過程所選中的推導(dǎo)式的右側(cè)的第一個(gè)字符，只有在推導(dǎo)式右部是以輸入字符開始時(shí)匹配才得以成立，而針對(duì)其他的右側(cè)推導(dǎo)式將會(huì)失敗。我們可以利用這一現(xiàn)象去限制我們所作出預(yù)測(cè)的數(shù)量：對(duì)于一個(gè)以某個(gè)終結(jié)符開始的推導(dǎo)式右部，只有當(dāng)其首個(gè)字符與輸入字符相等時(shí)，它才會(huì)被考慮加入預(yù)測(cè)集合。比如，考慮圖表8.1中的語(yǔ)法：我們使用廣度優(yōu)先搜索，同時(shí)結(jié)合剛才的觀察進(jìn)行分析。 圖(a)表示這個(gè)自動(dòng)機(jī)的開始，我們將#作為終結(jié)符添加到初始預(yù)測(cè)和輸入字符串的末尾。在S的右部中，只有一個(gè)是以

3、a開頭的(aB)，所以這是唯一匹配的右部。我們選擇了S 的第一個(gè) aB，故而用 S1 表示，放到左邊。圖(b)中我們直接匹配a，將a放到左面。圖(c)中，下一個(gè)輸入的符號(hào)又是a，在B的右部中，我們發(fā)現(xiàn)只有aBB能匹配成功。把B3放到左面，我們得到圖(d)。圖(d)中，直接匹配a，得到圖(e)。圖(e)中，我們能觀察到下一個(gè)輸入的字符是b，這一次有兩個(gè)B的右部能夠匹配成功(b,bS)，我們就針對(duì)兩種情況生成兩行，得到圖(f)，同樣我們把b都移向左側(cè)，得到(g)。圖(g)中，下一個(gè)輸入的字符是b。匹配第一行，B右部中的 b和bS可以滿足要求；匹配第二行，S中的bA可以滿足要求。把B 和 S 分別用

4、這三個(gè)可以匹配的右部替換并放到左邊，得到圖(h)，匹配b，得到圖(i)。圖(i)中，我們能發(fā)現(xiàn)，只剩下一個(gè)我們最初添加的#作為終止符號(hào)了，而S和AB不能再匹配成功，因此，下面兩行預(yù)測(cè)走到了死胡同，只給我么留下了唯一的預(yù)測(cè)，得到圖(j)。我們能夠再一次提高上述方法的效率，那就是我們?yōu)槊恳粚?duì)終結(jié)符與非終結(jié)符符的組合找到能使他們匹配的右部，就像剛才我們所尋找的那樣，找到后將他們填入表單中。針對(duì)圖表8.1中的語(yǔ)法，我們可以制作像圖表8.3一樣的表格，它被叫做 parse table其實(shí)怎樣構(gòu)造這樣一個(gè)表是需要我們著重考慮的。而一旦這樣的表格被建立起來，接下來的行動(dòng)就好辦了。我們所創(chuàng)造的這個(gè)語(yǔ)法分析器將

5、不再需要上面定義的語(yǔ)法推導(dǎo)式，取而代之的是在每一次預(yù)測(cè)時(shí)，語(yǔ)法分析器用下一個(gè)輸入的字符和需要匹配的非終結(jié)符作為這個(gè)表格的兩個(gè)索引，查找到對(duì)應(yīng)的格子，格子里存著的就是我們需要考慮的推導(dǎo)式的右部。比如，在圖表8.2(e)中，句法分析器將會(huì)用輸入字符b和非終結(jié)符B去確定他需要考慮的推導(dǎo)式右部B1和B2.如果對(duì)應(yīng)的格子是空的，我們就發(fā)現(xiàn)這個(gè)輸入是不符合語(yǔ)法的。這還沒有結(jié)束，前面格子里只有一個(gè)右部，而在A,a與B,b對(duì)應(yīng)的各自內(nèi)有不止一個(gè)元素，所以我們?nèi)孕枰阉鳑Q定哪一個(gè)符合語(yǔ)法。LL(1)語(yǔ)法分析在上一小節(jié)里我們舉例的從上至下的語(yǔ)法分析器，其中最大的限制是我們要求語(yǔ)法中非終結(jié)符的右部都以一個(gè)終結(jié)符開始

6、。而在這一節(jié)中，我們將去掉這個(gè)限制條件。你會(huì)看到，我們?nèi)匀豢梢越⒁粋€(gè)parse table。甚至，是帶有邊的。不帶有規(guī)則的語(yǔ)法分析如果語(yǔ)法不帶有規(guī)則，也就是說沒有非終結(jié)符可以推導(dǎo)出一個(gè)空字符串。換句話說，每一個(gè)非終結(jié)符最終至少都能導(dǎo)出長(zhǎng)度為1的字符串，這對(duì)每一個(gè)右部來說也成立。由此來說，由終結(jié)符開始的字符串就是我們所關(guān)注的對(duì)象。對(duì)于任意一個(gè)右部，一旦我們知道了它最后推導(dǎo)出來的字符串由哪一個(gè)字符開始，我們就能像上面那樣構(gòu)造一個(gè)parse table。所以，我們需要計(jì)算出每一個(gè)右部對(duì)應(yīng)的字符串的首個(gè)終止字符的集合。FIRST1 集合這些由終止符構(gòu)成的集合被我們叫做” FIRST1 集合”：假設(shè)我

7、們擁有一個(gè)非空左部x，那么FIRST1 (x)就是指x在一步或多步(>0)內(nèi)能推導(dǎo)出來的字符串的首個(gè)終止字符的集合。這個(gè)下標(biāo) 1 指的是這個(gè)集合只包含一個(gè)字符的終止符。其實(shí)還 FIRSTk ，當(dāng)下我們無須理會(huì)，暫且用FIRST代替FIRST1。如果x是由非終止符A起始的，那么FIRST(x)等同于FIRST(A)，因?yàn)锳不能產(chǎn)生邊，那么x所能推導(dǎo)出的式子的最左邊肯定是由A推導(dǎo)出來的。所以，如果我們能夠計(jì)算任意非終止符A的FIRST集合，我們也就能得到x的FIRST集合。然而，F(xiàn)IRST(A)取決于A的右部：是A不同右部的FIRST集合的并集，這些FIRST集合又再次取決于其他非終止符的并

8、集，在A的語(yǔ)法存在直接或間接地左遞歸（A描述A）的情況下，甚至這個(gè)其他有可能是A本身。這樣的觀察讓我們得到了一個(gè)迭代的過程去計(jì)算所有非終結(jié)符的FIRST集合：1. 將所有FIRST集合初始化為空集2. 我們對(duì)每一條語(yǔ)法規(guī)則進(jìn)行下面的工作：設(shè)當(dāng)前推導(dǎo)式的左部為x，右部為 xr如果xr是以一個(gè)終結(jié)符開始的，那么我們可以直接把這個(gè)符號(hào)添加到FIRST(x) 集合中。如果xr是由一個(gè)非終結(jié)符開始的，我們?cè)O(shè)這個(gè)非終結(jié)符為y，然后把當(dāng)前FIRST(y)中的所有元素添加到FIRST(x)中。這些被加入符號(hào)都是能夠被x推導(dǎo)出的字符串的首個(gè)字符。3. 重復(fù)第二個(gè)步驟直到在一次循環(huán)中沒有任何一個(gè)新的元素加入任何一

9、個(gè)FIRST集合最終一定會(huì)沒有新的符號(hào)能夠被添加，是因?yàn)橐粋€(gè)FIRST集合所能擁有的元素的最大數(shù)便是所有符號(hào)的總數(shù)，而FIRST集合的數(shù)量等同于非終結(jié)符的數(shù)量。因此，新元素能夠被加入FIRST集合的次數(shù)限制在字符數(shù)量和非終結(jié)符數(shù)量的乘積內(nèi)。這是一個(gè)傳遞閉包算法的典型例子。創(chuàng)建Parse Table通過FIRST集合的幫助，我們現(xiàn)在可以根據(jù)一種語(yǔ)法形式來創(chuàng)建Parse Table了！假設(shè)有一條語(yǔ)法規(guī)則（推導(dǎo)式）是A ，我們這樣進(jìn)行處理：如果是由一個(gè)終結(jié)符t開始的，我們就把這條推導(dǎo)式的右部加入到(A,t)對(duì)應(yīng)的格子中；如果是由一個(gè)非終結(jié)符開始的，我們就取出每一個(gè)FIRST()中的元素，設(shè)它為n，把

10、加入到(A,n)中?，F(xiàn)在，讓我們以圖表8.7中的語(yǔ)法為例演示一下計(jì)算出parse table的過程。這種語(yǔ)法描述了一個(gè)用在早期咨詢系統(tǒng)上的簡(jiǎn)單語(yǔ)言：用戶輸入一些事實(shí)，然后再提問，也有一些設(shè)施是為子對(duì)話服務(wù)的。事實(shí)和問題的內(nèi)容我們暫時(shí)先不去管它，他們用單詞STRING表示，在這里STRING被當(dāng)做終結(jié)符看待。第一步，我們計(jì)算FIRST集合。起初，把所有FIRST集合為空。接下來，我們對(duì)圖表8.7中的所有語(yǔ)法規(guī)則進(jìn)行前面所描述過的處理過程。對(duì)于語(yǔ)法規(guī)則：Session -> Fact Session ，我們需要把FIRST(Fact)集合中的字符都加入到FIRST(Session)中，但是F

11、IRST(Fact)一開始也是空的。對(duì)于語(yǔ)法規(guī)則：Session->Question ，我們需要把FIRST(Question)加入到FIRST(Session)中，當(dāng)然，F(xiàn)IRST(Question)目前也是空的。對(duì)于語(yǔ)法規(guī)則：Session -> ( Session ) Session ，我們需要把 ( 添加到FIRST(Session)中。對(duì)于語(yǔ)法規(guī)則：Fact -> ! STRING ，我們需要把 ! 添加到 FIRST(Fact)中。對(duì)于語(yǔ)法規(guī)則：Question -> ? STRING ，我們需要把 ? 添加到FIRST(Fact)中。好了，做完這一切之后，

12、我們有了以下的結(jié)果：接下來，我們?cè)僖淮螌?duì)所有的語(yǔ)法規(guī)則進(jìn)行上面的過程，這一次，對(duì)于Session -> Fact Session 我們把 ! 加到FIRST(Session)里（從FIRST(Fact)得到），對(duì)于Session -> Question 我們把?加入FIRST(Session)中，沒有其他的改變了。于是得到了：由于上一次循環(huán)產(chǎn)生了一些變化，所以我們必須重復(fù)這個(gè)循環(huán)，這一次，我們沒發(fā)現(xiàn)什么變化了，所以上面的表格就是我們所需要的有關(guān)于非終結(jié)符的FIRST集合?，F(xiàn)在我們已經(jīng)擁有了構(gòu)造一個(gè)parse table所需的全部信息。對(duì)于Session -> Fact Ses

13、sion，我們需要把FIRST(Fact Session)中的元素依次取出，設(shè)為t，對(duì)每一個(gè)t，把Fact Session加入到Session,t格子中。前面我們說過如果x是由非終止符A起始的，那么FIRST(x)等同于FIRST(A)，所以FIRST(Fact Session)在這里等同于FIRST(Fact),所以只需要把Fact Session加到Session,!中。類似的步驟，對(duì)于Session->Question，我們把Question加入到Session,?。對(duì)于Session -> ( Session ) Session，右部直接是終止符開始的，所以把( Sessi

14、on ) Session加入到Session,)。之后過程不再贅述。最終得到parse table如圖表8.8在這個(gè)表格中，格子里只有推導(dǎo)式的右部，因?yàn)樽蟛恳呀?jīng)成為了行的索引。如果一種語(yǔ)法生成的parse table所有的格子最多只有一個(gè)元素的話，我們就叫這種語(yǔ)法為L(zhǎng)L(1)。好了，這一小節(jié)中，我們費(fèi)了很大的勁終于去掉了最開始右部必須要由終結(jié)符開始的條件，創(chuàng)建一個(gè)parse table確實(shí)是是一個(gè)很復(fù)雜的活兒，但我們也收獲了許多：許多實(shí)際應(yīng)用的語(yǔ)法都是符合LL(1)或者可以簡(jiǎn)單地變化成LL(1)形式的。帶有 規(guī)則的LL(1)語(yǔ)法分析不允許規(guī)則不得不說是一個(gè)重大缺陷。若不利用規(guī)則，對(duì)某些語(yǔ)言的構(gòu)

15、建是十分困難甚至是不可能的。比如，非終結(jié)符描述一連串的終結(jié)符或非終結(jié)符就是很困難的。當(dāng)然你可以把一串a(chǎn)表示成 A -> aA | a，但這就不是LL(1)了（顯然格子里會(huì)超過一個(gè)元素）。對(duì)于上一節(jié)提到的語(yǔ)法：如果我們引入規(guī)則，能表達(dá)得更明晰：擴(kuò)展FIRST集合允許規(guī)則最大的問題便是FIRST集合，因?yàn)槲覀冎坝懻摰貌⒉怀浞帧１热?，非終結(jié)符Facts在圖表8.9的語(yǔ)法中存在規(guī)則，F(xiàn)IRST()是空的，所以它不會(huì)告訴我們哪一個(gè)輸入字符該使我們選擇這個(gè)右部。為了能表現(xiàn)出規(guī)則，對(duì)于FIRST集合的計(jì)算方法需要一些修改。比如，如果用以前的方法對(duì)Session的第一個(gè)右部計(jì)算FIRST集合 ? 不會(huì)

16、成為集合中的一員，但它卻應(yīng)該在，因?yàn)镕acts能推導(dǎo)出，當(dāng)Facts被忽略掉后 ? 作為Question的開頭，也被包含其中。讓我們先擴(kuò)展FIRST集合的定義以處理規(guī)則。這一次，除了終止符，也被允許成為FIRST集合中的一員。我們要去處理空的句式，所以我們有時(shí)需要FIRST()集合；我們把它定義成一個(gè)只包含字符串的集合。當(dāng)一個(gè)句式能推導(dǎo)出時(shí)，我們也把加入到那個(gè)句式的FIRST集合中。這些變動(dòng)影響了FIRST集合的計(jì)算過程。FIRST(u1u2 ···un)曾經(jīng)被我們看做等同于FIRST(u1) ,現(xiàn)在要這樣進(jìn)行計(jì)算了：我們檢查FIRST(u1)中是否存在 ，如果存

17、在，我們?nèi)サ簦阉鎿Q成FIRST(u2 ···un)，替換過后的FIRST(u1)等于FIRST(u1u2 ···un)。剛才的處理過程是很容易理解的：如果FIRST(u1)包含，那么u1便可能是透明的，所以把后面的FIRST(u2 ···un)就被暴露出來，也就可以拿掉了。當(dāng)然對(duì)于FIRST(u2 ···un)也要用一樣的算法。這個(gè)鏈條直到我們遇到了一個(gè)ui，當(dāng)FIRST(ui) 不包含時(shí)，把FIRST(ui)中的元素加到FIRST(u1u2 ··&#

18、183;un)中就可以了。如果 FIRST(u1), FIRST(u2), . FIRST(un) 都包含，我們就把加到FIRST(u1u2 ···un) ，表示所有的選項(xiàng)都是透明的。對(duì)于一些算法，我們需要知道一個(gè)非終結(jié)符A能否推導(dǎo)出，只需要查看是否在FIRST(A)中就可以了。因?yàn)榫拖裆厦嬲f的那樣，如果能被A所導(dǎo)出，那么它也一定在FIRST(A)中。如果你沒對(duì)此厭煩的話，我們?cè)賮硌菥氁幌聦?duì)于圖表8.9的FIRST集合的計(jì)算。首先我們先設(shè)置所有的集合為空。接著，我們對(duì)每一條語(yǔ)法進(jìn)行處理對(duì)于Session -> Facts Question，把FIRST(Fa

19、cts)中的添加到First(Session)，但FIRST(Facts)目前是空的。對(duì)于Session -> ( Session ) Session ，把 ( 加入FIRST(Session)。對(duì)于Facts -> Fact Facts ，把 FIRST(Fact) 加入 FIRST(Facts) 對(duì)于Facts -> ，把 添加到FIRST(Facts)對(duì)于Fact -> ! STRING ，把 ！添加到FIRST(Fact)對(duì)于Question -> ? STRING，把 ? 添加到FIRST(Question)最終我們得到：第二遍更有趣，我們知道 Fact

20、s 能推導(dǎo)出 ，因此對(duì)于Session -> Facts Question ，我們應(yīng)當(dāng)把FIRST(Question) 中的字符 (?) 加到FIRST(Session)中。對(duì)于Facts -> Fact Facts ，我們應(yīng)當(dāng)把FIRST(Fact)中的字符(!)加入FIRST(Facts)。我們得到了：再來一遍，唯一的變動(dòng)是我們要把FIRST(Fact)中新加入的!再加入到FIRST(Session)里，我們得到：第四遍并沒有變化，構(gòu)造結(jié)束?，F(xiàn)在問題還剩下在一些選擇的情況下，怎么決定何時(shí)選擇那個(gè)右部。假設(shè)我們有這樣的語(yǔ)法規(guī)則：A 1|2|···|n

21、其中，m是或者推導(dǎo)于一個(gè)，現(xiàn)在假設(shè)我們?cè)陬A(yù)測(cè)的最前面發(fā)現(xiàn)A，在最后添加#作為端記號(hào)：按照我們之前的方法，將產(chǎn)生多個(gè)預(yù)測(cè)以至于并列：我們知道如何計(jì)算出一個(gè)預(yù)測(cè)的FIRST集合，我們也知道這些集合中沒有一個(gè)包含的（因?yàn)樽詈笥?）。如果下一個(gè)輸入的字符不屬于這些集合當(dāng)中的任何一個(gè)，那么不是我們的預(yù)測(cè)Ax#是不可行的就是輸入的句式是不符合語(yǔ)法的。反之，下一個(gè)輸入的符號(hào)是屬于這些集合當(dāng)中的一個(gè)或多個(gè)的，我們就能刪去那些FIRST集合中不包含這個(gè)輸入符號(hào)的預(yù)測(cè)。對(duì)于FOLLOW集合的需求經(jīng)過前面的知識(shí)積累，原則上我們已經(jīng)能為任何一個(gè)符合LL(1)的語(yǔ)法創(chuàng)建一個(gè)語(yǔ)法分析器。這個(gè)語(yǔ)法分析器由一個(gè)預(yù)測(cè)S#開始，

22、他的預(yù)測(cè)步驟包括把預(yù)測(cè)的非終結(jié)符換成他的右部、計(jì)算已有預(yù)測(cè)的FIRST集合以及檢查下一個(gè)輸入字符是否屬于這些集合。但如果最后保留了超過一個(gè)預(yù)測(cè)，那么這個(gè)語(yǔ)法分析器就會(huì)聲明這個(gè)語(yǔ)法并非LL(1)然后停止。這當(dāng)然是不理想的。首先，我們前面辛辛苦苦構(gòu)建出來的parse table沒有被使用，直到對(duì)一個(gè)句子進(jìn)行語(yǔ)法分析的時(shí)候他才檢查語(yǔ)法是否符合LL(1)，而這實(shí)際上早在建立parse table的時(shí)候就能得到檢查。其次，這樣效率很差，因?yàn)槊恳徊筋A(yù)測(cè)都需要計(jì)算FIRST集。我們不能提前計(jì)算出這些FIRST集合，因?yàn)橛辛诉叺拇嬖?，一個(gè)FIRST集合取決于所有的預(yù)測(cè)（這是無窮盡的），而不單單取決于首個(gè)非終止

23、符。所以我們?nèi)匀徊恢廊绾螢閹в幸?guī)則的LL(1)構(gòu)建一個(gè)parse table，也沒有一種方法去確定一個(gè)語(yǔ)法是LL(1)。現(xiàn)在假設(shè)我們有一個(gè)預(yù)測(cè)Ax#和一個(gè)推導(dǎo)規(guī)則A , 本身是或者推導(dǎo)于。導(dǎo)致我們選擇A 的輸入字符存在于FIRST(x#)中，我們知道，由于的透明性，這個(gè)集合是由FIRST()并FIRST(x#)得到的。FIRST(x#)是個(gè)麻煩：我們不能在這個(gè)語(yǔ)法分析器的創(chuàng)建時(shí)期就得到它。然而，我們能提前計(jì)算的是所有x#跟著A情況下FIRST(x#)集合的并集。這僅僅是在任何S#能推導(dǎo)出的句式中能跟隨A的終結(jié)符的集合，我們把這樣的集合叫做FOLLOW(A)?？雌饋硪粋€(gè)粗略的近似能夠嚴(yán)重削弱一

24、個(gè)語(yǔ)法分析器甚至是讓他出錯(cuò)，但這一次不是。假設(shè)FOLLOW(A)包含一個(gè)字符a，不是FIRST(x#)的成員，成為下一個(gè)輸入字符。如果a不是FIRST(A)中的成員，我們將預(yù)測(cè)A ，最終會(huì)以匹配失敗告終，因?yàn)閤#不能推導(dǎo)出以a開始的式子。所以這個(gè)輸入字符串會(huì)被正確地拒絕掉，盡管錯(cuò)誤發(fā)現(xiàn)得比以前要晚，因?yàn)樵诎l(fā)現(xiàn)出錯(cuò)前，語(yǔ)法分析器會(huì)做一些假設(shè)。如果a是FIRST(A)中的成員，同時(shí)也是A其他右部的FIRST集的成員，那么我們也許會(huì)遇到問題，我們之后再擔(dān)心他。FOLLOW集有一個(gè)好處是我們能夠在語(yǔ)法分析器的構(gòu)造時(shí)期就計(jì)算出來。每一個(gè)非終結(jié)符都有一個(gè)FOLLOW集，他們可以用下面的方法來計(jì)算：1. 像

25、計(jì)算FIRST集合一樣，我們首先把所有的FOLLOW集置空。設(shè)S是起始預(yù)測(cè)，在他后面加上#作為端記號(hào)，把#加入FOLLOW(Session)里。2. 接著，我們處理所有的推導(dǎo)式。如果形式是AàB，那么我們就把FIRST()中除了外的全部字符加入到FOLLOW(B)中，如果推導(dǎo)式是AàB或是Aà B但FIRST()中存在，就把FOLLOW(A)中的元素添加到FOLLOW(B)。3. 重復(fù)以上步驟直到一次循環(huán)中沒有新的符號(hào)加入任何一個(gè)FOLLOW集。這又是一個(gè)傳遞閉包算法的例子。現(xiàn)在讓我們回到我們的例子，來計(jì)算FOLLOW集。首先把#加入FOLLOW(Session)

26、里。對(duì)于Session -> Facts Question FIRST(Question)中的字符 ? 被加入到FOLLOW(Facts)中。FOLLOW(Session)中的所有符號(hào)(#)要被添加到FOLLOW(Question)中。對(duì)于Session -> ( Session ) Session ，我們把 ) 添加到FOLLOW(Session)中，把FOLLOW(Session)添加到FOLLOW(Session)中。 對(duì)于Facts->Fact Facts ，我們把FIRST(Facts)的所有符號(hào)(!)加入到FOLLOW(Fact)中，由于 Facts 能推導(dǎo)出，所

27、以把FOLLOW(Facts)的所有字符(?)加入到FOLLW(Fact)中。第一遍循環(huán)后我們得到了：在第二遍過程中，) 被加入到FOLLOW(Question)中，因?yàn)樗F(xiàn)在成為了FOLLOW(Session)的成員。第三遍循環(huán)沒有引起什么變動(dòng)，最終結(jié)果是這樣的：使用FOLLOW集來創(chuàng)建Parse Table一旦我們知道每一個(gè)能推導(dǎo)出的非終止符的FOLLOW集合，我們就能構(gòu)建一個(gè)parse table了。首先我們對(duì)每一個(gè)非終止符計(jì)算它的FIRST集，在這個(gè)過程中我們也能知道哪一個(gè)非終止符會(huì)推導(dǎo)出。然后，我們計(jì)算每一個(gè)非終止符的FOLLOW集。接著，從一張空的parse table開始，我們對(duì)

28、每一條語(yǔ)法規(guī)則Aà進(jìn)行如下操作：像我們先前做的那樣，設(shè)FIRST()中的字符為a，我們將右部加入到A,a對(duì)應(yīng)的格子內(nèi)。但是在這一次，如果我們發(fā)現(xiàn)本身是或者能夠推導(dǎo)出時(shí)，我們同樣設(shè)FOLLOW(A)中的符號(hào)為a，把加入A,a的格子里。簡(jiǎn)單來說就是，我們對(duì)在FIRST( FOLLOW(A)中的所有終結(jié)符a，把加入到A,a的格子里。如果一個(gè)通過FOLLOW集合加入的格子中已經(jīng)有了一個(gè)通過FIRST集合加入的右部，就發(fā)生了FIRST/FOLLOW沖突，這種語(yǔ)法不是LL(1)的。也有可能會(huì)發(fā)生FOLLOW/FOLLOW沖突，也就是說一個(gè)格子兩次通過FOLLOW集合加入了兩個(gè)右部，如果超過一個(gè)候選的非終結(jié)符能推導(dǎo)出就會(huì)發(fā)生這一點(diǎn)。讓我們演練一下生成parse table的過程，還是根據(jù)下面的語(yǔ)法：對(duì)于Session -> Facts Question ，我們要先觀察得到FIRST(Facts Question)，從上面的表格能發(fā)現(xiàn)FIRST(Facts)中有，根據(jù)我們前面提到的算法，把去掉，換成FIRST(Que