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 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
final FiniteAutomaton.EndState<E>	end
final FiniteAutomaton.StartState<E>	start

Constructor Summary

Constructors

Constructor	Description
Automaton(Expression<E> expr)
Automaton(FiniteAutomaton.StartState<E> start, FiniteAutomaton.EndState<E> end)

Method Summary

Modifier and Type	Method	Description
boolean	apply(List<E> tokens)
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>	evaluate(List<E> tokens, boolean hasStart)
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.
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	expandEpsilons(List<FiniteAutomaton.Automaton.Step<E>> steps)	Expand all epsilon transitions for the supplied steps.
Match.FinalMatch<E>	lookingAt(List<E> tokens)
Match.FinalMatch<E>	lookingAt(List<E> tokens, int startIndex)
int	minMatchingLength()

Methods inherited from class Object

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

Field Details

start

public final FiniteAutomaton.StartState<E> start

end

public final FiniteAutomaton.EndState<E> end

Constructor Details

Automaton

public Automaton(FiniteAutomaton.StartState<E> start,
 FiniteAutomaton.EndState<E> end)

Automaton

public Automaton(Expression<E> expr)

Method Details

apply

public boolean apply(List<E> tokens)

minMatchingLength

public int minMatchingLength()

lookingAt

public Match.FinalMatch<E> lookingAt(List<E> tokens)

lookingAt

public Match.FinalMatch<E> lookingAt(List<E> tokens,
 int startIndex)

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

private void expandEpsilons(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,
 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

private FiniteAutomaton.Automaton.Step<E> evaluate(List<E> tokens,
 boolean hasStart)

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 against

steps - present list of accessible states.

hasStart - true iff tokens contains the start token.

Returns:

a Step object representing the last transition or null.