Text.Grampa

Collection of parsing algorithms with a common interface, operating on grammars represented as records with rank-2 field types.

Parsing methods

class MultiParsing m where

Choose one of the instances of this class to parse with.

Minimal complete definition

parseComplete, parsePrefix

Associated Types

type ResultFunctor m :: * -> *

Some parser types produce a single result, others a list of results.

type GrammarConstraint m (g :: (* -> *) -> *) :: Constraint

Methods

parseComplete :: (GrammarConstraint m g, FactorialMonoid s) => g (m g s) -> s -> g (ResultFunctor m)

Given a rank-2 record of parsers and input, produce a record of parses of the complete input.

parsePrefix :: (GrammarConstraint m g, FactorialMonoid s) => g (m g s) -> s -> g (Compose (ResultFunctor m) ((,) s))

Given a rank-2 record of parsers and input, produce a record of prefix parses paired with the remaining input suffix.

Instances

MultiParsing Parser

Memoizing parser guarantees O(n²) performance, but provides no left recursion support.

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

Associated Types

type ResultFunctor (Parser :: ((* -> *) -> *) -> * -> * -> *) :: * -> *

type GrammarConstraint (Parser :: ((* -> *) -> *) -> * -> * -> *) (g :: (* -> *) -> *) :: Constraint

Methods

parseComplete :: (GrammarConstraint Parser g, FactorialMonoid s) => g (Parser g s) -> s -> g (ResultFunctor Parser)

parsePrefix :: (GrammarConstraint Parser g, FactorialMonoid s) => g (Parser g s) -> s -> g (Compose * * (ResultFunctor Parser) ((,) s))

MultiParsing Parser

Parser of general context-free grammars, including left recursion. O(n³) performance.

parseComplete :: (Rank2.Apply g, Rank2.Traversable g, FactorialMonoid s) =>
                 g (LeftRecursive.Parser g s) -> s -> g (Compose ParseResults [])

Associated Types

type ResultFunctor (Parser :: ((* -> *) -> *) -> * -> * -> *) :: * -> *

type GrammarConstraint (Parser :: ((* -> *) -> *) -> * -> * -> *) (g :: (* -> *) -> *) :: Constraint

Methods

parseComplete :: (GrammarConstraint Parser g, FactorialMonoid s) => g (Parser g s) -> s -> g (ResultFunctor Parser)

parsePrefix :: (GrammarConstraint Parser g, FactorialMonoid s) => g (Parser g s) -> s -> g (Compose * * (ResultFunctor Parser) ((,) s))

MultiParsing Parser

Parallel parser produces a list of all possible parses.

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

Associated Types

type ResultFunctor (Parser :: ((* -> *) -> *) -> * -> * -> *) :: * -> *

type GrammarConstraint (Parser :: ((* -> *) -> *) -> * -> * -> *) (g :: (* -> *) -> *) :: Constraint

Methods

parseComplete :: (GrammarConstraint Parser g, FactorialMonoid s) => g (Parser g s) -> s -> g (ResultFunctor Parser)

parsePrefix :: (GrammarConstraint Parser g, FactorialMonoid s) => g (Parser g s) -> s -> g (Compose * * (ResultFunctor Parser) ((,) s))

MultiParsing Parser

Backtracking PEG parser

parseComplete :: (Rank2.Functor g, FactorialMonoid s) =>
                 g (Backtrack.Parser g s) -> s -> g ParseResults

Associated Types

type ResultFunctor (Parser :: ((* -> *) -> *) -> * -> * -> *) :: * -> *

type GrammarConstraint (Parser :: ((* -> *) -> *) -> * -> * -> *) (g :: (* -> *) -> *) :: Constraint

Methods

parseComplete :: (GrammarConstraint Parser g, FactorialMonoid s) => g (Parser g s) -> s -> g (ResultFunctor Parser)

parsePrefix :: (GrammarConstraint Parser g, FactorialMonoid s) => g (Parser g s) -> s -> g (Compose * * (ResultFunctor Parser) ((,) s))

MultiParsing Parser

Packrat parser

parseComplete :: (Rank2.Functor g, FactorialMonoid s) =>
                 g (Packrat.Parser g s) -> s -> g ParseResults

Associated Types

type ResultFunctor (Parser :: ((* -> *) -> *) -> * -> * -> *) :: * -> *

type GrammarConstraint (Parser :: ((* -> *) -> *) -> * -> * -> *) (g :: (* -> *) -> *) :: Constraint

Methods

parseComplete :: (GrammarConstraint Parser g, FactorialMonoid s) => g (Parser g s) -> s -> g (ResultFunctor Parser)

parsePrefix :: (GrammarConstraint Parser g, FactorialMonoid s) => g (Parser g s) -> s -> g (Compose * * (ResultFunctor Parser) ((,) s))

simply :: (Only r (p (Only r) s) -> s -> Only r f) -> p (Only r) s r -> s -> f r

Apply the given parse function to the given grammar-free parser and its input.

Types

type Grammar g p s = g (p g s)

A type synonym for a fixed grammar record type g with a given parser type p on input streams of type s

type GrammarBuilder g g' p s = g (p g' s) -> g (p g' s)

A type synonym for an endomorphic function on a grammar record type g, whose parsers of type p build grammars of type g', parsing input streams of type s

type ParseResults = Either ParseFailure

data ParseFailure

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

Constructors

ParseFailure Int [String]

Instances

Eq ParseFailure

Methods

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

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

Show ParseFailure

Methods

showsPrec :: Int -> ParseFailure -> ShowS

show :: ParseFailure -> String

showList :: [ParseFailure] -> ShowS

Parser combinators and primitives

class MultiParsing m => GrammarParsing m where

Parsers that belong to this class memoize the parse results to avoid exponential performance complexity.

Minimal complete definition

nonTerminal

Associated Types

type GrammarFunctor m :: ((* -> *) -> *) -> * -> * -> *

Methods

nonTerminal :: (g (GrammarFunctor m g s) -> GrammarFunctor m g s a) -> m g s a

Used to reference a grammar production, only necessary from outside the grammar itself

selfReferring :: Distributive g => g (m g s)

Construct a grammar whose every production refers to itself.

fixGrammar :: forall g s. Distributive g => (g (m g s) -> g (m g s)) -> g (m g s)

Convert a self-referring grammar function to a grammar.

recursive :: m g s a -> m g s a

Mark a parser that relies on primitive recursion to prevent an infinite loop in fixGrammar.

Instances

GrammarParsing Parser

Associated Types

type GrammarFunctor (Parser :: ((* -> *) -> *) -> * -> * -> *) :: ((* -> *) -> *) -> * -> * -> *

Methods

nonTerminal :: (g (GrammarFunctor Parser g s) -> GrammarFunctor Parser g s a) -> Parser g s a

selfReferring :: Distributive g => g (Parser g s)

fixGrammar :: Distributive g => (g (Parser g s) -> g (Parser g s)) -> g (Parser g s)

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

GrammarParsing Parser

Associated Types

type GrammarFunctor (Parser :: ((* -> *) -> *) -> * -> * -> *) :: ((* -> *) -> *) -> * -> * -> *

Methods

nonTerminal :: (g (GrammarFunctor Parser g s) -> GrammarFunctor Parser g s a) -> Parser g s a

selfReferring :: Distributive g => g (Parser g s)

fixGrammar :: Distributive g => (g (Parser g s) -> g (Parser g s)) -> g (Parser g s)

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

GrammarParsing Parser

Associated Types

type GrammarFunctor (Parser :: ((* -> *) -> *) -> * -> * -> *) :: ((* -> *) -> *) -> * -> * -> *

Methods

nonTerminal :: (g (GrammarFunctor Parser g s) -> GrammarFunctor Parser g s a) -> Parser g s a

selfReferring :: Distributive g => g (Parser g s)

fixGrammar :: Distributive g => (g (Parser g s) -> g (Parser g s)) -> g (Parser g s)

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

class MonoidParsing m where

Methods for parsing monoidal inputs

Minimal complete definition

endOfInput, getInput, anyToken, satisfy, satisfyChar, scan, scanChars, string, takeWhile, takeWhile1, takeCharsWhile, takeCharsWhile1, whiteSpace, concatMany

Methods

endOfInput :: FactorialMonoid s => m s ()

A parser that fails on any input and succeeds at its end.

getInput :: MonoidNull s => m s s

Always sucessful parser that returns the remaining input without consuming it.

anyToken :: FactorialMonoid s => m s s

A parser that accepts any single input atom.

token :: (Eq s, FactorialMonoid s) => s -> m s s

A parser that accepts a specific input atom.

satisfy :: FactorialMonoid s => (s -> Bool) -> m s s

A parser that accepts an input atom only if it satisfies the given predicate.

satisfyChar :: TextualMonoid s => (Char -> Bool) -> m s Char

Specialization of satisfy on TextualMonoid inputs, accepting an input character only if it satisfies the given predicate.

scan :: FactorialMonoid t => s -> (s -> t -> Maybe s) -> m t t

A stateful scanner. The predicate modifies a state argument, and each transformed state is passed to successive invocations of the predicate on each token of the input until one returns Nothing or the input ends.

This parser does not fail. It will return an empty string if the predicate returns Nothing on the first character.

Note: Because this parser does not fail, do not use it with combinators such as many, because such parsers loop until a failure occurs. Careless use will thus result in an infinite loop.

scanChars :: TextualMonoid t => s -> (s -> Char -> Maybe s) -> m t t

Stateful scanner like scanChars, but specialized for TextualMonoid inputs.

string :: (FactorialMonoid s, LeftReductiveMonoid s, Show s) => s -> m s s

A parser that consumes and returns the given prefix of the input.

takeWhile :: FactorialMonoid s => (s -> Bool) -> m s s

A parser accepting the longest sequence of input atoms that match the given predicate; an optimized version of 'concatMany . satisfy'.

Note: Because this parser does not fail, do not use it with combinators such as many, because such parsers loop until a failure occurs. Careless use will thus result in an infinite loop.

takeWhile1 :: FactorialMonoid s => (s -> Bool) -> m s s

A parser accepting the longest non-empty sequence of input atoms that match the given predicate; an optimized version of 'concatSome . satisfy'.

takeCharsWhile :: TextualMonoid s => (Char -> Bool) -> m s s

Specialization of takeWhile on TextualMonoid inputs, accepting the longest sequence of input characters that match the given predicate; an optimized version of 'fmap fromString . many . satisfyChar'.

Note: Because this parser does not fail, do not use it with combinators such as many, because such parsers loop until a failure occurs. Careless use will thus result in an infinite loop.

takeCharsWhile1 :: TextualMonoid s => (Char -> Bool) -> m s s

Specialization of takeWhile1 on TextualMonoid inputs, accepting the longest sequence of input characters that match the given predicate; an optimized version of 'fmap fromString . some . satisfyChar'.

whiteSpace :: TextualMonoid s => m s ()

Consume all whitespace characters.

concatMany :: Monoid a => m s a -> m s a

Zero or more argument occurrences like many, with concatenated monoidal results.

Instances

MonoidParsing (Parser g)

Methods

endOfInput :: FactorialMonoid s => Parser g s ()

getInput :: MonoidNull s => Parser g s s

anyToken :: FactorialMonoid s => Parser g s s

token :: (Eq s, FactorialMonoid s) => s -> Parser g s s

satisfy :: FactorialMonoid s => (s -> Bool) -> Parser g s s

satisfyChar :: TextualMonoid s => (Char -> Bool) -> Parser g s Char

scan :: FactorialMonoid t => s -> (s -> t -> Maybe s) -> Parser g t t

scanChars :: TextualMonoid t => s -> (s -> Char -> Maybe s) -> Parser g t t

string :: (FactorialMonoid s, LeftReductiveMonoid s, Show s) => s -> Parser g s s

takeWhile :: FactorialMonoid s => (s -> Bool) -> Parser g s s

takeWhile1 :: FactorialMonoid s => (s -> Bool) -> Parser g s s

takeCharsWhile :: TextualMonoid s => (Char -> Bool) -> Parser g s s

takeCharsWhile1 :: TextualMonoid s => (Char -> Bool) -> Parser g s s

whiteSpace :: TextualMonoid s => Parser g s ()

concatMany :: Monoid a => Parser g s a -> Parser g s a

MonoidParsing (Parser g)

Methods

endOfInput :: FactorialMonoid s => Parser g s ()

getInput :: MonoidNull s => Parser g s s

anyToken :: FactorialMonoid s => Parser g s s

token :: (Eq s, FactorialMonoid s) => s -> Parser g s s

satisfy :: FactorialMonoid s => (s -> Bool) -> Parser g s s

satisfyChar :: TextualMonoid s => (Char -> Bool) -> Parser g s Char

scan :: FactorialMonoid t => s -> (s -> t -> Maybe s) -> Parser g t t

scanChars :: TextualMonoid t => s -> (s -> Char -> Maybe s) -> Parser g t t

string :: (FactorialMonoid s, LeftReductiveMonoid s, Show s) => s -> Parser g s s

takeWhile :: FactorialMonoid s => (s -> Bool) -> Parser g s s

takeWhile1 :: FactorialMonoid s => (s -> Bool) -> Parser g s s

takeCharsWhile :: TextualMonoid s => (Char -> Bool) -> Parser g s s

takeCharsWhile1 :: TextualMonoid s => (Char -> Bool) -> Parser g s s

whiteSpace :: TextualMonoid s => Parser g s ()

concatMany :: Monoid a => Parser g s a -> Parser g s a

MonoidParsing (Parser g)

Methods

endOfInput :: FactorialMonoid s => Parser g s ()

getInput :: MonoidNull s => Parser g s s

anyToken :: FactorialMonoid s => Parser g s s

token :: (Eq s, FactorialMonoid s) => s -> Parser g s s

satisfy :: FactorialMonoid s => (s -> Bool) -> Parser g s s

satisfyChar :: TextualMonoid s => (Char -> Bool) -> Parser g s Char

scan :: FactorialMonoid t => s -> (s -> t -> Maybe s) -> Parser g t t

scanChars :: TextualMonoid t => s -> (s -> Char -> Maybe s) -> Parser g t t

string :: (FactorialMonoid s, LeftReductiveMonoid s, Show s) => s -> Parser g s s

takeWhile :: FactorialMonoid s => (s -> Bool) -> Parser g s s

takeWhile1 :: FactorialMonoid s => (s -> Bool) -> Parser g s s

takeCharsWhile :: TextualMonoid s => (Char -> Bool) -> Parser g s s

takeCharsWhile1 :: TextualMonoid s => (Char -> Bool) -> Parser g s s

whiteSpace :: TextualMonoid s => Parser g s ()

concatMany :: Monoid a => Parser g s a -> Parser g s a

MonoidParsing (Parser g)

Methods

endOfInput :: FactorialMonoid s => Parser g s ()

getInput :: MonoidNull s => Parser g s s

anyToken :: FactorialMonoid s => Parser g s s

token :: (Eq s, FactorialMonoid s) => s -> Parser g s s

satisfy :: FactorialMonoid s => (s -> Bool) -> Parser g s s

satisfyChar :: TextualMonoid s => (Char -> Bool) -> Parser g s Char

scan :: FactorialMonoid t => s -> (s -> t -> Maybe s) -> Parser g t t

scanChars :: TextualMonoid t => s -> (s -> Char -> Maybe s) -> Parser g t t

string :: (FactorialMonoid s, LeftReductiveMonoid s, Show s) => s -> Parser g s s

takeWhile :: FactorialMonoid s => (s -> Bool) -> Parser g s s

takeWhile1 :: FactorialMonoid s => (s -> Bool) -> Parser g s s

takeCharsWhile :: TextualMonoid s => (Char -> Bool) -> Parser g s s

takeCharsWhile1 :: TextualMonoid s => (Char -> Bool) -> Parser g s s

whiteSpace :: TextualMonoid s => Parser g s ()

concatMany :: Monoid a => Parser g s a -> Parser g s a

MonoidParsing (Parser g)

Methods

endOfInput :: FactorialMonoid s => Parser g s ()

getInput :: MonoidNull s => Parser g s s

anyToken :: FactorialMonoid s => Parser g s s

token :: (Eq s, FactorialMonoid s) => s -> Parser g s s

satisfy :: FactorialMonoid s => (s -> Bool) -> Parser g s s

satisfyChar :: TextualMonoid s => (Char -> Bool) -> Parser g s Char

scan :: FactorialMonoid t => s -> (s -> t -> Maybe s) -> Parser g t t

scanChars :: TextualMonoid t => s -> (s -> Char -> Maybe s) -> Parser g t t

string :: (FactorialMonoid s, LeftReductiveMonoid s, Show s) => s -> Parser g s s

takeWhile :: FactorialMonoid s => (s -> Bool) -> Parser g s s

takeWhile1 :: FactorialMonoid s => (s -> Bool) -> Parser g s s

takeCharsWhile :: TextualMonoid s => (Char -> Bool) -> Parser g s s

takeCharsWhile1 :: TextualMonoid s => (Char -> Bool) -> Parser g s s

whiteSpace :: TextualMonoid s => Parser g s ()

concatMany :: Monoid a => Parser g s a -> Parser g s a

module Text.Parser.Char

module Text.Parser.Combinators

module Text.Parser.LookAhead