ANTLR学习心得——表达式 （转与JavaEye技术社区）

 

先说说我们打算干什么，表达式是几乎所有高级编程语言中，都会出现的重要组成部分。因此，如何准确的理解一个表达式，可以说是各种不同的语言所共同面临的问题。表达式千变万化，真正要想正确解释C/C++那样的复杂表达式，是非常困难的，我们这里只从最简单的表达式做起。   假设一个表达式中，只有常量，没有变量。所有的运算只有：“+”、“-”、“*”、“/”、“^”、“%”六种，而且没有括号，只有整数，没有小数。就这么简单，要解释这样的表达式，我们如果要想自己写个程序来解释，只怕也是非常麻烦的吧。当年我就自己搞过一次，我的本专业不是计算机系，所有也没有学过任何编译原理的东西，Lex呀、Yacc呀、Antlr呀，一概没有听说过，就一股子劲自己去搞。我的办法现在想想也挺简单的，一个表达式，要么是数字，要么是运算符，我就规定死了，中间一律用一个空格分割开来，这样就不需要词法分析了然后再自己编程序，硬写递归计算（当时连前缀表达式都没听说过），那个苦啊。   现在有了ANTLR，我们只需要将定义写清楚，程序就会自动帮我们生成了。可以先下载一个人家现成的文件来看看：expression.g，然后再antlr expression.g生成一堆java文件。   接下来的步骤和前面的也差不多，建一个Main.java， import java.io.*; import antlr.CommonAST; import antlr.collections.AST; import antlr.debug.misc.ASTFrame; public class Main {   public static void main(String args[]) {     try {       DataInputStream input = new DataInputStream(System.in);       ExpressionLexer lexer = new ExpressionLexer(input);       ExpressionParser parser = new ExpressionParser(lexer);       parser.expr();       CommonAST parseTree = (CommonAST)parser.getAST();       System.out.println(parseTree.toStringList());       ASTFrame frame = new ASTFrame("The tree", parseTree);       frame.setVisible(true);       ExpressionTreeWalker walker = new ExpressionTreeWalker();       double r = walker.expr(parseTree);       System.out.println("Value: "+r);     } catch(Exception e) { System.err.println("Exception: "+e); }   } } 执行这个Main.class，输入个表达式给它试一试，比如： 1+2-3*4/5^6;系统应该就能给出正确的答案了： ( - ( + 1 2 ) ( / ( * 3 4 ) ( ^ 5 6 ) ) ) ; Value: 2.999232   咱们来一句一句的解释一下这个expression.g文件。还是从最简单的几行开始：   class ExpressionLexer extends Lexer; //这是用来声明一个词法分析器，名字叫                                                    //ExpressionLexer PLUS  : ‘+‘ ;                                   //加号 MINUS : ‘-‘ ;                                   //减号 MUL   : ‘*‘ ;                                   //乘号 DIV   : ‘/‘ ;                                    //除号 MOD   : ‘%‘ ;                                 //求余 POW   : ‘^‘ ;                                 //开方 SEMI  : ‘;‘ ;                                    //结束号                                                    //上面这些都太简单了，简直就不需要说明 protected DIGIT : ‘0‘..‘9‘ ;               //数字，这是一个受保护的单词，只能被                                                    //词法分析器内部使用 INT   : (DIGIT)+ ;                           //出现了一次以上的数字的词，就是整数，                                                    //它通过受保护的单词：“数字”来定义自己。                                                    //如果DIGIT不是被保护的单词，则词法分析器就会                                                    //无法分辨究竟是数字还是整数了   接下来看语法分析器的代码：   class ExpressionParser extends Parser;   //定义一个语法分析器，名字叫ExpressionParser options { buildAST=true; }                  //告诉ANTLR，要帮我生成一个抽象语法树，                                                        //留着以后有用   //接下来的部分就非常复杂了，主要是多出来了两个特殊的符号“!”、“^” //这两个符号，不是EBNF原有的，而是ANTLR为了生成AST而增加的符号 //“!”，是告诉AST生成程序，不要把自己算进去 //“^”，是告诉AST生成程序，把这个符号，放在一颗树的根部，或者一颗子树的根部 //另外，“*”表示出现0次以上，“+”表示出现一次以上，“?”表示出现0或1次 expr     : sumExpr SEMI!;                                           //“;”作为结束符，不放入AST sumExpr  : prodExpr ((PLUS^|MINUS^) prodExpr)* ;     //“+”“-”作为计算符号                                                                               //放在树的顶部 prodExpr : powExpr ((MUL^|DIV^|MOD^) powExpr)* ; //剩下的就不解释了，都能明白的 powExpr  : atom (POW^ atom)? ; atom     : INT ;   再来看AST计算器的代码。这“AST计算器”是我起的名字，也就是通过对一个生成的抽象语法树，递归求值，得到最后的结果。   {import java.lang.Math;}                                     //ExpressionTreeWalker要用到的 class ExpressionTreeWalker extends TreeParser;    //声明一个树计算器 expr returns [double r]                                      //有一个方法叫expr                                                                       //它的返回值是double类型   {double a,b; r=0; }                                         //嵌入的代码，后面要用到   : #(PLUS a=expr b=expr)  { r=a+b; }               //以下就是计算各种算符，不用多说了   | #(MINUS a=expr b=expr) { r=a-b; }   | #(MUL  a=expr b=expr)  { r=a*b; }   | #(DIV  a=expr b=expr)  { r=a/b; }   | #(MOD  a=expr b=expr)  { r=a%b; }   | #(POW  a=expr b=expr)  { r=Math.pow(a,b); }   | i:INT { r=(double)Integer.parseInt(i.getText()); }   ;