title: Nested Boolean Expression Parser using ANTLR
body: <p>I'm trying to parse a Nested Boolean Expression and get the individual conditions within the expression separately. For e.g., if the input string is:</p>
  
  <p>(A = a OR B = b OR C = c AND ((D = d AND E = e) OR (F = f AND G = g)))</p>
  
  <p>I would like to get the conditions with the correct order. i.e.,</p>
  
  <p>D =d AND E = e
  OR
  F = f AND G = g
  AND
  A = a OR B = b OR C = c</p>
  
  <p>I'm using ANTLR 4 to parse the input text and here's my grammar:</p>
  
  <pre><code>grammar SimpleBoolean;
  
  rule_set : nestedCondition* EOF;
  
  AND : 'AND' ;
  OR  : 'OR' ;
  NOT : 'NOT';
  
  TRUE  : 'TRUE' ;
  FALSE : 'FALSE' ;
  
  GT : '&gt;' ;
  GE : '&gt;=' ;
  LT : '&lt;' ;
  LE : '&lt;=' ;
  EQ : '=' ;
  
  LPAREN : '(' ;
  RPAREN : ')' ;
  
  DECIMAL : '-'?[0-9]+('.'[0-9]+)? ;
  
  IDENTIFIER : [a-zA-Z_][a-zA-Z_0-9]* ;
  
  WS : [ \r\t\u000C\n]+ -&gt; skip;
  
  nestedCondition : LPAREN condition+ RPAREN (binary nestedCondition)*;
  condition: predicate (binary predicate)*
              | predicate (binary component)*;
  component: predicate | multiAttrComp;
  multiAttrComp : LPAREN predicate (and predicate)+ RPAREN;
  predicate : IDENTIFIER comparator IDENTIFIER;
  comparator : GT | GE | LT | LE | EQ ;
  binary: AND | OR ;
  unary: NOT;
  and: AND;
  </code></pre>
  
  <p>And here's the Java Code that I'm using to parse it:</p>
  
  <pre><code>ANTLRInputStream inputStr = new ANTLRInputStream(input);
  SimpleBooleanLexer lexer = new SimpleBooleanLexer(inputStr);
  TokenStream tokens = new CommonTokenStream(lexer);
  SimpleBooleanParser parser = new SimpleBooleanParser(tokens);
  parser.getBuildParseTree();
  ParseTree tree = parser.rule_set();
  System.out.println(tree.toStringTree(parser));
  </code></pre>
  
  <p>The output is:</p>
  
  <pre><code>(rule_set (nestedCondition ( (condition (predicate A (comparator =) a) (binary OR) (component (predicate B (comparator =) b)) (binary OR) (component (predicate C (comparator =) c)) (binary AND) (component (multiAttrComp ( (predicate ( D (comparator =) d) (and AND) (predicate E (comparator =) e) ))) (binary OR) (component (multiAttrComp ( (predicate F (comparator =) f) (and AND) (predicate G (comparator =) g) )))) ) )) &lt;EOF&gt;)
  </code></pre>
  
  <p>I'm looking for help on how to parse this tree to get the conditions in the correct order? In ANTLR 3, we could specify ^ and ! to decide how the tree is built(refer this <a href="https://stackoverflow.com/questions/4931346/how-to-output-the-ast-built-using-antlr">thread</a>), but I learnt that this is not supported in ANTLR 4. </p>
  
  <p>Can someone suggest how I can parse the String in the correct order in Java using the ParseTree created by ANTLR?</p>