dfa.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.io.*;
import java.util.*;


/**
 * DFA representation in JFlex.
 * Contains minimization algorithm.
 *
 * @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 DFA { 

  /**
   * The initial number of states 
   */
  private static final int STATES = 500;
  
  /**
   * The code for "no target state" in the transition table.
   */
  public static final int NO_TARGET = -1;

  /**
   * table[current_state][character] is the next state for <code>current_state</code>
   * with input <code>character</code>, <code>NO_TARGET</code> if there is no transition for
   * this input in <code>current_state</code>
   */
  int [][] table;


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

  
  /**
   * <code>action[state]</code> is the action that is to be carried out in
   * state <code>state</code>, <code>null</code> if there is no action.
   */
  Action [] action;

  /**
   * entryState[i] is the start-state of lexical state i or 
   * lookahead DFA i
   */
  int entryState [];

  /**
   * The number of states in this DFA
   */
  int numStates;

  /**
   * The current maximum number of input characters
   */
  int numInput;
    
  /**
   * The number of lexical states (2*numLexStates <= entryState.length)
   */
  int numLexStates;

  /**
   * all actions that are used in this DFA
   */
  Hashtable usedActions = new Hashtable();

  /** True iff this DFA contains general lookahead */
  boolean lookaheadUsed;
  
  public DFA(int numEntryStates, int numInp, int numLexStates) {
    numInput = numInp; 
    
    int statesNeeded = Math.max(numEntryStates, STATES);
    
    table       = new int [statesNeeded] [numInput];
    action      = new Action [statesNeeded];
    isFinal     = new boolean [statesNeeded];
    entryState  = new int [numEntryStates];
    numStates   = 0;

    this.numLexStates = numLexStates;
    
    for (int i = 0; i < statesNeeded; i++) {
      for (char j = 0; j < numInput; j++)
	      table [i][j] = NO_TARGET;    
    }
  }


  public void setEntryState(int eState, int trueState) {
    entryState[eState] = trueState;
  }

  private void ensureStateCapacity(int newNumStates) {
    int oldLength = isFinal.length;
    
    if ( newNumStates < oldLength ) return;
      
    int newLength = oldLength*2;
    while ( newLength <= newNumStates ) newLength*= 2;

    boolean [] newFinal    = new boolean [newLength];
    boolean [] newPushback = new boolean [newLength];
    Action  [] newAction   = new Action  [newLength];
    int [] []  newTable    = new int [newLength] [numInput];
    
    System.arraycopy(isFinal,0,newFinal,0,numStates);
    System.arraycopy(action,0,newAction,0,numStates);
    System.arraycopy(table,0,newTable,0,oldLength);
  
    int i,j;
  
    for (i = oldLength; i < newLength; i++) {
      for (j = 0; j < numInput; j++) {
        newTable[i][j] = NO_TARGET;
      }
    }

    isFinal    = newFinal;
    action     = newAction;
    table      = newTable;
  }


  public void setAction(int state, Action stateAction) {
    action[state]    = stateAction;
    if (stateAction != null) {
      usedActions.put(stateAction,stateAction);
      lookaheadUsed |= stateAction.isGenLookAction();
    }
  }
  
  public void setFinal(int state, boolean isFinalState) {
    isFinal[state] = isFinalState;
  }

  public void addTransition(int start, char input, int dest) {
    int max = Math.max(start,dest)+1;
    ensureStateCapacity(max);
    if (max > numStates) numStates = max;

    //  Out.debug("Adding DFA transition ("+start+", "+(int)input+", "+dest+")");

    table[start][input] = dest;
  }


  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 j=0; j < numInput; j++) {
	      if ( table[i][j] >= 0 ) 
	        result.append("  with "+(int)j+" in "+table[i][j]+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 DFA {"+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] >= 0 ) {
          result.append(i+" -> "+table[i][input]);
          result.append(" [label=\"["+input+"]\"]"+Out.NL);
          //          result.append(" [label=\"["+classes.toString(input)+"]\"]\n");
        }
      }
    }

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

    return result.toString();
  }


  /**
   * Check that all actions can actually be matched in this DFA.
   */ 
  public void checkActions(LexScan scanner, LexParse parser) {
    EOFActions eofActions = parser.getEOFActions();
    Enumeration l = scanner.actions.elements();

    while (l.hasMoreElements()) {
      Action a = (Action) l.nextElement();
      if ( !a.equals(usedActions.get(a)) && !eofActions.isEOFAction(a) ) {
        Out.warning(scanner.file, ErrorMessages.NEVER_MATCH, a.priority-1, -1);
      }
    }
  }


  /**
   * Implementation of Hopcroft's O(n log n) minimization algorithm, follows
   * description by D. Gries.
   *
   * Time: O(n log n)
   * Space: O(c n), size < 4*(5*c*n + 13*n + 3*c) byte
   */
  public void minimize() {
    Out.print(numStates+" states before minimization, ");

    if (numStates == 0) {
      Out.error(ErrorMessages.ZERO_STATES);
      throw new GeneratorException();
    }

    if (Options.no_minimize) {
      Out.println("minimization skipped.");
      return;
    }

    // the algorithm needs the DFA to be total, so we add an error state 0,
    // and translate the rest of the states by +1
    final int n = numStates+1;

    // block information:
    // [0..n-1] stores which block a state belongs to,
    // [n..2*n-1] stores how many elements each block has
    int [] block = new int[2*n];    

    // implements a doubly linked list of states (these are the actual blocks)
    int [] b_forward = new int[2*n];
    int [] b_backward = new int[2*n];   

    // the last of the blocks currently in use (in [n..2*n-1])
    // (end of list marker, points to the last used block)
    int lastBlock = n;  // at first we start with one empty block
    final int b0 = n;   // the first block    

    // the circular doubly linked list L of pairs (B_i, c)
    // (B_i, c) in L iff l_forward[(B_i-n)*numInput+c] > 0 // numeric value of block 0 = n!
    int [] l_forward = new int[n*numInput+1];
    int [] l_backward = new int[n*numInput+1];
    int anchorL = n*numInput; // list anchor

    // inverse of the transition table
    // if t = inv_delta[s][c] then { inv_delta_set[t], inv_delta_set[t+1], .. inv_delta_set[k] }
    // is the set of states, with inv_delta_set[k] = -1 and inv_delta_set[j] >= 0 for t <= j < k  
    int [] [] inv_delta = new int[n][numInput];
    int [] inv_delta_set = new int [2*n*numInput]; 

    // twin stores two things: 
    // twin[0]..twin[numSplit-1] is the list of blocks that have been split
    // twin[B_i] is the twin of block B_i
    int [] twin = new int[2*n];
    int numSplit;

    // SD[B_i] is the the number of states s in B_i with delta(s,a) in B_j
    // if SD[B_i] == block[B_i], there is no need to split
    int [] SD = new int[2*n]; // [only SD[n..2*n-1] is used]


    // for fixed (B_j,a), the D[0]..D[numD-1] are the inv_delta(B_j,a)
    int [] D = new int[n];
    int numD;    

    
    // initialize inverse of transition table
    int lastDelta = 0;
    int [] inv_lists = new int[n]; // holds a set of lists of states
    int [] inv_list_last = new int[n]; // the last element
    for (int c = 0; c < numInput; c++) {
      // clear "head" and "last element" pointers
      for (int s = 0; s < n; s++) {
        inv_list_last[s] = -1;
        inv_delta[s][c] = -1;
      }
      
      // the error state has a transition for each character into itself
      inv_delta[0][c] = 0;
      inv_list_last[0] = 0;

      // accumulate states of inverse delta into lists (inv_delta serves as head of list)
      for (int s = 1; s < n; s++) {
        int t = table[s-1][c]+1;

        if (inv_list_last[t] == -1) { // if there are no elements in the list yet
          inv_delta[t][c] = s;  // mark t as first and last element
          inv_list_last[t] = s;
        }
        else {
          inv_lists[inv_list_last[t]] = s; // link t into chain
          inv_list_last[t] = s; // and mark as last element
        }
      }

      // now move them to inv_delta_set in sequential order, 
      // and update inv_delta accordingly
      for (int s = 0; s < n; s++) {
        int i = inv_delta[s][c];  inv_delta[s][c] = lastDelta;
        int j = inv_list_last[s];
        boolean go_on = (i != -1);
        while (go_on) {
          go_on = (i != j);
          inv_delta_set[lastDelta++] = i;
          i = inv_lists[i];
        }
        inv_delta_set[lastDelta++] = -1;
      }
    } // of initialize inv_delta

    // printInvDelta(inv_delta, inv_delta_set);

    // initialize blocks 
    
    // make b0 = {0}  where 0 = the additional error state
    b_forward[b0]  = 0;
    b_backward[b0] = 0;          
    b_forward[0]   = b0;
    b_backward[0]  = b0;
    block[0]  = b0;
    block[b0] = 1;

    for (int s = 1; s < n; s++) {
      // System.out.println("Checking state ["+(s-1)+"]");
      // search the blocks if it fits in somewhere
      // (fit in = same pushback behavior, same finalness, same lookahead behavior, same action)
      int b = b0+1; // no state can be equivalent to the error state
      boolean found = false;
      while (!found && b <= lastBlock) {
        // get some state out of the current block
        int t = b_forward[b];
        // System.out.println("  picking state ["+(t-1)+"]");

        // check, if s could be equivalent with t
        if (isFinal[s-1]) {
          found = isFinal[t-1] && action[s-1].isEquiv(action[t-1]);
        }
        else {
          found = !isFinal[t-1];
        }
      
        if (found) { // found -> add state s to block b
          // System.out.println("Found! Adding to block "+(b-b0));
          // update block information
          block[s] = b;
          block[b]++;
          
          // chain in the new element
          int last = b_backward[b];
          b_forward[last] = s;
          b_forward[s] = b;
          b_backward[b] = s;
          b_backward[s] = last;
        }

        b++;
      }
      
      if (!found) { // fits in nowhere -> create new block
        // System.out.println("not found, lastBlock = "+lastBlock);

        // update block information
        block[s] = b;
        block[b]++;
        
        // chain in the new element
        b_forward[b] = s;
        b_forward[s] = b;
        b_backward[b] = s;
        b_backward[s] = b;
        
        lastBlock++;
      }
    } // of initialize blocks
  
    // printBlocks(block,b_forward,b_backward,lastBlock);

    // initialize worklist L
    // first, find the largest block B_max, then, all other (B_i,c) go into the list
    int B_max = b0;
    int B_i;
    for (B_i = b0+1; B_i <= lastBlock; B_i++)
      if (block[B_max] < block[B_i]) B_max = B_i;
    
    // L = empty
    l_forward[anchorL] = anchorL;
    l_backward[anchorL] = anchorL;

    // set up the first list element
    if (B_max == b0) B_i = b0+1; else B_i = b0; // there must be at least two blocks    

    int index = (B_i-b0)*numInput;  // (B_i, 0)
    while (index < (B_i+1-b0)*numInput) {
      int last = l_backward[anchorL];
      l_forward[last]     = index;
      l_forward[index]    = anchorL;
      l_backward[index]   = last;
      l_backward[anchorL] = index;
      index++;
    }

    // now do the rest of L
    while (B_i <= lastBlock) {
      if (B_i != B_max) {
        index = (B_i-b0)*numInput;
        while (index < (B_i+1-b0)*numInput) {