Text.ANTLR.Lex.Automata

Documentation

data Automata e s i

An automaton with edges e, symbols s, and state indices i

Constructors

Automata

Fields

• _S :: Set i

  Finite set of states.

• _Σ :: Set s

  Input (edge) alphabet

• _Δ :: Set (Transition e i)

  Transition function

• s0 :: i

  Start state

• _F :: Set i

  Accepting states

Instances

(Eq i, Eq s, Eq e) => Eq (Automata e s i)

Defined in Text.ANTLR.Lex.Automata

Methods

(==) :: Automata e s i -> Automata e s i -> Bool

(/=) :: Automata e s i -> Automata e s i -> Bool

(Eq e, Eq s, Eq i, Hashable e, Hashable s, Hashable i, Show e, Show s, Show i) => Show (Automata e s i)

Defined in Text.ANTLR.Lex.Automata

Methods

showsPrec :: Int -> Automata e s i -> ShowS

show :: Automata e s i -> String

showList :: [Automata e s i] -> ShowS

type AutomataEdge t = (Bool, Set t)

Edge label of an automaton, on which we traverse if we match on one of the tokens t in the set. The boolean is for negation of the set.

type Transition e i = (i, AutomataEdge e, i)

A triplet with an edge alphabet of e and node states of i.

tFrom :: Transition e i -> i

The from-node component of a Transition

tTo :: Transition e i -> i

The to-node component of a Transition

tEdge :: Transition e i -> Set e

The set of edge characters in e of a Transition

transitionAlphabet :: HashSet (a1, (a2, [b]), c) -> [b]

Determine the edge-label alphabet of a set of transitions.

compress :: (Eq i, Eq e, Hashable i, Hashable e) => Set (Transition e i) -> Set (Transition e i)

Compress a set of transitions such that every pair of (start,end) states appears at most once in the set.

xor :: Bool -> Bool -> Bool

XOR helper function over booleans.

transitionMember :: (Eq i, Hashable e, Eq e) => (i, e, i) -> Set (Transition e i) -> Bool

Is the given transition triplet (with a single e character as the edge edge label) in some set of transitions? Note that we need to handle complement sets here, in case the given e is in the complement of one of the transitions in the set.

edgeMember :: (Eq a, Hashable a) => a -> (Bool, HashSet a) -> Bool

Is the given character s accepted by the given edge label?

data Result

An automaton must either Accept or Reject.

Constructors

Accept

Reject

validStartState :: (Eq i, Hashable i) => Automata e s i -> Bool

Is the start state valid?

validFinalStates :: (Eq i, Hashable i) => Automata e s i -> Bool

Are all of the ending states valid?

validTransitions :: forall e s i. (Hashable e, Hashable i, Eq e, Eq i) => Automata e s i -> Bool

Can all of the nodes as defined by the set of transitions be found in the set of allowable states _S?

type Config i = Set i

An automaton configuration is the set of state (indices) your can currently be in.

closureWith :: forall e s i. (Hashable e, Hashable i, Eq e, Eq i) => (e -> Bool) -> Automata e s i -> Config i -> Config i

Generic closure function so that *someone* never asks "what's a closure?" ever again. For an epsilon-closure the given fncn needs to return True when given an e that is an epsilon, and False in all other cases.

move :: forall e s i. (Hashable e, Hashable i, Eq i, Eq e) => Automata e s i -> Config i -> e -> Config i

Consume the e character given, based on the fact that we are currently in some 'Config i' of states, resulting in a new config consisting of the states that we can get to by doing so.

complementMember :: (Hashable i, Eq i, Hashable e, Eq e) => (i, i) -> Set (Transition e i) -> Bool

Whether or not (a, (True, _), b) is a transition in our set of transitions.

moveComplement :: forall e s i. (Hashable e, Hashable i, Eq i, Eq e) => Automata e s i -> Config i -> Config i

Set of states you can move to if you see a character not in the alphabet.