com.inxar.syntacs.automaton.finite
Class TreeDFA

java.lang.Object
  |
  +--com.inxar.syntacs.automaton.finite.TreeDFA
All Implemented Interfaces:
DFA, Vizualizable

public class TreeDFA
extends Object
implements DFA, Vizualizable

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

TreeDFA

public TreeDFA(TreeDFA.State[] table)
Constructs the TreeDFA from the given State table.
Method Detail

go

public int go(int state,
              int input)
Description copied from interface: DFA
Returns the next state for the given state and given input symbol.
Specified by:
go in interface DFA

output

public int output(int state)
Description copied from interface: DFA
Returns the output at the given state. Output values generally correspond to to Token ID numbers. If no output has been defined for the given state, Token.UNDEF is returned.
Specified by:
output in interface DFA

toString

public String toString()
Overrides:
toString in class Object

vizualize

public void vizualize(GraphViz dot)
Description copied from interface: Vizualizable
Burn state to the GraphViz instance such that the instance may be visualized in postscript.
Specified by:
vizualize in interface Vizualizable

balance

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

inOrderDump

public static void inOrderDump(TreeDFA.Edge tree,
                               Vector v)
Recursively flatten the given Edge tree into the given Vector.

toStringInOrder

public static void toStringInOrder(TreeDFA.Edge tree,
                                   StringBuffer b,
                                   int level)
Recursively print the tree in-order.

balance

public static TreeDFA.Edge balance(TreeDFA.Edge[] edges,
                                   int off,
                                   int len)
Recursively balance the section of the Edge array specified.