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

> [...REs can be matched in one pass, no backup. -John]


J. Kanze <kanze@gabi-soft.fr> wrote:
>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).


It can't be done in one pass without requiring storage proportional to
the size of the string (not the pattern). I've never pursued a
rigorous proof of this, but having studied this and related issues
fairly extensively, I'd bet a significant amount of money on it being
true.


However, it is not necessary to resort to a traditional backtracking
implementation. You can do a lot better than that. And if I can ever
finish writing the code, I'll write a paper about it...


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


Perhaps, but it may be possible to make those occasions quite rare.
--
| Henry Spencer
| henry@zoo.toronto.edu
--

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