第四章語法分析

1、第四章語法分析本章介紹的語法分析方法通常被用于編譯器中。我們首先給出基本概念，然后給出適用于手工實(shí)現(xiàn)的技術(shù)，最后是已經(jīng)被用于自動(dòng)化工具的算法。因?yàn)樵闯绦蚩赡馨Z法錯(cuò)誤，我們討論了如何擴(kuò)展語法分析方法，使之可以從常見錯(cuò)誤中恢復(fù)。在語言設(shè)計(jì)時(shí)，每個(gè)程序設(shè)計(jì)語言都有一組精確的規(guī)則來描述了良構(gòu)(well-formed)程序的語法結(jié)構(gòu)。比如，在C中一個(gè)程序由多個(gè)函數(shù)組成，一個(gè)函數(shù)由聲明和語句組成，一個(gè)語句由表達(dá)式組成，等等。程序設(shè)計(jì)語言構(gòu)造的語法可以使用2.2節(jié)中介紹的上下文無關(guān)文法或者BNF（巴庫斯-瑙爾范式）表示法來描述。文法給語言設(shè)計(jì)者和編譯器作者都提供了很大的幫助。l 文法給出了一個(gè)程序設(shè)計(jì)語

2、言的精確易懂的語法規(guī)約。l 對(duì)于某些類型的文法，我們可以自動(dòng)地構(gòu)造出高效的語法分析器，它能夠得出一個(gè)源程序的語法構(gòu)造。另一個(gè)附帶的好處是，語法分析器的構(gòu)造過程可以揭示出語法的二義性，同時(shí)還可能發(fā)現(xiàn)一些容易在語言的初始設(shè)計(jì)階段被忽略的問題。l 一個(gè)正確設(shè)計(jì)的文法給出了一個(gè)語言的結(jié)構(gòu)。該結(jié)構(gòu)有助于把源程序翻譯為正確的目標(biāo)代碼，也有助于錯(cuò)誤檢測(cè)。l 一個(gè)文法允許語言迭代地演化和開發(fā)，逐步加入可以完成新任務(wù)的新語言構(gòu)造。如果對(duì)語言的實(shí)現(xiàn)遵循語言的文法結(jié)構(gòu)，那么加入這些新構(gòu)造的工作就變得相對(duì)容易。4.1 引論在本節(jié)中，我們將考察語法分析器是按照什么方法被集成到一個(gè)典型的編譯器中的。然后我們將研究算術(shù)表達(dá)

3、式的典型文法。表達(dá)式文法已經(jīng)足以演示語法分析的本質(zhì)，因?yàn)樘幚肀磉_(dá)式的語法分析技術(shù)可以被用于處理程序設(shè)計(jì)語言的大部分構(gòu)造。這一節(jié)的最后討論了錯(cuò)誤處理的問題，因?yàn)楫?dāng)語法分析程序發(fā)現(xiàn)它的輸入不能由它的文法生成時(shí)，它必須作出得體的反應(yīng)。4.1.1 語法分析器的角色在我們的編譯器模型中，語法分析器從詞法分析器獲得一個(gè)由詞法單元組成的串，并驗(yàn)證這個(gè)串可以由源語言的文法生成，如圖4.1所示。我們期望語法分析器能夠以易于理解的方式報(bào)告語法錯(cuò)誤，并且能夠從常見的錯(cuò)誤中恢復(fù)并繼續(xù)處理程序的其余部分。從概念上講，對(duì)于良構(gòu)的程序，語法分析器構(gòu)造出一棵語法分析樹，并把它傳遞給編譯器的其余部分進(jìn)一步處理。實(shí)際上并不需要顯

4、式地構(gòu)造出這棵語法分析樹，因?yàn)檎缥覀儗⒖吹降?，?duì)源程序的檢查和翻譯處理可以和語法分析過程交錯(cuò)完成。因此，語法分析器和前端的其它部分可以用一個(gè)模塊來實(shí)現(xiàn)。Source program源程序Lexical Analyzer詞法分析器token詞法單元get next token獲取下一個(gè)詞法單元Parser語法分析器parse tree語法分析樹Rest of Front End前端的其余部分intermediate representation中間表示Symbol Table符號(hào)表圖4.1：語法分析器在編譯器模型中的位置處理文法的語法分析器大體上可以分為三種類型：通用的、自頂向下的、和自底向上

5、的。象Cocke-Younger-Kasami算法和Earley算法這樣的通用語法分析方法可以對(duì)任意文法進(jìn)行語法分析（見參考文獻(xiàn)）。然而，這些通用方法效率很低，不能用于編譯器產(chǎn)品。編譯器中常用的方法可以分為自頂向下的和自底向上的。正如它們的名字所指出的，自頂向下的方法從語法分析樹的頂部（根結(jié)點(diǎn)）開始向底部（葉子結(jié)點(diǎn)）構(gòu)造樹，而自底向上的方法從葉子結(jié)點(diǎn)開始，逐漸向頂部構(gòu)造。這兩種分析方法中，語法分析器的輸入總是按照從左向右的方式被掃描，每次掃描一個(gè)符號(hào)。最高效的自頂向下方法和自底向上方法只能處理某些文法子類，但其中的某些子類，特別是LL和LR文法，的表達(dá)能力已經(jīng)足以描述現(xiàn)代程序設(shè)計(jì)語言的大部分語

6、法構(gòu)造了。手工實(shí)現(xiàn)的語法分析器通常使用LL文法；比如2.4.2節(jié)中的預(yù)測(cè)分析方法能夠處理LL文法。處理較大的LR文法類的語法分析器常常是由自動(dòng)化工具構(gòu)造得到的。在本章中，我們假設(shè)語法分析器的輸出是語法分析樹的某種表示形式。該語法分析樹對(duì)應(yīng)于來自詞法分析器的詞法單元流。在實(shí)踐中，語法分析過程中可能完成多個(gè)任務(wù)，比如將不同詞法單元的信息收集到符號(hào)表中，進(jìn)行類型檢查和其它類型的語義分析，以及生成中間代碼。我們把所有這些活動(dòng)都?xì)w到圖4.1中的方框“前端的其余部分”里面。在后續(xù)幾章中將詳細(xì)討論這些活動(dòng)。4.1.2 代表性的文法為了便于參考，我們?cè)谶@里給出一些即將在本章中分析的文法。對(duì)那些以while或i

7、nt這樣的關(guān)鍵字開頭的構(gòu)造進(jìn)行語法分析相對(duì)容易，因?yàn)檫@個(gè)關(guān)鍵字可以引導(dǎo)我們選擇適當(dāng)?shù)奈姆óa(chǎn)生式來匹配輸入。因此我們主要關(guān)注表達(dá)式。因?yàn)楸磉_(dá)式的結(jié)合性和優(yōu)先級(jí)問題，對(duì)表達(dá)式的處理更具挑戰(zhàn)性。下面的文法指明了表達(dá)式的結(jié)合性和優(yōu)先級(jí)。這個(gè)文法和我們?cè)诘?章中使用的文法類似，它描述了表達(dá)式、項(xiàng)和因子。E表示了以+號(hào)分隔的一組項(xiàng)所組成的表達(dá)式；T表示由以*號(hào)分隔的一組因子所組成的項(xiàng)；而F表示因子，它可能是括號(hào)括起的表達(dá)式，也可能是標(biāo)識(shí)符：EàE+T | TTàT*F | F(4.1)Fà(E) | id表達(dá)式文法(4.1)屬于LR文法類，適于使用自底向上的識(shí)別技術(shù)。這個(gè)文法

8、經(jīng)過修改可以處理更多的運(yùn)算符和更多的優(yōu)先級(jí)層次。然而，它不能被用于自頂向下的語法分析，因?yàn)樗亲筮f歸的。下面給出表達(dá)式文法（4.1）的無左遞歸版本，該版本將被用于自頂向下的語法分析：E à T EEà + T E | T à F T(4.2)T à * F T | F à ( E ) | id下面的文法以相同的方式處理+和*，因此它可以被用來演示那些在語法分析過程中處理二義性的技術(shù)：E à E + E | E * E | ( E ) | id(4.3)這里E表示各種類型的表達(dá)式。文法(4.3)允許一個(gè)表達(dá)式，比如a+b*c，具有多棵語

9、法分析樹。4.1.3 語法錯(cuò)誤的處理本節(jié)的其余部分考慮語法錯(cuò)誤的特性以及錯(cuò)誤恢復(fù)的一般性策略。其中的兩種策略分別被稱為恐慌模式和短語層次恢復(fù)。它們將和特定的語法分析方法一起詳細(xì)討論。如果一個(gè)編譯器只需要處理正確的程序，那么它的設(shè)計(jì)和實(shí)現(xiàn)將會(huì)大大簡化。然而，人們還期望編譯器能夠幫助程序員定位和跟蹤錯(cuò)誤。不管程序員如何努力，總會(huì)有錯(cuò)誤溜進(jìn)程序。令人驚奇的是，雖然錯(cuò)誤是如此常見，很少有語言在設(shè)計(jì)的時(shí)候就考慮了錯(cuò)誤處理問題。如果我們的口語也需要具有象計(jì)算機(jī)語言那樣的語法精確性，那么我們的文明就會(huì)有非常大的不同。大部分程序設(shè)計(jì)語言的規(guī)范沒有規(guī)定編譯器應(yīng)該如果處理錯(cuò)誤；錯(cuò)誤處理方法由編譯器的設(shè)計(jì)者決定。一

10、開始就計(jì)劃好如何進(jìn)行錯(cuò)誤處理不僅可以簡化編譯器的結(jié)構(gòu)，還可以改進(jìn)它的錯(cuò)誤處理方法。常見的程序錯(cuò)誤可能出現(xiàn)在多個(gè)不同的層次上。l 詞法錯(cuò)誤，包括標(biāo)識(shí)符、關(guān)鍵字或運(yùn)算符的錯(cuò)誤拼寫，比如把標(biāo)識(shí)符ellipseSize寫成elipseSize。它還包括沒有在字符串文本上正確地加上引號(hào)。l 語法錯(cuò)誤，包括放錯(cuò)地方的分號(hào)、多余或缺失的花括號(hào)，即“”或“”。另一個(gè)語法錯(cuò)誤例子是在C或Java中，一個(gè)case語句的外圍沒有相應(yīng)的switch語句。（然而，語法分析器通常允許這種情況出現(xiàn)，當(dāng)編譯器在之后要生成代碼時(shí)才會(huì)發(fā)現(xiàn)這個(gè)錯(cuò)誤）。l 語義錯(cuò)誤，包括運(yùn)算符和運(yùn)算分量之間的類型不匹配。例子之一是返回類型為void

11、的某個(gè)Java例程中出現(xiàn)了一個(gè)返回某個(gè)值的return語句。l 邏輯錯(cuò)誤，可以是因程序員的錯(cuò)誤推理而引起的任何錯(cuò)誤。比如在一個(gè)C程序中該使用比較運(yùn)算符=的地方使用了賦值運(yùn)算符=。這樣的程序可能是良構(gòu)的；但是卻可能沒有正確反映出程序員的意圖。語法分析方法的精確性使得我們可以非常高效地檢測(cè)語法錯(cuò)誤。有些語法分析方法，比如LL和LR方法，能夠在第一時(shí)間發(fā)現(xiàn)錯(cuò)誤；就是說，當(dāng)來自詞法分析器的詞法單元流不能根據(jù)該語言的文法進(jìn)一步分析時(shí)就可以發(fā)現(xiàn)錯(cuò)誤。更精確地講，它們具有可行前綴特性，也就是說，一旦它們發(fā)現(xiàn)輸入的某個(gè)前綴不能夠通過添加符號(hào)而形成這個(gè)語言的串，它們立刻就可以檢測(cè)到語法錯(cuò)誤。下面的情況也說明了為

12、什么要在語法分析過程中重視錯(cuò)誤恢復(fù)。不管產(chǎn)生錯(cuò)誤的原因是什么，很多錯(cuò)誤都以語法錯(cuò)誤的方式出現(xiàn)，并且在不能繼續(xù)進(jìn)行語法分析時(shí)暴露出來。有些語義錯(cuò)誤，比如類型不匹配，也可以被高效地檢測(cè)到；然而，總的來說在編譯時(shí)刻精確地檢測(cè)語義錯(cuò)誤和邏輯錯(cuò)誤是很困難的。語法分析器中的錯(cuò)誤處理程序的目標(biāo)說起來很簡單，但實(shí)現(xiàn)起來卻很有挑戰(zhàn)性：l 清晰精確地報(bào)告出現(xiàn)的錯(cuò)誤。l 足夠快地從各個(gè)錯(cuò)誤中恢復(fù)，并繼續(xù)檢測(cè)后面的錯(cuò)誤。l 盡可能少地增加處理正確程序時(shí)的開銷。幸運(yùn)的是，常見的錯(cuò)誤都很簡單，相對(duì)直接的錯(cuò)誤處理機(jī)制常常就足以達(dá)到目標(biāo)。一個(gè)錯(cuò)誤處理程序應(yīng)該如何報(bào)告出現(xiàn)的錯(cuò)誤？至少，它必須報(bào)告檢測(cè)到該錯(cuò)誤的源程序中的位置，因

13、為實(shí)際的錯(cuò)誤很可能就出現(xiàn)在這個(gè)位置之前幾個(gè)詞法單元的地方。一個(gè)常用的策略是打印出有問題的那一行，然后用一個(gè)指針指向檢測(cè)到錯(cuò)誤的地方。4.1.4 錯(cuò)誤恢復(fù)策略當(dāng)檢測(cè)到一個(gè)錯(cuò)誤時(shí)，語法分析器應(yīng)該如何恢復(fù)？雖然還沒有哪個(gè)策略能夠證明自己是被普遍接受的，有一些方法的適用范圍很廣。最簡單的方法是讓語法分析器在檢測(cè)到第一個(gè)錯(cuò)誤時(shí)給出一個(gè)錯(cuò)誤提示信息，然后退出。如果語法處理器能夠把自己恢復(fù)到某個(gè)狀態(tài)，且有理由預(yù)期從那里開始繼續(xù)處理輸入將提供有意義的診斷信息，那么它通常會(huì)發(fā)現(xiàn)更多的錯(cuò)誤。如果錯(cuò)誤太多，那么最好讓編譯器在超過某個(gè)錯(cuò)誤上界之后停止分析。這樣做要比讓編譯器產(chǎn)生大量惱人的“可疑”錯(cuò)誤信息更好?？只拍Ｊ?/p>

14、的恢復(fù)使用這個(gè)方法時(shí)，語法分析程序一旦發(fā)現(xiàn)錯(cuò)誤就不斷丟棄輸入中的符號(hào)，直到找到同步詞法單元集合中的某個(gè)元素。同步詞法單元通常是界限符，比如分號(hào)或者。它們?cè)谠闯绦蛑械慕巧乔逦o二義的。編譯器作者必須為源語言選擇適當(dāng)?shù)耐皆~法單元?？只拍Ｊ降腻e(cuò)誤糾正方法常常會(huì)跳過相當(dāng)多的輸入，不檢查被跳過部分其它錯(cuò)誤。但是它很簡單，并且能夠保證不會(huì)進(jìn)入無限循環(huán)。我們稍后考慮的某些方法則比較難保證不進(jìn)入無限循環(huán)。短語層次的恢復(fù)當(dāng)發(fā)現(xiàn)一個(gè)錯(cuò)誤時(shí)，語法分析器可以在余下的輸入上進(jìn)行局部性糾正；就是說，它可能將余下輸入的某個(gè)前綴替換為另一個(gè)串，使語法分析器可以繼續(xù)分析。有代表性的局部糾正方法包括將一個(gè)逗號(hào)替換為分號(hào)、刪

15、除一個(gè)多余的分號(hào)、或者插入一個(gè)被遺漏的分號(hào)。如何選擇局部糾正方法是由編譯器設(shè)計(jì)者決定的。當(dāng)然，我們必須小心選擇替換方法，以避免進(jìn)入無限循環(huán)。比如，如果我們總是在當(dāng)前輸入符號(hào)之前插入符號(hào)，就出現(xiàn)了無限循環(huán)。短語層次替換方法已經(jīng)在多個(gè)錯(cuò)誤修復(fù)型編譯器中使用，它可以糾正任何輸入串。它的主要不足之處在于它難以處理實(shí)際錯(cuò)誤發(fā)生在被檢測(cè)到之前的情況。錯(cuò)誤產(chǎn)生式通過預(yù)測(cè)可能會(huì)碰到的常見錯(cuò)誤，我們可以在當(dāng)前語言的文法中加入特殊的產(chǎn)生式。這些產(chǎn)生式能夠產(chǎn)生含有錯(cuò)誤的構(gòu)造?？梢曰谠黾恿隋e(cuò)誤產(chǎn)生式的文法構(gòu)造得到一個(gè)語法分析器。如果分析過程中使用了某個(gè)錯(cuò)誤產(chǎn)生式，語法分析器就檢測(cè)到了一個(gè)預(yù)期的錯(cuò)誤。語法分析器能夠據(jù)

16、此生成適當(dāng)?shù)腻e(cuò)誤診斷信息，指出識(shí)別得到的錯(cuò)誤構(gòu)造。全局糾正在理想情況下，我們希望編譯器在處理一個(gè)錯(cuò)誤輸入串時(shí)通過最少的改動(dòng)將其轉(zhuǎn)化為語法正確的串。有一些算法可以選擇一個(gè)最小的改動(dòng)序列，得到開銷最低的全局性糾正方法。給定一個(gè)不正確的輸入x和文法G，這些算法將找出一個(gè)相關(guān)串y的語法分析樹，使得將x轉(zhuǎn)換為y所需要插入、刪除和改變的詞法單元數(shù)量最少。不幸的是，從時(shí)間和空間的角度看，實(shí)現(xiàn)這些方法一般來說開銷太大，因此這些技術(shù)當(dāng)前僅具有理論價(jià)值。請(qǐng)注意，一個(gè)最接近的正確程序可能并不是程序員想要的那個(gè)程序。不管怎樣，最低開銷糾正的概念仍然提供了一個(gè)可用于評(píng)價(jià)錯(cuò)誤恢復(fù)技術(shù)的標(biāo)尺，并曾被用于為短語層次恢復(fù)尋找最

17、佳替換串。4.2 上下文無關(guān)文法2.2節(jié)中已經(jīng)介紹了文法的概念。在那里，它被用于系統(tǒng)地描述程序設(shè)計(jì)語言構(gòu)造，比如表達(dá)式和語句，的語法。下面的產(chǎn)生式使用語法變量stmt來表示語句，變量expr來表示表達(dá)式。stmt à if (expr) stmt else stmt（4.4）它描述了這種形式的條件語句的結(jié)構(gòu)。其它的產(chǎn)生式則精確地定義了一個(gè)expr是什么，以及一個(gè)stmt還可以是什么。這一節(jié)回顧了上下文無關(guān)文法的定義，并介紹了討論語法分析技術(shù)時(shí)要用到的一些術(shù)語。特別地，推導(dǎo)的概念在討論分析過程中產(chǎn)生式的應(yīng)用順序時(shí)非常有用。4.2.1 上下文無關(guān)文法的正式定義根據(jù)2.2節(jié)，一個(gè)上下文無關(guān)

18、文法（簡稱文法）由終結(jié)符號(hào)，非終結(jié)符號(hào)，一個(gè)開始符號(hào)和一組產(chǎn)生式組成。1. 終結(jié)符號(hào)是組成串的基本符號(hào)。術(shù)語“詞法單元名字”是“終結(jié)符號(hào)”的同義詞。當(dāng)我們討論的顯然是詞法單元的名字時(shí)，我們經(jīng)常使用“詞法單元”這個(gè)詞來指稱終結(jié)符號(hào)。我們假設(shè)終結(jié)符號(hào)是詞法分析器輸出的詞法單元的第一個(gè)分量。在(4.4)中，終結(jié)符號(hào)是關(guān)鍵字if和else以及符號(hào)“(”和“)”。2. 非終結(jié)符號(hào)是表示串的集合的語法變量。在(4.4)中，stmt和expr是非終結(jié)符號(hào)。非終結(jié)符號(hào)表示的串集合被用于定義由文法生成的語言。非終結(jié)符號(hào)給出了語言的層次結(jié)構(gòu)，而這種結(jié)構(gòu)是語法分析和翻譯的關(guān)鍵。3. 在一個(gè)文法中，某個(gè)非終結(jié)符號(hào)被指

19、定為開始符號(hào)。這個(gè)符號(hào)表示的串集合就是這個(gè)文法生成的語言。按照慣例，開始符號(hào)的產(chǎn)生式被第一個(gè)列出。4. 一個(gè)文法的產(chǎn)生式描述了將終結(jié)符號(hào)和非終結(jié)符號(hào)組合成串的方法。每個(gè)產(chǎn)生式由下列元素組成：(a) 一個(gè)被稱為產(chǎn)生式頭或左部的非終結(jié)符號(hào)；這個(gè)產(chǎn)生式定義了這個(gè)頭所代表的串集合的一部分。(b) 符號(hào)à。有時(shí)也使用:=來替代箭頭。(c) 一個(gè)由零個(gè)或多個(gè)終結(jié)符號(hào)與非終結(jié)符號(hào)組成的產(chǎn)生式體或右部。產(chǎn)生式體中的成分描述了產(chǎn)生式頭上的非終結(jié)符號(hào)所對(duì)應(yīng)的串的構(gòu)造方法之一。例子4.5：圖4.2中的文法定義了簡單的算術(shù)表達(dá)式。在這個(gè)文法中，終結(jié)符號(hào)是id+-*/()非終結(jié)符號(hào)是expression，te

20、rm和factor，而expression是開始符號(hào)。圖4.2：簡單算術(shù)表達(dá)式的文法4.2.2符號(hào)表示的慣例為了避免總是不得不聲明“這些是終結(jié)符號(hào)，”“這些是非終結(jié)符號(hào)，”等等，在本書的其余部分將使用下面的文法符號(hào)表示慣例。1、 這些符號(hào)是終結(jié)符號(hào)：(a) 在字母表里排在前面的小寫字母，比如a、b、c。(b) 運(yùn)算符號(hào)，比如+、*等。(c) 標(biāo)點(diǎn)符號(hào)，比如括號(hào)、逗號(hào)等。(d) 數(shù)字0、1、9。(e) 黑體字符串，比如id或if。每個(gè)這樣的字符串表示一個(gè)終結(jié)符號(hào)。2、 這些符號(hào)是非終結(jié)符號(hào)：(a) 在字母表中排在前面的大寫字母，比如A、B、C。(b) 字母S。它出現(xiàn)時(shí)通常表示開始符號(hào)。(c) 小

21、寫、斜體的名字，比如expr或stmt。(d) 當(dāng)討論程序設(shè)計(jì)語言構(gòu)造時(shí)，大寫字母可能被用于表示代表程序構(gòu)造的非終結(jié)符號(hào)。比如，表達(dá)式、項(xiàng)和因子的非終結(jié)符號(hào)通常分別用E、T和F表示。3、 在字母表中排在后面的大寫字母，比如X、Y、Z表示文法符號(hào)；就是說表示非終結(jié)符號(hào)或終結(jié)符號(hào)。4、 在字母表中排在后面的小寫字母，主要是u、v、z，表示（可能為空的）終結(jié)符號(hào)串。5、 小寫的希臘字母，比如、，表示（可能為空的）文法符號(hào)串。因此，一個(gè)普通的產(chǎn)生式可以寫作Aà，其中A是產(chǎn)生式的頭而是產(chǎn)生式的體。6、 具有相同的頭符號(hào)的一組產(chǎn)生式Aà1，Aà2，Aàn可以被寫作A

22、à1|2|n。我們把1，2，n稱作A的不同可選體。7、 除非另外說明，第一個(gè)產(chǎn)生式的頭就是開始符號(hào)。例子4.6：按照這些慣例，例子4.5的文法可以簡明地寫作：E à E + T | E T | TT à T * F | T / F | FF à ( E ) | id上面的符號(hào)表示慣例告訴我們E、T和F是非終結(jié)符號(hào)，其中E是開始符號(hào)。其余的符號(hào)是終結(jié)符號(hào)。4.2.3 推導(dǎo)將產(chǎn)生式看作重寫規(guī)則，就可以從推導(dǎo)的角度精確地描述一棵語法分析樹的構(gòu)造方法。從開始符號(hào)出發(fā)，每個(gè)重寫步驟把一個(gè)非終結(jié)符號(hào)替換為它的某個(gè)產(chǎn)生式的體。這個(gè)推導(dǎo)的視角對(duì)應(yīng)于自頂向下構(gòu)造一棵語法分

23、析樹的過程，但是推導(dǎo)概念所給出的精確性在討論自底向上的語法分析過程時(shí)尤其有用。如我們將看到的，自底向上語法分析和一種被稱為“最右”推導(dǎo)的推導(dǎo)種類相關(guān)。在這種推導(dǎo)過程中，每一步重寫的都是最右邊的非終結(jié)符號(hào)。比如，考慮下面的只有一個(gè)非終結(jié)符號(hào)E的文法。它在文法(4.3)中增加了一個(gè)產(chǎn)生式Eà-E：E à E + E | E * E | - E | ( E ) | id(4.7)產(chǎn)生式Eà-E表明如果E表示一個(gè)表達(dá)式，那么-E必然也表示一個(gè)表達(dá)式。將一個(gè)E替換為-E的過程寫作E -E讀作“E推導(dǎo)出-E”。產(chǎn)生式E à ( E )可以將任何文法符號(hào)串中出現(xiàn)的E的

24、任何實(shí)例替換為( E )。比如E * E ( E ) * E或E * E E * ( E )。我們可以按照任意順序?qū)蝹€(gè)E不斷地應(yīng)用各個(gè)產(chǎn)生式，得到一個(gè)替換的序列。比如，E - E - ( E ) - ( id )我們將這個(gè)替換序列稱為從E到- ( id )的推導(dǎo)。這個(gè)推導(dǎo)證明了串 - ( id )是表達(dá)式的一個(gè)特定實(shí)例。要給出推導(dǎo)的一般性定義，考慮一個(gè)文法符號(hào)序列中間的非終結(jié)符號(hào)A，比如A，其中和是任意的文法符號(hào)串。假設(shè)Aà是一個(gè)產(chǎn)生式。那么我們寫作A。符號(hào)表示“通過一步推導(dǎo)出”。當(dāng)一個(gè)推導(dǎo)序列12n將1替換為n，我們說1推導(dǎo)出n。我們經(jīng)常要說“經(jīng)過零步或多步推導(dǎo)出”。我們可以使用

25、符號(hào)來表示這種關(guān)系。因此，1、 對(duì)于任何串，并且2、 如果且，那么。類似地，表示“經(jīng)過一步或多步推導(dǎo)出”。如果S，其中S是文法G的開始符號(hào)，我們說是G的一個(gè)句型。請(qǐng)注意一個(gè)句型可能既包含終結(jié)符號(hào)又包含非終結(jié)符號(hào)，也可能是空串。文法G的一個(gè)句子是不包含非終結(jié)符號(hào)的句型。一個(gè)文法生成的語言是它的所有句子的集合。因此，一個(gè)終結(jié)符號(hào)串w在G生成的語言L(G)中，當(dāng)且僅當(dāng)w是G的一個(gè)句子（或者說Sw）。可以由文法生成的語言被稱為上下文無關(guān)語言。如果兩個(gè)文法生成相同語言，這兩個(gè)文法就被稱為是等價(jià)的。串-(id+id)是文法(4.7)的一個(gè)句子，因?yàn)榇嬖谝粋€(gè)推導(dǎo)過程E - E - ( E ) - ( E +

26、 E ) - ( id + E ) - ( id + id )(4.8)串E、-E、-(E)、-(id+id)都是這個(gè)文法的句型。我們用E- ( id + id )來指明- ( id + id )可以從E推導(dǎo)得到。在推導(dǎo)的每一個(gè)步驟上都需要做兩個(gè)選擇。我們需要選擇替換哪個(gè)非終結(jié)符號(hào)，并且在做出這個(gè)決定之后，我們還必須選擇一個(gè)以此非終結(jié)符號(hào)作為頭符號(hào)的產(chǎn)生式。比如，下面給出的- ( id + id )的另一種推導(dǎo)和推導(dǎo)(4.8)在最后兩步中不同：E - E - ( E ) - ( E + E ) - ( E + id ) - ( id + id )(4.9)在這兩個(gè)推導(dǎo)中，每個(gè)非終結(jié)符號(hào)都被替換

27、為同一個(gè)產(chǎn)生式體，但替換的順序有所不同。為了理解語法分析器是如何工作的，我們將考慮在每個(gè)推導(dǎo)步驟中按照如下方式選擇被替換非終結(jié)符號(hào)的兩種推導(dǎo)過程：1、 在最左推導(dǎo)中總是選擇每個(gè)句型的最左非終結(jié)符號(hào)。如果是一個(gè)推導(dǎo)步驟，且被替換的是中的最左非終結(jié)符號(hào)，我們寫作。2、 在最右推導(dǎo)中總是選擇最右邊的非終結(jié)符號(hào)；此時(shí)我們寫作。推導(dǎo)(4.8)的最左推導(dǎo)，因此它可以被寫成E - E - ( E ) - ( E + E ) - ( id + E ) - ( id + id )請(qǐng)注意推導(dǎo)(4.9)是一個(gè)最右推導(dǎo)。使用我們的符號(hào)表示慣例，每個(gè)最左推導(dǎo)都可以寫成wAw，其中w只包含終結(jié)符號(hào)，Aà是被應(yīng)用

28、的產(chǎn)生式，而是一個(gè)文法符號(hào)串。為了強(qiáng)調(diào)經(jīng)過一個(gè)最左推導(dǎo)過程得到，我們寫作。如果S ，那么我們說是當(dāng)前文法的左句型。對(duì)于最右推導(dǎo)也有對(duì)應(yīng)的定義。最右推導(dǎo)有時(shí)也被稱為規(guī)范推導(dǎo)。4.2.4 語法分析樹和推導(dǎo)一棵語法分析樹是一個(gè)推導(dǎo)的圖形表示形式。它過濾掉了應(yīng)用產(chǎn)生式替換非終結(jié)符號(hào)的順序。一棵語法分析樹的每個(gè)內(nèi)部結(jié)點(diǎn)表示了一個(gè)產(chǎn)生式的一次應(yīng)用。該內(nèi)部結(jié)點(diǎn)的標(biāo)號(hào)是此產(chǎn)生式頭中的非終結(jié)符號(hào)A；這個(gè)結(jié)點(diǎn)的子結(jié)點(diǎn)的標(biāo)號(hào)，從左到右組成了在推導(dǎo)過程中替換這個(gè)A的產(chǎn)生式體。比如，圖4.3中- ( id + id )的語法分析樹是根據(jù)推導(dǎo)(4.8)得到的。它也可以根據(jù)推導(dǎo)(4.9)得到。一棵語法分析樹的葉子的標(biāo)號(hào)既可

29、以是非終結(jié)符號(hào)，也可以是終結(jié)符號(hào)。從左到右排列這些符號(hào)就可以得到一個(gè)句型，被稱為這棵樹的結(jié)果或邊緣。為了了解推導(dǎo)和語法分析樹之間的關(guān)系，考慮任意的推導(dǎo)12n，其中1是單個(gè)非終結(jié)符號(hào)A。對(duì)于推導(dǎo)中的每個(gè)句型i，我們可以構(gòu)造出一個(gè)結(jié)果為i的語法分析樹。這個(gè)構(gòu)造過程是對(duì)i的一次歸納?；A(chǔ)：1=A的語法分析樹就是標(biāo)號(hào)為A的單個(gè)結(jié)點(diǎn)。圖4.3：- ( id + id )的語法分析樹歸納步驟：假設(shè)我們已經(jīng)構(gòu)造出了一棵結(jié)果為i-1=X1X2Xk的語法分析樹（請(qǐng)注意按照我們的符號(hào)表示慣例，每個(gè)文法符號(hào)Xi可以是非終結(jié)符號(hào)，也可以是終結(jié)符號(hào)）。假設(shè)i是將i-1中的某個(gè)非終結(jié)符號(hào)Xj替換為=Y1Y2Ym而得到的句

30、型。就是說，這個(gè)推導(dǎo)的第i步對(duì)i-1應(yīng)用規(guī)則Xjà，推導(dǎo)出i=X1X2Xj-1Xj+1Xk。為了模擬這一推導(dǎo)步驟，我們?cè)诋?dāng)前的語法分析樹中找出左起第j個(gè)非葉子結(jié)點(diǎn)。這個(gè)結(jié)點(diǎn)的標(biāo)號(hào)為Xj。向這個(gè)葉子結(jié)點(diǎn)添加m個(gè)子結(jié)點(diǎn)，從左邊開始給這些子結(jié)點(diǎn)加上標(biāo)號(hào)Y1、Y2、Ym。作為一種特殊情況，如果m=0，那么=，我們給第j個(gè)葉結(jié)點(diǎn)加上一個(gè)標(biāo)號(hào)為的子結(jié)點(diǎn)。例子4.10：根據(jù)推導(dǎo)(4.8)構(gòu)造得到的語法分析樹的序列顯示在圖4.4中。推導(dǎo)的第一步是E à - E。為了模擬這一步，我們將標(biāo)號(hào)分別為-和E的兩個(gè)子結(jié)點(diǎn)加到第一棵樹的根結(jié)點(diǎn)E上，得到第二棵語法分析樹。這個(gè)推導(dǎo)的第二步是- E 

31、24; - ( E )。相應(yīng)地，將標(biāo)號(hào)分別為(、E、)的三個(gè)子結(jié)點(diǎn)加到第二棵樹中標(biāo)號(hào)為E的葉子結(jié)點(diǎn)上，得到了結(jié)果為- ( E )的第三棵樹。按照這個(gè)方法繼續(xù)，我們就得到了完整的語法分析樹，即第六棵樹。因?yàn)檎Z法分析樹忽略了替換句型中的符號(hào)的不同順序，在推導(dǎo)和語法分析樹之間具有多對(duì)一的關(guān)系。比如，推導(dǎo)(4.8)和(4.9)都和圖4.4中的最后一棵語法分析樹關(guān)聯(lián)。因?yàn)樵谡Z法分析樹和最左推導(dǎo)/最右推導(dǎo)之間存在一對(duì)一的關(guān)系，在接下來的內(nèi)容中，我們將頻繁地通過構(gòu)造最左推導(dǎo)或最右推導(dǎo)來進(jìn)行語法分析。最左或最右推導(dǎo)都選擇一個(gè)特定的順序來替換句型中的符號(hào)，因此它們也過濾掉了順序上的不同。因此不難說明每一棵語法分

32、析樹都和唯一的最左推導(dǎo)及唯一的最右推導(dǎo)相關(guān)聯(lián)。圖4.4：推導(dǎo)(4.8)對(duì)應(yīng)的語法分析樹的序列4.2.5 二義性根據(jù)2.2.4節(jié)，如果一個(gè)文法可以為某個(gè)句子生成多棵語法分析樹，那么它就是二義性的。換句話說，一個(gè)二義性文法就是對(duì)同一個(gè)句子有多個(gè)最左推導(dǎo)或多個(gè)最右推導(dǎo)的文法。例子4.11：算術(shù)表達(dá)式文法(4.3)允許句子id + id * id具有兩個(gè)最左推導(dǎo)：E E + EE E * E id + E E + E * Eid + E * E id + E * Eid + id * E id + id * Eid + id * id id + id * id相應(yīng)的語法分析樹顯示在圖4.5中。請(qǐng)注意圖

33、4.5(a)的語法分析樹反映了通常的+和*之間的優(yōu)先級(jí)關(guān)系，而圖4.5(b)沒有反映出這一點(diǎn)。就是說，按照慣例應(yīng)該將運(yùn)算符*當(dāng)作優(yōu)先級(jí)高于+的運(yùn)算符來處理，相應(yīng)地，我們通常將象a + b * c這樣的表達(dá)式按照a + ( b * c )，而不是( a + b ) * c，進(jìn)行求值。大部分語法分析器都期望文法是無二義性的，因?yàn)槿绻皇沁@樣，我們就不能為一個(gè)句子唯一地選定語法分析樹。在一些其它情況下，使用經(jīng)過精心選擇的二義性文法也可以帶來方便。但同時(shí)需要使用去二義性規(guī)則來“拋棄”不想要的語法分析樹，只為每個(gè)語句留下一棵語法分析樹。圖5.5：id + id * id的兩棵語法分析樹4.2.6驗(yàn)證文法

34、生成的語言能夠推斷出一個(gè)給定的產(chǎn)生式集合生成了某個(gè)特定的語言是很有用的，雖然編譯器的設(shè)計(jì)者很少會(huì)對(duì)整個(gè)程序設(shè)計(jì)語言文法做這樣的事情。當(dāng)研究一個(gè)棘手的構(gòu)造時(shí)，我們可以寫出該構(gòu)造的一個(gè)簡明、抽象的文法，并研究該文法生成的語言。我們將為下面的條件語句構(gòu)造出一個(gè)這樣的文法。證明一個(gè)文法G生成一個(gè)語言L的過程可以分成兩個(gè)部分：證明G生成的每個(gè)串都在L中，并且反過來證明L中的每個(gè)串都確實(shí)能由G生成。例子4.12：考慮下面的文法：Sà( S ) S | (4.13)初看可能不是很明顯，但這個(gè)簡單的文法確實(shí)生成了所有具有對(duì)稱括號(hào)對(duì)的串，并且只生成這樣的串。為了說明為什么，我們將首先說明從S推導(dǎo)得到的

35、每個(gè)句子都是括號(hào)對(duì)稱的，然后說明每個(gè)括號(hào)對(duì)稱的串都可以從S推導(dǎo)得到。為了證明從S推導(dǎo)出的每個(gè)句子都是括號(hào)對(duì)稱的，我們對(duì)推導(dǎo)步數(shù)n進(jìn)行歸納。基礎(chǔ)：基礎(chǔ)是n=1。唯一可以從S經(jīng)過一步推導(dǎo)得到的終結(jié)符號(hào)串是空串，它當(dāng)然是括號(hào)對(duì)稱的。歸納步驟：現(xiàn)在假設(shè)所有步數(shù)少于n的推導(dǎo)都得到括號(hào)對(duì)稱的句子，并考慮一個(gè)恰巧為n步的最左推導(dǎo)。這樣的推導(dǎo)必然具有如下形式：S(S)S(x)S(x)y從S到x和y的推導(dǎo)過程都少于n步，因此根據(jù)歸納假設(shè)x和y都是括號(hào)對(duì)稱的。因此，串( x ) y必然是括號(hào)對(duì)稱的。就是說，它具有相同數(shù)量的左括號(hào)和右括號(hào)，并且它的每個(gè)前綴中的左括號(hào)不少于右括號(hào)?，F(xiàn)在已經(jīng)證明了可以從S推導(dǎo)出的任何串

36、都是括號(hào)對(duì)稱的，接下來我們必須證明每個(gè)括號(hào)對(duì)稱的串都可以從S推導(dǎo)得到。為了證明這一點(diǎn)，我們對(duì)串的長度進(jìn)行歸納?；A(chǔ)：如果串的長度是0，它必然是。它可以從S推導(dǎo)得到。歸納步驟：首先請(qǐng)注意每個(gè)括號(hào)對(duì)稱的串的長度是偶數(shù)。假設(shè)每個(gè)長度小于2n的括號(hào)對(duì)稱的串都能夠從S推導(dǎo)得到，并考慮一個(gè)長度為2n（n1）的括號(hào)對(duì)稱的串w。首先w一定以左括號(hào)開頭。令(x)是w的最短的、左括號(hào)個(gè)數(shù)和右括號(hào)個(gè)數(shù)相同的非空前綴。那么w可以被寫成w=(x)y的形式，其中x和y都是括號(hào)對(duì)稱的。因?yàn)閤和y的長度都小于2n，根據(jù)歸納假設(shè)，它們可以從S推導(dǎo)得到。因此，我們可以找到一個(gè)如下形式的推導(dǎo)：S (S)S (x)S(x)y證明了w

37、=(x)y也可以從S推導(dǎo)得到。4.2.7上下文無關(guān)文法和正則表達(dá)式在結(jié)束這個(gè)關(guān)于文法及其性質(zhì)的討論之前，我們證明文法是一個(gè)比正則表達(dá)式更具表達(dá)能力的表示方法。每個(gè)可以使用正則表達(dá)式描述的構(gòu)造都可以使用文法來描述，但是反過來不成立。換個(gè)說法，每個(gè)正則語言都是一個(gè)上下文無關(guān)語言，但是反過來不成立。比如，正則表達(dá)式(a|b)*abb和文法A0 à aA0 | bA0 | aA1A1 à bA2A2 à bA3A3 à 描述了同一個(gè)語言，即以abb結(jié)尾的、由a和b組成的串的集合。我們可以機(jī)械地構(gòu)造出和一個(gè)不確定有窮自動(dòng)機(jī)（NFA）識(shí)別同樣語言的文法。上面的文法是

38、使用下面的構(gòu)造方法，根據(jù)圖3.24中的NFA構(gòu)造得到的。1、 對(duì)于NFA的每個(gè)狀態(tài)i，創(chuàng)建一個(gè)非終結(jié)符號(hào)Ai。2、 如果狀態(tài)i有一個(gè)在輸入a上到達(dá)狀態(tài)j的轉(zhuǎn)換，加入產(chǎn)生式AiàaAj。如果狀態(tài)i在輸入上到達(dá)狀態(tài)j，加入產(chǎn)生式AiàAj。3、 如果i是一個(gè)接受狀態(tài)，加入產(chǎn)生式Aià。4、 如果i是自動(dòng)機(jī)的開始狀態(tài)，令A(yù)i為所得文法的開始符號(hào)。另一方面，語言L=anbn | n1，即由多個(gè)a和同樣多個(gè)b組成的串的集合，是一個(gè)可以用文法描述但不能用正則表達(dá)式描述的語言的原型例子。下面用反證法來說明為什么。假設(shè)L是用某個(gè)正則表達(dá)式描述的語言。我們可以構(gòu)造一個(gè)具有有窮多個(gè)狀

39、態(tài)，比如說k個(gè)狀態(tài)，的DFA D來接受L。因?yàn)镈只有k個(gè)狀態(tài)，對(duì)于一個(gè)以多于k個(gè)a開頭的輸入，D一定會(huì)進(jìn)入某個(gè)狀態(tài)兩次，假設(shè)這個(gè)狀態(tài)是si，如圖4.6所示。假設(shè)從si返回到其自身的路徑的標(biāo)號(hào)序列是aj-i。因?yàn)閍ibi在這個(gè)語言中，因此必然存在一條標(biāo)號(hào)為bi、從si到某個(gè)接受狀態(tài)f的路徑。那么一定還存在一條從開始狀態(tài)s0出發(fā)、經(jīng)過si、最后到達(dá)f的路徑，它的標(biāo)號(hào)序列為ajbi，如圖4.6所示。因此D同時(shí)接受ajbi，但這個(gè)串不在語言L中，這和L是D所接受的語言這個(gè)假設(shè)矛盾。path labeled ai標(biāo)號(hào)為ai的路徑path labeled aj-i標(biāo)號(hào)為aj-i的路徑path labele

40、d bi標(biāo)號(hào)為bi的路徑圖4.6：接受aibi和ajbi的DFA D我們通俗地說“有窮自動(dòng)機(jī)不能計(jì)數(shù)”，表示一個(gè)有窮自動(dòng)機(jī)不能接受一個(gè)象anbn|n1這樣的語言，因?yàn)樗荒軌蛴涗浵滤吹降谝粋€(gè)b之前讀入的a的個(gè)數(shù)。類似地，“一個(gè)文法可以對(duì)兩個(gè)個(gè)體進(jìn)行計(jì)數(shù)，但是無法對(duì)三個(gè)個(gè)體計(jì)數(shù)”，如我們?cè)?.3.5節(jié)中考慮非上下文無關(guān)的語言構(gòu)造時(shí)將看到的。4.2.8 4.2節(jié)的練習(xí)練習(xí)4.2.1：考慮上下文無關(guān)文法：S à S S + | S S * | a以及串a(chǎn)a+a*。a） 給出這個(gè)串的一個(gè)最左推導(dǎo)。b） 給出這個(gè)串的一個(gè)最右推導(dǎo)。c） 給出這個(gè)串的一棵語法分析樹。！d）這個(gè)文法是否二義性的？

41、證明你的回答。！e）描述這個(gè)文法生成的語言。練習(xí)4.2.2：對(duì)下列的每一對(duì)文法和串重復(fù)練習(xí)4.2.1。a） S à 0 S 1 | 0 1和串000111。b） S à + S S | * S S | a和串+*aaa。！c）SàS ( S ) S | 和串()()。！d）SàS + S | S S | ( S ) | S* | a和串(a+a)*a。！e）Sà ( L ) | a 以及 LàL，S | S 和串(a,a),a,(a)。！f）Sà a S b S | b S a S | 和串a(chǎn)abbab。！g）下面的布爾表達(dá)

42、式的文法：bexpr à bexpr or bterm | btermbterm à bterm and bfactor | bfactorbfactor à not bfactor | ( bexpr ) | true | false練習(xí)4.2.3：為下面的語言設(shè)計(jì)文法：a） 所有由0和1組成的、并且每個(gè)0之后都至少跟著一個(gè)1的串的集合。！b）所有由0和1組成的回文的集合；也就是從前面和從后面讀都相同的串的集合。！c）所有由0和1組成的、具有相同多個(gè)0和1的串的集合。！d）所有由0和1組成的、0的個(gè)數(shù)和1的個(gè)數(shù)不同的串的集合。！e）所有由0和1組成的、且其中不包

43、含子串011的串的集合。！f）所有由0和1組成的、形如xy的串的集合，其中xy且x和y等長。!練習(xí)4.2.4：有一個(gè)常用的擴(kuò)展的文法表示方法。在這個(gè)表示方法中，產(chǎn)生式體中的方括號(hào)和花括號(hào)是元符號(hào)（就像à或 | ），且具有如下含義：i） 一個(gè)或多個(gè)文法符號(hào)兩邊的方括號(hào)表示這些構(gòu)造是可選的。因此，產(chǎn)生式AàXYZ和兩個(gè)產(chǎn)生式AàXYZ和AàXZ具有相同的效果。ii） 一個(gè)或多個(gè)文法符號(hào)兩邊的花括號(hào)表示這些符號(hào)可以重復(fù)任意多次，包括零次。因此AàXYZ和如下的無窮的產(chǎn)生式序列具有相同的效果：AàX，AàXYZ，AàXYZ

44、YZ，等等。證明這兩個(gè)擴(kuò)展并沒有增加文法的表達(dá)能力；就是說，由帶有這些擴(kuò)展表示的文法生成的任何語言都可以由一個(gè)不帶擴(kuò)展表示法的文法生成。練習(xí)4.2.5：使用練習(xí)4.2.4中描述的括號(hào)表示法來簡化如下的關(guān)于語句塊和條件語句的文法。stmt à if expr then stmt else stmt|if stmt then stmt|begin stmtList endstmtList àstmt; stmtList | stmt！練習(xí)4.2.6：擴(kuò)展練習(xí)4.2.4中的思想，使得產(chǎn)生式體中可以出現(xiàn)文法符號(hào)的任意正則表達(dá)式。證明這個(gè)擴(kuò)展并沒有使得文法可以定義任何新的語言。！練習(xí)

45、4.2.7：如果不存在形如SwXy wxy的推導(dǎo)，那么文法符號(hào)X（終結(jié)符號(hào)或非終結(jié)符號(hào)）就被稱為無用的。就是說，X不可能出現(xiàn)在任何句子的推導(dǎo)過程中。a） 給出一個(gè)算法，從一個(gè)文法中消除所有包含無用符號(hào)的產(chǎn)生式。b） 將你的算法應(yīng)用于文法：Sà 0 | AA à ABB à 1圖4.7：多屬性聲明的文法練習(xí)4.2.8：圖4.7中的文法可生成單個(gè)數(shù)值標(biāo)識(shí)符的聲明；這些聲明包含了四種不同的、相互獨(dú)立的數(shù)字性質(zhì)。a） 擴(kuò)展圖4.7中的文法，使得它可以允許n種選項(xiàng)Ai，其中n是一個(gè)固定的數(shù)，i=1，2，n。選項(xiàng)Ai的取值可以是ai或bi。你的文法只能使用O(n)個(gè)文法符號(hào)，

46、并且產(chǎn)生式的總長度也必須是O(n)的。！b）圖4.7中的文法和它在（a）中的擴(kuò)展允許互相矛盾和/或冗余的聲明，比如：declare foo real fixed real floating我們可以要求這個(gè)語言的語法禁止這種聲明；就是說，由這個(gè)文法生成的每個(gè)聲明中，n種選項(xiàng)中的每一項(xiàng)都有且只有一個(gè)取值。如果我們這樣做，那么對(duì)于任意給定的n值，合法聲明的個(gè)數(shù)是有窮的。因此和任何有窮語言一樣，全部合法聲明組成的語言有一個(gè)文法（同時(shí)也有一個(gè)正則表達(dá)式）。最顯而易見的文法是這樣的：文法的開始符號(hào)對(duì)每個(gè)合法聲明都有一個(gè)產(chǎn)生式，這樣共有n!個(gè)產(chǎn)生式。該文法的產(chǎn)生式的總長度是O(n×n!)。你必須做

47、得更好：給出一個(gè)產(chǎn)生式總長度為O(n2n)的文法。！c）說明對(duì)于任何滿足(b)部分中的要求的文法，其產(chǎn)生式的總長度至少是2 n。d）我們可以通過程序設(shè)計(jì)語言的語法來保證聲明中的選項(xiàng)無冗余性、無矛盾。對(duì)于這個(gè)方法的可行性，本題（c）部分的結(jié)論說明了什么問題？4.3 寫文法文法能夠描述大部分程序設(shè)計(jì)語言的語法，但不是全部。比如，在程序中標(biāo)識(shí)符必須先聲明后使用，但是這個(gè)要求不能通過一個(gè)上下文無關(guān)文法來描述。因此，一個(gè)語法分析器所接受的詞法單元序列構(gòu)成了程序設(shè)計(jì)語言的超集；編譯器的后續(xù)步驟必須對(duì)語法分析器的輸出進(jìn)行分析，以保證源程序遵守那些語法分析器沒有檢查的規(guī)則。本節(jié)首先討論了如何在詞法分析器和語法

48、分析器之間分配工作。然后我們考慮了幾個(gè)可以被用來使文法更適于語法分析的轉(zhuǎn)換方法。其中的一個(gè)技術(shù)可以消除文法中的二義性，而其它的技術(shù)左遞歸消除和提取左公因子可用于改寫文法，使得這些文法適合于自頂向下的語法分析技術(shù)。我們?cè)诒竟?jié)的結(jié)尾部分考慮了一些不能使用任何文法描述的程序設(shè)計(jì)語言構(gòu)造。4.3.1 詞法分析和語法分析如我們?cè)?.2.7節(jié)看到的，任何能夠使用正則表達(dá)式描述的東西都可以使用文法描述。因此我們有理由問：“為什么使用正則表達(dá)式來定義一個(gè)語言的詞法構(gòu)造？”，理由有多個(gè)。1、 將一個(gè)語言的語法結(jié)構(gòu)分為詞法和非詞法兩部分，可以很方便地將編譯器前端模塊化，將前端分解為兩個(gè)大小適中的組件。2、 一個(gè)語

49、言的詞法規(guī)則通常相當(dāng)簡單，我們不需要使用一個(gè)象文法這樣的、強(qiáng)大的表示方法來描述這些規(guī)則。3、 和文法相比，正則表達(dá)式通常提供了一個(gè)更加簡明且易于理解的表示詞法單元的方法。4、 根據(jù)正則表達(dá)式自動(dòng)構(gòu)造得到的詞法分析器的效率要高于根據(jù)任意文法構(gòu)造得到的分析器。并不存在一個(gè)嚴(yán)格的指導(dǎo)方針來規(guī)定哪些東西應(yīng)該放到（和語法規(guī)則相對(duì)的）詞法規(guī)則中。正則表達(dá)式最適于描述諸如標(biāo)識(shí)符、常量、關(guān)鍵字、空白這樣的語言構(gòu)造的結(jié)構(gòu)。另一方面，文法最適于描述嵌套結(jié)構(gòu)，比如對(duì)稱的括號(hào)對(duì)，匹配的begin-end，相互對(duì)應(yīng)的if-then-else等等。這些嵌套結(jié)構(gòu)不能使用正則表達(dá)式描述。4.3.2 消除二義性有時(shí)一個(gè)二義性文

50、法可以被改寫為無二義性的文法。例如，我們將消除下面的“懸掛-else”文法中的二義性：stmtàif expr then stmt |if expr then stmt else stmt(4.14) |other這里“other”表示任何其它語句。根據(jù)這個(gè)文法，下面的復(fù)合條件語句if E1 then S1 else if E2 then S2 else S3的語法分析樹如圖4.8所示 E和S的下標(biāo)僅用于區(qū)分同一個(gè)非終結(jié)符號(hào)的不同出現(xiàn)，并不表示不同的非終結(jié)符號(hào)。文法(4.14)是二義性的，因?yàn)榇甶f E1 then if E2 then S1 else S2(4.15)具有圖4.9所

51、示的兩棵語法分析樹。圖4.8：一個(gè)條件語句的語法分析樹圖4.9：一個(gè)二義性句子的兩棵語法分析樹在所有包含這種形式的條件語句的程序設(shè)計(jì)語言中，被選擇的總是第一棵語法分析樹。通用的規(guī)則是“每個(gè)else和最近的尚未匹配的then匹配。” 我們應(yīng)該注意到C和它的派生語言也是這一類語言。雖然C系列的語言中沒有使用關(guān)鍵字then，then的角色是由if之后、條件表達(dá)式的括號(hào)對(duì)來承擔(dān)的。 從理論上講，這個(gè)去二義性規(guī)則可以用一個(gè)文法直接表示，但是在實(shí)踐中很少把該規(guī)則用產(chǎn)生式來表示。例子4.16：我們可以將懸空-else文法(4.14)改寫成如下的無二義性文法?；舅枷胧窃谝粋€(gè)then和一個(gè)else之間出現(xiàn)的語

52、句必須是“已匹配的”；就是說，中間的語句不能以一個(gè)尚未匹配的，或者說開放的，then結(jié)尾。一個(gè)已匹配的語句要么是一個(gè)不包含開放語句的if-then-else語句，要么是一個(gè)非條件語句。因此，我們可以使用圖4.10中的文法。這個(gè)文法和懸空-else文法(4.14)生成同樣的串集合，但是它只允許對(duì)串(4.15)進(jìn)行一種語法分析；即將每個(gè)else和前面最近的尚未匹配的then匹配。圖4.10：if-then-else語句的無二義性文法4.3.3左遞歸的消除如果一個(gè)文法中有一個(gè)非終結(jié)符號(hào)A使得對(duì)某個(gè)串存在一個(gè)推導(dǎo)AA，那么這個(gè)文法就是左遞歸的。自頂向下語法分析方法不能處理左遞歸的文法，因此需要一個(gè)轉(zhuǎn)換

53、方法來消除左遞歸。在2.4.5節(jié)中，我們討論了立即左遞歸，即存在一個(gè)形如AàA的產(chǎn)生式的情況。這里我們研究一般性的情況。在2.4.5節(jié)中，我們顯示了如何把左遞歸的產(chǎn)生式對(duì)AàA | 替換為非左遞歸的產(chǎn)生式：A àAAàA | 這樣的替換不會(huì)改變可從A推導(dǎo)得到的串的集合。這個(gè)規(guī)則本身已經(jīng)足以處理很多文法。例子4.17：這里重復(fù)一下非左遞歸的表達(dá)式文法(4.2)：EàTEEà+ T E | TàF TTà* F T | Fà( E ) | id它是通過消除表達(dá)式文法(4.1)中的立即左遞歸而得到的。左遞歸的產(chǎn)

54、生式對(duì)EàE+T | T被替換為E à T E和E à + T E | 。類似地，T和T的新產(chǎn)生式也是通過消除立即左遞歸而得到的。立即左遞歸可以使用下面的技術(shù)消除，該技術(shù)可以處理任意數(shù)量的A-產(chǎn)生式。首先將A的全部產(chǎn)生式分組如下：AàA1 | A2 | | Am | 1 | 2 | | n其中i都不以A開頭。然后，將這些A-產(chǎn)生式替換為Aà1A | 2A | | nAAà1A | 2A | | mA | 非終結(jié)符號(hào)A生成的串和替換之前生成的一樣，但不再是左遞歸的。這個(gè)過程消除了所有來自A和A的產(chǎn)生式的左遞歸（前提是i都不是），但是它沒

55、有消除那些因?yàn)閮刹交蚨嗖酵茖?dǎo)而產(chǎn)生的左遞歸。比如，考慮文法SàA a | bAàA c | S d | (4.18)因?yàn)镾 Aa Sda，非終結(jié)符號(hào)S是左遞歸的，但它不是立即左遞歸的。下面的算法4.19系統(tǒng)地消除了文法中的左遞歸。如果文法中不存在環(huán)（即形如AA的推導(dǎo)）或-產(chǎn)生式（即形如Aà的產(chǎn)生式），它保證能夠消除左遞歸。環(huán)和-產(chǎn)生式都可以從文法中系統(tǒng)地消除（見練習(xí)4.4.6和4.4.7）。算法4.19：消除左遞歸。輸入：沒有環(huán)或-產(chǎn)生式的文法G。輸出：一個(gè)等價(jià)的無左遞歸文法。方法：對(duì)G應(yīng)用圖4.11中的算法。請(qǐng)注意得到的非左遞歸文法可能具有-產(chǎn)生式。arrang

56、e the nonterminals in some order A1,A2,An按照某個(gè)順序?qū)⒎墙K結(jié)符號(hào)排序?yàn)锳1,A2,Aneach i from 1 to n從1到n的每個(gè)ieach j from 1 to i-1從1到i-1的每個(gè)jreplace each production of the form AiàAj by the productions Aià1 |2 |k ，where Ajà1 |2 |k are all current Aj-productions將每個(gè)形如AiàAj的產(chǎn)生式替換為產(chǎn)生式組Aià1 |2 |k，其中Ajà1 |2 |k是所有的Aj-產(chǎn)生式eliminate the immediate left recursion among the Ai-productions消除Ai-產(chǎn)生式之間的立即左遞歸圖4.11：消除文法中的左遞歸的算法圖4.11中的過程的工作原理如下。在i=1的第一次迭代中，第(2)到第(7)行的外層循環(huán)消除了A1-產(chǎn)生式之間的所有立即左遞歸。因此余下的所有形如A1àAl的產(chǎn)生式都一定滿足l>1。在外層循環(huán)的第i-1次迭代執(zhí)行之后