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

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

public class REtoNFAConverter<L extends LabelInterface>
extends AbstractREVisitor<L>

The REtoNFAConverter class converts from a basic Regular Expression (RE) to a Non-Deterministic Finite State Automaton (NFA). NOTE:

A basic RE only uses following operators: choice, concatenation, and kleene star.

Author:
Jamieson M. Cobleigh (laser-software@cs.umass.edu) FUTURE: For now, the label patterns are not being supported since they may interact badly with the alphabet specification and (not) class set specifications.

Field Summary
 
Fields inherited from class laser.regularlanguage.regularexpression.AbstractREVisitor
result
 
Constructor Summary
REtoNFAConverter(RLFactory<L> rlFactory, FSAFactoryInterface<L> fsaFactory)
          Creates a new REtoNFAConverter.
 
Method Summary
protected  FSAEpsilonTransitionInterface<L> addEpsilonTransition(FSAStateInterface<L> source, FSAStateInterface<L> target)
          Adds a transition from source to target on epsilon.
protected  FSALabelTransitionInterface<L> addLabelTransition(FSAStateInterface<L> source, FSAStateInterface<L> target, L label)
          Adds a transition from source to target on the given label.
 void caseChoiceNode(ChoiceNode<L> node, java.lang.Object context)
          Converts the given ChoiceNode into a sub-NFA that represents the alternation of the children sub-NFA.
 void caseConcatenationNode(ConcatenationNode<L> node, java.lang.Object context)
          Converts the given ConcatenationNode into a sub-NFA that represents the concatenation of the children sub-NFA.
 void caseEmptyNode(EmptyNode<L> node, java.lang.Object context)
          Creates an NFA that has two states: the start and trap state that are both non-accepting sinks.
 void caseEpsilonNode(EpsilonNode<L> node, java.lang.Object context)
          Converts the given EpsilonNode into a sub-NFA that represents an epsilon transition.
 void caseKleeneStarNode(KleeneStarNode<L> node, java.lang.Object context)
          Converts the given KleeneStartNode into a sub-NFA that represents the kleene star of its child sub-NFA.
 void caseLabelNode(LabelNode<L> node, java.lang.Object context)
          Converts the given LabelNode into a sub-NFA that represents the label or label pattern transition.
 MutableFSAInterface<L> convert(RE<L> theRE)
          Converts the given (basic) RE into its corresponding NFA.
protected  laser.regularlanguage.util.REtoNFAConverter.REtoNFAInfo convert(TreeNode<L> node)
          Converts from an RE to an NFA
protected  java.lang.Object[] getCreateArgsForState(MutableFSAInterface<L> newFSA, TreeNode<L> oldTreeNode)
          Gets any required arguments for the state factory method from the given TreeNode.
 
Methods inherited from class laser.regularlanguage.regularexpression.AbstractREVisitor
caseClassSetNode, caseDotNode, 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

REtoNFAConverter

public REtoNFAConverter(RLFactory<L> rlFactory,
                        FSAFactoryInterface<L> fsaFactory)
Creates a new REtoNFAConverter.

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

convert

public MutableFSAInterface<L> convert(RE<L> theRE)
                                                      throws FSAInterfaceException,
                                                             REException
Converts the given (basic) RE into its corresponding NFA.

PRECONDITIONS:

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

convert

protected laser.regularlanguage.util.REtoNFAConverter.REtoNFAInfo convert(TreeNode<L> node)
                                                                   throws REVisitorException
Converts from an RE to an NFA

Parameters:
node - The RE to be converted
Returns:
The REtoNFAInfo object detailing the conversion
Throws:
REVisitorException - if an error occurs

getCreateArgsForState

protected java.lang.Object[] getCreateArgsForState(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

addEpsilonTransition

protected FSAEpsilonTransitionInterface<L> addEpsilonTransition(FSAStateInterface<L> source,
                                                                FSAStateInterface<L> target)
Adds a transition from source to target on epsilon.

Parameters:
source - The source for the new transition
target - The target for the new transition
Returns:
The new epsilon transition

addLabelTransition

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

Parameters:
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

caseChoiceNode

public void caseChoiceNode(ChoiceNode<L> node,
                           java.lang.Object context)
                    throws REVisitorException
Converts the given ChoiceNode into a sub-NFA that represents the alternation of the children sub-NFA.

Specified by:
caseChoiceNode in interface REVisitor<L extends LabelInterface>
Overrides:
caseChoiceNode in class AbstractREVisitor<L extends LabelInterface>
Parameters:
node - The ChoiceNode to be converted
context - This is currently not being used
Throws:
REVisitorException - if an error occurs

caseConcatenationNode

public void caseConcatenationNode(ConcatenationNode<L> node,
                                  java.lang.Object context)
                           throws REVisitorException
Converts the given ConcatenationNode into a sub-NFA that represents the concatenation of the children sub-NFA.

Specified by:
caseConcatenationNode in interface REVisitor<L extends LabelInterface>
Overrides:
caseConcatenationNode in class AbstractREVisitor<L extends LabelInterface>
Parameters:
node - The ConcatenationNode to be converted
context - This is currently not being used
Throws:
REVisitorException - if an error occurs

caseEmptyNode

public void caseEmptyNode(EmptyNode<L> node,
                          java.lang.Object context)
                   throws REVisitorException
Creates an NFA that has two states: the start and trap state that are both non-accepting sinks.

NOTE: This is a base case.

Specified by:
caseEmptyNode in interface REVisitor<L extends LabelInterface>
Overrides:
caseEmptyNode in class AbstractREVisitor<L extends LabelInterface>
Parameters:
node - The EmptyNode to be converted
context - This is currently not being used
Throws:
REVisitorException - if an error occurs

caseEpsilonNode

public void caseEpsilonNode(EpsilonNode<L> node,
                            java.lang.Object context)
                     throws REVisitorException
Converts the given EpsilonNode into a sub-NFA that represents an epsilon transition. NOTE: This is a base case.

Specified by:
caseEpsilonNode in interface REVisitor<L extends LabelInterface>
Overrides:
caseEpsilonNode in class AbstractREVisitor<L extends LabelInterface>
Parameters:
node - The EpsilonNode to be converted
context - This is currently not being used
Throws:
REVisitorException - if the epsilonTransition cannot be added

caseKleeneStarNode

public void caseKleeneStarNode(KleeneStarNode<L> node,
                               java.lang.Object context)
                        throws REVisitorException
Converts the given KleeneStartNode into a sub-NFA that represents the kleene star of its child sub-NFA.

Specified by:
caseKleeneStarNode in interface REVisitor<L extends LabelInterface>
Overrides:
caseKleeneStarNode in class AbstractREVisitor<L extends LabelInterface>
Parameters:
node - The KleeneStarNode to be converted
context - This is currently not being used
Throws:
REVisitorException - if an error occurs

caseLabelNode

public void caseLabelNode(LabelNode<L> node,
                          java.lang.Object context)
                   throws REVisitorException
Converts the given LabelNode into a sub-NFA that represents the label or label pattern transition.

NOTE: This is a base case.

Specified by:
caseLabelNode in interface REVisitor<L extends LabelInterface>
Overrides:
caseLabelNode in class AbstractREVisitor<L extends LabelInterface>
Parameters:
node - The LabelNode to be converted
context - This is currently not being used
Throws:
REVisitorException - if the label or label pattern transition cannot be added