nfastate.java

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

            }
         }
      }

      return null;
   }

   // generates code (without outputting it) and returns the name used.
   void GenerateCode()
   {
      if (stateName != -1)
         return;

      if (next != null)
      {
         next.GenerateCode();
         if (next.kind != Integer.MAX_VALUE)
            kindToPrint = next.kind;
      }

      if (stateName == -1 && HasTransitions())
      {
         NfaState tmp = GetEquivalentRunTimeState();

         if (tmp != null)
         {
            stateName = tmp.stateName;
//????
            //tmp.inNextOf += inNextOf;
//????
            dummy = true;
            return;
         }

         stateName = generatedStates++;
         indexedAllStates.addElement(this);
         GenerateNextStatesCode();
      }
   }

   public static void ComputeClosures()
   {
      for (int i = allStates.size(); i-- > 0; )
      {
         NfaState tmp = (NfaState)allStates.elementAt(i);

         if (!tmp.closureDone)
            tmp.OptimizeEpsilonMoves(true);
      }

      for (int i = 0; i < allStates.size(); i++)
      {
         NfaState tmp = (NfaState)allStates.elementAt(i);

         if (!tmp.closureDone)
            tmp.OptimizeEpsilonMoves(false);
      }

      for (int i = 0; i < allStates.size(); i++)
      {
         NfaState tmp = (NfaState)allStates.elementAt(i);
         tmp.epsilonMoveArray = new NfaState[tmp.epsilonMoves.size()];
         tmp.epsilonMoves.copyInto(tmp.epsilonMoveArray);
      }
   }

   void OptimizeEpsilonMoves(boolean optReqd)
   {
      int i;

      // First do epsilon closure
      done = false;
      while (!done)
      {
         if (mark == null || mark.length < allStates.size())
            mark = new boolean[allStates.size()];

         for (i = allStates.size(); i-- > 0;)
            mark[i] = false;

         done = true;
         EpsilonClosure();
      }

      for (i = allStates.size(); i-- > 0;)
         ((NfaState)allStates.elementAt(i)).closureDone =
                                  mark[((NfaState)allStates.elementAt(i)).id];

      // Warning : The following piece of code is just an optimization.
      // in case of trouble, just remove this piece.

      boolean sometingOptimized = true;

      NfaState newState = null;
      NfaState tmp1, tmp2;
      int j;
      Vector equivStates = null;

      while (sometingOptimized)
      {
         sometingOptimized = false;
         for (i = 0; optReqd && i < epsilonMoves.size(); i++)
         {
            if ((tmp1 = (NfaState)epsilonMoves.elementAt(i)).HasTransitions())
            {
               for (j = i + 1; j < epsilonMoves.size(); j++)
               {
                  if ((tmp2 = (NfaState)epsilonMoves.elementAt(j)).
                                                           HasTransitions() &&
                      (tmp1.asciiMoves[0] == tmp2.asciiMoves[0] &&
                       tmp1.asciiMoves[1] == tmp2.asciiMoves[1] &&
                       EqualCharArr(tmp1.charMoves, tmp2.charMoves) &&
                       EqualCharArr(tmp1.rangeMoves, tmp2.rangeMoves)))
                  {
                     if (equivStates == null)
                     {
                        equivStates = new Vector();
                        equivStates.addElement(tmp1);
                     }

                     InsertInOrder(equivStates, tmp2);
                     epsilonMoves.removeElementAt(j--);
                  }
               }
            }

            if (equivStates != null)
            {
               sometingOptimized = true;
               String tmp = "";
               for (int l = 0; l < equivStates.size(); l++)
                  tmp += String.valueOf(
                            ((NfaState)equivStates.elementAt(l)).id) + ", ";

               if ((newState = (NfaState)equivStatesTable.get(tmp)) == null)
               {
                  newState = CreateEquivState(equivStates);
                  equivStatesTable.put(tmp, newState);
               }

               epsilonMoves.removeElementAt(i--);
               epsilonMoves.addElement(newState);
               equivStates = null;
               newState = null;
            }
         }

         for (i = 0; i < epsilonMoves.size(); i++)
         {
            //if ((tmp1 = (NfaState)epsilonMoves.elementAt(i)).next == null)
               //continue;
            tmp1 = (NfaState)epsilonMoves.elementAt(i);

            for (j = i + 1; j < epsilonMoves.size(); j++)
            {
               tmp2 = (NfaState)epsilonMoves.elementAt(j);

               if (tmp1.next == tmp2.next)
               {
                  if (newState == null)
                  {
                     newState = tmp1.CreateClone();
                     newState.next = tmp1.next;
                     sometingOptimized = true;
                  }

                  newState.MergeMoves(tmp2);
                  epsilonMoves.removeElementAt(j--);
               }
            }

            if (newState != null)
            {
               epsilonMoves.removeElementAt(i--);
               epsilonMoves.addElement(newState);
               newState = null;
            }
         }
      }

      // End Warning

      NfaState tempState;

      // Generate an array of states for epsilon moves (not vector)
      if (epsilonMoves.size() > 0)
      {
         for (i = 0; i < epsilonMoves.size(); i++)
            // Since we are doing a closure, just epsilon moves are unncessary
            if ((tempState = (NfaState)epsilonMoves.elementAt(i)).
                                                          HasTransitions())
               usefulEpsilonMoves++;
            else
               epsilonMoves.removeElementAt(i--);
      }
   }

   void GenerateNextStatesCode()
   {
      if (next.usefulEpsilonMoves > 0)
         next.GetEpsilonMovesString();
   }

   String GetEpsilonMovesString()
   {
      int[] stateNames = new int[usefulEpsilonMoves];
      int cnt = 0;

      if (epsilonMovesString != null)
         return epsilonMovesString;

      if (usefulEpsilonMoves > 0)
      {
         NfaState tempState;
         epsilonMovesString = "{ ";
         for (int i = 0; i < epsilonMoves.size(); i++)
         {
            if ((tempState = (NfaState)epsilonMoves.elementAt(i)).
                                                     HasTransitions())
            {
               if (tempState.stateName == -1)
                  tempState.GenerateCode();

               ((NfaState)indexedAllStates.elementAt(tempState.stateName)).inNextOf++;
               stateNames[cnt] = tempState.stateName;
               epsilonMovesString += tempState.stateName + ", ";
               if (cnt++ > 0 && cnt % 16 == 0)
                  epsilonMovesString += "\n";
            }
         }

         epsilonMovesString += "};";
      }

      usefulEpsilonMoves = cnt;
      if (epsilonMovesString != null &&
          allNextStates.get(epsilonMovesString) == null)
      {
         int[] statesToPut = new int[usefulEpsilonMoves];

         System.arraycopy(stateNames, 0, statesToPut, 0, cnt);
         allNextStates.put(epsilonMovesString, statesToPut);
      }

      return epsilonMovesString;
   }

   public static boolean CanStartNfaUsingAscii(char c)
   {
      if (c >= 128)
         throw new Error("JavaCC Bug: Please send mail to [e-mail]");

      String s = LexGen.initialState.GetEpsilonMovesString();

      if (s == null || s.equals("null;"))
         return false;

      int[] states = (int[])allNextStates.get(s);

      for (int i = 0; i < states.length; i++)
      {
         NfaState tmp = (NfaState)indexedAllStates.elementAt(states[i]);

         if ((tmp.asciiMoves[c / 64 ] & (1L << c % 64)) != 0L)
            return true;
      }

      return false;
   }

   final boolean CanMoveUsingChar(char c)
   {
      int i;

      if (onlyChar == 1)
         return c == matchSingleChar;

      if (c < 128)
         return ((asciiMoves[c / 64 ] & (1L << c % 64)) != 0L);

      // Just check directly if there is a move for this char
      if (charMoves != null && charMoves[0] != 0)
      {
         for (i = 0; i < charMoves.length; i++)
         {
            if (c == charMoves[i])
               return true;
            else if (c < charMoves[i] || charMoves[i] == 0)
               break;
         }
      }


      // For ranges, iterate thru the table to see if the current char
      // is in some range
      if (rangeMoves != null && rangeMoves[0] != 0)
         for (i = 0; i < rangeMoves.length; i += 2)
            if (c >= rangeMoves[i] && c <= rangeMoves[i + 1])
               return true;
            else if (c < rangeMoves[i] || rangeMoves[i] == 0)
               break;

      //return (nextForNegatedList != null);
      return false;
   }

   public int getFirstValidPos(String s, int i, int len)
   {
      if (onlyChar == 1)
      {
         char c = matchSingleChar;
         while (c != s.charAt(i) && ++i < len);
         return i;
      }

      do
      {
         if (CanMoveUsingChar(s.charAt(i)))
            return i;
      } while (++i < len);

      return i;
   }

   public int MoveFrom(char c, Vector newStates)
   {
      if (CanMoveUsingChar(c))
      {
         for (int i = next.epsilonMoves.size(); i-- > 0;)
            InsertInOrder(newStates, (NfaState)next.epsilonMoves.elementAt(i));

         return kindToPrint;
      }

      return Integer.MAX_VALUE;
   }

   public static int MoveFromSet(char c, Vector states, Vector newStates)
   {
      int tmp;
      int retVal = Integer.MAX_VALUE;

      for (int i = states.size(); i-- > 0;)
         if (retVal >
             (tmp = ((NfaState)states.elementAt(i)).MoveFrom(c, newStates)))
            retVal = tmp;

      return retVal;
   }

   public static int moveFromSetForRegEx(char c, NfaState[] states, NfaState[] newStates, int round)
   {
      int start = 0;
      int sz = states.length;

      for (int i = 0; i < sz; i++)
      {
         NfaState tmp1, tmp2;

         if ((tmp1 = states[i]) == null)
            break;

         if (tmp1.CanMoveUsingChar(c))
         {
            if (tmp1.kindToPrint != Integer.MAX_VALUE)
            {
               newStates[start] = null;
               return 1;
            }

            NfaState[] v = tmp1.next.epsilonMoveArray;
            for (int j = v.length; j-- > 0;)
            {
               if ((tmp2 = v[j]).round != round)
               {
                  tmp2.round = round;
                  newStates[start++] = tmp2;
               }
            }
         }
      }

      newStates[start] = null;
      return Integer.MAX_VALUE;
   }

   static Vector allBitVectors = new Vector();

   /* This function generates the bit vectors of low and hi bytes for common
      bit vectors and retunrs those that are not common with anything (in
      loBytes) and returns an array of indices that can be used to generate
      the function names for char matching using the common bit vectors.
      It also generates code to match a char with the common bit vectors.
      (Need a better comment). */

   static int[] tmpIndices = new int[512]; // 2 * 256
   void GenerateNonAsciiMoves(java.io.PrintWriter ostr)
   {
      int i = 0, j = 0;
      char hiByte;
      int cnt = 0;
      long[][] loBytes = new long[256][4];

      if ((charMoves == null || charMoves[0] == 0) &&
          (rangeMoves == null || rangeMoves[0] == 0))
         return;

      if (charMoves != null)
      {
         for (i = 0; i < charMoves.length; i++)
         {
            if (charMoves[i] == 0)
               break;

            hiByte = (char)(charMoves[i] >> 8);
            loBytes[hiByte][(charMoves[i] & 0xff) / 64] |=
                              (1L << ((charMoves[i] & 0xff) % 64));
         }
      }

      if (rangeMoves != null)
      {
         for (i = 0; i < rangeMoves.length; i += 2)
         {
            if (rangeMoves[i] == 0)
               break;

            char c, r;

            r = (char)(rangeMoves[i + 1] & 0xff);
            hiByte = (char)(rangeMoves[i] >> 8);

            if (hiByte == (char)(rangeMoves[i + 1] >> 8))
            {
               for (c = (char)(rangeMoves[i] & 0xff); c <= r; c++)
                  loBytes[hiByte][c / 64] |= (1L << (c % 64));

               continue;
            }

            for (c = (char)(rangeMoves[i] & 0xff); c <= 0xff; c++)
               loBytes[hiByte][c / 64] |= (1L << (c % 64));

            while (++hiByte < (char)(rangeMoves[i + 1] >> 8))
            {
               loBytes[hiByte][0] |= 0xffffffffffffffffL;
               loBytes[hiByte][1] |= 0xffffffffffffffffL;
               loBytes[hiByte][2] |= 0xffffffffffffffffL;
               loBytes[hiByte][3] |= 0xffffffffffffffffL;
            }