org.stekikun.dolmen.automaton

Class DFA

java.lang.Object

org.stekikun.dolmen.automaton.DFA

public class DFA
extends Object

Describes a tagged Deterministic Finite Automaton recognizing the language of some given tagged regular expression. This automaton's states represent sets of states in the Non-deterministic Finite Automaton, along with memory maps describing where tags values can be found in memory cells.

Author:

Stéphane Lescuyer

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	DFA.Cell Describes the actual behavior of one cell of the automaton, i.e. either performing some final action or shifting to another state according to a transition table.
static class	DFA.GotoAction Describes an automaton action, i.e. either jumping to another state with number DFA.GotoAction.target, or back-tracking
static class	DFA.Key A key is an abstraction of a DFA state which represents the set of NFA states and memory maps that the DFA state stands for, in such a way that two different states with the same key can be made equal by copying some memory cells in others.
static class	DFA.MemAction Action on memory cells to take when following a DFA transition Actions are of two kinds: either setting some memory cell to the current position input, or copying one memory cell's contents into another.
static class	DFA.MemMap A memory map describes what memory cell corresponds to each tag.
static class	DFA.Perform Accepts the input by performing some semantic action and the associated finisher list
static class	DFA.Remember Describes action that should be taken when reaching a final state during traversal of the automaton: either do nothing or remember the associated action number and tag actions for later (useful when backtracking for longest match)
static class	DFA.Shift Shifts to another state of the automaton, potentially performing some side-effects
static class	DFA.State A state in the (tagged) deterministic finite automaton corresponds to a set of states in the non-deterministic automaton, each being associated with a memory map.
static class	DFA.TagAction Describes a tag action, i.e. commands which are performed as part of the finisher set corresponding to some final action.
static class	DFA.TEquiv Abstraction of the memory maps in a DFA state Describes a DFA.TEquiv.tag and all the possible sets of transitions that use this tag with some common memory cell.
static class	DFA.TransActions Packs together everything that describes shifting from one automaton cell to another, namely the state to go to (or whether to backtrack), and the associated memory actions to execute

Field Summary

Fields

Modifier and Type	Field and Description
static int	NO_ACTION A special number to mark the absence of an action

Method Summary

Modifier and Type	Method and Description
protected static DFA.Key	getKey(DFA.State s)

Methods inherited from class java.lang.Object

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

Field Detail

NO_ACTION

public static final int NO_ACTION

A special number to mark the absence of an action

See Also:

Constant Field Values

Method Detail

getKey

protected static DFA.Key getKey(DFA.State s)

Parameters:

s -

Returns:

the key correponding to the DFA state s