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-15 (15:06)
From: skaller <skaller@u...>
Subject: [Caml-list] Need NFA/DFA conversion help
I need some help understanding how to convert
an NFA with *labelled* arcs into an equivalent DFA.
I'm not even sure it is possible. Any advice,
pointers to papers, or code appreciated. The main
use will be in a set of regexp related tools intended
to replace Ocamllex, Str, and PCRE with pure caml code,
and then extend that with an RTN based parsing system.

Ocamllex functionality is already available,
however group extraction and friends seem
to require labelled arcs (and RTNs definitely do).
I'm using the naive algorithm (regexp->DFA) from
the Dragon book with the pattern-recognition 
modification (which is enough for a tokeniser).
I can't see how to modify it to keep track of
the arcs (special marks in regexps like group
brackets, lookahead operator, etc).

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