跳至內容

英文维基 | 中文维基 | 日文维基 | 草榴社区

ANTLR

維基百科,自由的百科全書
ANTLR
原作者Terence Parr英語Terence Parr 與其他參與者
首次發佈1992年2月
當前版本
  • 4.13.2(2024年8月3日;穩定版本)[1]
編輯維基數據鏈接
原始碼庫 編輯維基數據鏈接
程式語言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最初叫做PCCTSPurdue Compiler Construction Tool Set,是Terence Parr在普渡大學攻讀碩士學位時的創作,在Hank Dietz教授的指導下,開始研究構造自動化的分析器。1993年,Parr取得博士學位,並於同年發佈ANTLR 1.10版。最早的ANTLR只支持Java,直到ANTLR 3以後開始支持Ada95CC#JavaScriptObjective-CPerlPythonRubyC++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值。

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

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

用於何處

[編輯]

下列為ANTLR的使用列表:

參見

[編輯]

註釋

[編輯]
  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」錯誤。

文獻

[編輯]

深入閱讀

[編輯]

外部連結

[編輯]