Sherborn

Using regular expressions to crack the inconsistencies of a century-old bibliography and bring an important compendium of zoological taxonomy into the semantic web: Suzanne C. Pilsk et al., "Unlocking Index Animalium: From paper slips to bytes and bits."

Another opportunity to go Conrad on someone else's code

Remy Porter and RJ reveal a regular expression that might be longer than the texts it's matched against.

Compact

Lea Verou explains some simple, clever ways to do your own bitpacking in JavaScript, including a sneaky way to break up text into 16-character chunks with a regular expression match.

Taling to the duck

Harry Roberts offers coding conventions for writing CSS. His tip about pattern-matching selectors with regular expressions is nifty.

Regex mystery, once more

I spent some quality time with Friedl's Mastering Regular Expressions, and I'm beginning to get a better understanding of JavaScript's NFA regular expression engine. I dimly understand how the case I described in an earlier post sent the engine into backtracking perdition. I tested (but did not commit to the codebase) this version. It addresses the specific bad data case, but I don't think it's a comprehensive solution.




var PROBE_REGEX = /client\.org/;
var URL_REGEX = /^(http:\/\/)?(\w+\.?)*client\.org(.*)$/i;

stripUrlPrefix = function (url) {
 var regex = new RegExp(URL_REGEX);
 var result = jQuery.trim(url);
 if (result.search(PROBE_REGEX) == -1) {
     return result;
 }
 var matches = regex.exec(result);
 if (matches) {
     return matches[3];
 } else {
     return result;
 }
}

It's one or both of the quantified expressions (\w+\.?)* and (.*) that are responsible for the performance issues.

Return of the regex mystery

The little one-off function that I wrote to extract the file name from a URL still continues to baffle. Rekha, in the course of reviewing some other code and functionality, threw a random string of letters (no punctuation) at it, which caused the browser's script engine to time out. I rewrote the code somewhat, but even this version takes about 30 seconds to complete, when given a string like "asdfghjklasdfghjklasdfghjkl":

var URL_REGEX = /^(http:\/\/)?(\w+\.?)*client\.org(.*)$/i;

stripUrlPrefix = function (url) {
    var regex = new RegExp(URL_REGEX);
    var result = jQuery.trim(url);
    var matches = regex.exec(result);
    if (matches) {
        return matches[3];
    } else {
        return result;
    }
}

Another regex issue

For a bit of code designed to block all HTML tags from an input string, I picked up the following regular expression from Friedl, Mastering Regular Expressions, 3/e:

<("[^"]*"|'[^']*'|[^'">])*>

As in:

if (inputString.match(/<("[^"]*"|'[^']*'|[^'">])*>/)) {
    CLIENT.Utilities.addValidationMessage($(this), 'No HTML tags, please.');
    isValid = false;
}

Unfortunately, colleague Jared points out that ill-formed HTML tags will pass this validation, and colleague Jason demonstrated that browsers (at least some, under certain conditions) will (more or less) render the ill-formed HTML. Jared's examples:

<a href="bad link" attr'>click me</a attr=">

Since this code is used for an internal app where users aren't actively trying to clobber things, we've chosen to live with the situation that the fishy markup can slip through.

Regex mystery

One little bit of the app that I've been working on for the past several months is an HTML text box where the editor/producer can enter a relative URL that identifies an image file. But, in reality, it's common for the editor to have an absolute URL that he/she is pasting into the text box (maybe context-clicking to grab a URL from elsewhere on the web site), so one of the bits of processing to be done in JavaScript is to remove the scheme and server name from the URL. My client has multiple media servers within its client.org domain. So I wrote this tiny function, which in essence is nothing but

var URL_REGEX = /(http:\/\/)?(\w+\.{0,1})*client\.org/i;

function stripUrlPrefix (url) {
    return url.replace(URL_REGEX, '');
}

stripUrlPrefix() removes the scheme, if present, and the server name, and it usually works like a champ.

However, Tony on the testing team found that the following input string (a real path name from one of our servers) sends the regex engines in IE 7 and Firefox 3 completely out to lunch:

/images/ap//AP_News_Wire:_World_News/3_Australia_Thirsty_Camels.sff_300.jpg

On my middle-of-the-line Windows XP laptop, IE 7 takes about 10 minutes to execute stripUrlPrefix(), given this input string; Firefox just pegs the CPU and never does return. Jason is going to give this code a spin on Chrome to see what happens.

I have somehow stumbled into some kind of backtracking morass with a regex that looks pretty vanilla to me, and an input string that's likewise not too gnarly.

It turns out that we can fix the problem by trimming leading whitespace from the input and adding a beginning of string anchor to the regular expression, thus:

var URL_REGEX = /^(http:\/\/)?(\w+\.{0,1})*client\.org/i;

I haven't checked to see whether explicitly using the RegExp class would make a difference.

Oracle numeric test

A colleague and I found ourselves needing to write a one-off bit of SQL that used a character column in a join condition. The character column is performing double duty, sometimes acting as a (numeric) foreign key, and sometimes holding other data.

I was perplexed by the lack of some kind of "is numeric" test in Oracle's dialect of SQL. I scrounged around forums and found something that I thought would work, but my colleague finally put me straight and we used this condition:

REGEXP_LIKE(char_column, '^[[:digit:]]+$')

All that is the case

I'm working on a short piece of code to capitalize all the initials in a given sentence (headlines for news stories from a wire service, to be specific), in order to match house style. At first, I was a little surprised that I couldn't find a Java class to do most of the work for me. But once I waded into the actual sentences that I had to process, with their variations and exceptions, I came to the conclusion that some degree of RYO was called for. Here's my current draft:

import java.util.regex.*;

* * * 

    private String capitalizeAllInitials(String text)
    {
        //capitalize the first letter of every word in the passed text
        //(including little words like "a," "the," "and," "to")
        //also capitalize words in quoted and hyphenated phrases
       
        //NOTES: The pattern requires a leading space; I have found that
        //ingested stories already capitalize the first word of the title.

        Pattern p = Pattern.compile("(-|( (`|\\\"|\\\')?))([a-z])");
        Matcher m = p.matcher(text);

        StringBuffer sb = new StringBuffer();
        while (m.find())
        {
            m.appendReplacement(sb, m.group(1) + m.group(4).toUpperCase());
        }
        m.appendTail(sb);

        return sb.toString();
    }

As the comments note, this code will handle ordinary words (The quick brown fox jumps over the lazy dog becomes The Quick Brown Fox Jumps Over The Lazy Dog), hyphenated phrases (Senator proposes pay-as-you-go plan becomes Senator Proposes Pay-As-You-Go Plan), and quoted phrases (Accused confesses, "we did it" becomes Accused Confesses, "We Did It") with single, double, or backquotes. The code assumes that the first word is already capitalized, so if that's not the case with you, you would need to add a ^ to the regular expression.

This code also doesn't handle the common forms of title casing, whereby articles, prepositions, and other small words are not capitalized. Also, this code capitalizes proper names and trademarks indiscriminately.

I detect a pattern here

I've had Coding Horror's post on regular expressions bookmarked for a while now, just waiting for the chance to take a few minutes to type "Right on!" For certain validation problems, a regex is the only way to go. At Vovici, I used them with the RegularExpressionValidator control to ensure that a text box was, say, filled in with a valid e-mail address or with a URL from a particular domain. And about once a quarter my colleague Cap would IM me with a request for a quick regex consult.

You can also use a regex to make sure that a text box is filled in with a valid date (in, MM-DD-YY, format, for instance), but in this case you're usually better off using a specialized date picker, for instance, one that presents a pop-up monthly calendar and all the user has to do is click a number.

The big problem with regular expressions is the proliferation of implementations and all the bells and whistles that come with. For example, we found a particularly useful pattern at RegExLib.com to match e-mail addresses that include the display-name part (as in "User, Joe" <joe.user@example.com>), but the pattern wasn't useful for client-side validation because it used features that depended on a browser-specific regex engine. So a reference book like Jeffrey Friedl's Mastering Regular Expressions is really handy to help you keep track of platform-specifics. By all means, use the contributed patterns form a site like RegExLib.com, but don't put a pattern into production that you don't understand yourself.

Another tool that you may find useful is Ivaylo Badinov's test harness for regular expressions, REGex TESTER.

Just to amplify a couple of Jeff Atwood's points:

Do not try to do everything in one uber-regex. I know you can do it that way, but you're not going to. It's not worth it. Break the operation down into several smaller, more understandable regular expressions, and apply each in turn. Nobody will be able to understand or debug that monster 20-line regex, but they might just have a fighting chance at understanding and debugging five mini regexes.

This is also good advice for smaller patterns, too. If you're trying to recognize U.S. telephone numbers, for instance, start with a pattern that recognizes area codes (something like /\d{3}/) and one that recognizes exchange and number body (/\d{3}-\d{4}/) and then put the two patterns together (into /(\d{3}-)?\d{3}-\d{4}/).

Regular expressions are not Parsers. Although you can do some amazing things with regular expressions, they are weak at balanced tag matching. Some regex variants have balanced matching, but it is clearly a hack—and a nasty one. You can often make it kinda-sorta work, as I have in the sanitize routine. But no matter how clever your regex, don't delude yourself: it is in no way, shape or form a substitute for a real live parser.

Exactly. Regular expressions are good for problems that call for a bounded degree of nesting: breaking up a file of XML into tokens that represent the element and attribute names, for instance. These problems are what the language translation people would call lexical analysis. For problems that permit arbitrarily deep nesting, like parsing the stream of XML tokens into a document tree, ensuring that each tag is properly closed and nested, you're doing syntactic analysis, and you need a tool like yacc.