Safe Haskell	None
Language	Haskell2010

FormalLanguage.CFG.Grammar.Types

Description

The data types that define a CFG.

Synopsis

Documentation

newtype IndexName Source

Constructors

IndexName
Fields _getIndexName :: String

Instances

Eq IndexName
Data IndexName
Ord IndexName
Show IndexName
IsString IndexName
Typeable * IndexName

getIndexName :: Iso' IndexName String Source

data IOP Source

Constructors

IPlus
IMinus
IEq
INone
ISymbol

Instances

Eq IOP
Data IOP
Ord IOP
Show IOP
Typeable * IOP

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.

Constructors

Index
Fields _indexName :: IndexName _indexHere :: Integer _indexOp :: IOP _indexRange :: [Integer] _indexStep :: Integer

Instances

Eq Index
Data Index
Ord Index
Show Index
Typeable * Index

indexStep :: Lens' Index Integer Source

indexRange :: Lens' Index [Integer] Source

indexOp :: Lens' Index IOP Source

indexName :: Lens' Index IndexName Source

indexHere :: Lens' Index Integer Source

newtype SymbolName Source

Newtype wrapper for symbol names.

Constructors

SymbolName
Fields _getSteName :: String

Instances

Eq SymbolName
Data SymbolName
Ord SymbolName
Show SymbolName
IsString SymbolName
Typeable * SymbolName

getSteName :: Iso' SymbolName String 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 _getTape :: Int

Instances

Enum Tape
Eq Tape
Data Tape
Num Tape
Ord Tape
Show Tape
Typeable * Tape

getTape :: Iso' Tape Int Source

data SynTermEps Source

Symbols, potentially with an index or more than one.

Constructors

SynVar	Syntactic variables.
Fields _name :: SymbolName _index :: [Index] _splitN :: Integer _splitK :: Integer
SynTerm
Fields _name :: SymbolName _index :: [Index]
Term	Regular old terminal symbol -- reads stuff from the input.
Fields _name :: SymbolName _index :: [Index]
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
Data SynTermEps
Ord SynTermEps
Show SynTermEps
Typeable * SynTermEps

splitN :: Traversal' SynTermEps Integer Source

splitK :: Traversal' SynTermEps Integer Source

name :: Traversal' SynTermEps SymbolName Source

index :: Traversal' SynTermEps [Index] Source

_Epsilon :: Prism' SynTermEps () Source

_Deletion :: Prism' SynTermEps () Source

_Term :: Prism' SynTermEps (SymbolName, [Index]) Source

_SynTerm :: Prism' SynTermEps (SymbolName, [Index]) Source

_SynVar :: Prism' SynTermEps (SymbolName, [Index], Integer, Integer) Source

newtype Symbol Source

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

Constructors

Symbol
Fields _getSymbolList :: [SynTermEps]

Instances

Eq Symbol
Data Symbol
Ord Symbol
Show Symbol
Monoid Symbol
Semigroup Symbol
Typeable * Symbol

getSymbolList :: Iso' Symbol [SynTermEps] Source

newtype AttributeFunction Source

The name of an attribute function

Constructors

Attr
Fields _getAttr :: String

Instances

Eq AttributeFunction
Data AttributeFunction
Ord AttributeFunction
Show AttributeFunction
IsString AttributeFunction
Typeable * AttributeFunction

getAttr :: Iso' AttributeFunction String Source

data Rule Source

Production rules for at-most CFGs.

Constructors

Rule
Fields _lhs :: Symbol the left-hand side of the rule _attr :: [AttributeFunction] the attribute for this rule _rhs :: [Symbol] the right-hand side with a collection of terminals and syntactic variables

Instances

Eq Rule
Data Rule
Ord Rule
Show Rule
Typeable * Rule

rhs :: Lens' Rule [Symbol] Source

lhs :: Lens' Rule Symbol Source

attr :: Lens' Rule [AttributeFunction] Source

data DerivedGrammar Source

Constructors

Inside
Outside String

Instances

Eq DerivedGrammar
Data DerivedGrammar
Show DerivedGrammar
Default DerivedGrammar
Typeable * DerivedGrammar

isOutside :: DerivedGrammar -> Bool Source

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

_synvars :: Map SymbolName SynTermEps: regular syntactic variables, without dimension
_synterms :: Map SymbolName SynTermEps: Terminal synvars are somewhat weird. They are used in Outside grammars, and hold previously calculated inside values.
_termvars :: Map SymbolName SynTermEps: regular terminal symbols
_outside :: DerivedGrammar: Is this an automatically derived outside grammar
_rules :: Set Rule: set of production rules
_start :: Symbol: start symbol
_params :: Map IndexName Index: any global variables
_indices :: Map IndexName Index: active indices
_grammarName :: String: grammar name
_write :: Bool: some grammar file requested this grammar to be expanded into code -- TODO remove, we have an emission queue

Instances

Data Grammar
Show Grammar
Default Grammar
Typeable * Grammar

write :: Lens' Grammar Bool Source

termvars :: Lens' Grammar (Map SymbolName SynTermEps) Source

synvars :: Lens' Grammar (Map SymbolName SynTermEps) Source

synterms :: Lens' Grammar (Map SymbolName SynTermEps) Source

start :: Lens' Grammar Symbol Source

rules :: Lens' Grammar (Set Rule) Source

params :: Lens' Grammar (Map IndexName Index) Source

outside :: Lens' Grammar DerivedGrammar Source

indices :: Lens' Grammar (Map IndexName Index) Source

grammarName :: Lens' Grammar String Source