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/。

该插件特点：

1. 新建一般的java project（如果要生成的目标语言是java的话）并convert成antlr即可，之后只需写grammar文件。
2. 默认情况下保存每一次grammar文件就会进行自动生成对应的lexer和parser的java文件（默认target language是java）和对应tokens文件；每次打开eclipse时会重新解析一次。
3. 似乎生成的lexer和parser并不会添加grammar文件所在package信息（吐槽：这一点和上面一个特点加起来足以让人抓狂！！！）。
4. 编辑器的content assit功能和java编辑器的功能有不少出入，括号、引号、缩进等功能做得并不好。
5. grammar（g文件）除编辑器的两个tab Interpreter和Railroad view非常棒，一个用于傻瓜式写，一个用于GUI显示，并且可以导出成html。

还可以考虑使用StringTemplate：http://www.stringtemplate.org/download.html

开始使用

以含有加减乘法的计算器且目标语言java为例。

• 在g文件中写出所要定义的grammer（一般是词法和语法的综合）

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();};

• 生成的ExprLexer.java文件中会将'(',')'等涉及判定的字符用新的identifier如T__8等来对应，识别这样的字符的方法形如T__8。新生成的ExprLexer类继承了antlr定义的Lexer类，封装了一些方法。ExprParser继承Parser类，诸如expr等g文件中的左式会有个对应的方法（例如expr()）来处理它；为了处理出错和从错误状态恢复，该类还生成了FOLLOW_expr_in_stat34这样的变量并调用了pushFollow()这类方法。
• 这样，从输入流中可以生成lexer对象，将由lexer得到的tokens作为输入就得到一个parser对象；调用顶层的方法就可以完成语法分析了。

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();
	}

• 上述代码对于符合grammar的输入不会有输出，如果需要给出相应的输出的话仍可以在g文件中添加（java）代码。

1. 添加包含的package

@header{
import java.util.HashMap;
}

2. 添加parser中的成员变量

@members{
/** Map variable name to Integer object holding value */
HashMap memory = new HashMap();
}

3. 添加parser中左式处理函数的返回值（前面代码中的方法的返回值都为void），并且在每个生成式上在{}里添加特定的方法。值得注意的是对于诸如INT这样在lexer中得到的Token用的是antlr定义好的Token类的一个对象，包含了getText()方法；故不需要定义INT的text返回值。如下面的一段：

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致敬？）。