Class FiniteAutomaton.Automaton<E>
- java.lang.Object
-
- edu.washington.cs.knowitall.regex.FiniteAutomaton.Automaton<E>
-
- Type Parameters:
E
-
- Enclosing class:
- FiniteAutomaton
public static class FiniteAutomaton.Automaton<E> extends java.lang.Object
A component automaton with a single start state and a single end state.
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description private static class
FiniteAutomaton.Automaton.Step<E>
A representation of a movement from a state to another, with a backreference to the previous state.
-
Field Summary
Fields Modifier and Type Field Description FiniteAutomaton.EndState<E>
end
FiniteAutomaton.StartState<E>
start
-
Constructor Summary
Constructors Constructor Description Automaton(Expression<E> expr)
Automaton(FiniteAutomaton.StartState<E> start, FiniteAutomaton.EndState<E> end)
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description boolean
apply(java.util.List<E> tokens)
private FiniteAutomaton.State<E>
buildMatch(java.util.Iterator<E> tokenIterator, Expression<E> expression, java.util.concurrent.atomic.AtomicInteger index, FiniteAutomaton.State<E> state, java.util.Iterator<FiniteAutomaton.AbstractEdge<E>> edgeIterator, Match.IntermediateMatch<E> match)
Retrace the path through the NFA and produce an object that represents the match.private FiniteAutomaton.Automaton.Step<E>
evaluate(java.util.List<E> tokens, boolean hasStart)
private FiniteAutomaton.Automaton.Step<E>
evaluate(java.util.List<E> tokens, java.util.List<FiniteAutomaton.Automaton.Step<E>> steps, boolean hasStart)
Evaluate the NFA against the list of tokens using the Thompson NFA algorithm.private void
expandAssertions(java.util.List<FiniteAutomaton.Automaton.Step<E>> steps, java.util.List<FiniteAutomaton.Automaton.Step<E>> newsteps, boolean hasStart, java.util.List<E> tokens, int totalTokens)
Expand any state that has an assertion edge if the assertion passes given the present state.private void
expandEpsilon(FiniteAutomaton.Automaton.Step<E> step, java.util.List<FiniteAutomaton.Automaton.Step<E>> steps)
Expand all epsilon transitions for the specified step.private void
expandEpsilons(java.util.List<FiniteAutomaton.Automaton.Step<E>> steps)
Expand all epsilon transitions for the supplied steps.Match.FinalMatch<E>
lookingAt(java.util.List<E> tokens)
Match.FinalMatch<E>
lookingAt(java.util.List<E> tokens, int startIndex)
int
minMatchingLength()
-
-
-
Field Detail
-
start
public final FiniteAutomaton.StartState<E> start
-
end
public final FiniteAutomaton.EndState<E> end
-
-
Constructor Detail
-
Automaton
public Automaton(FiniteAutomaton.StartState<E> start, FiniteAutomaton.EndState<E> end)
-
Automaton
public Automaton(Expression<E> expr)
-
-
Method Detail
-
apply
public boolean apply(java.util.List<E> tokens)
-
minMatchingLength
public int minMatchingLength()
-
lookingAt
public Match.FinalMatch<E> lookingAt(java.util.List<E> tokens)
-
lookingAt
public Match.FinalMatch<E> lookingAt(java.util.List<E> tokens, int startIndex)
- Returns:
- null if no match, otherwise a representation of the match
-
buildMatch
private FiniteAutomaton.State<E> buildMatch(java.util.Iterator<E> tokenIterator, Expression<E> expression, java.util.concurrent.atomic.AtomicInteger index, FiniteAutomaton.State<E> state, java.util.Iterator<FiniteAutomaton.AbstractEdge<E>> edgeIterator, Match.IntermediateMatch<E> match)
Retrace the path through the NFA and produce an object that represents the match.- Parameters:
tokenIterator
- an iterator over the tokens.expression
- the expression to match.index
- the present index.state
- the present state.edgeIterator
- an iterator over the edges in the solution.match
- the solution.- Returns:
-
expandEpsilons
private void expandEpsilons(java.util.List<FiniteAutomaton.Automaton.Step<E>> steps)
Expand all epsilon transitions for the supplied steps. That is, add all states available via an epsilon transition from a supplied state to the list.- Parameters:
steps
-
-
expandEpsilon
private void expandEpsilon(FiniteAutomaton.Automaton.Step<E> step, java.util.List<FiniteAutomaton.Automaton.Step<E>> steps)
Expand all epsilon transitions for the specified step. That is, add all states avaiable via an epsilon transition from step.state.- Parameters:
step
-steps
-
-
expandAssertions
private void expandAssertions(java.util.List<FiniteAutomaton.Automaton.Step<E>> steps, java.util.List<FiniteAutomaton.Automaton.Step<E>> newsteps, boolean hasStart, java.util.List<E> tokens, int totalTokens)
Expand any state that has an assertion edge if the assertion passes given the present state.- Parameters:
steps
-newsteps
-hasStart
- true iff the tokens contains the start token.tokens
-totalTokens
-
-
evaluate
private FiniteAutomaton.Automaton.Step<E> evaluate(java.util.List<E> tokens, boolean hasStart)
-
evaluate
private FiniteAutomaton.Automaton.Step<E> evaluate(java.util.List<E> tokens, java.util.List<FiniteAutomaton.Automaton.Step<E>> steps, boolean hasStart)
Evaluate the NFA against the list of tokens using the Thompson NFA algorithm.- Parameters:
tokens
- the tokens to evaluate againststeps
- present list of accessible states.hasStart
- true iff tokens contains the start token.- Returns:
- a Step object representing the last transition or null.
-
-