Minimisation question

Adrian Thurston thurs... at
Thu Sep 14 16:46:42 UTC 2006

Pretty much every operation can cause unreachable states. For example, 
during union a new start state is created with epsilon transitions drawn to 
the old start states. The epsilon operation effectively copies transition 
lists from the destination state to the source state. If the old start 
states don't have any transitions in from elsewhere in the machine then they 
become unreachable. The on-the-fly cleanup will reap states with no external 
entry points. This gets most unreachables, but just like in garbage 
collection, cycles cause problems.

In your ragel file the subtraction operation is leaving behind unreachables. 
Subtraction may in fact need a full mark and sweep (I had thought the 
on-the-fly was sufficient). The attached patch will allow you to compile 
without -e.


Colin Fleming wrote:
> Ok, thanks for the help! What causes unreachable states? Can I change
> something about the grammar to avoid them (apart from -e, of course)?
> Cheers,
> Colin
-------------- next part --------------
Index: ragel/fsmgraph.cpp
--- ragel/fsmgraph.cpp	(revision 3586)
+++ ragel/fsmgraph.cpp	(working copy)
@@ -496,6 +496,7 @@
 	/* Remove states that have no path to a final state. */
+	removeUnreachableStates();
 bool FsmAp::inEptVect( EptVect *eptVect, StateAp *state )

More information about the ragel-users mailing list