"Fossies" - the Fresh Open Source Software Archive  

Source code changes of the file "src/parsetree.cc" between
ragel-7.0.0.11.tar.gz and ragel-7.0.0.12.tar.gz

About: Ragel compiles executable finite state machines from regular languages (C, C++, Obj-C, C#, D, Java, Go and Ruby). Development version.

parsetree.cc  (ragel-7.0.0.11):parsetree.cc  (ragel-7.0.0.12)
skipping to change at line 291 skipping to change at line 291
InlineList *inlineList = new InlineList; InlineList *inlineList = new InlineList;
inlineList->append( new InlineItem( InputLoc(), InlineItem::Stmt ) ); inlineList->append( new InlineItem( InputLoc(), InlineItem::Stmt ) );
inlineList->head->children = new InlineList; inlineList->head->children = new InlineList;
inlineList->head->children->append( new InlineItem( lmi->getLoc() , this, lmi, inlineList->head->children->append( new InlineItem( lmi->getLoc() , this, lmi,
InlineItem::LmOnLagBehind ) ); InlineItem::LmOnLagBehind ) );
char *actName = new char[50]; char *actName = new char[50];
sprintf( actName, "lag%i", lmi->longestMatchId ); sprintf( actName, "lag%i", lmi->longestMatchId );
lmi->actLagBehind = newLmAction( pd, lmi->getLoc(), actName, inli neList ); lmi->actLagBehind = newLmAction( pd, lmi->getLoc(), actName, inli neList );
} }
/*
* NFA actions
*
* Actions that execute the user action and restart on the next character
.
* These actions will set tokend themselves (it is the current char). The
y
* also reset the nfa machinery used to choose between tokens.
*/
for ( LmPartList::Iter lmi = *longestMatchList; lmi.lte(); lmi++ ) {
/* For each part create actions for setting the match type. We n
eed
* to do this so that the actions will go into the actionIndex. *
/
InlineList *inlineList = new InlineList;
inlineList->append( new InlineItem( InputLoc(), InlineItem::Stmt
) );
inlineList->head->children = new InlineList;
inlineList->head->children->append( new InlineItem( lmi->getLoc()
, this, lmi,
InlineItem::LmNfaOnLast ) );
char *actName = new char[50];
sprintf( actName, "nlast%i", lmi->longestMatchId );
lmi->actNfaOnLast = newLmAction( pd, lmi->getLoc(), actName, inli
neList );
}
for ( LmPartList::Iter lmi = *longestMatchList; lmi.lte(); lmi++ ) {
/* For each part create actions for setting the match type. We n
eed
* to do this so that the actions will go into the actionIndex. *
/
InlineList *inlineList = new InlineList;
inlineList->append( new InlineItem( InputLoc(), InlineItem::Stmt
) );
inlineList->head->children = new InlineList;
inlineList->head->children->append( new InlineItem( lmi->getLoc()
, this, lmi,
InlineItem::LmNfaOnNext ) );
char *actName = new char[50];
sprintf( actName, "nnext%i", lmi->longestMatchId );
lmi->actNfaOnNext = newLmAction( pd, lmi->getLoc(), actName, inli
neList );
}
for ( LmPartList::Iter lmi = *longestMatchList; lmi.lte(); lmi++ ) {
/* For each part create actions for setting the match type. We n
eed
* to do this so that the actions will go into the actionIndex. *
/
InlineList *inlineList = new InlineList;
inlineList->append( new InlineItem( InputLoc(), InlineItem::Stmt
) );
inlineList->head->children = new InlineList;
inlineList->head->children->append( new InlineItem( lmi->getLoc()
, this, lmi,
InlineItem::LmNfaOnEof ) );
char *actName = new char[50];
sprintf( actName, "neof%i", lmi->longestMatchId );
lmi->actNfaOnEof = newLmAction( pd, lmi->getLoc(), actName, inlin
eList );
}
InputLoc loc; InputLoc loc;
loc.line = 1; loc.line = 1;
loc.col = 1; loc.col = 1;
loc.fileName = "NONE"; loc.fileName = "NONE";
/* Create the error action. */ /* Create the error action. */
InlineList *il6 = new InlineList; InlineList *il6 = new InlineList;
il6->append( new InlineItem( loc, this, 0, InlineItem::LmSwitch ) ); il6->append( new InlineItem( loc, this, 0, InlineItem::LmSwitch ) );
lmActSelect = newLmAction( pd, loc, "switch", il6 ); lmActSelect = newLmAction( pd, loc, "switch", il6 );
} }
skipping to change at line 356 skipping to change at line 402
/* Recurse down the join. */ /* Recurse down the join. */
lmi->join->resolveNameRefs( pd ); lmi->join->resolveNameRefs( pd );
} }
/* The name scope ends, pop the name instantiation. */ /* The name scope ends, pop the name instantiation. */
pd->popNameScope( nameFrame ); pd->popNameScope( nameFrame );
} }
void LongestMatch::restart( FsmAp *graph, TransAp *trans ) void LongestMatch::restart( FsmAp *graph, TransAp *trans )
{ {
if ( trans->plain() ) { StateAp *fromState = trans->tdap()->fromState;
StateAp *fromState = trans->tdap()->fromState; graph->detachTrans( fromState, trans->tdap()->toState, trans->tdap() );
graph->detachTrans( fromState, trans->tdap()->toState, trans->tda graph->attachTrans( fromState, graph->startState, trans->tdap() );
p() );
graph->attachTrans( fromState, graph->startState, trans->tdap() )
;
}
else {
for ( CondList::Iter cti = trans->tcap()->condList; cti.lte(); ct
i++ ) {
StateAp *fromState = cti->fromState;
graph->detachTrans( fromState, cti->toState, cti );
graph->attachTrans( fromState, graph->startState, cti );
}
}
} }
void LongestMatch::runLongestMatch( ParseData *pd, FsmAp *graph ) void LongestMatch::restart( FsmAp *graph, CondAp *cti )
{ {
graph->markReachableFromHereStopFinal( graph->startState ); StateAp *fromState = cti->fromState;
for ( StateList::Iter ms = graph->stateList; ms.lte(); ms++ ) { graph->detachTrans( fromState, cti->toState, cti );
if ( ms->stateBits & STB_ISMARKED ) { graph->attachTrans( fromState, graph->startState, cti );
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->plain() ) {
TransDataAp *tdap = trans->tdap();
if ( tdap->lmActionTable.length() > 0 ) {
LmActionTableEl *lmAct = tdap->lmActionTa
ble.data;
StateAp *toState = tdap->toState;
assert( toState );
/* Can only optimize this if there are no
transitions out.
* Note there can be out transitions goin
g nowhere with
* actions and they too must inhibit this
optimization. */
if ( toState->outList.length() > 0 ) {
/* Fill the item sets. */
graph->markReachableFromHereStopF
inal( toState );
for ( StateList::Iter ms = graph-
>stateList; ms.lte(); ms++ ) {
if ( ms->stateBits & STB_
ISMARKED ) {
ms->lmItemSet.ins
ert( lmAct->value );
ms->stateBits &=
~ STB_ISMARKED;
}
}
}
}
}
else {
for ( CondList::Iter cond = trans->tcap()->condLi
st; cond.lte(); cond++ ) {
if ( cond->lmActionTable.length() > 0 ) {
LmActionTableEl *lmAct = cond->lm
ActionTable.data;
StateAp *toState = cond->toState;
assert( toState );
/* Can only optimize this if ther
e are no transitions out.
* Note there can be out transiti
ons going nowhere with
* actions and they too must inhi
bit this optimization. */
if ( toState->outList.length() >
0 ) {
/* Fill the item sets. */
graph->markReachableFromH
ereStopFinal( toState );
for ( StateList::Iter ms
= graph->stateList; ms.lte(); ms++ ) {
if ( ms->stateBit
s & STB_ISMARKED ) {
ms->lmIte
mSet.insert( lmAct->value );
ms->state
Bits &= ~ 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. */
FsmRes res = FsmAp::isolateStartState( graph );
graph = res.fsm;
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 requi
re an
* error state. */
lmSwitchHandlesError = true;
pd->fsmCtx->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->plain() ) {
TransDataAp *tdap = trans->tdap();
if ( tdap->lmActionTable.length() > 0 ) {
LmActionTableEl *lmAct = tdap->lmActionTa
ble.data;
StateAp *toState = tdap->toState;
assert( toState );
/* Can only optimize this if there are no
transitions out.
* Note there can be out transitions goin
g nowhere with
* actions and they too must inhibit this
optimization. */
if ( toState->outList.length() == 0 ) {
/* Can execute the immediate acti
on for the longest match
* part. Redirect the action to t
he start state.
*
* NOTE: When we need to inhibit
on_last due to leaving
* actions the above test suffice
s. If the state has out
* actions then it will fail beca
use the out action will
* have been transferred to an er
ror transition, which
* makes the outlist non-empty. *
/
tdap->actionTable.setAction( lmAc
t->key,
lmAct->value->act
OnLast );
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 t
he highest item set
* length reachable from here (ex
cluding at transtions to
* final states). */
bool nonFinalNonEmptyItemSet = fa
lse;
maxItemSetLength = 0;
graph->markReachableFromHereStopF
inal( toState );
for ( StateList::Iter ms = graph-
>stateList; ms.lte(); ms++ ) {
if ( ms->stateBits & STB_
ISMARKED ) {
if ( ms->lmItemSe
t.length() > 0 && !ms->isFinState() )
nonFinalN
onEmptyItemSet = true;
if ( ms->lmItemSe
t.length() > maxItemSetLength )
maxItemSe
tLength = ms->lmItemSet.length();
ms->stateBits &=
~ STB_ISMARKED;
}
}
/* If there are reachable states
that are not final and
* have non empty item sets or th
at have an item set
* length greater than one then w
e need to set tokend
* because the error action that
matches the token will
* require it. */
if ( nonFinalNonEmptyItemSet || m
axItemSetLength > 1 )
tdap->actionTable.setActi
on( 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. */
tdap->actionTable.setActi
on( lmAct->key,
lmAct->va
lue->setActId );
}
}
}
}
else {
for ( CondList::Iter cond = trans->tcap()->condLi
st; cond.lte(); cond++ ) {
if ( cond->lmActionTable.length() > 0 ) {
LmActionTableEl *lmAct = cond->lm
ActionTable.data;
StateAp *toState = cond->toState;
assert( toState );
/* Can only optimize this if ther
e are no transitions out.
* Note there can be out transiti
ons going nowhere with
* actions and they too must inhi
bit this optimization. */
if ( toState->outList.length() ==
0 ) {
/* Can execute the immedi
ate action for the longest match
* part. Redirect the act
ion 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 f
ail because the out action will
* have been transferred
to an error transition, which
* makes the outlist non-
empty. */
cond->actionTable.setActi
on( lmAct->key,
lmAct->va
lue->actOnLast );
restartTrans.append( tran
s );
}
else {
/* Look for non final sta
tes that have a non-empty item
* set. If these are pres
ent then we need to record the
* end of the token. Als
o Find the highest item set
* length reachable from
here (excluding at transtions to
* final states). */
bool nonFinalNonEmptyItem
Set = false;
maxItemSetLength = 0;
graph->markReachableFromH
ereStopFinal( toState );
for ( StateList::Iter ms
= graph->stateList; ms.lte(); ms++ ) {
if ( ms->stateBit
s & STB_ISMARKED ) {
if ( ms->
lmItemSet.length() > 0 && !ms->isFinState() )
n
onFinalNonEmptyItemSet = true;
if ( ms->
lmItemSet.length() > maxItemSetLength )
m
axItemSetLength = ms->lmItemSet.length();
ms->state
Bits &= ~ STB_ISMARKED;
}
}
/* If there are reachable
states that are not final and
* have non empty item se
ts or that have an item set
* length greater than on
e then we need to set tokend
* because the error acti
on that matches the token will
* require it. */
if ( nonFinalNonEmptyItem
Set || maxItemSetLength > 1 )
cond->actionTable
.setAction( pd->setTokEndOrd, pd->setTokEnd );
/* Some states may not kn
ow which longest match item to
* execute, must set it.
*/
if ( maxItemSetLength > 1
) {
/* There are tran
sitions out, another match may come. */
cond->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->fsmCtx->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 k
nows that
* the last character of the token was one back a
nd restart. */
graph->setErrorTarget( st, graph->startState, &lm
ErrActionOrd,
&st->lmItemSet[0]->actOnNext, 1 )
;
st->eofActionTable.setAction( lmErrActionOrd,
st->lmItemSet[0]->actOnNext );
st->eofTarget = graph->startState;
}
else {
graph->setErrorTarget( st, graph->startState, &lm
ErrActionOrd,
&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 s
elect
* is needed for so only the necessary actions are includ
ed. */
for ( LmItemSet::Iter plmi = st->lmItemSet; plmi.lte(); p
lmi++ ) {
if ( *plmi != 0 )
(*plmi)->inLmSelect = true;
}
/* On error, execute the action select and go to the star
t state. */
graph->setErrorTarget( st, graph->startState, &lmErrActio
nOrd,
&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 ) void LongestMatch::transferScannerLeavingActions( FsmAp *graph )
{ {
for ( StateList::Iter st = graph->stateList; st.lte(); st++ ) { for ( StateList::Iter st = graph->stateList; st.lte(); st++ ) {
if ( st->outActionTable.length() > 0 ) if ( st->outActionTable.length() > 0 )
graph->setErrorActions( st, st->outActionTable ); graph->setErrorActions( st, st->outActionTable );
} }
} }
FsmRes LongestMatch::walk( ParseData *pd ) FsmRes LongestMatch::walkClassic( ParseData *pd )
{ {
/* The longest match has it's own name scope. */ /* The longest match has it's own name scope. */
NameFrame nameFrame = pd->enterNameScope( true, 1 ); NameFrame nameFrame = pd->enterNameScope( true, 1 );
/* Make each part of the longest match. */ /* Make each part of the longest match. */
FsmAp **parts = new FsmAp*[longestMatchList->length()]; FsmAp **parts = new FsmAp*[longestMatchList->length()];
LmPartList::Iter lmi = *longestMatchList; LmPartList::Iter lmi = *longestMatchList;
for ( int i = 0; lmi.lte(); lmi++, i++ ) { for ( int i = 0; lmi.lte(); lmi++, i++ ) {
/* Create the machine and embed the setting of the longest match id. */ /* Create the machine and embed the setting of the longest match id. */
FsmRes res = lmi->join->walk( pd ); FsmRes res = lmi->join->walk( pd );
skipping to change at line 695 skipping to change at line 465
runLongestMatch( pd, res.fsm ); runLongestMatch( pd, res.fsm );
/* Pop the name scope. */ /* Pop the name scope. */
pd->popNameScope( nameFrame ); pd->popNameScope( nameFrame );
delete[] parts; delete[] parts;
return res; return res;
} }
FsmRes LongestMatch::walk( ParseData *pd )
{
if ( nfaConstruction )
return walkNfa( pd );
else
return walkClassic( pd );
}
NfaUnion::~NfaUnion() NfaUnion::~NfaUnion()
{ {
for ( TermVect::Iter term = terms; term.lte(); term++ ) for ( TermVect::Iter term = terms; term.lte(); term++ )
delete *term; delete *term;
if ( roundsList != 0 ) if ( roundsList != 0 )
delete roundsList; delete roundsList;
} }
FsmRes NfaUnion::walk( ParseData *pd ) FsmRes NfaUnion::walk( ParseData *pd )
{ {
skipping to change at line 1952 skipping to change at line 1730
delete regExpr; delete regExpr;
break; break;
case ReferenceType: case ReferenceType:
break; break;
case ParenType: case ParenType:
delete join; delete join;
break; break;
case LongestMatchType: case LongestMatchType:
delete longestMatch; delete longestMatch;
break; break;
case NfaRep: case CondStar: case CondPlus: case NfaWrap: case NfaRep:
case CondStar: case CondPlus:
delete expression; delete expression;
break; break;
} }
} }
/* Evaluate a factor node. */ /* Evaluate a factor node. */
FsmRes Factor::walk( ParseData *pd ) FsmRes Factor::walk( ParseData *pd )
{ {
switch ( type ) { switch ( type ) {
case LiteralType: case LiteralType:
skipping to change at line 1979 skipping to change at line 1758
return FsmRes( FsmRes::Fsm(), regExpr->walk( pd, 0 ) ); return FsmRes( FsmRes::Fsm(), regExpr->walk( pd, 0 ) );
case ReferenceType: case ReferenceType:
return varDef->walk( pd ); return varDef->walk( pd );
case ParenType: case ParenType:
return join->walk( pd ); return join->walk( pd );
case LongestMatchType: case LongestMatchType:
return longestMatch->walk( pd ); return longestMatch->walk( pd );
case NfaRep: { case NfaRep: {
FsmRes exprTree = expression->walk( pd ); FsmRes exprTree = expression->walk( pd );
FsmRes res = FsmAp::nfaRepeatOp( exprTree.fsm, action1, action2, if ( mode == Factor::NfaLegacy ) {
action3, FsmRes res = FsmAp::nfaRepeatOp( exprTree.fsm, action1, a
action4, action5, action6 ); ction2, action3,
action4, action5, action6 );
res.fsm->verifyIntegrity(); res.fsm->verifyIntegrity();
return res; return res;
}
else if ( mode == Factor::NfaLazy ) {
FsmRes res = FsmAp::nfaRepeatOp2( exprTree.fsm, action1,
action2, action3,
action4, action5, action6, FsmAp::NfaLazy
);
res.fsm->verifyIntegrity();
return res;
}
else {
FsmRes res = FsmAp::nfaRepeatOp2( exprTree.fsm, action1,
action2, action3,
action4, action5, action6, FsmAp::NfaGree
dy );
res.fsm->verifyIntegrity();
return res;
}
}
case NfaWrap: {
FsmRes exprTree = expression->walk( pd );
if ( mode == Factor::NfaLazy ) {
FsmRes res = FsmAp::nfaWrap( exprTree.fsm, action1, actio
n2, action3,
action4, /* action5, */ action6, FsmAp::N
faLazy );
res.fsm->verifyIntegrity();
return res;
}
else {
FsmRes res = FsmAp::nfaWrap( exprTree.fsm, action1, actio
n2, action3,
action4, /* action5, */ action6, FsmAp::N
faGreedy );
res.fsm->verifyIntegrity();
return res;
}
} }
case CondStar: { case CondStar: {
FsmRes exprTree = expression->walk( pd ); FsmRes exprTree = expression->walk( pd );
if ( !exprTree.success() ) if ( !exprTree.success() )
return exprTree; return exprTree;
if ( exprTree.fsm->startState->isFinState() ) { if ( exprTree.fsm->startState->isFinState() ) {
pd->id->warning(loc) << "applying plus operator to a mach ine that " pd->id->warning(loc) << "applying plus operator to a mach ine that "
"accepts zero length word" << endl; "accepts zero length word" << endl;
} }
skipping to change at line 2030 skipping to change at line 1842
break; break;
case ReferenceType: case ReferenceType:
varDef->makeNameTree( loc, pd ); varDef->makeNameTree( loc, pd );
break; break;
case ParenType: case ParenType:
join->makeNameTree( pd ); join->makeNameTree( pd );
break; break;
case LongestMatchType: case LongestMatchType:
longestMatch->makeNameTree( pd ); longestMatch->makeNameTree( pd );
break; break;
case NfaWrap:
case NfaRep: case NfaRep:
case CondStar: case CondStar:
case CondPlus: case CondPlus:
expression->makeNameTree( pd ); expression->makeNameTree( pd );
break; break;
} }
} }
void Factor::resolveNameRefs( ParseData *pd ) void Factor::resolveNameRefs( ParseData *pd )
{ {
skipping to change at line 2056 skipping to change at line 1869
case ReferenceType: case ReferenceType:
varDef->resolveNameRefs( pd ); varDef->resolveNameRefs( pd );
break; break;
case ParenType: case ParenType:
join->resolveNameRefs( pd ); join->resolveNameRefs( pd );
break; break;
case LongestMatchType: case LongestMatchType:
longestMatch->resolveNameRefs( pd ); longestMatch->resolveNameRefs( pd );
break; break;
case NfaRep: case NfaRep:
case NfaWrap:
case CondStar: case CondStar:
case CondPlus: case CondPlus:
expression->resolveNameRefs( pd ); expression->resolveNameRefs( pd );
break; break;
} }
} }
/* Clean up a range object. Must delete the two literals. */ /* Clean up a range object. Must delete the two literals. */
Range::~Range() Range::~Range()
{ {
 End of changes. 11 change blocks. 
410 lines changed or deleted 129 lines changed or added

Home  |  About  |  Features  |  All  |  Newest  |  Dox  |  Diffs  |  RSS Feeds  |  Screenshots  |  Comments  |  Imprint  |  Privacy  |  HTTP(S)