laser.regularlanguage.util
Class REtoDFABuilder<L extends LabelInterface>

java.lang.Object
  extended by laser.regularlanguage.regularexpression.AbstractREVisitor<L>
      extended by laser.regularlanguage.util.AbstractREtoDFAVisitor<L>
          extended by laser.regularlanguage.util.REtoDFABuilder<L>
Type Parameters:
L - The type of labels used by the REs and DFAs.
All Implemented Interfaces:
REVisitor<L>

public class REtoDFABuilder<L extends LabelInterface>
extends AbstractREtoDFAVisitor<L>

The REtoDFABuilder class builds a Deterministic Finite State Automaton (DFA) from the given (basic) Regular Expresion (RE).

REFERENCES:

The RE to DFA algorithm comes from "Compilers: Principles, Techniques, and Tools" by Aho, Sethi, and Ullman (the Dragon Book), in Section 3.9.

Author:
Jamieson M. Cobleigh (laser-software@cs.umass.edu), Heather M. Conboy

Field Summary
 
Fields inherited from class laser.regularlanguage.regularexpression.AbstractREVisitor
result
 
Constructor Summary
REtoDFABuilder(FSAFactoryInterface<L> fsaFactory, RLFactory<L> rlFactory)
          Creates a new REtoDFABuilder that builds the DFA for the given RE.
 
Method Summary
protected  FSALabelTransitionInterface<L> addLabelTransition(MutableFSAInterface<L> fsa, FSAStateInterface<L> source, FSAStateInterface<L> target, L label)
          Adds a transition from the source to the target on the given label.
protected  TreeNode<L> addMarkerNode(TreeNode<L> oldRootNode)
          Adds a right end MarkerNode to the given regular expression.
 MutableFSAInterface<L> build(RE<L> theRE)
          Converts from the given RE to its corresponding DFA.
 void caseChoiceNode(ChoiceNode<L> node, java.lang.Object context)
          Allows this REVisitor to process the given ChoiceNode.
 void caseConcatenationNode(ConcatenationNode<L> node, java.lang.Object context)
          Allows this REVisitor to process the given ConcatenationNode.
 void caseEpsilonNode(EpsilonNode<L> node, java.lang.Object context)
          Allows this REVisitor to process the given EpsilonNode.
 void caseKleeneStarNode(KleeneStarNode<L> node, java.lang.Object context)
          Allows this REVisitor to process the given KleeneStarNode.
 void caseLabelNode(LabelNode<L> node, java.lang.Object context)
          Allows this REVisitor to process the given LabelNode.
 void caseMarkerNode(MarkerNode<L> node, java.lang.Object context)
          Allows this REVisitor to process the given MarkerNode.
 REtoDFAInfo generateNodeInfo(TreeNode<L> node, java.util.List<TreeNode<L>> leafNodes)
          Generates the firstpos, lastpos, followpos sets and nullable flag.
protected  java.lang.Object[] getCreateArgs(MutableFSAInterface<L> newFSA, TreeNode<L> oldTreeNode)
          Gets any required arguments for the state factory method from the given TreeNode.
protected  REtoDFAInfo getNodeInfo(TreeNode<L> node)
          Gets the REToDFAInfo Object associated with the given TreeNode.
protected  void setUp(RE<L> theRE, MutableFSAInterface<L> theDFA)
          Sets up the builder before the DFA is built.
protected  void tearDown()
          Tears down the builder after the DFA is built.
 
Methods inherited from class laser.regularlanguage.regularexpression.AbstractREVisitor
caseClassSetNode, caseDotNode, caseEmptyNode, caseExponentNode, caseKleenePlusNode, caseNotClassSetNode, caseOptionNode, defaultCase, getResult, setResult
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

REtoDFABuilder

public REtoDFABuilder(FSAFactoryInterface<L> fsaFactory,
                      RLFactory<L> rlFactory)
Creates a new REtoDFABuilder that builds the DFA for the given RE.

Parameters:
fsaFactory - The FSAFactoryInterface to be used to create new DFAs (non-null)
rlFactory - The RLFactory to be used to help convert between REs and DFAs (non-null)
Method Detail

build

public MutableFSAInterface<L> build(RE<L> theRE)
                                                    throws FSAInterfaceException,
                                                           REException
Converts from the given RE to its corresponding DFA.

NOTE: An EmptyNode can only occur as the root node.

PRECONDITIONS:

Parameters:
theRE - The RE to be converted
Returns:
The corresponding DFA
Throws:
FSAInterfaceException - if an FSA related error occurs
REException - if an RE related error occurs

addMarkerNode

protected TreeNode<L> addMarkerNode(TreeNode<L> oldRootNode)
Adds a right end MarkerNode to the given regular expression.

Parameters:
oldRootNode - The old regular expression
Returns:
The new regular expression with the right end MarkerNode

addLabelTransition

protected FSALabelTransitionInterface<L> addLabelTransition(MutableFSAInterface<L> fsa,
                                                            FSAStateInterface<L> source,
                                                            FSAStateInterface<L> target,
                                                            L label)
Adds a transition from the source to the target on the given label.

Parameters:
fsa - The FSA that will contain the new transition
source - The source for the new transition
target - The target for the new transition
label - The label for the new transition
Returns:
The new label transition

getCreateArgs

protected java.lang.Object[] getCreateArgs(MutableFSAInterface<L> newFSA,
                                           TreeNode<L> oldTreeNode)
Gets any required arguments for the state factory method from the given TreeNode.

Parameters:
newFSA - The FSA that will contain the new state
oldTreeNode - The old TreeNode
Returns:
Any required arguments for the new state

generateNodeInfo

public REtoDFAInfo generateNodeInfo(TreeNode<L> node,
                                    java.util.List<TreeNode<L>> leafNodes)
                             throws REVisitorException
Generates the firstpos, lastpos, followpos sets and nullable flag. It also numbers all of the leaf nodes and records them in the leafNodes List.

Parameters:
node - The TreeNode of interest
leafNodes - a List that is used to store a mapping between leaf-nodes and a number used to identify them.
Throws:
REVisitorException - if the given TreeNode cannot be converted to its corresponding REToDFAInfo Object

getNodeInfo

protected REtoDFAInfo getNodeInfo(TreeNode<L> node)
Gets the REToDFAInfo Object associated with the given TreeNode.

NOTE: It will be created if needed.

Parameters:
node - The TreeNode of interest
Returns:
The REToDFAInfo Object associated with the given TreeNode

setUp

protected void setUp(RE<L> theRE,
                     MutableFSAInterface<L> theDFA)
              throws REException
Sets up the builder before the DFA is built.

Parameters:
theRE - The RE to be converted
theDFA - The DFA being built
Throws:
REException - if the set up cannot be completed successfully

tearDown

protected void tearDown()
Tears down the builder after the DFA is built.


caseChoiceNode

public void caseChoiceNode(ChoiceNode<L> node,
                           java.lang.Object context)
                    throws REVisitorException
Allows this REVisitor to process the given ChoiceNode.

Specified by:
caseChoiceNode in interface REVisitor<L extends LabelInterface>
Overrides:
caseChoiceNode in class AbstractREVisitor<L extends LabelInterface>
Parameters:
node - The ChoiceNode to be processed
context - The calling context
Throws:
REVisitorException - if an error occurs

caseConcatenationNode

public void caseConcatenationNode(ConcatenationNode<L> node,
                                  java.lang.Object context)
                           throws REVisitorException
Allows this REVisitor to process the given ConcatenationNode.

Specified by:
caseConcatenationNode in interface REVisitor<L extends LabelInterface>
Overrides:
caseConcatenationNode in class AbstractREVisitor<L extends LabelInterface>
Parameters:
node - The ConcatenationNode to be processed
context - The calling context
Throws:
REVisitorException - if an error occurs

caseEpsilonNode

public void caseEpsilonNode(EpsilonNode<L> node,
                            java.lang.Object context)
Allows this REVisitor to process the given EpsilonNode.

Specified by:
caseEpsilonNode in interface REVisitor<L extends LabelInterface>
Overrides:
caseEpsilonNode in class AbstractREVisitor<L extends LabelInterface>
Parameters:
node - The EpsilonNode to be processed
context - The calling context

caseKleeneStarNode

public void caseKleeneStarNode(KleeneStarNode<L> node,
                               java.lang.Object context)
                        throws REVisitorException
Allows this REVisitor to process the given KleeneStarNode.

Specified by:
caseKleeneStarNode in interface REVisitor<L extends LabelInterface>
Overrides:
caseKleeneStarNode in class AbstractREVisitor<L extends LabelInterface>
Parameters:
node - The KleeneStarNode to be processed
context - The calling context
Throws:
REVisitorException - if an error occurs

caseLabelNode

public void caseLabelNode(LabelNode<L> node,
                          java.lang.Object context)
Allows this REVisitor to process the given LabelNode.

Specified by:
caseLabelNode in interface REVisitor<L extends LabelInterface>
Overrides:
caseLabelNode in class AbstractREVisitor<L extends LabelInterface>
Parameters:
node - The LabelNode to be processed
context - The calling context

caseMarkerNode

public void caseMarkerNode(MarkerNode<L> node,
                           java.lang.Object context)
Allows this REVisitor to process the given MarkerNode.

Overrides:
caseMarkerNode in class AbstractREtoDFAVisitor<L extends LabelInterface>
Parameters:
node - The MarkerNode to be processed
context - The calling context