10 Jun 2005 22:16:03 -0400

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) |

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.