- class (Show (ConcreteToken t), Eq (ConcreteToken t), Lift (ConcreteToken t), Eq t, Show t, Ord t, Lift t, Enumerable t) => Token t where
- type ConcreteToken t
- classify :: ConcreteToken t -> t
- enumConcreteTokens :: t -> [ConcreteToken t]
Documentation
class (Show (ConcreteToken t), Eq (ConcreteToken t), Lift (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).
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