??銜接上一章的詞法分析，這章就到了語法分析。語法分析大體上分了兩種：自上而下和自下而上。這章的主要內(nèi)容是前者，下一章會(huì)對(duì)后者進(jìn)行介紹。其實(shí)學(xué)到了這里應(yīng)該清楚語法分析和詞法分析的關(guān)系了。在實(shí)際編譯的過程中并不是先進(jìn)行一遍詞法分析，再來一遍語法分析。兩者其實(shí)是并行的。從緩沖區(qū)中讀入一定字符串，經(jīng)過詞法分析合格后進(jìn)行語法的審核。符合語法規(guī)則通過，不符合就報(bào)錯(cuò)。這樣周而復(fù)始直至結(jié)束。

??語法分析要聯(lián)系到第二章的內(nèi)容了，還記得什么是文法嗎？就是那個(gè)使用四元式表示（不過四元式在本章中沒什么地位），表示語法規(guī)則的文法啊。其實(shí)我覺得這章的一個(gè)核心內(nèi)容就是告訴如何利用文法來進(jìn)行語法分析的，更為通俗的一種說法是文法如何找到語法錯(cuò)誤的呢？且聽我慢慢道來！

??先列舉一下本章的關(guān)鍵詞：自上而下、FIRST集、FOLLOW集、LL（1）分析法，遞歸下降分析程序、預(yù)測(cè)分析程序、LL(1)文法的出錯(cuò)處理。

??希望通過這篇文章能說明這些關(guān)鍵詞是什么，更希望說明為什么。下面正式開始吧！

語法分析——自上而下

??這章的題目就是這個(gè)，其實(shí)說白了語法分析就是個(gè)匹配字符串的環(huán)節(jié)嘛。看你輸入的字符串在我已表示的語言中能否找到對(duì)應(yīng)的。之前第二章介紹過對(duì)于任何語法都可以構(gòu)建成一顆語法分析樹。從開始符號(hào)開始，一個(gè)又一個(gè)的產(chǎn)生式銜接，匹配結(jié)束且剛好到達(dá)葉子節(jié)點(diǎn)。整個(gè)過程就是自上而下的語法分析。Hhh，說起來很輕松哈，那如何在那么多個(gè)分岔口找到最正確的一條呢？這就需要學(xué)一下正確的語法分析步驟嘍~

??自上而下也是一個(gè)推導(dǎo)的過程，之前提過推導(dǎo)分為最左推導(dǎo)和最右推導(dǎo)。在自上而下中，統(tǒng)一規(guī)定使用最左推導(dǎo)。

??先來看一個(gè)簡單的例子（這個(gè)例子沒有說明語句是否符合語法規(guī)則，只是表示一下推導(dǎo)過程）：

??在本例中每步都要進(jìn)行一個(gè)產(chǎn)生式的選擇，選擇的原則就是盡可能讓終結(jié)符貼近要表達(dá)的。從字符逐個(gè)匹配的角度看，本例中的字符串一個(gè)個(gè)進(jìn)行匹配并且恰好都是正確（為什么這么說呢？來看下面這個(gè)：）

??對(duì)于上圖中，一眼就可以看見第二才是正確的，但是在計(jì)算機(jī)識(shí)別過程中由于**中的第一個(gè)和xy中達(dá)成了匹配，是不會(huì)立即檢驗(yàn)下一個(gè)字符的。當(dāng)檢驗(yàn)下一個(gè)字符時(shí)原式中是y而自己拼的是*，計(jì)算機(jī)這才知道：哦，錯(cuò)了！其實(shí)錯(cuò)了也沒關(guān)系嘛，可以采用回溯的思想退回到上一個(gè)成功匹配的字符處選擇另一個(gè)產(chǎn)生式，就選到了x*y了。回溯當(dāng)然OK啦！可我們都知道回溯是要多耗費(fèi)一些資源（時(shí)間/空間）的，避免回溯是學(xué)計(jì)算機(jī)人的偉大使命。但似乎隨著算力和空間的發(fā)展，當(dāng)我們真的不在乎回溯的影響時(shí)，就可以肆意妄為了嗎？答案是No!來看下面這個(gè)例子：

??按照前面的思想：不停的回溯重來，結(jié)果就會(huì)使Saaaaaa…aaaa，這樣運(yùn)行下去再大的空間也終有一日會(huì)滿（積硅步，行千里）。這種情況就叫做左遞歸。左遞歸作為語法分析最大的敵人之一，自然需要被先解決。那左遞歸如何可以被消除呢？

消除直接左遞歸的方法

??再配上我獨(dú)門的記憶口訣：引入新的非終結(jié)符，把所有原來沒有左遞歸的項(xiàng)加上新的非終結(jié)符組成一個(gè)產(chǎn)生式，再為新非終結(jié)符構(gòu)造一個(gè)產(chǎn)生式：把之前左遞歸的右邊系數(shù)加上新非終結(jié)符構(gòu)成一個(gè)右遞歸，最后再加上個(gè)空字即可大功告成。

??舉個(gè)例子：

??注意上面的副標(biāo)題我多加了“直接”兩字，只有一眼直接看到S->Sx的才是左遞歸嗎？當(dāng)然沒有這么簡單~看下例：

??如果把三個(gè)產(chǎn)生式一層層消除，就按照SQR的順序依次帶入前者（即Q帶入S，R帶入Q）最后會(huì)得到這樣的結(jié)果：

??當(dāng)出現(xiàn)這樣的情況時(shí)，就發(fā)現(xiàn)上面的解決辦法只能解決直接左遞歸。對(duì)于這種間接的還是比較麻煩。下面介紹一下通用的消除左遞歸辦法：

??其實(shí)這個(gè)說是辦法，方法還是屬于暴力迭代。盡可能消去無用的非終結(jié)符達(dá)到一眼看出直接左遞歸的情況為止，再按照上面的方法解決問題。

??這里有個(gè)事情需要強(qiáng)調(diào)下：第一步對(duì)于順序的排列是無所謂的。選擇不同的順序可能會(huì)導(dǎo)致最后構(gòu)造出的文法不完全相同（因?yàn)樵谶x擇添加新的非終結(jié)符時(shí)，非左遞歸項(xiàng)可能不同），但能完成同樣消除左遞歸的功能即可。

??所以對(duì)于上面問題的解決辦法就是：

??說到現(xiàn)在，左遞歸就基本說完了。其實(shí)回想整個(gè)過程，左遞歸是語法分析必須要避免的。具有消除左遞歸的方法，但同樣也需要付出：引入新的非終結(jié)符。（正所謂：天上不會(huì)掉餡餅~）

??上文介紹到，我們要避免回溯。那想想為什么會(huì)出現(xiàn)回溯呢？不就是因?yàn)橐粋€(gè)“虛假”的匹配嘛？如果我們能夠避免這種虛假，不就可以消除回溯嗎？什么意思呢？比如A->x1|x2|x3…，下個(gè)字符要匹配a，如果x1,x2,x3等所有項(xiàng)中只有一個(gè)第一個(gè)字符是a，那不就直接選這個(gè)，對(duì)了就繼續(xù)走，不對(duì)就匹配失敗唄。這就是提取公共左因子。

提取公共左因子

??其實(shí)這個(gè)方法有點(diǎn)像小時(shí)候?qū)W加法的時(shí)候提取公因式，當(dāng)把公因式提取出來時(shí)對(duì)于當(dāng)前字符只有了唯一項(xiàng)，就不會(huì)出現(xiàn)當(dāng)前字符造成回溯的情況了。需要注意的是：一定要提取最長公共前綴。

FIRST集、FOLLOW集

??按照思路：先懂是什么，再懂為什么？先對(duì)如何計(jì)算兩種集合做一個(gè)介紹。

FIRST集

??FIRST集的全名叫做終結(jié)首符集，每一個(gè)非終結(jié)符都有。就是由該非終結(jié)符能夠推導(dǎo)出的第一個(gè)終結(jié)符或空字組成的集合。看一下標(biāo)準(zhǔn)的概念：

??那求某一非終結(jié)符FIRST集的步驟呢？看下面（先形式化的定義下，后面有配合的例題進(jìn)行講解）：

FOLLOW集

??FOLLOW集是推導(dǎo)過程中非終結(jié)符緊接著的終結(jié)符組成的集合。

??對(duì)于FOLLOW集有兩個(gè)需要特別注意：

????1）對(duì)于起始符的FOLLOW集需要引入“#”符號(hào)

????2） 在FOLLOW集中不可能出現(xiàn)空字ε

??求FOLLOW集的步驟如下：

??從上面可知，FOLLOW集只關(guān)注于產(chǎn)生式的右邊。對(duì)于某一非終結(jié)符，影響其FOLLOW集的只是右邊包含該非終結(jié)符的產(chǎn)生式。

??如果你從上面文字性的就看懂了，求解FIRST集和FOLLOW集的步驟。那你真是個(gè)天才，像我這種稍微有點(diǎn)兒笨的只能看看例題理解理解哈：

??這類題順序是先求解FIRST集再求解FOLLOW集。

??對(duì)于FIRST(E)，E的產(chǎn)生式第一項(xiàng)是T是非終結(jié)符，所以求E必須先求出T的FIRST集，FIRST（T）中的內(nèi)容都屬于FIRST(E)。轉(zhuǎn)而求解FIRST(T)，T的產(chǎn)生式第一項(xiàng)是F，轉(zhuǎn)而求解F。F的第一項(xiàng)有兩個(gè)并且均為終結(jié)符——{(,i};所以可反推出FIRST(E/T/F)均為{（，i}；求解FIRST(E’)，E‘有兩項(xiàng)組成第一個(gè)是終結(jié)符+，加入集合。第二個(gè)是空字，按照定義也加入集合。最終得到{+，ε}。同理可得FIRST(T’)為{*，i}；

?? 對(duì)于FOLLOW集，首先E作為開始符，先將#加入FOLLOW（E）中，接著尋找右側(cè)產(chǎn)生式帶E的，看后面是否為終結(jié)符。本例中E后只有），將其加入FOLLOW（E）中。對(duì)于E’，在前兩個(gè)產(chǎn)生式中出現(xiàn)，但后面無任何符號(hào)（相當(dāng)于空字ε），于是順承左邊非終結(jié)符的FOLLOW集，即FOLLOW（E）。并且FIRST（E）中無空字ε。FOLLOW（E’）= FOLLOW(E) = { ），#}。接著計(jì)算FOLLOW（T）,T后為E’，于是將FOLLOW（E’）及非字FIRST（E‘）加入T中，得出FOLLOW(T)={+，），#}。對(duì)于T’后無字符，順承T，且FIRST(T)中無空字，FOLLOW(T‘)=FOLLOW（T’）。F后為T‘，FIRST(T’)含有空字，將FIRST集非空字符及FOLLOW(T‘)加入FOLLOW(F)中={*，+，），#}。

??弄懂以上的兩個(gè)過程，證明已經(jīng)會(huì)求解FIRST集和FOLLOW集了，也許可以參加考試了。但是為什么需要FIRST集和FOLLOW集呢？仔細(xì)想想FIRST集和FOLLOW集究竟干了什么呢？我將其理解為開始匹配和繼續(xù)匹配。當(dāng)我們面臨一個(gè)新的非終結(jié)符時(shí)，可能由于產(chǎn)生式的多個(gè)或，選錯(cuò)了就要進(jìn)行回溯。務(wù)必一擊就中，就可以通過FIRST集，FIRST集中每一項(xiàng)都是可直接到達(dá)，且路線唯一。而FOLLOW集就是當(dāng)前非終結(jié)符下一個(gè)終結(jié)符可以是哪個(gè)？如果當(dāng)前的符號(hào)不在備選范圍內(nèi)，就說明不存在下一個(gè)到達(dá)提供字符的可能，即認(rèn)定失敗。成功繼續(xù)，失敗結(jié)束。兩個(gè)集合起的作用就是讓一切看起來盡量直觀。

LL(1)文法

?? LL（1）文法是一類特殊的文法，其需滿足的條件如下：

??其實(shí)LL(1)文法就是進(jìn)行語法分析的一整套流程，滿足該文法字符串有效。不滿足就無效。之前一直在糾結(jié)于：LL(1)文法的作用是什么呢？其實(shí)LL(1)也是一種文法，文法就是用來定義語言的。不過LL1(1)文法特殊在有很多特別的限制。

遞歸下降分析程序

??其實(shí)遞歸下降程序就是文法（該文法需要確保已無左遞歸以及公共因子的情況，即LL(1)文法）的分析過程。把每一個(gè)產(chǎn)生式寫成了一個(gè)程序。所以對(duì)于任何一個(gè)非終結(jié)符都有一個(gè)屬于子集的程序。我把這個(gè)理解成貼近于高級(jí)語言的語法分析檢測(cè)過程。文字性的定義放一張圖：

??舉一個(gè)例子，再加上我總結(jié)的一點(diǎn)兒規(guī)律吧：

??程序開頭：PROCEDURE xxx(非終結(jié)符名稱)

??對(duì)于直接由非終結(jié)符組成，如E和T。BEGIN和END中間夾著產(chǎn)生式右端所有非終結(jié)符，以分號(hào)連接。對(duì)于第一項(xiàng)為終結(jié)符，如果是匹配的就調(diào)用ADVANCE。SYM代表當(dāng)前獲取到的單詞（即輸入字符）。如果是非終結(jié)符就調(diào)用相應(yīng)的過程。空字需要特殊處理（雖然在上面的圖里沒有展示出來），什么時(shí)候可以使用空字去進(jìn)行匹配呢？當(dāng)需要空字說明目前的SYM與非終結(jié)符不匹配。SYM可能是當(dāng)前非終結(jié)符的FOLLOW集，那么對(duì)當(dāng)前非終結(jié)符使用空字匹配就可以保證對(duì)SYM的匹配。但這有一個(gè)要求：SYM必須在取空字非終結(jié)符的FOLLOW集中使才可以。否則就是一種錯(cuò)誤。說的有點(diǎn)復(fù)雜：簡單點(diǎn)就是要想成功的取到空字，當(dāng)前的輸入字符必須在非終結(jié)符的FOLLOW集中。

擴(kuò)充的巴科斯范式

??擴(kuò)充的巴科斯范式是對(duì)文法符號(hào)的擴(kuò)展，具體擴(kuò)展包括三種：

??對(duì)以上做個(gè)小結(jié)：

??遞歸下降程序就是自頂向下的語法分析，擴(kuò)充的巴科斯范式是表示文法的一種方法，并且該方法能夠比較容易的處理左遞歸問題。

預(yù)測(cè)分析程序

?? 到了預(yù)測(cè)分析程序就有點(diǎn)偏實(shí)用了，采用預(yù)測(cè)表和棧結(jié)合的方法。對(duì)一個(gè)字符串進(jìn)行判斷。

??預(yù)測(cè)分析表的作用就是能夠直觀看出當(dāng)前非終結(jié)符在指定輸入下選擇哪個(gè)具體的產(chǎn)生式。表的列項(xiàng)是所有的非終結(jié)符，橫項(xiàng)是所有的終結(jié)符。具體的坐標(biāo)要么是產(chǎn)生式要么為空（說明不存在）。形式化的定義如下：

??還拿剛才的例子，說一下預(yù)測(cè)分析表怎么構(gòu)造：

??想求預(yù)測(cè)分析表還是要先求出FIRST和FOLLOW集。按順序說，寫每一個(gè)的時(shí)候先看FIRST集，對(duì)非終結(jié)符求每一個(gè)候選式的FIRST集合。結(jié)果大體可分為兩類：有空字和無空字。對(duì)于無空字像E和T，在FIRST集合對(duì)應(yīng)的單元格填入該候選式。比如i輸入E的FIRST集。在（E，i）中填入候選式E->TE’。如果FIRST集合含有空字，說明xxx->ε。則在該非終結(jié)符的FOLLOW集對(duì)應(yīng)的單元格放入該產(chǎn)生式。比如E‘的FIRST集中包含空字，并且FOLLOW（E’）={}，#}。于是在<E’，）>、<E’,#>中加入產(chǎn)生式E’->ε

?? 需要注意兩個(gè)事情：

????1. 空出來的地方就是不合法的情況

????2. 表內(nèi)每個(gè)產(chǎn)生式右端只可能出現(xiàn)一種情況

??說完了表，再說說棧。都知道棧是一種數(shù)據(jù)結(jié)構(gòu)——后進(jìn)先出。還記得前面說要在起始符的FOLLOW集中加入#嘛？這就是為了在此匹配。在輸入字符串的最后加入#，如果兩個(gè)#匹配到，說明分析結(jié)束。結(jié)束不代表正確。下文關(guān)于錯(cuò)誤處理會(huì)給出解釋。對(duì)于棧，在此不在多說（其實(shí)是我也不會(huì)，不過上機(jī)的時(shí)候應(yīng)該需要。如果過后搞懂了，再來補(bǔ)充）。附上形式化描述：

LL(1)文法中的出錯(cuò)處理：

??文法中的錯(cuò)誤難免出現(xiàn)，但如果一出錯(cuò)就全部停止。未免有些影響效率。我們崇尚的是那種報(bào)錯(cuò)了保留錯(cuò)誤位置并且程序能夠繼續(xù)執(zhí)行的情況。如果在預(yù)測(cè)分析處理的過程中發(fā)現(xiàn)了錯(cuò)誤，錯(cuò)誤分兩種：

??錯(cuò)誤一：棧頂?shù)慕K結(jié)符與當(dāng)前的輸入符號(hào)不匹配

??錯(cuò)誤二：非終結(jié)符A處于棧頂，面臨的輸入符號(hào)為a，但預(yù)測(cè)分析表中M的M[A,a]為空。

??解決方法采用忽略的思想，不斷跳過直至下一次匹配再此出現(xiàn)。（此處解釋了分析結(jié)束并不代表語法正確）

??說到這里自上而下的語法分析主要內(nèi)容就基本結(jié)束了，整個(gè)過程說起來比較簡單。但如果真正實(shí)現(xiàn)起來想必是困難重重。收拾心態(tài)，準(zhǔn)備迎接更大的挑戰(zhàn)，繼續(xù)加油叭~

感謝編譯原理課程謝老師對(duì)本文的耐心修改，同時(shí)感謝各位博主的優(yōu)秀文章作為參考。

因作者水平有限，如有錯(cuò)誤之處，請(qǐng)?jiān)谙路皆u(píng)論區(qū)指出，謝謝！

總結(jié)

以上是生活随笔為你收集整理的语法分析——自上而下的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。