Can't get Antlr4 parser to follow order of operations with implicit multiplication

2
votes

I'm new to ANTLR and I'm attempting to generate a relatively simply parser for a calculator application, using ANTLR4 and C#. Here is my grammar file.

parser grammar CalculatorExpressionParser;

options{
language = CSharp2;
}

expr:  FUNC expr? (COMMA expr)* RIGHTPAREN               #CallFunction
    |  LEFTPAREN expr RIGHTPAREN                         #Parens
    |  expr POW<assoc=right> expr                        #Pow
    |  expr op=(MULTIPLY | DIVIDE)? expr                 #MultDivide
    |  expr op=(ADD | SUBTRACT) expr                     #AddSubtract
    |  SUBTRACT expr                                     #Negative
    |  NUMBER                                            #Number
    ;

I wrote a custom lexer to generate the tokens in order to support implicit multiplication and conversion of variables to their numerical equivalent before parsing.

But upon input I get the following results.

2+6/3 => 4 (correct)
6/3+2 => 1.2 (should be 4)
6/(3+2) => 4 (also correct)

1+2*3 => 7 (correct)
2*3+1 => 8 (should be 7 too)
(2*3)+1 => 7 (correct)

Note that I tried turning off the error recovery capabilities and setting it to report all ambiguity errors and I don't appear to be getting any.

Anyways, if I change the grammar to the following by removing the ? after the division/multiplication operator, then it appears to work great, except implicit multiplication is no longer supported.

parser grammar CalculatorExpressionParser;

options{
language = CSharp2;
}

expr:  FUNC expr? (COMMA expr)* RIGHTPAREN               #CallFunction
    |  LEFTPAREN expr RIGHTPAREN                         #Parens
    |  expr POW<assoc=right> expr                        #Pow
    |  expr op=(MULTIPLY | DIVIDE) expr                  #MultDivide
    |  expr op=(ADD | SUBTRACT) expr                     #AddSubtract
    |  SUBTRACT expr                                     #Negative
    |  NUMBER                                            #Number
    ;

I was wondering why putting the ? breaks the matching order? And is there an easy way to fix this?

2
c#antlrantlr4
This may have been fixed in the latest release. Do you have a self-contained example that demonstrates the problem so that I can test it? – Sam Harwell
Here is a simple combined lexer/parser grammar file, visitor implementation, and test program that exhibits the issue. dl.dropboxusercontent.com/u/22576981/ANTLR4Test/Combined1.zip – hashtable
I was using the Antlr4 version 4.1.0-alpha003 from Nuget – hashtable

2 Answers

1
votes

"expr expr" doesn't fit the pattern of operators though ANTLR 4.2 might handle this. Sam is still working on updating C# target.

1
votes

Split your expr statement into multiple statements in order to get proper order of operations.

Typically it goes like below: Note how each expr only handles one set of mathematical operations and then calls down to a lower precedence rule. Typically the lowest rule is your atomic operator like INT or FLOAT

So in this case you handle logical AND and OR's then comparisons, then exponents, then multiplications/division then addition/subtraction.

NOTE I should also point out, here I've created an AST tree instead of doing the operations inline.

expr
: subExpr -> ^(EXPR subExpr)
;

subExpr : logicalAndExp (addSubtractOp^ logicalAndExp)*
;   

logicalAndExp
: logicalOrExp (multiplyDivideOp^  logicalOrExp)*    
;

logicalOrExp
: comparatorExp (CARET^  comparatorExp)*    
;

comparatorExp
: powExp (comparatorOp^  powExp)*   
;

powExp  : multExp (BARBAR^   multExp)*  
;

multExp 
:  expressionAtom (AMPAMP^ expressionAtom)*
;expression 
: subExpr -> ^(EXPR subExpr)
;

subExpr : logicalAndExp (addSubtractOp^ logicalAndExp)*
;   

logicalAndExp
: logicalOrExp (multiplyDivideOp^  logicalOrExp)*    
;

logicalOrExp
: comparatorExp (CARET^  comparatorExp)*    
;

comparatorExp
: powExp (comparatorOp^  powExp)*   
;

powExp  : multExp (BARBAR^   multExp)*  
;

multExp 
:  expressionAtom (AMPAMP^ expressionAtom)*
;