4 ms·

I’ve often wondered why there isn't a tool that generates regex for you automatically when you feed it a number of similar strings. Is this too complicated math

I’ve often wondered why there isn't a tool that generates regex for you automatically when you feed it a number of similar strings. Is this too complicated mathematically (even for machine-learning), or does such a thing actually exist (and I just don’t know about it)? Imagine you want to write a regex that captures hex values such as 0xC0D3. You enter a few sample values (the more you enter, the more concise the regex which the generator will spit out) and the generator should easily discover that all your values start with 0x followed by exactly four digits 0-9 or a-f and give you a (albeit maybe not the best, or several) expression it can. Bonus points if it indeed explains in natural language each part of the regex it generated... I’d imagine this would also be a great tool for learning regex, a sort-of “learning by reverse-engineering” if you will. I seem to need regex only once every two years or so, which is not enough to learn it properly or, if I did, to retain it. So such a tool would be awesome.

TFortunato 6y ago
Something like this, perhaps? http://regex.inginf.units.it/ http://regex.inginf.units.it/
- boogies 6y ago
  Interesting, though it seems like it might take more time to create enough examples for useful results than to just learn regex (eg. complete https://regexone.com/ https://regexone.com/). > The quality of the solution depends on a number of factors, including size and syntactical properties of the learning information. > The algorithms embedded in this experimental prototype have always been tested with at least 25 matches over at least 2 examples. It is very unlikely that a smaller number of matches allows obtaining an useful solution.
kazinator 6y ago
A DFA-based regex engine will spit out an optimal state machine if you give it a regex which just combines all your inputs with the disjunction: 0xC0D3|0xC0FD|...|0xBEEF For example, NFA-DFA subset construction algorithm will implicitly figure out that every branch starts with 0x, and so the initial state will have only a single transition out of it on the character 0, and the next state on the character x. If we feed it every 16 bit hex string from 0x0000 to 0xFFFF, it should reduce to just 7 states: S0 -[0]-> S1 -[x]-> S2 -[01234569789ABCDEF]-> S3 ... What you need is just a way to convert the compiled DFA to a regex, which you could then take in place of the original catenation. The transitions on multiple characters have to be intelligently converted to readable classes like [0-9A-F]. Now suppose we feed it every 0xXXXX string except 0xFFFE. What that simply means is that the last state transition will not include the F character. In that state, if the next input character is F, the machine errors out. I'm sure there are issues with this idea that have to be solved. It's a famous fact of DFA construction that a case insensitive match like "[Ff][Oo][Oo]..." leads to an exponential explosion of states.
ufo 6y ago
The search keyword you might want to use for this is "program synthesis".
TeMPOraL 6y ago
Emacs has something similar, for generating compressed matchers from examples you provide. Though this operates on a closed-world principle: the result will match your examples, but only your examples. ELISP> (message (regexp-opt '("0x12" "0x13" "0x2f" "0x1d" "0xcc"))) "\\(?:0x\\(?:1[23d]\\|2f\\|cc\\)\\)" (in *Messages* buffer) \(?:0x\(?:1[23d]\|2f\|cc\)\) (Note that Emacs' regex syntax is slightly different than PCRE.)

TFortunato 6y ago

Something like this, perhaps? http://regex.inginf.units.it/ http://regex.inginf.units.it/

boogies 6y ago
Interesting, though it seems like it might take more time to create enough examples for useful results than to just learn regex (eg. complete https://regexone.com/ https://regexone.com/). > The quality of the solution depends on a number of factors, including size and syntactical properties of the learning information. > The algorithms embedded in this experimental prototype have always been tested with at least 25 matches over at least 2 examples. It is very unlikely that a smaller number of matches allows obtaining an useful solution.

kazinator 6y ago

A DFA-based regex engine will spit out an optimal state machine if you give it a regex which just combines all your inputs with the disjunction: 0xC0D3|0xC0FD|...|0xBEEF For example, NFA-DFA subset construction algorithm will implicitly figure out that every branch starts with 0x, and so the initial state will have only a single transition out of it on the character 0, and the next state on the character x. If we feed it every 16 bit hex string from 0x0000 to 0xFFFF, it should reduce to just 7 states: S0 -[0]-> S1 -[x]-> S2 -[01234569789ABCDEF]-> S3 ... What you need is just a way to convert the compiled DFA to a regex, which you could then take in place of the original catenation. The transitions on multiple characters have to be intelligently converted to readable classes like [0-9A-F]. Now suppose we feed it every 0xXXXX string except 0xFFFE. What that simply means is that the last state transition will not include the F character. In that state, if the next input character is F, the machine errors out. I'm sure there are issues with this idea that have to be solved. It's a famous fact of DFA construction that a case insensitive match like "[Ff][Oo][Oo]..." leads to an exponential explosion of states.

ufo 6y ago

The search keyword you might want to use for this is "program synthesis".

TeMPOraL 6y ago

Emacs has something similar, for generating compressed matchers from examples you provide. Though this operates on a closed-world principle: the result will match your examples, but only your examples. ELISP> (message (regexp-opt '("0x12" "0x13" "0x2f" "0x1d" "0xcc"))) "\\(?:0x\\(?:1[23d]\\|2f\\|cc\\)\\)" (in *Messages* buffer) \(?:0x\(?:1[23d]\|2f\|cc\)\) (Note that Emacs' regex syntax is slightly different than PCRE.)