ANTLR Grammar incomplete

Question

Using this grammar i could find the exponents but the answer I get is in reverse order (example : this is what i am getting : 2 ^ 2 ^ 3 = 64 this is what i am supposed to get : 2 ^ 2 ^ 3 = 2 ^ 8 = 256 ) )

grammar SDD1
;

options {
  language = Java;
}
// header for parser related java
@header {
  package com.compiler.tutorial;
}

// header for lexer related java
@lexer::header {
  package com.compiler.tutorial;

}

evaluator returns[int result]
  : expression EOF  {$result = $expression.result;}
  ;   

expression returns[int result]
    : op1=mult {$result = $op1.result;}  
    ( '+' op2=mult {$result = $result + $op2.result;}
    | '-' op2=mult {$result = $result - $op2.result;}
    )*
    ;

mult returns [int result]
  :  op1 = exponent {$result = $op1.result;}
  (  '*' op2=exponent  {$result = $result * $op2.result;}
  |  '/' op2=exponent  {$result = $result / $op2.result;}

  )*
   ;

 exponent returns [int result]
  :  op1=factor {$result = $op1.result;}
     ( '^' op2=factor {$result = (int) Math.pow( $result,$op2.result);}
     )*
  ;



factor returns [int result]
   :  NUMBER  {$result = Integer.parseInt($NUMBER.text); 
                System.out.println ("Number= " + $result);}|
      IDENT  {$result = 0;}|
      '(' expression ')' {$result = $expression.result;}
   ;


fragment LETTER: 'a'..'z' | 'A'..'Z';
fragment DIGIT: '0'..'9';
IDENT: LETTER( LETTER | DIGIT )*;
NUMBER: DIGIT+;
WS: (' ' | '\t' | '\n' | '\r' | '\f')+ {$channel=HIDDEN;};

2^2^3 = 64 is itself correct if you evaluate like (2^2)^3 = 64..........perhaps this is because your grammar is not exactly recursive as it should be (the right most expression should be evaluated first???) — Umer

vldmrrdjcc vldmrrdjcc · Accepted Answer · 2011-12-11T23:09:22

Your problem is that ^ operator is right associative. And with your current grammar it is defined like left associative. Operators like + , - or * are left associative which is naturally expressed in ANTLR grammar. To express right associativity you need recursive rule. I altered you grammar without touching your actions inside curly braces so it gives the correct parse tree:

grammar SDD1
;

options {
  language = Java;
}
// header for parser related java
@header {
  package com.compiler.tutorial;
}

// header for lexer related java
@lexer::header {
  package com.compiler.tutorial;

}

evaluator returns[int result]
  : expression EOF  {$result = $expression.result;}
  ;   

expression returns[int result]
    : op1=mult {$result = $op1.result;}  
    ( '+' op2=mult {$result = $result + $op2.result;}
    | '-' op2=mult {$result = $result - $op2.result;}
    )*
    ;

mult returns [int result]
  :  op1 = exponent {$result = $op1.result;}
  (  '*' op2=exponent  {$result = $result * $op2.result;}
  |  '/' op2=exponent  {$result = $result / $op2.result;}

  )*
   ;

 exponent returns [int result]
  : atom ('^' exponent)?
  ;



atom returns [int result]
   :  NUMBER  {$result = Integer.parseInt($NUMBER.text); 
                System.out.println ("Number= " + $result);}|
      IDENT  {$result = 0;}|
      '(' expression ')' {$result = $expression.result;}
   ;



fragment LETTER: 'a'..'z' | 'A'..'Z';
fragment DIGIT: '0'..'9';
IDENT: LETTER( LETTER | DIGIT )*;
NUMBER: DIGIT+;
WS: (' ' | '\t' | '\n' | '\r' | '\f')+ {$channel=HIDDEN;};

(Notice that the key rule that I added:

 exponent returns [int result]
  : atom ('^' exponent)?
  ;

doesn't have * behind the right brace, but ?)

So for the input:

2^3^4^5

you get the following parse tree:

enter image description here

ANTLR Grammar incomplete

2 Answers