EarleyM

Monadic combinators for Earley Parsing

Grammars, Non-terminals, Productions

data Gram a

Type of grammars. RHS of a production rules. Synthesizing values of type a. Monadic construction allows context-sensitive grammars.

Instances

Monad Gram

Functor Gram

Applicative Gram

alts :: [Gram a] -> Gram a

Grammar constructed from a list of alteratives. Alternations may be nested; we are not restricted to just having alternate productions for a given non-terminal.

fail :: Gram a

Grammar constructed from no alteratives. fail == alts []

many :: Gram a -> Gram [a]

Grammar for kleene *. Constructs an infinite RHS. Use in preference to right-recursion via a non-terminal, which has quadratic inefficiency.

skipWhile :: Gram () -> Gram ()

Kleene * which ignores the synthesized value. skipWhile p == do _ <- many p; return ()

data Lang t a

Type for language definition over terminals (tokens) of type t. A collection of production rules together with an entry point. Constructed monadically.

Instances

Monad (Lang t)

Functor (Lang t)

Applicative (Lang t)

getToken :: Lang t (Gram t)

Access to the grammar for tokens within a language definition.

data NT a

Type of non-terminals. LHS of a production rules. Carrying values of type a.

Instances

Show (NT a)

createNamedNT :: Show a => String -> Lang t (NT a)

Create a fresh non-terminal within a language definition. The name is only used for debugging and reporting ambiguity. This is a low level primitive. Simpler to use declare.

referenceNT :: NT a -> Gram a

Reference a non-terminal on the RHS of a production. This is a low level primitive. Simpler to use declare.

declare :: Show a => String -> Lang t (NT a, Gram a)

Convenience combination of createNamedNT and referenceNT, returning a pair of values for a fresh non-terminal, for use on the LHS/RHS.

produce :: NT a -> Gram a -> Lang t ()

Define a language production, linking the LHS and RHS of the rule.

fix :: Show a => String -> (Gram a -> Lang t (Gram a)) -> Lang t (Gram a)

Combination of declare/produce to allow reference to a grammar within its own defintion. Use this for language with left-recursion.

Parsing

data Parsing a

Result of running a parsing function: parse or parseAmb. Combines the outcome with the effort taken.

Constructors

Parsing

Fields

effort :: Eff

outcome :: a

Instances

Functor Parsing

data SyntaxError

Type describing a syntax-error encountered during parsing. In all cases the final position reached before the error is reported. This position is automatically determined by the Early parsing algorithm.

Constructors

UnexpectedTokenAt Pos

UnexpectedEOF Pos

ExpectedEOF Pos

Instances

Eq SyntaxError

Show SyntaxError

parseAmb :: (Show a, Show t) => Lang t (Gram a) -> [t] -> Parsing (Either SyntaxError [a])

Entry-point to run a parse. Allows ambiguity. Parses a list of tokens using a Lang/Gram definition. Returns all parses or a syntax-error.

data Ambiguity

Type describing a parse ambiguity for a specific non-terminal (name), across a position range. This may be reported as an error by the parse entry point.

Constructors

Ambiguity String Pos Pos

Instances

Eq Ambiguity

Show Ambiguity

data ParseError

Union of SyntaxError and Ambiguity, for reporting errors from parse.

Constructors

SyntaxError SyntaxError

AmbiguityError Ambiguity

Instances

Eq ParseError

Show ParseError

parse :: (Show a, Show t) => Lang t (Gram a) -> [t] -> Parsing (Either ParseError a)

Entry-point to run a parse. Rejects ambiguity. Parse a list of tokens using a Lang/Gram definition. Returns the single parse or a parse-error.

newtype Eff

Type to represent the effort taken during parsing. Used by some unit-tests.

Constructors

Eff Int

Instances

Show Eff

type Pos = Int

Type of positions. Used in parse error reports. Indicates the index of the input token list reached before the error was encountered.