茶年 · 中文维基百科

ANTLR

Wikipedia · 2024-09-20 维基百科 👁 1 阅读

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。

如同一般的詞法分析器（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），這是所有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的使用列表:

參見

  • JavaCC
  • SableCC
  • DMS Software Reengineering Toolkit
  • Coco/R
  • Modular Syntax Definition Formalism
  • Parboiled (Java)

注釋
文獻
*
*
*

深入閱讀
*

外部連結
*

#编译器软件

评论 (0)

  • 还没有评论，来抢沙发吧。