|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: INNER | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Object | +--com.inxar.syntacs.automaton.finite.TreeDFA
Concrete DFA
implementation which uses tree-based
parse tables. The TreeDFA
data structure is a
flexible general purpose DFA representation that is fast to compile
and memory conscious but slower than it could be when used by a
Lexer (binary search versus array indexing). Thus, TreeDFA and its
inner classes are used often in construction and transformation
algorithms, but generally "burned" to a MesoArrayDFA when used by a
Lexer.
Inner Class Summary | |
static class |
TreeDFA.Edge
The TreeDFA.Edge class is models a single edge as
a node in an binary interval tree. |
static class |
TreeDFA.State
The TreeDFA.State class is models a single state
as tuple (output, edge_tree) where
output is an integer which records the accepting
NFA state and edge_tree holds the outgoing edges
of the state tree. |
Fields inherited from interface org.inxar.syntacs.automaton.finite.DFA |
DEAD_STATE, START_STATE |
Constructor Summary | |
TreeDFA(TreeDFA.State[] table)
Constructs the TreeDFA from the given
State table. |
Method Summary | |
static TreeDFA.Edge |
balance(TreeDFA.Edge tree)
Given a (possibly unbalanced) binary edge tree, balance the tree such that a Red-Black tree would be pleased with the output. |
static TreeDFA.Edge |
balance(TreeDFA.Edge[] edges,
int off,
int len)
Recursively balance the section of the Edge array specified. |
int |
go(int state,
int input)
Returns the next state for the given state and given input symbol. |
static void |
inOrderDump(TreeDFA.Edge tree,
Vector v)
Recursively flatten the given Edge tree into the
given Vector . |
int |
output(int state)
Returns the output at the given state. |
String |
toString()
|
static void |
toStringInOrder(TreeDFA.Edge tree,
StringBuffer b,
int level)
Recursively print the tree in-order. |
void |
vizualize(GraphViz dot)
Burn state to the GraphViz instance such that the instance may be visualized in postscript. |
Methods inherited from class java.lang.Object |
equals, getClass, hashCode, notify, notifyAll, wait, wait, wait |
Constructor Detail |
public TreeDFA(TreeDFA.State[] table)
TreeDFA
from the given
State
table.Method Detail |
public int go(int state, int input)
DFA
go
in interface DFA
public int output(int state)
DFA
Token.UNDEF
is
returned.output
in interface DFA
public String toString()
toString
in class Object
public void vizualize(GraphViz dot)
Vizualizable
vizualize
in interface Vizualizable
public static TreeDFA.Edge balance(TreeDFA.Edge tree)
public static void inOrderDump(TreeDFA.Edge tree, Vector v)
Edge
tree into the
given Vector
.public static void toStringInOrder(TreeDFA.Edge tree, StringBuffer b, int level)
public static TreeDFA.Edge balance(TreeDFA.Edge[] edges, int off, int len)
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: INNER | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |