乐者为王

Do one thing, and do it well.

ANTLR 4权威参考读书笔记(24)

在本节中,我们准备讲讲有时候事件方法需要传递部分结果或其它信息的问题。

在事件方法间共享信息

无论收集信息还是计算值,传递参数和返回值都是比使用字段和全局变量更方便良好的编程实践。问题是ANTLR自动生成的监听器方法的签名不需要特定应用的返回值或参数,ANTLR也自动生成访问者方法而不需要特定应用的参数。

接下来,我们将探讨让事件方法无需修改事件方法签名就能传递数据的机制。我们将构建同样的简单计算器的3个不同实现,基于前面章节的LExpr表达式语法。第一个实现使用访问者方法返回值,第二个定义了一个在事件方法间共享的字段,第三个则注解语法分析树节点以便储存感兴趣的值。

使用访问者遍历语法分析树

构建基于访问者的计算器,最简单的方法是让和规则expr相关的事件方法返回子表达式的值。例如,visitAdd()将返回两个子表达式相加的值,visitInt()将返回整型的值。传统的访问者不指定visit方法的返回值。当我们为特定应用需求实现一个类时添加返回类型是容易的,扩展LExprBaseVisitor并提供Integer作为类型参数。访问者代码看起来如下所示:

1
2
3
4
5
6
7
8
9
10
11
public static class EvalVisitor extends LExprBaseVisitor<Integer> {
    public Integer visitMult(LExprParser.MultContext ctx) {
        return visit(ctx.e(0)) * visit(ctx.e(1));
    }
    public Integer visitAdd(LExprParser.AddContext ctx) {
        return visit(ctx.e(0)) + visit(ctx.e(1));
    }
    public Integer visitInt(LExprParser.IntContext ctx) {
        return Integer.valueOf(ctx.INT().getText());
    }
}

EvalVisitor从ANTLR生成的AbstractParseTreeVisitor类继承通用的visit()方法,我们的访问者使用它去准确地触发子树访问。

注意,EvalVisitor没有针对规则s的访问者方法。在LExprBaseVisitor中的visitS()的默认实现调用预定义的方法ParseTreeVisitor.visitChildren(). visitChildren()返回从最后的子节点访问返回的值。在这里,visitS()返回访问它唯一的子节点(节点e)时返回的表达式的值。我们可以使用这种默认的行为。

在测试文件TestLEvalVisitor.java中,我们有常用代码去启动LExprParser和打印语法分析树,然后我们需要编码去启动EvalVisitor和打印出当访问树时计算出的表达式的值。

1
2
3
EvalVisitor evalVisitor = new EvalVisitor();
int result = evalVisitor.visit(tree);
System.out.println("visitor result = " + result);

要构建计算器,需要告诉ANTLR使用-visitor参数去生成访问者。(如果我们不再需要生成监听器,可以使用-no-listener参数)以下是完整的构建和测试序列:

1
2
3
antlr -visitor LExpr.g
compile *.java
run TestLEvalVisitor

接着输入以下内容:

1
2
1+2*3
EOF

你就会看到如下结果:

1
2
(s (e (e 1) + (e (e 2) * (e 3))))
visitor result = 7

如果我们需要特定应用的返回值,访问者工作的相当好,因为我们使用了内建的Java返回值机制。如果我们不希望显式地调用访问者方法去访问子节点,我们可以切换到监听器机制,不幸的是,这意味着我们要放弃使用Java方法返回值的整洁。

使用栈模拟返回值

ANTLR生成的监听器事件方法没有返回值。为了给在语法分析树更高节点上执行的监听器方法返回值,我们可以把部分的值存储在监听器的一个字段中。我们会想到用栈来存储值,方法就是把计算一个子表达式的结果推送到栈中,在语法分析树上用于子表达式的方法则把运算元从栈中弹出。以下是完整的Evaluator计算器监听器(代码在TestLEvaluator.java文件中):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static class Evaluator extends LExprBaseListener {
    Stack<Integer> stack = new Stack<Integer>();
    public void exitMult(LExprParser.MultContext ctx) {
        int right = stack.pop();
        int left = stack.pop();
        stack.push(left * right);
    }
    public void exitAdd(LExprParser.AddContext ctx) {
        int right = stack.pop();
        int left = stack.pop();
        stack.push(left + right);
    }
    public void exitInt(LExprParser.IntContext ctx) {
        stack.push(Integer.valueOf(ctx.INT().getText()));
    }
}

要测试上面的这段代码,我们可以创建和使用在代码TestLEvaluator中的ParseTreeWalker,以下是完整的构建和测试序列:

1
2
3
antlr LExpr.g
compile *.java
run TestLEvaluator

接着输入以下内容:

1
2
1+2*3
EOF

你就会看到如下结果:

1
2
(s (e (e 1) + (e (e 2) * (e 3))))
stack result = 7

使用栈字段有点别扭但工作得很好。我们必须确保事件方法以正确的顺序压入和弹出跨越监听器事件的值。带有返回值的访问者没有栈的这种笨拙但却需要手工访问树的节点。第三种实现是通过把部分值隐藏在树节点中来捕获它们。

注解语法分析树

作为使用临时存储在事件方法间共享数据的替代,我们可以把这些值存储在语法分析树本身中。使用树注解方法时我们可以带有监听器或访问者,但在这里我们使用监听器来阐明如何使用它。让我们首先看一下用部分结果注解的1+2*3的LExpr语法分析树。

每个子表达式对应一个子树根(和对应一个e规则调用)。从e节点发出的水平线指向的数字是我们想要返回的部分结果。

让我们看看节点注解策略将如何工作在来自LExpr语法的规则e上。

1
2
3
4
e : e MULT e    # Mult
  | e ADD e     # Add
  | INT         # Int
  ;

e选项的监听器方法每个都会存储一个结果在相对应的e语法分析树节点中。任何随后的在语法分析树更高节点上的add或multiply事件将通过查看存储在它们对应的子节点中的值来抓取子表达式的值。

现在,让我们假设每个语法分析树节点(每个规则上下文对象)都有一个字段value,那么exitAdd()看起来将是这样;

1
2
3
4
public void exitAdd(LExprParser.AddContext ctx) {
    // e(0).value is the subexpression value of the first e in the alternative
    ctx.value = ctx.e(0).value + ctx.e(1).value;    // e '+' e # Add
}

这看起来相当合理,但不幸的是,在Java中我们不能扩展类ExprContext去动态地添加字段。为了让语法分析树注解生效,我们需要一种方法去注解各式各样的节点而不需要手工修改由ANTLR生成的关联节点类。

注解语法分析树节点最简单的方式是使用与节点任意值相关联的一个Map。因此,ANTLR提供了一个简单的帮助类ParseTreeProperty。让我们在文件TestLEvaluatorWithProps.java中构建称作EvaluatorWithProps的另一个计算器版本,它使用ParseTreeProperty关联了LExpr语法分析树节点和部分结果。以下是在监听器开始处的适当的定义:

1
2
3
public static class EvaluatorWithProps extends LExprBaseListener {
    /** maps nodes to integers with Map<ParseTree,Integer> */
    ParseTreeProperty<Integer> values = new ParseTreeProperty<Integer>();

注意:如果你想使用自己的Map类型字段代替ParseTreeProperty,确保它继承自IdentityHashMap,而不是通常的HashMap。我们需要去注解特殊的节点,进行同一性测试而不是equals()。两个e节点可能是equals(),但在内存中不是同一个物理节点。

为注解一个节点,我们使用values.put(node, value)。为得到和一个节点有关联的值,我们使用values.get(node)。这很好,但是让我们创建一些有直白名字的帮助方法以便让代码更容易阅读。

1
2
public void setValue(ParseTree node, int value) { values.put(node, value); }
public int getValue(ParseTree node) { return values.get(node); }

让我们从最简单的表达式选项Int开始监听器方法。我们想使用它匹配的INT记号的整型值去注解它的语法分析树e节点。

1
2
3
4
public void exitInt(LExprParser.IntContext ctx) {
    String intText = ctx.INT().getText();    // INT    # Int
    setValue(ctx, Integer.valueOf(intText));
}

对于加法树,我们得到两个子表达式子节点的值(运算元)和带有和的注释的子树跟。

1
2
3
4
5
public void exitAdd(LExprParser.AddContext ctx) {
    int left = getValue(ctx.e(0));    // e '+' e    # Add
    int right = getValue(ctx.e(1));
    setValue(ctx, left + right);
}

方法exitMult()是相同的,只是运算的时候用multiply代替了add。

我们的测试代码从分析规则s开始。因此我们必须确保语法分析树根有e子树的值。为把值从e节点冒泡到根s节点,我们实现了exitS()。

1
2
3
4
/** Need to pass e's value out of rule s : e ; */
public void exitS(LExprParser.SContext ctx) {
    setValue(ctx, getValue(ctx.e()));    // like: int s() { return e(); }
}

以下是如何启动监听器以及打印出来自语法分析树根节点的表达式的值:

1
2
3
4
ParseTreeWalker walker = new ParseTreeWalker();
EvaluatorWithProps evalProp = new EvaluatorWithProps();
walker.walk(evalProp, tree);
System.out.println("properties result = " + evalProp.getValue(tree));

以下是构建和测试序列:

1
2
3
antlr LExpr.g
compile *.java
run TestLEvaluatorWithProps

接着输入以下内容:

1
2
1+2*3
EOF

你就会看到如下结果:

1
2
(s (e (e 1) + (e (e 2) * (e 3))))
stack result = 7

现在我们已经看到了相同计算器的3个实现,并且我们也已经准备好把我们的知识用于构建真实案例。因为每个方法都有它的优势和劣势,下面就让我们来比较下不同的技术。

比较信息共享方法

为得到可复用和可重定目标的语法,我们需要让它们完全清除用户定义的动作。这意味着要把所有特定应用的代码放到语法外的某些监听器和访问者中。监听器和访问者操作语法分析树,ANTLR自动生成合适的树遍历接口和默认实现。因为事件方法签名是固定的和不特定于应用的,所以事件方法可以共享信息的方式有3种:

  • 本地Java调用栈:访问者返回用户定义类型的一个值。如果访问者需要传递参数,它也必须使用下面两种技术的一种。
  • 基于栈:一个栈字段模仿参数和返回值,像Java调用栈那样。
  • 注解者:一个Map字段使用有用的值注解节点。

所有这3种方法是和语法本身完全解耦的,并且很好地封装在专门的对象中。除此之外,它们也都有各自的优点和缺点。我们可以根据问题的需要和个人的喜好决定采取哪种方法。你甚至可以在同一个应用中使用多种方法。

访问者方法很好懂,因为它们直接调用其它访问者方法去获取部分结果,并且能像其它任何方法那样返回值。这也是它们的缺点,访问者方法必须显式地访问它们的子节点。而监听器就不需要。因为访问者有个通用的接口,所以它不能定义参数。访问者必须使用其它解决方案的一种去传递参数给它在子节点上调用的访问者方法。访问者的空间效率很好,因为它在任何时间仅需保留少数的部分结果。在树遍历后没有部分结果保留。当访问者方法可以返回值时,每个值必须是同种类型,不想其它的解决方案。

基于栈的解决方案可以模仿参数和返回带有一个栈的值,但在手动管理栈时有个断开的机会。这可能会发生,因为监听器方法不能直接调用彼此。作为程序员,我们必须确定推入栈中的在将来事件方法调用能适当地弹出。栈可以传递多个值和多个返回值。基于栈的解决方案也是空间有效的,因为它不会把任何东西固定到树上。在树遍历后所有的部分结果存储消失。

注解者通常可以作为默认解决方案采用,因为它允许你任意地提供信息给事件方法操作语法分析树中上上下下的节点。你也可以传递多个值,它们可以是任意类型。在许多情况下注解胜于使用带有短暂值的栈。在各种方法的数据传递准备间很少有断开的机会。比起在编程语言中说返回值,使用setValue(ctx, value)注解树不太直观,但是更通用。超过其它两种的这种方法的唯一缺点是在树遍历期间部分结果是保留的,因此它有较大的内存占用。

从另一方面来说,在某些应用中能够注解树正是我们需要的。应用需要在树上通过多遍,第一遍是很方便在树上计算和储存数据的。当语法分析树遍历器重新遍历树的时候第二遍然后就很容易访问数据。总的来说,树注解非常灵活,有一个可接受的内存负担。

Comments