Visitor/Listener code for a while loop in ANTLR 4

Question

So far i have searched the whole "The Definitive ANTLR 4 Reference" book as well as many sites for an answer to my question and i still can't find anything on the topic.

I am using ANTLR 4 to create a sub-set of the C language that does some basic functionality. What i have no idea about is how to implement a simple while loop in my Visitor class. So far i got this in my grammar:

grammar Expr;

prog:   stat+ ;

stat:   expr NEWLINE                # printExpr
    |   ID '=' expr NEWLINE         # assign
    |   loop NEWLINE                # whileLoop
    |   relational NEWLINE          # relat
    |   NEWLINE                     # blank 
    ;

expr:   expr op=('*'|'/') expr      # MulDiv
    |   expr op=('+'|'-') expr      # AddSub
    |   INT                         # int
    |   ID                          # id
    |   '(' expr ')'                # parens
    ;

relational:     expr op=(GREATER|LESS) expr     # GreaterEqual
          ;

loop:   'while' '('relational')' NEWLINE? '{'stat*'}'   #while
    ;

GREATER : '>' ;
LESS : '<' ;
MUL :   '*' ; // assigns token name to '*' used above in grammar
DIV :   '/' ;
ADD :   '+' ;
SUB :   '-' ;
ID  :   [a-zA-Z]+ ;      // match identifiers
INT :   [0-9]+ ;         // match integers
NEWLINE:'\r'? '\n' ;     // return newlines to parser (is end-statement signal)
WS  :   [ \t]+ -> skip ; // toss out whitespace

This way i could have multiple statements inside a while loop. My Visitor class looks like this:

public class EvalVisitor extends ExprBaseVisitor<Integer> {

/** "memory" for our calculator; variable/value pairs go here */
Map<String, Integer> memory;

public EvalVisitor() {
    memory = new HashMap<String, Integer>();
}

/** ID '=' expr NEWLINE */
@Override
public Integer visitAssign(ExprParser.AssignContext ctx) {      
    String id = ctx.ID().getText();  // id is left-hand side of '='
    int value = super.visit(ctx.expr());   // compute value of expression on right        
    memory.put(id, value);           // store it in our memory
    return value;
}

/** expr NEWLINE */
@Override
public Integer visitPrintExpr(ExprParser.PrintExprContext ctx) {
    Integer value = super.visit(ctx.expr()); // evaluate the expr child
    System.out.println(value);         // print the result
    return 0;                          // return dummy value
}

/** INT */
@Override
public Integer visitInt(ExprParser.IntContext ctx) {
    return Integer.valueOf(ctx.INT().getText());
}

/** ID */
@Override
public Integer visitId(ExprParser.IdContext ctx) {
    String id = ctx.ID().getText();
    if ( memory.containsKey(id) ) return memory.get(id);        
    return 0;
}

/** expr op=('*'|'/') expr */
@Override
public Integer visitMulDiv(ExprParser.MulDivContext ctx) {
    int left = super.visit(ctx.expr(0));  // get value of left subexpression
    int right = super.visit(ctx.expr(1)); // get value of right subexpression
    if ( ctx.op.getType() == ExprParser.MUL ) return left * right;
    return left / right; // must be DIV
}

/** expr op=('+'|'-') expr */
@Override
public Integer visitAddSub(ExprParser.AddSubContext ctx) {
    int left = super.visit(ctx.expr(0));  // get value of left subexpression
    int right = super.visit(ctx.expr(1)); // get value of right subexpression        
    if ( ctx.op.getType() == ExprParser.ADD ) return left + right;
    return left - right; // must be SUB

}

/** '(' expr ')' */
@Override
public Integer visitParens(ExprParser.ParensContext ctx) {
    return super.visit(ctx.expr()); // return child expr's value
}

@Override
public boolean visitGreaterEqual(GreaterEqualContext ctx) {
    int left = super.visit(ctx.expr(0));
    int right = super.visit(ctx.expr(1));

    if(ctx.op.getType() == ExprParser.GREATER) {
        return left > right;
    }
    else {
        return left < right;
    }

}

@Override
public Integer visitWhileLoop(WhileLoopContext ctx) {

    if(visit(ctx.getRuleContext())) {

    }

    return super.visitWhileLoop(ctx);
}

}

Most of the code in the visitor class i took from the book because i am just starting using ANTLR 4. I find it hard to believe that, aside from the grammar for the while loop, there is no mention of how to implement any visitors/listeners or actions for a simple While loop in the book written by Terence Parr. Can somebody help me with writing a Visitor/Listener Java code for a While loop?

Lullaby

Hi, this is more content from "Language Implementation Patterns": amazon.com/… – Midsection

@TheANTLRGuy I have that book and took a quick look at it to see if i could find how to implement a while loop and, sadly, it doesn't. – Lullaby

Have you looked at the pattern called tree-based interpreter? Page 230. it does not specifically do while loops I think, but it does Colin return which is much more complicated. It clearly shows how to move a virtual program counter through a tree. – Midsection

Answer 1

I find it hard to believe that, aside from the grammar for the while loop, there is no mention of how to implement any visitors/listeners or actions for a simple While loop in the book written by Terence Parr.

That is because the ANTLR reference is about ANTLR, which is about parsing, not about the stage after parsing.

You can't do this:

@Override
public boolean visitGreaterEqual(GreaterEqualContext ctx) {
    ...

You've already declared your visitor to return Integers, so that's what every rule should return. Either make a custom wrapper Value that encapsulates your language's values (numbers, string, booleans), or just return 0 when a relation expression is false:

@Override
public Integer visitGreaterEqual(ExprParser.GreaterEqualContext ctx) {
    int left = this.visit(ctx.expr(0));
    int right = this.visit(ctx.expr(1));

    if (ctx.op.getType() == ExprParser.GREATER) {
        return left > right ? 1 : 0; // 0 is false (all other values are true)
    }
    else {
        return left < right ? 1 : 0;
    }
}

Then you can write your while as follows:

@Override
public Integer visitWhile(ExprParser.WhileContext ctx) {

    // Evaluate the relational expression and continue the while
    // loop as long as it is true (does not equal zero).
    while (this.visit(ctx.relational()) != 0) {

        // Evaluate all statements inside the while loop.
        for (ExprParser.StatContext stat : ctx.stat()) {
            this.visit(stat);
        }
    }

    // 0 now also is false, so maybe return null instead which would be
    // some sort of VOID value (or make a proper Value class).
    return 0;
}

Note that the code above will fail when nesting while statements because the inner while would return 0 causing the outer while to stop looping. In such cases, you'd be better off creating a custom Value class and introduce some sort of Value.VOID instance that would not cause the loop to stop.

Running the following main method:

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

    String expression = "n = 1\n" +
            "while (n < 10) {\n" +
            "  n\n" +
            "  n = n + 1\n" +
            "}\n";
    ExprLexer lexer = new ExprLexer(new ANTLRInputStream(expression));
    ExprParser parser = new ExprParser(new CommonTokenStream(lexer));
    new EvalVisitor().visit(parser.prog());
}

would print:

1
2
3
4
5
6
7
8
9

Also have a look at this demo language that uses ANTLR4 and if and while statements, as well as a custom Value object: https://github.com/bkiers/Mu

Megargee

Thank you so very much Bart. Your solution works wonders! One question though - I am trying to wrap my head about what is being done in the visitor methods that makes all of this work. Take for example your implementation of the if statement: what you are doing is collecting all of the conditions + their blocks of code in a list. Then you check which of the conditions are true so that you can then visit the statement block corresponding to that specific condition - this is why you merged your condition + statement block, to easily locate the block that should be run. Am i correct? – Lullaby