parser-combinators 0.4.0 → 1.0.0

raw patch · 10 files changed

+213/−103 lines, 10 filesdep ~base

Dependency ranges changed: base

Files

• CHANGELOG.md +9/−0
• Control/Applicative/Combinators.hs +1/−1
• Control/Applicative/Combinators/NonEmpty.hs +1/−1
• Control/Applicative/Permutations.hs +25/−93
• Control/Monad/Combinators.hs +1/−1
• Control/Monad/Combinators/Expr.hs +162/−0
• Control/Monad/Combinators/NonEmpty.hs +1/−1
• LICENSE.md +1/−1
• README.md +1/−1
• parser-combinators.cabal +11/−4

@@ -1,3 +1,12 @@+## Parser combinators 1.0.0++* Added the `Control.Monad.Combinators.Expr` module.++* Dropped the compatibility operators `(<$$>)`, `(<$?>)`, `(<||>)`, and+  `(<|?>)` from `Control.Applicative.Permutations`.++* Dropped support for GHCs older than 7.10.+ ## Parser combinators 0.4.0  * Improved the documentation.

@@ -1,6 +1,6 @@ -- | -- Module      :  Control.Applicative.Combinators--- Copyright   :  © 2017 Mark Karpov+-- Copyright   :  © 2017–2018 Mark Karpov -- License     :  BSD 3 clause -- -- Maintainer  :  Mark Karpov <markkarpov92@gmail.com>

@@ -1,6 +1,6 @@ -- | -- Module      :  Control.Applicative.Combinators--- Copyright   :  © 2017 Mark Karpov+-- Copyright   :  © 2017–2018 Mark Karpov -- License     :  BSD 3 clause -- -- Maintainer  :  Mark Karpov <markkarpov92@gmail.com>

@@ -1,6 +1,6 @@ -- | -- Module      :  Control.Applicative.Permutations--- Copyright   :  © 2017 Mark Karpov+-- Copyright   :  © 2017–2018 Mark Karpov -- License     :  BSD 3 clause -- -- Maintainer  :  Mark Karpov <markkarpov92@gmail.com>@@ -13,12 +13,14 @@ -- https://hackage.haskell.org/package/parsec-permutation -- -- This module also takes inspiration from the algorithm is described in:--- /Parsing Permutation Phrases/, by Arthur Baars, Andres Loh and Doaitse--- Swierstra. Published as a functional pearl at the Haskell Workshop 2001.+-- /Parsing Permutation Phrases/, by Arthur Baars, Andres Löh and Doaitse+-- Swierstra. Published as a functional pearl at the Haskell Workshop 2001: --+-- https://www.cs.ox.ac.uk/jeremy.gibbons/wg21/meeting56/loeh-paper.pdf+-- -- From these two works we derive a flexible and general method for parsing -- permutations over an 'Applicative' structure. Quite useful in conjunction--- with \"Free\" constructions of Applicatives, Monads, etc.+-- with \"Free\" constructions of 'Applicative's, 'Monad's, etc. -- -- Other permutation parsing libraries tend towards using special \"almost -- applicative\" combinators for construction which denies the library user@@ -36,14 +38,6 @@ -- >               <*> toPermutation (char 'b') -- >               <*> toPermutationWithDefault '_' (char 'c') ----- Equivalently, this can also be describe using the convenience operators--- reminiscent of other parsing libraries:------ > test = runPermutation $--- >          (,,) <$?> ("", some (char 'a'))--- >               <||> char 'b'--- >               <|?> ('_', char 'c')--- -- @since 0.2.0  module Control.Applicative.Permutations@@ -54,12 +48,7 @@   , intercalateEffect     -- ** Permutation constructors   , toPermutation-  , toPermutationWithDefault-    -- ** Convenience operators-  , (<$$>)-  , (<$?>)-  , (<||>)-  , (<|?>) )+  , toPermutationWithDefault ) where  import Control.Applicative@@ -93,26 +82,29 @@ -- | \"Unlifts\" a permutation parser into a parser to be evaluated with an -- intercalated effect. Useful for separators between permutation elements. ----- For example, suppose that similar to above we want to parse a permutation of:--- an optional string of @a@'s, the character @b@ and an optional @c@. /However/,--- we also want each element of the permutation to be separated by a colon.--- Using a standard parsing library combinator @char@, this can be described--- using the 'Applicative' instance by:+-- For example, suppose that similar to above we want to parse a permutation+-- of: an optional string of @a@'s, the character @b@ and an optional @c@.+-- /However/, we also want each element of the permutation to be separated+-- by a colon. Using a standard parsing library combinator @char@, this can+-- be described using the 'Applicative' instance by: -- -- > test = intercalateEffect (char ':') $--- >          (,,) <$?> ("", some (char 'a'))--- >               <||> char 'b'--- >               <|?> ('_', char 'c')------ This will accept strings such as: \"a:b:c\", \"b:c:a\", \"b:aa\", \"b\", etc.------ Note that the effect is intercalated /between/ permutation components and that:+-- >          (,,) <$> toPermutationWithDefault "" (some (char 'a'))+-- >               <*> toPermutation (char 'b')+-- >               <*> toPermutationWithDefault '_' (char 'c') -----  - There is never an effect parsed preceeding the first component of the permutation+-- This will accept strings such as: \"a:b:c\", \"b:c:a\", \"b:aa\", \"b\",+-- etc. -----  - There is never an effect parsed following the last component of the permutation+-- Note that the effect is intercalated /between/ permutation components and+-- that: -----  - No effects are intercalated between missing components with a default value.+--     * There is never an effect parsed preceeding the first component of+--       the permutation.+--     * There is never an effect parsed following the last component of the+--       permutation.+--     * No effects are intercalated between missing components with a+--       default value.  intercalateEffect   :: ( Alternative m@@ -151,63 +143,3 @@   -> m a -- ^ Permutation component   -> Permutation m a toPermutationWithDefault v p = P (Just v) $ pure <$> p--infixl 1 <||>, <|?>-infixl 2 <$$>, <$?>---- | The expression @f \<$$> p@ creates a fresh permutation parser--- consisting of parser @p@. The the final result of the permutation parser--- is the function @f@ applied to the return value of @p@. The parser @p@ is--- not allowed to accept empty input—use the optional combinator ('<$?>')--- instead.------ If the function @f@ takes more than one parameter, the type variable @b@--- is instantiated to a functional type which combines nicely with the adds--- parser @p@ to the ('<||>') combinator. This results in stylized code--- where a permutation parser starts with a combining function @f@ followed--- by the parsers. The function @f@ gets its parameters in the order in--- which the parsers are specified, but actual input can be in any order.--(<$$>)-  :: Alternative m-  => (a -> b)        -- ^ Function to use on result of parsing-  -> m a             -- ^ Normal parser-  -> Permutation m b -- ^ Permutation parser build from it-f <$$> c = toPermutation $ f <$> c---- | The expression @f \<$?> (x, p)@ creates a fresh permutation parser--- consisting of parser @p@. The final result of the permutation parser is--- the function @f@ applied to the return value of @p@. The parser @p@ is--- optional—if it cannot be applied, the default value @x@ will be used--- instead.--(<$?>)-  :: Alternative m-  => (a -> b)        -- ^ Function to use on result of parsing-  -> (a, m a)        -- ^ Default value and parser-  -> Permutation m b -- ^ Permutation parser-f <$?> (v,c) = f <$> toPermutationWithDefault v c---- | The expression @perm \<||> p@ adds parser @p@ to the permutation parser--- @perm@. The parser @p@ is not allowed to accept empty input—use the--- optional combinator ('<|?>') instead. Returns a new permutation parser--- that includes @p@.--(<||>)-  :: Alternative m-  => Permutation m (a -> b) -- ^ Given permutation parser-  -> m a                    -- ^ Parser to add (should not accept empty input)-  -> Permutation m b        -- ^ Resulting parser-p <||> c = p <*> toPermutation c---- | The expression @perm \<||> (x, p)@ adds parser @p@ to the permutation--- parser @perm@. The parser @p@ is optional—if it cannot be applied, the--- default value @x@ will be used instead. Returns a new permutation parser--- that includes the optional parser @p@.--(<|?>)-  :: Alternative m-  => Permutation m (a -> b) -- ^ Given permutation parser-  -> (a, m a)               -- ^ Default value and parser-  -> Permutation m b        -- ^ Resulting parser-p <|?> (v,c) = p <*> toPermutationWithDefault v c

@@ -1,6 +1,6 @@ -- | -- Module      :  Control.Monad.Combinators--- Copyright   :  © 2017 Mark Karpov+-- Copyright   :  © 2017–2018 Mark Karpov -- License     :  BSD 3 clause -- -- Maintainer  :  Mark Karpov <markkarpov92@gmail.com>

@@ -0,0 +1,162 @@+-- |+-- Module      :  Control.Monad.Combinators.Expr+-- Copyright   :  © 2017–2018 Mark Karpov+-- License     :  BSD 3 clause+--+-- Maintainer  :  Mark Karpov <markkarpov92@gmail.com>+-- Stability   :  experimental+-- Portability :  non-portable+--+-- A helper module to parse expressions. It can build a parser given a table+-- of operators.+--+-- @since 1.0.0++module Control.Monad.Combinators.Expr+  ( Operator (..)+  , makeExprParser )+where++import Control.Monad+import Control.Monad.Combinators++-- | 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.++data Operator m a+  = InfixN  (m (a -> a -> a)) -- ^ Non-associative infix+  | InfixL  (m (a -> a -> a)) -- ^ Left-associative infix+  | InfixR  (m (a -> a -> a)) -- ^ Right-associative infix+  | Prefix  (m (a -> a))      -- ^ Prefix+  | Postfix (m (a -> a))      -- ^ Postfix++-- | @'makeExprParser' term table@ builds an expression parser for terms+-- @term@ with operators from @table@, taking the associativity and+-- precedence specified in the @table@ into account.+--+-- @table@ is a list of @[Operator m a]@ lists. The list is ordered in+-- descending precedence. All operators in one list have the same precedence+-- (but may have different associativity).+--+-- Prefix and postfix operators of the same precedence associate to the left+-- (i.e. if @++@ is postfix increment, than @-2++@ equals @-1@, not @-3@).+--+-- Unary operators of the same precedence can only occur once (i.e. @--2@ is+-- not allowed if @-@ is prefix negate). If you need to parse several prefix+-- or postfix operators in a row, (like C pointers—@**i@) you can use this+-- approach:+--+-- > manyUnaryOp = foldr1 (.) <$> some singleUnaryOp+--+-- This is not done by default because in some cases allowing repeating+-- prefix or postfix operators is not desirable.+--+-- If you want to have an operator that is a prefix of another operator in+-- the table, use the following (or similar) wrapper (Megaparsec example):+--+-- > op n = (lexeme . try) (string n <* notFollowedBy punctuationChar)+--+-- 'makeExprParser' takes care of all the complexity involved in building an+-- expression parser. Here is an example of an expression parser that+-- handles prefix signs, postfix increment and basic arithmetic:+--+-- > expr = makeExprParser term table <?> "expression"+-- >+-- > term = parens expr <|> integer <?> "term"+-- >+-- > table = [ [ prefix  "-"  negate+-- >           , prefix  "+"  id ]+-- >         , [ postfix "++" (+1) ]+-- >         , [ binary  "*"  (*)+-- >           , binary  "/"  div  ]+-- >         , [ binary  "+"  (+)+-- >           , binary  "-"  (-)  ] ]+-- >+-- > binary  name f = InfixL  (f <$ symbol name)+-- > prefix  name f = Prefix  (f <$ symbol name)+-- > postfix name f = Postfix (f <$ symbol name)++makeExprParser :: MonadPlus m+  => m a               -- ^ Term parser+  -> [[Operator m a]]  -- ^ Operator table, see 'Operator'+  -> m a               -- ^ Resulting expression parser+makeExprParser = foldl addPrecLevel+{-# INLINEABLE makeExprParser #-}++-- | @addPrecLevel p ops@ adds the ability to parse operators in table @ops@+-- to parser @p@.++addPrecLevel :: MonadPlus m => m a -> [Operator m a] -> m a+addPrecLevel term ops =+  term' >>= \x -> choice [ras' x, las' x, nas' x, return x]+  where+    (ras, las, nas, prefix, postfix) = foldr splitOp ([],[],[],[],[]) ops+    term' = pTerm (choice prefix) term (choice postfix)+    ras'  = pInfixR (choice ras) term'+    las'  = pInfixL (choice las) term'+    nas'  = pInfixN (choice nas) term'+{-# INLINEABLE addPrecLevel #-}++-- | @pTerm prefix term postfix@ parses a @term@ surrounded by optional+-- prefix and postfix unary operators. Parsers @prefix@ and @postfix@ are+-- allowed to fail, in this case 'id' is used.++pTerm :: MonadPlus m => m (a -> a) -> m a -> m (a -> a) -> m a+pTerm prefix term postfix = do+  pre  <- option id prefix+  x    <- term+  post <- option id postfix+  return . post . pre $ x+{-# INLINE pTerm #-}++-- | @pInfixN op p x@ parses non-associative infix operator @op@, then term+-- with parser @p@, then returns result of the operator application on @x@+-- and the term.++pInfixN :: MonadPlus m => m (a -> a -> a) -> m a -> a -> m a+pInfixN op p x = do+  f <- op+  y <- p+  return $ f x y+{-# INLINE pInfixN #-}++-- | @pInfixL op p x@ parses left-associative infix operator @op@, then term+-- with parser @p@, then returns result of the operator application on @x@+-- and the term.++pInfixL :: MonadPlus m => m (a -> a -> a) -> m a -> a -> m a+pInfixL op p x = do+  f <- op+  y <- p+  let r = f x y+  pInfixL op p r <|> return r+{-# INLINE pInfixL #-}++-- | @pInfixR op p x@ parses right-associative infix operator @op@, then+-- term with parser @p@, then returns result of the operator application on+-- @x@ and the term.++pInfixR :: MonadPlus m => m (a -> a -> a) -> m a -> a -> m a+pInfixR op p x = do+  f <- op+  y <- p >>= \r -> pInfixR op p r <|> return r+  return $ f x y+{-# INLINE pInfixR #-}++type Batch m a =+  ( [m (a -> a -> a)]+  , [m (a -> a -> a)]+  , [m (a -> a -> a)]+  , [m (a -> a)]+  , [m (a -> a)] )++-- | A helper to separate various operators (binary, unary, and according to+-- associativity) and return them in a tuple.++splitOp :: Operator m a -> Batch m a -> Batch m a+splitOp (InfixR  op) (r, l, n, pre, post) = (op:r, l, n, pre, post)+splitOp (InfixL  op) (r, l, n, pre, post) = (r, op:l, n, pre, post)+splitOp (InfixN  op) (r, l, n, pre, post) = (r, l, op:n, pre, post)+splitOp (Prefix  op) (r, l, n, pre, post) = (r, l, n, op:pre, post)+splitOp (Postfix op) (r, l, n, pre, post) = (r, l, n, pre, op:post)

@@ -1,6 +1,6 @@ -- | -- Module      :  Control.Monad.Combinators.NonEmpty--- Copyright   :  © 2017 Mark Karpov+-- Copyright   :  © 2017–2018 Mark Karpov -- License     :  BSD 3 clause -- -- Maintainer  :  Mark Karpov <markkarpov92@gmail.com>

@@ -1,4 +1,4 @@-Copyright © 2017 Mark Karpov+Copyright © 2017–2018 Mark Karpov  All rights reserved. 

@@ -21,6 +21,6 @@  ## License -Copyright © 2017 Mark Karpov+Copyright © 2017–2018 Mark Karpov  Distributed under BSD 3 clause license.

@@ -1,7 +1,7 @@ name:                 parser-combinators-version:              0.4.0-cabal-version:        >= 1.18-tested-with:          GHC==7.4.2, GHC==7.6.3, GHC==7.8.4, GHC==7.10.3, GHC==8.0.2, GHC==8.2.2+version:              1.0.0+cabal-version:        1.18+tested-with:          GHC==7.10.3, GHC==8.0.2, GHC==8.2.2, GHC==8.4.2 license:              BSD3 license-file:         LICENSE.md author:               Mark Karpov <markkarpov92@gmail.com>@@ -25,7 +25,7 @@   default:            False  library-  build-depends:      base             >= 4.5 && < 5.0+  build-depends:      base             >= 4.8 && < 5.0    if !impl(ghc >= 8.0)     build-depends:    semigroups == 0.18.*@@ -34,9 +34,16 @@                     , Control.Applicative.Combinators.NonEmpty                     , Control.Applicative.Permutations                     , Control.Monad.Combinators+                    , Control.Monad.Combinators.Expr                     , Control.Monad.Combinators.NonEmpty   if flag(dev)     ghc-options:      -Wall -Werror   else     ghc-options:      -O2 -Wall+  if flag(dev) && impl(ghc >= 8.0)+    ghc-options:      -Wcompat+                      -Wincomplete-record-updates+                      -Wincomplete-uni-patterns+                      -Wnoncanonical-monad-instances+                      -Wnoncanonical-monadfail-instances   default-language:   Haskell2010