Re:Fast request routing using regular expressions
by JadeNB on Thursday February 20, 2014 @03:19PM
(#7273270)
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.
Re:Fast request routing using regular expressions
by abecedarius on Thursday February 20, 2014 @12:28PM
(#7272152)
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...
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).