大学时, 写过不少需要文法分析的Project, 如MiniSQL的SQL语法, 简易计算器等. 从计算理论的角度来说, 相对于正则的孱弱. DFA对于文法的表达能力是简单强大的. 因此, 也就有了DFA的文法分析工具. 几乎每一本编译原理的书上, 都会提到Lex/Yacc这一对词法语法分析工具(如果没有, 就扔掉它, -,-). 30几年的历史, 也证明了Lex/Yacc的强大. 然而, 也正因为其历史, 使之的OO支持上存在着很大问题. 毕竟, C才是其母语. 所以, 新的工具ANTLR就自然地诞生了.
首先来介绍一下吧.
What is ANTLR?
ANTLR, ANother Tool for Language Recognition, (formerly PCCTS) is a language tool that provides a framework for constructing recognizers, compilers, and translators from grammatical descriptions containing Java, C#, C++, or Python actions.
究其源, ANTLR只是一个Java工具, 一个文法分析工具, 它提供了把相应rule生成包括Java,C++等语言的支持.
Q: How to use?
A: $java -cp $(antlr-jar-path) antlr.Tool example.g
然后就生成了相应的文件了.
相比于Lex/Yacc, ANTLR多了以下优点(个人使用感觉).
- 面向对象的设计和面对对象的使用. OO的过程.
- LL(k)语法. 比LALR, 更加的强大. 同时也没有了烦人的shift-reduce, reduce-reduce之类的语法冲突错误.
- Error Handling. ANTLR是完全exception-driven的. 错误处理机制灵活健全. exception的最小粒度能得到具体token, 方便你在语法解析时控制系统的错误处理.
- 生成后代码的可读性. 全部封装在对应的class里面, 便于阅读. 在语法的parser上, ANTLR使用了直观的switch/case来匹配token(而不是Yacc的parser table), 进而匹配这个规则, 类似于手动写一个DFA. 同时, 由于编译器对于switch的优化, 效率上并没多大影响.
- 对语言的支持. 对于一个rule, 你可以方便的加入一段代码. 同时, 你可以很方便在规则之外加入类的成员变量, 类的成员函数(对于封装很有好处)以及全局的变量和函数等.
- 生成后的代码使用简单. Simple Example: ExampleLexer lexer(cin); ExampleParser paser(lexer); parser.expr(); . 同时也可见, 易于封装.
- 可以定义rule的返回值, rule的参数. 在rule relation的处理上更加地强大.
- 提供了丰富的built-in function.
- Unicode的支持. 你几乎不需要做额外的工作.
在官网里面, 还特别提到了一点:
ANTLR provides excellent support for tree construction, tree walking, and translation.
即对TreeParser和AST的支持. 不过由于我的语法很少需要用到TreeWalker, 没多少体会.
ok. 先介绍到这吧. 后续将给出具体的example.
强烈推荐一下.
官方网址: http://www./
maillist: antlr-interest@
不知道现在大学是否还在使用yacc/lex, 还是类似javacc/antrl这类比较oo的文法分析器。
LL(k)语法. 比LALR, 更加的强大. 同时也没有了烦人的shift-reduce, reduce-reduce之类的语法冲突错误.
怎么解释?
现在编译课上lex/yacc还是主流, 至少我当时学时老师连javacc/antlr这些文法分析器介都没介绍过. 另一个原因也是我提到的, 基本每一本编译原理的书都是以lex/yacc作为词法分析工具的.
LL(k)语法, 较之 LALR, 主要的区别是LL是top-down, LALR是bottom-up. 所以, 对我们而言, 显然使用top-down的递归下降方式更能接受, 符合我们直接的逻辑. 同时, 这也是LL语法没有shift-reduce, reduce-reduce的原因. 可以说, 后面ANTLR的特性, 如错误处理, 代码可读性, 就是LL带来的好处. 用LALR是没有办法做到的.
LL(k)有两个限制:
1. 不能用left-recursive
2. lookahead是k个.
第一个是硬限制. 第二个ANTLR v3有较好解决.
ANTLR v3 其中的一个大的新feature: significantly enhanced parsing strength via LL(*) parsing with arbitrary lookahead.
~~~~~~~
the lookahead length is not fixed.
用官网的例子就是:
func : type ID ‘(’ arg* ‘)’ ‘;’
| type ID ‘(’ arg* ‘)’ ‘{’ body ‘}’
文法分析使用’,‘, ‘{’来区别两个不同的规则.
在ANTLR v2.7里, 这个就没有办法做到, 我们只能用semantic predict或者分开两个规则.
semantic predict方式:
func: ( type ID ‘(’ arg* ‘)’ ) => type ID ‘(’ arg* ‘)’ ‘;’
| (type ID ‘(’ arg* ‘)’ ‘{’ ) => type ID ‘(’ arg* ‘)’ ‘{] body ‘}’
ps: 个人愚见, :) 编译原理很久没碰, 不一定说对了. 欢迎大家指出.
路过
[…] 在(I)里，我已经简单介绍了ANTLR。现在，让我们继续ANTLR之旅，来真实感受一下它的强大。 […]