Antlr - Expression parser and evaluator

Question

I am required to write a boolean expression parser/evaluator. The expressions would be of the form and would be enclosed in parenthesis :

exp1 : (A = B)
exp2 : ((A = B) AND (C = D))
exp3 : ((A = B) AND ((C = D) OR (E = F)))
exp4: (((A = B) AND (C = D)) OR (E = F))

and it goes on. The rule may contain 'n' number of expressions with proper grouping 2 in each group. My grammar file looks like this:

/*
Expression grammar
 */

grammar Exparser;

options

{
    language = Java;
}
cond    :   
tc EOF;

tc:
      exp
  | binary_exp
| leftparen* exp ( binaryop leftparen* exp rightparen+)*
| leftparen* exp ( binaryop leftparen* exp rightparen*)*

;

binary_exp:
 '(' exp BINARYOP exp ')'
;

binaryop:
            BINARYOP
        ;
leftparen:
             LEFTPARN
         ;

rightparen:
              RIGHTPARN
          ;

exp:
LEFTPARN VARIABLE COMPOP VARIABLE RIGHTPARN

;

variable:
            VARIABLE;


BINARYOP: AND | OR;
COMPOP: EQUAL | LT | GT | LTE | GTE | NE;
VARIABLE: (CHAR)+;
LEFTPARN: '(';
RIGHTPARN: ')';
EQUAL: '=' | 'EQ';
LT: '<' | 'LT';

GT:'>' | 'GT';
LTE: '<=';
GTE: '>=';
NE  :   '!=' | 'NE';
AND: 'AND' | '&' | 'and';

OR: 'OR' | 'or';

CHAR  :   'a'..'z'|'A'..'Z'|'_' |'0'..'9'|'-' | '.'
   ;

this grammar works fine, but I am not able to achieve the depth in the AST. for example exp3 is parsed as three exp and not as one exp and one binary_exp. Also how do I evaluate a boolean expression using my parser? How does my grammar enforce balancing of parenthesis? Though Nested Boolean Expression Parser using ANTLR give some idea for evaluating an expression, I am not able to apply in my case

score 1 · Accepted Answer · edited May 23 '17 at 12:33

1

The parser generated from the following grammar parses all your example input:

grammar Exparser;

parse
 : expr EOF
 ;

expr
 : expr binop expr
 | VARIABLE
 | '(' expr ')'
 ;

binop
 : AND | OR | EQUAL | LT | GT | LTE | GTE | NE
 ;

EQUAL     : '=' | 'EQ';
LT        : '<' | 'LT';
GT        : '>' | 'GT';
LTE       : '<=';
GTE       : '>=';
NE        : '!=' | 'NE';
AND       : 'AND' | '&' | 'and';
OR        : 'OR' | 'or';
VARIABLE  : [a-zA-Z0-9_.-]+;
SPACE     : [ \t\r\n] -> skip;

Evaluating these expressions should be the same as the Q&A you linked to in your question.

edited May 23 '17 at 12:33

Community

1
1

answered Sep 23 '16 at 20:43

Bart Kiers

166,582
36
299
288

Thanks Bart . I could get my tree structure when I ran this on antlrworks 2. I am yet to work on the evaluation part. – ssdimmanuel Sep 24 '16 at 17:40
The grammar worked like a charm. I made simple modifications to suit my needs. For me the expressions in my applications are fairly static once defined. I was thinking to write the parse tree to disk but found that it's not possible since the classes are not Serializable. Is there any other proven method to do this ? – ssdimmanuel Oct 03 '16 at 02:56
I've not yet looked into serializing/persisting ANTLR 4 classes. – Bart Kiers Oct 05 '16 at 15:34
Thank you so much Bart. For a beginner in ANTLR like me, your answer helped a lot. I found an another way to store the parse tree. Convert the AST to an xml using the ANTLR generated listener and store it to disk. When I evaluate the rule next time, I read the xml file and walk thru the nodes using a xml tree walker to evaluate the expression – ssdimmanuel Oct 07 '16 at 03:48

score 0 · Answer 2 · answered Sep 23 '16 at 19:04

Caveat: I don't know antlr. However, I think you need to make your grammar more explicit. You are overloading exp too much. Try something like this pseudocode:

tc <- binary_exp ;
binary_exp <- comparison_exp
            | LEFTPARN binary_exp RIGHTPARN
            | LEFTPARN binary_exp BINARYOP binary_exp RIGHTPARN ;
comparison_exp <- LEFTPARN VARIABLE COMPOP VARIABLE RIGHTPARN ;

Every tc is a binary expression binary_exp.
A binary expression is one of:
- a comparison expression comparison_exp,
- a binary expression surrounded by parentheses (LEFTPARN and RIGHTPARN),
- or a sequence of left-parenthesis LEFTPARN, a binary_exp, a binary operator BINARYOP, a binary_exp, and a right-parenthesis RIGHTPARN.
a comparison expression is a sequence of left-parenthesis LEFTPARN, a variable VARIABLE, a comparison operator COMPOP, a VARIABLE, and a right-parenthesis RIGHTPARN.

This grammar would allow binary expressions to be nested inside extra parentheses or nested inside one another, but comparison expressions cannot have other expressions nested inside them.

Antlr - Expression parser and evaluator

2 Answers2