nfa.java

java语法解释器生成器

      }

    }

    return maxAction;
  }


  /**
   * Calculates the epsilon closure for a specified set of states.
   *
   * The epsilon closure for set a is the set of states that can be reached 
   * by epsilon edges from a.
   *
   * @param set the set of states to calculate the epsilon closure for
   *
   * @return the epsilon closure of the specified set of states 
   *         in this NFA
   */
  private StateSet closure(int startState) {

    // Out.debug("Calculating closure of "+set);

    StateSet notvisited = tempStateSet;
    StateSet closure = new StateSet(numStates,startState);

    notvisited.clear();
    notvisited.addState(startState);

    while ( notvisited.containsElements() ) {
      // Out.debug("closure is now "+closure);
      // Out.debug("notvisited is "+notvisited);
      int state = notvisited.getAndRemoveElement();
      // Out.debug("removed element "+state+" of "+notvisited);
      // Out.debug("epsilon[states] = "+epsilon[state]);
      notvisited.add(closure.complement(epsilon[state]));
      closure.add(epsilon[state]);
    }

    // Out.debug("Closure is : "+closure);

    return closure;
  }

  /**
   * Returns the epsilon closure of a set of states
   */
  private StateSet closure(StateSet startStates) {
    StateSet result = new StateSet(numStates);

    if (startStates != null) {      
      states.reset(startStates);
      while (states.hasMoreElements()) 
        result.add( closure(states.nextElement()) );
    }
      
    return result;
  }
  

  private void epsilonFill() {
    for (int i = 0; i < numStates; i++) {
      epsilon[i] = closure(i);
    }
  }

  /**
   * Calculates the set of states that can be reached from another
   * set of states <code>start</code> with an specified input 
   * character <code>input</code>
   *
   * @param start the set of states to start from
   * @param input the input character for which to search the next states
   *
   * @return the set of states that are reached from <code>start</code> 
   *         via <code>input</code>
   */
  private StateSet DFAEdge(StateSet start, char input) {    
    // Out.debug("Calculating DFAEdge for state set "+start+" and input '"+input+"'");

    tempStateSet.clear();

    states.reset(start);
    while ( states.hasMoreElements() ) 
      tempStateSet.add( table[states.nextElement()][input] );

    StateSet result = new StateSet(tempStateSet);
    
    states.reset(tempStateSet);
    while ( states.hasMoreElements() ) 
      result.add( epsilon[states.nextElement()] );
    
    // Out.debug("DFAEdge is : "+result);

    return result;
  }

  
  /**
   * Returns an DFA that accepts the same language as this NFA.
   * This DFA is usually not minimal.
   */
  public DFA getDFA() {

    Hashtable dfaStates = new Hashtable(numStates);
    Vector dfaVector    = new Vector(numStates);

    DFA dfa = new DFA(numEntryStates(), numInput, numLexStates);

    int numDFAStates = 0;
    int currentDFAState = 0;

    Out.println("Converting NFA to DFA : ");

    epsilonFill();

    StateSet currentState, newState;
    
    // create the initial states of the DFA
    for ( int i = 0;  i < numEntryStates();  i++ ) {
      newState = epsilon[i];
  
      dfaStates.put(newState, new Integer(numDFAStates));
      dfaVector.addElement(newState);
  
      dfa.setEntryState( i, numDFAStates );
        
      dfa.setFinal( numDFAStates, containsFinal(newState) );
      dfa.setAction( numDFAStates, getAction(newState) );

      numDFAStates++;
    }
     
    numDFAStates--;

    if (Options.DEBUG)
      Out.debug("DFA start states are :"+Out.NL+dfaStates+Out.NL+Out.NL+"ordered :"+Out.NL+dfaVector);
     
    currentDFAState = 0;
      
    StateSet tempStateSet = NFA.tempStateSet;    
    StateSetEnumerator states = NFA.states;

    // will be reused
    newState = new StateSet(numStates);

    while ( currentDFAState <= numDFAStates ) {

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

      for (char input = 0; input < numInput; input++) {

	      // newState = DFAEdge(currentState, input);

        // inlining DFAEdge for performance:

        // Out.debug("Calculating DFAEdge for state set "+currentState+" and input '"+input+"'");

        tempStateSet.clear();        
        states.reset(currentState);
        while ( states.hasMoreElements() ) 
          tempStateSet.add( table[states.nextElement()][input] );
        
        newState.copy(tempStateSet);
        
        states.reset(tempStateSet);
        while ( states.hasMoreElements() ) 
          newState.add( epsilon[states.nextElement()] );
    
        // Out.debug("DFAEdge is : "+newState);


	      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!");
	          dfa.addTransition(currentDFAState, input, nextDFAState.intValue());
	        }
	        else {
            if (Options.progress) Out.print(".");
	          // Out.debug("NOT FOUND!");
	          // Out.debug("Table was "+dfaStates);
            numDFAStates++;

            // make a new copy of newState to store in dfaStates
            StateSet storeState = new StateSet(newState);

	          dfaStates.put(storeState, new Integer(numDFAStates));
	          dfaVector.addElement(storeState);
	    
	          dfa.addTransition(currentDFAState, input, numDFAStates);
	          dfa.setFinal( numDFAStates, containsFinal(storeState) );
	          dfa.setAction( numDFAStates, getAction(storeState) );
	        }
	      }
      }
      
      currentDFAState++;     
    }
    
    if (Options.verbose) Out.println("");

    return dfa;
  }


  public void dumpTable() {
    Out.dump(toString());
  }

  public String toString() {
    StringBuffer result = new StringBuffer();

    for (int i=0; i < numStates; i++) {
      result.append("State");
      if ( isFinal[i] ) {
        result.append("[FINAL");
        String l = action[i].lookString();
        if (!l.equals("")) {
          result.append(", ");
          result.append(l);        
        }
        result.append("]");
      }
      result.append(" "+i+Out.NL);
      
      for (char input = 0; input < numInput; input++) {
	      if ( table[i][input] != null && table[i][input].containsElements() ) 
	        result.append("  with "+((int) input)+" in "+table[i][input]+Out.NL);	
        }

      if ( epsilon[i] != null && epsilon[i].containsElements() ) 
	      result.append("  with epsilon in "+epsilon[i]+Out.NL);
    }    
    
    return result.toString();
  }

  public void writeDot(File file) {
    try {
      PrintWriter writer = new PrintWriter(new FileWriter(file));
      writer.println(dotFormat());
      writer.close();
    }
    catch (IOException e) {
      Out.error(ErrorMessages.FILE_WRITE, file);
      throw new GeneratorException();
    }
  }

  public String dotFormat() {
    StringBuffer result = new StringBuffer();

    result.append("digraph NFA {"+Out.NL);
    result.append("rankdir = LR"+Out.NL);

    for (int i=0; i < numStates; i++) {
      if ( isFinal[i] ) {
          result.append(i);
          result.append(" [shape = doublecircle]");
          result.append(Out.NL);
      }      
    }

    for (int i=0; i < numStates; i++) {
      for (int input = 0; input < numInput; input++) {
	      if ( table[i][input] != null ) {
          StateSetEnumerator states = table[i][input].states();
        
          while (states.hasMoreElements()) {
            int s = states.nextElement();
            result.append(i+" -> "+s);
            result.append(" [label=\""+classes.toString(input)+"\"]"+Out.NL);
          }
        }
      }
      if ( epsilon[i] != null ) {
        StateSetEnumerator states = epsilon[i].states();
        while (states.hasMoreElements()) {
          int s = states.nextElement();
          result.append(i+" -> "+s+" [style=dotted]"+Out.NL);
        }
      }
    }

    result.append("}"+Out.NL);

    return result.toString();
  }


  //-----------------------------------------------------------------------
  // Functions for constructing NFAs out of regular expressions.

  private void insertLetterNFA(boolean caseless, char letter, int start, int end) {
    if (caseless) {
      int lower = classes.getClassCode(Character.toLowerCase(letter));
      int upper = classes.getClassCode(Character.toUpperCase(letter));
      addTransition(start, lower, end);
      if (upper != lower) addTransition(start, upper, end);
    }
    else {
      addTransition(start, classes.getClassCode(letter), end);
    }
  }
  
  private IntPair insertStringNFA(boolean caseless, String letters) {
    int start = numStates;
    int i;

    for (i = 0; i < letters.length(); i++) {
      if (caseless) {
        char c = letters.charAt(i);
        int lower = classes.getClassCode(Character.toLowerCase(c));
        int upper = classes.getClassCode(Character.toUpperCase(c));
        addTransition(i+start, lower, i+start+1);
        if (upper != lower) addTransition(i+start, upper, i+start+1);
      }
      else {
        addTransition(i+start, classes.getClassCode(letters.charAt(i)), i+start+1);
      }
    }

    return new IntPair(start, i+start);
  }
  

  private void insertClassNFA(Vector intervalls, int start, int end) {
    // empty char class is ok:
    if (intervalls == null) return;

    int [] cl = classes.getClassCodes(intervalls);    
    for (int i = 0; i < cl.length; i++) 
      addTransition(start, cl[i], end);
  }

  private void insertNotClassNFA(Vector intervalls, int start, int end) {
    int [] cl = classes.getNotClassCodes(intervalls);

    for (int i = 0; i < cl.length; i++) 
      addTransition(start, cl[i], end);
  }
  

  /**