Version française
Home     About     Download     Resources     Contact us    

This site is updated infrequently. For up-to-date information, please visit the new OCaml website at

Browse thread
Thread safe Str
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: skaller <skaller@u...>
Subject: Re: [Caml-list] Thread safe Str
On Wed, 2005-01-12 at 07:30, Gerd Stolpmann wrote:

> It's a matter of taste. Granted, you cannot define capturing directly
> for an automaton, only by a possibly poor backtracking algorithm. (This
> means the approach is "definition by algorithm", not really the best way
> to do it.)

It's worse than that ..

> Which leads to a more serious problem: One must know the algorithm of
> the implementation to avoid running into a hard backtracking case (which
> can be exponential). 

.. it's worse .. some cases could be infinite recursion:
see Frisch & Cardelli.

It is known PCRE has this problem. It was hacked to
fix one of the common cases. The hack isn't general.

> There are a lot of tutorials explaining good and
> bad regexps.

Which are worthless junk if you're generating them.. 

The point is -- this is folklore not mathematics.

>  The lex-type scanners do not have this problem (but you may
> run into space problems instead because the automaton becomes large).

Indeed, but they also have another problem: they don't support 
captures at all.

> > 
> > Unfortunately this has a problem: it requires a
> > bidirectional iterator, whereas a DFA only requires
> > an input iterator. (NFA's require forward iterators)
> For string regexps this is not a big problem, the string is in memory.
> For XML, this is more a problem, especially when the XML document is
> only available event by event (processing large documents).

Hehe .. but the main use of the algorithm is in the specialist
XML processing language XDuce...

John Skaller,
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language