English version
Accueil     À propos     Téléchargement     Ressources     Contactez-nous    

Ce site est rarement mis à jour. Pour les informations les plus récentes, rendez-vous sur le nouveau site OCaml à l'adresse ocaml.org.

Browse thread
[Caml-list] Need NFA/DFA conversion help
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2004-09-16 (13:29)
From: skaller <skaller@u...>
Subject: Re: [Caml-list] Need NFA/DFA conversion help
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