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