CODEWITHSUNDEEP
antlr
gooner4
gooner4

Reputation: 33

ANTLR Grammar incomplete

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;};

Upvotes: 1

Views: 1380

Answers (2)

vldmrrdjcc
vldmrrdjcc

Reputation: 2112

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

Upvotes: 3

paxdiablo
paxdiablo

Reputation: 881423

For starters, 2(23) is 256, not 512 - there is no (non-bizarre) associativity that will give you a 512 from that expression :-)

But, if you want right-to-left associativity for your exponential operator, you'll need to modify the exponent rule to make it greedy. In other words, allow it to take an exponent as a secondary operand (in preference) rather than just a factor as it currently stands.

That way, 2^2^3 will indeed evaluate as 2(23) rather than (22)3.

Apologies, I don't know exactly how to achieve that with ANTLR, I'm showing my age here but I'm very much a lex/yacc man :-)

But this PDF seems to be what you're after (see slide 35). Basically, you define your item subject to exponentiation I (factor in your case) and the exponent E becomes:

E = I  ^ E
  | I

Upvotes: 2

Related Questions