Text.Grampa.ContextFree.SortedMemoizing

A context-free memoizing parser that handles all alternatives in parallel.

Documentation

data ParseFailure pos s

A ParseFailure contains the offset of the parse failure and the list of things expected at that offset.

Constructors

ParseFailure

Fields

• failurePosition :: pos
• expectedAlternatives :: [FailureDescription s]

  expected input alternatives

• errorAlternatives :: [FailureDescription s]

  erroneous input descriptions

Instances

Functor (ParseFailure pos)

Defined in Text.Grampa.Class

Methods

fmap :: (a -> b) -> ParseFailure pos a -> ParseFailure pos b

(<$) :: a -> ParseFailure pos b -> ParseFailure pos a

(Eq pos, Eq s) => Eq (ParseFailure pos s)

Defined in Text.Grampa.Class

Methods

(==) :: ParseFailure pos s -> ParseFailure pos s -> Bool

(/=) :: ParseFailure pos s -> ParseFailure pos s -> Bool

(Show pos, Show s) => Show (ParseFailure pos s)

Defined in Text.Grampa.Class

Methods

showsPrec :: Int -> ParseFailure pos s -> ShowS

show :: ParseFailure pos s -> String

showList :: [ParseFailure pos s] -> ShowS

(Ord pos, Ord s) => Semigroup (ParseFailure pos s)

Defined in Text.Grampa.Class

Methods

(<>) :: ParseFailure pos s -> ParseFailure pos s -> ParseFailure pos s

sconcat :: NonEmpty (ParseFailure pos s) -> ParseFailure pos s

stimes :: Integral b => b -> ParseFailure pos s -> ParseFailure pos s

Ord s => Monoid (ParseFailure Pos s)

Defined in Text.Grampa.Class

Methods

mempty :: ParseFailure Pos s

mappend :: ParseFailure Pos s -> ParseFailure Pos s -> ParseFailure Pos s

mconcat :: [ParseFailure Pos s] -> ParseFailure Pos s

data ResultList g s r

Constructors

ResultList ![ResultsOfLength g s r] !(ParseFailure Pos s)

Instances

Functor (ResultList g s)

Defined in Text.Grampa.Internal

Methods

fmap :: (a -> b) -> ResultList g s a -> ResultList g s b

(<$) :: a -> ResultList g s b -> ResultList g s a

Ord s => Applicative (ResultList g s)

Defined in Text.Grampa.Internal

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

Ord s => Alternative (ResultList g s)

Defined in Text.Grampa.Internal

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]

Show s => Show1 (ResultList g s)

Defined in Text.Grampa.Internal

Methods

liftShowsPrec :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> ResultList g s a -> ShowS

liftShowList :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> [ResultList g s a] -> ShowS

Filterable (ResultList g s)

Defined in Text.Grampa.Internal

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

(Show s, Show r) => Show (ResultList g s r)

Defined in Text.Grampa.Internal

Methods

showsPrec :: Int -> ResultList g s r -> ShowS

show :: ResultList g s r -> String

showList :: [ResultList g s r] -> ShowS

Ord s => Semigroup (ResultList g s r)

Defined in Text.Grampa.Internal

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

Ord s => Monoid (ResultList g s r)

Defined in Text.Grampa.Internal

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

newtype Parser g s r

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

Ord s => Monad (Parser g s)

Defined in Text.Grampa.ContextFree.SortedMemoizing

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

Functor (Parser g i)

Defined in Text.Grampa.ContextFree.SortedMemoizing

Methods

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

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

Ord s => MonadFail (Parser g s)

Defined in Text.Grampa.ContextFree.SortedMemoizing

Methods

fail :: String -> Parser g s a

Ord s => Applicative (Parser g s)

Defined in Text.Grampa.ContextFree.SortedMemoizing

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

Ord s => Alternative (Parser g s)

Defined in Text.Grampa.ContextFree.SortedMemoizing

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 => MonadPlus (Parser g s)

Defined in Text.Grampa.ContextFree.SortedMemoizing

Methods

mzero :: Parser g s a

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

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

Defined in Text.Grampa.ContextFree.SortedMemoizing

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 ()

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

Defined in Text.Grampa.ContextFree.SortedMemoizing

Associated Types

type ParserInput (Parser g s)

type ParserPosition (Parser g s)

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) => InputCharParsing (Parser g s)

Defined in Text.Grampa.ContextFree.SortedMemoizing

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) => ConsumedInputParsing (Parser g s)

Defined in Text.Grampa.ContextFree.SortedMemoizing

Methods

match :: Parser g s a -> Parser g s (ParserInput (Parser g s), a)

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

Defined in Text.Grampa.ContextFree.SortedMemoizing

Methods

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

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

Defined in Text.Grampa.ContextFree.SortedMemoizing

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)

Defined in Text.Grampa.ContextFree.SortedMemoizing

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 ()

Filterable (Parser g s)

Defined in Text.Grampa.ContextFree.SortedMemoizing

Methods

mapMaybe :: (a -> Maybe b) -> Parser g s a -> Parser g s b

catMaybes :: Parser g s (Maybe a) -> Parser g s a

filter :: (a -> Bool) -> Parser g s a -> Parser g s a

Ord s => CommittedParsing (Parser g s)

Defined in Text.Grampa.ContextFree.SortedMemoizing

Associated Types

type CommittedResults (Parser g s) :: Type -> Type

Methods

commit :: Parser g s a -> Parser g s (CommittedResults (Parser g s) a)

admit :: Parser g s (CommittedResults (Parser g s) a) -> Parser g s a

Ord s => AmbiguousParsing (Parser g s)

Defined in Text.Grampa.ContextFree.SortedMemoizing

Methods

ambiguous :: Parser g s a -> Parser g s (Ambiguous a)

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

Memoizing parser guarantees O(n²) performance for grammars with unambiguous productions. Can be wrapped with Fixed to provide left recursion support.

Defined in Text.Grampa.ContextFree.SortedMemoizing

Associated Types

type ParserGrammar (Parser g s) :: (Type -> Type) -> Type

type GrammarFunctor (Parser g s) :: Type -> Type

Methods

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

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

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

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)

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

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

Memoizing parser guarantees O(n²) performance for grammars with unambiguous productions. Can be wrapped with Fixed to provide left recursion support.

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

Defined in Text.Grampa.ContextFree.SortedMemoizing

Associated Types

type ResultFunctor (Parser g s) :: Type -> Type

type GrammarConstraint (Parser g s) g

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))

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))

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

Defined in Text.Grampa.ContextFree.SortedMemoizing

Methods

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

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

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

Defined in Text.Grampa.ContextFree.SortedMemoizing

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

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

Defined in Text.Grampa.ContextFree.SortedMemoizing

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

type ParserPosition (Parser g s)

Defined in Text.Grampa.ContextFree.SortedMemoizing

type ParserPosition (Parser g s) = Down Int

type ParserInput (Parser g s)

Defined in Text.Grampa.ContextFree.SortedMemoizing

type ParserInput (Parser g s) = s

type CommittedResults (Parser g s)

Defined in Text.Grampa.ContextFree.SortedMemoizing

type CommittedResults (Parser g s) = ParseResults s

type ParserGrammar (Parser g s)

Defined in Text.Grampa.ContextFree.SortedMemoizing

type ParserGrammar (Parser g s) = g

type GrammarFunctor (Parser g s)

Defined in Text.Grampa.ContextFree.SortedMemoizing

type GrammarFunctor (Parser g s) = ResultList g s

type ResultFunctor (Parser g s)

Defined in Text.Grampa.ContextFree.SortedMemoizing

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

type GrammarConstraint (Parser g s) g'

Defined in Text.Grampa.ContextFree.SortedMemoizing

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

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

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

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

terminalPEG :: Monoid s => Ord s => Parser g s a -> Parser g s a

Turns a backtracking PEG parser into a context-free parser