《ANTLR 4權威指南 》一導讀

antlr是一款強大的文法分析器生成工具，可用于讀取、處理、執行和翻譯結構化的文本或二進制檔案。它被廣泛應用于學術領域和工業生産實踐，是衆多語言、工具和架構的基石。twitter搜尋使用antlr進行文法分析，每天處理超過20億次查詢；hadoop生态系統中的hive、pig、資料倉庫和分析系統所使用的語言都用到了antlr；lex machina将antlr用于分析法律文本；oracle公司在sql開發者ide和遷移工具中使用了antlr；netbeans公司的ide使用antlr來解析c++；hibernate對象-關系映射架構（orm）使用antlr來處理hql語言。

除了這些鼎鼎大名的項目之外，還可以利用antlr建構各種各樣的實用工具，如配置檔案讀取器、遺留代碼轉換器、維基文本渲染器，以及json解析器。我編寫了一些工具，用于建立資料庫的對象-關系映射、描述三維可視化以及在java源代碼中插入性能監控代碼。我甚至為一次演講編寫了一個簡單的dna模式比對程式。

一門語言的正式描述稱為文法（grammar），antlr能夠為該語言生成一個文法分析器，并自動建立文法分析樹——一種描述文法與輸入文本比對關系的資料結構。antlr也能夠自動生成樹的周遊器，這樣你就可以通路樹中的節點，執行自定義的業務邏輯代碼。

本書既是antlr 4的參考手冊，也是解決語言識别問題的指南。你會學到如下知識：

識别語言樣例和參考手冊中的文法模式，進而編寫自定義的文法。

循序漸進地為從簡單的json到複雜的r語言編寫文法。同時還能學會解決xml和python中棘手的識别問題。

基于文法，通過周遊自動生成的文法分析樹，實作自己的語言類應用程式。

在特定的應用領域中，自定義識别過程的錯誤處理機制和錯誤報告機制。

通過在文法中嵌入java動作（action），對文法分析過程進行完全的掌控。

本書并非教科書，所有的讨論都是基于執行個體的，旨在令你鞏固所學的知識，并提供語言類應用程式的基本範例。

本書的讀者對象

本書尤其适用于對資料讀取器、語言解釋器和翻譯器感興趣的開發者。雖然本書主要利用antlr來完成這些工作，你仍然可以學到很多有關詞法分析器和文法分析器的知識。初學者和專家都需要本書來高效地使用antlr 4。如果希望學習第三部分中的進階特性，你需要先了解之前章節中的antlr基礎知識。此外，讀者還需要具備一定的java功底。

honey badger版本

的勇敢無畏的主角——一隻蜜獾。它敢吃你給它的任何東西，根本不在乎那是什麼！

antlr 4有哪些神奇之處

antlr 4引入了一些新功能，降低了入門門檻，使得文法和語言類應用程式的開發更加容易。最重要的新特性在于，antlr 4幾乎能夠處理任何文法（除了間接左遞歸，稍後會提到）。在antlr将你的文法轉換成可執行的、人類可讀的文法分析代碼的過程中，文法沖突或者歧義性警告不會再出現。

無論多複雜的文法，隻要你提供給antlr自動生成的文法分析器的輸入是合法的，該文法分析器就能夠自動識别之。當然，你需要自行保證該文法能夠準确地描述目智語言。

antlr文法分析器使用了一種名為自适應ll()或者all()（讀作“all star”）的新技術，它是由我和sam harwell一起開發的。all()是antlr 3中的ll()的擴充，在實際生成的文法分析器執行前，它能夠在運作時以動态方式對文法執行分析，而非先前的靜态方式。由于all(*)文法分析器能夠通路實際的輸入文本，通過反複分析文法的方式，它最終能夠決定如何識别輸入文本。相比之下，靜态分析必須考慮所有可行的（無限長的）輸入序列。

在實踐中，擁有all(*)意味着你無須像在其他文法分析器生成工具（包括antlr 3）中那樣，扭曲文法以适應底層的文法分析政策。如果你曾經為antlr 3的歧義性警告和yacc的歸約/歸約沖突（reduce/reduce conflict）而抓狂，antlr 4就是你的不二之選！

另外一個強大的新功能是antlr 4極大地簡化了比對某些句法結構（如程式設計語言中的算術表達式）所需的文法規則。長久以來，處理表達式都是antlr文法（以及手工編寫的遞歸下降文法分析器）的難題。識别表達式最自然的文法對于傳統的自頂向下的文法分析器生成器（如antlr 3）是無效的。現在，利用antlr 4，你可以通過如下規則比對表達式：

類似expr的自引用規則是遞歸的，更準确地說，是左遞歸（left recursive）的，因為它的至少一個備選分支直接引用了它自己。

antlr 4自動将類似expr的左遞歸規則重寫成了等價的非左遞歸形式。唯一的限制是左遞歸必須是直接的，也就是說規則直接引用自身。一條規則不能引用另外一條規則，如果後者的備選分支之一在左側直接引用了前者（而沒有比對一個詞法符号）。詳見5.4節。

除了上述兩項與文法相關的改進，antlr 4還使得編寫語言類應用程式更加容易。antlr生成的文法分析器能夠自動建立名為文法分析樹（parse tree）的視圖，其他程式可以周遊此樹，并在所需處理的結構處觸發回調函數。在先前的antlr 3中，使用者需要補充文法來建立樹。除了自動建立樹結構之外，antlr 4還能自動生成文法分析樹周遊器的實作：監聽器（listener）或者通路器（visitor）。監聽器與在xml文檔的解析過程中響應sax事件的處理器相似。

由于擁有以下幾點antlr 3所不具備的新特性，antlr 4顯得非常容易上手：

最大的改變是antlr 4降低了文法中内嵌動作（代碼）的重要性，取而代之的是監聽器和通路器。新機制将文法和應用的邏輯代碼解耦，使得應用程式本身被封裝起來，而非散落在文法的各處。在沒有内嵌動作的情況下，你可以在多個程式中複用同一份文法，甚至都無須重新編譯生成的文法分析器。雖然antlr仍然允許内嵌動作的存在，但是在antlr 4中，它們更像是一種進階用法。這樣的行為能夠最大程度地掌控文法分析過程，但其代價是文法複用性的喪失。

由于antlr能夠自動生成文法分析樹和樹的周遊器，在antlr 4中，你無須再編寫樹文法。取而代之的是一些廣為人知的設計模式，如通路者模式。這意味着，在學會了antlr文法之後，你就可以重回自己熟悉的java領域來實作真正的語言類應用程式。

antlr 3的ll()文法分析政策不如antlr 4的all()強大，是以antlr 3為了能夠正确識别輸入的文本，有時候不得不進行回溯。回溯的存在使得文法的調試格外困難，因為生成的文法分析器會對同樣的輸入進行（遞歸的）多趟文法分析。回溯也為文法分析器在面對非法輸入時給出錯誤消息設定了重重障礙。

antlr 4是25年前我讀研究所學生時所走的一小段彎路的成果。我想，我也許會稍微改變我曾經的座右銘。

為什麼不花5天時間程式設計，來使你25年的生活自動化呢？

antlr 4正是我所期望的文法分析器生成器，現在，我終于能夠回頭去研究我原先在20世紀80年代試圖解決的問題——假如我還記得它的話。

本書的主要内容

本書是你所能找到的有關antlr 4的資訊源中最好、最完整的。免費的線上文檔提供了足夠多有關基礎文法的句法和語義的資料，不過沒有詳細解釋antlr的相關概念。在本書中，識别語言的文法模式和将其表述為antlr文法的内容是獨一無二的。貫穿全書的示例能夠在建構語言類應用程式方面助你一臂之力。本書可幫助你融會貫通，成為antlr專家。

本書由四部分組成。

第一部分介紹了antlr，提供了一些與語言相關的背景知識，并展示了antlr的一些簡單應用。在這一部分中，你會了解antlr的句法以及主要用途。

第二部分是一部有關設計文法和使用文法來建構語言類應用程式的“百科全書”。

第三部分展示了自定義antlr生成的文法分析器的錯誤處理機制的方法。随後，你會學到在文法中嵌入動作的方法——在某些場景下，這樣做比建立樹并周遊之更簡單，也更有效率。此外，你還将學會使用語義判定（semantic predicate）來修改文法分析器的行為，以便解決一些充滿挑戰的識别難題。

本部分的最後一章解決了一些充滿挑戰的識别難題，例如識别xml和python中的上下文相關的換行符。

第四部分是參考章節，詳細列出了antlr文法元語言的所有規則和antlr運作庫的用法。

完全不了解文法和語言識别工具的讀者請務必從頭開始閱讀。具備antlr 3使用經驗的使用者可從第4章開始閱讀以學習antlr 4的新功能。

第一部分　antlr和計算機語言簡介

第1章 初識antlr

第2章 縱觀全局

第3章 入門的antlr項目

第4章 快速指南

4.1 比對算術表達式的語言

4.2 利用通路器建構一個電腦

4.3 利用監聽器建構一個翻譯程式

4.4 定制文法分析過程

4.5 神奇的詞法分析特性

第二部分　使用antlr文法開發語言類應用程式

第5章 設計文法

5.1 從程式設計語言的範例代碼中提取文法

5.2 以現有的文法規範為指南

5.3 使用antlr文法識别常見的語言模式

5.4 處理優先級、左遞歸和結合性

5.5 識别常見的詞法結構

5.6 劃定詞法分析器和文法分析器的界線

第6章 探索真實的文法世界

6.1 解析csv檔案

6.2 解析json

6.3 解析dot語言

6.4 解析cymbol語言

6.5 解析r語言

第7章 将文法和程式的邏輯代碼解耦

7.1 從内嵌動作到監聽器的演進

7.2 使用文法分析樹監聽器編寫程式

7.3 使用通路器編寫程式

7.4 标記備選分支以擷取精确的事件方法

7.5 在事件方法中共享資訊

第8章 建構真實的語言類應用程式

8.1 加載csv資料

8.2 将json翻譯成xml

8.3 生成調用圖

8.4 驗證程式中符号的使用

第三部分　進階特性

第9章 錯誤報告與恢複

9.1 錯誤處理入門

9.2 修改和轉發antlr的錯誤消息

9.3 自動錯誤恢複機制

9.4 勘誤備選分支

9.5 修改antlr的錯誤處理政策

第10章 屬性和動作

10.1 使用帶動作的文法編寫一個電腦

10.2 通路詞法符号和規則的屬性

10.3 識别關鍵字不固定的語言

第11章 使用語義判定修改文法分析過程

11.1 識别程式設計語言的多種方言

11.2 關閉詞法符号

11.3 識别歧義性文本

第12章 掌握詞法分析的“黑魔法”

12.1 将詞法符号送入不同通道

12.2 上下文相關的詞法問題

12.3 字元流中的孤島

12.4 對xml進行文法分析和詞法分析

第四部分　antlr參考文檔

第13章 探究運作時api

13.1 包結構概覽

13.2 識别器

13.3 輸入字元流和詞法符号流

13.4 詞法符号和詞法符号工廠

13.5 文法分析樹

13.6 錯誤監聽器和監聽政策

13.7 提高文法分析器的速度

13.8 無緩沖的字元流和詞法符号流

13.9 修改antlr的代碼生成機制

第14章 移除直接左遞歸

14.1 直接左遞歸備選分支模式

14.2 左遞歸規則轉換

第15章 文法參考

15.1 文法詞彙表

15.2 文法結構

15.3 文法規則

15.4 動作和屬性

15.5 詞法規則

15.6 通配符與非貪婪子規則

15.7 語義判定

15.8 選項

15.9 antlr指令行參數

參考文獻