From 4c1bc5a3211e758e04872b41b6ea8515e4c2d87d Mon Sep 17 00:00:00 2001 From: thurston Date: Thu, 14 Feb 2008 23:34:03 +0000 Subject: [PATCH] Scanners now ensure that a pattern's leaving actions are executed. git-svn-id: http://svn.complang.org/ragel/trunk@415 052ea7fc-9027-0410-9066-f65837a77df0 --- ragel/fsmap.cpp | 12 ++++++++++++ ragel/fsmgraph.h | 1 + ragel/parsetree.cpp | 47 +++++++++++++++++++++++++++++++++++------------ ragel/parsetree.h | 3 ++- 4 files changed, 50 insertions(+), 13 deletions(-) diff --git a/ragel/fsmap.cpp b/ragel/fsmap.cpp index ff6f929..d35df11 100644 --- a/ragel/fsmap.cpp +++ b/ragel/fsmap.cpp @@ -302,6 +302,18 @@ void FsmAp::fillGaps( StateAp *state ) } } +void FsmAp::setErrorActions( StateAp *state, const ActionTable &other ) +{ + /* Fill any gaps in the out list with an error transition. */ + fillGaps( state ); + + /* Set error transitions in the transitions that go to error. */ + for ( TransList::Iter trans = state->outList; trans.lte(); trans++ ) { + if ( trans->toState == 0 ) + trans->actionTable.setActions( other ); + } +} + void FsmAp::setErrorAction( StateAp *state, int ordering, Action *action ) { /* Fill any gaps in the out list with an error transition. */ diff --git a/ragel/fsmgraph.h b/ragel/fsmgraph.h index c8dac52..ba3848e 100644 --- a/ragel/fsmgraph.h +++ b/ragel/fsmgraph.h @@ -1136,6 +1136,7 @@ struct FsmAp /* Action setting support. */ void transferOutActions( StateAp *state ); void transferErrorActions( StateAp *state, int transferPoint ); + void setErrorActions( StateAp *state, const ActionTable &other ); void setErrorAction( StateAp *state, int ordering, Action *action ); /* Fill all spaces in a transition list with an error transition. */ diff --git a/ragel/parsetree.cpp b/ragel/parsetree.cpp index f31d8bc..048d171 100644 --- a/ragel/parsetree.cpp +++ b/ragel/parsetree.cpp @@ -178,13 +178,15 @@ void LongestMatch::makeActions( ParseData *pd ) /* 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 ) ); + 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. */ + /* 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. */ @@ -292,7 +294,7 @@ void LongestMatch::restart( FsmAp *graph, TransAp *trans ) graph->attachTrans( fromState, graph->startState, trans ); } -void LongestMatch::runLonestMatch( ParseData *pd, FsmAp *graph ) +void LongestMatch::runLongestMatch( ParseData *pd, FsmAp *graph ) { graph->markReachableFromHereStopFinal( graph->startState ); for ( StateList::Iter ms = graph->stateList; ms.lte(); ms++ ) { @@ -313,9 +315,9 @@ void LongestMatch::runLonestMatch( ParseData *pd, FsmAp *graph ) StateAp *toState = trans->toState; assert( toState ); - /* Check if there are transitions out, this may be a very - * close approximation? Out transitions going nowhere? - * FIXME: Check. */ + /* 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 ); @@ -374,12 +376,18 @@ void LongestMatch::runLonestMatch( ParseData *pd, FsmAp *graph ) StateAp *toState = trans->toState; assert( toState ); - /* Check if there are transitions out, this may be a very - * close approximation? Out transitions going nowhere? - * FIXME: Check. */ + /* 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. */ + * 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 ); @@ -451,7 +459,7 @@ void LongestMatch::runLonestMatch( ParseData *pd, FsmAp *graph ) } } else if ( st->lmItemSet.length() > 1 ) { - /* Need to use the select. Take note of the which items the select + /* 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 ) @@ -469,6 +477,14 @@ void LongestMatch::runLonestMatch( ParseData *pd, FsmAp *graph ) 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. */ @@ -483,6 +499,13 @@ FsmAp *LongestMatch::walk( ParseData *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]; @@ -491,7 +514,7 @@ FsmAp *LongestMatch::walk( ParseData *pd ) afterOpMinimize( rtnVal ); } - runLonestMatch( pd, rtnVal ); + runLongestMatch( pd, rtnVal ); /* Pop the name scope. */ pd->popNameScope( nameFrame ); diff --git a/ragel/parsetree.h b/ragel/parsetree.h index f1f4181..7e35c34 100644 --- a/ragel/parsetree.h +++ b/ragel/parsetree.h @@ -298,7 +298,8 @@ struct LongestMatch FsmAp *walk( ParseData *pd ); void makeNameTree( ParseData *pd ); void resolveNameRefs( ParseData *pd ); - void runLonestMatch( ParseData *pd, FsmAp *graph ); + void transferScannerLeavingActions( FsmAp *graph ); + void runLongestMatch( ParseData *pd, FsmAp *graph ); Action *newAction( ParseData *pd, const InputLoc &loc, const char *name, InlineList *inlineList ); void makeActions( ParseData *pd ); -- 2.7.4