5 ms·

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

17 points by draegtun 15y ago

Jun8 15y ago
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.
- bartonfink 15y ago
  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?
- audreyt 15y ago
  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"]
kordless 15y ago
genex '(o|O|0)(_)(o|O|0)'
andrewcooke 15y ago
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.
- audreyt 15y ago
  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/ 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. :-)
groks 15y ago
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.
- audreyt 15y ago
  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.1972.29 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/S0304397597001047 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! :-)
  - groks 15y ago
    Well goddamn. Thanks for the links :-)

17 points by draegtun 15y ago

Jun8 15y ago

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.

bartonfink 15y ago
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?
audreyt 15y ago
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"]

kordless 15y ago

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

andrewcooke 15y ago

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.

audreyt 15y ago
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/ 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. :-)

groks 15y ago

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.

audreyt 15y ago
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.1972.29 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/S0304397597001047 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! :-)
- groks 15y ago
  Well goddamn. Thanks for the links :-)