On Wed, 28 Aug 2002, Deven T. Corzine wrote: : I'd like to do that, if I can find the time. It would be interesting to : make a small experimental prototype to see if DFA construction could really : improve performance over backtracking, but it would probably need to be a : very restricted subset of regex operations to test the idea...
That'd be cool. : However, while I'm still on perl6-language, I have two language issues to : discuss first: : : (1) Can we have a ":study" modifier in Perl 6 for patterns? : : It could be a no-op if necessary, but it could take the place of Perl 5's : "study" operator and indicate that the programmer WANTS the pattern : optimized for maximum runtime speed, even at the cost of compile time or : memory. (Hey, how about a ":cram" modifier for extreme optimization? :-) Well, "studied" isn't really a property of a pattern--it's a property of a string that knows it will have multiple patterns matched against it. One could put a :study on the first pattern, but that's somewhat deceptive. : (2) Would simple alternation impede DFA-style optimizations? : : Currently, a pattern like (Jun|June) would never match "June" because the : "leftmost" match "Jun" would always take precedence, despite the normal : "longest-match" behavior of regexes in general. This example could be : implemented in a DFA; would that always be the case? Well, "June" can match if what follows fails to match after "Jun". : Would it be better for the matching of (Jun|June) to be "undefined" and : implementation-dependent? Or is it best to require "leftmost" semantics? Well, the semantics shouldn't generally wobble around like that, but it'd be pretty easy to let them wobble on purpose via pragma (or via :modifier, which are really just pragmas that scope to regex groups). Larry
