ANTLR Grammar for Expressions

Question

I am trying to implement an expression processing grammar (which concerns nested brackets, etc.). I have the following so far, but they cannot deal with some cases (successful / unsuccessful cases appear after the next block of code). Does anyone know what is going on?

Note. The varname + = and varname = data are just additional supporting material for the AST generation in XText. Do not worry about them now.

... NilExpression returns Expression: 'nil'; FalseExpression returns Expression: 'false'; TrueExpression returns Expression: 'true'; NumberExpression returns Expression: value=Number; StringExpression returns Expression: value=STRING; //EllipsesExpression: '...'; //FunctionExpression: function=function; //don't allow random functions UnaryExpression: op=unop ('(' expr=Expression ')')|expr=Expression; BinaryExpression: 'or'? AndOp; //or op AndOp: 'and'? ComparisonOp; ComparisonOp: ('>'|'<'|'>='|'<='|'=='|'~=')? ConcatOp; ConcatOp: '..'? AddSubOp; AddSubOp: ('+' '-')? MultDivOp; MultDivOp: ('*' '/')? ExpOp; ExpOp: '^'? (('(' expr=Expression ')')|expr=Expression); ExprSideOne : Variable|NilExpression|FalseExpression|TrueExpression| NumberExpression|StringExpression|UnaryExpression; Expression: ( '(' expression1=ExprSideOne expression2+=BinaryExpression* ')' ) | ( expression1=ExprSideOne expression2+=BinaryExpression* ) ; ... 

And here is a list of parses / failures:

 c = ((b)); //fails c = ((a not b)); //fails c = b; //parses d = (b); //parses 

Answer 1

What happens is that your expressions / expressions support single parentheses, but not multiple parentheses (as you concluded). I have no specific ANTLR experience, but I worked with Javacc, which shares a lot of similar concepts (I wrote a grammar for Prolog ... I don't ask).

To handle nested parentheses, you usually have something similar to:

 ParenthesisExpression: '(' (ParenthesisExpression | Expression) ')'; 

This would mean that the expression is either wrapped in parentheses or just a raw expression. As for how AST handles this, ParenthesisExpression is an “expression”, so it can be represented as a subclass or implementation (if the expression is an interface / abstract class).

Answer 2

I used this grammar for simple expressions: http://fisheye2.atlassian.com/browse/~raw,r=5175/antlr-examples/C/polydiff/Poly.g

I also used grammar in this project for more complex expressions: http://www.codeproject.com/KB/recipes/sota_expression_evaluator.aspx

Answer 3

Using ^ placed after the token / rule name is very useful for defining expressions.

  expression : e1 (OR^ e1)* ; e1 : e2 (AND^ e2)*; e2 : e3 (PIPE^ e3)*; e3 : e4 (ANDSYMB^ e4)*; e4 : e5 ((EQUAL^|NOTEQUAL^) e5)*; e5 : e6 ((LESS^|GREATER^) e6)*; e6 : e7 ((PLUS^|MINUS^) e7)* ; e7 : e8 ((STAR^|SLASH^) e8)* ; e8 : e9 (NEW^ ID LPAREN RPAREN)*; e9 : (NOT^)? e10; e10 : e11 | call_def; e11 : constant | '(' expression ')' -> expression;