Re:Fast request routing using regular expressions
by _delirium on Thursday February 20, 2014 @11:08AM
(#7271507)
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).
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...
Re:Fast request routing using regular expressions
by colanderman on Thursday February 20, 2014 @01:21PM
(#7272567)
See Laurikari's paper on Tagged DFAs. It solves exactly this problem without impacting O(n) matching performance.
Re:Fast request routing using regular expressions
by JadeNB on Thursday February 20, 2014 @03:38PM
(#7273391)
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-...
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.