Re: regular expression question

torbenm@diku.dk (=?iso-8859-1?q?Torben_=C6gidius_Mogensen?=)
10 Jun 2005 22:16:03 -0400

          From comp.compilers

Related articles
[4 earlier articles]
Re: regular expression question gvheurn@gmail.com (Gijs) (2005-06-09)
Re: regular expression question nicola.musatti@gmail.com (Nicola Musatti) (2005-06-09)
Re: regular expression question cfc@shell01.TheWorld.com (Chris F Clark) (2005-06-09)
Re: regular expression question snicol@apk.net (Scott Nicol) (2005-06-10)
Re: regular expression question snicol@apk.net (Scott Nicol) (2005-06-10)
Re: regular expression question d148f3wg02@sneakemail.com (Karsten Nyblad) (2005-06-10)
Re: regular expression question torbenm@diku.dk (2005-06-10)
Re: regular expression question skandgoe@gwdg.de (Skandinavisches Seminar) (2005-06-10)
Re: regular expression question mailbox@dmitry-kazakov.de (Dmitry A. Kazakov) (2005-06-12)
| List of all articles for this month |

From: torbenm@diku.dk (=?iso-8859-1?q?Torben_=C6gidius_Mogensen?=)
Newsgroups: comp.compilers
Date: 10 Jun 2005 22:16:03 -0400
Organization: Department of Computer Science, University of Copenhagen
References: 05-06-045
Keywords: lex

"Gijs" <gvheurn@gmail.com> writes:


> Can anyone tell me how
> to create a regular expression that matches all except for one string?
> I tried to use the complement sign ^, but this is only usable for one
> character, not for a whole string.


Other people have suggested converting to a DFA and complementing
this, which works for all regular languages. But for the complement
of a single string, it isn't that hard to make a regular expression:


  1) For the empty string, the complement is .+, where "." matches any
        character in the alphabet.


  2) For a non-empty string starting with the character a and
        continuing with the suffix s (i.e., the string is equal to as,
        where a is a single character and s is a (possibly empty) string),
        the complement is ("" | [^a] .* | a s'), where s' is the
        complement of s. I.e., either the empty string, any string not
        starting with a or a string starting with a followed by the
        complement of s.


                Torben


Post a followup to this message

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