Given a list of regexes, generate all possible strings that matches all of them | Hacker News Reader

Given a list of regexes, generate all possible strings that matches all of them

github.com

17 pointsdraegtun9 comments

This is really interesting, but wait: won't the number of strings matching a given set of regexes be infinite, for many different types of regexes, i.e. it's like the number of phrases in language that fit a certain grammatical rule.

The github page mentions that * and + quantifiers are redefined to have limits of {0,3} and {1,4} respectively. That wasn't what you were thinking of, was it?

Yes. The list is generated lazily and ordered from shortest to longest, though, so piping the output to "|head -n 100" will terminate rather quickly.

The ([String] -> IO [String]) API also generated a lazy list:

    http://hackage.haskell.org/packages/archive/regex-genex/0.2.0/doc/html/Regex-Genex.html

so one can take only part of the output like this:

   Regex.Genex> fmap (take 5) (genex ["([abc]+)\\1"])
   ["bb","cc","aa","bbbb","cccc"]

nice idea. it doesn't say whether it can filter/flag duplicates, but that seems like it would be useful functionality to add if not present (it can indicate that you've made a mistake, or that your regexp is inefficient[* ]).

it's such a sweet idea, with an obvious implementation and use, that you'd think it would have been done before. but i've not heard of anything and am having a hard time finding a good search term that isn't swamped by regexp howtos.

[* ] having said that, if it's compiled to a dfa then it might not be. a lot depends on the implementation... [edit] oh, and since a dfa-related package is a dependency my guess is that he can't display this info, because duplication will be lost in the transformation. interesting.

Nice suggestion and thanks for the compliment!

The inspiration for this work is the Regexp::Genex module from CPAN: http://search.cpan.org/dist/Regexp-Genex/ -- though it uses a random-walk approach for character classes, instead of enumerating all possibilities.

regex-tdfa was only really used for parsing regexes, so it's certainly possible to find duplicates. That said, piping the output to "|perl -pe 's/.*\t//' | sort | uniq -d" is quite usable too. :-)

Anyone aware of something which does the exact opposite: given a list of strings generate a regex which matches all, and only those strings? The shorter the regex the better.

Unfortunately, the problem of finding a minimally equivalent regex from an /alt1|alt2|alt3|.../ form is known to be PSPACE-complete ( http://www.computer.org/portal/web/csdl/doi/10.1109/SWAT.197... ), as well as not finitely axiomatizable ( http://www.sciencedirect.com/science/article/pii/S0304397597... ).

That means the naïve SMT-solver-based approach in genex will not apply to this problem... Links/suggestions to relevant research welcome! :-)

Well goddamn. Thanks for the links :-)

genex '(o|O|0)(_)(o|O|0)'

Reply on news.ycombinator.com