From: Philippe Verdy (verdy_p@wanadoo.fr)
Date: Tue Oct 09 2007 - 18:11:22 CDT
Hans Aberg [mailto:haberg@math.su.se] wrote:
> REs can be rewritten into DFAs, and vice versa. And taking the
> language complement of a DFA is easier than that of a RE.
May be, but the production of the DFA is prohibitive. I've implemented
negated regexps without flattening the transition graph into asingle-sate
DFA.
In fact, my implementation can be seen as a DFA too (it just has more state
variables, but I can determine which one to use in a deterministic way and a
bounded time that does not depend much on the regexp length, but only on the
number of alternations in the source regexp). It does not
explodecombinatorially like traditional DFA implementation and the needed
resource for storing the complied transition graph only grows linearily, not
exponsentially, with the source regexp length, meaning that it stays within
the limits of the data cache, and avoids almost all misses (the matcher
benefits from data locality). And I don't need any backtracking.
Anyway, you're still not replying to the question: which is the expected
ordering for the returned matches? I absolutely don't care if you use a DFA
or not. This is important because it affects the way a matcher that needsto
recognize negated regexps will return its results (because if you want the
"complementary", the order of analysis of the transition graph changes
completely to keep the condition about the order of results.
(1) the fact that the transitions from a node in the graph are fully
determined from a single variable does NOT affect the system, given that
even in a DFA there's an order (and in fact you can't build easily (without
exploding the graph size); the full determination of transitions that
allowpossible matches can't be determined without first testing them ALL one
by one, due to the dynamic character classes and to the counted aggregates,
in order to get the full set of transition to use and advance; and this is
NOT backtracking as the decision is based ONLY on the current atomic
symbol).
(2) negating a regexp (or subrexp) also affects its quantification (for its
terminal aggregate), when the terminal node in the NFA contains a loop (so
if you have a priority based on longest matches for the output, the negated
regexp will need to reverse this priority for its smallest matches.
This archive was generated by hypermail 2.1.5 : Tue Oct 09 2007 - 18:14:06 CDT