6
\$\begingroup\$

I'm looking for a program such that, given a finite list of strings, can find short regexes to match exactly all of them and nothing else.

Since there are multiple languages that express regexes differently, there can correspondingly be multiple regex generators. Each answer must discuss regex generation in one langauge only (or a family of languages for which there is a direct correspondence between regexes in each of them).

\$\endgroup\$
  • 1
    \$\begingroup\$ @Arnauld Yeah, I thought the "exactly" made it clear enough. Edited. \$\endgroup\$ – ghosts_in_the_code May 19 at 11:55
  • \$\begingroup\$ Do you mean like matching 'dome' and 'home' with the regex (h|d)ome? \$\endgroup\$ – Krish May 19 at 12:03
  • 3
    \$\begingroup\$ Another useful feature of such a tool would be to generate a regex that matches all strings in a list A but not any of the strings in a list B, with undefined behavior for any other input. (This is what I would have needed to optimize this handcrafted answer.) \$\endgroup\$ – Arnauld May 19 at 20:48
  • 1
    \$\begingroup\$ @ghosts_in_the_code to write code implementing it without reducing it(code). \$\endgroup\$ – Victor VosMottor Jul 21 at 10:27
  • 1
    \$\begingroup\$ @VictorVosMottorthanksMonica oh yeah the regex generator doesn't have to be golfed \$\endgroup\$ – ghosts_in_the_code Jul 21 at 10:33
3
\$\begingroup\$

The Machine Learning Lab at the University of Trieste, Italy, wrote a web app to solve this exact problem, available at: Automatic Generation of Regular Expressions from Examples based on "genetic programming" and published a paper about it. Based on the fact that it had to come from the Machine Learning Lab of a university in Italy, and was worth publishing a paper about, it is probably a pretty hard problem to solve. Doesn't sound like the type of question for Code Golf SE, but I'm new here, so I wouldn't be the expert on that.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Welcome to the site. That's a cool approach to regex generation. Note, though, that the app isn't guaranteed to find the shortest possible regex. From the FAQ: '3. The generated regexes look unoptimized. Why? There are some optimization which could make a given regex appear better, e.g., [\d\d\.\d][\d\.]. Currently, our prototype does not apply any of these optimizations.' Nor will the generated regex match only the given strings and nothing else. You are right - this is a hard problem. \$\endgroup\$ – Dingus Aug 19 at 2:58
  • \$\begingroup\$ I didn't look into it, but the description of the website I linked does include "old version", so maybe there is a newer version which does apply the optimizations? I seem to remember the website looking different the first time I saw it than this time around, so maybe I really did link an old one... \$\endgroup\$ – Sam Aug 19 at 3:03
  • \$\begingroup\$ I believe I linked to the "Regex Generator" page, here is the "Regex Generator++" page: regex.inginf.units.it . I updated the post. I wonder if the ++ version does perform the optimizations... \$\endgroup\$ – Sam Aug 19 at 15:58
  • \$\begingroup\$ I believe that the ++ version does perform the optimizations. At least, in the regex golf section - which looks more similair in its UI to the ++ version - it has a stage when it is figuring out the Regex where it says "Optimizing..." \$\endgroup\$ – Sam Aug 19 at 19:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.