Hacker News Reader

Comment by joosters | Hacker News Reader

It's a shame that the regex API doesn't seem to provide a way to indicate which part of a (?:foo|bar|...) matched. The underlying regex code must know this. A large part of the article is coming up with workarounds to solve this problem.

View on HN

PCRE actually provides this information. There's a feature called backtracking control verbs, and one of those is (* MARK:NAME). You could put a (* MARK:A), (* MARK:B), etc at the end of every path and PCRE would tell you which of the paths was taken. However PHP does not expose this information - just like it does not expose the (?C) callout feature :(

Maybe I should implement those two things.

Note: There is no whitespace between * and MARK, but if I remove it HN formats it as an italic string.

It could probably be done by actually doing a replacement. Make all but the first group in each route non-capturing, and then replace it with something like " $1 $2 $3 .... $n", and count the spaces. You'd have to then do another regex just for that route with all groups capturing. So for 100 routes with 9 placeholders each you would do 1 regex replace that worst-case had to populate 100 groups, and then a second replace for the identified route to populate 9 capturing groups. Does that make sense?

Awesome! I never knew perl (compatible) regexes had this, thanks. One day I will force myself to read the whole perlre man page...

Perl (5.18, at least) does let you (ab)use named groups to provide match-part identification.

Given `(?<g1>Sat)urday|(?<g2>Sun)day`, and a successful match, either `$+{g1}` or `$+{g2}` will hold the relevant subpart.

Quickie demo script:

    my $re = "(?<g1>Sat)urday|(?<g2>Sun)day";
    foreach my $d (qw(Friday Sunday Thursday Saturday)) {
        my $out = '<default>';
        if ($d =~ /$re/) {
            if ($+{g1}) { $out = 'Saturday' }
            elsif ($+{g2}) { $out = 'Sunday' }
        }
        print "$d routes to $out\n";
    }

Nice to see code. :-)

Perl 5.10 from 2007 supports named captures. (Google confirmed that.)

Edit: nikic in the parallel comment is correct, named captures are affected the same way in Perl's regexp engine with ?|. (Google perlre and search for ?|.)

Not sure I understand this comment. Your code snippet uses named subpatterns, but not within a (?| group. The interesting question is whether you can combined those two. Without (?| you can use named captures in PCRE as well (there's just little point in this context as a non-named capture would do equally well and be more efficient.)

Oh, hmm, yeah, fair point. I was mistakenly assuming that using named captures would obviate the creation of N spurious capture groups but a quick benchmark proves that horribly wrong. Sorry all!

> It's a shame that the regex API doesn't seem to provide a way to indicate which part of a (?:foo|bar|...) matched. The underlying regex code must know this.

As lmm points out (I think), one can get a big advantage precisely by not requiring the regex code to know this. (Regexes are 'really' DFAs, and a DFA that makes it to its start state not just does not but can not know how it got there.) The more power one gives regexes, the less, well, regular they are, and the slower they become to match.

A DFA can give you more than just a yes/no decision, though sometimes they're narrowly defined as only machines that give yes/no decisions. But if you have multiple accept states and number or label the states, a DFA can report not only 'accept' but 'accept' plus the label of the accepting state (this could be seen as a special case of a Moore machine, in which you only care about the last output).

You'd have to compile the DFA differently, of course. A really simple version would just compile each alternation into its own DFA separately, and then chain them together with "try each in sequence". That's still a DFA, so it's not a matter of a different class of computations, though it's often slower by a constant factor (due to not being able to share any information between the alternations when matching them).

You can compile the DFA exactly as you would with a single regex as input, just labeling each alternative's accept state differently. The subset construction would put a set of these labels on each DFA accepting state. When I coded this I had it break these ties by picking the minimum label in each set, so earlier alternatives win:

https://github.com/darius/sketchbook/blob/master/lex/dfa_nfa...

Good point: a DFA can do exactly what joosters asked, namely, distinguish between "matched regex '(a|b)' to input 'a'" and "matched regex '(a|b)' to input 'b'". However, it may be worth noting—as I'm sure you know, but others may not—that there is no way for even a juiced-up DFA to say, for example, how many a's were actually in the input when the regex is 'a * ' (spaces to fool the Markdown processor).

P.S. I might as well mention that I obviously meant to refer to a DFA reaching its end, rather than start, state.

See Laurikari's paper on Tagged DFAs. It solves exactly this problem without impacting O(n) matching performance.

Thanks; I hadn't heard of this. To save others hunting down the link, here's a StackOverflow question with a (very little) discussion, a link, and related code:

http://stackoverflow.com/questions/3287860/what-is-a-tagged-...

Not quite what you asked for, but how about this?

  ~^(?|
      xx(x)/user/([^/]+)/(\d+)
    | x(xx)/user/(\d+)
    | (xxx)/user/([^/]+)
  )$~x

Then just prepend 'xxx' to the front of uri in the call to preg_match. Now the second entry in matches tells you which handler, so for example for uri = '/user/nikic/42' you pass 'xxx/user/nikic/42' and get back 'xxx/user/nikic/42', 'x', 'nikic', and '42' where that 'x' tells you it's the first handler.

I'm not an expert in how php does REs but I imagine there may be a way to use preg_replace or similar to replace the first '/' in the uri with 'x', 'xx', or 'xxx' and still get a the groups returned for the matches for user and id say. This could save a potentially costly string creation.

You could use a lexer generator instead of regular expressions, since this is exactly what lexer generators do.

You can use a lexer, yes - but any fast lexer implementation in a high-level language will actually use the very same technique described here. Generating a character-comparison + goto based FSM works great in C, but has bad performance in PHP (and other dynamic languages).

There's a common misconception that regular expressions are slow, but in many cases they offer much better performance than a manual implementation with lots of strpos etc. In the end PCRE does the same thing, but in C and using a JIT compiler. Apart from very simple cases you don't have a chance to keep up with that using PHP code.

Reply on news.ycombinator.com