parco-0.1: Generalised parser combinators

Safe HaskellSafe-Inferred



This module implements permutation parsers, and is a generalisation of Expr that will work with any parser combinator library. It builds a parser given a table of operators and associativities.

This module is a drop-in replacement for Expr, and the implementation is taken from that module.



data Assoc Source

This data type specifies the associativity of operators: left, right or none.

data Operator p a Source

This data type specifies operators that work on values of type a. An operator is either binary infix or unary prefix or postfix. A binary operator has also an associated associativity. As in Parsec, Infix and Prefix operators cannot be directly nested - i.e, in an expression grammar, if - is a prefix operator, - -x would be a parse error, although -(-x) would work. Use 'PrefixNestable'/'PostfixNestable' if you want fully nestable unary operators.


Infix (p (a -> a -> a)) Assoc 
Prefix (p (a -> a)) 
Postfix (p (a -> a)) 
PrefixNestable (p (a -> a)) 
PostfixNestable (p (a -> a)) 

type OperatorTable p a = [[Operator p a]]Source

An OperatorTable p a is a list of Operator p a lists. The list is ordered in descending precedence. All operators in one list have the same precedence (but may have a different associativity).

buildExpressionParser :: (Monad p, Parser p) => OperatorTable p a -> p a -> p aSource

buildExpressionParser table term builds an expression parser for terms term with operators from table, taking the associativity and precedence specified in table into account. Prefix and postfix operators of the same precedence can only occur once (i.e. --2 is not allowed if - is prefix negate). Prefix and postfix operators of the same precedence associate to the left (i.e. if ++ is postfix increment, than -2++ equals -1, not -3).

The buildExpressionParser takes care of all the complexity involved in building expression parser. Here is an example of an expression parser that handles prefix signs, postfix increment and basic arithmetic.

  expr    = buildExpressionParser table term
          <?> "expression"

  term    =  parens expr
          <|> natural
          <?> "simple expression"

  table   = [ [prefix "-" negate, prefix "+" id ]
            , [postfix "++" (+1)]
            , [binary "*" (*) AssocLeft, binary "/" (div) AssocLeft ]
            , [binary "+" (+) AssocLeft, binary "-" (-)   AssocLeft ]

  binary  name fun assoc = Infix   (reservedOp name >> return fun) assoc
  prefix  name fun       = Prefix  (reservedOp name >> return fun)
  postfix name fun       = Postfix (reservedOp name >> return fun)