-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Linear time composable parser for PEG grammars
--   
@package frisby
@version 0.2


-- | Linear time composable parser for PEG grammars.
--   
--   frisby is a parser library that can parse arbitrary PEG grammars in
--   linear time. Unlike other parsers of PEG grammars, frisby need not be
--   supplied with all possible rules up front, allowing composition of
--   smaller parsers.
--   
--   PEG parsers are never ambiguous and allow infinite lookahead with no
--   backtracking penalty. Since PEG parsers can look ahead arbitrarily,
--   they can easily express rules such as the maximal munch rule used in
--   lexers, meaning no separate lexer is needed.
--   
--   In addition to many standard combinators, frisby provides routines to
--   translate standard regex syntax into frisby parsers.
--   
--   PEG based parsers have a number of advantages over other parsing
--   strategies:
--   
--   <ul>
--   <li>PEG parsers are never ambiguous</li>
--   <li>PEG is a generalization of regexes, they can be though of as
--   extended regexes with recursion, predicates, and ordered choice</li>
--   <li>you never need a separate lexing pass with PEG parsers, since you
--   have arbitrary lookahead there is no need to break the stream into
--   tokens to allow the limited LALR or LL lookahead to work.</li>
--   <li>things like the maximal munch and minimal munch rules are trivial
--   to specify with PEGs, yet tricky with other parsers</li>
--   <li>since you have ordered choice, things like the if then else
--   ambiguity are nonexistent.</li>
--   <li>parsers are very very fast, guaranteeing time linear in the size
--   of the input, at the cost of greater memory consumption</li>
--   <li>the ability to make local choices about whether to accept
--   something lets you write parsers that deal gracefully with errors very
--   easy to write, no more uninformative "parse error" messages</li>
--   <li>PEG parsers can be fully lazy, only as much of the input is read
--   as is needed to satisfy the demand on the output, and once the output
--   has been processed, the memory is immediately reclaimed since a PEG
--   parser never <tt>backtracks</tt></li>
--   <li>PEG parsers can deal with infinite input, acting in a streaming
--   manner</li>
--   <li>PEG parsers support predicates, letting you decide what rules to
--   follow based on whether other rules apply, so you can have rules that
--   match only if another rule does not match, or a rule that matches only
--   if two other rules both match the same input.</li>
--   </ul>
--   
--   Traditionally, PEG parsers have suffered from two major flaws:
--   
--   <ul>
--   <li>A global table of all productions must be generated or written by
--   hand, disallowing composable parsers implemented as libraries and in
--   general requiring the use of a parser generator tool like
--   <tt>pappy</tt></li>
--   <li>Although memory consumption is linear in the size of the input,
--   the constant factor is very large.</li>
--   </ul>
--   
--   frisby attempts to address both these concerns.
--   
--   frisby parsers achieve composability by having a <tt>compilation</tt>
--   pass, recursive parsers are specified using the recursive do notation
--   'mdo' which builds up a description of your parser where the recursive
--   calls for which memoized entries must be made are explicit. then
--   <a>runPeg</a> takes this description and compiles it into a form that
--   can be applied, during this compilation step it examines your composed
--   parser, and collects the global table of rules needed for a packrat
--   parser to work.
--   
--   Memory consumption is much less of an issue on modern machines; tests
--   show it is not a major concern, however frisby uses a couple of
--   techniques for reducing the impact. First it attempts to create
--   parsers that are as lazy as possible -- this means that no more of the
--   file is read into memory than is needed, and more importantly, memory
--   used by the parser can be reclaimed as you process its output.
--   
--   frisby also attempts to <tt>optimize</tt> your parser, using
--   specialized strategies when allowed to reduce the number of entries in
--   your memoization tables.
--   
--   frisby attempts to be lazy in reading the results of parsers, parsers
--   tend to work via sending out 'feeler' predicates to get an idea of
--   what the rest of the file looks like before deciding what pass to
--   take, frisby attempts to optimize these feeler predicates via extra
--   lazyness such that they do not cause the actual computation of the
--   results, but rather just compute enough to determine whether a
--   predicate would have succeeded or not.
--   
--   (It is interesting to note that the memory efficiency of frisby
--   depends vitally on being as lazy as possible, in contrast to
--   traditional thoughts when it comes to memory consumption)
--   
--   frisby is a work in progress, it has a darcs repo at
--   <a>http://repetae.net/repos/frisby</a> which may be browsed at
--   <a>http://repetae.net/dw/darcsweb.cgi?r=frisby;a=summary</a>
--   
--   And its homepage is at <a>http://repetae.net/computer/frisby</a>
--   
--   To learn more about PEG parsers, see this paper
--   <a>http://pdos.csail.mit.edu/~baford/packrat/popl04</a> and Bryan
--   Ford's packrat parsing page
--   <a>http://pdos.csail.mit.edu/~baford/packrat/</a>
module Text.Parsers.Frisby
data P s a
data PM s a

-- | Create a new rule, which may be used recursively and caches its
--   results.
--   
--   This is intended to be use in an 'mdo' block. such as the following.
--   
--   <pre>
--   additive = mdo
--       additive &lt;- newRule $ multitive &lt;&gt; char '+' -&gt;&gt; additive ## uncurry (+) // multitive
--       multitive &lt;- newRule $ primary &lt;&gt; char '*' -&gt;&gt; multitive ## uncurry (*) // primary
--       primary &lt;- newRule $ char '(' -&gt;&gt; additive &lt;&lt;- char ')' // decimal
--       decimal &lt;- newRule $ many1 (oneOf ['0' .. '9']) ## read
--       return additive
--   </pre>
--   
--   All recursive calls must be bound via a rule. Left recursion should be
--   avoided.
newRule :: P s a -> PM s (P s a)

-- | Run a PEG grammar. Takes the rank-2 argument in order to ensure a rule
--   created in one PM session isn't returned and used in another PEG
--   parser.
--   
--   There is no need for special error handling, as it can be trivially
--   implemented via
--   
--   <pre>
--   -- parse complete file, returning 'Nothing' if parse fails
--   fmap Just (myParser &lt;&lt;- eof) // unit Nothing
--   </pre>
--   
--   There is also no need for the parser to return its unused input, as
--   that can be retrieved via <a>rest</a>.
--   
--   <pre>
--   -- Now this returns (a,String) where String is the unconsumed input.
--   myParser &lt;&gt; rest
--   </pre>
runPeg :: (forall s. PM s (P s a)) -> String -> a

-- | Ordered choice, try left argument, if it fails try the right one. This
--   does not introduce any backtracking or penalty.
(//) :: P s a -> P s a -> P s a

-- | Match first argument, then match the second, returning both in a tuple
(<>) :: P s a -> P s b -> P s (a, b)

-- | Match a pair of lists and concatenate them
(<++>) :: P s [a] -> P s [a] -> P s [a]

-- | Match first argument, then match the second, returning only the value
--   on the right.
--   
--   <pre>
--   x -&gt;&gt; y = x &lt;&gt; y ## snd
--   </pre>
(->>) :: P s a -> P s b -> P s b

-- | Match first argument, then match the second, returning only the value
--   on the left.
--   
--   <pre>
--   x &lt;&lt;- y = x &lt;&gt; y ## fst
--   </pre>
(<<-) :: P s a -> P s b -> P s a

-- | Ordered choice, try left argument, if it fails then return right
--   argument.
(//>) :: P s a -> a -> P s a

-- | Map a parser through a function. a fancy version of <a>fmap</a>.
(##) :: P s a -> (a -> b) -> P s b

-- | Parse left argument and return the right argument.
(##>) :: P s a -> b -> P s b

-- | Match any character, fails on EOF
anyChar :: P s Char

-- | am at the beginning of the string.
bof :: P s ()

-- | am at the end of string.
eof :: P s ()

-- | Get current position in file as number of characters since the
--   beginning.
getPos :: P s Int

-- | Match a specified character
char :: Char -> P s Char

-- | Match any character other than the ones in the list.
noneOf :: [Char] -> P s Char

-- | Match one of the set of characters.
oneOf :: [Char] -> P s Char

-- | Match some text
text :: String -> P s String

-- | Return a value, always succeeds
unit :: a -> P s a

-- | Immediately consume and return the rest of the input equivalent to
--   (many anyChar), but more efficient.
rest :: P s String

-- | Throw away the result of something.
--   
--   <pre>
--   discard p = p -&gt;&gt; unit ()
--   </pre>
discard :: P s a -> P s ()

-- | Fails, is identity of (//) and unit of (&lt;&gt;).
parseFailure :: P s a

-- | Parse something and return it, but do not advance the input stream.
peek :: P s a -> P s a

-- | Succeeds when the argument does not.
doesNotMatch :: P s a -> P s ()

-- | always succeeds, returning true if it consumed something.
isMatch :: P s a -> P s Bool

-- | Succeed only if thing parsed passes a predicate.
onlyIf :: P s a -> (a -> Bool) -> P s a

-- | Succeeds when the argument does, but consumes no input. Equivalant to
--   p -&gt; discard (peek p)
matches :: P s a -> P s ()

-- | Parse many of something. Behaves like * in regexes. This eats as much
--   as it possibly can, if you want a minimal much rule, then use
--   <a>manyUntil</a> which stops when a.
many :: P s a -> P s [a]

-- | Match one or more of something via maximal munch rule.
many1 :: P s a -> P s [a]

-- | Parse many of something via the minimal munch rule. behaves like *? in
--   perl regexes. The final item is not consumed.
manyUntil :: P s b -> P s a -> PM s (P s [a])

-- | Equivalent to
--   
--   <pre>
--   between open close thing = open -&gt;&gt; thing &lt;&lt;- close
--   </pre>
between :: P s a -> P s b -> P s c -> P s c

-- | First matching parse wins, a simple iteration of (//).
choice :: [P s a] -> P s a

-- | Parse something if you can, else return first value
--   
--   <pre>
--   option a p = p // unit a
--   </pre>
option :: a -> P s a -> P s a

-- | Parse something if you can, discarding it.
--   
--   <pre>
--   option a p = discard p // unit ()
--   </pre>
optional :: P s a -> P s ()

-- | Create a new regular expression matching parser. it returns something
--   in a possibly failing monad to indicate an error in the regular
--   expression itself.
newRegex :: Monad m => String -> m (PM s (P s String))

-- | Make a new regex but abort on an error in the regex string itself.
regex :: String -> PM s (P s String)

-- | Show a representation of the parsed regex, mainly for debugging.
showRegex :: String -> IO ()
instance Eq Token
instance Ord Token
instance Num Token
instance Show Token
instance Ix Token
instance Monad (PM s)
instance MonadFix (PM s)
instance Functor (PM s)
instance Functor (P s)
instance Applicative (P s)
instance Alternative (P s)
instance Monoid (P s a)
instance Show Regex
instance Eq Regex
instance Ord Regex
instance Functor Results
instance Monoid (PE a)
instance Alternative PE
instance Applicative PE
instance Functor PE
instance Applicative (PM s)


-- | Unicode character parsers. The character classification is identical
--   to the classification in the <a>Data.Char</a> module.
module Text.Parsers.Frisby.Char

-- | Match a control character.
control :: P s Char

-- | Match a white-space character in the Latin-1 range.
space :: P s Char

-- | Match a lower-case alphabetic Unicode character.
lower :: P s Char

-- | Match an upper-case or title-case alphabetic Unicode character.
upper :: P s Char

-- | Match an alphabetic Unicode character. Equivalent to <a>letter</a>.
alpha :: P s Char

-- | Match an alphabetic or numeric digit Unicode character.
alphaNum :: P s Char

-- | Match a printable Unicode character.
printable :: P s Char

-- | Match an ASCII digit.
digit :: P s Char

-- | Match an ASCII octal digit.
octDigit :: P s Char

-- | Match an ASCII hexadecimal digit.
hexDigit :: P s Char

-- | Match an alphabetic Unicode character. Equivalent to <a>alpha</a>.
letter :: P s Char

-- | Match a Unicode mark character.
mark :: P s Char

-- | Match a Unicode numeric character.
number :: P s Char

-- | Match a Unicode punctuation character.
punctuation :: P s Char

-- | Match a Unicode symbol character.
symbol :: P s Char

-- | Match a Unicode space or separator character.
separator :: P s Char

-- | Match a character of the ASCII character set.
ascii :: P s Char

-- | Match a character of the ISO 8859-1 (Latin-1) character set.
latin1 :: P s Char

-- | Match an ASCII upper-case letter.
asciiUpper :: P s Char

-- | Match an ASCII lower-case letter.
asciiLower :: P s Char