Wed, 19 May 2010 21:31:15 -0700

Related articles |
---|

[2 earlier articles] |

Re: NFA and negation/conjunction sh006d3592@blueyonder.co.uk (Stephen Horne) (2010-05-15) |

Re: NFA and negation/conjunction monnier@iro.umontreal.ca (Stefan Monnier) (2010-05-15) |

Re: NFA and negation/conjunction klyjikoo@gmail.com (klyjikoo) (2010-05-16) |

Re: NFA and negation/conjunction cfc@shell01.TheWorld.com (Chris F Clark) (2010-05-16) |

Re: NFA and negation/conjunction torbenm@diku.dk (2010-05-17) |

Re: NFA and negation/conjunction klyjikoo@gmail.com (klyjikoo) (2010-05-19) |

Re: NFA and negation/conjunction rsc@swtch.com (Russ Cox) (2010-05-19) |

Re: NFA and negation/conjunction torbenm@diku.dk (2010-05-20) |

From: | Russ Cox <rsc@swtch.com> |

Newsgroups: | comp.compilers |

Date: | Wed, 19 May 2010 21:31:15 -0700 |

Organization: | Compilers Central |

References: | 10-05-078 |

Keywords: | lex |

Posted-Date: | 20 May 2010 00:57:31 EDT |

On Thu, May 13, 2010 at 8:42 PM, Stefan Monnier

<monnier@iro.umontreal.ca> wrote:

*> I'm looking for any work that tries to provide negation and/or*

*> conjunction operations in regexps without using a DFA (or at least*

*> while avoiding the DFA state explosion problem).*

*>*

*> My search has currently come up empty (actually I pretty much haven't*

*> seen mention of conjunction and negation in regexps other than in*

*> Brzozowski's derivatives). B So any pointer would be welcome,*

Torben Cgidius Mogensen's mail makes a pretty good case that

one can't avoid a lot of effort in the general case. However,

derivatives are a great way to avoid unnecessary effort, because

that formalism can model the concepts directly (in contrast to the

NFA formalism). http://www.ccs.neu.edu/home/turon/re-deriv.pdf

is a recent paper worth looking at. If I needed to implement support

for those concepts, I would start there.

Russ

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.