nfa.java

java语法解释器生成器

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
 * JFlex 1.4.2                                                             *
 * Copyright (C) 1998-2008  Gerwin Klein <[e-mail]>                    *
 * All rights reserved.                                                    *
 *                                                                         *
 * This program is free software; you can redistribute it and/or modify    *
 * it under the terms of the GNU General Public License. See the file      *
 * COPYRIGHT for more information.                                         *
 *                                                                         *
 * This program is distributed in the hope that it will be useful,         *
 * but WITHOUT ANY WARRANTY; without even the implied warranty of          *
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the           *
 * GNU General Public License for more details.                            *
 *                                                                         *
 * You should have received a copy of the GNU General Public License along *
 * with this program; if not, write to the Free Software Foundation, Inc., *
 * 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA                 *
 *                                                                         *
 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
package JFlex;

import java.util.*;
import java.io.*;


/**
 * NFA representation in JFlex.
 *
 * Contains algorithms RegExp -> NFA and NFA -> DFA.
 *
 * @author Gerwin Klein
 * @version JFlex 1.4.2, $Revision: 358 $, $Date: 2008-05-27 16:28:29 +1000 (Tue, 27 May 2008) $
 */
final public class NFA {

  /** table[current_state][next_char] is the set of states that can be reached
  /* from current_state with an input next_char */
  StateSet [][] table;

  /** epsilon[current_state] is the set of states that can be reached
  /* from current_state via epsilon edges */
  StateSet [] epsilon;

  /** isFinal[state] == true <=> state is a final state of the NFA */
  boolean [] isFinal;

  /** action[current_state]: the action associated with the state 
  /* current_state (null, if there is no action for the state) */
  Action [] action;

  /** the number of states in this NFA */
  int numStates;

  /** the current maximum number of input characters */
  int numInput;

  /** the number of lexical States. Lexical states have the indices
  /* 0..numLexStates-1 in the transition table */
  int numLexStates;

  /** estimated size of the NFA (before actual construction) */
  int estSize = 256;
  
  Macros macros;
  CharClasses classes;

  LexScan scanner;
  RegExps regExps;

  // will be reused by several methods (avoids excessive object creation)
  private static StateSetEnumerator states = new StateSetEnumerator();
  private static StateSet     tempStateSet = new StateSet();
  
  public NFA(int numInput, int estSize) {
    this.numInput = numInput;
    this.estSize = estSize;
    numStates = 0;
    epsilon = new StateSet [estSize];
    action = new Action [estSize];
    isFinal = new boolean [estSize];
    table = new StateSet [estSize][numInput];
  }

  /** 
   * Construct new NFA.
   * 
   * Assumes that lookahead cases and numbers are already resolved in RegExps.
   * @see RegExps#checkLookAheads()
   */ 
  public NFA(int numInput, LexScan scanner, RegExps regExps, 
             Macros macros, CharClasses classes) {
    this(numInput, regExps.NFASize(macros)+2*scanner.states.number());

    this.scanner = scanner;
    this.regExps = regExps;
    this.macros  = macros;
    this.classes = classes;
    
    numLexStates = scanner.states.number();

    // ensureCapacity assumes correctly set up numStates. 
    int new_num = numEntryStates();
    ensureCapacity(new_num);
    numStates = new_num;
  }
    
  public int numEntryStates() {
    return 2*(numLexStates+regExps.gen_look_count);
  }
  
  /**
   * Add a standalone rule that has minimum priority, fires a transition
   * on all single input characters and has a "print yytext" action.
   */
  public void addStandaloneRule() {
    int start = numStates;
    int end   = numStates+1;

    for (int c = 0; c < classes.getNumClasses(); c++) 
      addTransition(start, c, end);
   
    for (int i = 0; i < numLexStates*2; i++) 
      addEpsilonTransition(i, start);

    action[end]  = new Action("System.out.print(yytext());", Integer.MAX_VALUE);
    isFinal[end] = true;    
  }

  /**
   * Add a regexp to this NFA. 
   * 
   * @param regExpNum   the number of the regexp to add.
   */
  public void addRegExp(int regExpNum) {

    if (Options.DEBUG)
      Out.debug("Adding nfa for regexp "+regExpNum+" :"+Out.NL+regExps.getRegExp(regExpNum));
    
    IntPair nfa = insertNFA( regExps.getRegExp(regExpNum) );
    
    Enumeration lexStates = regExps.getStates(regExpNum).elements();
    
    if ( !lexStates.hasMoreElements() )
      lexStates = scanner.states.getInclusiveStates();

    while ( lexStates.hasMoreElements() ) {
      int stateNum = ((Integer)lexStates.nextElement()).intValue();
        
      if ( !regExps.isBOL(regExpNum) )
        addEpsilonTransition(2*stateNum, nfa.start);
      
      addEpsilonTransition(2*stateNum+1, nfa.start);        
    }
        
        
    if ( regExps.getLookAhead(regExpNum) != null ) {
      Action a = regExps.getAction(regExpNum);

      if (a.lookAhead() == Action.FINITE_CHOICE) {
        insertLookAheadChoices(nfa.end, a, regExps.getLookAhead(regExpNum));
        // remove the original action from the collection: it will never
        // be matched directly, only its copies will.
        scanner.actions.remove(a);
      }
      else {
        RegExp r1 = regExps.getRegExp(regExpNum);
        RegExp r2 = regExps.getLookAhead(regExpNum);
  
        IntPair look = insertNFA(r2);
        
        addEpsilonTransition(nfa.end, look.start);
  
        action[look.end]  = a;
        isFinal[look.end] = true;
  
        if (a.lookAhead() == Action.GENERAL_LOOK) {
          // base forward pass
          IntPair forward = insertNFA(r1);
          // lookahead backward pass
          IntPair backward = insertNFA(r2.rev(macros));
          
          isFinal[forward.end] = true;
          action[forward.end] = new Action(Action.FORWARD_ACTION);
          
          isFinal[backward.end] = true;
          action[backward.end] = new Action(Action.BACKWARD_ACTION);
          
          int entry = 2*(regExps.getLookEntry(regExpNum) + numLexStates);
          addEpsilonTransition(entry, forward.start);
          addEpsilonTransition(entry+1, backward.start);
          
          a.setEntryState(entry);
        }
      }
    }
    else {
      action[nfa.end] = regExps.getAction(regExpNum);
      isFinal[nfa.end] = true;
    }
  }

  /**
   * Insert NFAs for the (finitely many) fixed length lookahead choices.
   * 
   * @param lookAhead   a lookahead of which isFiniteChoice is true
   * @param baseEnd     the end state of the base expression NFA
   * @param a           the action of the expression
   *  
   * @see SemCheck#isFiniteChoice(RegExp) 
   */
  private void insertLookAheadChoices(int baseEnd, Action a, RegExp lookAhead) {
    if (lookAhead.type == sym.BAR) {
      RegExp2 r = (RegExp2) lookAhead;
      insertLookAheadChoices(baseEnd, a, r.r1);
      insertLookAheadChoices(baseEnd, a, r.r2);
    }
    else {
      int len = SemCheck.length(lookAhead);
      
      if (len >= 0) {
        // termination case
        IntPair look = insertNFA(lookAhead);
        
        addEpsilonTransition(baseEnd, look.start);
  
        Action x = a.copyChoice(len);
        action[look.end]  = x;
        isFinal[look.end] = true;
        
        // add new copy to the collection of known actions such that
        // it can be checked for the NEVER_MATCH warning.
        scanner.actions.add(x);
      }
      else {
        // should never happen
        throw new Error("When inserting lookahead expression: unkown expression type "+lookAhead.type+" in "+lookAhead); //$NON-NLS-1$ //$NON-NLS-2$
      }
    }
  }

  /**
   * Make sure the NFA can contain at least newNumStates states. 
   * 
   * @param newNumStates  the minimu number of states. 
   */
  private void ensureCapacity(int newNumStates) {
    int oldLength = epsilon.length;
    
    if ( newNumStates < oldLength ) return;
      
    int newStatesLength = Math.max(oldLength*2, newNumStates);

    boolean [] newFinal   = new boolean [newStatesLength];
    boolean [] newIsPush  = new boolean [newStatesLength];
    Action  [] newAction  = new Action  [newStatesLength];
    StateSet [] [] newTable = new StateSet [newStatesLength] [numInput];
    StateSet [] newEpsilon  = new StateSet [newStatesLength];

    System.arraycopy(isFinal,0,newFinal,0,numStates);
    System.arraycopy(action,0,newAction,0,numStates);
    System.arraycopy(epsilon,0,newEpsilon,0,numStates);
    System.arraycopy(table,0,newTable,0,numStates);

    isFinal     = newFinal;
    action      = newAction;
    epsilon     = newEpsilon;
    table       = newTable;
  }
  
  public void addTransition(int start, int input, int dest) {
    Out.debug("Adding transition ("+start+", "+input+", "+dest+")");
    
    int maxS = Math.max(start,dest)+1;
 
    ensureCapacity( maxS );

    if (maxS > numStates) numStates = maxS;

    if ( table[start][input] != null ) 
      table[start][input].addState(dest); 
    else 
      table[start][input] = new StateSet(estSize,dest);
  }

  public void addEpsilonTransition(int start, int dest) {
    int max = Math.max(start,dest)+1;
    ensureCapacity( max );
    if (max > numStates) numStates = max;

    if (epsilon[start] != null)
      epsilon[start].addState(dest); 
    else
      epsilon[start] = new StateSet(estSize,dest);
  }


  /**
   * Returns <code>true</code>, iff the specified set of states
   * contains a final state.
   *
   * @param set   the set of states that is tested for final states.
   */
  private boolean containsFinal(StateSet set) {
    states.reset(set);

    while ( states.hasMoreElements() ) 
      if ( isFinal[states.nextElement()] ) return true;

    return false;
  }


  /**
   * Returns <code>true</code>, iff the specified set of states
   * contains a pushback-state.
   *
   * @param set   the set of states that is tested for pushback-states.
  private boolean containsPushback(StateSet set) {
    states.reset(set);

    while ( states.hasMoreElements() ) 
      if ( isPushback[states.nextElement()] ) return true;

    return false;
  }
  */

  /**
   * Returns the action with highest priority in the specified 
   * set of states.
   *
   * @param set  the set of states for which to determine the action
   */
  private Action getAction(StateSet set) {

    states.reset(set);
    
    Action maxAction = null;

    Out.debug("Determining action of : "+set);

    while ( states.hasMoreElements() ) {

      Action currentAction = action[ states.nextElement() ];
      
      if ( currentAction != null ) {
	      if (maxAction == null) 
	        maxAction = currentAction;
	      else
	        maxAction = maxAction.getHigherPriority(currentAction);