Re: --- Regexps, compilers etc., prog help ---

ok@cs.rmit.edu.au (Richard A. O'Keefe) writes:


|> Hursh Jain <sjain@a.chem.upenn.edu> wrote:
|> >I am interested in writing a regular expression evaluator, and also a
|> >toy compiler..
|>
|> Basic regular expressions are dealt with in "Software Tools", which is
|> such a classic it's probably out of print.


As much as I love the "Software Tools" book, I fear that it is dated
in this regard. Their algorithms don't actually handle full regular
expressions. On the other hand, they don't require much memory, but
this isn't generally considered an issue these days. (Although IMHO,
there are cases where it should be. In an editor, for example. You
don't really want to run out of memory in the middle of a regular
expression match.)


|> Even AWK and PERL are pathetically restricted compared with SNOBOL
|> patterns. It might be of interest that the next release of the (free)
|> GNAT compiler for Ada is going to include a _full_ implementation of
|> SNOBOL patterns. (Robert Dewar worked on the SPITBOL implementation
|> of SNOBOL, and is one of the key players in the GNAT team.)
|>
|> With this around, I expect never to write a regular expression
|> evaluator again in my life.
|>
|> --
|> Richard A. O'Keefe; http://www.cs.rmit.edu.au/%7Eok; RMIT Comp.Sci.
|> [Well, sure, but there can be the issue of performance. I've written some
|> pretty rococo Snobol patterns in my time, with lots of backing up and
|> conditional assignments and stuff, but one thing they were not is fast.
|> REs can be matched in one pass, no backup. -John]


Concerning the moderator's comment: most regular expression's I see
these days have been extended to allow saving part of the match. I
think that this requires back-tracking (or does anyone know of a one
pass solution that works in all cases).


Even with normal regular expressions, there are a number of tradeoffs
between memory use, execution time and flexibility. Enough to make me
think that there still will be occasions for writing your own parser.
--
James Kanze +33 (0)1 39 55 85 62 email: kanze@gabi-soft.fr
GABI Software, Sarl., 22 rue Jacques-Lemercier, 78000 Versailles, France
--

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