Variable order regex syntax

Question

Is there a way to indicate that two or more regex phrases can occur in any order? For instance, XML attributes can be written in any order. Say that I have the following XML:

<a href="home.php" class="link" title="Home">Home</a>
<a href="home.php" title="Home" class="link">Home</a>

How would I write a match that checks the class and title and works for both cases? I'm mainly looking for the syntax that allows me to check in any order, not just matching the class and title as I can do that. Is there any way besides just including both combinations and connecting them with a '|'?

Edit: My preference would be to do it in a single regex as I'm building it programatically and also unit testing it.

Answer 1

The easiest way would be to write a regex that picks up the <a .... > part, and then write two more regexes to pull out the class and the title. Although you could probably do it with a single regex, it would be very complicated, and probably a lot more error prone.

With a single regex you would need something like

<a[^>]*((class="([^"]*)")|(title="([^"]*)"))?((title="([^"]*)")|(class="([^"]*)"))?[^>]*>

Which is just a first hand guess without checking to see if it's even valid. Much easier to just divide and conquer the problem.

Answer 2

An first ad hoc solution might be to do the following.

((class|title)="[^"]*?" *)+

This is far from perfect because it allows every attribute to occur more than once. I could imagine that this might be solveable with assertions. But if you just want to extract the attributes this might already be sufficent.

Answer 3

No, I believe the best way to do it with a single RE is exactly as you describe. Unfortunately, it'll get very messy when your XML can have 5 different attributes, giving you 125 (I think, it's been quite a while since I did permutations and combinations :-) different REs to check.

On the other hand, I wouldn't be doing this with an RE at all since they're not meant to be programming languages. What's wrong with the old fashioned approach of using an XML processing library?

If you're required to use an RE, this answer probably won't help much, but I believe in using the right tools for the job.

Answer 4

This is one of the many reasons regexes are not suited to parsing XML or HTML.

Answer 5

You could use named groups to pull the attributes out of the tag. Run the regex and then loop over the groups doing whatever tests that you need.

Something like this (untested, using .net regex syntax with the \w for word characters and \s for whitespace):

<a ((?<key>\w+)\s?=\s?['"](?<value>\w+)['"])+ />

Answer 6

If you want to match a permutation of a set of elements, you could use a combination of back references and zero-width negative forward matching.

Say you want to match any one of these six lines:

123-abc-456-def-789-ghi-0AB
123-abc-456-ghi-789-def-0AB
123-def-456-abc-789-ghi-0AB
123-def-456-ghi-789-abc-0AB
123-ghi-456-abc-789-def-0AB
123-ghi-456-def-789-abc-0AB

You can do this with the following regex:

/123-(abc|def|ghi)-456-(?!\1)(abc|def|ghi)-789-(?!\1|\2)(abc|def|ghi)-0AB/

The back references (\1, \2), let you refer to your previous matches, and the zero width forward matching ((?!...) ) lets you negate a positional match, saying don't match if the contained matches at this position. Combining the two makes sure that your match is a legit permutation of the given elements, with each possibility only occuring once.

So, for example, in ruby:

input = <<LINES
123-abc-456-abc-789-abc-0AB
123-abc-456-abc-789-def-0AB
123-abc-456-abc-789-ghi-0AB
123-abc-456-def-789-abc-0AB
123-abc-456-def-789-def-0AB
123-abc-456-def-789-ghi-0AB
123-abc-456-ghi-789-abc-0AB
123-abc-456-ghi-789-def-0AB
123-abc-456-ghi-789-ghi-0AB
123-def-456-abc-789-abc-0AB
123-def-456-abc-789-def-0AB
123-def-456-abc-789-ghi-0AB
123-def-456-def-789-abc-0AB
123-def-456-def-789-def-0AB
123-def-456-def-789-ghi-0AB
123-def-456-ghi-789-abc-0AB
123-def-456-ghi-789-def-0AB
123-def-456-ghi-789-ghi-0AB
123-ghi-456-abc-789-abc-0AB
123-ghi-456-abc-789-def-0AB
123-ghi-456-abc-789-ghi-0AB
123-ghi-456-def-789-abc-0AB
123-ghi-456-def-789-def-0AB
123-ghi-456-def-789-ghi-0AB
123-ghi-456-ghi-789-abc-0AB
123-ghi-456-ghi-789-def-0AB
123-ghi-456-ghi-789-ghi-0AB
LINES

# outputs only the permutations
puts input.grep(/123-(abc|def|ghi)-456-(?!\1)(abc|def|ghi)-789-(?!\1|\2)(abc|def|ghi)-0AB/)

For a permutation of five elements, it would be:

/1-(abc|def|ghi|jkl|mno)-
 2-(?!\1)(abc|def|ghi|jkl|mno)-
 3-(?!\1|\2)(abc|def|ghi|jkl|mno)-
 4-(?!\1|\2|\3)(abc|def|ghi|jkl|mno)-
 5-(?!\1|\2|\3|\4)(abc|def|ghi|jkl|mno)-6/x

For your example, the regex would be

/<a href="home.php" (class="link"|title="Home") (?!\1)(class="link"|title="Home")>Home<\/a>/

Answer 7

You can create a lookahead for each of the attributes and plug them into a regex for the whole tag. For example, the regex for the tag could be

<a\b[^<>]*>

If you're using this on XML you'll probably need something more elaborate. By itself, this base regex will match a tag with zero or more attributes. Then you add a lookhead for each of the attributes you want to match:

(?=[^<>]*\s+class="link")
(?=[^<>]*\s+title="Home")

The [^<>]* lets it scan ahead for the attribute, but won't let it look beyond the closing angle bracket. Matching the leading whitespace here in the lookahead serves two purposes: it's more flexible than matching it in the base regex, and it ensure that we're matching a whole attribute name. Combining them we get:

<a\b(?=[^<>]*\s+class="link")(?=[^<>]*\s+title="Home")[^<>]+>[^<>]+</a>

Of course, I've made some simplifying assumptions for the sake of clarity. I didn't allow for whitespace around the equals signs, for single-quotes or no quotes around the attribute values, or for angle brackets in the attribute values (which I hear is legal, but I've never seen it done). Plugging those leaks (if you need to) will make the regex uglier, but won't require changes to the basic structure.

Answer 8

Have you considered xpath? (where attribute order doesn't matter)

//a[@class and @title]

Will select both <a> nodes as valid matches. The only caveat being that the input must be xhtml (well formed xml).