nfastate.java

来自「java 编译器java复杂编译器,可以编译java文件的类库」· Java 代码 · 共 2,249 行 · 第 1/5 页

/*
 * Copyright © 2002 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
 * California 95054, U.S.A. All rights reserved.  Sun Microsystems, Inc. has
 * intellectual property rights relating to technology embodied in the product
 * that is described in this document. In particular, and without limitation,
 * these intellectual property rights may include one or more of the U.S.
 * patents listed at http://www.sun.com/patents and one or more additional
 * patents or pending patent applications in the U.S. and in other countries.
 * U.S. Government Rights - Commercial software. Government users are subject
 * to the Sun Microsystems, Inc. standard license agreement and applicable
 * provisions of the FAR and its supplements.  Use is subject to license terms.
 * Sun,  Sun Microsystems,  the Sun logo and  Java are trademarks or registered
 * trademarks of Sun Microsystems, Inc. in the U.S. and other countries.  This
 * product is covered and controlled by U.S. Export Control laws and may be
 * subject to the export or import laws in other countries.  Nuclear, missile,
 * chemical biological weapons or nuclear maritime end uses or end users,
 * whether direct or indirect, are strictly prohibited.  Export or reexport
 * to countries subject to U.S. embargo or to entities identified on U.S.
 * export exclusion lists, including, but not limited to, the denied persons
 * and specially designated nationals lists is strictly prohibited.
 */

package org.javacc.parser;

import java.util.*;

public class NfaState
{
   public static boolean unicodeWarningGiven = false;
   public static int generatedStates = 0;
   static int idCnt = 0;
   static int lohiByteCnt;
   static int dummyStateIndex = -1;
   static boolean done;
   static boolean mark[];
   static boolean stateDone[];
   static boolean nonAsciiIntersections[][] = new boolean[20][20];

   static Vector allStates = new Vector();
   static Vector indexedAllStates = new Vector();
   static Vector nonAsciiTableForMethod = new Vector();
   static Hashtable equivStatesTable = new Hashtable();
   static Hashtable allNextStates = new Hashtable();
   static Hashtable lohiByteTab = new Hashtable();
   static Hashtable stateNameForComposite = new Hashtable();
   static Hashtable compositeStateTable = new Hashtable();
   static Hashtable stateBlockTable = new Hashtable();
   static Hashtable stateSetsToFix = new Hashtable();

   public static void ReInit()
   {
      generatedStates = 0;
      idCnt = 0;
      dummyStateIndex = -1;
      done = false;
      mark = null;
      stateDone = null;

      allStates.removeAllElements();
      indexedAllStates.removeAllElements();
      equivStatesTable.clear();
      allNextStates.clear();
      compositeStateTable.clear();
      stateBlockTable.clear();
      stateNameForComposite.clear();
      stateSetsToFix.clear();
   }

   long[] asciiMoves = new long[2];
   char[] charMoves = null;
   char[] rangeMoves = null;
   NfaState next = null;
   NfaState stateForCase;
   Vector epsilonMoves = new Vector();
   String epsilonMovesString;
   NfaState[] epsilonMoveArray;

   int id;
   int stateName = -1;
   int kind = Integer.MAX_VALUE;
   int lookingFor;
   int usefulEpsilonMoves = 0;
   int inNextOf;
   private int lexState;
   int nonAsciiMethod = -1;
   int kindToPrint = Integer.MAX_VALUE;
   boolean dummy = false;
   boolean isComposite = false;
   int[] compositeStates = null;
   boolean isFinal = false;
   public Vector loByteVec;
   public int[] nonAsciiMoveIndices;
   int round = 0;
   int onlyChar = 0;
   char matchSingleChar;

   NfaState()
   {
      id = idCnt++;
      allStates.addElement(this);
      lexState = LexGen.lexStateIndex;
      lookingFor = LexGen.curKind;
   }

   NfaState CreateClone()
   {
      NfaState retVal = new NfaState();

      retVal.isFinal = isFinal;
      retVal.kind = kind;
      retVal.lookingFor = lookingFor;
      retVal.lexState = lexState;
      retVal.inNextOf = inNextOf;

      retVal.MergeMoves(this);

      return retVal;
   }

   static void InsertInOrder(Vector v, NfaState s)
   {
      int j;

      for (j = 0; j < v.size(); j++)
         if (((NfaState)v.elementAt(j)).id > s.id)
            break;
         else if (((NfaState)v.elementAt(j)).id  == s.id)
            return;

      v.insertElementAt(s, j);
   }

   private static char[] ExpandCharArr(char[] oldArr, int incr)
   {
      char[] ret = new char[oldArr.length + incr];
      System.arraycopy(oldArr, 0, ret, 0, oldArr.length);
      return ret;
   }

   void AddMove(NfaState newState)
   {
      if (!epsilonMoves.contains(newState))
         InsertInOrder(epsilonMoves, newState);
   }

   private final void AddASCIIMove(char c)
   {
      asciiMoves[c / 64] |= (1L << (c % 64));
   }

   void AddChar(char c)
   {
      onlyChar++;
      matchSingleChar = c;
      int i;
      char temp;
      char temp1;

      if ((int)c < 128) // ASCII char
      {
         AddASCIIMove(c);
         return;
      }

      if (charMoves == null)
         charMoves = new char[10];

      int len = charMoves.length;

      if (charMoves[len - 1] != 0)
      {
         charMoves = ExpandCharArr(charMoves, 10);
         len += 10;
      }

      for (i = 0; i < len; i++)
         if (charMoves[i] == 0 || charMoves[i] > c)
            break;

      if (!unicodeWarningGiven && c > 0xff &&
          !Options.B("JAVA_UNICODE_ESCAPE") &&
          !Options.B("USER_CHAR_STREAM"))
      {
         unicodeWarningGiven = true;
         JavaCCErrors.warning(LexGen.curRE, "Non-ASCII characters used in regular expression.\n" +
              "Please make sure you use the correct Reader when you create the parser that can handle your character set.");
      }

      temp = charMoves[i];
      charMoves[i] = c;

      for (i++; i < len; i++)
      {
         if (temp == 0)
            break;

         temp1 = charMoves[i];
         charMoves[i] = temp;
         temp = temp1;
      }
   }

   void AddRange(char left, char right)
   {
      onlyChar = 2;
      int i;
      char tempLeft1, tempLeft2, tempRight1, tempRight2;

      if (left < 128)
      {
         if (right < 128)
         {
            for (; left <= right; left++)
               AddASCIIMove(left);

            return;
         }

         for (; left < 128; left++)
            AddASCIIMove(left);
      }

      if (!unicodeWarningGiven && (left > 0xff || right > 0xff) &&
          !Options.B("JAVA_UNICODE_ESCAPE") &&
          !Options.B("USER_CHAR_STREAM"))
      {
         unicodeWarningGiven = true;
         JavaCCErrors.warning(LexGen.curRE, "Non-ASCII characters used in regular expression.\n" +
              "Please make sure you use the correct Reader when you create the parser that can handle your character set.");
      }

      if (rangeMoves == null)
         rangeMoves = new char[20];

      int len = rangeMoves.length;

      if (rangeMoves[len - 1] != 0)
      {
         rangeMoves = ExpandCharArr(rangeMoves, 20);
         len += 20;
      }

      for (i = 0; i < len; i += 2)
         if (rangeMoves[i] == 0 ||
             (rangeMoves[i] > left) ||
             ((rangeMoves[i] == left) && (rangeMoves[i + 1] > right)))
            break;

      tempLeft1 = rangeMoves[i];
      tempRight1 = rangeMoves[i + 1];
      rangeMoves[i] = left;
      rangeMoves[i + 1] = right;

      for (i += 2; i < len; i += 2)
      {
         if (tempLeft1 == 0)
            break;

         tempLeft2 = rangeMoves[i];
         tempRight2 = rangeMoves[i + 1];
         rangeMoves[i] = tempLeft1;
         rangeMoves[i + 1] = tempRight1;
         tempLeft1 = tempLeft2;
         tempRight1 = tempRight2;
      }
   }

   // From hereon down all the functions are used for code generation

   private static boolean EqualCharArr(char[] arr1, char[] arr2)
   {
      if (arr1 == arr2)
         return true;

      if (arr1 != null &&
          arr2 != null &&
          arr1.length == arr2.length)
      {
         for (int i = arr1.length; i-- > 0;)
            if (arr1[i] != arr2[i])
               return false;

         return true;
      }

      return false;
   }

   private boolean closureDone = false;

   /** This function computes the closure and also updates the kind so that
     * any time there is a move to this state, it can go on epsilon to a
     * new state in the epsilon moves that might have a lower kind of token
     * number for the same length.
   */

   private void EpsilonClosure()
   {
      int i = 0;

      if (closureDone || mark[id])
         return;

      mark[id] = true;

      // Recursively do closure
      for (i = 0; i < epsilonMoves.size(); i++)
         ((NfaState)epsilonMoves.elementAt(i)).EpsilonClosure();

      Enumeration e = epsilonMoves.elements();

      while (e.hasMoreElements())
      {
         NfaState tmp = (NfaState)e.nextElement();

         for (i = 0; i < tmp.epsilonMoves.size(); i++)
         {
            NfaState tmp1 = (NfaState)tmp.epsilonMoves.elementAt(i);
            if (tmp1.UsefulState() && !epsilonMoves.contains(tmp1))
            {
               InsertInOrder(epsilonMoves, tmp1);
               done = false;
            }
         }

         if (kind > tmp.kind)
            kind = tmp.kind;
      }

      if (HasTransitions() && !epsilonMoves.contains(this))
         InsertInOrder(epsilonMoves, this);
   }

   private boolean UsefulState()
   {
      return isFinal || HasTransitions();
   }

   public boolean HasTransitions()
   {
      return (asciiMoves[0] != 0L || asciiMoves[1] != 0L ||
              (charMoves != null && charMoves[0] != 0) ||
              (rangeMoves != null && rangeMoves[0] != 0));
   }

   void MergeMoves(NfaState other)
   {
      // Warning : This function does not merge epsilon moves
      if (asciiMoves == other.asciiMoves)
      {
         JavaCCErrors.semantic_error("Bug in JavaCC : Please send " +
                   "a report along with the input that caused this. Thank you.");
         throw new Error();
      }

      asciiMoves[0] = asciiMoves[0] | other.asciiMoves[0];
      asciiMoves[1] = asciiMoves[1] | other.asciiMoves[1];

      if (other.charMoves != null)
      {
         if (charMoves == null)
            charMoves = other.charMoves;
         else
         {
            char[] tmpCharMoves = new char[charMoves.length +
                                              other.charMoves.length];
            System.arraycopy(charMoves, 0, tmpCharMoves, 0, charMoves.length);
            charMoves = tmpCharMoves;

            for (int i = 0; i < other.charMoves.length; i++)
               AddChar(other.charMoves[i]);
         }
      }

      if (other.rangeMoves != null)
      {
         if (rangeMoves == null)
            rangeMoves = other.rangeMoves;
         else
         {
            char[] tmpRangeMoves = new char[rangeMoves.length +
                                                     other.rangeMoves.length];
            System.arraycopy(rangeMoves, 0, tmpRangeMoves,
                                                        0, rangeMoves.length);
            rangeMoves = tmpRangeMoves;
            for (int i = 0; i < other.rangeMoves.length; i += 2)
               AddRange(other.rangeMoves[i], other.rangeMoves[i + 1]);
         }
      }

      if (other.kind < kind)
         kind = other.kind;

      if (other.kindToPrint < kindToPrint)
         kindToPrint = other.kindToPrint;

      isFinal |= other.isFinal;
   }

   NfaState CreateEquivState(Vector states)
   {
      NfaState newState = ((NfaState)states.elementAt(0)).CreateClone();

      newState.next = new NfaState();

      InsertInOrder(newState.next.epsilonMoves,
                           ((NfaState)states.elementAt(0)).next);

      for (int i = 1; i < states.size(); i++)
      {
         NfaState tmp2 = ((NfaState)states.elementAt(i));

         if (tmp2.kind < newState.kind)
            newState.kind = tmp2.kind;

         newState.isFinal |= tmp2.isFinal;

         InsertInOrder(newState.next.epsilonMoves, tmp2.next);
      }

      return newState;
   }

   private NfaState GetEquivalentRunTimeState()
   {
      Outer :
      for (int i = allStates.size(); i-- > 0;)
      {
         NfaState other = (NfaState)allStates.elementAt(i);

         if (this != other && other.stateName != -1 &&
             kindToPrint == other.kindToPrint &&
             asciiMoves[0] == other.asciiMoves[0] &&
             asciiMoves[1] == other.asciiMoves[1] &&
             EqualCharArr(charMoves, other.charMoves) &&
             EqualCharArr(rangeMoves, other.rangeMoves))
         {
            if (next == other.next)
               return other;
            else if (next != null && other.next != null)
            {
               if (next.epsilonMoves.size() == other.next.epsilonMoves.size())
               {
                  for (int j = 0; j < next.epsilonMoves.size(); j++)
                     if (next.epsilonMoves.elementAt(j) !=
                           other.next.epsilonMoves.elementAt(j))
                        continue Outer;

                  return other;
               }