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, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net