> 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


As regards ocamllex, I worked from various recent publications by
Ville Larikari.

Here is the relevent comment from ocamllex sources (lex/lexgen.ml)

(* To generate directly a NFA from a regular expression.
     Confer Aho-Sethi-Ullman, dragon book, chap. 3 
   Extension to tagged automata.
     Confer
       Ville Larikari
      ``NFAs with Tagged Transitions, their Conversion to Deterministic
        Automata and Application to Regular Expressions''.
       Symposium on String Processing and Information Retrieval (SPIRE 2000),
<http://kouli.iki.fi/~vlaurika/spire2000-tnfa.ps>
(See also)
<http://kouli.iki.fi/~vlaurika/regex-submatch.ps.gz>
*)

To me, all that is far from being obvious...

Bon courage !

--Luc

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