ANTLR Implicit Multiplication

Question

I'm new to ANTLR, and I'm trying to expand upon the example of a simple calculator presented here. Specifically, I've tried adding some simple functions, negative numbers and so on, to familiarize myself with ANTLR. However, I've run into a bit of a problem trying to implement "implicit" multiplication (for example, 3cos(2)sin(2) would be interpreted as 3*cos(2)*sin(2)).

I've found a question on Stack Overflow with the same kind of problem (here). The general form of the solution to that problem looks like what I'd found on my own, so I'm not sure where my problem lies.

My grammar is below. Without the | p2 = signExpr {$value *= $p2.value;} line (the last line in the multiplicationExpr), everything seems to work fine according to my tests. When I add this line and run it through antlr, I receive the following errors:

error(211): calculator.g:24:3: [fatal] rule multiplicationExpr has non-LL(*) decision due to recursive rule invocations reachable from alts 3,4.  Resolve by left-factoring or using syntactic predicates or using backtrack=true option.
warning(200): calculator.g:24:3: Decision can match input such as "'-' FLOAT" using multiple alternatives: 3, 4
As a result, alternative(s) 4 were disabled for that input

Enabling backtrack results in wrong calculations for some of my (normally working) test expressions. Further, the warning talks about alternatives 3 and 4 for multiplicationExpr, but I only have three alternatives in that block, which has me confused.

Would someone be able to point out the error in my grammar, given below?

grammar calculator;

eval    returns [double value]
        : exp = additionExpr    {$value = $exp.value;}
        ;

additionExpr    returns [double value]
        :               m1 = multiplicationExpr {$value = $m1.value;}
                ( '+'   m2 = multiplicationExpr {$value += $m2.value;}
                | '-'   m2 = multiplicationExpr {$value -= $m2.value;}
                )*
        ;

multiplicationExpr      returns [double value]
        :               p1 = signExpr   {$value = $p1.value;}
                ( '*'   p2 = signExpr   {$value *= $p2.value;}
                | '/'   p2 = signExpr   {$value /= $p2.value;}
                |       p2 = signExpr   {$value *= $p2.value;}
                )*
        ;

signExpr        returns [double value]
        :       (       '-' a = funcExpr        {$value = -1*$a.value;}
                ) | (   a = funcExpr            {$value = $a.value;}
                )
        ;

funcExpr        returns [double value]
        :       (       'cos' s = signExpr      {$value = Math.cos($s.value);}
                ) | (   'sin' s = signExpr      {$value = Math.sin($s.value);}
                ) | (   s = powExpr             {$value = s;}
                )
        ;

powExpr returns [double value]
        :               s1 = atomExpr   {$value = $s1.value;}
                ( '^'   s2 = signExpr   {$value = Math.pow($value, $s2.value);}
                )?
        ;

atomExpr        returns [double value]
        :       f = FLOAT                       {$value = Double.parseDouble($f.text);}
        |       '(' exp = additionExpr ')'      {$value = $exp.value;}
        ;

FLOAT
    :   ('0'..'9')+ ('.' ('0'..'9')*)? EXPONENT?
    |   '.' ('0'..'9')+ EXPONENT?
    ;

WS  :   ( ' '
        | '\t'
        | '\r'
        | '\n'
        ) {$channel=HIDDEN;}
    ;

fragment
EXPONENT : ('e'|'E') ('+'|'-')? ('0'..'9')+ ;

Answer 1

With BernardK's solution massaged into my previous grammar, here is the new multiplicationExpr that gets everything working for me:

multiplicationExpr      returns [double value]
        :
                        p1 = signExpr   {$value = $p1.value;}
                ( (signExpr funcExpr*) => p2 = funcExpr {$value *= $p2.value;}
                | '*'   p2 = signExpr   {$value *= $p2.value;}
                | '/'   p2 = signExpr   {$value /= $p2.value;}
                )*
        ;

After a bit more playing around, something close to what I originally had works as well:

multiplicationExpr      returns [double value]
        :               p1 = signExpr   {$value = $p1.value;}
                (       p2 = funcExpr   {$value *= $p2.value;}
                | '*'   p2 = signExpr   {$value *= $p2.value;}
                | '/'   p2 = signExpr   {$value /= $p2.value;}
                )*
        ;

Thank you again, Bernard.

Answer 2

New year, new version :-)

As you are new to ANTLR, and now have seen some ambiguity problems with v3, you will surely appreciate the power of v4. Following is a solution (I'm new to v4) keeping the computation at the expression level, but showing how simple it is to describe expressions with ANTLR4.

grammar Calculator;

progr : eval+ EOF ;

eval 
    :   mult ';' {System.out.println($eval.text + " -> " + $mult.value);}
    ;

mult    returns [double value]
    :   e1 = expr                  {$value = $e1.value;}
    |   e1 = expr e2 = mult        {$value = $e1.value * $e2.value;}
    ;

expr    returns [double value]
    :   e1 = expr '^'<assoc=right> e2 = expr   {$value = Math.pow($e1.value, $e2.value);}
    |   '-' e1 = expr              {$value = -1 * $e1.value;}
    |   e1 = expr '*' e2 = expr    {$value = $e1.value * $e2.value;}
    |   e1 = expr '/' e2 = expr    {$value = $e1.value / $e2.value;}
    |   e1 = expr '+' e2 = expr    {$value = $e1.value + $e2.value;}
    |   e1 = expr '-' e2 = expr    {$value = $e1.value - $e2.value;}
    |   'cos' s = expr             {$value = 2; System.out.println("cos" + $s.text + "=2");} // {$value = Math.cos($s.value);}
    |   'sin' s = expr             {$value = 5; System.out.println("sin" + $s.text + "=5");} // {$value = Math.sin($s.value);}
    |   FLOAT                      {$value = Double.parseDouble($FLOAT.text); System.out.println("FLOAT=" + $FLOAT.text);}
    |   '(' FLOAT ')'              {$value = $expr.value;} // just for demo, to avoid printing FLOAT parameters
    |   '(' e1 = expr ')'          {$value = $e1.value; System.out.println("expr(" + $e1.text + ")=" + $e1.value);}
    ;

FLOAT
    :   DIGIT+ ( '.' DIGIT* )? EXPONENT?
    |   '.' DIGIT+ EXPONENT?
    ;

WS  :   [ \t\r\n] -> channel(HIDDEN)
    ;

fragment DIGIT    : [0-9] ;
fragment EXPONENT : [Ee] ( '+' | '-' )? DIGIT+ ;

File input.txt :

3cos(2)sin(6);
4cos(2)cos(8)sin(6);
sin(1)sin(6);
sin(1)sin(6)cos(8)10sin(8);
sin(1)5cos(6)3;
2^8;
3*-12;
55/sin(0);
55/(2 + 3);

Execution :

$ echo $CLASSPATH
.:/usr/local/lib/antlr-4.0b3-complete.jar
$ alias
alias antlr4='java -jar /usr/local/lib/antlr-4.0b3-complete.jar'
alias grun='java org.antlr.v4.runtime.misc.TestRig'
$ antlr4 Calculator.g4 
$ javac Calculator*.java
$ grun Calculator progr input.txt 
FLOAT=3
cos(2)=2
sin(6)=5
3cos(2)sin(6); -> 30.0
FLOAT=4
cos(2)=2
cos(8)=2
sin(6)=5
4cos(2)cos(8)sin(6); -> 80.0
sin(1)=5
sin(6)=5
sin(1)sin(6); -> 25.0
sin(1)=5
sin(6)=5
cos(8)=2
FLOAT=10
sin(8)=5
sin(1)sin(6)cos(8)10sin(8); -> 2500.0
sin(1)=5
FLOAT=5
cos(6)=2
FLOAT=3
sin(1)5cos(6)3; -> 150.0
FLOAT=2
FLOAT=8
2^8; -> 256.0
FLOAT=3
FLOAT=12
3*-12; -> -36.0
FLOAT=55
sin(0)=5
55/sin(0); -> 11.0
FLOAT=55
FLOAT=2
FLOAT=3
expr(2 + 3)=5.0
55/(2 + 3); -> 11.0

Notes :
1) I have given fixed values to cos and sin to be able to easily verify the computations.
2) Run with -diagnostics and you'll see ambiguity messages :

$ grun Calculator progr -diagnostics input.txt 
FLOAT=3
line 1:6 reportAttemptingFullContext d=2, input='(2)'
line 1:6 reportAmbiguity d=2: ambigAlts={5, 6}, input='(2)'

This is because I have added the line :

    |   '(' FLOAT ')'              {$value = $expr.value;} // just for demo

to print nicely (avoid printing parameters to cos/sin). This is ambiguous with '(' e1 = expr ')'. Remove it and the messages disappear.
3) To see how ANTLR4 tokenizes (-tokens) and parses (-trace) :

grun Calculator progr -tokens -diagnostics -trace input.txt

4) site : http://antlr4.org
5) book : http://pragprog.com/book/tpantlr2/the-definitive-antlr-4-reference
6) install 4.0b3 on OS X : http://forums.pragprog.com/forums/206/topics/11231
7) SO filter : https://stackoverflow.com/questions/tagged/antlr4
8) group : https://groups.google.com/forum/#!forum/antlr-discussion