Logo Search packages:      
Sourcecode: ragel version File versions

parsetree.cpp

/*
 *  Copyright 2001-2004 Adrian Thurston <adriant@ragel.ca>
 */

/*  This file is part of Ragel.
 *
 *  Ragel is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 2 of the License, or
 *  (at your option) any later version.
 * 
 *  Ragel 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 Ragel; if not, write to the Free Software
 *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA 
 */

#include <iostream>
#include <iomanip>
#include <errno.h>
#include <limits.h>
#include <stdlib.h>

/* Parsing. */
#include "ragel.h"
#include "ptreetypes.h"
#include "rlparse.h"
#include "parsedata.h"
#include "parsetree.h"

/* Machine building. */
#include "redfsm.h"

/* Code generators. */
#include "tabcodegen.h"
#include "ftabcodegen.h"
#include "gotocodegen.h"
#include "fgotocodegen.h"
#include "ipgotocodegen.h"

/* Dumping the fsm. */
#include "fsmdump.h"
#include "gvdotgen.h"

using namespace std;
ostream &operator<<( ostream &out, const NameRef &nameRef );
ostream &operator<<( ostream &out, const NameInst &nameInst );

FsmAp *VarDef::walk( ParseData *pd )
{
      /* We enter into a new name scope. */
      NameFrame nameFrame = pd->enterNameScope( true, 1 );

      /* Recurse on the expression. */
      FsmAp *rtnVal = join->walk( pd );
      
      /* Do the tranfer of local error actions. */
      LocalErrDictEl *localErrDictEl = pd->localErrDict.find( name );
      if ( localErrDictEl != 0 ) {
            for ( StateList::Iter state = rtnVal->stateList; state.lte(); state++ )
                  rtnVal->transferErrorActions( state, localErrDictEl->value );
      }

      /* If the expression below is a join operation then it just had epsilon
       * transisions resolved. Otherwise run the epsilon op now. */
      if ( join->exprList.length() == 1 )
            rtnVal->epsilonOp();

      /* We can now unset entry points that are not longer used. */
      pd->unsetObsoleteEntries( rtnVal );

      /* If the name of the variable is referenced then add the entry point to
       * the graph. */
      if ( pd->curNameInst->numRefs > 0 )
            rtnVal->setEntry( pd->curNameInst->id, rtnVal->startState );
      
      /* Pop the name scope. */
      pd->popNameScope( nameFrame );
      return rtnVal;
}

void VarDef::makeNameTree( const InputLoc &loc, ParseData *pd )
{
      /* The variable definition enters a new scope. */
      NameInst *prevNameInst = pd->curNameInst;
      pd->curNameInst = pd->addNameInst( loc, name, false );

      /* Recurse. */
      join->makeNameTree( pd );
      
      /* The name scope ends, pop the name instantiation. */
      pd->curNameInst = prevNameInst;
}

void VarDef::resolveNameRefs( ParseData *pd )
{
      /* Entering into a new scope. */
      NameFrame nameFrame = pd->enterNameScope( true, 1 );

      /* Recurse. */
      join->resolveNameRefs( pd );
      
      /* The name scope ends, pop the name instantiation. */
      pd->popNameScope( nameFrame );
}

/* Construct with a location and the first expression. */
Join::Join( const InputLoc &loc, Expression *expr )
:
      loc(loc)
{
      exprList.append( expr );
}

/* Construct with a location and the first expression. */
Join::Join( Expression *expr )
:
      loc(loc)
{
      exprList.append( expr );
}

/* Walk an expression node. */
FsmAp *Join::walk( ParseData *pd )
{
      if ( exprList.length() > 1 )
            return walkJoin( pd );
      else
            return exprList.head->walk( pd );
}

/* There is a list of expressions to join. */
FsmAp *Join::walkJoin( ParseData *pd )
{
      /* We enter into a new name scope. */
      NameFrame nameFrame = pd->enterNameScope( true, 1 );

      /* Evaluate the machines. */
      FsmAp **fsms = new FsmAp*[exprList.length()];
      ExprList::Iter expr = exprList;
      for ( int e = 0; e < exprList.length(); e++, expr++ )
            fsms[e] = expr->walk( pd );
      
      /* Get the start and final names. Final is 
       * guaranteed to exist, start is not. */
      NameInst *startName = pd->curNameInst->start;
      NameInst *finalName = pd->curNameInst->final;

      int startId = -1;
      if ( startName != 0 ) {
            /* Take note that there was an implicit link to the start machine. */
            pd->localNameScope->referencedNames.append( startName );
            startId = startName->id;
      }

      /* A final id of -1 indicates there is no epsilon that references the
       * final state, therefor do not create one or set an entry point to it. */
      int finalId = -1;
      if ( finalName->numRefs > 0 )
            finalId = finalName->id;

      /* Join machines 1 and up onto machine 0. */
      FsmAp *retFsm = fsms[0];
      retFsm->joinOp( startId, finalId, fsms+1, exprList.length()-1 );

      /* We can now unset entry points that are not longer used. */
      pd->unsetObsoleteEntries( retFsm );

      /* Pop the name scope. */
      pd->popNameScope( nameFrame );

      delete[] fsms;
      return retFsm;
}

void Join::makeNameTree( ParseData *pd )
{
      if ( exprList.length() > 1 ) {
            /* Create the new anonymous scope. */
            NameInst *prevNameInst = pd->curNameInst;
            pd->curNameInst = pd->addNameInst( loc, 0, false );

            /* Join scopes need an implicit "final" target. */
            pd->curNameInst->final = new NameInst( InputLoc(), pd->curNameInst, "final", 
                        pd->nextNameId++, false );

            /* Recurse into all expressions in the list. */
            for ( ExprList::Iter expr = exprList; expr.lte(); expr++ )
                  expr->makeNameTree( pd );

            /* The name scope ends, pop the name instantiation. */
            pd->curNameInst = prevNameInst;
      }
      else {
            /* Recurse into the single expression. */
            exprList.head->makeNameTree( pd );
      }
}


void Join::resolveNameRefs( ParseData *pd )
{
      /* Branch on whether or not there is to be a join. */
      if ( exprList.length() > 1 ) {
            /* The variable definition enters a new scope. */
            NameFrame nameFrame = pd->enterNameScope( true, 1 );

            /* The join scope must contain a start label. */
            NameSet resolved = pd->resolvePart( pd->localNameScope, "start", true );
            if ( resolved.length() > 0 ) {
                  /* Take the first. */
                  pd->curNameInst->start = resolved[0];
                  if ( resolved.length() > 1 ) {
                        /* Complain about the multiple references. */
                        error(loc) << "multiple start labels" << endl;
                        errorStateLabels( resolved );
                  }
            }

            /* Make sure there is a start label. */
            if ( pd->curNameInst->start != 0 ) {
                  /* There is an implicit reference to start name. */
                  pd->curNameInst->start->numRefs += 1;
            }
            else {
                  /* No start label. Complain and recover by adding a label to the
                   * adding one. Recover ignoring the problem. */
                  error(loc) << "no start label" << endl;
            }

            /* Recurse into all expressions in the list. */
            for ( ExprList::Iter expr = exprList; expr.lte(); expr++ )
                  expr->resolveNameRefs( pd );

            /* The name scope ends, pop the name instantiation. */
            pd->popNameScope( nameFrame );
      }
      else {
            /* Recurse into the single expression. */
            exprList.head->resolveNameRefs( pd );
      }
}

/* Clean up after an expression node. */
Expression::~Expression()
{
      switch ( type ) {
            case OrType: case IntersectType: case SubtractType:
                  delete expression;
                  delete term;
                  break;
            case TermType:
                  delete term;
                  break;
            case BuiltinType:
                  break;
      }
}

/* Evaluate a single expression node. */
FsmAp *Expression::walk( ParseData *pd )
{
      FsmAp *rtnVal = 0;
      switch ( type ) {
            case OrType: {
                  /* Evaluate the expression. */
                  rtnVal = expression->walk( pd );
                  /* Evaluate the term. */
                  FsmAp *rhs = term->walk( pd );
                  /* Perform union. */
                  rtnVal->unionOp( rhs );
                  afterOpMinimize( rtnVal );
                  break;
            }
            case IntersectType: {
                  /* Evaluate the expression. */
                  rtnVal = expression->walk( pd );
                  /* Evaluate the term. */
                  FsmAp *rhs = term->walk( pd );
                  /* Perform intersection. */
                  rtnVal->intersectOp( rhs );
                  afterOpMinimize( rtnVal );
                  break;
            }
            case SubtractType: {
                  /* Evaluate the expression. */
                  rtnVal = expression->walk( pd );
                  /* Evaluate the term. */
                  FsmAp *rhs = term->walk( pd );
                  /* Perform subtraction. */
                  rtnVal->subtractOp( rhs );
                  afterOpMinimize( rtnVal );
                  break;
            }
            case TermType: {
                  /* Return result of the term. */
                  rtnVal = term->walk( pd );
                  break;
            }
            case BuiltinType: {
                  /* Duplicate the builtin. */
                  rtnVal = makeBuiltin( builtin, pd );
                  break;
            }
      }

      return rtnVal;
}

void Expression::makeNameTree( ParseData *pd )
{
      switch ( type ) {
      case OrType:
      case IntersectType:
      case SubtractType:
            expression->makeNameTree( pd );
            term->makeNameTree( pd );
            break;
      case TermType:
            term->makeNameTree( pd );
            break;
      case BuiltinType:
            break;
      }
}

void Expression::resolveNameRefs( ParseData *pd )
{
      switch ( type ) {
      case OrType:
      case IntersectType:
      case SubtractType:
            expression->resolveNameRefs( pd );
            term->resolveNameRefs( pd );
            break;
      case TermType:
            term->resolveNameRefs( pd );
            break;
      case BuiltinType:
            break;
      }
}

/* Clean up after a term node. */
Term::~Term()
{
      switch ( type ) {
            case ConcatType:
                  delete term;
                  delete factorWithAug;
                  break;
            case FactorWithAugType:
                  delete factorWithAug;
                  break;
      }
}

/* Evaluate a term node. */
FsmAp *Term::walk( ParseData *pd )
{
      FsmAp *rtnVal = 0;
      switch ( type ) {
            case ConcatType: {
                  /* Evaluate the Term. */
                  rtnVal = term->walk( pd );
                  /* Evaluate the FactorWithRep. */
                  FsmAp *rhs = factorWithAug->walk( pd );
                  /* Perform concatenation. */
                  rtnVal->concatOp( rhs );
                  afterOpMinimize( rtnVal );
                  break;
            }
            case FactorWithAugType: {
                  rtnVal = factorWithAug->walk( pd );
                  break;
            }
      }
      return rtnVal;
}

void Term::makeNameTree( ParseData *pd )
{
      switch ( type ) {
      case ConcatType:
            term->makeNameTree( pd );
            factorWithAug->makeNameTree( pd );
            break;
      case FactorWithAugType:
            factorWithAug->makeNameTree( pd );
            break;
      }
}

void Term::resolveNameRefs( ParseData *pd )
{
      switch ( type ) {
      case ConcatType:
            term->resolveNameRefs( pd );
            factorWithAug->resolveNameRefs( pd );
            break;
      case FactorWithAugType:
            factorWithAug->resolveNameRefs( pd );
            break;
      }
}

/* Clean up after a factor with augmentation node. */
FactorWithAug::~FactorWithAug()
{
      delete factorWithRep;

      /* Walk the vector of parser actions, deleting function names. */

      /* Clean up priority descriptors. */
      if ( priorDescs != 0 )
            delete[] priorDescs;
}

void FactorWithAug::assignActions( ParseData *pd, FsmAp *graph, int *actionOrd )
{
      /* Assign actions. */
      for ( int i = 0; i < actions.length(); i++ )  {
            switch ( actions[i].type ) {
            case at_start:
                  graph->startFsmAction( actionOrd[i], actions[i].action->actionId );
                  afterOpMinimize( graph );
                  break;
            case at_all:
                  graph->allTransAction( actionOrd[i], actions[i].action->actionId );
                  break;
            case at_finish:
                  graph->finishFsmAction( actionOrd[i], actions[i].action->actionId );
                  break;
            case at_leave:
                  graph->leaveFsmAction( actionOrd[i], actions[i].action->actionId );
                  break;

            case at_start_gbl_error:
                  graph->startErrorAction( actionOrd[i], actions[i].action->actionId, 0 );
                  afterOpMinimize( graph );
                  break;
            case at_all_gbl_error:
                  graph->allErrorAction( actionOrd[i], actions[i].action->actionId, 0 );
                  break;
            case at_finish_gbl_error:
                  graph->finishErrorAction( actionOrd[i], actions[i].action->actionId, 0 );
                  break;
            case at_leave_gbl_error:
                  graph->leaveErrorAction( actionOrd[i], actions[i].action->actionId, 0 );
                  break;
            case at_start_finish_gbl_error:
                  graph->startErrorAction( actionOrd[i], actions[i].action->actionId, 0 );
                  graph->finishErrorAction( actionOrd[i], actions[i].action->actionId, 0 );
                  afterOpMinimize( graph );
                  break;
            case at_finish_leave_gbl_error:
                  graph->finishErrorAction( actionOrd[i], actions[i].action->actionId, 0 );
                  graph->leaveErrorAction( actionOrd[i], actions[i].action->actionId, 0 );
                  break;

            case at_start_local_error:
                  graph->startErrorAction( actionOrd[i], actions[i].action->actionId,
                              actions[i].localErrKey );
                  afterOpMinimize( graph );
                  break;
            case at_all_local_error:
                  graph->allErrorAction( actionOrd[i], actions[i].action->actionId,
                              actions[i].localErrKey );
                  break;
            case at_finish_local_error:
                  graph->finishErrorAction( actionOrd[i], actions[i].action->actionId,
                              actions[i].localErrKey );
                  break;
            case at_leave_local_error:
                  graph->leaveErrorAction( actionOrd[i], actions[i].action->actionId,
                              actions[i].localErrKey );
                  break;
            case at_start_finish_local_error:
                  graph->startErrorAction( actionOrd[i], actions[i].action->actionId,
                              actions[i].localErrKey );
                  graph->finishErrorAction( actionOrd[i], actions[i].action->actionId,
                              actions[i].localErrKey );
                  afterOpMinimize( graph );
                  break;
            case at_finish_leave_local_error:
                  graph->finishErrorAction( actionOrd[i], actions[i].action->actionId,
                              actions[i].localErrKey );
                  graph->leaveErrorAction( actionOrd[i], actions[i].action->actionId,
                              actions[i].localErrKey );
                  break;

            default:
                  /* Parser Prevents this case. */
                  break;
            }
      }
}

void FactorWithAug::assignPriorities( FsmAp *graph, int *priorOrd )
{
      /* Assign priorities. */
      for ( int i = 0; i < priorityAugs.length(); i++ ) {
            switch ( priorityAugs[i].type ) {
            case at_start:
                  graph->startFsmPrior( priorOrd[i], &priorDescs[i]);
                  /* Start fsm priorities are a special case that may require
                   * minimization afterwards. */
                  afterOpMinimize( graph );
                  break;
            case at_all:
                  graph->allTransPrior( priorOrd[i], &priorDescs[i] );
                  break;
            case at_finish:
                  graph->finishFsmPrior( priorOrd[i], &priorDescs[i] );
                  break;
            case at_leave:
                  graph->leaveFsmPrior( priorOrd[i], &priorDescs[i] );
                  break;

            default:
                  /* Parser Prevents this case. */
                  break;
            }
      }
}

/* Assign context. */
void FactorWithAug::assignContext( FsmAp *graph )
{
      for ( int i = 0; i < contexts.length(); i++ ) {
            switch ( contexts[i].type ) {
            case at_start_context:
                  graph->startContext( contexts[i].contextId );
                  break;
            case at_all_context:
                  graph->allContext( contexts[i].contextId );
                  break;
            case at_finish_context:
                  graph->finishContext( contexts[i].contextId );
                  break;
            case at_leave_context:
                  graph->leaveContext( contexts[i].contextId );
                  break;
            case at_start_finish_context:
                  graph->startContext( contexts[i].contextId );
                  graph->finishContext( contexts[i].contextId );
                  break;
            case at_finish_leave_context:
                  graph->finishContext( contexts[i].contextId );
                  graph->leaveContext( contexts[i].contextId );
                  break;

            default:
                  /* Parser Prevents this case. */
                  break;
            }
      }
}

/* Evaluate a factor with augmentation node. */
FsmAp *FactorWithAug::walk( ParseData *pd )
{
      /* Enter into the scopes created for the labels. */
      NameFrame nameFrame = pd->enterNameScope( false, labels.length() );

      /* Make the array of function orderings. */
      int *actionOrd = 0;
      if ( actions.length() > 0 )
            actionOrd = new int[actions.length()];
      
      /* First walk the list of functions, assigning the
       * starting function ordering. */
      for ( int i = 0; i < actions.length(); i++ ) {
            if ( actions[i].type == at_start || 
                        actions[i].type == at_start_gbl_error ||
                        actions[i].type == at_start_local_error )
                  actionOrd[i] = pd->curActionOrd++;
      }

      /* Evaluate the factor with repetition. */
      FsmAp *rtnVal = factorWithRep->walk( pd );

      /* Compute the remaining function call orderings. */
      for ( int i = 0; i < actions.length(); i++ ) {
            if ( actions[i].type != at_start && 
                        actions[i].type != at_start_gbl_error &&
                        actions[i].type != at_start_local_error )
                  actionOrd[i] = pd->curActionOrd++;
      }

      assignActions( pd, rtnVal , actionOrd );

      /* Make the array of priority orderings. Orderings are local to this walk
       * of the factor with augmentation. */
      int *priorOrd = 0;
      if ( priorityAugs.length() > 0 )
            priorOrd = new int[priorityAugs.length()];
      
      /* Walk all priorities, assigning the priority ordering. */
      for ( int i = 0; i < priorityAugs.length(); i++ )
            priorOrd[i] = pd->curPriorOrd++;

      /* If the priority descriptors have not been made, make them now.  Make
       * priority descriptors for each priority asignment that will be passed to
       * the fsm. Used to keep track of the key, value and used bit. */
      if ( priorDescs == 0 && priorityAugs.length() > 0 ) {
            priorDescs = new PriorDesc[priorityAugs.length()];
            for ( int i = 0; i < priorityAugs.length(); i++ ) {
                  /* Init the prior descriptor for the priority setting. */
                  priorDescs[i].key = priorityAugs[i].priorKey;
                  priorDescs[i].priority = priorityAugs[i].priorValue;
                  priorDescs[i].used = false;
            }
      }

      /* Assign priorities into the machine. */
      assignPriorities( rtnVal, priorOrd );

      /* Assign epsilon transitions. */
      for ( int e = 0; e < epsilonLinks.length(); e++ ) {
            /* Get the name, which may not exist. If it doesn't then silently
             * ignore it because an error has already been reported. */
            NameInst *epTarg = epsilonLinks[e].resolvedName;
            if ( epTarg != 0 ) {
                  /* Make the epsilon transitions. */
                  rtnVal->epsilonTrans( epTarg->id );

                  /* Note that we have made a link to the name. */
                  pd->localNameScope->referencedNames.append( epTarg );
            }
      }

      /* Assign context. */
      assignContext( rtnVal );

      if ( labels.length() > 0 ) {
            /* Pop the names. */
            pd->resetNameScope( nameFrame );

            /* Make labels that are referenced into entry points. */
            for ( int i = 0; i < labels.length(); i++ ) {
                  pd->enterNameScope( false, 1 );

                  /* Will always be found. */
                  NameInst *name = pd->curNameInst;

                  /* If the name is referenced then set the entry point. */
                  if ( name->numRefs > 0 )
                        rtnVal->setEntry( name->id, rtnVal->startState );
            }

            pd->popNameScope( nameFrame );
      }

      if ( priorOrd != 0 )
            delete[] priorOrd;
      if ( actionOrd != 0 )
            delete[] actionOrd;     
      return rtnVal;
}

void FactorWithAug::makeNameTree( ParseData *pd )
{
      /* Add the labels to the tree of instantiated names. Each label
       * makes a new scope. */
      NameInst *prevNameInst = pd->curNameInst;
      for ( int i = 0; i < labels.length(); i++ )
            pd->curNameInst = pd->addNameInst( labels[i].loc, labels[i].data, true );

      /* Recurse, then pop the names. */
      factorWithRep->makeNameTree( pd );
      pd->curNameInst = prevNameInst;
}


void FactorWithAug::resolveNameRefs( ParseData *pd )
{
      /* Enter into the name scope created by any labels. */
      NameFrame nameFrame = pd->enterNameScope( false, labels.length() );

      /* Note action references. */
      for ( int i = 0; i < actions.length(); i++ ) 
            actions[i].action->actionRefs.append( pd->localNameScope );

      /* Resolve epsilon transitions. */
      for ( int ep = 0; ep < epsilonLinks.length(); ep++ ) {
            /* Get the link. */
            EpsilonLink &link = epsilonLinks[ep];

            if ( link.target.length() == 1 && strcmp( link.target.data[0], "final" ) == 0 ) {
                  /* Epsilon drawn to an implicit final state. An implicit final is
                   * only available in join operations. */
                  link.resolvedName = pd->localNameScope->final;
            }
            else {
                  /* Do an search for the name. */
                  NameSet resolved;
                  pd->resolveFrom( resolved, pd->localNameScope, link.target, 0 );
                  if ( resolved.length() > 0 ) {
                        /* Take the first one. */
                        link.resolvedName = resolved[0];
                        if ( resolved.length() > 1 ) {
                              /* Complain about the multiple references. */
                              error(link.loc) << "state reference " << link.target << 
                                          " resolves to multiple entry points" << endl;
                              errorStateLabels( resolved );
                        }
                  }
            }

            if ( link.resolvedName != 0 ) {
                  /* Found the name, bump of the reference count on it. */
                  link.resolvedName->numRefs += 1;
            }
            else {
                  /* Complain, no recovery action, the epsilon op will ignore any
                   * epsilon transitions whose names did not resolve. */
                  error(link.loc) << "could not resolve label " << link.target << endl;
            }
      }

      /* Recurse, then pop the names. */
      factorWithRep->resolveNameRefs( pd );
      if ( labels.length() > 0 )
            pd->popNameScope( nameFrame );
}


/* Clean up after a factor with repetition node. */
FactorWithRep::~FactorWithRep()
{
      switch ( type ) {
            case StarType: case StarStarType: case OptionalType: case PlusType:
            case ExactType: case MaxType: case MinType: case RangeType:
                  delete factorWithRep;
                  break;
            case FactorWithNegType:
                  delete factorWithNeg;
                  break;
      }
}

/* Evaluate a factor with repetition node. */
FsmAp *FactorWithRep::walk( ParseData *pd )
{
      FsmAp *retFsm = 0;

      switch ( type ) {
      case StarType: {
            /* Evaluate the FactorWithRep. */
            retFsm = factorWithRep->walk( pd );
            if ( retFsm->startState->isFinState() ) {
                  warning(loc) << "applying kleene star to a machine that "
                              "accepts zero length word" << endl;
            }

            /* Shift over the start action orders then do the kleene star. */
            pd->curActionOrd += retFsm->shiftStartActionOrder( pd->curActionOrd );
            retFsm->starOp( );
            afterOpMinimize( retFsm );
            break;
      }
      case StarStarType: {
            /* Evaluate the FactorWithRep. */
            retFsm = factorWithRep->walk( pd );
            if ( retFsm->startState->isFinState() ) {
                  warning(loc) << "applying kleene star to a machine that "
                              "accepts zero length word" << endl;
            }

            /* Set up the prior descs. All gets priority one, whereas leaving gets
             * priority zero. Make a unique key so that these priorities don't
             * interfere with any priorities set by the user. */
            priorDescs[0].key = pd->nextPriorKey++;
            priorDescs[0].priority = 1;
            priorDescs[0].used = false;

            /* Leaveing gets priority 0. Use same unique key. */
            priorDescs[1].key = priorDescs[0].key;
            priorDescs[1].priority = 0;
            priorDescs[1].used = false;

            retFsm->allTransPrior( pd->curPriorOrd++, &priorDescs[0] );
            retFsm->leaveFsmPrior( pd->curPriorOrd++, &priorDescs[1] );

            /* Shift over the start action orders then do the kleene star. */
            pd->curActionOrd += retFsm->shiftStartActionOrder( pd->curActionOrd );
            retFsm->starOp( );
            afterOpMinimize( retFsm );
            break;
      }
      case OptionalType: {
            /* Make the null fsm. */
            FsmAp *nu = new FsmAp( &pd->keyOps );
            nu->nullFsm( );

            /* Evaluate the FactorWithRep. */
            retFsm = factorWithRep->walk( pd );

            /* Perform the question operator. */
            retFsm->unionOp( nu );
            afterOpMinimize( retFsm );
            break;
      }
      case PlusType: {
            /* Evaluate the FactorWithRep. */
            retFsm = factorWithRep->walk( pd );
            if ( retFsm->startState->isFinState() ) {
                  warning(loc) << "applying plus operator to a machine that "
                              "accpets zero length word" << endl;
            }

            /* Need a duplicated for the star end. */
            FsmAp *dup = new FsmAp( *retFsm );

            /* The start func orders need to be shifted before doing the star. */
            pd->curActionOrd += dup->shiftStartActionOrder( pd->curActionOrd );

            /* Star the duplicate. */
            dup->starOp( );
            afterOpMinimize( dup );

            retFsm->concatOp( dup );
            afterOpMinimize( retFsm );
            break;
      }
      case ExactType: {
            /* Get an int from the repetition amount. */
            if ( lowerRep == 0 ) {
                  /* No copies. Don't need to evaluate the factorWithRep. 
                   * This Defeats the purpose so give a warning. */
                  warning(loc) << "exactly zero repetitions results "
                              "in the null machine" << endl;

                  retFsm = new FsmAp( &pd->keyOps );
                  retFsm->nullFsm();
            }
            else {
                  /* Evaluate the first FactorWithRep. */
                  retFsm = factorWithRep->walk( pd );
                  if ( retFsm->startState->isFinState() ) {
                        warning(loc) << "applying repetition to a machine that "
                                    "accepts zero length word" << endl;
                  }

                  /* The start func orders need to be shifted before doing the
                   * repetition. */
                  pd->curActionOrd += retFsm->shiftStartActionOrder( pd->curActionOrd );

                  /* Do the repetition on the machine. Already guarded against n == 0 */
                  retFsm->repeatOp( lowerRep );
                  afterOpMinimize( retFsm );
            }
            break;
      }
      case MaxType: {
            /* Get an int from the repetition amount. */
            if ( upperRep == 0 ) {
                  /* No copies. Don't need to evaluate the factorWithRep. 
                   * This Defeats the purpose so give a warning. */
                  warning(loc) << "max zero repetitions results "
                              "in the null machine" << endl;

                  retFsm = new FsmAp( &pd->keyOps );
                  retFsm->nullFsm();
            }
            else {
                  /* Evaluate the first FactorWithRep. */
                  retFsm = factorWithRep->walk( pd );
                  if ( retFsm->startState->isFinState() ) {
                        warning(loc) << "applying max repetition to a machine that "
                                    "accepts zero length word" << endl;
                  }

                  /* The start func orders need to be shifted before doing the 
                   * repetition. */
                  pd->curActionOrd += retFsm->shiftStartActionOrder( pd->curActionOrd );

                  /* Do the repetition on the machine. Already guarded against n == 0 */
                  retFsm->optionalRepeatOp( upperRep );
                  afterOpMinimize( retFsm );
            }
            break;
      }
      case MinType: {
            /* Evaluate the repeated machine. */
            retFsm = factorWithRep->walk( pd );
            if ( retFsm->startState->isFinState() ) {
                  warning(loc) << "applying min repetition to a machine that "
                              "accepts zero length word" << endl;
            }

            /* The start func orders need to be shifted before doing the repetition
             * and the kleene star. */
            pd->curActionOrd += retFsm->shiftStartActionOrder( pd->curActionOrd );
      
            if ( lowerRep == 0 ) {
                  /* Acts just like a star op on the machine to return. */
                  retFsm->starOp( );
                  afterOpMinimize( retFsm );
            }
            else {
                  /* Take a duplicate for the plus. */
                  FsmAp *dup = new FsmAp( *retFsm );

                  /* Do repetition on the first half. */
                  retFsm->repeatOp( lowerRep );
                  afterOpMinimize( retFsm );

                  /* Star the duplicate. */
                  dup->starOp( );
                  afterOpMinimize( dup );

                  /* Tak on the kleene star. */
                  retFsm->concatOp( dup );
                  afterOpMinimize( retFsm );
            }
            break;
      }
      case RangeType: {
            /* Check for bogus range. */
            if ( upperRep - lowerRep < 0 ) {
                  error(loc) << "invalid range repetition" << endl;

                  /* Return null machine as recovery. */
                  retFsm = new FsmAp( &pd->keyOps );
                  retFsm->nullFsm();
            }
            else if ( lowerRep == 0 && upperRep == 0 ) {
                  /* No copies. Don't need to evaluate the factorWithRep.  This
                   * defeats the purpose so give a warning. */
                  warning(loc) << "zero to zero repetitions results "
                              "in the null machine" << endl;

                  retFsm = new FsmAp( &pd->keyOps );
                  retFsm->nullFsm();
            }
            else {
                  /* Now need to evaluate the repeated machine. */
                  retFsm = factorWithRep->walk( pd );
                  if ( retFsm->startState->isFinState() ) {
                        warning(loc) << "applying range repetition to a machine that "
                                    "accepts zero length word" << endl;
                  }

                  /* The start func orders need to be shifted before doing both kinds
                   * of repetition. */
                  pd->curActionOrd += retFsm->shiftStartActionOrder( pd->curActionOrd );

                  if ( lowerRep == 0 ) {
                        /* Just doing max repetition. Already guarded against n == 0. */
                        retFsm->optionalRepeatOp( upperRep );
                        afterOpMinimize( retFsm );
                  }
                  else if ( lowerRep == upperRep ) {
                        /* Just doing exact repetition. Already guarded against n == 0. */
                        retFsm->repeatOp( lowerRep );
                        afterOpMinimize( retFsm );
                  }
                  else {
                        /* This is the case that 0 < lowerRep < upperRep. Take a
                         * duplicate for the optional repeat. */
                        FsmAp *dup = new FsmAp( *retFsm );

                        /* Do repetition on the first half. */
                        retFsm->repeatOp( lowerRep );
                        afterOpMinimize( retFsm );

                        /* Do optional repetition on the second half. */
                        dup->optionalRepeatOp( upperRep - lowerRep );
                        afterOpMinimize( dup );

                        /* Tak on the duplicate machine. */
                        retFsm->concatOp( dup );
                        afterOpMinimize( retFsm );
                  }
            }
            break;
      }
      case FactorWithNegType: {
            /* Evaluate the Factor. Pass it up. */
            retFsm = factorWithNeg->walk( pd );
            break;
      }}
      return retFsm;
}

void FactorWithRep::makeNameTree( ParseData *pd )
{
      switch ( type ) {
      case StarType:
      case StarStarType:
      case OptionalType:
      case PlusType:
      case ExactType:
      case MaxType:
      case MinType:
      case RangeType:
            factorWithRep->makeNameTree( pd );
            break;
      case FactorWithNegType:
            factorWithNeg->makeNameTree( pd );
            break;
      }
}

void FactorWithRep::resolveNameRefs( ParseData *pd )
{
      switch ( type ) {
      case StarType:
      case StarStarType:
      case OptionalType:
      case PlusType:
      case ExactType:
      case MaxType:
      case MinType:
      case RangeType:
            factorWithRep->resolveNameRefs( pd );
            break;
      case FactorWithNegType:
            factorWithNeg->resolveNameRefs( pd );
            break;
      }
}

/* Clean up after a factor with negation node. */
FactorWithNeg::~FactorWithNeg()
{
      switch ( type ) {
            case NegateType:
                  delete factorWithNeg;
                  break;
            case FactorType:
                  delete factor;
                  break;
      }
}

/* Evaluate a factor with negation node. */
FsmAp *FactorWithNeg::walk( ParseData *pd )
{
      FsmAp *retFsm = 0;

      switch ( type ) {
      case NegateType: {
            /* Evaluate the factorWithNeg. */
            FsmAp *toNegate = factorWithNeg->walk( pd );

            /* Negation is subtract from dot-star. */
            retFsm = new FsmAp( &pd->keyOps );
            retFsm->dotStarFsm( );
            retFsm->subtractOp( toNegate );
            afterOpMinimize( retFsm );
            break;
      }
      case FactorType: {
            /* Evaluate the Factor. Pass it up. */
            retFsm = factor->walk( pd );
            break;
      }}
      return retFsm;
}

void FactorWithNeg::makeNameTree( ParseData *pd )
{
      switch ( type ) {
      case NegateType:
            factorWithNeg->makeNameTree( pd );
            break;
      case FactorType:
            factor->makeNameTree( pd );
            break;
      }
}

void FactorWithNeg::resolveNameRefs( ParseData *pd )
{
      switch ( type ) {
      case NegateType:
            factorWithNeg->resolveNameRefs( pd );
            break;
      case FactorType:
            factor->resolveNameRefs( pd );
            break;
      }
}

/* Clean up after a factor node. */
Factor::~Factor()
{
      switch ( type ) {
            case LiteralType:
                  delete literal;
                  break;
            case RangeType:
                  delete range;
                  break;
            case OrExprType:
                  delete reItem;
                  break;
            case RegExprType:
                  delete regExp;
                  break;
            case ReferenceType:
                  break;
            case ParenType:
                  delete join;
                  break;
      }
}

/* Evaluate a factor node. */
FsmAp *Factor::walk( ParseData *pd )
{
      FsmAp *rtnVal = 0;
      switch ( type ) {
      case LiteralType:
            rtnVal = literal->walk( pd );
            break;
      case RangeType:
            rtnVal = range->walk( pd );
            break;
      case OrExprType:
            rtnVal = reItem->walk( pd );
            break;
      case RegExprType:
            rtnVal = regExp->walk( pd );
            break;
      case ReferenceType:
            rtnVal = varDef->walk( pd );
            break;
      case ParenType:
            rtnVal = join->walk( pd );
            break;
      }
      return rtnVal;
}

void Factor::makeNameTree( ParseData *pd )
{
      switch ( type ) {
      case LiteralType:
      case RangeType:
      case OrExprType:
      case RegExprType:
            break;
      case ReferenceType:
            varDef->makeNameTree( loc, pd );
            break;
      case ParenType:
            join->makeNameTree( pd );
            break;
      }
}

void Factor::resolveNameRefs( ParseData *pd )
{
      switch ( type ) {
      case LiteralType:
      case RangeType:
      case OrExprType:
      case RegExprType:
            break;
      case ReferenceType:
            varDef->resolveNameRefs( pd );
            break;
      case ParenType:
            join->resolveNameRefs( pd );
            break;
      }
}

/* Clean up a range object. Must delete the two literals. */
Range::~Range()
{
      delete lowerLit;
      delete upperLit;
}

/* Evaluate a range. Gets the lower an upper key and makes an fsm range. */
FsmAp *Range::walk( ParseData *pd )
{
      long lowKey = lowerLit->makeRangeEndPoint( pd );
      long highKey = upperLit->makeRangeEndPoint( pd );

      /* Validate the range. */
      if ( pd->keyOps.gt( lowKey, highKey ) ) {
            /* Recover by setting upper to lower; */
            error(lowerLit->loc) << "lower end of range is greater then upper end" << endl;
            highKey = lowKey;
      }

      /* Return the range now that it is validated. */
      FsmAp *retFsm = new FsmAp( &pd->keyOps );
      retFsm->rangeFsm( lowKey, highKey );
      return retFsm;
}

/* Return an fsm key for a literal that is a range end point. */
long Literal::makeRangeEndPoint( ParseData *pd )
{
      long retVal;
      switch ( type ) {
      case Number: {
            /* Make the fsm key from the number. */
            retVal = makeFsmKeyNum( str, loc, pd );
            break;
      }
      case LitString: {
            /* The string should be verified length one. */
            makeFsmKeyArray( &retVal, str, 1, pd );
            break;
      }}
      return retVal;
}

/* Evaluate a literal object. */
FsmAp *Literal::walk( ParseData *pd )
{
      /* FsmAp to return, is the alphabet signed. */
      FsmAp *rtnVal = 0;

      switch ( type ) {
      case Number: {
            /* Make the fsm key in int format. */
            long fsmKey = makeFsmKeyNum( str, loc, pd );
            /* Make the new machine. */
            rtnVal = new FsmAp( &pd->keyOps );
            rtnVal->concatFsm( fsmKey );
            break;
      }
      case LitString: {
            /* Make the array of keys in int format. */
            long *arr = new long[str.length()];
            makeFsmKeyArray( arr, str, str.length(), pd );

            /* Make the new machine. */
            rtnVal = new FsmAp( &pd->keyOps );
            rtnVal->concatFsm( arr, str.length() );
            delete[] arr;
            break;
      }}
      return rtnVal;
}

/* Clean up after a regular expression object. */
RegExpr::~RegExpr()
{
      switch ( type ) {
            case RecurseItem:
                  delete regExp;
                  delete item;
                  break;
            case Empty:
                  break;
      }
}

/* Evaluate a regular expression object. */
FsmAp *RegExpr::walk( ParseData *pd )
{
      FsmAp *rtnVal = 0;
      switch ( type ) {
            case RecurseItem: {
                  /* Walk both items. */
                  FsmAp *fsm1 = regExp->walk( pd );
                  FsmAp *fsm2 = item->walk( pd );
                  if ( fsm1 == 0 )
                        rtnVal = fsm2;
                  else {
                        fsm1->concatOp( fsm2 );
                        rtnVal = fsm1;
                  }
                  break;
            }
            case Empty: {
                  rtnVal = 0;
                  break;
            }
      }
      return rtnVal;
}

/* Clean up after an item in a regular expression. */
ReItem::~ReItem()
{
      switch ( type ) {
            case Data:
            case Dot:
                  break;
            case OrBlock:
            case NegOrBlock:
                  delete orBlock;
                  break;
      }
}

/* Evaluate a regular expression object. */
FsmAp *ReItem::walk( ParseData *pd )
{
      /* The fsm to return, is the alphabet signed? */
      FsmAp *rtnVal = 0;

      switch ( type ) {
            case Data: {
                  /* Move the data into an integer array and make a concat fsm. */
                  long *arr = new long[str.length()];
                  makeFsmKeyArray( arr, str, str.length(), pd );

                  /* Make the concat fsm. */
                  rtnVal = new FsmAp( &pd->keyOps );
                  rtnVal->concatFsm( arr, str.length() );

                  /* If the data item is stared, it should be of length one. */
                  assert( ! (str.length() > 1 && star ) );
                  delete[] arr;
                  break;
            }
            case Dot: {
                  /* Make the dot fsm. */
                  rtnVal = new FsmAp( &pd->keyOps );
                  rtnVal->dotFsm( );
                  break;
            }
            case OrBlock: {
                  /* Get the or block and minmize it. */
                  rtnVal = orBlock->walk( pd );
                  rtnVal->minimizePartition2();
                  break;
            }
            case NegOrBlock: {
                  /* Get the or block and minimize it. */
                  FsmAp *fsm = orBlock->walk( pd );
                  fsm->minimizePartition2();

                  /* Make a dot fsm and subtract from it. */
                  rtnVal = new FsmAp( &pd->keyOps );
                  rtnVal->dotFsm( );
                  rtnVal->subtractOp( fsm );
                  rtnVal->minimizePartition2();
                  break;
            }
      }

      /* If the item is followed by a star, then apply the star op. */
      if ( star ) {
            if ( rtnVal->startState->isFinState() ) {
                  warning(loc) << "applying kleene star to a machine that "
                              "accpets zero length word" << endl;
            }

            rtnVal->starOp();
            rtnVal->minimizePartition2();
      }
      return rtnVal;
}

/* Clean up after an or block of a regular expression. */
ReOrBlock::~ReOrBlock()
{
      switch ( type ) {
            case RecurseItem:
                  delete orBlock;
                  delete item;
                  break;
            case Empty:
                  break;
      }
}


/* Evaluate an or block of a regular expression. */
FsmAp *ReOrBlock::walk( ParseData *pd )
{
      FsmAp *rtnVal = 0;
      switch ( type ) {
            case RecurseItem: {
                  /* Evaluate the two fsm. */
                  FsmAp *fsm1 = orBlock->walk( pd );
                  FsmAp *fsm2 = item->walk( pd );
                  if ( fsm1 == 0 )
                        rtnVal = fsm2;
                  else {
                        fsm1->unionOp( fsm2 );
                        rtnVal = fsm1;
                  }
                  break;
            }
            case Empty: {
                  rtnVal = 0;
                  break;
            }
      }
      return rtnVal;;
}

/* Evaluate an or block item of a regular expression. */
FsmAp *ReOrItem::walk( ParseData *pd )
{
      /* The return value, is the alphabet signed? */
      FsmAp *rtnVal = 0;
      switch ( type ) {
      case Data: {
            /* Make the or machine. */
            rtnVal = new FsmAp( &pd->keyOps );

            /* Put the or data into an array of ints. Note that we find unique
             * keys. Duplicates are silently ignored. The alternative would be to
             * issue warning or an error but since we can't with [a0-9a] or 'a' |
             * 'a' don't bother here. */
            long *arr = new long[str.length()];
            int len = makeFsmUniqueKeyArray( arr, str, str.length(), pd );

            /* Run the or operator. */
            rtnVal->orFsm( arr, len );
            delete[] arr;
            break;
      }
      case Range: {
            /* Make the upper and lower keys. */
            long lowKey = makeFsmKeyChar( lower, pd );
            long highKey = makeFsmKeyChar( upper, pd );

            /* Validate the range. */
            if ( pd->keyOps.gt( lowKey, highKey ) ) {
                  /* Recover by setting upper to lower; */
                  error(loc) << "lower end of range is greater then upper end" << endl;
                  highKey = lowKey;
            }

            /* Make the range machine. */
            rtnVal = new FsmAp( &pd->keyOps );
            rtnVal->rangeFsm( lowKey, highKey );
            break;
      }}
      return rtnVal;
}

Generated by  Doxygen 1.6.0   Back to index