-- Hoogle documentation, generated by Haddock -- See Hoogle, http://www.haskell.org/hoogle/ -- | Parsing all context-free grammars using Earley's algorithm. -- -- See https://www.github.com/ollef/Earley for more information -- and https://github.com/ollef/Earley/tree/master/examples for -- examples. @package Earley @version 0.9.0 -- | Context-free grammars. module Text.Earley.Grammar -- | A production. -- -- The type parameters are: -- -- a: The return type of the production. -- -- t: The type of the terminals that the production operates on. -- -- e: The type of names, used for example to report expected -- tokens. -- -- r: The type of a non-terminal. This plays a role similar to -- the s in the type ST s a. Since the parser -- function expects the r to be universally quantified, there is -- not much to do with this parameter other than leaving it universally -- quantified. -- -- As an example, Prod r String Char -- Int is the type of a production that returns an -- Int, operates on (lists of) characters and reports -- String names. -- -- Most of the functionality of Prods is obtained through its -- instances, e.g. Functor, Applicative, and -- Alternative. data Prod r e t a Terminal :: !(t -> Bool) -> !(Prod r e t (t -> b)) -> Prod r e t b NonTerminal :: !(r e t a) -> !(Prod r e t (a -> b)) -> Prod r e t b Pure :: a -> Prod r e t a Alts :: ![Prod r e t a] -> !(Prod r e t (a -> b)) -> Prod r e t b Many :: !(Prod r e t a) -> !(Prod r e t ([a] -> b)) -> Prod r e t b Named :: !(Prod r e t a) -> e -> Prod r e t a -- | Match a token that satisfies the given predicate. Returns the matched -- token. satisfy :: (t -> Bool) -> Prod r e t t -- | A named production (used for reporting expected things). () :: Prod r e t a -> e -> Prod r e t a -- | A context-free grammar. -- -- The type parameters are: -- -- a: The return type of the grammar (often a Prod). -- -- e: The type of names, used for example to report expected -- tokens. -- -- r: The type of a non-terminal. This plays a role similar to -- the s in the type ST s a. Since the parser -- function expects the r to be universally quantified, there is -- not much to do with this parameter other than leaving it universally -- quantified. -- -- Most of the functionality of Grammars is obtained through its -- instances, e.g. Monad and MonadFix. Note that GHC has -- syntactic sugar for MonadFix: use {-# LANGUAGE RecursiveDo -- #-} and mdo instead of do. data Grammar r e a RuleBind :: Prod r e t a -> (Prod r e t a -> Grammar r e b) -> Grammar r e b FixBind :: (a -> Grammar r e a) -> (a -> Grammar r e b) -> Grammar r e b Return :: a -> Grammar r e a -- | Create a new non-terminal by giving its production. rule :: Prod r e t a -> Grammar r e (Prod r e t a) instance GHC.Base.Monoid (Text.Earley.Grammar.Prod r e t a) instance GHC.Base.Functor (Text.Earley.Grammar.Prod r e t) instance GHC.Base.Applicative (Text.Earley.Grammar.Prod r e t) instance GHC.Base.Alternative (Text.Earley.Grammar.Prod r e t) instance GHC.Base.Functor (Text.Earley.Grammar.Grammar r e) instance GHC.Base.Applicative (Text.Earley.Grammar.Grammar r e) instance GHC.Base.Monad (Text.Earley.Grammar.Grammar r e) instance Control.Monad.Fix.MonadFix (Text.Earley.Grammar.Grammar r e) -- | Derived operators. module Text.Earley.Derived -- | Match a single token. symbol :: Eq t => t -> Prod r e t t -- | Match a single token and give it the name of the token. namedSymbol :: Eq t => t -> Prod r t t t -- | Match a list of tokens in sequence. word :: Eq t => [t] -> Prod r e t [t] -- | This module exposes the internals of the package: its API may change -- independently of the PVP-compliant version number. module Text.Earley.Internal -- | The concrete rule type that the parser uses data Rule s r e t a Rule :: ProdR s r e t a -> !(STRef s (Maybe [a])) -> !(STRef s (STRef s [Cont s r e t a r])) -> Rule s r e t a [ruleProd] :: Rule s r e t a -> ProdR s r e t a [ruleNullable] :: Rule s r e t a -> !(STRef s (Maybe [a])) [ruleConts] :: Rule s r e t a -> !(STRef s (STRef s [Cont s r e t a r])) type ProdR s r e t a = Prod (Rule s r) e t a nullable :: Rule s r e t a -> ST s [a] nullableProd :: ProdR s r e t a -> ST s [a] resetConts :: Rule s r e t a -> ST s () -- | If we have something of type f, Args s f a is -- what we need to do to f to produce as. type Args s f a = f -> ST s [a] noArgs :: Args s a a funArg :: (f -> a) -> Args s f a pureArg :: x -> Args s f a -> Args s (x -> f) a pureArgs :: [x] -> Args s f a -> Args s (x -> f) a impureArgs :: ST s [x] -> Args s f a -> Args s (x -> f) a mapArgs :: (a -> b) -> Args s f a -> Args s f b composeArgs :: Args s a b -> Args s b c -> Args s a c type Pos = Int -- | An Earley state with result type a. data State s r e t a State :: !Pos -> !(ProdR s r e t f) -> !(Args s f b) -> !(Conts s r e t b a) -> State s r e t a Final :: f -> Args s f a -> State s r e t a -- | A continuation accepting an a and producing a b. data Cont s r e t a b Cont :: !Pos -> !(Args s a b) -> !(ProdR s r e t (b -> c)) -> !(Args s c d) -> !(Conts s r e t d e') -> Cont s r e t a e' FinalCont :: Args s a c -> Cont s r e t a c data Conts s r e t a c Conts :: !(STRef s [Cont s r e t a c]) -> !(STRef s (Maybe (STRef s (ST s [a])))) -> Conts s r e t a c [conts] :: Conts s r e t a c -> !(STRef s [Cont s r e t a c]) [contsArgs] :: Conts s r e t a c -> !(STRef s (Maybe (STRef s (ST s [a])))) newConts :: STRef s [Cont s r e t a c] -> ST s (Conts s r e t a c) contraMapCont :: Args s b a -> Cont s r e t a c -> Cont s r e t b c contToState :: ST s [a] -> Cont s r e t a c -> State s r e t c -- | Strings of non-ambiguous continuations can be optimised by removing -- indirections. simplifyCont :: Conts s r e t b a -> ST s [Cont s r e t b a] -- | Interpret an abstract Grammar. grammar :: Grammar (Rule s r) e a -> ST s a -- | Given a grammar, construct an initial state. initialState :: ProdR s a e t a -> ST s (State s a e t a) -- | A parsing report, which contains fields that are useful for presenting -- errors to the user if a parse is deemed a failure. Note however that -- we get a report even when we successfully parse something. data Report e i Report :: Int -> [e] -> i -> Report e i -- | The final position in the input (0-based) that the parser reached. [position] :: Report e i -> Int -- | The named productions processed at the final position. [expected] :: Report e i -> [e] -- | The part of the input string that was not consumed, which may be -- empty. [unconsumed] :: Report e i -> i -- | The result of a parse. data Result s e i a -- | The parser ended. Ended :: (Report e i) -> Result s e i a -- | The parser parsed a number of as. These are given as a -- computation, ST s [a] that constructs the as -- when run. We can thus save some work by ignoring this computation if -- we do not care about the results. The Int is the position in -- the input where these results were obtained, the i the rest -- of the input, and the last component is the continuation. Parsed :: (ST s [a]) -> Int -> i -> (ST s (Result s e i a)) -> Result s e i a safeHead :: ListLike i t => i -> Maybe t safeTail :: ListLike i t => i -> i data ParseEnv s e i t a ParseEnv :: ![ST s [a]] -> ![State s a e t a] -> !(ST s ()) -> ![e] -> !Pos -> !i -> ParseEnv s e i t a -- | Results ready to be reported (when this position has been processed) [results] :: ParseEnv s e i t a -> ![ST s [a]] -- | States to process at the next position [next] :: ParseEnv s e i t a -> ![State s a e t a] -- | Computation that resets the continuation refs of productions [reset] :: ParseEnv s e i t a -> !(ST s ()) -- | Named productions encountered at this position [names] :: ParseEnv s e i t a -> ![e] -- | The current position in the input string [pos] :: ParseEnv s e i t a -> !Pos -- | The input string [input] :: ParseEnv s e i t a -> !i emptyParseEnv :: i -> ParseEnv s e i t a -- | The internal parsing routine parse :: ListLike i t => [State s a e t a] -> ParseEnv s e i t a -> ST s (Result s e i a) -- | Create a parser from the given grammar. parser :: ListLike i t => (forall r. Grammar r e (Prod r e t a)) -> i -> ST s (Result s e i a) -- | Return all parses from the result of a given parser. The result may -- contain partial parses. The Ints are the position at which a -- result was produced. allParses :: (forall s. ST s (Result s e i a)) -> ([(a, Int)], Report e i) -- | Return all parses that reached the end of the input from the result of -- a given parser. fullParses :: ListLike i t => (forall s. ST s (Result s e i a)) -> ([a], Report e i) -- | See e.g. how far the parser is able to parse the input string before -- it fails. This can be much faster than getting the parse results for -- highly ambiguous grammars. report :: ListLike i t => (forall s. ST s (Result s e i a)) -> Report e i instance GHC.Base.Functor (Text.Earley.Internal.Result s e i) instance (GHC.Show.Show e, GHC.Show.Show i) => GHC.Show.Show (Text.Earley.Internal.Report e i) instance (GHC.Read.Read e, GHC.Read.Read i) => GHC.Read.Read (Text.Earley.Internal.Report e i) instance (GHC.Classes.Ord e, GHC.Classes.Ord i) => GHC.Classes.Ord (Text.Earley.Internal.Report e i) instance (GHC.Classes.Eq e, GHC.Classes.Eq i) => GHC.Classes.Eq (Text.Earley.Internal.Report e i) -- | Parsing. module Text.Earley.Parser -- | A parsing report, which contains fields that are useful for presenting -- errors to the user if a parse is deemed a failure. Note however that -- we get a report even when we successfully parse something. data Report e i Report :: Int -> [e] -> i -> Report e i -- | The final position in the input (0-based) that the parser reached. [position] :: Report e i -> Int -- | The named productions processed at the final position. [expected] :: Report e i -> [e] -- | The part of the input string that was not consumed, which may be -- empty. [unconsumed] :: Report e i -> i -- | The result of a parse. data Result s e i a -- | The parser ended. Ended :: (Report e i) -> Result s e i a -- | The parser parsed a number of as. These are given as a -- computation, ST s [a] that constructs the as -- when run. We can thus save some work by ignoring this computation if -- we do not care about the results. The Int is the position in -- the input where these results were obtained, the i the rest -- of the input, and the last component is the continuation. Parsed :: (ST s [a]) -> Int -> i -> (ST s (Result s e i a)) -> Result s e i a -- | Create a parser from the given grammar. parser :: ListLike i t => (forall r. Grammar r e (Prod r e t a)) -> i -> ST s (Result s e i a) -- | Return all parses from the result of a given parser. The result may -- contain partial parses. The Ints are the position at which a -- result was produced. allParses :: (forall s. ST s (Result s e i a)) -> ([(a, Int)], Report e i) -- | Return all parses that reached the end of the input from the result of -- a given parser. fullParses :: ListLike i t => (forall s. ST s (Result s e i a)) -> ([a], Report e i) -- | See e.g. how far the parser is able to parse the input string before -- it fails. This can be much faster than getting the parse results for -- highly ambiguous grammars. report :: ListLike i t => (forall s. ST s (Result s e i a)) -> Report e i -- | Parsing all context-free grammars using Earley's algorithm. module Text.Earley -- | A production. -- -- The type parameters are: -- -- a: The return type of the production. -- -- t: The type of the terminals that the production operates on. -- -- e: The type of names, used for example to report expected -- tokens. -- -- r: The type of a non-terminal. This plays a role similar to -- the s in the type ST s a. Since the parser -- function expects the r to be universally quantified, there is -- not much to do with this parameter other than leaving it universally -- quantified. -- -- As an example, Prod r String Char -- Int is the type of a production that returns an -- Int, operates on (lists of) characters and reports -- String names. -- -- Most of the functionality of Prods is obtained through its -- instances, e.g. Functor, Applicative, and -- Alternative. data Prod r e t a -- | Match a token that satisfies the given predicate. Returns the matched -- token. satisfy :: (t -> Bool) -> Prod r e t t -- | A named production (used for reporting expected things). () :: Prod r e t a -> e -> Prod r e t a -- | A context-free grammar. -- -- The type parameters are: -- -- a: The return type of the grammar (often a Prod). -- -- e: The type of names, used for example to report expected -- tokens. -- -- r: The type of a non-terminal. This plays a role similar to -- the s in the type ST s a. Since the parser -- function expects the r to be universally quantified, there is -- not much to do with this parameter other than leaving it universally -- quantified. -- -- Most of the functionality of Grammars is obtained through its -- instances, e.g. Monad and MonadFix. Note that GHC has -- syntactic sugar for MonadFix: use {-# LANGUAGE RecursiveDo -- #-} and mdo instead of do. data Grammar r e a -- | Create a new non-terminal by giving its production. rule :: Prod r e t a -> Grammar r e (Prod r e t a) -- | Match a single token. symbol :: Eq t => t -> Prod r e t t -- | Match a single token and give it the name of the token. namedSymbol :: Eq t => t -> Prod r t t t -- | Match a list of tokens in sequence. word :: Eq t => [t] -> Prod r e t [t] -- | A parsing report, which contains fields that are useful for presenting -- errors to the user if a parse is deemed a failure. Note however that -- we get a report even when we successfully parse something. data Report e i Report :: Int -> [e] -> i -> Report e i -- | The final position in the input (0-based) that the parser reached. [position] :: Report e i -> Int -- | The named productions processed at the final position. [expected] :: Report e i -> [e] -- | The part of the input string that was not consumed, which may be -- empty. [unconsumed] :: Report e i -> i -- | The result of a parse. data Result s e i a -- | The parser ended. Ended :: (Report e i) -> Result s e i a -- | The parser parsed a number of as. These are given as a -- computation, ST s [a] that constructs the as -- when run. We can thus save some work by ignoring this computation if -- we do not care about the results. The Int is the position in -- the input where these results were obtained, the i the rest -- of the input, and the last component is the continuation. Parsed :: (ST s [a]) -> Int -> i -> (ST s (Result s e i a)) -> Result s e i a -- | Create a parser from the given grammar. parser :: ListLike i t => (forall r. Grammar r e (Prod r e t a)) -> i -> ST s (Result s e i a) -- | Return all parses from the result of a given parser. The result may -- contain partial parses. The Ints are the position at which a -- result was produced. allParses :: (forall s. ST s (Result s e i a)) -> ([(a, Int)], Report e i) -- | Return all parses that reached the end of the input from the result of -- a given parser. fullParses :: ListLike i t => (forall s. ST s (Result s e i a)) -> ([a], Report e i) -- | See e.g. how far the parser is able to parse the input string before -- it fails. This can be much faster than getting the parse results for -- highly ambiguous grammars. report :: ListLike i t => (forall s. ST s (Result s e i a)) -> Report e i module Text.Earley.Mixfix data Associativity LeftAssoc :: Associativity NonAssoc :: Associativity RightAssoc :: Associativity -- | An identifier with identifier parts (Justs), and holes -- (Nothings) representing the positions of its arguments. -- -- Example (commonly written "if_then_else_"): [Just "if", -- Nothing, Just "then", Nothing, Just -- "else", Nothing] :: Holey String type Holey a = [Maybe a] -- | Create a grammar for parsing mixfix expressions. mixfixExpression :: [[(Holey (Prod r e t ident), Associativity)]] -> Prod r e t expr -> (Holey ident -> [expr] -> expr) -> Grammar r e (Prod r e t expr) instance GHC.Show.Show Text.Earley.Mixfix.Associativity instance GHC.Classes.Eq Text.Earley.Mixfix.Associativity