編譯原理語法分析總結：

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

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

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

　　LL（1）分析

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

　　1） 不存在終結符號a使得α和β都能夠推導出以a開頭的串。

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

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

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

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

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

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

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

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

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

　　LR語法分析技術優點：

　　1． 對于幾乎所有的程序設計語言構造，只要能夠寫出該構造的上下文無關文法，就能夠構造出識別該構造的LR語法分析器。確實存在非LR的上下文無關文法，但一般來說，常見的程序設計語言構造都可以避免使用這樣的文法。

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

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

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

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

　　1. LR（0）分析

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

　　2. SLR（1）分析

　　由于大多數實用的程序設計語言的文法不能滿足LR（0）文法的條件，經過改進后得到了一種新的SLR（1）文法，其思想是基于容許LR（0）規范族中有沖突的項目集（狀態）用向前查看一個符號的辦法來進行處理，已解決沖突。因為只有對有沖突的狀態才向前查看一個符號，以確定做哪種動作，所以稱這種分析方法為簡單的LR（1）分析法，用SLR（1）表示。通常對于LR（0）規范族的一個項目集I可能含有多個項目和多個歸約項目，假設項目集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），FOLLOW（B2），… ，FOLLOW（Bn）兩兩交集都為空，那么我們可以考察當前輸入符號決定動作，解決沖突。盡管采用SLR（1）方法能夠對某些LR（0）項目集規范族中存在動作沖突的項目集，通過用向前查看一個符號的辦法來解決沖突，但是仍有很多文法構造的LR（0）項目集規范族存在的動作沖突不能用SLR（1）方法解決。當集合{α1 ，α2 ，… ，αm}和FOLLOW（B1），FOLLOW（B2），… ，FOLLOW（Bn）之間存在交集不為空的情況，則不能根據當前輸入符號決定動作，存在動作沖突。

　　3. LR（1）分析

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

　　4. LALR（1）分析

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