/*---------------------------------------------------------------------------
File:         			RegExptoFSAParser.java
Package:                        JFLAP Version 3.1
Author:			        Ted Hung
                                
Description of Contents:	Parses a Regular Expression step-by-step
				
--------------------------------------------------------------------------*/

/* 
 * Susan H. Rodger, Magda Procopiuc, Octavian Procopiuc, Eric Gramond, Ted Hung
 * Computer Science Department
 * Duke University
 * August 1999
 * Supported by National Science Foundation DUE-9596002, DUE-9555084,
 *  and DUE-9752583
 *
 * Copyright (c) 1999
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms are permitted
 * provided that the above copyright notice and this paragraph are
 * duplicated in all such forms and that any documentation,
 * advertising materials, and other materials related to such
 * distribution and use acknowledge that the software was developed
 * by the author.  The name of the author may not be used to
 * endorse or promote products derived from this software without
 * specific prior written permission.
 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
 * WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
 */

package flap;

import java.awt.*;
import java.awt.event.*;
import java.util.*;
import flap.operators.*;

//
//
// RegExptoFSAParser
//
//
public class RegExptoFSAParser
{
   /**
    * handles the conversion from infix to postfix
    */
   private Stack opstack;
   private Stack operandstack;
   private OperatorFactory opfactory;
   private String expstr;
   private Environment environ;

   /**
    * user interface controls
    */
   private int	     strpos;

   //tells whether the last value can be concatenated with
   // allows for the detection of concatenation that is
   // without operator: "ab", "a*b", etc
   private boolean canconcat = false;

   public RegExptoFSAParser(Environment env, String parsestr)
      throws Exception
   {
      expstr = parsestr;
      environ = env;
      opfactory = new OperatorFactory();
      opfactory.registerOperator(new OrOperator(env));
      opfactory.registerOperator(new KleeneStarOperator(env));
      opstack = new Stack();
      operandstack = new Stack();

      Operator temp;
      int prevOpIndex = -10;
      String str;
      for(int x = 0; x < parsestr.length(); ++x)
      {
         str = expstr.substring(x, x + 1);
         if(str.equals("!"))
            str = " ";
	 temp = opfactory.createOperator(str);
	 if(temp != null)
	 {
	    if(temp.numArguments() == 1)
	    {
	       if(x == 0 || x == prevOpIndex + 1)
		  throw new Exception("Invalid Regular Expression");
	    }
	    else if(temp.numArguments() == 2)
	    {
               str = expstr.substring(x + 1, x + 2);
               if(str.equals("!"))
                  str = " ";
	       if(x == 0 || x == parsestr.length() - 1 ||
		  x == prevOpIndex + 1 || 
		  opfactory.createOperator(str) != null)
		  throw new Exception("Invalid Regular Expression");
	       prevOpIndex = x;
	    }
	 }
      }

      //repeat and do a check on the regular expression
      strpos = 0;
      try
      {
	 while(stepNext(false) != null);
      }
      catch(EmptyStackException e)
      {
	 throw new Exception("Invalid Regular Expression");
      }

      canconcat = false;
      expstr = parsestr;
      opstack.removeAllElements();
      operandstack.removeAllElements();
      strpos = 0;
   }

   public String stepNext()
   {
      return stepNext(true);
   }

   /**
    * steps through the regular expression.  The argument
    * specifies whether to actually execute the instructions
    * or not.
    */
   public String stepNext(boolean exec)
   {
      //place operators onto the stack
      Operator temp;
      String ident;

      //tells whether an operation needs to be executed
      boolean execOp = false;

      while(strpos < expstr.length() && !execOp)
      {
	 ident = expstr.substring(strpos, strpos+1);
	 temp = opfactory.createOperator(ident);

	 if(temp != null)
	 {
	    if(!opstack.isEmpty() &&
	       temp.getPriority() < ((Operator) opstack.peek()).getPriority())
	    {
	       //pop off everything until the current node
	       //has a lower priority than the top node of the stack
	       execOp = true;
	    }
	    else
	    {
	       opstack.push(temp);
	       ++strpos;
	    }
	    canconcat = temp.canConcatenate();
	 }
	 else
	 {  
	    if(ident.equals(")"))
	    {
	       if(((Operator) opstack.peek()).getIdentifier().equals("("))
	       {
		  opstack.pop();
		  ++strpos;
		  canconcat = true;
	       }
	       else
	       {
		  execOp = true;
	       }
	    }
	    else if(canconcat && !ident.equals(" ")) //if two letters are concatenated
	    {
	       temp = new ConcatOperator(environ);
	       if(!opstack.isEmpty() &&
		  temp.getPriority() < ((Operator) opstack.peek()).getPriority())
	       {

		  //pop off everything until the current node
		  //has a lower priority than the top node of the stack
		  execOp = true;
	       }
	       else
	       {
		  opstack.push(temp);

		  //if it is a parenthesis, insert a placeholder
		  if(ident.equals("("))
		  {
		     temp = new BeginParenthesis();
		     opstack.push(temp);
		  }
		  else
		  {
                     if(ident.equals("!"))
                        ident = " ";
		     operandstack.push(new Expression(ident, null));
		  }

		  ++strpos;
		  canconcat = temp.canConcatenate();
	       }
	    }
	    else
	    {
	       //if it is a parenthesis, insert a placeholder
	       if(ident.equals("("))
	       {
		  opstack.push(new BeginParenthesis());
		  canconcat = false;
	       }
	       else if(!ident.equals(" "))
	       {
                  if(ident.equals("!"))
                     ident = " ";
		  operandstack.push(new Expression(ident, null));
		  canconcat = true;
	       }
	       ++strpos;
	    }
	 }
	 
      }
     
      //Placement of the actual state's and transitions is
      //handled by the operators.
      if(!opstack.isEmpty())
      {
	 temp = (Operator) opstack.pop();
	 if(exec)
	 {
	    return temp.execute(operandstack);
	 }
	 else
	 {
	    //take off one less than the number of arguments
	    //because the result must be pushed back onto the
	    //stack
	    for(int x = 0; x < temp.numArguments() - 1; ++x)
	    {
	       operandstack.pop();
	    }
	    return temp.getIdentifier();
	 }
      }
      else if(opstack.isEmpty() && strpos >= expstr.length())
      {
	 //done
	 return null;
      }
      //syntax error
      return null;
   }

   public boolean isDone()
   {
      if(opstack.isEmpty() || operandstack.isEmpty())
      {
	 //done
	 return true;
      }
      return false;
   }
}

