if then else conditional evaluation

Question

I have a language which basically is meant to map columns to a new structure in an array. The language is meant for product managers to define mappings without having to know a lot of programming details. I'm sure there is a lot more to improve here but this is what I have.

The language works, mostly. The problem I have is with conditional statements.

My parser has the following rule:

conditionalexpr :  IF^ LPAREN! (statement) RPAREN! THEN! LCURLY! statement RCURLY! (ELSE! LCURLY! statement RCURLY!)?;

Which works to generate a tree with three children.

My problem is to avoid evaluating the statements if the condition doesn't allow it.

Very naively I did:

conditionalexpr returns[Object o]: 
  ^(IF a=statement b=statement (c=statement)?)
  {
    $o = (Boolean)$a.o ? $b.o : $c.o != null ? $c.o : "";
  }
  ;

Obviously this will not work.

I have been playing around with syntactic predicates but I can't make those work properly.

statement returns an object currently. Mostly the language deals in Strings but I need to support booleans and numbers (integer and decimal) as well.

If I add anything like {$a.o}?=> I get a $a in the generated code.

I have looked on the antlr-interest list but this question is not really answered well there, most likely because it seems obvious to them.

I am willing to post the complete grammar but have left it out to keep this short.

Idalia

Answer 1

If you don't want certain sub-trees to be evaluated, you'll need to let the tree rules return nodes instead of actual values. You can either extend CommonTree and provide a custom TreeAdaptor to help build your own nodes, but personally, I find it easiest to create a custom node class (or classes) and use them instead. A demo to clarify:

T.g

grammar T;

options {
  output=AST;
}

tokens {
  ASSIGNMENT;
}

parse
  :  statement+ EOF -> statement+
  ;

statement
  :  ifStatement
  |  assignment
  ;

ifStatement
  :  IF a=expression THEN b=expression (ELSE c=expression)? -> ^(IF $a $b $c?)
  ;

assignment
  :  ID '=' expression -> ^(ASSIGNMENT ID expression)
  ;

expression
  :  orExpression
  ;

orExpression
  :  andExpression (OR^ andExpression)*
  ;

andExpression
  :  equalityExpression (AND^ equalityExpression)*
  ;

equalityExpression
  :  relationalExpression (('==' | '!=')^ relationalExpression)*
  ;

relationalExpression
  :  atom (('<=' | '<' | '>=' | '>')^ atom)*
  ;

atom
  :  BOOLEAN
  |  NUMBER
  |  ID
  |  '(' expression ')' -> expression
  ;

IF      : 'if';
THEN    : 'then';
ELSE    : 'else';
OR      : 'or';
AND     : 'and';
BOOLEAN : 'true' | 'false';
ID      : ('a'..'z' | 'A'..'Z')+;
NUMBER  : '0'..'9'+ ('.' '0'..'9'+)?;
SPACE   : (' ' | '\t' | '\r' | '\n') {skip();};

Main.java

I've created a Node interface that has a eval(): Object method, and also created an abstract class BinaryNode which implements Node and will have always 2 children. As you can see in the tree grammar that follows after these Java classes, all rule now return a Node.

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

public class Main {
  public static void main(String[] args) throws Exception {
    String source = "a = 3   b = 4   if b > a then b==b else c==c";
    TLexer lexer = new TLexer(new ANTLRStringStream(source));
    TParser parser = new TParser(new CommonTokenStream(lexer));
    TWalker walker = new TWalker(new CommonTreeNodeStream(parser.parse().getTree()));
    Node root = walker.walk();
    System.out.println(root.eval());
  }
}

interface Node {
  Object eval();
}

abstract class BinaryNode implements Node {

  protected Node left;
  protected Node right;

  public BinaryNode(Node l, Node r) {
    left = l;
    right = r;
  }
}

class AtomNode implements Node {

  private Object value;

  public AtomNode(Object v) {
    value = v;
  }

  @Override
  public Object eval() {
    return value;
  }
}

class OrNode extends BinaryNode {

  public OrNode(Node left, Node right) { super(left, right); }

  @Override
  public Object eval() {
    return (Boolean)super.left.eval() || (Boolean)super.right.eval();
  }
}

class AndNode extends BinaryNode {

  public AndNode(Node left, Node right) { super(left, right); }

  @Override
  public Object eval() {
    return (Boolean)super.left.eval() && (Boolean)super.right.eval();
  }
}

class LTNode extends BinaryNode {

  public LTNode(Node left, Node right) { super(left, right); }

  @Override
  public Object eval() {
    return (Double)super.left.eval() < (Double)super.right.eval();
  }
}

class LTEqNode extends BinaryNode {

  public LTEqNode(Node left, Node right) { super(left, right); }

  @Override
  public Object eval() {
    return (Double)super.left.eval() <= (Double)super.right.eval();
  }
}

class GTNode extends BinaryNode {

  public GTNode(Node left, Node right) { super(left, right); }

  @Override
  public Object eval() {
    return (Double)super.left.eval() > (Double)super.right.eval();
  }
}

class GTEqNode extends BinaryNode {

  public GTEqNode(Node left, Node right) { super(left, right); }

  @Override
  public Object eval() {
    return (Double)super.left.eval() >= (Double)super.right.eval();
  }
}

class EqNode extends BinaryNode {

  public EqNode(Node left, Node right) { super(left, right); }

  @Override
  public Object eval() {
    return super.left.eval().equals(super.right.eval());
  }
}

class NEqNode extends BinaryNode {

  public NEqNode(Node left, Node right) { super(left, right); }

  @Override
  public Object eval() {
    return !super.left.eval().equals(super.right.eval());
  }
}

class VarNode implements Node {

  private java.util.Map<String, Object> memory;
  private String var;

  VarNode(java.util.Map<String, Object> m, String v) {
    memory = m;
    var = v;
  }

  @Override
  public Object eval() {
    Object value = memory.get(var);
    if(value == null) {
      throw new RuntimeException("Unknown variable: " + var);
    }
    return value;
  }
}

class IfNode implements Node {

  private Node test;
  private Node ifTrue;
  private Node ifFalse;

  public IfNode(Node a, Node b, Node c) {
    test = a;
    ifTrue = b;
    ifFalse = c;
  }

  @Override
  public Object eval() {
    return (Boolean)test.eval() ? ifTrue.eval() : ifFalse.eval();
  }
}

TWalker.g

tree grammar TWalker;

options {
  tokenVocab=T;
  ASTLabelType=CommonTree;
}

@members {
  private java.util.Map<String, Object> memory = new java.util.HashMap<String, Object>();
}

walk returns [Node n]
  :  (statement {$n = $statement.n;})+
  ;

statement returns [Node n]
  :  ifStatement {$n = $ifStatement.n;}
  |  assignment  {$n = null;}
  ;

assignment
  :  ^(ASSIGNMENT ID expression) {memory.put($ID.text, $expression.n.eval());}
  ;

ifStatement returns [Node n]
  :  ^(IF a=expression b=expression c=expression?) {$n = new IfNode($a.n, $b.n, $c.n);}
  ;

expression returns [Node n]
  :  ^(OR a=expression b=expression)   {$n = new OrNode($a.n, $b.n);}
  |  ^(AND a=expression b=expression)  {$n = new AndNode($a.n, $b.n);}
  |  ^('==' a=expression b=expression) {$n = new EqNode($a.n, $b.n);}
  |  ^('!=' a=expression b=expression) {$n = new NEqNode($a.n, $b.n);}
  |  ^('<=' a=expression b=expression) {$n = new LTEqNode($a.n, $b.n);}
  |  ^('<' a=expression b=expression)  {$n = new LTNode($a.n, $b.n);}
  |  ^('>=' a=expression b=expression) {$n = new GTEqNode($a.n, $b.n);}
  |  ^('>' a=expression b=expression)  {$n = new GTNode($a.n, $b.n);}
  |  BOOLEAN                           {$n = new AtomNode(Boolean.valueOf($BOOLEAN.text));}
  |  NUMBER                            {$n = new AtomNode(Double.valueOf($NUMBER.text));}
  |  ID                                {$n = new VarNode(memory, $ID.text);}
  ;

---

If you now run the main class, and evaluate:

a = 3   
b = 4   
if b > a then 
  b==b 
else 
  c==c

true is being printed to the console:

bart@hades:~/Programming/ANTLR/Demos/T$ java -cp antlr-3.3.jar org.antlr.Tool T.g
bart@hades:~/Programming/ANTLR/Demos/T$ java -cp antlr-3.3.jar org.antlr.Tool TWalker.g
bart@hades:~/Programming/ANTLR/Demos/T$ javac -cp antlr-3.3.jar *.java
bart@hades:~/Programming/ANTLR/Demos/T$ java -cp .:antlr-3.3.jar Main
true

But if you check if b < a, causing the else to be executed, you'll see the following:

Exception in thread "main" java.lang.RuntimeException: Unknown variable: c
        at VarNode.eval(Main.java:140)
        at EqNode.eval(Main.java:112)
        at IfNode.eval(Main.java:160)
        at Main.main(Main.java:11)

For implementations of more complicated language constructs (scopes, functions, etc.), see my blog.

Good luck!

Papua

The reason it won't work is that this means that both the then and the (optional) else clause will be evaluated. This can lead to undesirable consequences. That code should only be evaluated if necessary not in all cases. – Idalia

OK, its been busy at work so it took a while to get back to this, but the answer looks very nice. Thanks for your help – Idalia