ANTLR

ANTLR
原作者	Terence Parr（英語：Terence Parr）與其他參與者
首次發布	1992年2月
當前版本	4.13.2（2024年8月3日；穩定版本）;
原始碼庫	github.com/antlr/antlr4;
程式語言	Java
平台	Cross-platform
許可協議	BSD License
網站	www.antlr.org

ANTLR（全名：ANother Tool for Language Recognition）是基於LL(*)算法實現的語法解析器生成器（parser generator），用Java語言編寫，使用自上而下（top-down）的遞歸下降LL剖析器方法。由舊金山大學的Terence Parr博士等人於1989年開始發展。

ANTLR最初叫做PCCTS，Purdue Compiler Construction Tool Set，是Terence Parr在普渡大學攻讀碩士學位時的創作，在Hank Dietz教授的指導下，開始研究構造自動化的分析器。1993年，Parr取得博士學位，並於同年發布ANTLR 1.10版。最早的ANTLR只支持Java，直到ANTLR 3以後開始支持Ada95、C、C＃、JavaScript、Objective-C、Perl、Python、Ruby、C++和Standard ML^[2]。

如同一般的詞法分析器（lexer）和語法分析器（parser），ANTLR可以用來產生樹狀分析器（tree parsers）。ANTLR 文法定義使用類似EBNF（Extended Backus-Naur Form）的定義方式，形象十分簡潔直觀。例如: ANTLR用A : a;來表示規則，舊式的方法則是以 A=>a 表示，所以ANTLR是以「:」代替了「=>」。ANTLR的規則要以分號「;」結束。又如其他ANTLR符號「|」代表「或」的關係，又如「*，+」表示可以出現0次或多次。

ANTLR本身使用switch-case來匹配token，形成記號序列記號流，舊式的Yacc則利用符號表（parser table）。ANTLR是完全exception-driven，LL(k)語法比目前流行的LR剖析器（包含SLR, LALR等）強大，更可以避免LR剖析器既有的位移-歸約（shift-reduce）或歸約-歸約（reduce-reduce）之類的語法衝突，產生的代碼清楚易懂，便於程式設計師閱讀和理解。同時更支持Unicode。

ANTLR v4

早期Antlr的LL(*)文法仍不支持「左遞歸」（left-recursion）^[3]，這是所有LL剖析器的侷限，在左遞歸過程沒有消耗掉任何token, LL剖析器很容易造成stack overflow。至於如何消除左遞歸問題，在ANTLR 3中會將parsing策略退化為LL(1) + 回溯的形式。ANTLRWorks則提供一些自動消除左遞歸的功能，但不實用。接下來的ANTLR v4大力支持Kleene Closure表示法，透過kleene star(*)和kleene cross(+)的語法糖（syntax sugar），直接以while語句取代遞歸，總算可以順利解決LL分析法所不允許的左遞歸（但仍不能應付間接左遞歸，比如兩條分支擁有共同的遞歸規則作為前綴），因此可兼容Yacc的文法。再者，ANTLR對於LL(*)不能正確分析的情況，還支持語義斷言（Semantic Predicate）來輔助判斷, Semantic Predicate可以是任何邏輯，只需返回bool值。

目前Hibernate與WebLogic都是使用ANTLR做為來解析HQL。在NetBeans IDE中更以ANTLR解析C++。Twitter搜索使用ANTLR解析，一天超過200億次查詢。

雖然ANTLR本身是免費的，但《The Definitive ANTLR Reference》這本參考書則屬於使用者付費。目前免費文件極少。

用於何處

下列為ANTLR的使用列表:

Groovy
Jython
Hibernate
OpenJDK Compiler Grammar project（頁面存檔備份，存於網際網路檔案館） experimental version of the javac compiler based upon a grammar written in ANTLR
Apex, Salesforce.com's programming language
The expression evaluator in Numbers, Apple's spreadsheet
Twitter's search query language
Weblogic server
IntelliJ IDEA（頁面存檔備份，存於網際網路檔案館） and Clion.（頁面存檔備份，存於網際網路檔案館）
Apache Cassandra
Processing

參見

注釋

^ Release 4.13.2. 2024年8月3日 [2024年8月20日].
^ SML/NJ Language Processing Tools: User Guide (PDF). [2015-02-17]. （原始內容存檔 (PDF)於2014-12-01）.
^ ANTLR會提示:「rule is left-recursive」錯誤。

文獻

Parr, Terence, The Definitive Antlr Reference: Building Domain-Specific Languages 1st, Pragmatic Bookshelf: 376, May 17, 2007 [2015-02-17], ISBN 0-9787392-5-6, （原始內容存檔於2016-04-03）
Parr, Terence, Language Implementation Patterns: Create Your Own Domain-Specific and General Programming Languages 1st, Pragmatic Bookshelf: 374, December 2009 [2015-02-17], ISBN 978-1-934356-45-6, （原始內容存檔於2016-02-24）
Parr, Terence, The Definitive ANTLR 4 Reference 1st, Pragmatic Bookshelf: 328, January 15, 2013 [2015-02-17], ISBN 978-1-93435-699-9, （原始內容存檔於2015-04-18）

深入閱讀

Parr, T.J.; Quong, R.W. ANTLR: A Predicated-LL(k) Parser Generator. Software: Practice and Experience. July 1995, 25 (7): 789–810. doi:10.1002/spe.4380250705.

外部連結

官方網站
ANTLRWorks（頁面存檔備份，存於網際網路檔案館）
ANTLR Studio（頁面存檔備份，存於網際網路檔案館）
ANTLR tutorial（頁面存檔備份，存於網際網路檔案館） at the University of Birmingham
Why Use ANTLR?（頁面存檔備份，存於網際網路檔案館）
Antlr plugin for Maven

[wikidata-8d6ed93e8cc764507952eea0e407bf7185aa56a1-v3-1] Release 4.13.2. 2024年8月3日 [2024年8月20日].

[2] SML/NJ Language Processing Tools: User Guide (PDF). [2015-02-17]. （原始內容存檔 (PDF)於2014-12-01）.

[3] ANTLR會提示:「rule is left-recursive」錯誤。

[1]

[2]

[3]