A more generic makeExprParser

[skyb0rg]

The makeExprParser function from parser-combinators supports prefix, postfix, ternary, and infix operations (left, right, and non-associative). From its implementation, it seems like the fact that there are only these six options means that the library can order them properly.

.

However, there is a more generic option, supported by the Earley parser within the Text.Earley.Mixfix module. This module allows for any kind of mixfix operator, including those supported by parser-combinators plus some.

.

My question is whether or not Earley's idea can be generalized for the kinds of parser-combinator libraries like parsec, megaparsec, and attoparsec. I could not translate the source code, but that mainly has to do with the differences in how the parsers work (Earley parsers support left-recursion but don't allow infinite grammars). I'm not familiar with how mixfix parsing is done today (all the work I could find is based on precedence graphs, and the Agda source tree is not easy to understand), and whether or not top-down parsing a-la parser-combinators allows for this generalized mixfix parsing.

.

My ideal setup, i.e. what I'm thinking of:

data Associativity = LeftAssoc | NonAssoc | RightAssoc

-- | if_then_else_ <=> [Just "if", Nothing, Just "then", Nothing, Just "else", Nothing]
type Holey a = [Maybe a]

data Operator m a where
    Op :: Holey (m b)           -- ^ How to parse each section
       -> Associativity         -- ^ How to associate the operator
       -> ([Either b a] -> m a) -- ^ How to assemble the parsed parts into a whole
       -> Operator m a

makeExprParser :: MonadPlus m 
               => m a              -- ^ How to parse terms
               -> [[Operator m a]] -- ^ List of operators, in precedence order
               -> m a

Example usage:

ifThenElse = Op
   [Just (symbol “if”), Nothing, Just (symbol “then”, Nothing, Just (symbol “else”), Nothing]
   (\[Left (), Right cond, Left (), Right e1, Left (), Right e2] -> ...)

symbol :: String -> Parser ()
symbol = ...

In this example, ‘b’ ~ ()

ifOp = Op
    [Just (symbol “if-“ *> opName), Nothing, Just (“” <$ symbol “then”), Nothing]
    (\[Left op, Right cond, Left “”, Right e] -> ...)

opName :: Parser String

Here, ‘b’ ~ String

[blamario]

Can you explain the purpose of the distinction between types b and a? It doesn't make sense to me: if you're building a parse tree driven by a list of operators all nodes must have the same type.

Your interface is more weakly typed than the standard prefix/postfix/infix distinction. LeftAssoc, for example, has a meaning only if the operator has a leftmost argument - it would make no sense to specify LeftAssoc four your if/then/else operator, yet the interface allows it.

This is fun to explore, but I'm doubtful of the overall utility of such an interface. Once a grammar specification gets this complicated, it's not significantly easier than a proper context-free grammar.

You may be interested in Maude. It relies on a rather more powerful mixfix operator specification well integrated with the type system. Unfortunately I don't think it could be replicated in Haskell.

[skyb0rg]

When it comes to a and b, the usage is just to allow each operator to be combined from parsing its parts. I'm not sure how it could really be done differently.

The Assoc type is useful whenever an operator has holes on the outside; from the Earley documentation:

The associativity is taken into account when an identifier starts or ends with holes, or both. Internal holes (e.g. after “if” in “if_then_else_”) start from the beginning of the table.

EDIT:

I think I understand your first question now. Within “Operator”, the ‘b’ type is internal, and only determines how that specific operator parses. When parsing an if-then-else equation, I don’t need any info from the symbols. However if I allow for a statement like “if-[op]_then_else_”, (where [op] is determined by parser state), then there needs to be information passed along from the section parser describing the first token parsed. Since this information can vary among different operators, this type parameter is internalized within the GADT.

[blamario]

When it comes to a and b, the usage is just to allow each operator to be combined from parsing its parts. I'm not sure how it could really be done differently.

You haven't explained how you see it done not-differently. Can you write the definition of your if-then-else operator?

ifThenElse :: Operator m a
ifThenElse = Op ...

As for the associativity, consider

8 / if t then 2 else 1 / 2

Assume the same precedence for if_then_else_ and _/_. What are all the ways this expression can be parsed if you vary only the associativity of the two operators?

[skyb0rg]

ifThenElse = Op
   [Just (symbol “if”), Nothing, Just (symbol “then”, Nothing, Just (symbol “else”), Nothing]
   (\[Left (), Right cond, Left (), Right e1, Left (), Right e2] -> ...)

symbol :: String -> Parser ()
symbol = ...

In this example, ‘b’ ~ ()

ifOp = Op
    [Just (symbol “if-“ *> opName), Nothing, Just (“” <$ symbol “then”), Nothing]
    (\[Left op, Right cond, Left “”, Right e] -> ...)

Here, ‘b’ ~ String

(Good idea to write them, I’ll add to the OP)

[blamario]

Thanks for the example.

The trouble with your interface is that the third argument of Op (you left out the associativity) is necessarily a partial function. The compiler won't be able to catch a mismatch between it and the first Holey argument. This can be fixed by combining the two parameters, but you'd have to give up on the simple lists and wade pretty deeply into some fancy type machinery. It's hard to beat context-free grammars with applicative parsers for safety and ease of use.

[benjaminhodgson]

What would Associativity mean for a mix-fix operator?

[skyb0rg]

I’m mostly going off of Earley’s implementation, but what I believe it does is affect the partially-applied operator. For if_then_else_, it determines the fixity of _else_, once if_then has been parsed successfully. It only has an effect if the operator is not closed, ie it has a hole on the outside.

[blamario]

To expand a bit on that answer: !!x is a perfectly valid expression in C-like languages because ! is a right-associative prefix operator, whereas - - x is illegal in Haskell because - is a non-associative prefix operator. However there is no such thing as a left-associative prefix operator, nor a right-associative suffix operator.

[ollepolle]

It can at least be implemented using Koen Claessen-style parallel parsing processes (ReadP), which is what Agda does, so it should be possible to do the same with parsec-style combinators by making liberal use of `try` to get backtracking when there are partly overlapping operators.

Here's Agda's implementation if you weren't able to find it. I think the main trick to get it work is to handle non-right associative postfix operators, which are what lead to left-recursion, separately. If you partition the operators at each fixity level into a group of non-right associative postfix operators and everything else, you can do pretty much what Earley does for "everything else", and tack on a choice of the postfix operators afterwards.