Regex Guru

Monday, 27 July 2009

Magically Generating Regular Expressions

Filed under: The Guru's Kitchen — Jan Goyvaerts @ 14:23

A lot of people are looking for a program that can automatically generate regular expressions for them. The program would only take examples of valid matches as input, and produce the proper regular expression as output, inferring the user’s idea of “proper” as by magic. It is certainly one of the more frequent feature request I receive for RegexBuddy. Unfortunately, no computer program will ever be able to generate a meaningful regular expression based purely on a list of valid matches. Let me show you why.

Suppose you provide the examples 111111 and 999999. Which regular expression should the computer generate?

  1. A regex matching exactly those two examples: (?:111111|999999)
  2. A regex matching 6 identical digits (\d)\1{5}
  3. A regex matching 6 ones and nines [19]{6}
  4. A regex matching any 6 digits \d{6}
  5. Any of the above four, with word boundaries, e.g. \b\d{6}\b
  6. Any of the first four, not preceded or followed by a digit, e.g. (?<!\d)\d{6}(?!\d)

As you can see, there are many ways in which examples can be generalized into a regular expression. The only way for the computer to build a predictable regular expression is to require you to list all possible matches. Then it could generate a search pattern that matches exactly those matches, and nothing else. Usually, providing an exhaustive list of matches is exactly what we’re trying to avoid. And when you do have an exhaustive list of all possible matches, an optimized plain text search processing the whole list at once will be as fast as or faster than a regex search. The plain text search can be optimized to scan the text only once, without backtracking like regular expressions do

If you don’t want to list all possible matches, you need a higher-level description. Instead of providing a long list of 6-digit numbers, you simply tell the program to match “any six digits”. The regular expression syntax itself is one way to provide such a description. Regular expressions are powerful enough that they can describe any text that doesn’t depend on its context. “Any six digits” is written as \d{6} in regular expression syntax.

To make the higher-level description easy to work with, it needs domain knowledge. Matching a date between January 1st and March 31st is much easier if your tool or language knows what a date is. This is where regular expressions fall short. Regular expressions only know about characters. Essentially, a regular expression describes which character comes next, or which characters are allowed next.

This wouldn’t be the regex guru blog if there story ended here. Though pure auto-generation of regexes isn’t feasible, there have to be better ways of creating text patterns than spelling things out character by character. I don’t mean trying to make regular expressions more accessible by coming up with a more verbose syntax, as some people have tried. Microsoft would be pushing COBOL# instead of C# if wordiness was key.

I mean a tool that works at a higher level. Something that allows you to say “a number between 1 and 12” instead of “a digit between 1 and 9, or a digit 1 followed by a digit between 0 and 2”. That’s what I’ve been working on for the past two years. It’s the reason why there haven’t been any major Just Great Software releases since 2007.

RegexMagic is a brand new product from Just Great Software. Its purpose is to make it easier to create regular expressions, but without using the regular expression syntax. You can tell RegexMagic you want a date between January 1st and March 31st, and that you want it in yyyy-mm-dd format, simply by selecting the “date and time” pattern and setting its options. Once you’ve done that, RegexMagic magically spits out your regular expression. Version 1.0 has patterns for characters, numbers, dates, times, email addresses, URLs, credit card numbers, national IDs, and more.

In practice, most of the regular expressions you want won’t neatly fit into one of RegexMagic’s predefined patterns. If you mark 1.2.12 as a whole, RegexMagic will guess it’s a date (1 February 2012, German style), rather than a product version number. If want a regex that matches 3 numbers delimited by dots, mark the numbers and the dots separately into 5 fields. Select the integer pattern for the numbers and the literal text pattern for the dots. Then RegexMagic can again magically spit out your regex, even if it didn’t magically read your mind.

Once you have created your higher-level description in RegexMagic, which is called a RegexMagic formula, editing and customizing that description is trivial compared to editing a regex. If you decide that the parts of a version should be restricted to values between 1 and 255, simply set the limits on the integer patterns, and regenerate the regular expression.

Just like RegexBuddy, RegexMagic supports nearly all popular regular expression flavors. Select your flavor, and RegexMagic makes sure to generate a regular expression that works with it. RegexMagic can also generate snippets in many programming languages that you can copy and paste directly into your source code to implement your regular expression. RegexMagic uses the same source code templates as RegexBuddy.

Though RegexMagic is mainly aimed at people new to regular expressions, experts on regular expressions may still find RegexMagic useful to quickly generate more complicated regexes. E.g. if you need to match numbers between 256 and 512, and all you can use is a single regex, it takes less than a minute to make RegexMagic spit out 51[0-2]|50[0-9]|[34][0-9]{2}|2[6-9][0-9]|25[6-9]. Though such a regex is conceptually very simple, it is quite a chore to build up by hand.

For more details, a trial download, and an introduction discount, please visit RegexMagic’s web site.

2 Comments

  1. First, let me thank you for providing an excellent reference site for REGEX. Your site is the best site I have discovered when learning about regular expressions.

    Next, about your comment. I don’t think a computer will ever be able to get as good as a human at picking out data, but I do believe there is a lot of room for growth.

    For example, I am often faced with having to find information in a dynamic web page and pull that information out using regular expressions. Many times the site may change around a bit and cause my anchors to break down.

    When I look at the web page, my brain can very quickly pick out the information and extract it and I believe computer programs could do the same. Generally the content is located at the same location but the anchors have shifted. What I have done in the past is create a program to find what I’m looking for using a DISTINCT selection from MySQL. I can then see the anchors around what I am looking for and quickly adapt a new REGEX for that criteria.

    Your example was correct but to specific. I am never looking for a specific number but any phone number and that of course is the power of REGEX. During the creation of my website http://www.craigsrelisted.com, I had to find innovative ways to extract phone numbers that varied from (719) 555-1212 to seven 1 NNNNINE 5 5 five one 2 1 TWO.

    People will try to hide their numbers in the postings, so you have to get very creative and ask yourself why your brain can so quickly recognize it as a phone number and then figure out a way to adapt a REGEX to make it work.

    All the best,
    Jason

    Comment by Jason — Monday, 27 July 2009 @ 20:52

  2. RegexBuddy and the new RegexMagic are both ways of making sense of the regex “noise”. Martin Fowler also talks about doing understanding the noise with the ComposedRegex http://martinfowler.com/bliki/ComposedRegex.html

    Comment by boardtc — Thursday, 30 July 2009 @ 16:49

Sorry, the comment form is closed at this time.