From: skaller <skaller@users.sourceforge.net>
To: Gerd Stolpmann <info@gerd-stolpmann.de>
Cc: Chris King <colanderman@gmail.com>,
"O'Caml Mailing List" <caml-list@inria.fr>
Subject: Re: [Caml-list] Thread safe Str
Date: 12 Jan 2005 18:42:12 +1100 [thread overview]
Message-ID: <1105515731.2574.213.camel@pelican.wigram> (raw)
In-Reply-To: <1105475416.15581.105.camel@ice.gerd-stolpmann.de>
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
next prev parent reply other threads:[~2005-01-12 7:42 UTC|newest]
Thread overview: 19+ messages / expand[flat|nested] mbox.gz Atom feed top
2005-01-09 19:30 Christophe TROESTLER
2005-01-09 20:57 ` [Caml-list] " Gerd Stolpmann
2005-01-10 9:57 ` Alex Baretta
2005-01-10 15:49 ` Xavier Leroy
2005-01-10 16:39 ` Richard Jones
2005-01-10 18:21 ` Eric C. Cooper
2005-01-10 20:25 ` Martin Jambon
2005-01-11 3:54 ` skaller
2005-01-11 7:03 ` Chris King
2005-01-11 8:06 ` skaller
2005-01-11 12:08 ` Gerd Stolpmann
2005-01-11 17:55 ` skaller
2005-01-11 20:30 ` Gerd Stolpmann
2005-01-12 7:42 ` skaller [this message]
[not found] ` <875c7e070501111007dc3e86d@mail.gmail.com>
[not found] ` <1105471138.2574.88.camel@pelican.wigram>
[not found] ` <875c7e07050111115618692184@mail.gmail.com>
2005-01-11 19:58 ` Chris King
2005-01-11 20:53 ` Martin Jambon
2005-01-12 7:59 ` skaller
2005-01-12 20:12 ` Martin Jambon
2005-01-11 6:41 ` Chris King
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=1105515731.2574.213.camel@pelican.wigram \
--to=skaller@users.sourceforge.net \
--cc=caml-list@inria.fr \
--cc=colanderman@gmail.com \
--cc=info@gerd-stolpmann.de \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).