Core contains the basic functionality of the parser library.
It defines the types and implementations of the elementary parsers and recognisers involved.
- class (Alternative p, Applicative p, ExtAlternative p) => IsParser p
- class Alternative p => ExtAlternative p where
- class Eof state where
- class Show loc => IsLocationUpdatedBy loc str where
- advance :: loc -> str -> loc
- class StoresErrors state error | state -> error where
- getErrors :: state -> ([error], state)
- class HasPosition state pos | state -> pos where
- getPos :: state -> pos
- data P st a
- data Steps a where
- type Cost = Int
- type Progress = Int
- data Nat
- type Strings = [String]
- micro :: P state a -> Int -> P state a
- amb :: P st a -> P st [a]
- pErrors :: StoresErrors st error => P st [error]
- pPos :: HasPosition st pos => P st pos
- pState :: P st st
- pEnd :: (StoresErrors st error, Eof st) => P st [error]
- pSwitch :: (st1 -> (st2, st2 -> st1)) -> P st2 a -> P st1 a
- pSymExt :: (forall a. (token -> state -> Steps a) -> state -> Steps a) -> Nat -> Maybe token -> P state token
- parse :: Eof t => P t a -> t -> a
- parse_h :: Eof t => P t a -> t -> a
- getZeroP :: P t a -> Maybe a
- getOneP :: P a b -> Maybe (P a b)
- addLength :: Int -> P st a -> P st a
- eval :: Steps a -> a
- module Control.Applicative
- module Control.Monad
In the class
IsParser we assemble the basic properties we expect parsers to have. The class itself does not have any methods.
Most properties come directly from the standard
Control.Applicative module. The class
ExtAlternative contains some extra methods we expect our parsers to have.
<<|> is the greedy version of
<|>. If its left hand side parser can
make any progress then it commits to that alternative. Can be used to make
parsers faster, and even get a complete Parsec equivalent behaviour, with
all its (dis)advantages. Intended use
p <<|> q <<|> r <|> x <|> y <?> "string". Use with care!
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 non-terminal .
<?> combinator replaces this list of symbols by the string argument.
doNotInterpret makes a parser opaque for abstract interpretation; used when permuting parsers
where we do not want to compare lengths.
must_be_non_empty checks whether its second argument
is a parser which can recognise the empty input. If so, an error message is
given using the String parameter. If not, then the third argument is
returned. This is useful in testing for illogical combinations. For its use see
the module Text.ParserCombinators.UU.Derived.
must_be_non_empties is similar to
must_be_non_empty, 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.
p can be recognized, the return value of
p is used. Otherwise,
v is used. Note that
opt by default is greedy. If you do not want
...<|> pure v instead. Furthermore,
p should not
recognise the empty string, since this would make the parser ambiguous!!
The input state may maintain a location which can be used in generating 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 this location by passing information about the part recognised. This function is typically
called in the
getErrors retrieves the correcting steps made since the last time the function was called. The result can,
by using it in a monad, be used to control how to proceed with the parsing process.
getPos retrieves the correcting steps made since the last time the function was called. The result can,
by using it as the left hand side of a monadic bind, be used to control how to proceed with the parsing process.
The parser descriptor
|Idiomatic st x (Ii -> P st x)|
|Idiomatic st f g => Idiomatic st (a -> f) (IF -> Bool -> THEN -> P st a -> ELSE -> P st a -> FI -> g)|
|Idiomatic st f g => Idiomatic st (a -> f) (P st a -> g)|
|Monad (P st)|
|Functor (P state)|
|Monad (P st) => MonadPlus (P st)|
|Functor (P state) => Applicative (P state)|
|Applicative (P state) => Alternative (P state)|
|Alternative (P st) => ExtAlternative (P st)|
|(Alternative (P st), Applicative (P st), ExtAlternative (P st)) => IsParser (P st)|
|Show (P st a)|
The progress information
The data type
Steps is the core data type around which the parsers are constructed.
It 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
which tells how much of the input state was consumed.
is used to implement the breadth-first search process, in which alternatives are
examined in a more-or-less synchronised way. The meaning of the various
constructors is as follows:
- A token was succesfully recognised, and as a result the input was
advancedby the distance
- The type of value represented by the
Stepschanges by applying the function parameter.
- A correcting step has to be 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
- 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 non-terminals. For a full description see the technical report referred to from Text.ParserCombinators.UU.README.
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-add` more than necesssary.
pErrors returns the error messages that were generated since its last call.
pEnd should be called at the end of the parsing process. It deletes any unconsumed input, turning it into error messages.
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 value of the original type.
For the second argument to
(say split) we expect the following to hold:
let (n,f) = split st in f n == st
The basic recognisers are written elsewhere (e.g. in our module Text.ParserCombinataors.UU.BasicInstances;
they (i.e. the parameter
splitState) are lifted to our
P descriptors by the function
pSymExt which also takes
the minimal number of tokens recognised by the parameter
splitState and an
Maybe value describing the possibly empty value.
shows the prototypical way of running a parser on
some specific input.
By default we use the future parser, since this gives us access to partal
result; future parsers are expected to run in less space.
Acessing and updating various components
Evaluating the online result
removes the progress information from a sequence of steps, and constructs the value embedded in it.
If you are really desparate to see how your parsers are making progress (e.g. when you have written an ambiguous parser, and you cannot find the cause of
the exponential blow-up of your parsing process), you may switch on the trace in the function
(you will need to edit the library source code).