makeExprParser: Mixing operators with different associativities in same precedence level does not work

[cbjadwani]

When makeExprParser is given two infix operators at the same precedence level but with different associativit it stops before parsing the expression completely for some inputs.

Example:

operatorTable =
  [ [ prefix "-" Negation
    , prefix "+" id
    ]
  , [ binaryR "^" Expo
    , binaryL "*" Product
    , binaryL "/" Division
    ]
  , [ binaryL "+" Sum
    , binaryL "-" Subtr
    ]
  ]

For the above slightly modified example from the tutorial the parser stops unexpectedly:

ghci> parseTest pExpr "2 ^ 2 * 3 ^ 2"
Expo (Int 2) (Int 2)

This is unexpected because documentation says it should work:

All operators in one list have the same precedence (but may have different associativity).

Looking at the code it seems like this could be fixed by adding recursion to addPrecLevel. But I am not sure this is a good idea so have not created a PR to fix this.

[mrkkrp]

Thanks for reporting this. Hmm, isn't mixing right and left associative operators with the same precedence inherently ambiguous?

[cbjadwani]

True, mixing operators with different associativity is ambiguous. I think failing on ambiguous expressions is not a bug but probably need to update doc to mention that while makeExprParser accepts operators at same precedence and associativity it will not parse expressions that mix such operators. It will only parse expressions with operators of any one associativity from each precedence level.

A useful feature would be to detect ambiguous expressions and generate specific errors.

Some languages have custom rules for parsing these kind of expressions which can be implemented by adding recursion to addPrecLevel though that does seem like a good solution.

Haskell is even more strict than makeExprParser because it does not accept operators with different associativity at same precedence level.