Provides
Eof
Location
 The triples containg a history, a future parser and a recogniser:
T
 Triples are Applicative:
,<*>
,<*
and*>
pure
 Triples are Applicative:
 The descriptor
of a parser, including the tupled parser corresponding to this descriptorP
 Additional useful combinators
 Maintaining Progress Information
 Auxiliary functions and types
 Checking for nonsensical combinations:
andmust_be_non_empty
must_be_non_empties
 The type
for describing the minimal number of tokens consumedNat
 Checking for nonsensical combinations:
The module Core
contains the basic functionality of the parser library.
It uses the breadthfirst module to realise online generation of results, the error
correction administration, dealing with ambigous grammars; it defines the types of the elementary parsers
and recognisers involved.For typical use cases of the libray see the module Text.ParserCombinators.UU.Examples
 class Provides state symbol token  state symbol > token where
 splitState :: symbol > (token > state > Steps a) > state > Steps a
 class Eof state where
 eof :: state > Bool
 deleteAtEnd :: state > Maybe (Cost, state)
 class Show loc => IsLocationUpdatedBy loc str where
 advance :: loc > str > loc
 class ExtAlternative p where
 (<<>) :: p a > p a > p a
 data T st a = T (forall r. (a > st > Steps r) > st > Steps r) (forall r. (st > Steps r) > st > Steps (a, r)) (forall r. (st > Steps r) > st > Steps r)
 data P st a = P (T st a) (Maybe (T st a)) Nat (Maybe a)
 mkParser :: Maybe (T st a) > Maybe a > T st a
 pSymExt :: Provides state symbol token => Nat > Maybe token > symbol > P state token
 pSym :: Provides state symbol token => symbol > P state token
 (<?>) :: P state a > String > P state a
 micro :: P state a > Int > P state a
 amb :: P st a > P st [a]
 class Stores state error  state > error where
 getErrors :: state > ([error], state)
 pErrors :: Stores st error => P st [error]
 class HasPosition state pos  state > pos where
 getPos :: state > pos
 pPos :: HasPosition st pos => P st pos
 pEnd :: (Stores st error, Eof st) => P st [error]
 parse :: Eof t => P t a > t > a
 pSwitch :: (st1 > (st2, st2 > st1)) > P st2 a > P st1 a
 type Cost = Int
 type Progress = Int
 type Strings = [String]
 data Steps a where
 eval :: Steps a > a
 push :: v > Steps r > Steps (v, r)
 apply :: Steps (b > a, (b, r)) > Steps (a, r)
 pushapply :: (b > a) > Steps (b, r) > Steps (a, r)
 norm :: Steps a > Steps a
 best :: Steps a > Steps a > Steps a
 best' :: Steps b > Steps b > Steps b
 getCheapest :: Int > [(Int, Steps a)] > Steps a
 traverse :: Int > Steps a > Int > Int > Int
 removeEnd_h :: Steps (a, r) > Steps r
 removeEnd_f :: Steps r > Steps [r]
 must_be_non_empty :: [Char] > P t t1 > t2 > t2
 must_be_non_empties :: [Char] > P t1 t > P t3 t2 > t4 > t4
 data Nat
 nat_min :: Nat > Nat > Int > (Nat, Bool)
 module Control.Applicative
Provides
class Provides state symbol token  state symbol > token whereSource
The function splitState
playes a crucial role in splitting up the state. The symbol
parameter tells us what kind of thing, and even which value of that kind, is expected from the input.
The state and and the symbol type together determine what kind of token has to be returned. Since the function is overloaded we do not have to invent
all kind of different names for our elementary parsers.
splitState :: symbol > (token > state > Steps a) > state > Steps aSource
(Eq a, Show a, IsLocationUpdatedBy loc a) => Provides (Str a loc) a a  
(Show a, Eq a, IsLocationUpdatedBy loc [a]) => Provides (Str a loc) (Token a) [a]  
(Show a, IsLocationUpdatedBy loc [a]) => Provides (Str a loc) (Munch a) [a]  
(Ord a, Show a, IsLocationUpdatedBy loc a) => Provides (Str a loc) (a, a) a  
(Show a, IsLocationUpdatedBy loc a) => Provides (Str a loc) (a > Bool, String, a) a 
Eof
Location
class Show loc => IsLocationUpdatedBy loc str whereSource
The input state may contain a location which can be used in error messages. Since we do not want to fix our input to be just a String
we provide an interface
which can be used to advance the location by passing its information in the function splitState
class ExtAlternative p whereSource
In order to be able to describe greedy parsers we introduce an extra operator, whch indicates a biased choice
ExtAlternative Maybe  
ExtAlternative (P st) 

The triples containg a history, a future parser and a recogniser: T
T
T (forall r. (a > st > Steps r) > st > Steps r) (forall r. (st > Steps r) > st > Steps (a, r)) (forall r. (st > Steps r) > st > Steps r) 
Functor (T st)  
Applicative (T state)  
Alternative (T state) 
Triples are Applicative: <*>
, <*
, *>
and pure
<*>
<*
*>
pure
The descriptor P
of a parser, including the tupled parser corresponding to this descriptor
P
Monad (P st)  
Functor (P state)  
MonadPlus (P st)  
Applicative (P state)  
Alternative (P state)  
ExtAlternative (P st) 

Show (P st a) 
Parsers are functors: fmap
fmap
Parsers are Applicative: <*>
, <*
, *>
and pure
<*>
<*
*>
pure
Parsers are Alternative: <>
and empty
<>
empty
An alternative for the Alternative, which is greedy: <<>
<<>
Parsers can recognise single tokens: pSym
and pSymExt
pSym
pSymExt
pSymExt :: Provides state symbol token => Nat > Maybe token > symbol > P state tokenSource
Since pSymExt
is overloaded both the type and the value of a symbol
determine how to decompose the input in a token
and the remaining input.
pSymExt
takes two extra parameters: the first describing the minimal number of tokens recognised,
and the second telling whether the symbol can recognise the empty string and the value which is to be returned in that case
pSym :: Provides state symbol token => symbol > P state tokenSource
covers the most common case of recognsiing a symbol: a single token is removed form the input,
and it cannot recognise the empty string
pSym
Parsers are Monads: >>=
and return
>>=
return
Additional useful combinators
(<?>) :: P state a > String > P state aSource
The parsers build a list of symbols which are expected at a specific point.
This list is used to report errors.
Quite often it is more informative to get e.g. the name of the nonterminal.
The
combinator replaces this list of symbols by it's righhand side argument.
<?>
class Stores state error  state > error whereSource
getErrors
retreives the correcting steps made since the last time the function was called. The result can,
using a monad, be used to control how to proceed with the parsing process.
class HasPosition state pos  state > pos whereSource
retreives the correcting steps made since the last time the function was called. The result can,
using a monad, be used to control how to proceed with the parsing process.
pPos
HasPosition (Str a loc) loc 
pPos :: HasPosition st pos => P st posSource
pEnd :: (Stores st error, Eof st) => P st [error]Source
The function pEnd
should be called at the end of the parsing process. It deletes any unconsumed input, turning them into error messages
pSwitch :: (st1 > (st2, st2 > st1)) > P st2 a > P st1 aSource
takes the current state and modifies it to a different type of state to which its argument parser is applied.
The second component of the result is a function which converts the remaining state of this parser back into a valuee of the original type.
For the second argumnet to pSwitch
(say split) we expect the following to hold:
pSwitch
let (n,f) = split st in f n to be equal to st
Maintaining Progress Information
The data type
is the core data type around which the parsers are constructed.
It is a describes a tree structure of streams containing (in an interleaved way) both the online result of the parsing process,
and progress information. Recognising an input token should correspond to a certain amount of Steps
,
which tells how much of the input state was consumed.
The Progress
is used to implement the breadthfirst search process, in which alternatives are
examined in a moreorless synchonised way. The meaning of the various Progress
constructors is as follows:
Step
Step
 A token was succesfully recognised, and as a result the input was
advanced
by the distanceProgress
Apply
 The type of value represented by the
Steps
changes by applying the function parameter. Fail
 A correcting step has to made to the input; the first parameter contains information about what was expected in the input,
and the second parameter describes the various corrected alternatives, each with an associated
Cost
Micro
 A small cost is inserted in the sequence, which is used to disambiguate. Use with care!
The last two alternatives play a role in recognising ambigous nonterminals. For a full description see the technical report referred to from the README file..
norm :: Steps a > Steps aSource
makes sure that the head of the seqeunce contains progress information. It does so by pushing information about the result (i.e. the norm
Apply
steps) backwards.
removeEnd_h :: Steps (a, r) > Steps rSource
removeEnd_f :: Steps r > Steps [r]Source
Auxiliary functions and types
Checking for nonsensical combinations: must_be_non_empty
and must_be_non_empties
must_be_non_empty
must_be_non_empties
must_be_non_empty :: [Char] > P t t1 > t2 > t2Source
The function checks wehther its second argument is a parser which can recognise the mety sequence. If so an error message is given using the name of the context. If not then the third argument is returned. This is useful in testing for loogical combinations. For its use see the module Text>parserCombinators.UU.Derived
must_be_non_empties :: [Char] > P t1 t > P t3 t2 > t4 > t4Source
This function is similar to the above, but can be used in situations where we recognise a sequence of elements separated by other elements. This does not make sense if both parsers can recognise the empty string. Your grammar is then highly ambiguous.
The type Nat
for describing the minimal number of tokens consumed
Nat
The data type
is used to represent the minimal length of a parser.
Care should be taken in order to not evaluate the right hand side of the binary function Nat
`natadd`
more than necesssary.
module Control.Applicative