首页 > 代码库 > 用antlr4来实现《按编译原理的思路设计的一个计算器》中的计算器

用antlr4来实现《按编译原理的思路设计的一个计算器》中的计算器

上次在公司内部讲《词法分析——使用正则文法》是一次失败的尝试——上午有十几个人在场,下午就只来了四个听众。

本来我还在构思如何来讲“语法分析”的知识呢,但现在看来已不太可能。

 

这个课程没有预想中的受欢迎,其原因可能是:

1.课程内容相对复杂,听众知识背景与基础差异比较大。

2.授课技巧不够,不能把复杂的知识简单化的呈现给基础稍差一点的人。

 

针对这两个可能的原因,我要尝试做出以下调整:

1.使用antlr来实现词法和语法的部分。

2.暂时把“编译”过程改为“解释”来实现。

 

使用antlr的原因是:

1.采用文法生成器可直接略过词法和语法的部分直接进入语义分析,这样利于速成,同时避免学员被词法分析和语法分析的复杂性吓到,而失去了继续学习的勇气。

2.antlr的文法是LL(k)型,非常易于编写——虽然k型方法的性能肯定不如1型文法,但与初学者谈性能问题并不是一个好主意,不如直接避开性能不谈,能运行即可。

3.antlr默认生成的是java代码,这与公司内大多数员工的现有知识是相吻合的。

 

 下面进入正文。

 

一、什么是antlr?如何安装?

这不是一篇凑字数的文章,所以请直接参考官方网站(http://www.antlr.org/)。

我使用的是目前的最新版本(V4.2).

我上传了参考资料(包括jar包、电子书和官方示例)到百度云上,可从这个地址下载(http://pan.baidu.com/s/1hq65XWC)。

 

二、本计算器的文法示例及文法的解释。

整个计算器的词法的语法就由以下几行的antlr4代码来实现,先贴在下面:

grammar Calc;                            // 文法的名字为Calc

// 以下以小写字母开头的文法表示为语法元素
// 由大写字母开头的文法表示为词法元素
// 词法元素的表示类似于正则表示式
// 语法元素的表示类似于BNF

exprs : setExpr                            // set表达式
    | calcExpr                            // 或calc表达式
    ;

setExpr : ‘set‘ agmts ;                    // 以set命令开头,后面是多个赋值语句
agmts   : agmt (‘;‘ agmts)? ‘;‘? ;        // 多个赋值语句是由一个赋值语句后根着多个赋值语句,中间由分号分隔,结尾有一个可选的分号
agmt    : id=ID ‘=‘ num=NUMBER ;        // 一个赋值语句是由一个ID,后跟着一个等号,再后面跟送一个数字组成
calcExpr: ‘calc‘ expr ;                    // 以calc命令开头,后面是一个计算表达式

// expr可能由多个产生式
// 在前面的产生式优先于在后面的产生式
// 这样来解决优先级的问题

expr: expr op=(MUL | DIV) expr            // 乘法或除法
    | expr op=(ADD | SUB) expr            // 加法或减法
    | factor                            // 一个计算因子——可做为+-*/的操作数据的东西
    ;

factor: (sign=(ADD | SUB))? num=NUMBER    // 计算因子可以是一个正数或负数
    | ‘(‘ expr ‘)‘                        // 计算因子可以是括号括起来的表示式
    | id=ID                                // 计算因子可以是一个变量
    | funCall                            // 计算因子可以是一个函数调用
    ;

funCall: name=ID ‘(‘ params ‘)‘ ;        // 函数名后面加参数列表
params : expr (‘,‘ params)? ;            // 参数列表是由一个表达式后面跟关一个可选的参数列表组成

WS : [ \t\n\r]+ -> skip ;                // 空白, 后面的->skip表示antlr4在分析语言的文本时,符合这个规则的词法将被无视
ID : [a-z]+ ;                            // 标识符,由0到多个小写字母组成
NUMBER : [0-9]+(‘.‘([0-9]+)?)? ;        // 数字
ADD : ‘+‘ ;
SUB : ‘-‘ ;
MUL : ‘*‘ ;
DIV : ‘/‘ ;

 

 

我们把这段文法保存到一个文件Calc.g4中,并运行命令“antlr4 -visitor Calc.g4”即生成6个java文件和两个tokens文件。

这几个文件包括了这个计算器的“词法分析程序”、“语法分析程序”和一个visitor(CalcBaseVisitor.java),不过此时这个visitor内部实现都是空的,我们需要自己实现它。

在实现这个visitor之前,我们先实现一个上下文,上下文的做用有两个:

1.保存变量——用于在计算表达式中引用变量。

2.保存堆栈——用于函数的参数传递。

这个上下文的内容很少,代码也很短,直接贴在下面:

 1 public class Context {
 2     private static Context ourInstance = new Context();
 3 
 4     public static Context getInstance() {
 5         return ourInstance;
 6     }
 7 
 8     private Context() {
 9     }
10 
11     private Map<String, Double> map = new HashMap<>();
12     private Deque<Double> stack = new ArrayDeque<>();
13 
14     public Double getValue(String key) {
15         Double d = map.get(key);
16         return d == null ? Double.NaN : d;
17     }
18 
19     public void setContext(String key, Double value) {
20         map.put(key, value);
21     }
22 
23     public void setContext(String key, String value) {
24         setContext(key, Double.valueOf(value));
25     }
26 
27     public void pushStack(Double d) {
28         stack.push(d);
29     }
30 
31     public Double popStack() {
32         return stack.pop();
33     }
34 }

 

下面我们开始实现这个计算器的visitor,

 1 public class MyCalcVisitor extends CalcBaseVisitor<Double> {
 2 
 3     @Override
 4     public Double visitExprs(CalcParser.ExprsContext ctx) {
 5         return visit(ctx.getChild(0));
 6     }
 7 
 8     @Override
 9     public Double visitAgmt(CalcParser.AgmtContext ctx) {
10         Context.getInstance().setContext(ctx.id.getText(), ctx.num.getText());
11         return null;
12     }
13 
14     @Override
15     public Double visitAgmts(CalcParser.AgmtsContext ctx) {
16         visit(ctx.agmt());
17         if (ctx.agmts() != null)
18             visit(ctx.agmts());
19         return null;
20     }
21 
22     @Override
23     public Double visitCalcExpr(CalcParser.CalcExprContext ctx) {
24         return visit(ctx.expr());
25     }
26 
27     @Override
28     public Double visitExpr(CalcParser.ExprContext ctx) {
29         int cc = ctx.getChildCount();
30         if (cc == 3) {
31             switch (ctx.op.getType()) {
32             case CalcParser.ADD:
33                 return visit(ctx.expr(0)) + visit(ctx.expr(1));
34             case CalcParser.SUB:
35                 return visit(ctx.expr(0)) - visit(ctx.expr(1));
36             case CalcParser.MUL:
37                 return visit(ctx.expr(0)) * visit(ctx.expr(1));
38             case CalcParser.DIV:
39                 return visit(ctx.expr(0)) / visit(ctx.expr(1));
40             }
41         } else if (cc == 1) {
42             return visit(ctx.getChild(0));
43         }
44         throw new RuntimeException();
45     }
46 
47     @Override
48     public Double visitFactor(CalcParser.FactorContext ctx) {
49         int cc = ctx.getChildCount();
50         if (cc == 3) {
51             return visit(ctx.getChild(1));
52         } else if (cc == 2) {
53             if (ctx.sign.getType() == CalcParser.ADD)
54                 return Double.valueOf(ctx.getChild(1).getText());
55             if (ctx.sign.getType() == CalcParser.SUB)
56                 return -1 * Double.valueOf(ctx.getChild(1).getText());
57         } else if (cc == 1) {
58             if (ctx.num != null)
59                 return Double.valueOf(ctx.getChild(0).getText());
60             if (ctx.id != null)
61                 return Context.getInstance().getValue(ctx.id.getText());
62             return visit(ctx.funCall());
63         }
64         throw new RuntimeException();
65     }
66 
67     @Override
68     public Double visitParams(CalcParser.ParamsContext ctx) {
69         if (ctx.params() != null)
70             visit(ctx.params());
71         Context.getInstance().pushStack(visit(ctx.expr()));
72         return null;
73     }
74 
75     @Override
76     public Double visitFunCall(CalcParser.FunCallContext ctx) {
77         visit(ctx.params());
78         String funName = ctx.name.getText();
79         switch (funName) {
80         case "pow":
81             return Math.pow(Context.getInstance().popStack(), Context.getInstance().popStack());
82         case "sqrt":
83             return Math.sqrt(Context.getInstance().popStack());
84         }
85         throw new RuntimeException();
86     }
87 
88     @Override
89     public Double visitSetExpr(CalcParser.SetExprContext ctx) {
90         return visit(ctx.agmts());
91     }
92 
93 }

 最后再实现一个入口,调用这个Visitor即完成了我们的计算器。

入口代码如下:

 1 import java.util.Scanner;
 2 
 3 import org.antlr.v4.runtime.ANTLRInputStream;
 4 import org.antlr.v4.runtime.CommonTokenStream;
 5 import org.antlr.v4.runtime.tree.ParseTree;
 6 
 7 public class Portal {
 8 
 9     private static final String lineStart = "CALC> ";
10 
11     public static void main(String[] args) {
12         try (Scanner scanner = new Scanner(System.in)) {
13             System.out.print(lineStart);
14             while (scanner.hasNext()) {
15                 String line = scanner.nextLine();
16                 if (line != null) {
17                     line = line.trim();
18                     if (line.length() != 0) {
19                         if ("exit".equals(line) || "bye".equals(line))
20                             break;
21                         ANTLRInputStream input = new ANTLRInputStream(line);
22                         CalcLexer lexer = new CalcLexer(input);
23                         CommonTokenStream tokens = new CommonTokenStream(lexer);
24                         CalcParser parser = new CalcParser(tokens);
25                         ParseTree tree = parser.exprs();
26                         MyCalcVisitor mv = new MyCalcVisitor();
27                         Double res = mv.visit(tree);
28                         if (res != null)
29                             System.out.println(res);
30                     }
31                 }
32 
33                 System.out.print(lineStart);
34             }
35         }
36     }
37 
38 }

 

整个计算器只写了一个文法和三个类,所有代码都贴在上面了,想对于完全自己手写的计算器来说,的确是简单很多了。