com.nobigsoftware.dfalex

Class Nfa<MATCHRESULT>

java.lang.Object

com.nobigsoftware.dfalex.Nfa<MATCHRESULT>

public class Nfa<MATCHRESULT>
extends java.lang.Object

Simple non-deterministic finite automaton (NFA) representation

A set of Matchable patterns is converted to an NFA as an intermediate step toward creating the DFA.

You can also build an NFA directly with this class and convert it to a DFA with DfaBuilder.buildFromNfa(Nfa, int[], DfaAmbiguityResolver, com.nobigsoftware.util.BuilderCache).

See NFA on Wikipedia

Constructor Summary

Constructors

Constructor and Description
Nfa()

Method Summary

Modifier and Type	Method and Description
void	addEpsilon(int from, int to) Add an epsilon transition to the NFA
int	addState(MATCHRESULT accept) Add a new state to the NFA
void	addTransition(int from, int to, char firstChar, char lastChar) Add a transition to the NFA
int	Disemptify(int state) Make modified state, if necessary, that doesn't match the empty string
MATCHRESULT	getAccept(int state) Get the result attached to the given state
java.lang.Iterable<java.lang.Integer>	getStateEpsilons(int state) Get all the epsilon transitions from a state
java.lang.Iterable<NfaTransition>	getStateTransitions(int state) Get all the non-epsilon transitions from a state
boolean	hasTransitionsOrAccepts(int state) Check whether a state has any non-epsilon transitions or has a result attached
int	numStates() Get the number of states in the NFA

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

Nfa

public Nfa()

Method Detail

numStates

public int numStates()

Get the number of states in the NFA

Returns:

the total number of states that have been added with addState(Object)

addState

public int addState(MATCHRESULT accept)

Add a new state to the NFA

Parameters:

accept - if non-null, then the NFA will produce this result for any string that reaches the new state

Returns:

the number of the new state

addTransition

public void addTransition(int from,
                          int to,
                          char firstChar,
                          char lastChar)

Add a transition to the NFA

A new transition will be created from state from to state to for all characters with code points in [from,to] (inclusive)

Parameters:

from - the number of the state to transition from

to - the number of the state to transition to, for characters in the accepted range

firstChar - the first character in the accepted range

lastChar - the last character in the accepted range

addEpsilon

public void addEpsilon(int from,
                       int to)

Add an epsilon transition to the NFA

An epsilon transition is created from state from to state to.

This will cause any string that is accepted by to to be accepted by from as well

Parameters:

from - the number of the state to transition from

to - the number of the state to transition to

getAccept

public MATCHRESULT getAccept(int state)

Get the result attached to the given state

Parameters:

state - the state number

Returns:

the result that was provided to addState(Object) when the state was created

hasTransitionsOrAccepts

public boolean hasTransitionsOrAccepts(int state)

Check whether a state has any non-epsilon transitions or has a result attached

Parameters:

state - the state number

Returns:

true if the state has any transitions or accepts

getStateEpsilons

public java.lang.Iterable<java.lang.Integer> getStateEpsilons(int state)

Get all the epsilon transitions from a state

Parameters:

state - the state number

Returns:

An iterable over all transitions out of the given state

getStateTransitions

public java.lang.Iterable<NfaTransition> getStateTransitions(int state)

Get all the non-epsilon transitions from a state

Parameters:

state - the state number

Returns:

An iterable over all transitions out of the given state

Disemptify

public int Disemptify(int state)

Make modified state, if necessary, that doesn't match the empty string

If state has a non-null result attached, or can reach such a state through epsilon transitions, then a DFA made from that state would match the empty string. In that case a new NFA state will be created that matches all the same strings except the empty string.

Parameters:

state - the number of the state to disemptify

Returns:

If state matches the empty string, then a new state that does not match the empty string is returned. Otherwise state is returned.