Safe Haskell	None
Language	Haskell2010

Text.Grampa.ContextFree.Memoizing

Description

A context-free parser with packrat-like memoization of parse results.

Synopsis

data ResultList (g :: (Type -> Type) -> Type) s r = ResultList !(BinTree (ResultInfo g s r)) (ParseFailure Pos s)
newtype Parser (g :: (Type -> Type) -> Type) s r = Parser {
- applyParser :: [(s, g (ResultList g s))] -> ResultList g s r
}
data BinTree a
- = Fork !(BinTree a) !(BinTree a)
- | Leaf !a
- | EmptyTree
reparseTails :: Functor g => g (Parser g s) -> [(s, g (ResultList g s))] -> [(s, g (ResultList g s))]
longest :: Parser g s a -> Parser g [(s, g (ResultList g s))] a
peg :: Ord s => Parser g [(s, g (ResultList g s))] a -> Parser g s a
terminalPEG :: forall s (g :: (Type -> Type) -> Type) a. (Monoid s, Ord s) => Parser g s a -> Parser g s a

Documentation

data ResultList (g :: (Type -> Type) -> Type) s r Source #

Constructors

ResultList !(BinTree (ResultInfo g s r)) (ParseFailure Pos s)

Instances

Instances details

Show s => Show1 (ResultList g s) Source #
Instance details Defined in Text.Grampa.ContextFree.Memoizing Methods liftShowsPrec :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> ResultList g s a -> ShowS # liftShowList :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> [ResultList g s a] -> ShowS #
Ord s => Alternative (ResultList g s) Source #
Instance details Defined in Text.Grampa.ContextFree.Memoizing Methods empty :: ResultList g s a # (<\|>) :: ResultList g s a -> ResultList g s a -> ResultList g s a # some :: ResultList g s a -> ResultList g s [a] # many :: ResultList g s a -> ResultList g s [a] #
Ord s => Applicative (ResultList g s) Source #
Instance details Defined in Text.Grampa.ContextFree.Memoizing Methods pure :: a -> ResultList g s a # (<>) :: ResultList g s (a -> b) -> ResultList g s a -> ResultList g s b # liftA2 :: (a -> b -> c) -> ResultList g s a -> ResultList g s b -> ResultList g s c # (>) :: ResultList g s a -> ResultList g s b -> ResultList g s b # (<*) :: ResultList g s a -> ResultList g s b -> ResultList g s a #
Functor (ResultList g s) Source #
Instance details Defined in Text.Grampa.ContextFree.Memoizing Methods fmap :: (a -> b) -> ResultList g s a -> ResultList g s b # (<$) :: a -> ResultList g s b -> ResultList g s a #
Filterable (ResultList g s) Source #
Instance details Defined in Text.Grampa.ContextFree.Memoizing Methods mapMaybe :: (a -> Maybe b) -> ResultList g s a -> ResultList g s b # catMaybes :: ResultList g s (Maybe a) -> ResultList g s a # filter :: (a -> Bool) -> ResultList g s a -> ResultList g s a # drain :: ResultList g s a -> ResultList g s b #
Ord s => Monoid (ResultList g s r) Source #
Instance details Defined in Text.Grampa.ContextFree.Memoizing Methods mempty :: ResultList g s r # mappend :: ResultList g s r -> ResultList g s r -> ResultList g s r # mconcat :: [ResultList g s r] -> ResultList g s r #
Ord s => Semigroup (ResultList g s r) Source #
Instance details Defined in Text.Grampa.ContextFree.Memoizing Methods (<>) :: ResultList g s r -> ResultList g s r -> ResultList g s r # sconcat :: NonEmpty (ResultList g s r) -> ResultList g s r # stimes :: Integral b => b -> ResultList g s r -> ResultList g s r #
(Show s, Show r) => Show (ResultList g s r) Source #
Instance details Defined in Text.Grampa.ContextFree.Memoizing Methods showsPrec :: Int -> ResultList g s r -> ShowS # show :: ResultList g s r -> String # showList :: [ResultList g s r] -> ShowS #

newtype Parser (g :: (Type -> Type) -> Type) s r Source #

Parser for a context-free grammar with packrat-like sharing of parse results. It does not support left-recursive grammars.

Constructors

Parser
Fields applyParser :: [(s, g (ResultList g s))] -> ResultList g s r

Instances

Instances details

Ord s => MonadFail (Parser g s) Source #

Instance details

Defined in Text.Grampa.ContextFree.Memoizing

Methods

fail :: String -> Parser g s a #

Ord s => Alternative (Parser g s) Source #

Instance details

Defined in Text.Grampa.ContextFree.Memoizing

Methods

empty :: Parser g s a #

(<|>) :: Parser g s a -> Parser g s a -> Parser g s a #

some :: Parser g s a -> Parser g s [a] #

many :: Parser g s a -> Parser g s [a] #

Ord s => Applicative (Parser g s) Source #

Instance details

Defined in Text.Grampa.ContextFree.Memoizing

Methods

pure :: a -> Parser g s a #

(<*>) :: Parser g s (a -> b) -> Parser g s a -> Parser g s b #

liftA2 :: (a -> b -> c) -> Parser g s a -> Parser g s b -> Parser g s c #

(*>) :: Parser g s a -> Parser g s b -> Parser g s b #

(<*) :: Parser g s a -> Parser g s b -> Parser g s a #

Functor (Parser g i) Source #

Instance details

Defined in Text.Grampa.ContextFree.Memoizing

Methods

fmap :: (a -> b) -> Parser g i a -> Parser g i b #

(<$) :: a -> Parser g i b -> Parser g i a #

Ord s => Monad (Parser g s) Source #

Instance details

Defined in Text.Grampa.ContextFree.Memoizing

Methods

(>>=) :: Parser g s a -> (a -> Parser g s b) -> Parser g s b #

(>>) :: Parser g s a -> Parser g s b -> Parser g s b #

return :: a -> Parser g s a #

Ord s => MonadPlus (Parser g s) Source #

Instance details

Defined in Text.Grampa.ContextFree.Memoizing

Methods

mzero :: Parser g s a #

mplus :: Parser g s a -> Parser g s a -> Parser g s a #

(Ord s, LeftReductive s, FactorialMonoid s) => GrammarParsing (Parser g s) Source #

Instance details

Defined in Text.Grampa.ContextFree.Memoizing

Associated Types

type ParserGrammar (Parser g s)
Instance details Defined in Text.Grampa.ContextFree.Memoizing type ParserGrammar (Parser g s) = g
type GrammarFunctor (Parser g s)
Instance details Defined in Text.Grampa.ContextFree.Memoizing type GrammarFunctor (Parser g s) = ResultList g s

Methods

parsingResult :: ParserInput (Parser g s) -> GrammarFunctor (Parser g s) a -> ResultFunctor (Parser g s) (ParserInput (Parser g s), a) Source #

nonTerminal :: (g0 ~ ParserGrammar (Parser g s), GrammarConstraint (Parser g s) g0) => (g0 (GrammarFunctor (Parser g s)) -> GrammarFunctor (Parser g s) a) -> Parser g s a Source #

selfReferring :: (g0 ~ ParserGrammar (Parser g s), GrammarConstraint (Parser g s) g0, Distributive g0) => g0 (Parser g s) Source #

fixGrammar :: (g0 ~ ParserGrammar (Parser g s), GrammarConstraint (Parser g s) g0, Distributive g0) => (g0 (Parser g s) -> g0 (Parser g s)) -> g0 (Parser g s) Source #

recursive :: Parser g s a -> Parser g s a Source #

chainRecursive :: (g0 ~ ParserGrammar (Parser g s), f ~ GrammarFunctor (Parser g s), GrammarConstraint (Parser g s) g0) => (f a -> g0 f -> g0 f) -> Parser g s a -> Parser g s a -> Parser g s a Source #

chainLongestRecursive :: (g0 ~ ParserGrammar (Parser g s), f ~ GrammarFunctor (Parser g s), GrammarConstraint (Parser g s) g0) => (f a -> g0 f -> g0 f) -> Parser g s a -> Parser g s a -> Parser g s a Source #

(LeftReductive s, FactorialMonoid s, Ord s) => MultiParsing (Parser g s) Source #

Memoizing parser guarantees O(n²) performance for grammars with unambiguous productions, but provides no left recursion support.

parseComplete :: (Rank2.Functor g, FactorialMonoid s) =>
                 g (Memoizing.Parser g s) -> s -> g (Compose (ParseResults s) [])

Instance details

Defined in Text.Grampa.ContextFree.Memoizing

Associated Types

type ResultFunctor (Parser g s)
Instance details Defined in Text.Grampa.ContextFree.Memoizing type ResultFunctor (Parser g s) = Compose (ParseResults s) []

Methods

parseComplete :: (ParserInput (Parser g s) ~ s0, GrammarConstraint (Parser g s) g0, Eq s0, FactorialMonoid s0) => g0 (Parser g s) -> s0 -> g0 (ResultFunctor (Parser g s)) Source #

parsePrefix :: (ParserInput (Parser g s) ~ s0, GrammarConstraint (Parser g s) g0, Eq s0, FactorialMonoid s0) => g0 (Parser g s) -> s0 -> g0 (Compose (ResultFunctor (Parser g s)) ((,) s0)) Source #

InputParsing (Parser g s) => TraceableParsing (Parser g s) Source #

Instance details

Defined in Text.Grampa.ContextFree.Memoizing

Methods

traceInput :: (ParserInput (Parser g s) -> String) -> Parser g s a -> Parser g s a Source #

traceAs :: Show (ParserInput (Parser g s)) => String -> Parser g s a -> Parser g s a Source #

(MonoidNull s, Ord s) => DeterministicParsing (Parser g s) Source #

Instance details

Defined in Text.Grampa.ContextFree.Memoizing

Methods

(<<|>) :: Parser g s a -> Parser g s a -> Parser g s a #

takeOptional :: Parser g s a -> Parser g s (Maybe a) #

takeMany :: Parser g s a -> Parser g s [a] #

takeSome :: Parser g s a -> Parser g s [a] #

concatAll :: Monoid a => Parser g s a -> Parser g s a #

skipAll :: Parser g s a -> Parser g s () #

(Ord s, Show s, TextualMonoid s) => InputCharParsing (Parser g s) Source #

Instance details

Defined in Text.Grampa.ContextFree.Memoizing

Methods

satisfyCharInput :: (Char -> Bool) -> Parser g s (ParserInput (Parser g s)) #

notSatisfyChar :: (Char -> Bool) -> Parser g s () #

scanChars :: state -> (state -> Char -> Maybe state) -> Parser g s (ParserInput (Parser g s)) #

takeCharsWhile :: (Char -> Bool) -> Parser g s (ParserInput (Parser g s)) #

takeCharsWhile1 :: (Char -> Bool) -> Parser g s (ParserInput (Parser g s)) #

(LeftReductive s, FactorialMonoid s, Ord s) => InputParsing (Parser g s) Source #

Instance details

Defined in Text.Grampa.ContextFree.Memoizing

Associated Types

type ParserInput (Parser g s)
Instance details Defined in Text.Grampa.ContextFree.Memoizing type ParserInput (Parser g s) = s
type ParserPosition (Parser g s)
Instance details Defined in Text.Grampa.ContextFree.Memoizing type ParserPosition (Parser g s) = Down Int

Methods

getInput :: Parser g s (ParserInput (Parser g s)) #

getSourcePos :: Parser g s (ParserPosition (Parser g s)) #

anyToken :: Parser g s (ParserInput (Parser g s)) #

take :: Int -> Parser g s (ParserInput (Parser g s)) #

satisfy :: (ParserInput (Parser g s) -> Bool) -> Parser g s (ParserInput (Parser g s)) #

notSatisfy :: (ParserInput (Parser g s) -> Bool) -> Parser g s () #

scan :: state -> (state -> ParserInput (Parser g s) -> Maybe state) -> Parser g s (ParserInput (Parser g s)) #

string :: ParserInput (Parser g s) -> Parser g s (ParserInput (Parser g s)) #

takeWhile :: (ParserInput (Parser g s) -> Bool) -> Parser g s (ParserInput (Parser g s)) #

takeWhile1 :: (ParserInput (Parser g s) -> Bool) -> Parser g s (ParserInput (Parser g s)) #

(Ord s, Show s, TextualMonoid s) => CharParsing (Parser g s) Source #

Instance details

Defined in Text.Grampa.ContextFree.Memoizing

Methods

satisfy :: (Char -> Bool) -> Parser g s Char #

char :: Char -> Parser g s Char #

notChar :: Char -> Parser g s Char #

anyChar :: Parser g s Char #

string :: String -> Parser g s String #

text :: Text -> Parser g s Text #

(MonoidNull s, Ord s) => Parsing (Parser g s) Source #

Instance details

Defined in Text.Grampa.ContextFree.Memoizing

Methods

try :: Parser g s a -> Parser g s a #

(<?>) :: Parser g s a -> String -> Parser g s a #

skipMany :: Parser g s a -> Parser g s () #

skipSome :: Parser g s a -> Parser g s () #

unexpected :: String -> Parser g s a #

eof :: Parser g s () #

notFollowedBy :: Show a => Parser g s a -> Parser g s () #

(MonoidNull s, Ord s) => LookAheadParsing (Parser g s) Source #

Instance details

Defined in Text.Grampa.ContextFree.Memoizing

Methods

lookAhead :: Parser g s a -> Parser g s a #

Filterable (Parser g i) Source #

Instance details

Defined in Text.Grampa.ContextFree.Memoizing

Methods

mapMaybe :: (a -> Maybe b) -> Parser g i a -> Parser g i b #

catMaybes :: Parser g i (Maybe a) -> Parser g i a #

filter :: (a -> Bool) -> Parser g i a -> Parser g i a #

drain :: Parser g i a -> Parser g i b #

(Monoid x, Ord s) => Monoid (Parser g s x) Source #

Instance details

Defined in Text.Grampa.ContextFree.Memoizing

Methods

mempty :: Parser g s x #

mappend :: Parser g s x -> Parser g s x -> Parser g s x #

mconcat :: [Parser g s x] -> Parser g s x #

(Semigroup x, Ord s) => Semigroup (Parser g s x) Source #

Instance details

Defined in Text.Grampa.ContextFree.Memoizing

Methods

(<>) :: Parser g s x -> Parser g s x -> Parser g s x #

sconcat :: NonEmpty (Parser g s x) -> Parser g s x #

stimes :: Integral b => b -> Parser g s x -> Parser g s x #

type GrammarFunctor (Parser g s) Source #

Instance details

Defined in Text.Grampa.ContextFree.Memoizing

type GrammarFunctor (Parser g s) = ResultList g s

type ParserGrammar (Parser g s) Source #

Instance details

Defined in Text.Grampa.ContextFree.Memoizing

type ParserGrammar (Parser g s) = g

type ResultFunctor (Parser g s) Source #

Instance details

Defined in Text.Grampa.ContextFree.Memoizing

type ResultFunctor (Parser g s) = Compose (ParseResults s) []

type ParserInput (Parser g s) Source #

Instance details

Defined in Text.Grampa.ContextFree.Memoizing

type ParserInput (Parser g s) = s

type ParserPosition (Parser g s) Source #

Instance details

Defined in Text.Grampa.ContextFree.Memoizing

type ParserPosition (Parser g s) = Down Int

type GrammarConstraint (Parser g s) g' Source #

Instance details

Defined in Text.Grampa.ContextFree.Memoizing

type GrammarConstraint (Parser g s) g' = (g ~ g', Functor g)

data BinTree a Source #

Constructors

Fork !(BinTree a) !(BinTree a)
Leaf !a
EmptyTree

Instances

Instances details

Foldable BinTree Source #
Instance details Defined in Text.Grampa.Internal Methods fold :: Monoid m => BinTree m -> m # foldMap :: Monoid m => (a -> m) -> BinTree a -> m # foldMap' :: Monoid m => (a -> m) -> BinTree a -> m # foldr :: (a -> b -> b) -> b -> BinTree a -> b # foldr' :: (a -> b -> b) -> b -> BinTree a -> b # foldl :: (b -> a -> b) -> b -> BinTree a -> b # foldl' :: (b -> a -> b) -> b -> BinTree a -> b # foldr1 :: (a -> a -> a) -> BinTree a -> a # foldl1 :: (a -> a -> a) -> BinTree a -> a # toList :: BinTree a -> [a] # null :: BinTree a -> Bool # length :: BinTree a -> Int # elem :: Eq a => a -> BinTree a -> Bool # maximum :: Ord a => BinTree a -> a # minimum :: Ord a => BinTree a -> a # sum :: Num a => BinTree a -> a # product :: Num a => BinTree a -> a #
Traversable BinTree Source #
Instance details Defined in Text.Grampa.Internal Methods traverse :: Applicative f => (a -> f b) -> BinTree a -> f (BinTree b) # sequenceA :: Applicative f => BinTree (f a) -> f (BinTree a) # mapM :: Monad m => (a -> m b) -> BinTree a -> m (BinTree b) # sequence :: Monad m => BinTree (m a) -> m (BinTree a) #
Applicative BinTree Source #
Instance details Defined in Text.Grampa.Internal Methods pure :: a -> BinTree a # (<>) :: BinTree (a -> b) -> BinTree a -> BinTree b # liftA2 :: (a -> b -> c) -> BinTree a -> BinTree b -> BinTree c # (>) :: BinTree a -> BinTree b -> BinTree b # (<*) :: BinTree a -> BinTree b -> BinTree a #
Functor BinTree Source #
Instance details Defined in Text.Grampa.Internal Methods fmap :: (a -> b) -> BinTree a -> BinTree b # (<$) :: a -> BinTree b -> BinTree a #
Filterable BinTree Source #
Instance details Defined in Text.Grampa.Internal Methods mapMaybe :: (a -> Maybe b) -> BinTree a -> BinTree b # catMaybes :: BinTree (Maybe a) -> BinTree a # filter :: (a -> Bool) -> BinTree a -> BinTree a # drain :: BinTree a -> BinTree b #
Monoid (BinTree a) Source #
Instance details Defined in Text.Grampa.Internal Methods mempty :: BinTree a # mappend :: BinTree a -> BinTree a -> BinTree a # mconcat :: [BinTree a] -> BinTree a #
Semigroup (BinTree a) Source #
Instance details Defined in Text.Grampa.Internal Methods (<>) :: BinTree a -> BinTree a -> BinTree a # sconcat :: NonEmpty (BinTree a) -> BinTree a # stimes :: Integral b => b -> BinTree a -> BinTree a #
Show a => Show (BinTree a) Source #
Instance details Defined in Text.Grampa.Internal Methods showsPrec :: Int -> BinTree a -> ShowS # show :: BinTree a -> String # showList :: [BinTree a] -> ShowS #

reparseTails :: Functor g => g (Parser g s) -> [(s, g (ResultList g s))] -> [(s, g (ResultList g s))] Source #

longest :: Parser g s a -> Parser g [(s, g (ResultList g s))] a Source #

Turns a context-free parser into a backtracking PEG parser that consumes the longest possible prefix of the list of input tails, opposite of peg

peg :: Ord s => Parser g [(s, g (ResultList g s))] a -> Parser g s a Source #

Turns a backtracking PEG parser of the list of input tails into a context-free parser, opposite of longest

terminalPEG :: forall s (g :: (Type -> Type) -> Type) a. (Monoid s, Ord s) => Parser g s a -> Parser g s a Source #

Turns a backtracking PEG parser into a context-free parser