ANTLR 4 tree inject/rewrite operator

Question

In ANTLR 3 you could just do the following:

    andExpression
  :  (andnotExpression        -> andnotExpression)
     (AND? a=andnotExpression -> ^(AndNode $andExpression $a))* 
  ;

Any idea how to do it in the new version?

Boeschen

Answer 1

As mentioned by Sam (280Z28), ANTLR 4 does not have rewrite operators.

When generating the parser, ANTLR 4 creates some listener classes that you can use to listen for "enter" and "exit" events of all parser rules.

Also, ANTLR 4 supports "direct left recursive rules", so your expression rules can be defined in a single rule as demonstrated below:

grammar Expr;

parse
 : expression EOF
 ;

expression
 : '(' expression ')'
 | IDENTIFIER
 | NOT expression
 | expression AND? expression
 | expression OR expression
 ;

LPAREN     : '(';
RPAREN     : ')';
NOT        : 'NOT';
AND        : 'AND';
OR         : 'OR';
IDENTIFIER : [a-zA-Z_] [a-zA-Z_0-9]*;
SPACE      : [ \t\r\n]+ -> skip;

When parsing the input "a b OR NOT c AND d", the following parse tree will be created:

(image created using ANTLRWorks2, thank you Sam! Very impressive IDE, I love it!)

Generate the parser and listener classes:

java -cp antlr-4.0-complete.jar org.antlr.v4.Tool Expr.g4

and the following class is generated that will let you help "walk" the tree:

public class ExprBaseListener implements ExprListener {

    @Override public void enterExpression(ExprParser.ExpressionContext ctx) { }
    @Override public void exitExpression(ExprParser.ExpressionContext ctx) { }

    @Override public void enterParse(ExprParser.ParseContext ctx) { }
    @Override public void exitParse(ExprParser.ParseContext ctx) { }

    @Override public void enterEveryRule(ParserRuleContext<Token> ctx) { }
    @Override public void exitEveryRule(ParserRuleContext<Token> ctx) { }
    @Override public void visitTerminal(TerminalNode<Token> node) { }
    @Override public void visitErrorNode(ErrorNode<Token> node) { }
}

Now you'll need to inspect the ExprParser.ExpressionContext to see which of the alternatives in expression is matched, which is where "tree-labels" come in handy. Change the expression rule as follows:

expression
 : '(' expression ')'           # EXPR
 | IDENTIFIER                   # ID_EXPR
 | 'NOT' expression             # NOT_EXPR
 | expression 'AND'? expression # AND_EXPR
 | expression 'OR' expression   # OR_EXPR
 ;

and regenerate the parser and listeners, and you'll see that ExprBaseListener now looks like this:

public class ExprBaseListener implements ExprListener {
    @Override public void enterAND_EXPR(ExprParser.AND_EXPRContext ctx) { }
    @Override public void exitAND_EXPR(ExprParser.AND_EXPRContext ctx) { }

    @Override public void enterOR_EXPR(ExprParser.OR_EXPRContext ctx) { }
    @Override public void exitOR_EXPR(ExprParser.OR_EXPRContext ctx) { }

    @Override public void enterEXPR(ExprParser.EXPRContext ctx) { }
    @Override public void exitEXPR(ExprParser.EXPRContext ctx) { }

    @Override public void enterNOT_EXPR(ExprParser.NOT_EXPRContext ctx) { }
    @Override public void exitNOT_EXPR(ExprParser.NOT_EXPRContext ctx) { }

    @Override public void enterID_EXPR(ExprParser.ID_EXPRContext ctx) { }
    @Override public void exitID_EXPR(ExprParser.ID_EXPRContext ctx) { }

    @Override public void enterParse(ExprParser.ParseContext ctx) { }
    @Override public void exitParse(ExprParser.ParseContext ctx) { }

    @Override public void enterEveryRule(ParserRuleContext ctx) { }
    @Override public void exitEveryRule(ParserRuleContext ctx) { }
    @Override public void visitTerminal(TerminalNode node) { }
    @Override public void visitErrorNode(ErrorNode node) { }
}

I.e., for each label in expression a separate enter- and exit-method is created.

Now, let's say you're only interested in enter-events of the AND expression. You could create a custom class that extends this ExprBaseListener and override enterAND_EXPR:

public class ExprWalker extends ExprBaseListener {

    @Override 
    public void enterAND_EXPR(ExprParser.AND_EXPRContext ctx) { 
        java.util.List<ExprParser.ExpressionContext> e = ctx.expression();
        System.out.println("AND -> " + e.get(0).getText() + ", " + e.get(1).getText());
    }
}

To test this all, create a small driver class:

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

public class Main {

    public static void main(String[] args) throws Exception {

        String input = "a b OR NOT c AND d";
        ExprLexer lexer = new ExprLexer(new ANTLRInputStream(input));
        ExprParser parser = new ExprParser(new CommonTokenStream(lexer));
        ParseTree tree = parser.parse();
        ParseTreeWalker walker = new ParseTreeWalker();
        walker.walk(new ExprWalker(), tree);
    }
}

and run it:

java -cp antlr-4.0-complete.jar org.antlr.v4.Tool Expr.g4
javac -cp antlr-4.0-complete.jar *.java
java -cp .:antlr-4.0-complete.jar Main

after which you'll see the following being printed to your console:

AND -> a, bORNOTcANDd
AND -> NOTc, d

Goofball

Answer 2

ANTLR 4 does not have a rewrite operator or an output=AST option like ANTLR 3. Trees produced by ANTLR 4 parsers are parse trees, the shape of which is implicitly defined by the grammar rules.

Hanker

Thank you the answer does it mean that I have to rewrite it like andExpr: andExpr ? (AND? andnotExpression) ? – Boeschen

Hy Sam! Is this still valid? Is there still no rewriting of the parse tree? The ANTLR grammar rule on github (github.com/antlr/antlr4/blob/master/tool/src/org/antlr/v4/parse/…) states that the grammar contains "rewrite" within it's text... Has that been left over from v3? – Pigling

The grammar from the link above is just a v3 grammar. So to answer the (rather old) question above: yes, it is still valid. ANTLR v4 does not have tree rewriting (nor is it likely it ever will). – Goofball