ANTLR
ANTLR(全名:ANother Tool for Language Recognition)是基于LL(*)算法实现的语法解析器生成器(parser generator),用Java语言编写,使用自上而下(top-down)的递归下降LL剖析器方法。由旧金山大学的Terence Parr博士等人於1989年開始發展。
原作者 | Terence Parr 與其他參與者 |
---|---|
初始版本 | 1992年2月 |
穩定版本 | 4.7.1 / 3.5.2 (2017年12月10日 / 2014年3月25日 ) |
源代码库 | |
编程语言 | Java |
系統平台 | Cross-platform |
许可协议 | BSD License |
网站 | www |
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[1]。
如同一般的詞法分析器(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)[2],這是所有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
參見
- JavaCC
- SableCC
- DMS Software Reengineering Toolkit
- Coco/R
- Modular Syntax Definition Formalism
- Parboiled (Java)
注釋
- (PDF). [2015-02-17]. (原始内容存档 (PDF)于2014-12-01).
- ANTLR会提示:“rule is left-recursive”错误。
文獻
- Parr, Terence, 1st, Pragmatic Bookshelf: 376, May 17, 2007 [2015-02-17], ISBN 0-9787392-5-6, (原始内容存档于2016-04-03)
- Parr, Terence, 1st, Pragmatic Bookshelf: 374, December 2009 [2015-02-17], ISBN 978-1-934356-45-6, (原始内容存档于2016-02-24)
- Parr, Terence, 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. . 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