Logo Search packages:      
Sourcecode: jflex version File versions

IntPair JFlex::NFA::complement ( IntPair  nfa  )  [inline]

Constructs an NFA accepting the complement of the language of a given NFA.

Converts the NFA into a DFA, then negates that DFA. Exponential state blowup possible and common.

Parameters:
the NFA to construct the complement for.
Returns:
a pair of integers denoting the index of start and end state of the complement NFA.

Definition at line 605 of file NFA.java.

References JFlex::StateSet::containsElements(), DFAEdge(), JFlex::IntPair::end, JFlex::StateSet::isElement(), and JFlex::IntPair::start.

Referenced by insertNFA().

                                         {

    if (Out.DEBUG) {
      Out.debug("complement for "+nfa);
      Out.debug("NFA is :"+Out.NL+this);
    }

    int dfaStart = nfa.end+1; 
    
    // fixme: only need epsilon closure of states reachable from nfa.start
    epsilonFill();
    
    Hashtable dfaStates = new Hashtable(numStates);
    Vector dfaVector    = new Vector(numStates);

    int numDFAStates = 0;
    int currentDFAState = 0;

    StateSet currentState, newState;
    
    newState = epsilon[nfa.start];
    dfaStates.put(newState, new Integer(numDFAStates));
    dfaVector.addElement(newState);

    if (Out.DEBUG)
      Out.debug("pos DFA start state is :"+Out.NL+dfaStates+Out.NL+Out.NL+"ordered :"+Out.NL+dfaVector);
     
    currentDFAState = 0;
      
    while ( currentDFAState <= numDFAStates ) {

      currentState = (StateSet) dfaVector.elementAt(currentDFAState);

      for (char input = 0; input < numInput; input++) {
            newState = DFAEdge(currentState, input);

            if ( newState.containsElements() ) {

          // Out.debug("DFAEdge for input "+(int)input+" and state set "+currentState+" is "+newState);
       
              // Out.debug("Looking for state set "+newState);
              Integer nextDFAState = (Integer) dfaStates.get(newState);

              if ( nextDFAState != null ) {
                // Out.debug("FOUND!");
            addTransition(dfaStart+currentDFAState, input, dfaStart+nextDFAState.intValue());
              }
              else {
            if (Out.DUMP) Out.print("+");
                // Out.debug("NOT FOUND!");
                // Out.debug("Table was "+dfaStates);
            numDFAStates++;

                dfaStates.put(newState, new Integer(numDFAStates));
                dfaVector.addElement(newState);

            addTransition(dfaStart+currentDFAState, input, dfaStart+numDFAStates);
              }
            }
      }
      
      currentDFAState++;     
    }   
    
    // We have a dfa accepting the positive regexp. 

    // Now the complement:    
    if (Out.DEBUG) 
      Out.debug("dfa finished, nfa is now :"+Out.NL+this);

    int start = dfaStart+numDFAStates+1;
    int error = dfaStart+numDFAStates+2;
    int end   = dfaStart+numDFAStates+3; 

    addEpsilonTransition(start, dfaStart);

    for (int i = 0; i < numInput; i++)
      addTransition(error, i, error);

    addEpsilonTransition(error, end);

    for (int s = 0; s <= numDFAStates; s++) {
      currentState = (StateSet) dfaVector.elementAt(s);
      
      currentDFAState = dfaStart+s;

      // if it was not a final state, it is now in the complement
      if (!currentState.isElement(nfa.end)) 
        addEpsilonTransition(currentDFAState, end);

      // all inputs not present (formerly leading to an implicit error)
      // now lead to an explicit (final) state accepting everything.
      for (int i = 0; i < numInput; i++)
        if (table[currentDFAState][i] == null)
          addTransition(currentDFAState, i, error);
    }

    // eliminate transitions leading to dead states
    if (live.length < numStates) {
      live    = new boolean [2*numStates];
      visited = new boolean [2*numStates];
    }

    _end = end;
    _dfaStates = dfaVector;
    _dfaStart = dfaStart;    
    removeDead(dfaStart);

    if (Out.DEBUG)
      Out.debug("complement finished, nfa ("+start+","+end+") is now :"+this);

    return new IntPair(start, end);
  }


Generated by  Doxygen 1.6.0   Back to index