ragel/parsetree.cpp

   1 /*
   2  *  Copyright 2001-2006 Adrian Thurston <thurston@cs.queensu.ca>
   3  */
   4
   5 /*  This file is part of Ragel.
   6  *
   7  *  Ragel is free software; you can redistribute it and/or modify
   8  *  it under the terms of the GNU General Public License as published by
   9  *  the Free Software Foundation; either version 2 of the License, or
  10  *  (at your option) any later version.
  11  *
  12  *  Ragel is distributed in the hope that it will be useful,
  13  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  14  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15  *  GNU General Public License for more details.
  16  *
  17  *  You should have received a copy of the GNU General Public License
  18  *  along with Ragel; if not, write to the Free Software
  19  *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  20  */
  21
  22 #include <iostream>
  23 #include <iomanip>
  24 #include <errno.h>
  25 #include <limits.h>
  26 #include <stdlib.h>
  27
  28 /* Parsing. */
  29 #include "ragel.h"
  30 #include "rlparse.h"
  31 #include "parsetree.h"
  32
  33 using namespace std;
  34 ostream &operator<<( ostream &out, const NameRef &nameRef );
  35 ostream &operator<<( ostream &out, const NameInst &nameInst );
  36
  37 /* Convert the literal string which comes in from the scanner into an array of
  38  * characters with escapes and options interpreted. Also null terminates the
  39  * string. Though this null termination should not be relied on for
  40  * interpreting literals in the parser because the string may contain \0 */
  41 char *prepareLitString( const InputLoc &loc, char *data, long length,
  42                 long &resLen, bool &caseInsensitive )
  43 {
  44         char *resData = new char[length+1];
  45         caseInsensitive = false;
  46
  47         char *src = data + 1;
  48         char *end = data + length - 1;
  49
  50         while ( *end != '\'' && *end != '\"' ) {
  51                 if ( *end == 'i' )
  52                         caseInsensitive = true;
  53                 else {
  54                         error( loc ) << "literal string '" << *end <<
  55                                         "' option not supported" << endl;
  56                 }
  57                 end -= 1;
  58         }
  59
  60         char *dest = resData;
  61         long len = 0;
  62         while ( src != end ) {
  63                 if ( *src == '\\' ) {
  64                         switch ( src[1] ) {
  65                         case '0': dest[len++] = '\0'; break;
  66                         case 'a': dest[len++] = '\a'; break;
  67                         case 'b': dest[len++] = '\b'; break;
  68                         case 't': dest[len++] = '\t'; break;
  69                         case 'n': dest[len++] = '\n'; break;
  70                         case 'v': dest[len++] = '\v'; break;
  71                         case 'f': dest[len++] = '\f'; break;
  72                         case 'r': dest[len++] = '\r'; break;
  73                         case '\n':  break;
  74                         default: dest[len++] = src[1]; break;
  75                         }
  76                         src += 2;
  77                 }
  78                 else {
  79                         dest[len++] = *src++;
  80                 }
  81         }
  82
  83         resLen = len;
  84         resData[resLen] = 0;
  85         return resData;
  86 }
  87
  88 FsmAp *VarDef::walk( ParseData *pd )
  89 {
  90         /* We enter into a new name scope. */
  91         NameFrame nameFrame = pd->enterNameScope( true, 1 );
  92
  93         /* Recurse on the expression. */
  94         FsmAp *rtnVal = joinOrLm->walk( pd );
  95
  96         /* Do the tranfer of local error actions. */
  97         LocalErrDictEl *localErrDictEl = pd->localErrDict.find( name );
  98         if ( localErrDictEl != 0 ) {
  99                 for ( StateList::Iter state = rtnVal->stateList; state.lte(); state++ )
 100                         rtnVal->transferErrorActions( state, localErrDictEl->value );
 101         }
 102
 103         /* If the expression below is a join operation with multiple expressions
 104          * then it just had epsilon transisions resolved. If it is a join
 105          * with only a single expression then run the epsilon op now. */
 106         if ( joinOrLm->type == JoinOrLm::JoinType && joinOrLm->join->exprList.length() == 1 )
 107                 rtnVal->epsilonOp();
 108
 109         /* We can now unset entry points that are not longer used. */
 110         pd->unsetObsoleteEntries( rtnVal );
 111
 112         /* If the name of the variable is referenced then add the entry point to
 113          * the graph. */
 114         if ( pd->curNameInst->numRefs > 0 )
 115                 rtnVal->setEntry( pd->curNameInst->id, rtnVal->startState );
 116
 117         /* Pop the name scope. */
 118         pd->popNameScope( nameFrame );
 119         return rtnVal;
 120 }
 121
 122 void VarDef::makeNameTree( const InputLoc &loc, ParseData *pd )
 123 {
 124         /* The variable definition enters a new scope. */
 125         NameInst *prevNameInst = pd->curNameInst;
 126         pd->curNameInst = pd->addNameInst( loc, name, false );
 127
 128         if ( joinOrLm->type == JoinOrLm::LongestMatchType )
 129                 pd->curNameInst->isLongestMatch = true;
 130
 131         /* Recurse. */
 132         joinOrLm->makeNameTree( pd );
 133
 134         /* The name scope ends, pop the name instantiation. */
 135         pd->curNameInst = prevNameInst;
 136 }
 137
 138 void VarDef::resolveNameRefs( ParseData *pd )
 139 {
 140         /* Entering into a new scope. */
 141         NameFrame nameFrame = pd->enterNameScope( true, 1 );
 142
 143         /* Recurse. */
 144         joinOrLm->resolveNameRefs( pd );
 145
 146         /* The name scope ends, pop the name instantiation. */
 147         pd->popNameScope( nameFrame );
 148 }
 149
 150 InputLoc LongestMatchPart::getLoc()
 151 {
 152         return action != 0 ? action->loc : semiLoc;
 153 }
 154
 155 /*
 156  * If there are any LMs then all of the following entry points must reset
 157  * tokstart:
 158  *
 159  *  1. fentry(StateRef)
 160  *  2. ftoto(StateRef), fcall(StateRef), fnext(StateRef)
 161  *  3. targt of any transition that has an fcall (the return loc).
 162  *  4. start state of all longest match routines.
 163  */
 164
 165 Action *LongestMatch::newAction( ParseData *pd, const InputLoc &loc,
 166                 const char *name, InlineList *inlineList )
 167 {
 168         Action *action = new Action( loc, name, inlineList, pd->nextCondId++ );
 169         action->actionRefs.append( pd->curNameInst );
 170         pd->actionList.append( action );
 171         action->isLmAction = true;
 172         return action;
 173 }
 174
 175 void LongestMatch::makeActions( ParseData *pd )
 176 {
 177         /* Make actions that set the action id. */
 178         for ( LmPartList::Iter lmi = *longestMatchList; lmi.lte(); lmi++ ) {
 179                 /* For each part create actions for setting the match type.  We need
 180                  * to do this so that the actions will go into the actionIndex. */
 181                 InlineList *inlineList = new InlineList;
 182                 inlineList->append( new InlineItem( lmi->getLoc(), this, lmi,
 183                                 InlineItem::LmSetActId ) );
 184                 char *actName = new char[50];
 185                 sprintf( actName, "store%i", lmi->longestMatchId );
 186                 lmi->setActId = newAction( pd, lmi->getLoc(), actName, inlineList );
 187         }
 188
 189         /* Make actions that execute the user action and restart on the last
 190          * character. */
 191         for ( LmPartList::Iter lmi = *longestMatchList; lmi.lte(); lmi++ ) {
 192                 /* For each part create actions for setting the match type.  We need
 193                  * to do this so that the actions will go into the actionIndex. */
 194                 InlineList *inlineList = new InlineList;
 195                 inlineList->append( new InlineItem( lmi->getLoc(), this, lmi,
 196                                 InlineItem::LmOnLast ) );
 197                 char *actName = new char[50];
 198                 sprintf( actName, "last%i", lmi->longestMatchId );
 199                 lmi->actOnLast = newAction( pd, lmi->getLoc(), actName, inlineList );
 200         }
 201
 202         /* Make actions that execute the user action and restart on the next
 203          * character.  These actions will set tokend themselves (it is the current
 204          * char). */
 205         for ( LmPartList::Iter lmi = *longestMatchList; lmi.lte(); lmi++ ) {
 206                 /* For each part create actions for setting the match type.  We need
 207                  * to do this so that the actions will go into the actionIndex. */
 208                 InlineList *inlineList = new InlineList;
 209                 inlineList->append( new InlineItem( lmi->getLoc(), this, lmi,
 210                                 InlineItem::LmOnNext ) );
 211                 char *actName = new char[50];
 212                 sprintf( actName, "next%i", lmi->longestMatchId );
 213                 lmi->actOnNext = newAction( pd, lmi->getLoc(), actName, inlineList );
 214         }
 215
 216         /* Make actions that execute the user action and restart at tokend. These
 217          * actions execute some time after matching the last char. */
 218         for ( LmPartList::Iter lmi = *longestMatchList; lmi.lte(); lmi++ ) {
 219                 /* For each part create actions for setting the match type.  We need
 220                  * to do this so that the actions will go into the actionIndex. */
 221                 InlineList *inlineList = new InlineList;
 222                 inlineList->append( new InlineItem( lmi->getLoc(), this, lmi,
 223                                 InlineItem::LmOnLagBehind ) );
 224                 char *actName = new char[50];
 225                 sprintf( actName, "lag%i", lmi->longestMatchId );
 226                 lmi->actLagBehind = newAction( pd, lmi->getLoc(), actName, inlineList );
 227         }
 228
 229         InputLoc loc;
 230         loc.line = 1;
 231         loc.col = 1;
 232
 233         /* Create the error action. */
 234         InlineList *il6 = new InlineList;
 235         il6->append( new InlineItem( loc, this, 0, InlineItem::LmSwitch ) );
 236         lmActSelect = newAction( pd, loc, "switch", il6 );
 237 }
 238
 239 void LongestMatch::findName( ParseData *pd )
 240 {
 241         NameInst *nameInst = pd->curNameInst;
 242         while ( nameInst->name == 0 ) {
 243                 nameInst = nameInst->parent;
 244                 /* Since every machine must must have a name, we should always find a
 245                  * name for the longest match. */
 246                 assert( nameInst != 0 );
 247         }
 248         name = nameInst->name;
 249 }
 250
 251 void LongestMatch::makeNameTree( ParseData *pd )
 252 {
 253         /* Create an anonymous scope for the longest match. Will be used for
 254          * restarting machine after matching a token. */
 255         NameInst *prevNameInst = pd->curNameInst;
 256         pd->curNameInst = pd->addNameInst( loc, 0, false );
 257
 258         /* Recurse into all parts of the longest match operator. */
 259         for ( LmPartList::Iter lmi = *longestMatchList; lmi.lte(); lmi++ )
 260                 lmi->join->makeNameTree( pd );
 261
 262         /* Traverse the name tree upwards to find a name for this lm. */
 263         findName( pd );
 264
 265         /* Also make the longest match's actions at this point. */
 266         makeActions( pd );
 267
 268         /* The name scope ends, pop the name instantiation. */
 269         pd->curNameInst = prevNameInst;
 270 }
 271
 272 void LongestMatch::resolveNameRefs( ParseData *pd )
 273 {
 274         /* The longest match gets its own name scope. */
 275         NameFrame nameFrame = pd->enterNameScope( true, 1 );
 276
 277         /* Take an action reference for each longest match item and recurse. */
 278         for ( LmPartList::Iter lmi = *longestMatchList; lmi.lte(); lmi++ ) {
 279                 /* Record the reference if the item has an action. */
 280                 if ( lmi->action != 0 )
 281                         lmi->action->actionRefs.append( pd->localNameScope );
 282
 283                 /* Recurse down the join. */
 284                 lmi->join->resolveNameRefs( pd );
 285         }
 286
 287         /* The name scope ends, pop the name instantiation. */
 288         pd->popNameScope( nameFrame );
 289 }
 290
 291 void LongestMatch::restart( FsmAp *graph, TransAp *trans )
 292 {
 293         StateAp *fromState = trans->fromState;
 294         graph->detachTrans( fromState, trans->toState, trans );
 295         graph->attachTrans( fromState, graph->startState, trans );
 296 }
 297
 298 void LongestMatch::runLongestMatch( ParseData *pd, FsmAp *graph )
 299 {
 300         graph->markReachableFromHereStopFinal( graph->startState );
 301         for ( StateList::Iter ms = graph->stateList; ms.lte(); ms++ ) {
 302                 if ( ms->stateBits & STB_ISMARKED ) {
 303                         ms->lmItemSet.insert( 0 );
 304                         ms->stateBits &= ~ STB_ISMARKED;
 305                 }
 306         }
 307
 308         /* Transfer the first item of non-empty lmAction tables to the item sets
 309          * of the states that follow. Exclude states that have no transitions out.
 310          * This must happen on a separate pass so that on each iteration of the
 311          * next pass we have the item set entries from all lmAction tables. */
 312         for ( StateList::Iter st = graph->stateList; st.lte(); st++ ) {
 313                 for ( TransList::Iter trans = st->outList; trans.lte(); trans++ ) {
 314                         if ( trans->lmActionTable.length() > 0 ) {
 315                                 LmActionTableEl *lmAct = trans->lmActionTable.data;
 316                                 StateAp *toState = trans->toState;
 317                                 assert( toState );
 318
 319                                 /* Can only optimize this if there are no transitions out.
 320                                  * Note there can be out transitions going nowhere with
 321                                  * actions and they too must inhibit this optimization. */
 322                                 if ( toState->outList.length() > 0 ) {
 323                                         /* Fill the item sets. */
 324                                         graph->markReachableFromHereStopFinal( toState );
 325                                         for ( StateList::Iter ms = graph->stateList; ms.lte(); ms++ ) {
 326                                                 if ( ms->stateBits & STB_ISMARKED ) {
 327                                                         ms->lmItemSet.insert( lmAct->value );
 328                                                         ms->stateBits &= ~ STB_ISMARKED;
 329                                                 }
 330                                         }
 331                                 }
 332                         }
 333                 }
 334         }
 335
 336         /* The lmItem sets are now filled, telling us which longest match rules
 337          * can succeed in which states. First determine if we need to make sure
 338          * act is defaulted to zero. We need to do this if there are any states
 339          * with lmItemSet.length() > 1 and NULL is included. That is, that the
 340          * switch may get called when in fact nothing has been matched. */
 341         int maxItemSetLength = 0;
 342         graph->markReachableFromHereStopFinal( graph->startState );
 343         for ( StateList::Iter ms = graph->stateList; ms.lte(); ms++ ) {
 344                 if ( ms->stateBits & STB_ISMARKED ) {
 345                         if ( ms->lmItemSet.length() > maxItemSetLength )
 346                                 maxItemSetLength = ms->lmItemSet.length();
 347                         ms->stateBits &= ~ STB_ISMARKED;
 348                 }
 349         }
 350
 351         /* The actions executed on starting to match a token. */
 352         graph->isolateStartState();
 353         graph->startState->toStateActionTable.setAction( pd->initTokStartOrd, pd->initTokStart );
 354         graph->startState->fromStateActionTable.setAction( pd->setTokStartOrd, pd->setTokStart );
 355         if ( maxItemSetLength > 1 ) {
 356                 /* The longest match action switch may be called when tokens are
 357                  * matched, in which case act must be initialized, there must be a
 358                  * case to handle the error, and the generated machine will require an
 359                  * error state. */
 360                 lmSwitchHandlesError = true;
 361                 pd->lmRequiresErrorState = true;
 362                 graph->startState->toStateActionTable.setAction( pd->initActIdOrd, pd->initActId );
 363         }
 364
 365         /* The place to store transitions to restart. It maybe possible for the
 366          * restarting to affect the searching through the graph that follows. For
 367          * now take the safe route and save the list of transitions to restart
 368          * until after all searching is done. */
 369         Vector<TransAp*> restartTrans;
 370
 371         /* Set actions that do immediate token recognition, set the longest match part
 372          * id and set the token ending. */
 373         for ( StateList::Iter st = graph->stateList; st.lte(); st++ ) {
 374                 for ( TransList::Iter trans = st->outList; trans.lte(); trans++ ) {
 375                         if ( trans->lmActionTable.length() > 0 ) {
 376                                 LmActionTableEl *lmAct = trans->lmActionTable.data;
 377                                 StateAp *toState = trans->toState;
 378                                 assert( toState );
 379
 380                                 /* Can only optimize this if there are no transitions out.
 381                                  * Note there can be out transitions going nowhere with
 382                                  * actions and they too must inhibit this optimization. */
 383                                 if ( toState->outList.length() == 0 ) {
 384                                         /* Can execute the immediate action for the longest match
 385                                          * part. Redirect the action to the start state.
 386                                          *
 387                                          * NOTE: When we need to inhibit on_last due to leaving
 388                                          * actions the above test suffices. If the state has out
 389                                          * actions then it will fail because the out action will
 390                                          * have been transferred to an error transition, which
 391                                          * makes the outlist non-empty. */
 392                                         trans->actionTable.setAction( lmAct->key,
 393                                                         lmAct->value->actOnLast );
 394                                         restartTrans.append( trans );
 395                                 }
 396                                 else {
 397                                         /* Look for non final states that have a non-empty item
 398                                          * set. If these are present then we need to record the
 399                                          * end of the token.  Also Find the highest item set
 400                                          * length reachable from here (excluding at transtions to
 401                                          * final states). */
 402                                         bool nonFinalNonEmptyItemSet = false;
 403                                         maxItemSetLength = 0;
 404                                         graph->markReachableFromHereStopFinal( toState );
 405                                         for ( StateList::Iter ms = graph->stateList; ms.lte(); ms++ ) {
 406                                                 if ( ms->stateBits & STB_ISMARKED ) {
 407                                                         if ( ms->lmItemSet.length() > 0 && !ms->isFinState() )
 408                                                                 nonFinalNonEmptyItemSet = true;
 409                                                         if ( ms->lmItemSet.length() > maxItemSetLength )
 410                                                                 maxItemSetLength = ms->lmItemSet.length();
 411                                                         ms->stateBits &= ~ STB_ISMARKED;
 412                                                 }
 413                                         }
 414
 415                                         /* If there are reachable states that are not final and
 416                                          * have non empty item sets or that have an item set
 417                                          * length greater than one then we need to set tokend
 418                                          * because the error action that matches the token will
 419                                          * require it. */
 420                                         if ( nonFinalNonEmptyItemSet || maxItemSetLength > 1 )
 421                                                 trans->actionTable.setAction( pd->setTokEndOrd, pd->setTokEnd );
 422
 423                                         /* Some states may not know which longest match item to
 424                                          * execute, must set it. */
 425                                         if ( maxItemSetLength > 1 ) {
 426                                                 /* There are transitions out, another match may come. */
 427                                                 trans->actionTable.setAction( lmAct->key,
 428                                                                 lmAct->value->setActId );
 429                                         }
 430                                 }
 431                         }
 432                 }
 433         }
 434
 435         /* Now that all graph searching is done it certainly safe set the
 436          * restarting. It may be safe above, however this must be verified. */
 437         for ( Vector<TransAp*>::Iter pt = restartTrans; pt.lte(); pt++ )
 438                 restart( graph, *pt );
 439
 440         int lmErrActionOrd = pd->curActionOrd++;
 441
 442         /* Embed the error for recognizing a char. */
 443         for ( StateList::Iter st = graph->stateList; st.lte(); st++ ) {
 444                 if ( st->lmItemSet.length() == 1 && st->lmItemSet[0] != 0 ) {
 445                         if ( st->isFinState() ) {
 446                                 /* On error execute the onActNext action, which knows that
 447                                  * the last character of the token was one back and restart. */
 448                                 graph->setErrorTarget( st, graph->startState, &lmErrActionOrd,
 449                                                 &st->lmItemSet[0]->actOnNext, 1 );
 450                                 st->eofActionTable.setAction( lmErrActionOrd,
 451                                                 st->lmItemSet[0]->actOnNext );
 452                                 st->eofTarget = graph->startState;
 453                         }
 454                         else {
 455                                 graph->setErrorTarget( st, graph->startState, &lmErrActionOrd,
 456                                                 &st->lmItemSet[0]->actLagBehind, 1 );
 457                                 st->eofActionTable.setAction( lmErrActionOrd,
 458                                                 st->lmItemSet[0]->actLagBehind );
 459                                 st->eofTarget = graph->startState;
 460                         }
 461                 }
 462                 else if ( st->lmItemSet.length() > 1 ) {
 463                         /* Need to use the select. Take note of which items the select
 464                          * is needed for so only the necessary actions are included. */
 465                         for ( LmItemSet::Iter plmi = st->lmItemSet; plmi.lte(); plmi++ ) {
 466                                 if ( *plmi != 0 )
 467                                         (*plmi)->inLmSelect = true;
 468                         }
 469                         /* On error, execute the action select and go to the start state. */
 470                         graph->setErrorTarget( st, graph->startState, &lmErrActionOrd,
 471                                         &lmActSelect, 1 );
 472                         st->eofActionTable.setAction( lmErrActionOrd, lmActSelect );
 473                         st->eofTarget = graph->startState;
 474                 }
 475         }
 476
 477         /* Finally, the start state should be made final. */
 478         graph->setFinState( graph->startState );
 479 }
 480
 481 void LongestMatch::transferScannerLeavingActions( FsmAp *graph )
 482 {
 483         for ( StateList::Iter st = graph->stateList; st.lte(); st++ ) {
 484                 if ( st->outActionTable.length() > 0 )
 485                         graph->setErrorActions( st, st->outActionTable );
 486         }
 487 }
 488
 489 FsmAp *LongestMatch::walk( ParseData *pd )
 490 {
 491         /* The longest match has it's own name scope. */
 492         NameFrame nameFrame = pd->enterNameScope( true, 1 );
 493
 494         /* Make each part of the longest match. */
 495         FsmAp **parts = new FsmAp*[longestMatchList->length()];
 496         LmPartList::Iter lmi = *longestMatchList;
 497         for ( int i = 0; lmi.lte(); lmi++, i++ ) {
 498                 /* Create the machine and embed the setting of the longest match id. */
 499                 parts[i] = lmi->join->walk( pd );
 500                 parts[i]->longMatchAction( pd->curActionOrd++, lmi );
 501         }
 502
 503         /* Before we union the patterns we need to deal with leaving actions. They
 504          * are transfered to error transitions out of the final states (like local
 505          * error actions) and to eof actions. In the scanner we need to forbid
 506          * on_last for any final state that has an leaving action. */
 507         for ( int i = 0; i < longestMatchList->length(); i++ )
 508                 transferScannerLeavingActions( parts[i] );
 509
 510         /* Union machines one and up with machine zero. The grammar dictates that
 511          * there will always be at least one part. */
 512         FsmAp *rtnVal = parts[0];
 513         for ( int i = 1; i < longestMatchList->length(); i++ ) {
 514                 rtnVal->unionOp( parts[i] );
 515                 afterOpMinimize( rtnVal );
 516         }
 517
 518         runLongestMatch( pd, rtnVal );
 519
 520         /* Pop the name scope. */
 521         pd->popNameScope( nameFrame );
 522
 523         delete[] parts;
 524         return rtnVal;
 525 }
 526
 527 FsmAp *JoinOrLm::walk( ParseData *pd )
 528 {
 529         FsmAp *rtnVal = 0;
 530         switch ( type ) {
 531         case JoinType:
 532                 rtnVal = join->walk( pd );
 533                 break;
 534         case LongestMatchType:
 535                 rtnVal = longestMatch->walk( pd );
 536                 break;
 537         }
 538         return rtnVal;
 539 }
 540
 541 void JoinOrLm::makeNameTree( ParseData *pd )
 542 {
 543         switch ( type ) {
 544         case JoinType:
 545                 join->makeNameTree( pd );
 546                 break;
 547         case LongestMatchType:
 548                 longestMatch->makeNameTree( pd );
 549                 break;
 550         }
 551 }
 552
 553 void JoinOrLm::resolveNameRefs( ParseData *pd )
 554 {
 555         switch ( type ) {
 556         case JoinType:
 557                 join->resolveNameRefs( pd );
 558                 break;
 559         case LongestMatchType:
 560                 longestMatch->resolveNameRefs( pd );
 561                 break;
 562         }
 563 }
 564
 565
 566 /* Construct with a location and the first expression. */
 567 Join::Join( const InputLoc &loc, Expression *expr )
 568 :
 569         loc(loc)
 570 {
 571         exprList.append( expr );
 572 }
 573
 574 /* Construct with a location and the first expression. */
 575 Join::Join( Expression *expr )
 576 :
 577         loc(loc)
 578 {
 579         exprList.append( expr );
 580 }
 581
 582 /* Walk an expression node. */
 583 FsmAp *Join::walk( ParseData *pd )
 584 {
 585         if ( exprList.length() > 1 )
 586                 return walkJoin( pd );
 587         else
 588                 return exprList.head->walk( pd );
 589 }
 590
 591 /* There is a list of expressions to join. */
 592 FsmAp *Join::walkJoin( ParseData *pd )
 593 {
 594         /* We enter into a new name scope. */
 595         NameFrame nameFrame = pd->enterNameScope( true, 1 );
 596
 597         /* Evaluate the machines. */
 598         FsmAp **fsms = new FsmAp*[exprList.length()];
 599         ExprList::Iter expr = exprList;
 600         for ( int e = 0; e < exprList.length(); e++, expr++ )
 601                 fsms[e] = expr->walk( pd );
 602
 603         /* Get the start and final names. Final is
 604          * guaranteed to exist, start is not. */
 605         NameInst *startName = pd->curNameInst->start;
 606         NameInst *finalName = pd->curNameInst->final;
 607
 608         int startId = -1;
 609         if ( startName != 0 ) {
 610                 /* Take note that there was an implicit link to the start machine. */
 611                 pd->localNameScope->referencedNames.append( startName );
 612                 startId = startName->id;
 613         }
 614
 615         /* A final id of -1 indicates there is no epsilon that references the
 616          * final state, therefor do not create one or set an entry point to it. */
 617         int finalId = -1;
 618         if ( finalName->numRefs > 0 )
 619                 finalId = finalName->id;
 620
 621         /* Join machines 1 and up onto machine 0. */
 622         FsmAp *retFsm = fsms[0];
 623         retFsm->joinOp( startId, finalId, fsms+1, exprList.length()-1 );
 624
 625         /* We can now unset entry points that are not longer used. */
 626         pd->unsetObsoleteEntries( retFsm );
 627
 628         /* Pop the name scope. */
 629         pd->popNameScope( nameFrame );
 630
 631         delete[] fsms;
 632         return retFsm;
 633 }
 634
 635 void Join::makeNameTree( ParseData *pd )
 636 {
 637         if ( exprList.length() > 1 ) {
 638                 /* Create the new anonymous scope. */
 639                 NameInst *prevNameInst = pd->curNameInst;
 640                 pd->curNameInst = pd->addNameInst( loc, 0, false );
 641
 642                 /* Join scopes need an implicit "final" target. */
 643                 pd->curNameInst->final = new NameInst( InputLoc(), pd->curNameInst, "final",
 644                                 pd->nextNameId++, false );
 645
 646                 /* Recurse into all expressions in the list. */
 647                 for ( ExprList::Iter expr = exprList; expr.lte(); expr++ )
 648                         expr->makeNameTree( pd );
 649
 650                 /* The name scope ends, pop the name instantiation. */
 651                 pd->curNameInst = prevNameInst;
 652         }
 653         else {
 654                 /* Recurse into the single expression. */
 655                 exprList.head->makeNameTree( pd );
 656         }
 657 }
 658
 659
 660 void Join::resolveNameRefs( ParseData *pd )
 661 {
 662         /* Branch on whether or not there is to be a join. */
 663         if ( exprList.length() > 1 ) {
 664                 /* The variable definition enters a new scope. */
 665                 NameFrame nameFrame = pd->enterNameScope( true, 1 );
 666
 667                 /* The join scope must contain a start label. */
 668                 NameSet resolved = pd->resolvePart( pd->localNameScope, "start", true );
 669                 if ( resolved.length() > 0 ) {
 670                         /* Take the first. */
 671                         pd->curNameInst->start = resolved[0];
 672                         if ( resolved.length() > 1 ) {
 673                                 /* Complain about the multiple references. */
 674                                 error(loc) << "join operation has multiple start labels" << endl;
 675                                 errorStateLabels( resolved );
 676                         }
 677                 }
 678
 679                 /* Make sure there is a start label. */
 680                 if ( pd->curNameInst->start != 0 ) {
 681                         /* There is an implicit reference to start name. */
 682                         pd->curNameInst->start->numRefs += 1;
 683                 }
 684                 else {
 685                         /* No start label. */
 686                         error(loc) << "join operation has no start label" << endl;
 687                 }
 688
 689                 /* Recurse into all expressions in the list. */
 690                 for ( ExprList::Iter expr = exprList; expr.lte(); expr++ )
 691                         expr->resolveNameRefs( pd );
 692
 693                 /* The name scope ends, pop the name instantiation. */
 694                 pd->popNameScope( nameFrame );
 695         }
 696         else {
 697                 /* Recurse into the single expression. */
 698                 exprList.head->resolveNameRefs( pd );
 699         }
 700 }
 701
 702 /* Clean up after an expression node. */
 703 Expression::~Expression()
 704 {
 705         switch ( type ) {
 706                 case OrType: case IntersectType: case SubtractType:
 707                 case StrongSubtractType:
 708                         delete expression;
 709                         delete term;
 710                         break;
 711                 case TermType:
 712                         delete term;
 713                         break;
 714                 case BuiltinType:
 715                         break;
 716         }
 717 }
 718
 719 /* Evaluate a single expression node. */
 720 FsmAp *Expression::walk( ParseData *pd, bool lastInSeq )
 721 {
 722         FsmAp *rtnVal = 0;
 723         switch ( type ) {
 724                 case OrType: {
 725                         /* Evaluate the expression. */
 726                         rtnVal = expression->walk( pd, false );
 727                         /* Evaluate the term. */
 728                         FsmAp *rhs = term->walk( pd );
 729                         /* Perform union. */
 730                         rtnVal->unionOp( rhs );
 731                         afterOpMinimize( rtnVal, lastInSeq );
 732                         break;
 733                 }
 734                 case IntersectType: {
 735                         /* Evaluate the expression. */
 736                         rtnVal = expression->walk( pd );
 737                         /* Evaluate the term. */
 738                         FsmAp *rhs = term->walk( pd );
 739                         /* Perform intersection. */
 740                         rtnVal->intersectOp( rhs );
 741                         afterOpMinimize( rtnVal, lastInSeq );
 742                         break;
 743                 }
 744                 case SubtractType: {
 745                         /* Evaluate the expression. */
 746                         rtnVal = expression->walk( pd );
 747                         /* Evaluate the term. */
 748                         FsmAp *rhs = term->walk( pd );
 749                         /* Perform subtraction. */
 750                         rtnVal->subtractOp( rhs );
 751                         afterOpMinimize( rtnVal, lastInSeq );
 752                         break;
 753                 }
 754                 case StrongSubtractType: {
 755                         /* Evaluate the expression. */
 756                         rtnVal = expression->walk( pd );
 757
 758                         /* Evaluate the term and pad it with any* machines. */
 759                         FsmAp *rhs = dotStarFsm( pd );
 760                         FsmAp *termFsm = term->walk( pd );
 761                         FsmAp *trailAnyStar = dotStarFsm( pd );
 762                         rhs->concatOp( termFsm );
 763                         rhs->concatOp( trailAnyStar );
 764
 765                         /* Perform subtraction. */
 766                         rtnVal->subtractOp( rhs );
 767                         afterOpMinimize( rtnVal, lastInSeq );
 768                         break;
 769                 }
 770                 case TermType: {
 771                         /* Return result of the term. */
 772                         rtnVal = term->walk( pd );
 773                         break;
 774                 }
 775                 case BuiltinType: {
 776                         /* Duplicate the builtin. */
 777                         rtnVal = makeBuiltin( builtin, pd );
 778                         break;
 779                 }
 780         }
 781
 782         return rtnVal;
 783 }
 784
 785 void Expression::makeNameTree( ParseData *pd )
 786 {
 787         switch ( type ) {
 788         case OrType:
 789         case IntersectType:
 790         case SubtractType:
 791         case StrongSubtractType:
 792                 expression->makeNameTree( pd );
 793                 term->makeNameTree( pd );
 794                 break;
 795         case TermType:
 796                 term->makeNameTree( pd );
 797                 break;
 798         case BuiltinType:
 799                 break;
 800         }
 801 }
 802
 803 void Expression::resolveNameRefs( ParseData *pd )
 804 {
 805         switch ( type ) {
 806         case OrType:
 807         case IntersectType:
 808         case SubtractType:
 809         case StrongSubtractType:
 810                 expression->resolveNameRefs( pd );
 811                 term->resolveNameRefs( pd );
 812                 break;
 813         case TermType:
 814                 term->resolveNameRefs( pd );
 815                 break;
 816         case BuiltinType:
 817                 break;
 818         }
 819 }
 820
 821 /* Clean up after a term node. */
 822 Term::~Term()
 823 {
 824         switch ( type ) {
 825                 case ConcatType:
 826                 case RightStartType:
 827                 case RightFinishType:
 828                 case LeftType:
 829                         delete term;
 830                         delete factorWithAug;
 831                         break;
 832                 case FactorWithAugType:
 833                         delete factorWithAug;
 834                         break;
 835         }
 836 }
 837
 838 /* Evaluate a term node. */
 839 FsmAp *Term::walk( ParseData *pd, bool lastInSeq )
 840 {
 841         FsmAp *rtnVal = 0;
 842         switch ( type ) {
 843                 case ConcatType: {
 844                         /* Evaluate the Term. */
 845                         rtnVal = term->walk( pd, false );
 846                         /* Evaluate the FactorWithRep. */
 847                         FsmAp *rhs = factorWithAug->walk( pd );
 848                         /* Perform concatenation. */
 849                         rtnVal->concatOp( rhs );
 850                         afterOpMinimize( rtnVal, lastInSeq );
 851                         break;
 852                 }
 853                 case RightStartType: {
 854                         /* Evaluate the Term. */
 855                         rtnVal = term->walk( pd );
 856
 857                         /* Evaluate the FactorWithRep. */
 858                         FsmAp *rhs = factorWithAug->walk( pd );
 859
 860                         /* Set up the priority descriptors. The left machine gets the
 861                          * lower priority where as the right get the higher start priority. */
 862                         priorDescs[0].key = pd->nextPriorKey++;
 863                         priorDescs[0].priority = 0;
 864                         rtnVal->allTransPrior( pd->curPriorOrd++, &priorDescs[0] );
 865
 866                         /* The start transitions of the right machine gets the higher
 867                          * priority. Use the same unique key. */
 868                         priorDescs[1].key = priorDescs[0].key;
 869                         priorDescs[1].priority = 1;
 870                         rhs->startFsmPrior( pd->curPriorOrd++, &priorDescs[1] );
 871
 872                         /* Perform concatenation. */
 873                         rtnVal->concatOp( rhs );
 874                         afterOpMinimize( rtnVal, lastInSeq );
 875                         break;
 876                 }
 877                 case RightFinishType: {
 878                         /* Evaluate the Term. */
 879                         rtnVal = term->walk( pd );
 880
 881                         /* Evaluate the FactorWithRep. */
 882                         FsmAp *rhs = factorWithAug->walk( pd );
 883
 884                         /* Set up the priority descriptors. The left machine gets the
 885                          * lower priority where as the finishing transitions to the right
 886                          * get the higher priority. */
 887                         priorDescs[0].key = pd->nextPriorKey++;
 888                         priorDescs[0].priority = 0;
 889                         rtnVal->allTransPrior( pd->curPriorOrd++, &priorDescs[0] );
 890
 891                         /* The finishing transitions of the right machine get the higher
 892                          * priority. Use the same unique key. */
 893                         priorDescs[1].key = priorDescs[0].key;
 894                         priorDescs[1].priority = 1;
 895                         rhs->finishFsmPrior( pd->curPriorOrd++, &priorDescs[1] );
 896
 897                         /* If the right machine's start state is final we need to guard
 898                          * against the left machine persisting by moving through the empty
 899                          * string. */
 900                         if ( rhs->startState->isFinState() ) {
 901                                 rhs->startState->outPriorTable.setPrior(
 902                                                 pd->curPriorOrd++, &priorDescs[1] );
 903                         }
 904
 905                         /* Perform concatenation. */
 906                         rtnVal->concatOp( rhs );
 907                         afterOpMinimize( rtnVal, lastInSeq );
 908                         break;
 909                 }
 910                 case LeftType: {
 911                         /* Evaluate the Term. */
 912                         rtnVal = term->walk( pd );
 913
 914                         /* Evaluate the FactorWithRep. */
 915                         FsmAp *rhs = factorWithAug->walk( pd );
 916
 917                         /* Set up the priority descriptors. The left machine gets the
 918                          * higher priority. */
 919                         priorDescs[0].key = pd->nextPriorKey++;
 920                         priorDescs[0].priority = 1;
 921                         rtnVal->allTransPrior( pd->curPriorOrd++, &priorDescs[0] );
 922
 923                         /* The right machine gets the lower priority. We cannot use
 924                          * allTransPrior here in case the start state of the right machine
 925                          * is final. It would allow the right machine thread to run along
 926                          * with the left if just passing through the start state. Using
 927                          * startFsmPrior prevents this. */
 928                         priorDescs[1].key = priorDescs[0].key;
 929                         priorDescs[1].priority = 0;
 930                         rhs->startFsmPrior( pd->curPriorOrd++, &priorDescs[1] );
 931
 932                         /* Perform concatenation. */
 933                         rtnVal->concatOp( rhs );
 934                         afterOpMinimize( rtnVal, lastInSeq );
 935                         break;
 936                 }
 937                 case FactorWithAugType: {
 938                         rtnVal = factorWithAug->walk( pd );
 939                         break;
 940                 }
 941         }
 942         return rtnVal;
 943 }
 944
 945 void Term::makeNameTree( ParseData *pd )
 946 {
 947         switch ( type ) {
 948         case ConcatType:
 949         case RightStartType:
 950         case RightFinishType:
 951         case LeftType:
 952                 term->makeNameTree( pd );
 953                 factorWithAug->makeNameTree( pd );
 954                 break;
 955         case FactorWithAugType:
 956                 factorWithAug->makeNameTree( pd );
 957                 break;
 958         }
 959 }
 960
 961 void Term::resolveNameRefs( ParseData *pd )
 962 {
 963         switch ( type ) {
 964         case ConcatType:
 965         case RightStartType:
 966         case RightFinishType:
 967         case LeftType:
 968                 term->resolveNameRefs( pd );
 969                 factorWithAug->resolveNameRefs( pd );
 970                 break;
 971         case FactorWithAugType:
 972                 factorWithAug->resolveNameRefs( pd );
 973                 break;
 974         }
 975 }
 976
 977 /* Clean up after a factor with augmentation node. */
 978 FactorWithAug::~FactorWithAug()
 979 {
 980         delete factorWithRep;
 981
 982         /* Walk the vector of parser actions, deleting function names. */
 983
 984         /* Clean up priority descriptors. */
 985         if ( priorDescs != 0 )
 986                 delete[] priorDescs;
 987 }
 988
 989 void FactorWithAug::assignActions( ParseData *pd, FsmAp *graph, int *actionOrd )
 990 {
 991         /* Assign actions. */
 992         for ( int i = 0; i < actions.length(); i++ )  {
 993                 switch ( actions[i].type ) {
 994                 /* Transition actions. */
 995                 case at_start:
 996                         graph->startFsmAction( actionOrd[i], actions[i].action );
 997                         afterOpMinimize( graph );
 998                         break;
 999                 case at_all:
1000                         graph->allTransAction( actionOrd[i], actions[i].action );
1001                         break;
1002                 case at_finish:
1003                         graph->finishFsmAction( actionOrd[i], actions[i].action );
1004                         break;
1005                 case at_leave:
1006                         graph->leaveFsmAction( actionOrd[i], actions[i].action );
1007                         break;
1008
1009                 /* Global error actions. */
1010                 case at_start_gbl_error:
1011                         graph->startErrorAction( actionOrd[i], actions[i].action, 0 );
1012                         afterOpMinimize( graph );
1013                         break;
1014                 case at_all_gbl_error:
1015                         graph->allErrorAction( actionOrd[i], actions[i].action, 0 );
1016                         break;
1017                 case at_final_gbl_error:
1018                         graph->finalErrorAction( actionOrd[i], actions[i].action, 0 );
1019                         break;
1020                 case at_not_start_gbl_error:
1021                         graph->notStartErrorAction( actionOrd[i], actions[i].action, 0 );
1022                         break;
1023                 case at_not_final_gbl_error:
1024                         graph->notFinalErrorAction( actionOrd[i], actions[i].action, 0 );
1025                         break;
1026                 case at_middle_gbl_error:
1027                         graph->middleErrorAction( actionOrd[i], actions[i].action, 0 );
1028                         break;
1029
1030                 /* Local error actions. */
1031                 case at_start_local_error:
1032                         graph->startErrorAction( actionOrd[i], actions[i].action,
1033                                         actions[i].localErrKey );
1034                         afterOpMinimize( graph );
1035                         break;
1036                 case at_all_local_error:
1037                         graph->allErrorAction( actionOrd[i], actions[i].action,
1038                                         actions[i].localErrKey );
1039                         break;
1040                 case at_final_local_error:
1041                         graph->finalErrorAction( actionOrd[i], actions[i].action,
1042                                         actions[i].localErrKey );
1043                         break;
1044                 case at_not_start_local_error:
1045                         graph->notStartErrorAction( actionOrd[i], actions[i].action,
1046                                         actions[i].localErrKey );
1047                         break;
1048                 case at_not_final_local_error:
1049                         graph->notFinalErrorAction( actionOrd[i], actions[i].action,
1050                                         actions[i].localErrKey );
1051                         break;
1052                 case at_middle_local_error:
1053                         graph->middleErrorAction( actionOrd[i], actions[i].action,
1054                                         actions[i].localErrKey );
1055                         break;
1056
1057                 /* EOF actions. */
1058                 case at_start_eof:
1059                         graph->startEOFAction( actionOrd[i], actions[i].action );
1060                         afterOpMinimize( graph );
1061                         break;
1062                 case at_all_eof:
1063                         graph->allEOFAction( actionOrd[i], actions[i].action );
1064                         break;
1065                 case at_final_eof:
1066                         graph->finalEOFAction( actionOrd[i], actions[i].action );
1067                         break;
1068                 case at_not_start_eof:
1069                         graph->notStartEOFAction( actionOrd[i], actions[i].action );
1070                         break;
1071                 case at_not_final_eof:
1072                         graph->notFinalEOFAction( actionOrd[i], actions[i].action );
1073                         break;
1074                 case at_middle_eof:
1075                         graph->middleEOFAction( actionOrd[i], actions[i].action );
1076                         break;
1077
1078                 /* To State Actions. */
1079                 case at_start_to_state:
1080                         graph->startToStateAction( actionOrd[i], actions[i].action );
1081                         afterOpMinimize( graph );
1082                         break;
1083                 case at_all_to_state:
1084                         graph->allToStateAction( actionOrd[i], actions[i].action );
1085                         break;
1086                 case at_final_to_state:
1087                         graph->finalToStateAction( actionOrd[i], actions[i].action );
1088                         break;
1089                 case at_not_start_to_state:
1090                         graph->notStartToStateAction( actionOrd[i], actions[i].action );
1091                         break;
1092                 case at_not_final_to_state:
1093                         graph->notFinalToStateAction( actionOrd[i], actions[i].action );
1094                         break;
1095                 case at_middle_to_state:
1096                         graph->middleToStateAction( actionOrd[i], actions[i].action );
1097                         break;
1098
1099                 /* From State Actions. */
1100                 case at_start_from_state:
1101                         graph->startFromStateAction( actionOrd[i], actions[i].action );
1102                         afterOpMinimize( graph );
1103                         break;
1104                 case at_all_from_state:
1105                         graph->allFromStateAction( actionOrd[i], actions[i].action );
1106                         break;
1107                 case at_final_from_state:
1108                         graph->finalFromStateAction( actionOrd[i], actions[i].action );
1109                         break;
1110                 case at_not_start_from_state:
1111                         graph->notStartFromStateAction( actionOrd[i], actions[i].action );
1112                         break;
1113                 case at_not_final_from_state:
1114                         graph->notFinalFromStateAction( actionOrd[i], actions[i].action );
1115                         break;
1116                 case at_middle_from_state:
1117                         graph->middleFromStateAction( actionOrd[i], actions[i].action );
1118                         break;
1119
1120                 /* Remaining cases, prevented by the parser. */
1121                 default:
1122                         assert( false );
1123                         break;
1124                 }
1125         }
1126 }
1127
1128 void FactorWithAug::assignPriorities( FsmAp *graph, int *priorOrd )
1129 {
1130         /* Assign priorities. */
1131         for ( int i = 0; i < priorityAugs.length(); i++ ) {
1132                 switch ( priorityAugs[i].type ) {
1133                 case at_start:
1134                         graph->startFsmPrior( priorOrd[i], &priorDescs[i]);
1135                         /* Start fsm priorities are a special case that may require
1136                          * minimization afterwards. */
1137                         afterOpMinimize( graph );
1138                         break;
1139                 case at_all:
1140                         graph->allTransPrior( priorOrd[i], &priorDescs[i] );
1141                         break;
1142                 case at_finish:
1143                         graph->finishFsmPrior( priorOrd[i], &priorDescs[i] );
1144                         break;
1145                 case at_leave:
1146                         graph->leaveFsmPrior( priorOrd[i], &priorDescs[i] );
1147                         break;
1148
1149                 default:
1150                         /* Parser Prevents this case. */
1151                         break;
1152                 }
1153         }
1154 }
1155
1156 void FactorWithAug::assignConditions( FsmAp *graph )
1157 {
1158         for ( int i = 0; i < conditions.length(); i++ )  {
1159                 switch ( conditions[i].type ) {
1160                 /* Transition actions. */
1161                 case at_start:
1162                         graph->startFsmCondition( conditions[i].action, conditions[i].sense );
1163                         afterOpMinimize( graph );
1164                         break;
1165                 case at_all:
1166                         graph->allTransCondition( conditions[i].action, conditions[i].sense );
1167                         break;
1168                 case at_leave:
1169                         graph->leaveFsmCondition( conditions[i].action, conditions[i].sense );
1170                         break;
1171                 default:
1172                         break;
1173                 }
1174         }
1175 }
1176
1177
1178 /* Evaluate a factor with augmentation node. */
1179 FsmAp *FactorWithAug::walk( ParseData *pd )
1180 {
1181         /* Enter into the scopes created for the labels. */
1182         NameFrame nameFrame = pd->enterNameScope( false, labels.length() );
1183
1184         /* Make the array of function orderings. */
1185         int *actionOrd = 0;
1186         if ( actions.length() > 0 )
1187                 actionOrd = new int[actions.length()];
1188
1189         /* First walk the list of actions, assigning order to all starting
1190          * actions. */
1191         for ( int i = 0; i < actions.length(); i++ ) {
1192                 if ( actions[i].type == at_start ||
1193                                 actions[i].type == at_start_gbl_error ||
1194                                 actions[i].type == at_start_local_error ||
1195                                 actions[i].type == at_start_to_state ||
1196                                 actions[i].type == at_start_from_state ||
1197                                 actions[i].type == at_start_eof )
1198                         actionOrd[i] = pd->curActionOrd++;
1199         }
1200
1201         /* Evaluate the factor with repetition. */
1202         FsmAp *rtnVal = factorWithRep->walk( pd );
1203
1204         /* Compute the remaining action orderings. */
1205         for ( int i = 0; i < actions.length(); i++ ) {
1206                 if ( actions[i].type != at_start &&
1207                                 actions[i].type != at_start_gbl_error &&
1208                                 actions[i].type != at_start_local_error &&
1209                                 actions[i].type != at_start_to_state &&
1210                                 actions[i].type != at_start_from_state &&
1211                                 actions[i].type != at_start_eof )
1212                         actionOrd[i] = pd->curActionOrd++;
1213         }
1214
1215         /* Embed conditions. */
1216         assignConditions( rtnVal );
1217
1218         /* Embed actions. */
1219         assignActions( pd, rtnVal , actionOrd );
1220
1221         /* Make the array of priority orderings. Orderings are local to this walk
1222          * of the factor with augmentation. */
1223         int *priorOrd = 0;
1224         if ( priorityAugs.length() > 0 )
1225                 priorOrd = new int[priorityAugs.length()];
1226
1227         /* Walk all priorities, assigning the priority ordering. */
1228         for ( int i = 0; i < priorityAugs.length(); i++ )
1229                 priorOrd[i] = pd->curPriorOrd++;
1230
1231         /* If the priority descriptors have not been made, make them now.  Make
1232          * priority descriptors for each priority asignment that will be passed to
1233          * the fsm. Used to keep track of the key, value and used bit. */
1234         if ( priorDescs == 0 && priorityAugs.length() > 0 ) {
1235                 priorDescs = new PriorDesc[priorityAugs.length()];
1236                 for ( int i = 0; i < priorityAugs.length(); i++ ) {
1237                         /* Init the prior descriptor for the priority setting. */
1238                         priorDescs[i].key = priorityAugs[i].priorKey;
1239                         priorDescs[i].priority = priorityAugs[i].priorValue;
1240                 }
1241         }
1242
1243         /* Assign priorities into the machine. */
1244         assignPriorities( rtnVal, priorOrd );
1245
1246         /* Assign epsilon transitions. */
1247         for ( int e = 0; e < epsilonLinks.length(); e++ ) {
1248                 /* Get the name, which may not exist. If it doesn't then silently
1249                  * ignore it because an error has already been reported. */
1250                 NameInst *epTarg = pd->epsilonResolvedLinks[pd->nextEpsilonResolvedLink++];
1251                 if ( epTarg != 0 ) {
1252                         /* Make the epsilon transitions. */
1253                         rtnVal->epsilonTrans( epTarg->id );
1254
1255                         /* Note that we have made a link to the name. */
1256                         pd->localNameScope->referencedNames.append( epTarg );
1257                 }
1258         }
1259
1260         /* Set entry points for labels. */
1261         if ( labels.length() > 0 ) {
1262                 /* Pop the names. */
1263                 pd->resetNameScope( nameFrame );
1264
1265                 /* Make labels that are referenced into entry points. */
1266                 for ( int i = 0; i < labels.length(); i++ ) {
1267                         pd->enterNameScope( false, 1 );
1268
1269                         /* Will always be found. */
1270                         NameInst *name = pd->curNameInst;
1271
1272                         /* If the name is referenced then set the entry point. */
1273                         if ( name->numRefs > 0 )
1274                                 rtnVal->setEntry( name->id, rtnVal->startState );
1275                 }
1276
1277                 pd->popNameScope( nameFrame );
1278         }
1279
1280         if ( priorOrd != 0 )
1281                 delete[] priorOrd;
1282         if ( actionOrd != 0 )
1283                 delete[] actionOrd;
1284         return rtnVal;
1285 }
1286
1287 void FactorWithAug::makeNameTree( ParseData *pd )
1288 {
1289         /* Add the labels to the tree of instantiated names. Each label
1290          * makes a new scope. */
1291         NameInst *prevNameInst = pd->curNameInst;
1292         for ( int i = 0; i < labels.length(); i++ )
1293                 pd->curNameInst = pd->addNameInst( labels[i].loc, labels[i].data, true );
1294
1295         /* Recurse, then pop the names. */
1296         factorWithRep->makeNameTree( pd );
1297         pd->curNameInst = prevNameInst;
1298 }
1299
1300
1301 void FactorWithAug::resolveNameRefs( ParseData *pd )
1302 {
1303         /* Enter into the name scope created by any labels. */
1304         NameFrame nameFrame = pd->enterNameScope( false, labels.length() );
1305
1306         /* Note action references. */
1307         for ( int i = 0; i < actions.length(); i++ )
1308                 actions[i].action->actionRefs.append( pd->localNameScope );
1309
1310         /* Recurse first. IMPORTANT: we must do the exact same traversal as when
1311          * the tree is constructed. */
1312         factorWithRep->resolveNameRefs( pd );
1313
1314         /* Resolve epsilon transitions. */
1315         for ( int ep = 0; ep < epsilonLinks.length(); ep++ ) {
1316                 /* Get the link. */
1317                 EpsilonLink &link = epsilonLinks[ep];
1318                 NameInst *resolvedName = 0;
1319
1320                 if ( link.target.length() == 1 && strcmp( link.target.data[0], "final" ) == 0 ) {
1321                         /* Epsilon drawn to an implicit final state. An implicit final is
1322                          * only available in join operations. */
1323                         resolvedName = pd->localNameScope->final;
1324                 }
1325                 else {
1326                         /* Do an search for the name. */
1327                         NameSet resolved;
1328                         pd->resolveFrom( resolved, pd->localNameScope, link.target, 0 );
1329                         if ( resolved.length() > 0 ) {
1330                                 /* Take the first one. */
1331                                 resolvedName = resolved[0];
1332                                 if ( resolved.length() > 1 ) {
1333                                         /* Complain about the multiple references. */
1334                                         error(link.loc) << "state reference " << link.target <<
1335                                                         " resolves to multiple entry points" << endl;
1336                                         errorStateLabels( resolved );
1337                                 }
1338                         }
1339                 }
1340
1341                 /* This is tricky, we stuff resolved epsilon transitions into one long
1342                  * vector in the parse data structure. Since the name resolution and
1343                  * graph generation both do identical walks of the parse tree we
1344                  * should always find the link resolutions in the right place.  */
1345                 pd->epsilonResolvedLinks.append( resolvedName );
1346
1347                 if ( resolvedName != 0 ) {
1348                         /* Found the name, bump of the reference count on it. */
1349                         resolvedName->numRefs += 1;
1350                 }
1351                 else {
1352                         /* Complain, no recovery action, the epsilon op will ignore any
1353                          * epsilon transitions whose names did not resolve. */
1354                         error(link.loc) << "could not resolve label " << link.target << endl;
1355                 }
1356         }
1357
1358         if ( labels.length() > 0 )
1359                 pd->popNameScope( nameFrame );
1360 }
1361
1362
1363 /* Clean up after a factor with repetition node. */
1364 FactorWithRep::~FactorWithRep()
1365 {
1366         switch ( type ) {
1367                 case StarType: case StarStarType: case OptionalType: case PlusType:
1368                 case ExactType: case MaxType: case MinType: case RangeType:
1369                         delete factorWithRep;
1370                         break;
1371                 case FactorWithNegType:
1372                         delete factorWithNeg;
1373                         break;
1374         }
1375 }
1376
1377 /* Evaluate a factor with repetition node. */
1378 FsmAp *FactorWithRep::walk( ParseData *pd )
1379 {
1380         FsmAp *retFsm = 0;
1381
1382         switch ( type ) {
1383         case StarType: {
1384                 /* Evaluate the FactorWithRep. */
1385                 retFsm = factorWithRep->walk( pd );
1386                 if ( retFsm->startState->isFinState() ) {
1387                         warning(loc) << "applying kleene star to a machine that "
1388                                         "accepts zero length word" << endl;
1389                         retFsm->unsetFinState( retFsm->startState );
1390                 }
1391
1392                 /* Shift over the start action orders then do the kleene star. */
1393                 pd->curActionOrd += retFsm->shiftStartActionOrder( pd->curActionOrd );
1394                 retFsm->starOp( );
1395                 afterOpMinimize( retFsm );
1396                 break;
1397         }
1398         case StarStarType: {
1399                 /* Evaluate the FactorWithRep. */
1400                 retFsm = factorWithRep->walk( pd );
1401                 if ( retFsm->startState->isFinState() ) {
1402                         warning(loc) << "applying kleene star to a machine that "
1403                                         "accepts zero length word" << endl;
1404                 }
1405
1406                 /* Set up the prior descs. All gets priority one, whereas leaving gets
1407                  * priority zero. Make a unique key so that these priorities don't
1408                  * interfere with any priorities set by the user. */
1409                 priorDescs[0].key = pd->nextPriorKey++;
1410                 priorDescs[0].priority = 1;
1411                 retFsm->allTransPrior( pd->curPriorOrd++, &priorDescs[0] );
1412
1413                 /* Leaveing gets priority 0. Use same unique key. */
1414                 priorDescs[1].key = priorDescs[0].key;
1415                 priorDescs[1].priority = 0;
1416                 retFsm->leaveFsmPrior( pd->curPriorOrd++, &priorDescs[1] );
1417
1418                 /* Shift over the start action orders then do the kleene star. */
1419                 pd->curActionOrd += retFsm->shiftStartActionOrder( pd->curActionOrd );
1420                 retFsm->starOp( );
1421                 afterOpMinimize( retFsm );
1422                 break;
1423         }
1424         case OptionalType: {
1425                 /* Make the null fsm. */
1426                 FsmAp *nu = new FsmAp();
1427                 nu->lambdaFsm( );
1428
1429                 /* Evaluate the FactorWithRep. */
1430                 retFsm = factorWithRep->walk( pd );
1431
1432                 /* Perform the question operator. */
1433                 retFsm->unionOp( nu );
1434                 afterOpMinimize( retFsm );
1435                 break;
1436         }
1437         case PlusType: {
1438                 /* Evaluate the FactorWithRep. */
1439                 retFsm = factorWithRep->walk( pd );
1440                 if ( retFsm->startState->isFinState() ) {
1441                         warning(loc) << "applying plus operator to a machine that "
1442                                         "accepts zero length word" << endl;
1443                 }
1444
1445                 /* Need a duplicated for the star end. */
1446                 FsmAp *dup = new FsmAp( *retFsm );
1447
1448                 /* The start func orders need to be shifted before doing the star. */
1449                 pd->curActionOrd += dup->shiftStartActionOrder( pd->curActionOrd );
1450
1451                 /* Star the duplicate. */
1452                 dup->starOp( );
1453                 afterOpMinimize( dup );
1454
1455                 retFsm->concatOp( dup );
1456                 afterOpMinimize( retFsm );
1457                 break;
1458         }
1459         case ExactType: {
1460                 /* Get an int from the repetition amount. */
1461                 if ( lowerRep == 0 ) {
1462                         /* No copies. Don't need to evaluate the factorWithRep.
1463                          * This Defeats the purpose so give a warning. */
1464                         warning(loc) << "exactly zero repetitions results "
1465                                         "in the null machine" << endl;
1466
1467                         retFsm = new FsmAp();
1468                         retFsm->lambdaFsm();
1469                 }
1470                 else {
1471                         /* Evaluate the first FactorWithRep. */
1472                         retFsm = factorWithRep->walk( pd );
1473                         if ( retFsm->startState->isFinState() ) {
1474                                 warning(loc) << "applying repetition to a machine that "
1475                                                 "accepts zero length word" << endl;
1476                         }
1477
1478                         /* The start func orders need to be shifted before doing the
1479                          * repetition. */
1480                         pd->curActionOrd += retFsm->shiftStartActionOrder( pd->curActionOrd );
1481
1482                         /* Do the repetition on the machine. Already guarded against n == 0 */
1483                         retFsm->repeatOp( lowerRep );
1484                         afterOpMinimize( retFsm );
1485                 }
1486                 break;
1487         }
1488         case MaxType: {
1489                 /* Get an int from the repetition amount. */
1490                 if ( upperRep == 0 ) {
1491                         /* No copies. Don't need to evaluate the factorWithRep.
1492                          * This Defeats the purpose so give a warning. */
1493                         warning(loc) << "max zero repetitions results "
1494                                         "in the null machine" << endl;
1495
1496                         retFsm = new FsmAp();
1497                         retFsm->lambdaFsm();
1498                 }
1499                 else {
1500                         /* Evaluate the first FactorWithRep. */
1501                         retFsm = factorWithRep->walk( pd );
1502                         if ( retFsm->startState->isFinState() ) {
1503                                 warning(loc) << "applying max repetition to a machine that "
1504                                                 "accepts zero length word" << endl;
1505                         }
1506
1507                         /* The start func orders need to be shifted before doing the
1508                          * repetition. */
1509                         pd->curActionOrd += retFsm->shiftStartActionOrder( pd->curActionOrd );
1510
1511                         /* Do the repetition on the machine. Already guarded against n == 0 */
1512                         retFsm->optionalRepeatOp( upperRep );
1513                         afterOpMinimize( retFsm );
1514                 }
1515                 break;
1516         }
1517         case MinType: {
1518                 /* Evaluate the repeated machine. */
1519                 retFsm = factorWithRep->walk( pd );
1520                 if ( retFsm->startState->isFinState() ) {
1521                         warning(loc) << "applying min repetition to a machine that "
1522                                         "accepts zero length word" << endl;
1523                 }
1524
1525                 /* The start func orders need to be shifted before doing the repetition
1526                  * and the kleene star. */
1527                 pd->curActionOrd += retFsm->shiftStartActionOrder( pd->curActionOrd );
1528
1529                 if ( lowerRep == 0 ) {
1530                         /* Acts just like a star op on the machine to return. */
1531                         retFsm->starOp( );
1532                         afterOpMinimize( retFsm );
1533                 }
1534                 else {
1535                         /* Take a duplicate for the plus. */
1536                         FsmAp *dup = new FsmAp( *retFsm );
1537
1538                         /* Do repetition on the first half. */
1539                         retFsm->repeatOp( lowerRep );
1540                         afterOpMinimize( retFsm );
1541
1542                         /* Star the duplicate. */
1543                         dup->starOp( );
1544                         afterOpMinimize( dup );
1545
1546                         /* Tak on the kleene star. */
1547                         retFsm->concatOp( dup );
1548                         afterOpMinimize( retFsm );
1549                 }
1550                 break;
1551         }
1552         case RangeType: {
1553                 /* Check for bogus range. */
1554                 if ( upperRep - lowerRep < 0 ) {
1555                         error(loc) << "invalid range repetition" << endl;
1556
1557                         /* Return null machine as recovery. */
1558                         retFsm = new FsmAp();
1559                         retFsm->lambdaFsm();
1560                 }
1561                 else if ( lowerRep == 0 && upperRep == 0 ) {
1562                         /* No copies. Don't need to evaluate the factorWithRep.  This
1563                          * defeats the purpose so give a warning. */
1564                         warning(loc) << "zero to zero repetitions results "
1565                                         "in the null machine" << endl;
1566
1567                         retFsm = new FsmAp();
1568                         retFsm->lambdaFsm();
1569                 }
1570                 else {
1571                         /* Now need to evaluate the repeated machine. */
1572                         retFsm = factorWithRep->walk( pd );
1573                         if ( retFsm->startState->isFinState() ) {
1574                                 warning(loc) << "applying range repetition to a machine that "
1575                                                 "accepts zero length word" << endl;
1576                         }
1577
1578                         /* The start func orders need to be shifted before doing both kinds
1579                          * of repetition. */
1580                         pd->curActionOrd += retFsm->shiftStartActionOrder( pd->curActionOrd );
1581
1582                         if ( lowerRep == 0 ) {
1583                                 /* Just doing max repetition. Already guarded against n == 0. */
1584                                 retFsm->optionalRepeatOp( upperRep );
1585                                 afterOpMinimize( retFsm );
1586                         }
1587                         else if ( lowerRep == upperRep ) {
1588                                 /* Just doing exact repetition. Already guarded against n == 0. */
1589                                 retFsm->repeatOp( lowerRep );
1590                                 afterOpMinimize( retFsm );
1591                         }
1592                         else {
1593                                 /* This is the case that 0 < lowerRep < upperRep. Take a
1594                                  * duplicate for the optional repeat. */
1595                                 FsmAp *dup = new FsmAp( *retFsm );
1596
1597                                 /* Do repetition on the first half. */
1598                                 retFsm->repeatOp( lowerRep );
1599                                 afterOpMinimize( retFsm );
1600
1601                                 /* Do optional repetition on the second half. */
1602                                 dup->optionalRepeatOp( upperRep - lowerRep );
1603                                 afterOpMinimize( dup );
1604
1605                                 /* Tak on the duplicate machine. */
1606                                 retFsm->concatOp( dup );
1607                                 afterOpMinimize( retFsm );
1608                         }
1609                 }
1610                 break;
1611         }
1612         case FactorWithNegType: {
1613                 /* Evaluate the Factor. Pass it up. */
1614                 retFsm = factorWithNeg->walk( pd );
1615                 break;
1616         }}
1617         return retFsm;
1618 }
1619
1620 void FactorWithRep::makeNameTree( ParseData *pd )
1621 {
1622         switch ( type ) {
1623         case StarType:
1624         case StarStarType:
1625         case OptionalType:
1626         case PlusType:
1627         case ExactType:
1628         case MaxType:
1629         case MinType:
1630         case RangeType:
1631                 factorWithRep->makeNameTree( pd );
1632                 break;
1633         case FactorWithNegType:
1634                 factorWithNeg->makeNameTree( pd );
1635                 break;
1636         }
1637 }
1638
1639 void FactorWithRep::resolveNameRefs( ParseData *pd )
1640 {
1641         switch ( type ) {
1642         case StarType:
1643         case StarStarType:
1644         case OptionalType:
1645         case PlusType:
1646         case ExactType:
1647         case MaxType:
1648         case MinType:
1649         case RangeType:
1650                 factorWithRep->resolveNameRefs( pd );
1651                 break;
1652         case FactorWithNegType:
1653                 factorWithNeg->resolveNameRefs( pd );
1654                 break;
1655         }
1656 }
1657
1658 /* Clean up after a factor with negation node. */
1659 FactorWithNeg::~FactorWithNeg()
1660 {
1661         switch ( type ) {
1662                 case NegateType:
1663                 case CharNegateType:
1664                         delete factorWithNeg;
1665                         break;
1666                 case FactorType:
1667                         delete factor;
1668                         break;
1669         }
1670 }
1671
1672 /* Evaluate a factor with negation node. */
1673 FsmAp *FactorWithNeg::walk( ParseData *pd )
1674 {
1675         FsmAp *retFsm = 0;
1676
1677         switch ( type ) {
1678         case NegateType: {
1679                 /* Evaluate the factorWithNeg. */
1680                 FsmAp *toNegate = factorWithNeg->walk( pd );
1681
1682                 /* Negation is subtract from dot-star. */
1683                 retFsm = dotStarFsm( pd );
1684                 retFsm->subtractOp( toNegate );
1685                 afterOpMinimize( retFsm );
1686                 break;
1687         }
1688         case CharNegateType: {
1689                 /* Evaluate the factorWithNeg. */
1690                 FsmAp *toNegate = factorWithNeg->walk( pd );
1691
1692                 /* CharNegation is subtract from dot. */
1693                 retFsm = dotFsm( pd );
1694                 retFsm->subtractOp( toNegate );
1695                 afterOpMinimize( retFsm );
1696                 break;
1697         }
1698         case FactorType: {
1699                 /* Evaluate the Factor. Pass it up. */
1700                 retFsm = factor->walk( pd );
1701                 break;
1702         }}
1703         return retFsm;
1704 }
1705
1706 void FactorWithNeg::makeNameTree( ParseData *pd )
1707 {
1708         switch ( type ) {
1709         case NegateType:
1710         case CharNegateType:
1711                 factorWithNeg->makeNameTree( pd );
1712                 break;
1713         case FactorType:
1714                 factor->makeNameTree( pd );
1715                 break;
1716         }
1717 }
1718
1719 void FactorWithNeg::resolveNameRefs( ParseData *pd )
1720 {
1721         switch ( type ) {
1722         case NegateType:
1723         case CharNegateType:
1724                 factorWithNeg->resolveNameRefs( pd );
1725                 break;
1726         case FactorType:
1727                 factor->resolveNameRefs( pd );
1728                 break;
1729         }
1730 }
1731
1732 /* Clean up after a factor node. */
1733 Factor::~Factor()
1734 {
1735         switch ( type ) {
1736                 case LiteralType:
1737                         delete literal;
1738                         break;
1739                 case RangeType:
1740                         delete range;
1741                         break;
1742                 case OrExprType:
1743                         delete reItem;
1744                         break;
1745                 case RegExprType:
1746                         delete regExpr;
1747                         break;
1748                 case ReferenceType:
1749                         break;
1750                 case ParenType:
1751                         delete join;
1752                         break;
1753                 case LongestMatchType:
1754                         delete longestMatch;
1755                         break;
1756         }
1757 }
1758
1759 /* Evaluate a factor node. */
1760 FsmAp *Factor::walk( ParseData *pd )
1761 {
1762         FsmAp *rtnVal = 0;
1763         switch ( type ) {
1764         case LiteralType:
1765                 rtnVal = literal->walk( pd );
1766                 break;
1767         case RangeType:
1768                 rtnVal = range->walk( pd );
1769                 break;
1770         case OrExprType:
1771                 rtnVal = reItem->walk( pd, 0 );
1772                 break;
1773         case RegExprType:
1774                 rtnVal = regExpr->walk( pd, 0 );
1775                 break;
1776         case ReferenceType:
1777                 rtnVal = varDef->walk( pd );
1778                 break;
1779         case ParenType:
1780                 rtnVal = join->walk( pd );
1781                 break;
1782         case LongestMatchType:
1783                 rtnVal = longestMatch->walk( pd );
1784                 break;
1785         }
1786
1787         return rtnVal;
1788 }
1789
1790 void Factor::makeNameTree( ParseData *pd )
1791 {
1792         switch ( type ) {
1793         case LiteralType:
1794         case RangeType:
1795         case OrExprType:
1796         case RegExprType:
1797                 break;
1798         case ReferenceType:
1799                 varDef->makeNameTree( loc, pd );
1800                 break;
1801         case ParenType:
1802                 join->makeNameTree( pd );
1803                 break;
1804         case LongestMatchType:
1805                 longestMatch->makeNameTree( pd );
1806                 break;
1807         }
1808 }
1809
1810 void Factor::resolveNameRefs( ParseData *pd )
1811 {
1812         switch ( type ) {
1813         case LiteralType:
1814         case RangeType:
1815         case OrExprType:
1816         case RegExprType:
1817                 break;
1818         case ReferenceType:
1819                 varDef->resolveNameRefs( pd );
1820                 break;
1821         case ParenType:
1822                 join->resolveNameRefs( pd );
1823                 break;
1824         case LongestMatchType:
1825                 longestMatch->resolveNameRefs( pd );
1826                 break;
1827         }
1828 }
1829
1830 /* Clean up a range object. Must delete the two literals. */
1831 Range::~Range()
1832 {
1833         delete lowerLit;
1834         delete upperLit;
1835 }
1836
1837 /* Evaluate a range. Gets the lower an upper key and makes an fsm range. */
1838 FsmAp *Range::walk( ParseData *pd )
1839 {
1840         /* Construct and verify the suitability of the lower end of the range. */
1841         FsmAp *lowerFsm = lowerLit->walk( pd );
1842         if ( !lowerFsm->checkSingleCharMachine() ) {
1843                 error(lowerLit->token.loc) <<
1844                         "bad range lower end, must be a single character" << endl;
1845         }
1846
1847         /* Construct and verify the upper end. */
1848         FsmAp *upperFsm = upperLit->walk( pd );
1849         if ( !upperFsm->checkSingleCharMachine() ) {
1850                 error(upperLit->token.loc) <<
1851                         "bad range upper end, must be a single character" << endl;
1852         }
1853
1854         /* Grab the keys from the machines, then delete them. */
1855         Key lowKey = lowerFsm->startState->outList.head->lowKey;
1856         Key highKey = upperFsm->startState->outList.head->lowKey;
1857         delete lowerFsm;
1858         delete upperFsm;
1859
1860         /* Validate the range. */
1861         if ( lowKey > highKey ) {
1862                 /* Recover by setting upper to lower; */
1863                 error(lowerLit->token.loc) << "lower end of range is greater then upper end" << endl;
1864                 highKey = lowKey;
1865         }
1866
1867         /* Return the range now that it is validated. */
1868         FsmAp *retFsm = new FsmAp();
1869         retFsm->rangeFsm( lowKey, highKey );
1870         return retFsm;
1871 }
1872
1873 /* Evaluate a literal object. */
1874 FsmAp *Literal::walk( ParseData *pd )
1875 {
1876         /* FsmAp to return, is the alphabet signed. */
1877         FsmAp *rtnVal = 0;
1878
1879         switch ( type ) {
1880         case Number: {
1881                 /* Make the fsm key in int format. */
1882                 Key fsmKey = makeFsmKeyNum( token.data, token.loc, pd );
1883                 /* Make the new machine. */
1884                 rtnVal = new FsmAp();
1885                 rtnVal->concatFsm( fsmKey );
1886                 break;
1887         }
1888         case LitString: {
1889                 /* Make the array of keys in int format. */
1890                 long length;
1891                 bool caseInsensitive;
1892                 char *data = prepareLitString( token.loc, token.data, token.length,
1893                                 length, caseInsensitive );
1894                 Key *arr = new Key[length];
1895                 makeFsmKeyArray( arr, data, length, pd );
1896
1897                 /* Make the new machine. */
1898                 rtnVal = new FsmAp();
1899                 if ( caseInsensitive )
1900                         rtnVal->concatFsmCI( arr, length );
1901                 else
1902                         rtnVal->concatFsm( arr, length );
1903                 delete[] data;
1904                 delete[] arr;
1905                 break;
1906         }}
1907         return rtnVal;
1908 }
1909
1910 /* Clean up after a regular expression object. */
1911 RegExpr::~RegExpr()
1912 {
1913         switch ( type ) {
1914                 case RecurseItem:
1915                         delete regExpr;
1916                         delete item;
1917                         break;
1918                 case Empty:
1919                         break;
1920         }
1921 }
1922
1923 /* Evaluate a regular expression object. */
1924 FsmAp *RegExpr::walk( ParseData *pd, RegExpr *rootRegex )
1925 {
1926         /* This is the root regex, pass down a pointer to this. */
1927         if ( rootRegex == 0 )
1928                 rootRegex = this;
1929
1930         FsmAp *rtnVal = 0;
1931         switch ( type ) {
1932                 case RecurseItem: {
1933                         /* Walk both items. */
1934                         rtnVal = regExpr->walk( pd, rootRegex );
1935                         FsmAp *fsm2 = item->walk( pd, rootRegex );
1936                         rtnVal->concatOp( fsm2 );
1937                         break;
1938                 }
1939                 case Empty: {
1940                         rtnVal = new FsmAp();
1941                         rtnVal->lambdaFsm();
1942                         break;
1943                 }
1944         }
1945         return rtnVal;
1946 }
1947
1948 /* Clean up after an item in a regular expression. */
1949 ReItem::~ReItem()
1950 {
1951         switch ( type ) {
1952                 case Data:
1953                 case Dot:
1954                         break;
1955                 case OrBlock:
1956                 case NegOrBlock:
1957                         delete orBlock;
1958                         break;
1959         }
1960 }
1961
1962 /* Evaluate a regular expression object. */
1963 FsmAp *ReItem::walk( ParseData *pd, RegExpr *rootRegex )
1964 {
1965         /* The fsm to return, is the alphabet signed? */
1966         FsmAp *rtnVal = 0;
1967
1968         switch ( type ) {
1969                 case Data: {
1970                         /* Move the data into an integer array and make a concat fsm. */
1971                         Key *arr = new Key[token.length];
1972                         makeFsmKeyArray( arr, token.data, token.length, pd );
1973
1974                         /* Make the concat fsm. */
1975                         rtnVal = new FsmAp();
1976                         if ( rootRegex != 0 && rootRegex->caseInsensitive )
1977                                 rtnVal->concatFsmCI( arr, token.length );
1978                         else
1979                                 rtnVal->concatFsm( arr, token.length );
1980                         delete[] arr;
1981                         break;
1982                 }
1983                 case Dot: {
1984                         /* Make the dot fsm. */
1985                         rtnVal = dotFsm( pd );
1986                         break;
1987                 }
1988                 case OrBlock: {
1989                         /* Get the or block and minmize it. */
1990                         rtnVal = orBlock->walk( pd, rootRegex );
1991                         if ( rtnVal == 0 ) {
1992                                 rtnVal = new FsmAp();
1993                                 rtnVal->lambdaFsm();
1994                         }
1995                         rtnVal->minimizePartition2();
1996                         break;
1997                 }
1998                 case NegOrBlock: {
1999                         /* Get the or block and minimize it. */
2000                         FsmAp *fsm = orBlock->walk( pd, rootRegex );
2001                         fsm->minimizePartition2();
2002
2003                         /* Make a dot fsm and subtract from it. */
2004                         rtnVal = dotFsm( pd );
2005                         rtnVal->subtractOp( fsm );
2006                         rtnVal->minimizePartition2();
2007                         break;
2008                 }
2009         }
2010
2011         /* If the item is followed by a star, then apply the star op. */
2012         if ( star ) {
2013                 if ( rtnVal->startState->isFinState() ) {
2014                         warning(loc) << "applying kleene star to a machine that "
2015                                         "accepts zero length word" << endl;
2016                 }
2017
2018                 rtnVal->starOp();
2019                 rtnVal->minimizePartition2();
2020         }
2021         return rtnVal;
2022 }
2023
2024 /* Clean up after an or block of a regular expression. */
2025 ReOrBlock::~ReOrBlock()
2026 {
2027         switch ( type ) {
2028                 case RecurseItem:
2029                         delete orBlock;
2030                         delete item;
2031                         break;
2032                 case Empty:
2033                         break;
2034         }
2035 }
2036
2037
2038 /* Evaluate an or block of a regular expression. */
2039 FsmAp *ReOrBlock::walk( ParseData *pd, RegExpr *rootRegex )
2040 {
2041         FsmAp *rtnVal = 0;
2042         switch ( type ) {
2043                 case RecurseItem: {
2044                         /* Evaluate the two fsm. */
2045                         FsmAp *fsm1 = orBlock->walk( pd, rootRegex );
2046                         FsmAp *fsm2 = item->walk( pd, rootRegex );
2047                         if ( fsm1 == 0 )
2048                                 rtnVal = fsm2;
2049                         else {
2050                                 fsm1->unionOp( fsm2 );
2051                                 rtnVal = fsm1;
2052                         }
2053                         break;
2054                 }
2055                 case Empty: {
2056                         rtnVal = 0;
2057                         break;
2058                 }
2059         }
2060         return rtnVal;;
2061 }
2062
2063 /* Evaluate an or block item of a regular expression. */
2064 FsmAp *ReOrItem::walk( ParseData *pd, RegExpr *rootRegex )
2065 {
2066         /* The return value, is the alphabet signed? */
2067         FsmAp *rtnVal = 0;
2068         switch ( type ) {
2069         case Data: {
2070                 /* Make the or machine. */
2071                 rtnVal = new FsmAp();
2072
2073                 /* Put the or data into an array of ints. Note that we find unique
2074                  * keys. Duplicates are silently ignored. The alternative would be to
2075                  * issue warning or an error but since we can't with [a0-9a] or 'a' |
2076                  * 'a' don't bother here. */
2077                 KeySet keySet;
2078                 makeFsmUniqueKeyArray( keySet, token.data, token.length,
2079                         rootRegex != 0 ? rootRegex->caseInsensitive : false, pd );
2080
2081                 /* Run the or operator. */
2082                 rtnVal->orFsm( keySet.data, keySet.length() );
2083                 break;
2084         }
2085         case Range: {
2086                 /* Make the upper and lower keys. */
2087                 Key lowKey = makeFsmKeyChar( lower, pd );
2088                 Key highKey = makeFsmKeyChar( upper, pd );
2089
2090                 /* Validate the range. */
2091                 if ( lowKey > highKey ) {
2092                         /* Recover by setting upper to lower; */
2093                         error(loc) << "lower end of range is greater then upper end" << endl;
2094                         highKey = lowKey;
2095                 }
2096
2097                 /* Make the range machine. */
2098                 rtnVal = new FsmAp();
2099                 rtnVal->rangeFsm( lowKey, highKey );
2100
2101                 if ( rootRegex != 0 && rootRegex->caseInsensitive ) {
2102                         if ( lowKey <= 'Z' && 'A' <= highKey ) {
2103                                 Key otherLow = lowKey < 'A' ? Key('A') : lowKey;
2104                                 Key otherHigh = 'Z' < highKey ? Key('Z') : highKey;
2105
2106                                 otherLow = 'a' + ( otherLow - 'A' );
2107                                 otherHigh = 'a' + ( otherHigh - 'A' );
2108
2109                                 FsmAp *otherRange = new FsmAp();
2110                                 otherRange->rangeFsm( otherLow, otherHigh );
2111                                 rtnVal->unionOp( otherRange );
2112                                 rtnVal->minimizePartition2();
2113                         }
2114                         else if ( lowKey <= 'z' && 'a' <= highKey ) {
2115                                 Key otherLow = lowKey < 'a' ? Key('a') : lowKey;
2116                                 Key otherHigh = 'z' < highKey ? Key('z') : highKey;
2117
2118                                 otherLow = 'A' + ( otherLow - 'a' );
2119                                 otherHigh = 'A' + ( otherHigh - 'a' );
2120
2121                                 FsmAp *otherRange = new FsmAp();
2122                                 otherRange->rangeFsm( otherLow, otherHigh );
2123                                 rtnVal->unionOp( otherRange );
2124                                 rtnVal->minimizePartition2();
2125                         }
2126                 }
2127
2128                 break;
2129         }}
2130         return rtnVal;
2131 }