Parsec.Expr repeated Prefix with different priority

Question

The documentation for Parsec.Expr.buildExpressionParser says:

Prefix and postfix operators of the same precedence can only occur once (i.e. --2 is not allowed if - is prefix negate).

However, I would like to parse such strings.

Concretely, consider the following grammar:

sentence: 
    | identifier
    | "~" sentence
    | sentence & sentence
    | "!" sentence

Where operator precedence is: "~" binds stronger than "&" binds stronger than "!"

For example, I would like the sentence

! ~a & b

to be parsed as

! ( (~a) & b )

And the sentence

~ ! a & b 

as

~( ! ( a & b) )

Parsec allows me to do this (and specify the operator precedence), however, I would like to be able to chain prefixes, e.g. ~ ~ ! ~ a. Parsec does not allow this. I have found the solution for chaining prefixes, but this solution does not allow me to specify a different operator priority for the different prefix operators (either both "~" and "!" bind stronger than "&", or none of them does)

Does anyone have a solution for this?

Edit:

Partial solution that gets the operator bindings correct, but allows no chaining: http://lpaste.net/143362

Partial solution with chaining but that has a wrong binding for the "~" operator: http://lpaste.net/143364

Edit: Some more clarifications related to the latest answer.

I actually want & to be associative. Left or right does not matter. Left vs right associativity only matters between operators of the same precedence. For your examples, it is all resolved by noting that & binds stronger than ! (& has greater operator precedence)

Hence, the expression you were worried about:

a & ! b & c should become: (first bind & where possible) a & ! (b & c)

Similarly, ! a & ! b & c should be parsed (first bind &) ! a & ! (b & c), thus ! a & (! (b & c)), thus ! (a & (! (b & c)))

Answer 1

One problem with my partial solution at http://lpaste.net/143362 is that it doesn't recognize ~ ! a.

However, if you change the operator table to:

table   = [ [ Prefix tilde ]
          , [ Infix amper AssocLeft ]
          , [ Prefix bang ]
          , [ Prefix tilde ]
          ]

it can parse that expression as well as ! ~a & b, ~ ! a & b correctly. Code at: http://lpaste.net/143370

So now combine this idea with your chaining and try:

table   = [ [ Prefix (chained tilde) ]
          , [ Infix amper AssocLeft ]
          , [ Prefix (chained bang) ]
          , [ Prefix (chained tilde) ]
          ]

chained  p = chainl1 p $ return (.)

Code at: http://lpaste.net/143371

Answer 2

I wasn't satisfied with my original answer since it doesn't solve the general case of prefix and postfix operators at various precedences, and it requires the programmer to have to think about the grammar instead of just relying on buildExpressionParser to do the right thing.

I hunted around online and discovered the Pratt method for recursive descent parsing of expressions. I was able to implement a compact Haskell version that replaces buildExpressionParser. It has exactly the same interface as buildExpressionParser, but doesn't require you to use the chained prefix combinators or muck around with the term parser. I played around with your grammar, changing the associativity of &, and switching the prefix operators to postfix operators, and it all seems to work...

buildPrattParser table termP = parser precs where

  precs = reverse table

  prefixP = choice prefixPs <|> termP where
    prefixPs = do
      precsR@(ops:_) <- tails precs 
      Prefix opP <- ops
      return $ opP <*> parser precsR

  infixP precs lhs = choice infixPs <|> pure lhs where
    infixPs = do
      precsR@(ops:precsL) <- tails precs
      op <- ops
      p <- case op of
        Infix opP assoc -> do
          let p precs = opP <*> pure lhs <*> parser precs
          return $ case assoc of
            AssocNone  -> error "Non associative operators are not supported"
            AssocLeft  -> p precsL
            AssocRight -> p precsR
        Postfix opP ->
          return $ opP <*> pure lhs
        Prefix _ -> mzero
      return $ p >>= infixP precs

  parser precs = prefixP >>= infixP precs