Class FiniteAutomaton.Automaton<E>
java.lang.Object
edu.washington.cs.knowitall.regex.FiniteAutomaton.Automaton<E>
- Type Parameters:
E
-
- Enclosing class:
FiniteAutomaton
A component automaton with a single start state and a single end
state.
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescriptionprivate static class
A representation of a movement from a state to another, with a backreference to the previous state. -
Field Summary
FieldsModifier and TypeFieldDescriptionfinal FiniteAutomaton.EndState
<E> final FiniteAutomaton.StartState
<E> -
Constructor Summary
ConstructorsConstructorDescriptionAutomaton
(Expression<E> expr) Automaton
(FiniteAutomaton.StartState<E> start, FiniteAutomaton.EndState<E> end) -
Method Summary
Modifier and TypeMethodDescriptionboolean
private FiniteAutomaton.State
<E> buildMatch
(Iterator<E> tokenIterator, Expression<E> expression, AtomicInteger index, FiniteAutomaton.State<E> state, 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> private FiniteAutomaton.Automaton.Step
<E> Evaluate the NFA against the list of tokens using the Thompson NFA algorithm.private void
expandAssertions
(List<FiniteAutomaton.Automaton.Step<E>> steps, List<FiniteAutomaton.Automaton.Step<E>> newsteps, boolean hasStart, 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, List<FiniteAutomaton.Automaton.Step<E>> steps) Expand all epsilon transitions for the specified step.private void
Expand all epsilon transitions for the supplied steps.int
-
Field Details
-
start
-
end
-
-
Constructor Details
-
Automaton
-
Automaton
-
-
Method Details
-
apply
-
minMatchingLength
public int minMatchingLength() -
lookingAt
-
lookingAt
- Returns:
- null if no match, otherwise a representation of the match
-
buildMatch
private FiniteAutomaton.State<E> buildMatch(Iterator<E> tokenIterator, Expression<E> expression, AtomicInteger index, FiniteAutomaton.State<E> state, 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
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, 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(List<FiniteAutomaton.Automaton.Step<E>> steps, List<FiniteAutomaton.Automaton.Step<E>> newsteps, boolean hasStart, 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
-
evaluate
private FiniteAutomaton.Automaton.Step<E> evaluate(List<E> tokens, 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.
-