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

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

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

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

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

　　LL（1）分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

　　3． 一個(gè)LR語法分析器可以在對(duì)輸入進(jìn)行從左到右掃描時(shí)盡可能早地檢測(cè)到錯(cuò)誤。

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

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

　　1. LR（0）分析

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

　　2. SLR（1）分析

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

　　3. LR（1）分析

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

　　4. LALR（1）分析

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