17

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).

and indeed, this is biting me, since the language I am trying to parse allows arbitrary repetition of its prefix and postfix operators (think of a C expression like **a[1][2]).

So, why does Parsec make this restriction, and how can I work around it?

I think I can move my prefix/postfix parsers down into the term parser since they have the highest precedence.

i.e.

**a + 1

is parsed as

(*(*(a)))+(1)

but what could I have done if I wanted it to parse as

*(*((a)+(1)))

if buildExpressionParser did what I want, I could simply have rearranged the order of the operators in the table.

Note See here for a better solution

Community
  • 1
  • 1
pat
  • 12,587
  • 1
  • 23
  • 52

1 Answers1

16

I solved it myself by using chainl1:

prefix  p = Prefix  . chainl1 p $ return       (.)
postfix p = Postfix . chainl1 p $ return (flip (.))

These combinators use chainl1 with an op parser that always succeeds, and simply composes the functions returned by the term parser in left-to-right or right-to-left order. These can be used in the buildExprParser table; where you would have done this:

exprTable = [ [ Postfix subscr
              , Postfix dot
              ]
            , [ Prefix pos
              , Prefix neg
              ]
            ]

you now do this:

exprTable = [ [ postfix $ choice [ subscr
                                 , dot
                                 ]
              ]
            , [ prefix $ choice [ pos
                                , neg
                                ]
              ]
            ]

in this way, buildExprParser can still be used to set operator precedence, but now only sees a single Prefix or Postfix operator at each precedence. However, that operator has the ability to slurp up as many copies of itself as it can, and return a function which makes it look as if there were only a single operator.

pat
  • 12,587
  • 1
  • 23
  • 52
  • I found your answer extremely useful, but I ran into another problem, detailed [here](http://stackoverflow.com/questions/11174775), and I'd appreciate it if you could take a look, on the off chance you have a solution. – Alex R Jun 24 '12 at 03:41
  • Thanks for the useful answer. I am having a bit of difficulties with a generalisation of this problem. If you have any suggestions, they would be very welcome (see http://stackoverflow.com/questions/33214163/parsec-expr-repeated-prefix-with-different-priority/33217888#33217888) – BartBog Oct 20 '15 at 12:33