Package edu.washington.cs.knowitall.regex

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

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()

Methods inherited from class java.lang.Object

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

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 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.