ragel/parsetree.cpp

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