Re: Need regexp source

ralph@inputplus.demon.co.uk (Ralph Corderoy)
15 Jan 2000 14:20:36 -0500

          From comp.compilers
Related articles
Need regexp source balachandr@yahoo.com (2000-01-02)
Re: Need regexp source arnold@mathcs.emory.edu (2000-01-06)
Re: Need regexp source jos@and.nl (Jos A. Horsmeier) (2000-01-06)
Re: Need regexp source george@castro.dbnet.ece.ntua.gr (2000-01-09)
Re: Need regexp source roumazeilles.NO.SPAM@NO.SPAM.magic.fr (Yves Roumazeilles) (2000-01-09)
Re: Need regexp source mottl@miss.wu-wien.ac.at (Markus Mottl) (2000-01-09)
Re: Need regexp source jenglish@flightlab.com (Joe English) (2000-01-09)
Re: Need regexp source ralph@inputplus.demon.co.uk (2000-01-15)
Re: Need regexp source thp@roam-thp2.cs.ucr.edu (Tom Payne) (2000-01-15)
Re: Need regexp source world!cfc@uunet.uu.net (Chris F Clark) (2000-01-19)
| List of all articles for this month |
From: ralph@inputplus.demon.co.uk (Ralph Corderoy)
Newsgroups: comp.compilers
Date: 15 Jan 2000 14:20:36 -0500
Organization: InputPlus Ltd.
References: 00-01-006 00-01-020
Keywords: lex, DFA

> > [There's always lex, I suppose. Is there a reasonable way to do
> > interative regex matching without all of the work of building a DFA
> > first? -John]
>
> If you are satisfied with styles other than "regexp", try the PCRE
> (Perl Compatibility Regular Expressions):
>
> ftp://ftp.cus.cam.ac.uk/pub/software/programs/pcre
>
> It has a function for "studying" regular expressions, which, AFAIK,
> builds a DFA "on the fly". Very fast...


IIRC its `study' just builds an extra table to do one or two
optimizations.


Otherwise, it builds an NFA for the regexp (which can include
backreferences like /(a+)b\1/) and then, rather than traverse it,
backtracking upon failure, it walks all possible paths in parallel,
selecting the appropriate matching path at the end.




Ralph.

Post a followup to this message

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