Great looking solutions you guys, but I actually have a few additional design constraints:
1. No perl code embedded in the regex. After demonstration of the prototype in perl, it will be implemented in the product using Java, so it must be compatible with the Java regex engine.
2. The regex should only have to be compiled once, so no rewriting of the regex string after starting to iterate through the matches.