On Thu, 2004-09-16 at 22:07, Luc Maranget wrote:
> > > What doesn't work is sub-group matching, look ahead, etc -- things
> > > requiring actions in the middle of a regexp (rather than at the
> > > end).
> > 
> > textbook say. They do not accept rational or context-free languages,
> > they do not use DFA, NFA or LR(k) automata as claimed.
> > 
> 
> Perhaps I should make my previous post (on the theoretic side of ocamllex)
> a bit more precise.
> 
> The cited articles relate to << sub-group matching >> in DFA implementation
> of regexp matching.
> 
> The proposed technique is an extension of the Dragon-Book technique
> (Glukov ?)

I have read the Laurikari article and it describes the kind
of thing I was looking for. It provides a mathematical formalism
for Tagged NFAs and gives an modification of the subset
construction which handles determinising such TNFAs.

I think this gives all the functionality of lex
and Str/PCRE together (except for back references).

That seems a reasonable goal for a first release
because it can simplify the life or ordinary
programmers as well as compiler implementors.

Perhaps more expressive automata will follow
(as well as performance improvements :)

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



-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners