grammar-combinators-0.1: A parsing library of context-free grammar combinators.




class (Show (ConcreteToken t), Eq (ConcreteToken t), Eq t, Show t, Ord t, Lift t, Enumerable t) => Token t whereSource

The Token class identifies a type that can be used as terminal identifier in a grammar definition. The type t itself is an abstract identifier, identifying a certain type of terminals, but any value of type t can correspond to a possibly infinite numer of values of type 'ConcreteToken t'. For example, if you use a lexer in a simple arithmetic expressions grammar, your lexer would typically return values like PLUS, MINUS, but also 'INTEGER 42' when a number is lexed. In this case, a separate Token type t would be defined, such that a value INTEGER_T of the Token type t could correspond to all values of the form 'INTEGER n' (for n an Integer) of type 'ConcreteToken t'. A production rule defined as token INTEGER_T would then produce result values of type ConcreteToken t (e.g. INTEGER 42).

The requirements on Token types are relatively strict, but this is necessary to make it usable in table-based parser algorithms. We reference the Lift class to allow for compile-time precalculation of tables using Template Haskell (See the LL1 and RealLL1 parsers).

Note that in some cases it is inefficient to use Char directly as token type, because of the big amount of tokens. For example when using transformLeftCorner, the new domain will contain O(n*t + n^2) non-terminals where n is the amount of non-terminals and t is th number of tokens, so when using this transformation, it is beneficial to use a token type with less token values than Char, at least if you will use algorithms that fold over the full new grammar's domain (e.g. printGrammar does, printReachableGrammar doesn't).

Associated Types

type ConcreteToken t Source


classify :: ConcreteToken t -> tSource

The classify function classifies a given ConcreteToken t into the value of type t it is represented by.

enumConcreteTokens :: t -> [ConcreteToken t]Source

The enumConcreteTokens function returns a (possibly infinite) list of all concrete tokens of type 'ConcreteToken t' corresponding to a given token of Token type t