17 ms·
In grad school I had a need for a tool that would generate all strings accepted by a regex of a specified size. I wrote one myself, but was never really satisf
by kenjackson 16y ago
In grad school I had a need for a tool that would generate all strings accepted by a regex of a specified size.
I wrote one myself, but was never really satisfied that I did a good job on it. I'd love to see the code of an efficient implementation of such a thing.
- rndmcnlly0 16y ago"Generate all" and "efficient" seems doomed at some level. Considering /[01]+/, there are clearly an exponential number of matches given some given max length. The expression itself provides a nice summary of the generative space it implies. Perhaps for a particular application you could apply a kind of lazy generation. Say, given /[01]+/ it would first expand it into the subspaces of /0/, /1/, /0[01]+/, and /1[01]+/. One of these branches could be expanded next depending on what was actually needed in the next step.
- abecedarius 16y agoDoug McIlroy wrote an article on that: http://www.cs.dartmouth.edu/~doug/nfa.ps.gz http://www.cs.dartmouth.edu/~doug/nfa.ps.gz Code: http://www.cs.dartmouth.edu/~doug/nfa.hs http://www.cs.dartmouth.edu/~doug/nfa.hs
- kenjackson 16y agoThank you. That is actually an excellent paper. A decade late for me, but excellent.
- elblanco 16y ago"Higher Order Perl" has a chapter on building one in Perl. http://en.wikipedia.org/wiki/Higher-Order_Perl http://en.wikipedia.org/wiki/Higher-Order_Perl I believe the full text is available.