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