packages feed

uu-tc (empty) → 2009.2.2

raw patch · 16 files changed

+1012/−0 lines, 16 filesdep +basesetup-changed

Dependencies added: base

Files

+ LICENSE view
@@ -0,0 +1,27 @@+Copyright (c) 2009 Andres Loeh++All rights reserved.++Redistribution and use in source and binary forms, with or without+modification, are permitted provided that the following conditions+are met:+1. Redistributions of source code must retain the above copyright+   notice, this list of conditions and the following disclaimer.+2. Redistributions in binary form must reproduce the above copyright+   notice, this list of conditions and the following disclaimer in the+   documentation and/or other materials provided with the distribution.+3. Neither the name of the author nor the names of his contributors+   may be used to endorse or promote products derived from this software+   without specific prior written permission.++THIS SOFTWARE IS PROVIDED BY THE AUTHORS ``AS IS'' AND+ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE+IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE+ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHORS OR CONTRIBUTORS BE LIABLE+FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL+DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS+OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)+HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT+LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY+OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF+SUCH DAMAGE.
+ Setup.hs view
@@ -0,0 +1,3 @@+import Distribution.Simple++main = defaultMain
+ src/ParseLib.hs view
@@ -0,0 +1,7 @@+module ParseLib+  (+    module ParseLib.Simple+  )+  where++import ParseLib.Simple
+ src/ParseLib/Abstract.hs view
@@ -0,0 +1,9 @@+module ParseLib.Abstract+  (+    module ParseLib.Abstract.Derived,+    module ParseLib.Abstract.Applications+  )+  where++import ParseLib.Abstract.Derived+import ParseLib.Abstract.Applications
+ src/ParseLib/Abstract/Applications.hs view
@@ -0,0 +1,50 @@+module ParseLib.Abstract.Applications+  (+    -- * Applications of elementary parsers+    digit,+    newdigit,+    natural,+    integer,+    identifier,+    parenthesised,+    bracketed,+    braced,+    commaList,+    semiList+  )+  where++import Data.Char+import ParseLib.Abstract.Core+import ParseLib.Abstract.Derived++digit  :: Parser Char Char+digit  =  satisfy isDigit++newdigit :: Parser Char Int+newdigit = read . (:[]) <$> digit++natural :: Parser Char Int+natural = foldl (\ a b -> a * 10 + b) 0 <$> many1 newdigit++integer :: Parser Char Int+integer = (const negate <$> (symbol '-')) `option` id  <*>  natural ++identifier :: Parser Char String+identifier = (:) <$> satisfy isAlpha <*> greedy (satisfy isAlphaNum)++parenthesised :: Parser Char a -> Parser Char a+parenthesised p = pack (symbol '(') p (symbol ')')++bracketed :: Parser Char a -> Parser Char a+bracketed p = pack (symbol '[') p (symbol ']')++braced :: Parser Char a -> Parser Char a+braced p = pack (symbol '{') p (symbol '}')++commaList :: Parser Char a -> Parser Char [a]+commaList p = listOf p (symbol ',')++semiList :: Parser Char a -> Parser Char [a]+semiList p = listOf p (symbol ';')+
+ src/ParseLib/Abstract/Core.hs view
@@ -0,0 +1,85 @@+module ParseLib.Abstract.Core+  (+    -- * The type of parsers+    Parser(),+    -- * Elementary parsers+    anySymbol,+    satisfy,+    empty, failp,+    succeed, pure,+    -- * Parser combinators+    (<|>),+    (<<|>),+    (<*>),+    (<$>),+    (>>=),+    -- * Lookahead+    look,+    -- * Running parsers+    parse+  )+  where++import Data.Char+import Data.Traversable+import Data.Maybe+import Control.Monad+import Control.Applicative+import qualified ParseLib.Simple.Core as SP++-- | An input string is mapped to a list of successful parses.+-- For each succesful parse, we return the result of type 'r',+-- and the remaining input string. The input must be a list of+-- symbols.+newtype Parser s r  =  Parser { runParser :: [s] -> [(r,[s])] }++instance Functor (Parser s) where+  fmap f p  =  Parser (f SP.<$> runParser p)++instance Applicative (Parser s) where+  pure x    =  Parser (SP.succeed x)+  p <*> q   =  Parser (runParser p SP.<*> runParser q)++instance Alternative (Parser s) where+  empty     =  Parser SP.empty+  p <|> q   =  Parser (runParser p SP.<|> runParser q)++infixr 3 <<|>++-- | Biased choice. If the left hand side parser succeeds,+-- the right hand side is not considered. Use with care!+(<<|>) :: Parser s a -> Parser s a -> Parser s a+p <<|> q  =  Parser (runParser p SP.<<|> runParser q)++instance Monad (Parser s) where+  return    =  pure+  p >>= f   =  Parser (runParser p SP.>>= (runParser . f))++instance MonadPlus (Parser s) where+  mzero     =  empty+  mplus     =  (<|>)++-- | Parses any single symbol.+anySymbol :: Parser s s+anySymbol = Parser (SP.anySymbol)++-- | Takes a predicate and returns a parser that parses a+-- single symbol satisfying that predicate.+satisfy :: (s -> Bool) -> Parser s s+satisfy p = Parser (SP.satisfy p)++-- | Parser that always succeeds, i.e., for epsilon.+succeed :: a -> Parser s a+succeed = pure++-- | Same as 'empty'; provided for compatibility with the lecture notes.+failp :: Parser s a+failp = empty++-- | Returns the rest of the input without consuming anything.+look :: Parser s [s]+look = Parser (\ xs -> [(xs, xs)])++-- | Runs a parser on a given string.+parse :: Parser s a -> [s] -> [(a,[s])]+parse = runParser
+ src/ParseLib/Abstract/Derived.hs view
@@ -0,0 +1,151 @@+module ParseLib.Abstract.Derived+  (+    module ParseLib.Abstract.Core,+    -- * Derived combinators+    (<$),+    (<*),+    (*>),+    epsilon,+    symbol,+    token,+    pack,+    sequence,+    choice,+    -- * EBNF parser combinators +    option,+    optional,+    many,+    some, many1,+    listOf,+    -- * Chain expression combinators+    chainr,+    chainl,+    -- * Greedy parsers+    greedy,+    greedy1,+    -- * End of input+    eof+  )+  where++import Prelude hiding ((>>=), sequence)+import ParseLib.Abstract.Core++infixl 4 <$+infixl 4 <*+infixl 4 *>++-- | Variant of '<$>' that ignores the result of the parser.+--+-- > f <$ p = const f <$> p+--+(<$) :: b -> Parser s a -> Parser s b+f <$ p = const f <$> p++-- | Variant of '<*>' that ignores the result of the right+-- argument.+--+-- > f <* p = const <$> p <*> q+--+(<*) :: Parser s a -> Parser s b -> Parser s a+p <* q = const <$> p <*> q++-- | Variant of '*>' that ignores the result of the left+-- argument.+--+-- > f *> p = flip const <$> p <*> q+--+(*>) :: Parser s a -> Parser s b -> Parser s b+p *> q = flip const <$> p <*> q++-- | Parser for epsilon that does return '()'.+epsilon :: Parser s ()+epsilon = succeed ()++-- | Parses a specific given symbol.+symbol :: Eq s  => s -> Parser s s+symbol x = satisfy (==x)++-- | Parses a specific given sequence of symbols.+token :: Eq s => [s] -> Parser s [s]+token []     = succeed []+token (x:xs) = (:) <$> symbol x <*> token xs++-- | Takes three parsers: a delimiter, the parser for the+-- content, and another delimiter. Constructs a sequence of+-- the three, but returns only the result of the enclosed+-- parser.+pack :: Parser s a -> Parser s b -> Parser s c -> Parser s b+pack p r q  =  p *> r <* q++-- | Takes a list of parsers and combines them in+-- sequence, returning a list of results.+sequence :: [Parser s a] -> Parser s [a]+sequence []      =  succeed []+sequence (p:ps)  =  (:) <$> p <*> sequence ps++-- | Takes a list of parsers and combines them using+-- choice.+choice :: [Parser s a] -> Parser s a+choice = foldr (<|>) empty++-- | Parses an optional element. Takes the default value+-- as its second argument.+option :: Parser s a -> a -> Parser s a+option p d = p <|> succeed d++-- | Variant of 'option' that returns a 'Maybe',+-- provided for compatibility with the applicative interface.+optional :: Parser s a -> Parser s (Maybe a)+optional p = option (Just <$> p) Nothing++-- | Parses many, i.e., zero or more, occurrences of+-- a given parser.+many :: Parser s a  -> Parser s [a]+many p  =  (:) <$> p <*> many p <|> succeed []++-- | Parser some, i.e., one or more, occurrences of+-- a given parser.+some :: Parser s a -> Parser s [a]+some p = (:) <$> p <*> many p++-- | Same as 'some'. Provided for compatibility with+-- the lecture notes.+many1 :: Parser s a -> Parser s [a]+many1 = some++-- | Takes a parser @p@ and a separator parser @s@. Parses+-- a sequence of @p@s that is separated by @s@s.+listOf :: Parser s a -> Parser s b -> Parser s [a]+listOf p s = (:) <$> p <*> many (s *> p)++-- | Takes a parser @pe@ and an operator parser @po@. Parses+-- a sequence of @pe@s separated by @po@s. The results are+-- combined using the operator associated with @po@ in a+-- right-associative way.+chainr  ::  Parser s a -> Parser s (a -> a -> a) -> Parser s a+chainr pe po  =  h <$> many (j <$> pe <*> po) <*> pe+  where j x op  =  (x `op`)+        h fs x  =  foldr ($) x fs++-- | Takes a parser @pe@ and an operator parser @po@. Parses+-- a sequence of @pe@s separated by @po@s. The results are+-- combined using the operator associated with @po@ in a+-- left-associative way.+chainl  ::  Parser s a -> Parser s (a -> a -> a) -> Parser s a+chainl pe po  =  h <$> pe <*> many (j <$> po <*> pe)+  where j op x  =  (`op` x)+        h x fs  =  foldl (flip ($)) x fs++-- | Greedy variant of 'many'.+greedy :: Parser s b -> Parser s [b]+greedy p = (:) <$> p <*> greedy p <<|> succeed []++-- | Greedy variant of 'many1'.+greedy1 :: Parser s b -> Parser s [b]+greedy1 p = (:) <$> p <*> greedy p++-- | Succeeds only on the end of the input.+eof :: Parser s ()+eof = look >>= \ xs -> if null xs then succeed () else failp+
+ src/ParseLib/Parallel.hs view
@@ -0,0 +1,9 @@+module ParseLib.Parallel+  (+    module ParseLib.Parallel.Derived,+    module ParseLib.Parallel.Applications+  )+  where++import ParseLib.Parallel.Derived+import ParseLib.Parallel.Applications
+ src/ParseLib/Parallel/Applications.hs view
@@ -0,0 +1,50 @@+module ParseLib.Parallel.Applications+  (+    -- * Applications of elementary parsers+    digit,+    newdigit,+    natural,+    integer,+    identifier,+    parenthesised,+    bracketed,+    braced,+    commaList,+    semiList+  )+  where++import Data.Char+import ParseLib.Parallel.Core+import ParseLib.Parallel.Derived++digit  :: Parser Char Char+digit  =  satisfy isDigit++newdigit :: Parser Char Int+newdigit = read . (:[]) <$> digit++natural :: Parser Char Int+natural = foldl (\ a b -> a * 10 + b) 0 <$> many1 newdigit++integer :: Parser Char Int+integer = (const negate <$> (symbol '-')) `option` id  <*>  natural ++identifier :: Parser Char String+identifier = (:) <$> satisfy isAlpha <*> greedy (satisfy isAlphaNum)++parenthesised :: Parser Char a -> Parser Char a+parenthesised p = pack (symbol '(') p (symbol ')')++bracketed :: Parser Char a -> Parser Char a+bracketed p = pack (symbol '[') p (symbol ']')++braced :: Parser Char a -> Parser Char a+braced p = pack (symbol '{') p (symbol '}')++commaList :: Parser Char a -> Parser Char [a]+commaList p = listOf p (symbol ',')++semiList :: Parser Char a -> Parser Char [a]+semiList p = listOf p (symbol ';')+
+ src/ParseLib/Parallel/Core.hs view
@@ -0,0 +1,106 @@+{-# LANGUAGE RankNTypes #-}+module ParseLib.Parallel.Core+  (+    -- * The type of parsers+    Parser(),+    -- * Elementary parsers+    anySymbol,+    satisfy,+    empty, failp,+    succeed, pure,+    -- * Parser combinators+    (<|>),+    (<<|>),+    (<*>),+    (<$>),+    (>>=),+    -- * Lookahead+    look,+    -- * Running parsers+    parse+  )+  where++import Data.Char+import Data.Traversable+import Data.Maybe+import Control.Monad+import Control.Applicative++-- | The parser is a CPS version of Parser'+newtype Parser s r  =  Parser (forall a. (r -> Parser' s a) -> Parser' s a)++runParser :: Parser s r -> (r -> Parser' s a) -> Parser' s a+runParser (Parser p) = p++data Parser' s r = SymbolBind (s -> Parser' s r)+                 | Fail+                 | ReturnPlus r (Parser' s r)+                 | LookBind ([s] -> Parser' s r)++instance Functor (Parser s) where+  fmap f p  =  p >>= \ r -> return (f r)++instance Applicative (Parser s) where+  pure x    =  return x+  p <*> q   =  p >>= \ f -> q >>= \ x -> return (f x)++instance Alternative (Parser s) where+  empty     =  mzero+  p <|> q   =  mplus p q++infixl 3 <<|>++-- | Biased choice. Not implemented by the parallel parser+-- combinators. Just maps to parallel choice.+(<<|>) :: Parser s a -> Parser s a -> Parser s a+(<<|>) = (<|>)++instance Monad (Parser s) where+  return x  =  Parser (\ k -> k x)+  p >>= f   =  Parser (\ k -> runParser p (\ x -> runParser (f x) k))++instance MonadPlus (Parser s) where+  mzero     =  Parser (\ k -> Fail)+  mplus p q =  Parser (\ k -> runParser p k +++ runParser q k)++(+++) :: Parser' s a -> Parser' s a -> Parser' s a+SymbolBind f   +++ SymbolBind g   = SymbolBind (\ x -> f x +++ g x)+Fail           +++ q              = q+p              +++ Fail           = p+ReturnPlus x p +++ q              = ReturnPlus x (p +++ q)+p              +++ ReturnPlus x q = ReturnPlus x (p +++ q)+LookBind f     +++ LookBind g     = LookBind (\ x -> f x +++ g x)+LookBind f     +++ q              = LookBind (\ x -> f x +++ q)+p              +++ LookBind g     = LookBind (\ x -> p +++ g x)++-- | Parses any single symbol.+anySymbol :: Parser s s+anySymbol = Parser (\ k -> SymbolBind k)++-- | Takes a predicate and returns a parser that parses a+-- single symbol satisfying that predicate.+satisfy :: (s -> Bool) -> Parser s s+satisfy p = anySymbol >>= \ x -> if p x then return x else mzero++-- | Parser that always succeeds, i.e., for epsilon.+succeed :: a -> Parser s a+succeed = pure++-- | Same as 'empty'; provided for compatibility with the lecture notes.+failp :: Parser s a+failp = empty++-- | Returns the rest of the input without consuming anything.+look :: Parser s [s]+look = Parser (\ k -> LookBind k)++-- | Runs a parser to a given string.+parse :: Parser s a -> [s] -> [(a,[s])]+parse p = parse' (runParser p (\ x -> ReturnPlus x Fail))++parse' :: Parser' s a -> [s] -> [(a,[s])]+parse' (SymbolBind f)    (x : xs)  =  parse' (f x) xs+parse' (ReturnPlus x p)  xs        =  (x,xs) : parse' p xs+parse' (LookBind f)      xs        =  parse' (f xs) xs+parse' _                 _         =  []
+ src/ParseLib/Parallel/Derived.hs view
@@ -0,0 +1,151 @@+module ParseLib.Parallel.Derived+  (+    module ParseLib.Parallel.Core,+    -- * Derived combinators+    (<$),+    (<*),+    (*>),+    epsilon,+    symbol,+    token,+    pack,+    sequence,+    choice,+    -- * EBNF parser combinators +    option,+    optional,+    many,+    some, many1,+    listOf,+    -- * Chain expression combinators+    chainr,+    chainl,+    -- * Greedy parsers+    greedy,+    greedy1,+    -- * End of input+    eof+  )+  where++import Prelude hiding ((>>=), sequence)+import ParseLib.Parallel.Core++infixl 4 <$+infixl 4 <*+infixl 4 *>++-- | Variant of '<$>' that ignores the result of the parser.+--+-- > f <$ p = const f <$> p+--+(<$) :: b -> Parser s a -> Parser s b+f <$ p = const f <$> p++-- | Variant of '<*>' that ignores the result of the right+-- argument.+--+-- > f <* p = const <$> p <*> q+--+(<*) :: Parser s a -> Parser s b -> Parser s a+p <* q = const <$> p <*> q++-- | Variant of '*>' that ignores the result of the left+-- argument.+--+-- > f *> p = flip const <$> p <*> q+--+(*>) :: Parser s a -> Parser s b -> Parser s b+p *> q = flip const <$> p <*> q++-- | Parser for epsilon that does return '()'.+epsilon :: Parser s ()+epsilon = succeed ()++-- | Parses a specific given symbol.+symbol :: Eq s  => s -> Parser s s+symbol x = satisfy (==x)++-- | Parses a specific given sequence of symbols.+token :: Eq s => [s] -> Parser s [s]+token []     = succeed []+token (x:xs) = (:) <$> symbol x <*> token xs++-- | Takes three parsers: a delimiter, the parser for the+-- content, and another delimiter. Constructs a sequence of+-- the three, but returns only the result of the enclosed+-- parser.+pack :: Parser s a -> Parser s b -> Parser s c -> Parser s b+pack p r q  =  p *> r <* q++-- | Takes a list of parsers and combines them in+-- sequence, returning a list of results.+sequence :: [Parser s a] -> Parser s [a]+sequence []      =  succeed []+sequence (p:ps)  =  (:) <$> p <*> sequence ps++-- | Takes a list of parsers and combines them using+-- choice.+choice :: [Parser s a] -> Parser s a+choice = foldr (<|>) empty++-- | Parses an optional element. Takes the default value+-- as its second argument.+option :: Parser s a -> a -> Parser s a+option p d = p <|> succeed d++-- | Variant of 'option' that returns a 'Maybe',+-- provided for compatibility with the applicative interface.+optional :: Parser s a -> Parser s (Maybe a)+optional p = option (Just <$> p) Nothing++-- | Parses many, i.e., zero or more, occurrences of+-- a given parser.+many :: Parser s a  -> Parser s [a]+many p  =  (:) <$> p <*> many p <|> succeed []++-- | Parser some, i.e., one or more, occurrences of+-- a given parser.+some :: Parser s a -> Parser s [a]+some p = (:) <$> p <*> many p++-- | Same as 'some'. Provided for compatibility with+-- the lecture notes.+many1 :: Parser s a -> Parser s [a]+many1 = some++-- | Takes a parser @p@ and a separator parser @s@. Parses+-- a sequence of @p@s that is separated by @s@s.+listOf :: Parser s a -> Parser s b -> Parser s [a]+listOf p s = (:) <$> p <*> many (s *> p)++-- | Takes a parser @pe@ and an operator parser @po@. Parses+-- a sequence of @pe@s separated by @po@s. The results are+-- combined using the operator associated with @po@ in a+-- right-associative way.+chainr  ::  Parser s a -> Parser s (a -> a -> a) -> Parser s a+chainr pe po  =  h <$> many (j <$> pe <*> po) <*> pe+  where j x op  =  (x `op`)+        h fs x  =  foldr ($) x fs++-- | Takes a parser @pe@ and an operator parser @po@. Parses+-- a sequence of @pe@s separated by @po@s. The results are+-- combined using the operator associated with @po@ in a+-- left-associative way.+chainl  ::  Parser s a -> Parser s (a -> a -> a) -> Parser s a+chainl pe po  =  h <$> pe <*> many (j <$> po <*> pe)+  where j op x  =  (`op` x)+        h x fs  =  foldl (flip ($)) x fs++-- | Greedy variant of 'many'.+greedy :: Parser s b -> Parser s [b]+greedy p = (:) <$> p <*> greedy p <<|> succeed []++-- | Greedy variant of 'many1'.+greedy1 :: Parser s b -> Parser s [b]+greedy1 p = (:) <$> p <*> greedy p++-- | Succeeds only on the end of the input.+eof :: Parser s ()+eof = look >>= \ xs -> if null xs then succeed () else failp+
+ src/ParseLib/Simple.hs view
@@ -0,0 +1,9 @@+module ParseLib.Simple+  (+    module ParseLib.Simple.Derived,+    module ParseLib.Simple.Applications+  )+  where++import ParseLib.Simple.Derived+import ParseLib.Simple.Applications
+ src/ParseLib/Simple/Applications.hs view
@@ -0,0 +1,50 @@+module ParseLib.Simple.Applications+  (+    -- * Applications of elementary parsers+    digit,+    newdigit,+    natural,+    integer,+    identifier,+    parenthesised,+    bracketed,+    braced,+    commaList,+    semiList+  )+  where++import Data.Char+import ParseLib.Simple.Core+import ParseLib.Simple.Derived++digit  :: Parser Char Char+digit  =  satisfy isDigit++newdigit :: Parser Char Int+newdigit = read . (:[]) <$> digit++natural :: Parser Char Int+natural = foldl (\ a b -> a * 10 + b) 0 <$> many1 newdigit++integer :: Parser Char Int+integer = (const negate <$> (symbol '-')) `option` id  <*>  natural ++identifier :: Parser Char String+identifier = (:) <$> satisfy isAlpha <*> greedy (satisfy isAlphaNum)++parenthesised :: Parser Char a -> Parser Char a+parenthesised p = pack (symbol '(') p (symbol ')')++bracketed :: Parser Char a -> Parser Char a+bracketed p = pack (symbol '[') p (symbol ']')++braced :: Parser Char a -> Parser Char a+braced p = pack (symbol '{') p (symbol '}')++commaList :: Parser Char a -> Parser Char [a]+commaList p = listOf p (symbol ',')++semiList :: Parser Char a -> Parser Char [a]+semiList p = listOf p (symbol ';')+
+ src/ParseLib/Simple/Core.hs view
@@ -0,0 +1,103 @@+module ParseLib.Simple.Core+  (+    -- * The type of parsers+    Parser,+    -- * Elementary parsers+    anySymbol,+    satisfy,+    empty, failp,+    succeed, pure,+    -- * Parser combinators +    (<|>),+    (<<|>),+    (<*>),+    (<$>),+    (>>=),+    -- * Lookahead+    look,+    -- * Running parsers+    parse+  )+  where++import Prelude hiding ((>>=))++-- | An input string is mapped to a list of successful parses.+-- For each succesful parse, we return the result of type 'r',+-- and the remaining input string. The input must be a list of+-- symbols.+type Parser s r  =  [s] -> [(r,[s])]++-- | Parses any single symbol.+anySymbol :: Parser s s+anySymbol (x:xs)  =  [(x,xs)]+anySymbol []      =  []++-- | Takes a predicate and returns a parser that parses a+-- single symbol satisfying that predicate.+satisfy  ::  (s -> Bool) -> Parser s s+satisfy p (x:xs) | p x       =  [(x,xs)]+satisfy _ _                  =  []++-- | Parser for the empty language, i.e., parser that always fails.+empty :: Parser s a+empty xs  =  []++-- | Same as 'empty'; provided for compatibility with the lecture notes.+failp :: Parser s a+failp = empty++-- | Parser that always succeeds, i.e., for epsilon.+succeed :: a -> Parser s a+succeed r xs = [(r,xs)]++-- | Same as 'succeed'; provided for compatiblity with the applicative+-- interface.+pure :: a -> Parser s a+pure = succeed++infixl 4  <$>, <*>+infixr 3  <|>, <<|>+infixl 1  >>=++-- | Choice between two parsers with the same result type.+(<|>) :: Parser s a -> Parser s a -> Parser s a+(p <|> q) xs  =  p xs ++ q xs++-- | Biased choice. If the left hand side parser succeeds,+-- the right hand side is not considered. Use with care!+(p <<|> q) xs  =  let r = p xs in if null r then q xs else r++-- | Sequence of two parsers.+(<*>) :: Parser s (b -> a) -> Parser s b -> Parser s a+(p <*> q) xs  =  [(f x,zs)+                 |(f  ,ys) <- p xs+                 ,(  x,zs) <- q ys+                 ]++-- | Map a function over the results of a parser. The '<$>' combinator+-- can also be defined in terms of 'succeed' and '<*>':+--+-- > f <$> p  =  succeed f <*> p+--+(<$>) :: (a -> b) -> Parser s a -> Parser s b+(f <$> p) xs  =  [(f y,ys)+                 |(  y,ys) <- p xs+                 ]++-- | Monadic bind. Do not use this combinator unless absolutely+-- required. Most sequencing can be done with '<*>'.+(>>=) :: Parser s a -> (a -> Parser s b) -> Parser s b+(p >>= f) xs  =  [(z  ,zs)+                 |(y  ,ys) <- p xs+                 ,(z  ,zs) <- f y ys+                 ]++-- | Returns the rest of the input without consuming anything.+look :: Parser s [s]+look xs = [(xs, xs)]++-- | For compatibility with the "newtype" version of the library:+-- runs a parser on a given string.+parse :: Parser s a -> [s] -> [(a, [s])]+parse = id
+ src/ParseLib/Simple/Derived.hs view
@@ -0,0 +1,151 @@+module ParseLib.Simple.Derived+  (+    module ParseLib.Simple.Core,+    -- * Derived combinators+    (<$),+    (<*),+    (*>),+    epsilon,+    symbol,+    token,+    pack,+    sequence,+    choice,+    -- * EBNF parser combinators +    option,+    optional,+    many,+    some, many1,+    listOf,+    -- * Chain expression combinators+    chainr,+    chainl,+    -- * Greedy parsers+    greedy,+    greedy1,+    -- * End of input+    eof+  )+  where++import Prelude hiding ((>>=), sequence)+import ParseLib.Simple.Core++infixl 4 <$+infixl 4 <*+infixl 4 *>++-- | Variant of '<$>' that ignores the result of the parser.+--+-- > f <$ p = const f <$> p+--+(<$) :: b -> Parser s a -> Parser s b+f <$ p = const f <$> p++-- | Variant of '<*>' that ignores the result of the right+-- argument.+--+-- > f <* p = const <$> p <*> q+--+(<*) :: Parser s a -> Parser s b -> Parser s a+p <* q = const <$> p <*> q++-- | Variant of '*>' that ignores the result of the left+-- argument.+--+-- > f *> p = flip const <$> p <*> q+--+(*>) :: Parser s a -> Parser s b -> Parser s b+p *> q = flip const <$> p <*> q++-- | Parser for epsilon that does return '()'.+epsilon :: Parser s ()+epsilon = succeed ()++-- | Parses a specific given symbol.+symbol :: Eq s  => s -> Parser s s+symbol x = satisfy (==x)++-- | Parses a specific given sequence of symbols.+token :: Eq s => [s] -> Parser s [s]+token []     = succeed []+token (x:xs) = (:) <$> symbol x <*> token xs++-- | Takes three parsers: a delimiter, the parser for the+-- content, and another delimiter. Constructs a sequence of+-- the three, but returns only the result of the enclosed+-- parser.+pack :: Parser s a -> Parser s b -> Parser s c -> Parser s b+pack p r q  =  p *> r <* q++-- | Takes a list of parsers and combines them in+-- sequence, returning a list of results.+sequence :: [Parser s a] -> Parser s [a]+sequence []      =  succeed []+sequence (p:ps)  =  (:) <$> p <*> sequence ps++-- | Takes a list of parsers and combines them using+-- choice.+choice :: [Parser s a] -> Parser s a+choice = foldr (<|>) empty++-- | Parses an optional element. Takes the default value+-- as its second argument.+option :: Parser s a -> a -> Parser s a+option p d = p <|> succeed d++-- | Variant of 'option' that returns a 'Maybe',+-- provided for compatibility with the applicative interface.+optional :: Parser s a -> Parser s (Maybe a)+optional p = option (Just <$> p) Nothing++-- | Parses many, i.e., zero or more, occurrences of+-- a given parser.+many :: Parser s a  -> Parser s [a]+many p  =  (:) <$> p <*> many p <|> succeed []++-- | Parser some, i.e., one or more, occurrences of+-- a given parser.+some :: Parser s a -> Parser s [a]+some p = (:) <$> p <*> many p++-- | Same as 'some'. Provided for compatibility with+-- the lecture notes.+many1 :: Parser s a -> Parser s [a]+many1 = some++-- | Takes a parser @p@ and a separator parser @s@. Parses+-- a sequence of @p@s that is separated by @s@s.+listOf :: Parser s a -> Parser s b -> Parser s [a]+listOf p s = (:) <$> p <*> many (s *> p)++-- | Takes a parser @pe@ and an operator parser @po@. Parses+-- a sequence of @pe@s separated by @po@s. The results are+-- combined using the operator associated with @po@ in a+-- right-associative way.+chainr  ::  Parser s a -> Parser s (a -> a -> a) -> Parser s a+chainr pe po  =  h <$> many (j <$> pe <*> po) <*> pe+  where j x op  =  (x `op`)+        h fs x  =  foldr ($) x fs++-- | Takes a parser @pe@ and an operator parser @po@. Parses+-- a sequence of @pe@s separated by @po@s. The results are+-- combined using the operator associated with @po@ in a+-- left-associative way.+chainl  ::  Parser s a -> Parser s (a -> a -> a) -> Parser s a+chainl pe po  =  h <$> pe <*> many (j <$> po <*> pe)+  where j op x  =  (`op` x)+        h x fs  =  foldl (flip ($)) x fs++-- | Greedy variant of 'many'.+greedy :: Parser s b -> Parser s [b]+greedy p  =  (:) <$> p <*> greedy p <<|> succeed []++-- | Greedy variant of 'many1'.+greedy1 :: Parser s b -> Parser s [b]+greedy1 p = (:) <$> p <*> greedy p++-- | Succeeds only on the end of the input.+eof :: Parser s ()+eof = look >>= \ xs -> if null xs then succeed () else failp+
+ uu-tc.cabal view
@@ -0,0 +1,51 @@+cabal-version: >= 1.6+name:          uu-tc+version:       2009.2.2+license:       BSD3+license-file:  LICENSE+author:        Andres Loeh <andres@cs.uu.nl>,+               Johan Jeuring <johanj@cs.uu.nl>,+               Doaitse Swierstra <doaitse@cs.uu.nl>+maintainer:    Jurriën Stutterheim <j.stutterheim@uu.nl>+description:+  Course software for INFOB3TC (Languages & Compilers)+  .+  This library currently contains three Haskell 98 parser combinator libraries.+  .+     * The default library, available as @ParseLib@ or more explicitly+       by importing @ParseLib.Simple@, is the one described in the+       lecture notes, using a type synonym as the type for parsers.+  .+     * The second library can be chosen by importing @ParseLib.Abstract@.+       It defines the same functions as @ParseLib.Simple@, but keeps+       the parser type abstract.++     * The third library is an implementation of Koen Claessen's+       /Parallel Parsing Processes/, available as @ParseLib.Parallel@.+  .+  In future versions of this package, more libraries with more+  advanced implementations of parser combinators may be added.++synopsis:      Haskell 98 parser combintors for INFOB3TC at Utrecht University+category:      Text, Parsing+build-type:    Simple++library+  build-depends:    base            >= 3.0   && < 5.0++  exposed-modules:  ParseLib+                    ParseLib.Simple+                    ParseLib.Simple.Core+                    ParseLib.Simple.Derived+                    ParseLib.Simple.Applications+                    ParseLib.Abstract+                    ParseLib.Abstract.Core+                    ParseLib.Abstract.Derived+                    ParseLib.Abstract.Applications+                    ParseLib.Parallel+                    ParseLib.Parallel.Core+                    ParseLib.Parallel.Derived+                    ParseLib.Parallel.Applications++  hs-source-dirs:   src+