News for hackers. Stuff that matters.
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...