编译原理
5 篇文章3 订阅
订阅专栏
Antlr(ANother Tool for Language Recognition)是一款优秀的语言识别工具，你只需要使用扩展巴科斯范式(EBNF)定义好语法规则，Antlr就可以帮你完成词法分析和语法分析的工作，然后自己再完成语义分析和运行时，就可以很轻易写出一门简单的脚本语言。 今天我们先不写语言，而是只用antlr完成一个比较简单的功能——表达式计算。
得益于antlr的强大功能，我们自己仅需要写20多行简单代码就能实现任意复杂度的四则运算表达求值。本次代码我已全部放在github上，其中Expr.g4为语法规则定义文件，MyExprVisitor.java为实现代码，ExprMain.java为测试功能用的main方法，其余均为antlr自动生成的java代码。
我们先来看下Expr.g4所定义的语法规则，没错，即便是简单的四则运算也是有规则的，其实就是我们小学三年级学到的四则运算计算优先级规则，括号内最优先，其次是乘除法，最后才是加减法。
grammar Expr; @header { package xyz.xindoo.ulang.expr; } expression : primary | expression bop=('*'|'/') expression | expression bop=('+'|'-') expression ; primary : '(' expression ')' | number ; number : Digits | Digits '.' Digits ; Digits : [0-9] ([0-9]*)? ;
上面语法就是四则运算的巴科斯范式定义(EBNF)，可能对初学者有点难理解，其实就是一个递归定义，一个表达式可能是有多个子表达式构成，但子表达式的尽头一定是数字。 antlr可以用EBNF所定义的规则，将某个输入串解析为一颗抽象语法树(AST)。我们以表达式((3+3)*(1+4))/(5-3) 为例，它的抽象语法树如下：
如果你仔细看上面这棵树，就会发现((3+3)*(1+4))/(5-3) 的结果就是这颗树后序遍历的结果。 优先级在哪体现呢？ 有没有发现，优先级越高的子表达式，其在AST中的深度越深，它也就被越先计算，上图太复杂可能看不出来，我们以1+2*3为例，如下图：
在antlr中，语法的优先级体现在其次序中，规则排的越靠前，其优先级越高。
说完了语法规则，我们来说下具体如何求值。上文已经说过了，对AST后序遍历就可以得到其结果。antlr可以中已经实现了语法树的遍历，而你只需要使用antlr的命令 antlr4 -visitor Expr ，生成代码后自己实现其中每个类型节点的遍历方法即可，这里我使用了visitor模式，自己只需要重写ExprBaseVisitor类即可，重写后如下：
package xyz.xindoo.ulang.expr; public class MyExprVisitor extends ExprBaseVisitor<Double> { @Override public Double visitExpression(ExprParser.ExpressionContext ctx) { if (null == ctx.bop) { return visitChildren(ctx); } switch (ctx.bop.getText()) { case "+": return visit(ctx.children.get(0)) + visit(ctx.children.get(2)); case "-": return visit(ctx.children.get(0)) - visit(ctx.children.get(2)); case "*": return visit(ctx.children.get(0)) * visit(ctx.children.get(2)); case "/": return visit(ctx.children.get(0)) / visit(ctx.children.get(2)); } return 0.0; } @Override public Double visitPrimary(ExprParser.PrimaryContext ctx) { if (ctx.children.size() == 3) { return visit(ctx.children.get(1)); } return visitChildren(ctx); } @Override public Double visitNumber(ExprParser.NumberContext ctx) { return Double.parseDouble(ctx.Digits().get(0).getText()); } }
没错，就这么简单，只实现每种类型节点的遍历方法就行了，接下来就是写个main方法来测试下功能是否正常。
public class ExprMain { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); while (scanner.hasNext()) { String expr = scanner.nextLine(); ExprLexer lexer = new ExprLexer(CharStreams.fromString(expr)); CommonTokenStream tokens = new CommonTokenStream(lexer); ExprParser parser = new ExprParser(tokens); ExprParser.ExpressionContext expressionContext = parser.expression(); MyExprVisitor visitor = new MyExprVisitor(); Double res = visitor.visitExpression(expressionContext); System.out.println("=" + res); } } }
跑几个样例测试下，结果全部正确。
写完收工……
