pattern-matching - Antlr 树模式匹配与重写规则

Question

对于像 a.b.c + d.e.f 这样的表达式，我有一个简单的 antlr 语法。 :

grammar Test;
options {
    output=AST;
}
tokens {
    VARIABLE_ID;
    QUALIFIER_ID;
}

ID  : ('a'..'z'|'A'..'Z'|'_') ('a'..'z'|'A'..'Z'|'0'..'9'|'_')*;
DOT : '.';
WS : ( ' ' | '\t' | '\r' | '\n' ) {$channel=HIDDEN;} ;

variable_id  : id=ID   -> VARIABLE_ID[$id];
qualifier_id  : id=ID   -> QUALIFIER_ID[$id];

expr_start : expr EOF;
expr : var (options {greedy=true;} : '+' expr)*;

var : variable_id (DOT qualifier_id)*;

现在我想在这个语法上定义一个模式匹配器，它变成 a.b.c进入 0.1.2 ，所以我定义了一个树模式匹配器如下

tree grammar TestWalker;
options {
    tokenVocab=Test;
    ASTLabelType=CommonTree;
    filter=true;
    backtrack=true;
}

@members {
    TokenRewriteStream tokens;

    public void setTreeNodeStream(TreeNodeStream input) {
        super.setTreeNodeStream(input);
        tokens = (TokenRewriteStream)input.getTokenStream(); 
    }
}

topdown : var;

variable_id [int i] : id=VARIABLE_ID {
    tokens.replace($id.getToken(), "" + $i);
};

qualifier_id [int i] : id=QUALIFIER_ID {
    tokens.replace($id.getToken(), "" + $i);
};

var 
@init { int index = 0; }
: variable_id[index] 
(   DOT 
    { ++index; }
    qualifier_id[index]
)*;

然后我整理了一个小测试程序:

import org.antlr.runtime.*;
import org.antlr.runtime.tree.*;

public class Main {
    public static void main(String[] args) throws Exception {
        TestLexer lex = new TestLexer(new ANTLRInputStream(System.in));
        TokenStream tokens = new TokenRewriteStream(lex);

        TestParser parser = new TestParser(tokens);
        TestParser.expr_return expr = parser.expr();

        CommonTreeNodeStream nodes = new CommonTreeNodeStream((Tree)expr.getTree());
        nodes.setTokenStream(tokens);
        TestWalker walker = new TestWalker(nodes);
        walker.downup(expr.getTree());
        System.out.println(tokens.toString());
    }
}

当我使用基本输入运行这个程序时，我看到了令人惊讶的结果: a.b.c -> 0.b.c a.b + d.e -> 0.b + 0.e等等。看来 (DOT qualifier_id)*我的规则的一部分从不匹配，我不知道为什么。我曾尝试将我的规则添加到树模式匹配的自上而下和自下而上的部分。如果我从过滤器匹配器切换到整个树匹配器并为 '+' 添加规则分支在适当的情况下它可以工作，但是当重写只是更大语法的一小部分时，这变得站不住脚。任何指针将不胜感激。

更新:使用 antlr 3.3

Answer 1

问题的关键(由@Bart 确定)是解析未正确生成 AST。语法需要构建 AST(注意附加的 ^ 标记)。

grammar Test;
options {
    output=AST;
}
tokens {
    VARIABLE_ID;
    QUALIFIER_ID;
}

ID  : ('a'..'z'|'A'..'Z'|'_') ('a'..'z'|'A'..'Z'|'0'..'9'|'_')*;
DOT : '.';
WS : ( ' ' | '\t' | '\r' | '\n' ) {$channel=HIDDEN;} ;

variable_id  : id=ID   -> VARIABLE_ID[$id];
qualifier_id  : id=ID   -> QUALIFIER_ID[$id];

expr_start : expr EOF;
expr : var (options {greedy=true;} : '+'^ expr)*;

var : variable_id (DOT^ qualifier_id)*;

然后，树模式匹配器需要在构造 AST 时遍历 AST。注意 expr 规则的结构和用于处理状态的参数。

tree grammar TestWalker;
options {
    tokenVocab=Test;
    ASTLabelType=CommonTree;
    filter=true;
    backtrack=true;
}

@members {
    TokenRewriteStream tokens;

    public void setTreeNodeStream(TreeNodeStream input) {
        super.setTreeNodeStream(input);
        tokens = (TokenRewriteStream)input.getTokenStream(); 
    }
}

topdown : expr[0];

variable_id returns [int r] : id=VARIABLE_ID {
    $r = 0;
    tokens.replace($id.getToken(), "" + $r);
};

qualifier_id [int i] returns [int r] : id=QUALIFIER_ID {
    $r = $i + 1;
    tokens.replace($id.getToken(), "" + $r);
};

expr [int i] returns [int r]
    : v=variable_id { $r = $v.r; }
    | ^(DOT e=expr[$i] q=qualifier_id[$e.r] { $r = $q.r; } )
    ;

现在输出将按预期运行: a.b + d.e + c.d.e.f 0.1 + 0.1 + 0.1.2.3并且生成的 AST 看起来是正确的。