FormalGrammars-0.3.1.2: (Context-free) grammars in formal language theory

Safe HaskellNone
LanguageHaskell2010

FormalLanguage.CFG.Grammar.Types

Description

The data types that define a CFG.

Synopsis

Documentation

newtype IndexName Source #

Constructors

IndexName 

Instances

Eq IndexName Source # 
Data IndexName Source # 

Methods

gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> IndexName -> c IndexName #

gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c IndexName #

toConstr :: IndexName -> Constr #

dataTypeOf :: IndexName -> DataType #

dataCast1 :: Typeable (* -> *) t => (forall d. Data d => c (t d)) -> Maybe (c IndexName) #

dataCast2 :: Typeable (* -> * -> *) t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c IndexName) #

gmapT :: (forall b. Data b => b -> b) -> IndexName -> IndexName #

gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> IndexName -> r #

gmapQr :: (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> IndexName -> r #

gmapQ :: (forall d. Data d => d -> u) -> IndexName -> [u] #

gmapQi :: Int -> (forall d. Data d => d -> u) -> IndexName -> u #

gmapM :: Monad m => (forall d. Data d => d -> m d) -> IndexName -> m IndexName #

gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> IndexName -> m IndexName #

gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> IndexName -> m IndexName #

Ord IndexName Source # 
Show IndexName Source # 
IsString IndexName Source # 

data IOP Source #

Constructors

IPlus 
IMinus 
IEq 
INone 
ISymbol 

Instances

Eq IOP Source # 

Methods

(==) :: IOP -> IOP -> Bool #

(/=) :: IOP -> IOP -> Bool #

Data IOP Source # 

Methods

gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> IOP -> c IOP #

gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c IOP #

toConstr :: IOP -> Constr #

dataTypeOf :: IOP -> DataType #

dataCast1 :: Typeable (* -> *) t => (forall d. Data d => c (t d)) -> Maybe (c IOP) #

dataCast2 :: Typeable (* -> * -> *) t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c IOP) #

gmapT :: (forall b. Data b => b -> b) -> IOP -> IOP #

gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> IOP -> r #

gmapQr :: (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> IOP -> r #

gmapQ :: (forall d. Data d => d -> u) -> IOP -> [u] #

gmapQi :: Int -> (forall d. Data d => d -> u) -> IOP -> u #

gmapM :: Monad m => (forall d. Data d => d -> m d) -> IOP -> m IOP #

gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> IOP -> m IOP #

gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> IOP -> m IOP #

Ord IOP Source # 

Methods

compare :: IOP -> IOP -> Ordering #

(<) :: IOP -> IOP -> Bool #

(<=) :: IOP -> IOP -> Bool #

(>) :: IOP -> IOP -> Bool #

(>=) :: IOP -> IOP -> Bool #

max :: IOP -> IOP -> IOP #

min :: IOP -> IOP -> IOP #

Show IOP Source # 

Methods

showsPrec :: Int -> IOP -> ShowS #

show :: IOP -> String #

showList :: [IOP] -> ShowS #

data Index Source #

Encode the index of the syntactic or terminal variable.

In case of grammar-based indexing, keep indexRange empty. The indexStep keeps track of any +k / -k given in the production rules.

We allow indexing terminals now, too. When glueing together terminals, one might want to be able to differentiate between terminals.

Instances

Eq Index Source # 

Methods

(==) :: Index -> Index -> Bool #

(/=) :: Index -> Index -> Bool #

Data Index Source # 

Methods

gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> Index -> c Index #

gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c Index #

toConstr :: Index -> Constr #

dataTypeOf :: Index -> DataType #

dataCast1 :: Typeable (* -> *) t => (forall d. Data d => c (t d)) -> Maybe (c Index) #

dataCast2 :: Typeable (* -> * -> *) t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c Index) #

gmapT :: (forall b. Data b => b -> b) -> Index -> Index #

gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Index -> r #

gmapQr :: (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> Index -> r #

gmapQ :: (forall d. Data d => d -> u) -> Index -> [u] #

gmapQi :: Int -> (forall d. Data d => d -> u) -> Index -> u #

gmapM :: Monad m => (forall d. Data d => d -> m d) -> Index -> m Index #

gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> Index -> m Index #

gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> Index -> m Index #

Ord Index Source # 

Methods

compare :: Index -> Index -> Ordering #

(<) :: Index -> Index -> Bool #

(<=) :: Index -> Index -> Bool #

(>) :: Index -> Index -> Bool #

(>=) :: Index -> Index -> Bool #

max :: Index -> Index -> Index #

min :: Index -> Index -> Index #

Show Index Source # 

Methods

showsPrec :: Int -> Index -> ShowS #

show :: Index -> String #

showList :: [Index] -> ShowS #

newtype SymbolName Source #

Newtype wrapper for symbol names.

Constructors

SymbolName 

Fields

Instances

Eq SymbolName Source # 
Data SymbolName Source # 

Methods

gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> SymbolName -> c SymbolName #

gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c SymbolName #

toConstr :: SymbolName -> Constr #

dataTypeOf :: SymbolName -> DataType #

dataCast1 :: Typeable (* -> *) t => (forall d. Data d => c (t d)) -> Maybe (c SymbolName) #

dataCast2 :: Typeable (* -> * -> *) t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c SymbolName) #

gmapT :: (forall b. Data b => b -> b) -> SymbolName -> SymbolName #

gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> SymbolName -> r #

gmapQr :: (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> SymbolName -> r #

gmapQ :: (forall d. Data d => d -> u) -> SymbolName -> [u] #

gmapQi :: Int -> (forall d. Data d => d -> u) -> SymbolName -> u #

gmapM :: Monad m => (forall d. Data d => d -> m d) -> SymbolName -> m SymbolName #

gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> SymbolName -> m SymbolName #

gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> SymbolName -> m SymbolName #

Ord SymbolName Source # 
Show SymbolName Source # 
IsString SymbolName Source # 

newtype Tape Source #

The tape, a terminal operates on. Terminals on different tapes could still have the same SymbolName but different type and input!

Constructors

Tape 

Fields

Instances

Enum Tape Source # 

Methods

succ :: Tape -> Tape #

pred :: Tape -> Tape #

toEnum :: Int -> Tape #

fromEnum :: Tape -> Int #

enumFrom :: Tape -> [Tape] #

enumFromThen :: Tape -> Tape -> [Tape] #

enumFromTo :: Tape -> Tape -> [Tape] #

enumFromThenTo :: Tape -> Tape -> Tape -> [Tape] #

Eq Tape Source # 

Methods

(==) :: Tape -> Tape -> Bool #

(/=) :: Tape -> Tape -> Bool #

Data Tape Source # 

Methods

gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> Tape -> c Tape #

gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c Tape #

toConstr :: Tape -> Constr #

dataTypeOf :: Tape -> DataType #

dataCast1 :: Typeable (* -> *) t => (forall d. Data d => c (t d)) -> Maybe (c Tape) #

dataCast2 :: Typeable (* -> * -> *) t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c Tape) #

gmapT :: (forall b. Data b => b -> b) -> Tape -> Tape #

gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Tape -> r #

gmapQr :: (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> Tape -> r #

gmapQ :: (forall d. Data d => d -> u) -> Tape -> [u] #

gmapQi :: Int -> (forall d. Data d => d -> u) -> Tape -> u #

gmapM :: Monad m => (forall d. Data d => d -> m d) -> Tape -> m Tape #

gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> Tape -> m Tape #

gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> Tape -> m Tape #

Num Tape Source # 

Methods

(+) :: Tape -> Tape -> Tape #

(-) :: Tape -> Tape -> Tape #

(*) :: Tape -> Tape -> Tape #

negate :: Tape -> Tape #

abs :: Tape -> Tape #

signum :: Tape -> Tape #

fromInteger :: Integer -> Tape #

Ord Tape Source # 

Methods

compare :: Tape -> Tape -> Ordering #

(<) :: Tape -> Tape -> Bool #

(<=) :: Tape -> Tape -> Bool #

(>) :: Tape -> Tape -> Bool #

(>=) :: Tape -> Tape -> Bool #

max :: Tape -> Tape -> Tape #

min :: Tape -> Tape -> Tape #

Show Tape Source # 

Methods

showsPrec :: Int -> Tape -> ShowS #

show :: Tape -> String #

showList :: [Tape] -> ShowS #

data SynTermEps Source #

Symbols, potentially with an index or more than one.

Constructors

SynVar

Syntactic variables.

SynTerm 

Fields

Term

Regular old terminal symbol -- reads stuff from the input.

Fields

Deletion

This sym denotes the case, where we have an Deletion terminal, i.e. something is matched to nothing. This is actually just a regular terminal symbol, we just treat it differently.

Epsilon

Finally, a real epsilon. Again, these are somewhat regular terminal symbols, but it is important to be able to recognize these, when trying to create outside variants of our algorithms.

Instances

Eq SynTermEps Source # 
Data SynTermEps Source # 

Methods

gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> SynTermEps -> c SynTermEps #

gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c SynTermEps #

toConstr :: SynTermEps -> Constr #

dataTypeOf :: SynTermEps -> DataType #

dataCast1 :: Typeable (* -> *) t => (forall d. Data d => c (t d)) -> Maybe (c SynTermEps) #

dataCast2 :: Typeable (* -> * -> *) t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c SynTermEps) #

gmapT :: (forall b. Data b => b -> b) -> SynTermEps -> SynTermEps #

gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> SynTermEps -> r #

gmapQr :: (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> SynTermEps -> r #

gmapQ :: (forall d. Data d => d -> u) -> SynTermEps -> [u] #

gmapQi :: Int -> (forall d. Data d => d -> u) -> SynTermEps -> u #

gmapM :: Monad m => (forall d. Data d => d -> m d) -> SynTermEps -> m SynTermEps #

gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> SynTermEps -> m SynTermEps #

gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> SynTermEps -> m SynTermEps #

Ord SynTermEps Source # 
Show SynTermEps Source # 

newtype Symbol Source #

The length of the list encodes the dimension of the symbol. Forms a monoid over dimensional concatenation.

Constructors

Symbol 

Instances

Eq Symbol Source # 

Methods

(==) :: Symbol -> Symbol -> Bool #

(/=) :: Symbol -> Symbol -> Bool #

Data Symbol Source # 

Methods

gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> Symbol -> c Symbol #

gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c Symbol #

toConstr :: Symbol -> Constr #

dataTypeOf :: Symbol -> DataType #

dataCast1 :: Typeable (* -> *) t => (forall d. Data d => c (t d)) -> Maybe (c Symbol) #

dataCast2 :: Typeable (* -> * -> *) t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c Symbol) #

gmapT :: (forall b. Data b => b -> b) -> Symbol -> Symbol #

gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Symbol -> r #

gmapQr :: (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> Symbol -> r #

gmapQ :: (forall d. Data d => d -> u) -> Symbol -> [u] #

gmapQi :: Int -> (forall d. Data d => d -> u) -> Symbol -> u #

gmapM :: Monad m => (forall d. Data d => d -> m d) -> Symbol -> m Symbol #

gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> Symbol -> m Symbol #

gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> Symbol -> m Symbol #

Ord Symbol Source # 
Show Symbol Source # 
Semigroup Symbol Source # 
Monoid Symbol Source # 

newtype AttributeFunction Source #

The name of an attribute function

Constructors

Attr 

Fields

Instances

Eq AttributeFunction Source # 
Data AttributeFunction Source # 

Methods

gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> AttributeFunction -> c AttributeFunction #

gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c AttributeFunction #

toConstr :: AttributeFunction -> Constr #

dataTypeOf :: AttributeFunction -> DataType #

dataCast1 :: Typeable (* -> *) t => (forall d. Data d => c (t d)) -> Maybe (c AttributeFunction) #

dataCast2 :: Typeable (* -> * -> *) t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c AttributeFunction) #

gmapT :: (forall b. Data b => b -> b) -> AttributeFunction -> AttributeFunction #

gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> AttributeFunction -> r #

gmapQr :: (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> AttributeFunction -> r #

gmapQ :: (forall d. Data d => d -> u) -> AttributeFunction -> [u] #

gmapQi :: Int -> (forall d. Data d => d -> u) -> AttributeFunction -> u #

gmapM :: Monad m => (forall d. Data d => d -> m d) -> AttributeFunction -> m AttributeFunction #

gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> AttributeFunction -> m AttributeFunction #

gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> AttributeFunction -> m AttributeFunction #

Ord AttributeFunction Source # 
Show AttributeFunction Source # 
IsString AttributeFunction Source # 

data Rule Source #

Production rules for at-most CFGs.

Constructors

Rule 

Fields

Instances

Eq Rule Source # 

Methods

(==) :: Rule -> Rule -> Bool #

(/=) :: Rule -> Rule -> Bool #

Data Rule Source # 

Methods

gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> Rule -> c Rule #

gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c Rule #

toConstr :: Rule -> Constr #

dataTypeOf :: Rule -> DataType #

dataCast1 :: Typeable (* -> *) t => (forall d. Data d => c (t d)) -> Maybe (c Rule) #

dataCast2 :: Typeable (* -> * -> *) t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c Rule) #

gmapT :: (forall b. Data b => b -> b) -> Rule -> Rule #

gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Rule -> r #

gmapQr :: (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> Rule -> r #

gmapQ :: (forall d. Data d => d -> u) -> Rule -> [u] #

gmapQi :: Int -> (forall d. Data d => d -> u) -> Rule -> u #

gmapM :: Monad m => (forall d. Data d => d -> m d) -> Rule -> m Rule #

gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> Rule -> m Rule #

gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> Rule -> m Rule #

Ord Rule Source # 

Methods

compare :: Rule -> Rule -> Ordering #

(<) :: Rule -> Rule -> Bool #

(<=) :: Rule -> Rule -> Bool #

(>) :: Rule -> Rule -> Bool #

(>=) :: Rule -> Rule -> Bool #

max :: Rule -> Rule -> Rule #

min :: Rule -> Rule -> Rule #

Show Rule Source # 

Methods

showsPrec :: Int -> Rule -> ShowS #

show :: Rule -> String #

showList :: [Rule] -> ShowS #

data DerivedGrammar Source #

Constructors

Inside 
Outside String 

Instances

Eq DerivedGrammar Source # 
Data DerivedGrammar Source # 

Methods

gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> DerivedGrammar -> c DerivedGrammar #

gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c DerivedGrammar #

toConstr :: DerivedGrammar -> Constr #

dataTypeOf :: DerivedGrammar -> DataType #

dataCast1 :: Typeable (* -> *) t => (forall d. Data d => c (t d)) -> Maybe (c DerivedGrammar) #

dataCast2 :: Typeable (* -> * -> *) t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c DerivedGrammar) #

gmapT :: (forall b. Data b => b -> b) -> DerivedGrammar -> DerivedGrammar #

gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> DerivedGrammar -> r #

gmapQr :: (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> DerivedGrammar -> r #

gmapQ :: (forall d. Data d => d -> u) -> DerivedGrammar -> [u] #

gmapQi :: Int -> (forall d. Data d => d -> u) -> DerivedGrammar -> u #

gmapM :: Monad m => (forall d. Data d => d -> m d) -> DerivedGrammar -> m DerivedGrammar #

gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> DerivedGrammar -> m DerivedGrammar #

gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> DerivedGrammar -> m DerivedGrammar #

Show DerivedGrammar Source # 
Default DerivedGrammar Source # 

Methods

def :: DerivedGrammar #

data Grammar Source #

Complete descrition of a grammar. In principle it would be enough to hold _rules and the _start symbol name. We also store dimensionless names for syntactiv variables, and terminals. This makes certain checks easier or possible.

We store all single-tape symbol names dimensionless. This means that, for terminals, symbols with the same name have the same tape. This is slightly inconvenient for special applications (say Protein-DNA alignment) but one can easily rename terminals.

TODO better way to handle indexed symbols?

Constructors

Grammar 

Fields

Instances

Data Grammar Source # 

Methods

gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> Grammar -> c Grammar #

gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c Grammar #

toConstr :: Grammar -> Constr #

dataTypeOf :: Grammar -> DataType #

dataCast1 :: Typeable (* -> *) t => (forall d. Data d => c (t d)) -> Maybe (c Grammar) #

dataCast2 :: Typeable (* -> * -> *) t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c Grammar) #

gmapT :: (forall b. Data b => b -> b) -> Grammar -> Grammar #

gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Grammar -> r #

gmapQr :: (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> Grammar -> r #

gmapQ :: (forall d. Data d => d -> u) -> Grammar -> [u] #

gmapQi :: Int -> (forall d. Data d => d -> u) -> Grammar -> u #

gmapM :: Monad m => (forall d. Data d => d -> m d) -> Grammar -> m Grammar #

gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> Grammar -> m Grammar #

gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> Grammar -> m Grammar #

Show Grammar Source # 
Default Grammar Source # 

Methods

def :: Grammar #