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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

18、183;un)中就可以了。如果 FIRST(u1), FIRST(u2), . FIRST(un) 都包含，我們就把加到FIRST(u1u2 ···un) ，表示所有的選項都是透明的。對于一些算法，我們需要知道一個非終結(jié)符A能否推導出，只需要查看是否在FIRST(A)中就可以了。因為就像上面說的那樣，如果能被A所導出，那么它也一定在FIRST(A)中。如果你沒對此厭煩的話，我們再來演練一下對于圖表8.9的FIRST集合的計算。首先我們先設(shè)置所有的集合為空。接著，我們對每一條語法進行處理對于Session -> Facts Question，把FIRST(Fa

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

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

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

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

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

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

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

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

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

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