3 ms·
> 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.
by JadeNB 13y ago
> 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.
- deleted 13y ago[deleted]
- _delirium 13y agoA 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).
- abecedarius 13y agoYou 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.py#L74 https://github.com/darius/sketchbook/blob/master/lex/dfa_nfa...
- JadeNB 13y agoGood 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.
- colanderman 13y agoSee Laurikari's paper on Tagged DFAs. It solves exactly this problem without impacting O(n) matching performance.
- JadeNB 13y agoThanks; 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-dfa http://stackoverflow.com/questions/3287860/what-is-a-tagged-...