/*
* Copyright 2001-2006 Adrian Thurston <thurston@complang.org>
*/
/* This file is part of Ragel.
*
* Ragel is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* Ragel is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with Ragel; if not, write to the Free Software
* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
*/
#include <iostream>
#include <iomanip>
#include <errno.h>
#include <limits.h>
#include <stdlib.h>
/* Parsing. */
#include "ragel.h"
#include "rlparse.h"
#include "parsetree.h"
using namespace std;
ostream &operator<<( ostream &out, const NameRef &nameRef );
ostream &operator<<( ostream &out, const NameInst &nameInst );
/* Convert the literal string which comes in from the scanner into an array of
* characters with escapes and options interpreted. Also null terminates the
* string. Though this null termination should not be relied on for
* interpreting literals in the parser because the string may contain \0 */
char *prepareLitString( const InputLoc &loc, const char *data, long length,
long &resLen, bool &caseInsensitive )
{
char *resData = new char[length+1];
caseInsensitive = false;
const char *src = data + 1;
const char *end = data + length - 1;
while ( *end != '\'' && *end != '\"' ) {
if ( *end == 'i' )
caseInsensitive = true;
else {
error( loc ) << "literal string '" << *end <<
"' option not supported" << endl;
}
end -= 1;
}
char *dest = resData;
long len = 0;
while ( src != end ) {
if ( *src == '\\' ) {
switch ( src[1] ) {
case '0': dest[len++] = '\0'; break;
case 'a': dest[len++] = '\a'; break;
case 'b': dest[len++] = '\b'; break;
case 't': dest[len++] = '\t'; break;
case 'n': dest[len++] = '\n'; break;
case 'v': dest[len++] = '\v'; break;
case 'f': dest[len++] = '\f'; break;
case 'r': dest[len++] = '\r'; break;
case '\n': break;
default: dest[len++] = src[1]; break;
}
src += 2;
}
else {
dest[len++] = *src++;
}
}
resLen = len;
resData[resLen] = 0;
return resData;
}
FsmAp *VarDef::walk( ParseData *pd )
{
/* We enter into a new name scope. */
NameFrame nameFrame = pd->enterNameScope( true, 1 );
/* Recurse on the expression. */
FsmAp *rtnVal = machineDef->walk( pd );
/* Do the tranfer of local error actions. */
LocalErrDictEl *localErrDictEl = pd->localErrDict.find( name );
if ( localErrDictEl != 0 ) {
for ( StateList::Iter state = rtnVal->stateList; state.lte(); state++ )
rtnVal->transferErrorActions( state, localErrDictEl->value );
}
/* If the expression below is a join operation with multiple expressions
* then it just had epsilon transisions resolved. If it is a join
* with only a single expression then run the epsilon op now. */
if ( machineDef->type == MachineDef::JoinType && machineDef->join->exprList.length() == 1 )
rtnVal->epsilonOp();
/* We can now unset entry points that are not longer used. */
pd->unsetObsoleteEntries( rtnVal );
/* If the name of the variable is referenced then add the entry point to
* the graph. */
if ( pd->curNameInst->numRefs > 0 )
rtnVal->setEntry( pd->curNameInst->id, rtnVal->startState );
/* Pop the name scope. */
pd->popNameScope( nameFrame );
return rtnVal;
}
void VarDef::makeNameTree( const InputLoc &loc, ParseData *pd )
{
/* The variable definition enters a new scope. */
NameInst *prevNameInst = pd->curNameInst;
pd->curNameInst = pd->addNameInst( loc, name, false );
if ( machineDef->type == MachineDef::LongestMatchType )
pd->curNameInst->isLongestMatch = true;
/* Recurse. */
machineDef->makeNameTree( pd );
/* The name scope ends, pop the name instantiation. */
pd->curNameInst = prevNameInst;
}
void VarDef::resolveNameRefs( ParseData *pd )
{
/* Entering into a new scope. */
NameFrame nameFrame = pd->enterNameScope( true, 1 );
/* Recurse. */
machineDef->resolveNameRefs( pd );
/* The name scope ends, pop the name instantiation. */
pd->popNameScope( nameFrame );
}
InputLoc LongestMatchPart::getLoc()
{
return action != 0 ? action->loc : semiLoc;
}
/*
* If there are any LMs then all of the following entry points must reset
* tokstart:
*
* 1. fentry(StateRef)
* 2. ftoto(StateRef), fcall(StateRef), fnext(StateRef)
* 3. targt of any transition that has an fcall (the return loc).
* 4. start state of all longest match routines.
*/
Action *LongestMatch::newAction( ParseData *pd, const InputLoc &loc,
const char *name, InlineList *inlineList )
{
Action *action = new Action( loc, name, inlineList, pd->nextCondId++ );
action->actionRefs.append( pd->curNameInst );
pd->actionList.append( action );
action->isLmAction = true;
return action;
}
void LongestMatch::makeActions( ParseData *pd )
{
/* Make actions that set the action id. */
for ( LmPartList::Iter lmi = *longestMatchList; lmi.lte(); lmi++ ) {
/* For each part create actions for setting the match type. We need
* to do this so that the actions will go into the actionIndex. */
InlineList *inlineList = new InlineList;
inlineList->append( new InlineItem( lmi->getLoc(), this, lmi,
InlineItem::LmSetActId ) );
char *actName = new char[50];
sprintf( actName, "store%i", lmi->longestMatchId );
lmi->setActId = newAction( pd, lmi->getLoc(), actName, inlineList );
}
/* Make actions that execute the user action and restart on the last
* character. */
for ( LmPartList::Iter lmi = *longestMatchList; lmi.lte(); lmi++ ) {
/* For each part create actions for setting the match type. We need
* to do this so that the actions will go into the actionIndex. */
InlineList *inlineList = new InlineList;
inlineList->append( new InlineItem( lmi->getLoc(), this, lmi,
InlineItem::LmOnLast ) );
char *actName = new char[50];
sprintf( actName, "last%i", lmi->longestMatchId );
lmi->actOnLast = newAction( pd, lmi->getLoc(), actName, inlineList );
}
/* Make actions that execute the user action and restart on the next
* character. These actions will set tokend themselves (it is the current
* char). */
for ( LmPartList::Iter lmi = *longestMatchList; lmi.lte(); lmi++ ) {
/* For each part create actions for setting the match type. We need
* to do this so that the actions will go into the actionIndex. */
InlineList *inlineList = new InlineList;
inlineList->append( new InlineItem( lmi->getLoc(), this, lmi,
InlineItem::LmOnNext ) );
char *actName = new char[50];
sprintf( actName, "next%i", lmi->longestMatchId );
lmi->actOnNext = newAction( pd, lmi->getLoc(), actName, inlineList );
}
/* Make actions that execute the user action and restart at tokend. These
* actions execute some time after matching the last char. */
for ( LmPartList::Iter lmi = *longestMatchList; lmi.lte(); lmi++ ) {
/* For each part create actions for setting the match type. We need
* to do this so that the actions will go into the actionIndex. */
InlineList *inlineList = new InlineList;
inlineList->append( new InlineItem( lmi->getLoc(), this, lmi,
InlineItem::LmOnLagBehind ) );
char *actName = new char[50];
sprintf( actName, "lag%i", lmi->longestMatchId );
lmi->actLagBehind = newAction( pd, lmi->getLoc(), actName, inlineList );
}
InputLoc loc;
loc.line = 1;
loc.col = 1;
loc.fileName = "NONE";
/* Create the error action. */
InlineList *il6 = new InlineList;
il6->append( new InlineItem( loc, this, 0, InlineItem::LmSwitch ) );
lmActSelect = newAction( pd, loc, "switch", il6 );
}
void LongestMatch::findName( ParseData *pd )
{
NameInst *nameInst = pd->curNameInst;
while ( nameInst->name == 0 ) {
nameInst = nameInst->parent;
/* Since every machine must must have a name, we should always find a
* name for the longest match. */
assert( nameInst != 0 );
}
name = nameInst->name;
}
void LongestMatch::makeNameTree( ParseData *pd )
{
/* Create an anonymous scope for the longest match. Will be used for
* restarting machine after matching a token. */
NameInst *prevNameInst = pd->curNameInst;
pd->curNameInst = pd->addNameInst( loc, 0, false );
/* Recurse into all parts of the longest match operator. */
for ( LmPartList::Iter lmi = *longestMatchList; lmi.lte(); lmi++ )
lmi->join->makeNameTree( pd );
/* Traverse the name tree upwards to find a name for this lm. */
findName( pd );
/* Also make the longest match's actions at this point. */
makeActions( pd );
/* The name scope ends, pop the name instantiation. */
pd->curNameInst = prevNameInst;
}
void LongestMatch::resolveNameRefs( ParseData *pd )
{
/* The longest match gets its own name scope. */
NameFrame nameFrame = pd->enterNameScope( true, 1 );
/* Take an action reference for each longest match item and recurse. */
for ( LmPartList::Iter lmi = *longestMatchList; lmi.lte(); lmi++ ) {
/* Record the reference if the item has an action. */
if ( lmi->action != 0 )
lmi->action->actionRefs.append( pd->localNameScope );
/* Recurse down the join. */
lmi->join->resolveNameRefs( pd );
}
/* The name scope ends, pop the name instantiation. */
pd->popNameScope( nameFrame );
}
void LongestMatch::restart( FsmAp *graph, TransAp *trans )
{
StateAp *fromState = trans->fromState;
graph->detachTrans( fromState, trans->toState, trans );
graph->attachTrans( fromState, graph->startState, trans );
}
void LongestMatch::runLongestMatch( ParseData *pd, FsmAp *graph )
{
graph->markReachableFromHereStopFinal( graph->startState );
for ( StateList::Iter ms = graph->stateList; ms.lte(); ms++ ) {
if ( ms->stateBits & STB_ISMARKED ) {
ms->lmItemSet.insert( 0 );
ms->stateBits &= ~ STB_ISMARKED;
}
}
/* Transfer the first item of non-empty lmAction tables to the item sets
* of the states that follow. Exclude states that have no transitions out.
* This must happen on a separate pass so that on each iteration of the
* next pass we have the item set entries from all lmAction tables. */
for ( StateList::Iter st = graph->stateList; st.lte(); st++ ) {
for ( TransList::Iter trans = st->outList; trans.lte(); trans++ ) {
if ( trans->lmActionTable.length() > 0 ) {
LmActionTableEl *lmAct = trans->lmActionTable.data;
StateAp *toState = trans->toState;
assert( toState );
/* Can only optimize this if there are no transitions out.
* Note there can be out transitions going nowhere with
* actions and they too must inhibit this optimization. */
if ( toState->outList.length() > 0 ) {
/* Fill the item sets. */
graph->markReachableFromHereStopFinal( toState );
for ( StateList::Iter ms = graph->stateList; ms.lte(); ms++ ) {
if ( ms->stateBits & STB_ISMARKED ) {
ms->lmItemSet.insert( lmAct->value );
ms->stateBits &= ~ STB_ISMARKED;
}
}
}
}
}
}
/* The lmItem sets are now filled, telling us which longest match rules
* can succeed in which states. First determine if we need to make sure
* act is defaulted to zero. We need to do this if there are any states
* with lmItemSet.length() > 1 and NULL is included. That is, that the
* switch may get called when in fact nothing has been matched. */
int maxItemSetLength = 0;
graph->markReachableFromHereStopFinal( graph->startState );
for ( StateList::Iter ms = graph->stateList; ms.lte(); ms++ ) {
if ( ms->stateBits & STB_ISMARKED ) {
if ( ms->lmItemSet.length() > maxItemSetLength )
maxItemSetLength = ms->lmItemSet.length();
ms->stateBits &= ~ STB_ISMARKED;
}
}
/* The actions executed on starting to match a token. */
graph->isolateStartState();
graph->startState->toStateActionTable.setAction( pd->initTokStartOrd, pd->initTokStart );
graph->startState->fromStateActionTable.setAction( pd->setTokStartOrd, pd->setTokStart );
if ( maxItemSetLength > 1 ) {
/* The longest match action switch may be called when tokens are
* matched, in which case act must be initialized, there must be a
* case to handle the error, and the generated machine will require an
* error state. */
lmSwitchHandlesError = true;
pd->lmRequiresErrorState = true;
graph->startState->toStateActionTable.setAction( pd->initActIdOrd, pd->initActId );
}
/* The place to store transitions to restart. It maybe possible for the
* restarting to affect the searching through the graph that follows. For
* now take the safe route and save the list of transitions to restart
* until after all searching is done. */
Vector<TransAp*> restartTrans;
/* Set actions that do immediate token recognition, set the longest match part
* id and set the token ending. */
for ( StateList::Iter st = graph->stateList; st.lte(); st++ ) {
for ( TransList::Iter trans = st->outList; trans.lte(); trans++ ) {
if ( trans->lmActionTable.length() > 0 ) {
LmActionTableEl *lmAct = trans->lmActionTable.data;
StateAp *toState = trans->toState;
assert( toState );
/* Can only optimize this if there are no transitions out.
* Note there can be out transitions going nowhere with
* actions and they too must inhibit this optimization. */
if ( toState->outList.length() == 0 ) {
/* Can execute the immediate action for the longest match
* part. Redirect the action to the start state.
*
* NOTE: When we need to inhibit on_last due to leaving
* actions the above test suffices. If the state has out
* actions then it will fail because the out action will
* have been transferred to an error transition, which
* makes the outlist non-empty. */
trans->actionTable.setAction( lmAct->key,
lmAct->value->actOnLast );
restartTrans.append( trans );
}
else {
/* Look for non final states that have a non-empty item
* set. If these are present then we need to record the
* end of the token. Also Find the highest item set
* length reachable from here (excluding at transtions to
* final states). */
bool nonFinalNonEmptyItemSet = false;
maxItemSetLength = 0;
graph->markReachableFromHereStopFinal( toState );
for ( StateList::Iter ms = graph->stateList; ms.lte(); ms++ ) {
if ( ms->stateBits & STB_ISMARKED ) {
if ( ms->lmItemSet.length() > 0 && !ms->isFinState() )
nonFinalNonEmptyItemSet = true;
if ( ms->lmItemSet.length() > maxItemSetLength )
maxItemSetLength = ms->lmItemSet.length();
ms->stateBits &= ~ STB_ISMARKED;
}
}
/* If there are reachable states that are not final and
* have non empty item sets or that have an item set
* length greater than one then we need to set tokend
* because the error action that matches the token will
* require it. */
if ( nonFinalNonEmptyItemSet || maxItemSetLength > 1 )
trans->actionTable.setAction( pd->setTokEndOrd, pd->setTokEnd );
/* Some states may not know which longest match item to
* execute, must set it. */
if ( maxItemSetLength > 1 ) {
/* There are transitions out, another match may come. */
trans->actionTable.setAction( lmAct->key,
lmAct->value->setActId );
}
}
}
}
}
/* Now that all graph searching is done it certainly safe set the
* restarting. It may be safe above, however this must be verified. */
for ( Vector<TransAp*>::Iter pt = restartTrans; pt.lte(); pt++ )
restart( graph, *pt );
int lmErrActionOrd = pd->curActionOrd++;
/* Embed the error for recognizing a char. */
for ( StateList::Iter st = graph->stateList; st.lte(); st++ ) {
if ( st->lmItemSet.length() == 1 && st->lmItemSet[0] != 0 ) {
if ( st->isFinState() ) {
/* On error execute the onActNext action, which knows that
* the last character of the token was one back and restart. */
graph->setErrorTarget( st, graph->startState, &lmErrActionOrd,
&st->lmItemSet[0]->actOnNext, 1 );
st->eofActionTable.setAction( lmErrActionOrd,
st->lmItemSet[0]->actOnNext );
st->eofTarget = graph->startState;
}
else {
graph->setErrorTarget( st, graph->startState, &lmErrActionOrd,
&st->lmItemSet[0]->actLagBehind, 1 );
st->eofActionTable.setAction( lmErrActionOrd,
st->lmItemSet[0]->actLagBehind );
st->eofTarget = graph->startState;
}
}
else if ( st->lmItemSet.length() > 1 ) {
/* Need to use the select. Take note of which items the select
* is needed for so only the necessary actions are included. */
for ( LmItemSet::Iter plmi = st->lmItemSet; plmi.lte(); plmi++ ) {
if ( *plmi != 0 )
(*plmi)->inLmSelect = true;
}
/* On error, execute the action select and go to the start state. */
graph->setErrorTarget( st, graph->startState, &lmErrActionOrd,
&lmActSelect, 1 );
st->eofActionTable.setAction( lmErrActionOrd, lmActSelect );
st->eofTarget = graph->startState;
}
}
/* Finally, the start state should be made final. */
graph->setFinState( graph->startState );
}
void LongestMatch::transferScannerLeavingActions( FsmAp *graph )
{
for ( StateList::Iter st = graph->stateList; st.lte(); st++ ) {
if ( st->outActionTable.length() > 0 )
graph->setErrorActions( st, st->outActionTable );
}
}
FsmAp *LongestMatch::walk( ParseData *pd )
{
/* The longest match has it's own name scope. */
NameFrame nameFrame = pd->enterNameScope( true, 1 );
/* Make each part of the longest match. */
FsmAp **parts = new FsmAp*[longestMatchList->length()];
LmPartList::Iter lmi = *longestMatchList;
for ( int i = 0; lmi.lte(); lmi++, i++ ) {
/* Create the machine and embed the setting of the longest match id. */
parts[i] = lmi->join->walk( pd );
parts[i]->longMatchAction( pd->curActionOrd++, lmi );
}
/* Before we union the patterns we need to deal with leaving actions. They
* are transfered to error transitions out of the final states (like local
* error actions) and to eof actions. In the scanner we need to forbid
* on_last for any final state that has an leaving action. */
for ( int i = 0; i < longestMatchList->length(); i++ )
transferScannerLeavingActions( parts[i] );
/* Union machines one and up with machine zero. The grammar dictates that
* there will always be at least one part. */
FsmAp *rtnVal = parts[0];
for ( int i = 1; i < longestMatchList->length(); i++ ) {
rtnVal->unionOp( parts[i] );
afterOpMinimize( rtnVal );
}
runLongestMatch( pd, rtnVal );
/* Pop the name scope. */
pd->popNameScope( nameFrame );
delete[] parts;
return rtnVal;
}
FsmAp *MachineDef::walk( ParseData *pd )
{
FsmAp *rtnVal = 0;
switch ( type ) {
case JoinType:
rtnVal = join->walk( pd );
break;
case LongestMatchType:
rtnVal = longestMatch->walk( pd );
break;
case LengthDefType:
condData->lastCondKey.increment();
rtnVal = new FsmAp();
rtnVal->concatFsm( condData->lastCondKey );
break;
}
return rtnVal;
}
void MachineDef::makeNameTree( ParseData *pd )
{
switch ( type ) {
case JoinType:
join->makeNameTree( pd );
break;
case LongestMatchType:
longestMatch->makeNameTree( pd );
break;
case LengthDefType:
break;
}
}
void MachineDef::resolveNameRefs( ParseData *pd )
{
switch ( type ) {
case JoinType:
join->resolveNameRefs( pd );
break;
case LongestMatchType:
longestMatch->resolveNameRefs( pd );
break;
case LengthDefType:
break;
}
}
/* Construct with a location and the first expression. */
Join::Join( const InputLoc &loc, Expression *expr )
:
loc(loc)
{
exprList.append( expr );
}
/* Construct with a location and the first expression. */
Join::Join( Expression *expr )
{
exprList.append( expr );
}
/* Walk an expression node. */
FsmAp *Join::walk( ParseData *pd )
{
if ( exprList.length() > 1 )
return walkJoin( pd );
else
return exprList.head->walk( pd );
}
/* There is a list of expressions to join. */
FsmAp *Join::walkJoin( ParseData *pd )
{
/* We enter into a new name scope. */
NameFrame nameFrame = pd->enterNameScope( true, 1 );
/* Evaluate the machines. */
FsmAp **fsms = new FsmAp*[exprList.length()];
ExprList::Iter expr = exprList;
for ( int e = 0; e < exprList.length(); e++, expr++ )
fsms[e] = expr->walk( pd );
/* Get the start and final names. Final is
* guaranteed to exist, start is not. */
NameInst *startName = pd->curNameInst->start;
NameInst *finalName = pd->curNameInst->final;
int startId = -1;
if ( startName != 0 ) {
/* Take note that there was an implicit link to the start machine. */
pd->localNameScope->referencedNames.append( startName );
startId = startName->id;
}
/* A final id of -1 indicates there is no epsilon that references the
* final state, therefor do not create one or set an entry point to it. */
int finalId = -1;
if ( finalName->numRefs > 0 )
finalId = finalName->id;
/* Join machines 1 and up onto machine 0. */
FsmAp *retFsm = fsms[0];
retFsm->joinOp( startId, finalId, fsms+1, exprList.length()-1 );
/* We can now unset entry points that are not longer used. */
pd->unsetObsoleteEntries( retFsm );
/* Pop the name scope. */
pd->popNameScope( nameFrame );
delete[] fsms;
return retFsm;
}
void Join::makeNameTree( ParseData *pd )
{
if ( exprList.length() > 1 ) {
/* Create the new anonymous scope. */
NameInst *prevNameInst = pd->curNameInst;
pd->curNameInst = pd->addNameInst( loc, 0, false );
/* Join scopes need an implicit "final" target. */
pd->curNameInst->final = new NameInst( InputLoc(), pd->curNameInst, "final",
pd->nextNameId++, false );
/* Recurse into all expressions in the list. */
for ( ExprList::Iter expr = exprList; expr.lte(); expr++ )
expr->makeNameTree( pd );
/* The name scope ends, pop the name instantiation. */
pd->curNameInst = prevNameInst;
}
else {
/* Recurse into the single expression. */
exprList.head->makeNameTree( pd );
}
}
void Join::resolveNameRefs( ParseData *pd )
{
/* Branch on whether or not there is to be a join. */
if ( exprList.length() > 1 ) {
/* The variable definition enters a new scope. */
NameFrame nameFrame = pd->enterNameScope( true, 1 );
/* The join scope must contain a start label. */
NameSet resolved = pd->resolvePart( pd->localNameScope, "start", true );
if ( resolved.length() > 0 ) {
/* Take the first. */
pd->curNameInst->start = resolved[0];
if ( resolved.length() > 1 ) {
/* Complain about the multiple references. */
error(loc) << "join operation has multiple start labels" << endl;
errorStateLabels( resolved );
}
}
/* Make sure there is a start label. */
if ( pd->curNameInst->start != 0 ) {
/* There is an implicit reference to start name. */
pd->curNameInst->start->numRefs += 1;
}
else {
/* No start label. */
error(loc) << "join operation has no start label" << endl;
}
/* Recurse into all expressions in the list. */
for ( ExprList::Iter expr = exprList; expr.lte(); expr++ )
expr->resolveNameRefs( pd );
/* The name scope ends, pop the name instantiation. */
pd->popNameScope( nameFrame );
}
else {
/* Recurse into the single expression. */
exprList.head->resolveNameRefs( pd );
}
}
/* Clean up after an expression node. */
Expression::~Expression()
{
switch ( type ) {
case OrType: case IntersectType: case SubtractType:
case StrongSubtractType:
delete expression;
delete term;
break;
case TermType:
delete term;
break;
case BuiltinType:
break;
}
}
/* Evaluate a single expression node. */
FsmAp *Expression::walk( ParseData *pd, bool lastInSeq )
{
FsmAp *rtnVal = 0;
switch ( type ) {
case OrType: {
/* Evaluate the expression. */
rtnVal = expression->walk( pd, false );
/* Evaluate the term. */
FsmAp *rhs = term->walk( pd );
/* Perform union. */
rtnVal->unionOp( rhs );
afterOpMinimize( rtnVal, lastInSeq );
break;
}
case IntersectType: {
/* Evaluate the expression. */
rtnVal = expression->walk( pd );
/* Evaluate the term. */
FsmAp *rhs = term->walk( pd );
/* Perform intersection. */
rtnVal->intersectOp( rhs );
afterOpMinimize( rtnVal, lastInSeq );
break;
}
case SubtractType: {
/* Evaluate the expression. */
rtnVal = expression->walk( pd );
/* Evaluate the term. */
FsmAp *rhs = term->walk( pd );
/* Perform subtraction. */
rtnVal->subtractOp( rhs );
afterOpMinimize( rtnVal, lastInSeq );
break;
}
case StrongSubtractType: {
/* Evaluate the expression. */
rtnVal = expression->walk( pd );
/* Evaluate the term and pad it with any* machines. */
FsmAp *rhs = dotStarFsm( pd );
FsmAp *termFsm = term->walk( pd );
FsmAp *trailAnyStar = dotStarFsm( pd );
rhs->concatOp( termFsm );
rhs->concatOp( trailAnyStar );
/* Perform subtraction. */
rtnVal->subtractOp( rhs );
afterOpMinimize( rtnVal, lastInSeq );
break;
}
case TermType: {
/* Return result of the term. */
rtnVal = term->walk( pd );
break;
}
case BuiltinType: {
/* Duplicate the builtin. */
rtnVal = makeBuiltin( builtin, pd );
break;
}
}
return rtnVal;
}
void Expression::makeNameTree( ParseData *pd )
{
switch ( type ) {
case OrType:
case IntersectType:
case SubtractType:
case StrongSubtractType:
expression->makeNameTree( pd );
term->makeNameTree( pd );
break;
case TermType:
term->makeNameTree( pd );
break;
case BuiltinType:
break;
}
}
void Expression::resolveNameRefs( ParseData *pd )
{
switch ( type ) {
case OrType:
case IntersectType:
case SubtractType:
case StrongSubtractType:
expression->resolveNameRefs( pd );
term->resolveNameRefs( pd );
break;
case TermType:
term->resolveNameRefs( pd );
break;
case BuiltinType:
break;
}
}
/* Clean up after a term node. */
Term::~Term()
{
switch ( type ) {
case ConcatType:
case RightStartType:
case RightFinishType:
case LeftType:
delete term;
delete factorWithAug;
break;
case FactorWithAugType:
delete factorWithAug;
break;
}
}
/* Evaluate a term node. */
FsmAp *Term::walk( ParseData *pd, bool lastInSeq )
{
FsmAp *rtnVal = 0;
switch ( type ) {
case ConcatType: {
/* Evaluate the Term. */
rtnVal = term->walk( pd, false );
/* Evaluate the FactorWithRep. */
FsmAp *rhs = factorWithAug->walk( pd );
/* Perform concatenation. */
rtnVal->concatOp( rhs );
afterOpMinimize( rtnVal, lastInSeq );
break;
}
case RightStartType: {
/* Evaluate the Term. */
rtnVal = term->walk( pd );
/* Evaluate the FactorWithRep. */
FsmAp *rhs = factorWithAug->walk( pd );
/* Set up the priority descriptors. The left machine gets the
* lower priority where as the right get the higher start priority. */
priorDescs[0].key = pd->nextPriorKey++;
priorDescs[0].priority = 0;
rtnVal->allTransPrior( pd->curPriorOrd++, &priorDescs[0] );
/* The start transitions of the right machine gets the higher
* priority. Use the same unique key. */
priorDescs[1].key = priorDescs[0].key;
priorDescs[1].priority = 1;
rhs->startFsmPrior( pd->curPriorOrd++, &priorDescs[1] );
/* Perform concatenation. */
rtnVal->concatOp( rhs );
afterOpMinimize( rtnVal, lastInSeq );
break;
}
case RightFinishType: {
/* Evaluate the Term. */
rtnVal = term->walk( pd );
/* Evaluate the FactorWithRep. */
FsmAp *rhs = factorWithAug->walk( pd );
/* Set up the priority descriptors. The left machine gets the
* lower priority where as the finishing transitions to the right
* get the higher priority. */
priorDescs[0].key = pd->nextPriorKey++;
priorDescs[0].priority = 0;
rtnVal->allTransPrior( pd->curPriorOrd++, &priorDescs[0] );
/* The finishing transitions of the right machine get the higher
* priority. Use the same unique key. */
priorDescs[1].key = priorDescs[0].key;
priorDescs[1].priority = 1;
rhs->finishFsmPrior( pd->curPriorOrd++, &priorDescs[1] );
/* If the right machine's start state is final we need to guard
* against the left machine persisting by moving through the empty
* string. */
if ( rhs->startState->isFinState() ) {
rhs->startState->outPriorTable.setPrior(
pd->curPriorOrd++, &priorDescs[1] );
}
/* Perform concatenation. */
rtnVal->concatOp( rhs );
afterOpMinimize( rtnVal, lastInSeq );
break;
}
case LeftType: {
/* Evaluate the Term. */
rtnVal = term->walk( pd );
/* Evaluate the FactorWithRep. */
FsmAp *rhs = factorWithAug->walk( pd );
/* Set up the priority descriptors. The left machine gets the
* higher priority. */
priorDescs[0].key = pd->nextPriorKey++;
priorDescs[0].priority = 1;
rtnVal->allTransPrior( pd->curPriorOrd++, &priorDescs[0] );
/* The right machine gets the lower priority. We cannot use
* allTransPrior here in case the start state of the right machine
* is final. It would allow the right machine thread to run along
* with the left if just passing through the start state. Using
* startFsmPrior prevents this. */
priorDescs[1].key = priorDescs[0].key;
priorDescs[1].priority = 0;
rhs->startFsmPrior( pd->curPriorOrd++, &priorDescs[1] );
/* Perform concatenation. */
rtnVal->concatOp( rhs );
afterOpMinimize( rtnVal, lastInSeq );
break;
}
case FactorWithAugType: {
rtnVal = factorWithAug->walk( pd );
break;
}
}
return rtnVal;
}
void Term::makeNameTree( ParseData *pd )
{
switch ( type ) {
case ConcatType:
case RightStartType:
case RightFinishType:
case LeftType:
term->makeNameTree( pd );
factorWithAug->makeNameTree( pd );
break;
case FactorWithAugType:
factorWithAug->makeNameTree( pd );
break;
}
}
void Term::resolveNameRefs( ParseData *pd )
{
switch ( type ) {
case ConcatType:
case RightStartType:
case RightFinishType:
case LeftType:
term->resolveNameRefs( pd );
factorWithAug->resolveNameRefs( pd );
break;
case FactorWithAugType:
factorWithAug->resolveNameRefs( pd );
break;
}
}
/* Clean up after a factor with augmentation node. */
FactorWithAug::~FactorWithAug()
{
delete factorWithRep;
/* Walk the vector of parser actions, deleting function names. */
/* Clean up priority descriptors. */
if ( priorDescs != 0 )
delete[] priorDescs;
}
void FactorWithAug::assignActions( ParseData *pd, FsmAp *graph, int *actionOrd )
{
/* Assign actions. */
for ( int i = 0; i < actions.length(); i++ ) {
switch ( actions[i].type ) {
/* Transition actions. */
case at_start:
graph->startFsmAction( actionOrd[i], actions[i].action );
afterOpMinimize( graph );
break;
case at_all:
graph->allTransAction( actionOrd[i], actions[i].action );
break;
case at_finish:
graph->finishFsmAction( actionOrd[i], actions[i].action );
break;
case at_leave:
graph->leaveFsmAction( actionOrd[i], actions[i].action );
break;
/* Global error actions. */
case at_start_gbl_error:
graph->startErrorAction( actionOrd[i], actions[i].action, 0 );
afterOpMinimize( graph );
break;
case at_all_gbl_error:
graph->allErrorAction( actionOrd[i], actions[i].action, 0 );
break;
case at_final_gbl_error:
graph->finalErrorAction( actionOrd[i], actions[i].action, 0 );
break;
case at_not_start_gbl_error:
graph->notStartErrorAction( actionOrd[i], actions[i].action, 0 );
break;
case at_not_final_gbl_error:
graph->notFinalErrorAction( actionOrd[i], actions[i].action, 0 );
break;
case at_middle_gbl_error:
graph->middleErrorAction( actionOrd[i], actions[i].action, 0 );
break;
/* Local error actions. */
case at_start_local_error:
graph->startErrorAction( actionOrd[i], actions[i].action,
actions[i].localErrKey );
afterOpMinimize( graph );
break;
case at_all_local_error:
graph->allErrorAction( actionOrd[i], actions[i].action,
actions[i].localErrKey );
break;
case at_final_local_error:
graph->finalErrorAction( actionOrd[i], actions[i].action,
actions[i].localErrKey );
break;
case at_not_start_local_error:
graph->notStartErrorAction( actionOrd[i], actions[i].action,
actions[i].localErrKey );
break;
case at_not_final_local_error:
graph->notFinalErrorAction( actionOrd[i], actions[i].action,
actions[i].localErrKey );
break;
case at_middle_local_error:
graph->middleErrorAction( actionOrd[i], actions[i].action,
actions[i].localErrKey );
break;
/* EOF actions. */
case at_start_eof:
graph->startEOFAction( actionOrd[i], actions[i].action );
afterOpMinimize( graph );
break;
case at_all_eof:
graph->allEOFAction( actionOrd[i], actions[i].action );
break;
case at_final_eof:
graph->finalEOFAction( actionOrd[i], actions[i].action );
break;
case at_not_start_eof:
graph->notStartEOFAction( actionOrd[i], actions[i].action );
break;
case at_not_final_eof:
graph->notFinalEOFAction( actionOrd[i], actions[i].action );
break;
case at_middle_eof:
graph->middleEOFAction( actionOrd[i], actions[i].action );
break;
/* To State Actions. */
case at_start_to_state:
graph->startToStateAction( actionOrd[i], actions[i].action );
afterOpMinimize( graph );
break;
case at_all_to_state:
graph->allToStateAction( actionOrd[i], actions[i].action );
break;
case at_final_to_state:
graph->finalToStateAction( actionOrd[i], actions[i].action );
break;
case at_not_start_to_state:
graph->notStartToStateAction( actionOrd[i], actions[i].action );
break;
case at_not_final_to_state:
graph->notFinalToStateAction( actionOrd[i], actions[i].action );
break;
case at_middle_to_state:
graph->middleToStateAction( actionOrd[i], actions[i].action );
break;
/* From State Actions. */
case at_start_from_state:
graph->startFromStateAction( actionOrd[i], actions[i].action );
afterOpMinimize( graph );
break;
case at_all_from_state:
graph->allFromStateAction( actionOrd[i], actions[i].action );
break;
case at_final_from_state:
graph->finalFromStateAction( actionOrd[i], actions[i].action );
break;
case at_not_start_from_state:
graph->notStartFromStateAction( actionOrd[i], actions[i].action );
break;
case at_not_final_from_state:
graph->notFinalFromStateAction( actionOrd[i], actions[i].action );
break;
case at_middle_from_state:
graph->middleFromStateAction( actionOrd[i], actions[i].action );
break;
/* Remaining cases, prevented by the parser. */
default:
assert( false );
break;
}
}
}
void FactorWithAug::assignPriorities( FsmAp *graph, int *priorOrd )
{
/* Assign priorities. */
for ( int i = 0; i < priorityAugs.length(); i++ ) {
switch ( priorityAugs[i].type ) {
case at_start:
graph->startFsmPrior( priorOrd[i], &priorDescs[i]);
/* Start fsm priorities are a special case that may require
* minimization afterwards. */
afterOpMinimize( graph );
break;
case at_all:
graph->allTransPrior( priorOrd[i], &priorDescs[i] );
break;
case at_finish:
graph->finishFsmPrior( priorOrd[i], &priorDescs[i] );
break;
case at_leave:
graph->leaveFsmPrior( priorOrd[i], &priorDescs[i] );
break;
default:
/* Parser Prevents this case. */
break;
}
}
}
void FactorWithAug::assignConditions( FsmAp *graph )
{
for ( int i = 0; i < conditions.length(); i++ ) {
switch ( conditions[i].type ) {
/* Transition actions. */
case at_start:
graph->startFsmCondition( conditions[i].action, conditions[i].sense );
afterOpMinimize( graph );
break;
case at_all:
graph->allTransCondition( conditions[i].action, conditions[i].sense );
break;
case at_leave:
graph->leaveFsmCondition( conditions[i].action, conditions[i].sense );
break;
default:
break;
}
}
}
/* Evaluate a factor with augmentation node. */
FsmAp *FactorWithAug::walk( ParseData *pd )
{
/* Enter into the scopes created for the labels. */
NameFrame nameFrame = pd->enterNameScope( false, labels.length() );
/* Make the array of function orderings. */
int *actionOrd = 0;
if ( actions.length() > 0 )
actionOrd = new int[actions.length()];
/* First walk the list of actions, assigning order to all starting
* actions. */
for ( int i = 0; i < actions.length(); i++ ) {
if ( actions[i].type == at_start ||
actions[i].type == at_start_gbl_error ||
actions[i].type == at_start_local_error ||
actions[i].type == at_start_to_state ||
actions[i].type == at_start_from_state ||
actions[i].type == at_start_eof )
actionOrd[i] = pd->curActionOrd++;
}
/* Evaluate the factor with repetition. */
FsmAp *rtnVal = factorWithRep->walk( pd );
/* Compute the remaining action orderings. */
for ( int i = 0; i < actions.length(); i++ ) {
if ( actions[i].type != at_start &&
actions[i].type != at_start_gbl_error &&
actions[i].type != at_start_local_error &&
actions[i].type != at_start_to_state &&
actions[i].type != at_start_from_state &&
actions[i].type != at_start_eof )
actionOrd[i] = pd->curActionOrd++;
}
/* Embed conditions. */
assignConditions( rtnVal );
/* Embed actions. */
assignActions( pd, rtnVal , actionOrd );
/* Make the array of priority orderings. Orderings are local to this walk
* of the factor with augmentation. */
int *priorOrd = 0;
if ( priorityAugs.length() > 0 )
priorOrd = new int[priorityAugs.length()];
/* Walk all priorities, assigning the priority ordering. */
for ( int i = 0; i < priorityAugs.length(); i++ )
priorOrd[i] = pd->curPriorOrd++;
/* If the priority descriptors have not been made, make them now. Make
* priority descriptors for each priority asignment that will be passed to
* the fsm. Used to keep track of the key, value and used bit. */
if ( priorDescs == 0 && priorityAugs.length() > 0 ) {
priorDescs = new PriorDesc[priorityAugs.length()];
for ( int i = 0; i < priorityAugs.length(); i++ ) {
/* Init the prior descriptor for the priority setting. */
priorDescs[i].key = priorityAugs[i].priorKey;
priorDescs[i].priority = priorityAugs[i].priorValue;
}
}
/* Assign priorities into the machine. */
assignPriorities( rtnVal, priorOrd );
/* Assign epsilon transitions. */
for ( int e = 0; e < epsilonLinks.length(); e++ ) {
/* Get the name, which may not exist. If it doesn't then silently
* ignore it because an error has already been reported. */
NameInst *epTarg = pd->epsilonResolvedLinks[pd->nextEpsilonResolvedLink++];
if ( epTarg != 0 ) {
/* Make the epsilon transitions. */
rtnVal->epsilonTrans( epTarg->id );
/* Note that we have made a link to the name. */
pd->localNameScope->referencedNames.append( epTarg );
}
}
/* Set entry points for labels. */
if ( labels.length() > 0 ) {
/* Pop the names. */
pd->resetNameScope( nameFrame );
/* Make labels that are referenced into entry points. */
for ( int i = 0; i < labels.length(); i++ ) {
pd->enterNameScope( false, 1 );
/* Will always be found. */
NameInst *name = pd->curNameInst;
/* If the name is referenced then set the entry point. */
if ( name->numRefs > 0 )
rtnVal->setEntry( name->id, rtnVal->startState );
}
pd->popNameScope( nameFrame );
}
if ( priorOrd != 0 )
delete[] priorOrd;
if ( actionOrd != 0 )
delete[] actionOrd;
return rtnVal;
}
void FactorWithAug::makeNameTree( ParseData *pd )
{
/* Add the labels to the tree of instantiated names. Each label
* makes a new scope. */
NameInst *prevNameInst = pd->curNameInst;
for ( int i = 0; i < labels.length(); i++ )
pd->curNameInst = pd->addNameInst( labels[i].loc, labels[i].data, true );
/* Recurse, then pop the names. */
factorWithRep->makeNameTree( pd );
pd->curNameInst = prevNameInst;
}
void FactorWithAug::resolveNameRefs( ParseData *pd )
{
/* Enter into the name scope created by any labels. */
NameFrame nameFrame = pd->enterNameScope( false, labels.length() );
/* Note action references. */
for ( int i = 0; i < actions.length(); i++ )
actions[i].action->actionRefs.append( pd->localNameScope );
/* Recurse first. IMPORTANT: we must do the exact same traversal as when
* the tree is constructed. */
factorWithRep->resolveNameRefs( pd );
/* Resolve epsilon transitions. */
for ( int ep = 0; ep < epsilonLinks.length(); ep++ ) {
/* Get the link. */
EpsilonLink &link = epsilonLinks[ep];
NameInst *resolvedName = 0;
if ( link.target.length() == 1 && strcmp( link.target.data[0], "final" ) == 0 ) {
/* Epsilon drawn to an implicit final state. An implicit final is
* only available in join operations. */
resolvedName = pd->localNameScope->final;
}
else {
/* Do an search for the name. */
NameSet resolved;
pd->resolveFrom( resolved, pd->localNameScope, link.target, 0 );
if ( resolved.length() > 0 ) {
/* Take the first one. */
resolvedName = resolved[0];
if ( resolved.length() > 1 ) {
/* Complain about the multiple references. */
error(link.loc) << "state reference " << link.target <<
" resolves to multiple entry points" << endl;
errorStateLabels( resolved );
}
}
}
/* This is tricky, we stuff resolved epsilon transitions into one long
* vector in the parse data structure. Since the name resolution and
* graph generation both do identical walks of the parse tree we
* should always find the link resolutions in the right place. */
pd->epsilonResolvedLinks.append( resolvedName );
if ( resolvedName != 0 ) {
/* Found the name, bump of the reference count on it. */
resolvedName->numRefs += 1;
}
else {
/* Complain, no recovery action, the epsilon op will ignore any
* epsilon transitions whose names did not resolve. */
error(link.loc) << "could not resolve label " << link.target << endl;
}
}
if ( labels.length() > 0 )
pd->popNameScope( nameFrame );
}
/* Clean up after a factor with repetition node. */
FactorWithRep::~FactorWithRep()
{
switch ( type ) {
case StarType: case StarStarType: case OptionalType: case PlusType:
case ExactType: case MaxType: case MinType: case RangeType:
delete factorWithRep;
break;
case FactorWithNegType:
delete factorWithNeg;
break;
}
}
/* Evaluate a factor with repetition node. */
FsmAp *FactorWithRep::walk( ParseData *pd )
{
FsmAp *retFsm = 0;
switch ( type ) {
case StarType: {
/* Evaluate the FactorWithRep. */
retFsm = factorWithRep->walk( pd );
if ( retFsm->startState->isFinState() ) {
warning(loc) << "applying kleene star to a machine that "
"accepts zero length word" << endl;
retFsm->unsetFinState( retFsm->startState );
}
/* Shift over the start action orders then do the kleene star. */
pd->curActionOrd += retFsm->shiftStartActionOrder( pd->curActionOrd );
retFsm->starOp( );
afterOpMinimize( retFsm );
break;
}
case StarStarType: {
/* Evaluate the FactorWithRep. */
retFsm = factorWithRep->walk( pd );
if ( retFsm->startState->isFinState() ) {
warning(loc) << "applying kleene star to a machine that "
"accepts zero length word" << endl;
}
/* Set up the prior descs. All gets priority one, whereas leaving gets
* priority zero. Make a unique key so that these priorities don't
* interfere with any priorities set by the user. */
priorDescs[0].key = pd->nextPriorKey++;
priorDescs[0].priority = 1;
retFsm->allTransPrior( pd->curPriorOrd++, &priorDescs[0] );
/* Leaveing gets priority 0. Use same unique key. */
priorDescs[1].key = priorDescs[0].key;
priorDescs[1].priority = 0;
retFsm->leaveFsmPrior( pd->curPriorOrd++, &priorDescs[1] );
/* Shift over the start action orders then do the kleene star. */
pd->curActionOrd += retFsm->shiftStartActionOrder( pd->curActionOrd );
retFsm->starOp( );
afterOpMinimize( retFsm );
break;
}
case OptionalType: {
/* Make the null fsm. */
FsmAp *nu = new FsmAp();
nu->lambdaFsm( );
/* Evaluate the FactorWithRep. */
retFsm = factorWithRep->walk( pd );
/* Perform the question operator. */
retFsm->unionOp( nu );
afterOpMinimize( retFsm );
break;
}
case PlusType: {
/* Evaluate the FactorWithRep. */
retFsm = factorWithRep->walk( pd );
if ( retFsm->startState->isFinState() ) {
warning(loc) << "applying plus operator to a machine that "
"accepts zero length word" << endl;
}
/* Need a duplicated for the star end. */
FsmAp *dup = new FsmAp( *retFsm );
/* The start func orders need to be shifted before doing the star. */
pd->curActionOrd += dup->shiftStartActionOrder( pd->curActionOrd );
/* Star the duplicate. */
dup->starOp( );
afterOpMinimize( dup );
retFsm->concatOp( dup );
afterOpMinimize( retFsm );
break;
}
case ExactType: {
/* Get an int from the repetition amount. */
if ( lowerRep == 0 ) {
/* No copies. Don't need to evaluate the factorWithRep.
* This Defeats the purpose so give a warning. */
warning(loc) << "exactly zero repetitions results "
"in the null machine" << endl;
retFsm = new FsmAp();
retFsm->lambdaFsm();
}
else {
/* Evaluate the first FactorWithRep. */
retFsm = factorWithRep->walk( pd );
if ( retFsm->startState->isFinState() ) {
warning(loc) << "applying repetition to a machine that "
"accepts zero length word" << endl;
}
/* The start func orders need to be shifted before doing the
* repetition. */
pd->curActionOrd += retFsm->shiftStartActionOrder( pd->curActionOrd );
/* Do the repetition on the machine. Already guarded against n == 0 */
retFsm->repeatOp( lowerRep );
afterOpMinimize( retFsm );
}
break;
}
case MaxType: {
/* Get an int from the repetition amount. */
if ( upperRep == 0 ) {
/* No copies. Don't need to evaluate the factorWithRep.
* This Defeats the purpose so give a warning. */
warning(loc) << "max zero repetitions results "
"in the null machine" << endl;
retFsm = new FsmAp();
retFsm->lambdaFsm();
}
else {
/* Evaluate the first FactorWithRep. */
retFsm = factorWithRep->walk( pd );
if ( retFsm->startState->isFinState() ) {
warning(loc) << "applying max repetition to a machine that "
"accepts zero length word" << endl;
}
/* The start func orders need to be shifted before doing the
* repetition. */
pd->curActionOrd += retFsm->shiftStartActionOrder( pd->curActionOrd );
/* Do the repetition on the machine. Already guarded against n == 0 */
retFsm->optionalRepeatOp( upperRep );
afterOpMinimize( retFsm );
}
break;
}
case MinType: {
/* Evaluate the repeated machine. */
retFsm = factorWithRep->walk( pd );
if ( retFsm->startState->isFinState() ) {
warning(loc) << "applying min repetition to a machine that "
"accepts zero length word" << endl;
}
/* The start func orders need to be shifted before doing the repetition
* and the kleene star. */
pd->curActionOrd += retFsm->shiftStartActionOrder( pd->curActionOrd );
if ( lowerRep == 0 ) {
/* Acts just like a star op on the machine to return. */
retFsm->starOp( );
afterOpMinimize( retFsm );
}
else {
/* Take a duplicate for the plus. */
FsmAp *dup = new FsmAp( *retFsm );
/* Do repetition on the first half. */
retFsm->repeatOp( lowerRep );
afterOpMinimize( retFsm );
/* Star the duplicate. */
dup->starOp( );
afterOpMinimize( dup );
/* Tak on the kleene star. */
retFsm->concatOp( dup );
afterOpMinimize( retFsm );
}
break;
}
case RangeType: {
/* Check for bogus range. */
if ( upperRep - lowerRep < 0 ) {
error(loc) << "invalid range repetition" << endl;
/* Return null machine as recovery. */
retFsm = new FsmAp();
retFsm->lambdaFsm();
}
else if ( lowerRep == 0 && upperRep == 0 ) {
/* No copies. Don't need to evaluate the factorWithRep. This
* defeats the purpose so give a warning. */
warning(loc) << "zero to zero repetitions results "
"in the null machine" << endl;
retFsm = new FsmAp();
retFsm->lambdaFsm();
}
else {
/* Now need to evaluate the repeated machine. */
retFsm = factorWithRep->walk( pd );
if ( retFsm->startState->isFinState() ) {
warning(loc) << "applying range repetition to a machine that "
"accepts zero length word" << endl;
}
/* The start func orders need to be shifted before doing both kinds
* of repetition. */
pd->curActionOrd += retFsm->shiftStartActionOrder( pd->curActionOrd );
if ( lowerRep == 0 ) {
/* Just doing max repetition. Already guarded against n == 0. */
retFsm->optionalRepeatOp( upperRep );
afterOpMinimize( retFsm );
}
else if ( lowerRep == upperRep ) {
/* Just doing exact repetition. Already guarded against n == 0. */
retFsm->repeatOp( lowerRep );
afterOpMinimize( retFsm );
}
else {
/* This is the case that 0 < lowerRep < upperRep. Take a
* duplicate for the optional repeat. */
FsmAp *dup = new FsmAp( *retFsm );
/* Do repetition on the first half. */
retFsm->repeatOp( lowerRep );
afterOpMinimize( retFsm );
/* Do optional repetition on the second half. */
dup->optionalRepeatOp( upperRep - lowerRep );
afterOpMinimize( dup );
/* Tak on the duplicate machine. */
retFsm->concatOp( dup );
afterOpMinimize( retFsm );
}
}
break;
}
case FactorWithNegType: {
/* Evaluate the Factor. Pass it up. */
retFsm = factorWithNeg->walk( pd );
break;
}}
return retFsm;
}
void FactorWithRep::makeNameTree( ParseData *pd )
{
switch ( type ) {
case StarType:
case StarStarType:
case OptionalType:
case PlusType:
case ExactType:
case MaxType:
case MinType:
case RangeType:
factorWithRep->makeNameTree( pd );
break;
case FactorWithNegType:
factorWithNeg->makeNameTree( pd );
break;
}
}
void FactorWithRep::resolveNameRefs( ParseData *pd )
{
switch ( type ) {
case StarType:
case StarStarType:
case OptionalType:
case PlusType:
case ExactType:
case MaxType:
case MinType:
case RangeType:
factorWithRep->resolveNameRefs( pd );
break;
case FactorWithNegType:
factorWithNeg->resolveNameRefs( pd );
break;
}
}
/* Clean up after a factor with negation node. */
FactorWithNeg::~FactorWithNeg()
{
switch ( type ) {
case NegateType:
case CharNegateType:
delete factorWithNeg;
break;
case FactorType:
delete factor;
break;
}
}
/* Evaluate a factor with negation node. */
FsmAp *FactorWithNeg::walk( ParseData *pd )
{
FsmAp *retFsm = 0;
switch ( type ) {
case NegateType: {
/* Evaluate the factorWithNeg. */
FsmAp *toNegate = factorWithNeg->walk( pd );
/* Negation is subtract from dot-star. */
retFsm = dotStarFsm( pd );
retFsm->subtractOp( toNegate );
afterOpMinimize( retFsm );
break;
}
case CharNegateType: {
/* Evaluate the factorWithNeg. */
FsmAp *toNegate = factorWithNeg->walk( pd );
/* CharNegation is subtract from dot. */
retFsm = dotFsm( pd );
retFsm->subtractOp( toNegate );
afterOpMinimize( retFsm );
break;
}
case FactorType: {
/* Evaluate the Factor. Pass it up. */
retFsm = factor->walk( pd );
break;
}}
return retFsm;
}
void FactorWithNeg::makeNameTree( ParseData *pd )
{
switch ( type ) {
case NegateType:
case CharNegateType:
factorWithNeg->makeNameTree( pd );
break;
case FactorType:
factor->makeNameTree( pd );
break;
}
}
void FactorWithNeg::resolveNameRefs( ParseData *pd )
{
switch ( type ) {
case NegateType:
case CharNegateType:
factorWithNeg->resolveNameRefs( pd );
break;
case FactorType:
factor->resolveNameRefs( pd );
break;
}
}
/* Clean up after a factor node. */
Factor::~Factor()
{
switch ( type ) {
case LiteralType:
delete literal;
break;
case RangeType:
delete range;
break;
case OrExprType:
delete reItem;
break;
case RegExprType:
delete regExpr;
break;
case ReferenceType:
break;
case ParenType:
delete join;
break;
case LongestMatchType:
delete longestMatch;
break;
}
}
/* Evaluate a factor node. */
FsmAp *Factor::walk( ParseData *pd )
{
FsmAp *rtnVal = 0;
switch ( type ) {
case LiteralType:
rtnVal = literal->walk( pd );
break;
case RangeType:
rtnVal = range->walk( pd );
break;
case OrExprType:
rtnVal = reItem->walk( pd, 0 );
break;
case RegExprType:
rtnVal = regExpr->walk( pd, 0 );
break;
case ReferenceType:
rtnVal = varDef->walk( pd );
break;
case ParenType:
rtnVal = join->walk( pd );
break;
case LongestMatchType:
rtnVal = longestMatch->walk( pd );
break;
}
return rtnVal;
}
void Factor::makeNameTree( ParseData *pd )
{
switch ( type ) {
case LiteralType:
case RangeType:
case OrExprType:
case RegExprType:
break;
case ReferenceType:
varDef->makeNameTree( loc, pd );
break;
case ParenType:
join->makeNameTree( pd );
break;
case LongestMatchType:
longestMatch->makeNameTree( pd );
break;
}
}
void Factor::resolveNameRefs( ParseData *pd )
{
switch ( type ) {
case LiteralType:
case RangeType:
case OrExprType:
case RegExprType:
break;
case ReferenceType:
varDef->resolveNameRefs( pd );
break;
case ParenType:
join->resolveNameRefs( pd );
break;
case LongestMatchType:
longestMatch->resolveNameRefs( pd );
break;
}
}
/* Clean up a range object. Must delete the two literals. */
Range::~Range()
{
delete lowerLit;
delete upperLit;
}
/* Evaluate a range. Gets the lower an upper key and makes an fsm range. */
FsmAp *Range::walk( ParseData *pd )
{
/* Construct and verify the suitability of the lower end of the range. */
FsmAp *lowerFsm = lowerLit->walk( pd );
if ( !lowerFsm->checkSingleCharMachine() ) {
error(lowerLit->token.loc) <<
"bad range lower end, must be a single character" << endl;
}
/* Construct and verify the upper end. */
FsmAp *upperFsm = upperLit->walk( pd );
if ( !upperFsm->checkSingleCharMachine() ) {
error(upperLit->token.loc) <<
"bad range upper end, must be a single character" << endl;
}
/* Grab the keys from the machines, then delete them. */
Key lowKey = lowerFsm->startState->outList.head->lowKey;
Key highKey = upperFsm->startState->outList.head->lowKey;
delete lowerFsm;
delete upperFsm;
/* Validate the range. */
if ( lowKey > highKey ) {
/* Recover by setting upper to lower; */
error(lowerLit->token.loc) << "lower end of range is greater then upper end" << endl;
highKey = lowKey;
}
/* Return the range now that it is validated. */
FsmAp *retFsm = new FsmAp();
retFsm->rangeFsm( lowKey, highKey );
return retFsm;
}
/* Evaluate a literal object. */
FsmAp *Literal::walk( ParseData *pd )
{
/* FsmAp to return, is the alphabet signed. */
FsmAp *rtnVal = 0;
switch ( type ) {
case Number: {
/* Make the fsm key in int format. */
Key fsmKey = makeFsmKeyNum( token.data, token.loc, pd );
/* Make the new machine. */
rtnVal = new FsmAp();
rtnVal->concatFsm( fsmKey );
break;
}
case LitString: {
/* Make the array of keys in int format. */
long length;
bool caseInsensitive;
char *data = prepareLitString( token.loc, token.data, token.length,
length, caseInsensitive );
Key *arr = new Key[length];
makeFsmKeyArray( arr, data, length, pd );
/* Make the new machine. */
rtnVal = new FsmAp();
if ( caseInsensitive )
rtnVal->concatFsmCI( arr, length );
else
rtnVal->concatFsm( arr, length );
delete[] data;
delete[] arr;
break;
}}
return rtnVal;
}
/* Clean up after a regular expression object. */
RegExpr::~RegExpr()
{
switch ( type ) {
case RecurseItem:
delete regExpr;
delete item;
break;
case Empty:
break;
}
}
/* Evaluate a regular expression object. */
FsmAp *RegExpr::walk( ParseData *pd, RegExpr *rootRegex )
{
/* This is the root regex, pass down a pointer to this. */
if ( rootRegex == 0 )
rootRegex = this;
FsmAp *rtnVal = 0;
switch ( type ) {
case RecurseItem: {
/* Walk both items. */
rtnVal = regExpr->walk( pd, rootRegex );
FsmAp *fsm2 = item->walk( pd, rootRegex );
rtnVal->concatOp( fsm2 );
break;
}
case Empty: {
rtnVal = new FsmAp();
rtnVal->lambdaFsm();
break;
}
}
return rtnVal;
}
/* Clean up after an item in a regular expression. */
ReItem::~ReItem()
{
switch ( type ) {
case Data:
case Dot:
break;
case OrBlock:
case NegOrBlock:
delete orBlock;
break;
}
}
/* Evaluate a regular expression object. */
FsmAp *ReItem::walk( ParseData *pd, RegExpr *rootRegex )
{
/* The fsm to return, is the alphabet signed? */
FsmAp *rtnVal = 0;
switch ( type ) {
case Data: {
/* Move the data into an integer array and make a concat fsm. */
Key *arr = new Key[token.length];
makeFsmKeyArray( arr, token.data, token.length, pd );
/* Make the concat fsm. */
rtnVal = new FsmAp();
if ( rootRegex != 0 && rootRegex->caseInsensitive )
rtnVal->concatFsmCI( arr, token.length );
else
rtnVal->concatFsm( arr, token.length );
delete[] arr;
break;
}
case Dot: {
/* Make the dot fsm. */
rtnVal = dotFsm( pd );
break;
}
case OrBlock: {
/* Get the or block and minmize it. */
rtnVal = orBlock->walk( pd, rootRegex );
if ( rtnVal == 0 ) {
rtnVal = new FsmAp();
rtnVal->lambdaFsm();
}
rtnVal->minimizePartition2();
break;
}
case NegOrBlock: {
/* Get the or block and minimize it. */
FsmAp *fsm = orBlock->walk( pd, rootRegex );
fsm->minimizePartition2();
/* Make a dot fsm and subtract from it. */
rtnVal = dotFsm( pd );
rtnVal->subtractOp( fsm );
rtnVal->minimizePartition2();
break;
}
}
/* If the item is followed by a star, then apply the star op. */
if ( star ) {
if ( rtnVal->startState->isFinState() ) {
warning(loc) << "applying kleene star to a machine that "
"accepts zero length word" << endl;
}
rtnVal->starOp();
rtnVal->minimizePartition2();
}
return rtnVal;
}
/* Clean up after an or block of a regular expression. */
ReOrBlock::~ReOrBlock()
{
switch ( type ) {
case RecurseItem:
delete orBlock;
delete item;
break;
case Empty:
break;
}
}
/* Evaluate an or block of a regular expression. */
FsmAp *ReOrBlock::walk( ParseData *pd, RegExpr *rootRegex )
{
FsmAp *rtnVal = 0;
switch ( type ) {
case RecurseItem: {
/* Evaluate the two fsm. */
FsmAp *fsm1 = orBlock->walk( pd, rootRegex );
FsmAp *fsm2 = item->walk( pd, rootRegex );
if ( fsm1 == 0 )
rtnVal = fsm2;
else {
fsm1->unionOp( fsm2 );
rtnVal = fsm1;
}
break;
}
case Empty: {
rtnVal = 0;
break;
}
}
return rtnVal;;
}
/* Evaluate an or block item of a regular expression. */
FsmAp *ReOrItem::walk( ParseData *pd, RegExpr *rootRegex )
{
/* The return value, is the alphabet signed? */
FsmAp *rtnVal = 0;
switch ( type ) {
case Data: {
/* Make the or machine. */
rtnVal = new FsmAp();
/* Put the or data into an array of ints. Note that we find unique
* keys. Duplicates are silently ignored. The alternative would be to
* issue warning or an error but since we can't with [a0-9a] or 'a' |
* 'a' don't bother here. */
KeySet keySet;
makeFsmUniqueKeyArray( keySet, token.data, token.length,
rootRegex != 0 ? rootRegex->caseInsensitive : false, pd );
/* Run the or operator. */
rtnVal->orFsm( keySet.data, keySet.length() );
break;
}
case Range: {
/* Make the upper and lower keys. */
Key lowKey = makeFsmKeyChar( lower, pd );
Key highKey = makeFsmKeyChar( upper, pd );
/* Validate the range. */
if ( lowKey > highKey ) {
/* Recover by setting upper to lower; */
error(loc) << "lower end of range is greater then upper end" << endl;
highKey = lowKey;
}
/* Make the range machine. */
rtnVal = new FsmAp();
rtnVal->rangeFsm( lowKey, highKey );
if ( rootRegex != 0 && rootRegex->caseInsensitive ) {
if ( lowKey <= 'Z' && 'A' <= highKey ) {
Key otherLow = lowKey < 'A' ? Key('A') : lowKey;
Key otherHigh = 'Z' < highKey ? Key('Z') : highKey;
otherLow = 'a' + ( otherLow - 'A' );
otherHigh = 'a' + ( otherHigh - 'A' );
FsmAp *otherRange = new FsmAp();
otherRange->rangeFsm( otherLow, otherHigh );
rtnVal->unionOp( otherRange );
rtnVal->minimizePartition2();
}
else if ( lowKey <= 'z' && 'a' <= highKey ) {
Key otherLow = lowKey < 'a' ? Key('a') : lowKey;
Key otherHigh = 'z' < highKey ? Key('z') : highKey;
otherLow = 'A' + ( otherLow - 'a' );
otherHigh = 'A' + ( otherHigh - 'a' );
FsmAp *otherRange = new FsmAp();
otherRange->rangeFsm( otherLow, otherHigh );
rtnVal->unionOp( otherRange );
rtnVal->minimizePartition2();
}
}
break;
}}
return rtnVal;
}