編譯原理語法分析總結(jié)：

　　語法分析是編譯原理的核心部分。語法分析的作用是識別由詞法分析給出的單詞符號序列是否是給定文法的正確句子，目前語法分析常用的方法有自頂向下分析和自底向上分析兩大類。自頂向下分析包括確定分析和不確定分析，自底向上分析又包括算符優(yōu)先分析法和LR分析，這些分析方法各有優(yōu)缺點。下面分別就自頂向下語法分析方法和自底向上語法分析方法展開描述：

　　A. 自頂向下語法分析方法

　　自頂向下分析法也稱面向目標(biāo)的分析方法，也就是從文法的開始符號出發(fā)企圖推導(dǎo)出與輸入的單詞串完全相匹配的句子，若輸入串是給定文法的句子，則必能推出，反之必然出錯。自頂向下的確定分析方法需對文法有一定的限制，但由于實現(xiàn)方法簡答、直觀，便于手工構(gòu)造或自動生成語法分析器，因而仍是目前常用的方法之一。而自頂向下的不確定分析方法是帶回溯的分析方法，這種方法實際上是一種窮舉的試探方法，因此效率低，代價高，因而極少使用。

　　LL（1）分析

　　自頂向下的確定分析方法，是從文法的開始符號出發(fā)，考慮如何根據(jù)當(dāng)前的輸入符號（單詞符號）唯一地確定選用哪個產(chǎn)生式替換相應(yīng)非終結(jié)符以往下推導(dǎo)，或如何構(gòu)造一棵相應(yīng)的語法樹。當(dāng)我們需要選用自頂向下的確定分析技術(shù)時，首先必須判別所給文法是否是LL（1）文法。因而對所給文法需計算FIRST、FOLLOW、SELECT集合，進而判別文法是否為LL（1）文法。LL（1）文法表示了自頂向下方法能夠處理的一類文法。LL（1）第一個“L”表示從左向右掃描輸入，第二個“L”表示產(chǎn)生最左推導(dǎo)，而“1”則表示每一步中只需要向前看一個輸入符號來決定語法分析動作。類似也可以有LL（k）文法，也就是需向前查看k個符號才可以確定選用哪個產(chǎn)生式。通常采用k=1，個別情況采用k=2。LL（1）文法已經(jīng)足以描述大多數(shù)程序設(shè)計語言構(gòu)造，雖然在為源語言設(shè)計適當(dāng)?shù)奈姆〞r需要多加小心。比如，左遞歸的文法和二義性的文法都不可能是LL（1）的。一個文法G是LL（1）的，當(dāng)且僅當(dāng)G的任意兩個不同的產(chǎn)生式A-》α|β滿足下面的條件：

　　1） 不存在終結(jié)符號a使得α和β都能夠推導(dǎo)出以a開頭的串。

　　2） α和β中最多只有一個可以推導(dǎo)出空串。

　　3） 如果βT*ε，那么α不能推導(dǎo)出任何以FOLLOW（A）中某個終結(jié)符號開頭的串。類似地，如果αT*ε，那么β不能推導(dǎo)出任何以FOLLOW（A）中某個終結(jié)符號開頭的串。

　　我們知道當(dāng)文法不滿足LL（1）時，則不能用確定的自頂向下分析，但在這種情況下可用不確定的自頂向下分析，也就是帶回溯的自頂向下分析。引起回溯的原因是在文法中當(dāng)關(guān)于某個非終結(jié)符的產(chǎn)生式有多個候選時，而面臨當(dāng)前的輸入符無法確定選用唯一的產(chǎn)生式，從而引起回溯。引起回溯的情況大致有3種：

　　1） 由于相同的左部的產(chǎn)生式的右部FIRST集交集不為空而引起回溯；

　　2） 由于相同左部非終結(jié)符的右部存在能T*ε的產(chǎn)生式，且該非終結(jié)符的FOLLOW集中含有其他產(chǎn)生式右部FIRST集的元素；

　　3） 由于文法含有左遞歸而引起回溯。

　　B. 自底向上語法分析方法

　　自底向上分析，也稱移近-歸約分析，粗略地說它的實現(xiàn)思想是對輸入符號串自左向右進行掃描，并將輸入符逐個移入一個后進先出棧中，邊移入邊分析，一旦棧頂符號串形成某個句型的句柄或可歸約串時（該句柄或可歸約串對應(yīng)某產(chǎn)生式的右部），就用該產(chǎn)生式的左部非終結(jié)符代替相應(yīng)右部的文法符號串，這稱為一步歸約。重復(fù)這一過程直到歸約到棧中只剩文法的開始符號時則為分析成功，也就確認(rèn)輸入串是文法的句子。

　　目前最流行的自底向上語法分析器都基于所謂的LR（k）語法分析的概念。其中，“L”表示對輸入進行從左到右的掃描，“R”表示反向構(gòu)造出一個最右推導(dǎo)序列，而k表示在做出語法分析決定時向前看k個輸入符號。

　　LR語法分析技術(shù)優(yōu)點：

　　1． 對于幾乎所有的程序設(shè)計語言構(gòu)造，只要能夠?qū)懗鲈摌?gòu)造的上下文無關(guān)文法，就能夠構(gòu)造出識別該構(gòu)造的LR語法分析器。確實存在非LR的上下文無關(guān)文法，但一般來說，常見的程序設(shè)計語言構(gòu)造都可以避免使用這樣的文法。

　　2． LR語法分析方法是已知的最通用的無回溯移入-歸約分析技術(shù)，并且它的實現(xiàn)可以和其他更原始的移入-歸約方法一樣高效。

　　3． 一個LR語法分析器可以在對輸入進行從左到右掃描時盡可能早地檢測到錯誤。

　　4． 可以使用LR方法進行語法分析的文法類是可以使用預(yù)測方法或LL方法進行語法分析的文法類的真超集。一個文法是LR（k）的條件是當(dāng)我們在一個最右句型中看到某個產(chǎn)生式的右部時，我們再向前看k個符號就可以決定是否使用這個產(chǎn)生式進行歸約。這個要求比LL（k）文法的要求寬松很多。對于LL（k）文法，我們在決定是否使用某個產(chǎn)生式時，只能向前看該產(chǎn)生式右部推導(dǎo)出的串的前k個符號。因此，LR文法能夠比LL文法描述更多的語言就一點也不奇怪了。

　　LR方法的主要缺點是為了一個典型的程序設(shè)計語言文法手工構(gòu)造LR分析器的工作量非常大，k愈大構(gòu)造愈復(fù)雜，實現(xiàn)比較困難。常見的LR方法有LR（0）、SLR（1）、LALR（1）和LR（1），其中SLR（1）和LALR（1）分別是LR（0）和LR（1）的一種改進。下面主要介紹這四種LR分析方法：

　　1. LR（0）分析

　　LR（0）分析器是在分析過程中不需向右查看輸入符號，因而它對文法的限制較大，對絕大多數(shù)高級語言的語法分析器是不能適用的，然而，它是構(gòu)造其他LR類分析器的基礎(chǔ)。LR（0）分析表構(gòu)造的思想和方法是構(gòu)造其他LR分析表的基礎(chǔ)，它是LR（0）分析器的重要組成部分，它是總控程序分析動作的依據(jù)。對于不同的文法，LR（0）分析表不同，它可以用一個二維數(shù)組表示，行標(biāo)為狀態(tài)號，列標(biāo)為文法符號和“#”號，分析表的內(nèi)容可由兩部分組成，一部分為動作（ACTION）表，它表示當(dāng)前狀態(tài)下所面臨輸入符應(yīng)做的動作是移近、歸約、接受或出錯，動作表的行標(biāo)只包含終結(jié)符和“#”，另一部分為轉(zhuǎn)換（GOTO）表，它表示在當(dāng)前狀態(tài)下面臨文法符號時應(yīng)轉(zhuǎn)向的下一個狀態(tài)，相當(dāng)于識別活前綴的有限自動機DFA 的狀態(tài)轉(zhuǎn)換矩陣。我們知道LR（0）對文法的限制較大，它要求對一個文法的LR（0）項目集規(guī)范族不存在移近-歸約，或歸約-歸約沖突。所謂移近-歸約沖突也就是在一個項目集中移近和歸約項目同時存在，而歸約-歸約沖突是在一個項目集中歸約和歸約項目同時存在。

　　2. SLR（1）分析

　　由于大多數(shù)實用的程序設(shè)計語言的文法不能滿足LR（0）文法的條件，經(jīng)過改進后得到了一種新的SLR（1）文法，其思想是基于容許LR（0）規(guī)范族中有沖突的項目集（狀態(tài)）用向前查看一個符號的辦法來進行處理，已解決沖突。因為只有對有沖突的狀態(tài)才向前查看一個符號，以確定做哪種動作，所以稱這種分析方法為簡單的LR（1）分析法，用SLR（1）表示。通常對于LR（0）規(guī)范族的一個項目集I可能含有多個項目和多個歸約項目，假設(shè)項目集I中有m個移近項目：A1-》α1 ?α1β1，A2-》α2 ?α2β2，… ， Am-》αm ?αmβm；同時含有n個歸約項目為：B1-》γ1? ，B1-》γ1? ， … ，Bn-》γn? 只要集合{α1 ，α2 ，… ，αm}和FOLLOW（B1），F(xiàn)OLLOW（B2），… ，F(xiàn)OLLOW（Bn）兩兩交集都為空，那么我們可以考察當(dāng)前輸入符號決定動作，解決沖突。盡管采用SLR（1）方法能夠?qū)δ承㎜R（0）項目集規(guī)范族中存在動作沖突的項目集，通過用向前查看一個符號的辦法來解決沖突，但是仍有很多文法構(gòu)造的LR（0）項目集規(guī)范族存在的動作沖突不能用SLR（1）方法解決。當(dāng)集合{α1 ，α2 ，… ，αm}和FOLLOW（B1），F(xiàn)OLLOW（B2），… ，F(xiàn)OLLOW（Bn）之間存在交集不為空的情況，則不能根據(jù)當(dāng)前輸入符號決定動作，存在動作沖突。

　　3. LR（1）分析

　　可以看出SLR（1）方法雖然相對LR（0）有所改進，但仍然存在著多余歸約，也說明SLR（1）方法向前查看一個符號的方法仍不夠確切，LR（1）方法恰好是要解決SLR（1）方法在某些情況下存在的無效歸約問題。LR（1）對比SLR（1）而言，多了向前搜索符這個概念。根據(jù)項目集構(gòu)造原則有：若［A-》α?Bβ］ ∈項目集I時。則［B-》?γ］也∈I（B-》γ為一產(chǎn)生式）。由此不妨考慮，把FIRST（β）作為用產(chǎn)生式B-》γ歸約的搜索符，稱為向前搜索符，作為歸約時查看的符號集合用以代替SLR（1）分析中的FOLLOW集，把此搜索符號的集合也放在相應(yīng)項目的后面，這種處理方法即為LR（1）方法。在多數(shù)情況下，對LR（1）的歸約項目不存在任何無效歸約，但同一個文法的LR（1）項目集的個數(shù)比LR（0）項目集的個數(shù)多，甚至可能多好幾倍。這是由于同一個LR（0）項目集的搜索符集合不同，多個搜索符集合則對應(yīng)著多個LR（1）項目集。這可以看成是LR（1）項目集的構(gòu)造使某些同心集進行了分裂，因而項目集的個數(shù)增多了。如果一個文法的LR（1）分析表不含多重入口時，（即任何一個LR（1）項目集中無移近-歸約沖突或歸約-歸約沖突），則稱該文法為LR（1）文法。LR（1）文法已能滿足當(dāng)前絕大多數(shù)高級語言編譯程序的需要。

　　4. LALR（1）分析

　　LR（1）分析表的構(gòu)造對搜索符的計算方法比較確切，對文法放寬了要求，也就是適應(yīng)的文法類廣，可以解決SLR（1）方法解決不了的問題，但是，由于它的構(gòu)造對某些同心集的分裂可能對狀態(tài)數(shù)目引起劇烈的增長，從而導(dǎo)致存儲容量的急劇增長，也使應(yīng)用受到了一定的限制，為了克服LR（1）的這種缺點，我們可以采用對LR（1）項目集規(guī)范族合并同心集的方法，若合并同心集后不產(chǎn)生新的沖突，則為LALR（1）項目集。它的狀態(tài)個數(shù)與LR（0）、SLR（1）的相同。關(guān)于合并同心集有幾個問題需要說明：1）同心集是指心相同的項目集合并在一起，因此同心集合并后心仍然相同，只是超前搜索符集合為各同心集超前搜索符集合的合集；2）對于合并同心集后的項目集經(jīng)轉(zhuǎn)換函數(shù)所達仍為同心集；3）若文法是LR（1）文法，合并同心集后若有沖突也只可能是歸約-歸約沖突，而不可能產(chǎn)生移近-歸約沖突；4）合并同心集后對某些錯誤發(fā)現(xiàn)的時間會產(chǎn)生推遲現(xiàn)象，但錯誤的出現(xiàn)位置仍是準(zhǔn)確的。這意味著LALR（1）分析表比LR（1）分析表對同一輸入串的分析可能會有多余歸約。