From: Gilles Lacroix <lacroix7@...>
Date: 2006-08-04T07:20:10+09:00
Subject: Re: Building the finite state machine of a Ruby regexp

On Thu, 03 Aug 2006 09:22:14 +0900, Matthew Smillie wrote�:

> (...) Like Caleb Clausen  
> suggested, though, there are probably partial solutions out there,  
> depending on how flexible your criteria are and exactly what  
> information you need - are you looking for an aid in building  
> regexes?  just visualising them?  some other sort of analysis?

What I'd like to do is, given any regexp :
1. To test *quickly* if a particular string matches this regexp : that's
why I'd prefer to use native Ruby regexes. They are the natural choice
when programming in Ruby and offer very good performance (because the
parser is compiled into the Ruby interpreter from a well-established C
code base (GNU regexps) that should be reasonably well optimized after
decades of public exposure).
2. To generate "random" strings that match the same regexp : that's why I
was thinking about using a Finite State Machine (or kind of it since, as
you pointed out 'modern' regexp are not alway representable as FSM) :
starting from the initial state and choosing randomly an outbound edge,
I can add a (first) character to the string. Repeating the process from
the node I arrived on, I can add a second character, and so on... (then
I will also have to make sure that I finally reach the final state in a
reasonable time but that's another problem).

Gilles Lacroix.