-- 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.8.2 -- | 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 Monoid (Prod r e t a) instance Functor (Prod r e t) instance Applicative (Prod r e t) instance Alternative (Prod r e t) instance Functor (Grammar r e) instance Applicative (Grammar r e) instance Monad (Grammar r e) instance MonadFix (Grammar r e) -- | 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 instance Functor (Result s e i) instance (Show e, Show i) => Show (Report e i) instance (Read e, Read i) => Read (Report e i) instance (Ord e, Ord i) => Ord (Report e i) instance (Eq e, Eq i) => Eq (Report e i) -- | 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] -- | 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 Show Associativity instance Eq Associativity