Re: RegEx: AND operator

henry@spsystems.net (Henry Spencer)
14 Oct 2003 23:44:09 -0400

          From comp.compilers
Related articles
RegEx: AND operator nikt@wp.pl (jan) (2003-10-12)
Re: RegEx: AND operator vannoord@let.rug.nl (2003-10-13)
Re: RegEx: AND operator ahelin@student.oulu.fi (2003-10-13)
Re: RegEx: AND operator henry@spsystems.net (2003-10-14)
Re: RegEx: AND operator clint@0lsen.net (Clint Olsen) (2003-10-14)
Re: RegEx: AND operator nikt@wp.pl (jan) (2003-10-18)
Re: RegEx: AND operator nikt@wp.pl (jan) (2003-10-19)
| List of all articles for this month |
From: henry@spsystems.net (Henry Spencer)
Newsgroups: comp.compilers
Date: 14 Oct 2003 23:44:09 -0400
Organization: SP Systems, Toronto, Canada
References: 03-10-045
Keywords: lex
Posted-Date: 14 Oct 2003 23:44:09 EDT

  jan <nikt@wp.pl> wrote:
>The algorithms for translation of regex into NFA are popular; however,
>in none have I seen support for the AND (&) operator...


If you are willing to use NFA->DFA conversions, you can preprocess it out,
exploiting the identity x&y == ~(~x | ~y) and the straightforward DFA
implementation of the NOT operator.


>It might be
>implemented as another NFA that is run in the required range
>(eg. regex (a.* & ~abc)+ would make one NFA (a.*)+ and for each
>matched (a.*) it would test the other NFA: ~abc) but that's not a good
>solution...


With DFAs, or DFA simulation via a state set -- with any matching
algorithm that tracks all possible states simultaneously -- you can run
two matchers in parallel. You advance both of them one character at a
time, looking for a character where they both match or one of them
declares complete failure.


But with a backtracking implementation, as far as I know, there just
is no graceful way of implementing AND.
--
MOST launched 1015 EDT 30 June, separated 1046, | Henry Spencer
first ground-station pass 1651, all nominal! | henry@spsystems.net

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.