antlr是什么
权威解释见官方或wikipedia,我只负责八卦。作者Terence Parr似乎是个有洁癖的人,写了antlr第一个版本之后觉得效率不高又写了v2,因为同样的理由又推倒重来写了v3。尽管以java为主打,但这个antlr非常有野心,Java/C#/Python/Ruby/Scala等语言通吃;由grammar生成lexer和parser使得这玩意儿非常适合教学用,也非常适合菜鸟级程序员提高编写编译器的自信。虽说没有JavaCC这么正统,但是个人觉得非常实用,现在Hibernate framework/Jython/Groovy可都是基于antlr的哦!这哥们还开发了一套template engine,同样是一个妄图大一统文本解析的干活。有了antlr这把锤子他就开始到处乱敲:paper自不用说,然后是《The Definitive ANTLR Reference》、《Language Implementation Patterns》。后者近期被译成中文,号称“屠龙”;虽说的确过誉了,但是不得不承认这本书的确深入浅出。尽管作者一直在自卖自夸antlr和StringTemplate,但是对于java系的人来讲这的确是学习编译原理基础知识的好东西;连Guido大叔和Dalvik设计者Dan Bornstein也对这本书颇有好评。
安装工具
antlr:http://www.antlr.org/download.html
对于我这样的习惯了eclipse的懒人来说antlrworks并不是上上之策,插件才是王道http://antlrv3ide.sourceforge.net/。
该插件特点:
还可以考虑使用StringTemplate:http://www.stringtemplate.org/download.html
开始使用
以含有加减乘法的计算器且目标语言java为例。
grammar Expr; prog : stat+; stat : expr NEWLINE | ID '=' expr NEWLINE | NEWLINE ; expr: multiExpr (('+'|'-') multiExpr)* ; multiExpr : atom('*' atom)* ; atom : INT | ID | '(' expr ')' ; ID : ('a'..'z'|'A'..'Z')+ ; INT : '0'..'9'+; NEWLINE : '\r'?'\n'; WS : (' '|'\t'|'\n'|'\r')+{skip();};
public static void main(String[] args) throws IOException, RecognitionException { // TODO Auto-generated method stub ANTLRInputStream input = new ANTLRInputStream(System.in); ExprLexer lexer = new ExprLexer(input); CommonTokenStream tokens = new CommonTokenStream(lexer); ExprParser parser = new ExprParser(tokens); parser.prog(); }
@header{ import java.util.HashMap; }
@members{ /** Map variable name to Integer object holding value */ HashMap memory = new HashMap(); }
expr returns [int value] : e=multExpr {$value = $e.value;} ( '+' e=multExpr {$value+=$e.value;} | '-' e=multExpr {$value-=$e.value;} )* ; multExpr returns [int value] : e = atom {$value=$e.value;}('*' e=atom {$value *= $e.value;})* atom returns [int value] : // value of an INT is the int computed from char sequence INT {$value=Integer.parseInt($INT.text);} | ID // variable reference { // look up value of variable Integer v = (Integer)memory.get($ID.text); // if found, set return value else error if(v!=null) $value = v.intValue(); else System.err.println("undefined variable "+$ID.text); } // value of parenthesized expression is just the expr value | '(' expr ')'{$value=$expr.value;} ;
--------------------------------------------------
参考自《The Definitive ANTLR Reference》,又是一本没付版权费的电子书:(
PS:通过antlr生成的代码,我才知道java对于退出多重循环有个不错的做法,就是在指定的循环前面添加上某个label,然后在要退出的时候加上break label。我们都知道尽管java把goto作为保留字,但是在咱码农是没法用goto的。使用这样break的做法肯定没有C/C++来得凶残;但是无疑很好地避免了goto带来的无结构编程恶习,同时又保留了灵活性(似乎该对D.E.Knuth致敬?)。
Wed, 26 Sep 2012 09:33:05 +0800
ANTLR 确实不错。LL'(k) basically makes LALR obsolete. 而且还支持回溯 parsing(通过 exception),基本解决了左递归和不确定语法的问题。这是我 04 年看的时候的成果。