Modify expressions, generated by Antlr?

Question

I would like to read expressions with Antlr4 and the perform some modifications on them.

For example, if grammar is arithmetic, I would modify expression, representing

2 * (3 + 1)

with

2 * 4

and then with

8

This is "calculation" or "simplification". To perform this thing I would create some tree structure and the first idea is to use the very same trees, created by Antlr.

Unfortunately, I don't see any setters for children.

How to accomplish? Should I really duplicate Antlr trees with my own ones for logic of expressions?

Answer 1

Solution

You shouldn't duplicate nor modify ANTRL trees. You should USE them by utilizing tree visitor and listener patterns.

The grammar

First we will prepare simple grammar for an arithmetic expression.

grammar expr;

WS : [ \t\r\n] -> skip;
INT : [0-9]+;

program
    : expr # baseExpr
    ;

expr
    : '(' expr ')'              # exprParentheses
    | left=expr '*' right=expr  # exprMul
    | left=expr '+' right=expr  # exprAdd
    | INT                       # exprINT
    ;

Evaluate expression

In order to evaluate an expression, we will traverse the parse tree to perform a calculation or to collect the result.

public class EvaluateExpr extends exprBaseVisitor<Integer> {
    @Override
    public Integer visitExprINT(exprParser.ExprINTContext ctx) {
        return Integer.valueOf(ctx.INT().getText());
    }

    @Override
    public Integer visitExprMul(exprParser.ExprMulContext ctx) {
        Integer left = visit(ctx.left);
        Integer right = visit(ctx.right);
        return left * right;
    }

    @Override
    public Integer visitExprAdd(exprParser.ExprAddContext ctx) {
        Integer left = visit(ctx.left);
        Integer right = visit(ctx.right);
        return left + right;
    }

    @Override
    public Integer visitExprParentheses(exprParser.ExprParenthesesContext ctx) {
        return visit(ctx.expr());
    }
}

Replace expression

In order to replace an expression with its evaluated form, we will use TokenStreamRewriter class. This tool allows for an easy substitution of tokens.

public class ReplaceExpr extends exprBaseListener {
    private TokenStreamRewriter rewriter;

    public ReplaceExpr(CommonTokenStream tokens) {
        rewriter = new TokenStreamRewriter(tokens);
    }

    @Override
    public void enterBaseExpr(exprParser.BaseExprContext ctx) {
        rewriter.replace(ctx.start, ctx.stop, new EvaluateExpr().visit(ctx));
    }

    public String getReplacedCode() {
        return rewriter.getText();
    }
}

Run the example

Now we need to perform evaluation and replacement of the expressions.

exprLexer lexer = new exprLexer(new ANTLRInputStream("2 * (3 + 1)"));
CommonTokenStream tokens = new CommonTokenStream(lexer);
exprParser parser = new exprParser(tokens);
ReplaceExpr replaceExpr = new ReplaceExpr(tokens);
ParseTreeWalker.DEFAULT.walk(replaceExpr, parser.program());
System.out.println("Replaced code: " + replaceExpr.getReplacedCode());

The parse tree or AST (abstract-syntax tree)

If you still need a modified parse tree you can parse the altered code again. If you would like to modify the tree structure, convert the parse tree to the AST (abstract-syntax tree), and work on the AST from the start.