skaller wrote:
> 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.

You might consider looking at the Mojave lexer--probably the easiest way
to get it is to download the omake sources at http://omake.metaprl.org,
and look at the file lm_lexer.{ml,mli}.  It is pure OCaml code, and
provides a tiny bit more functionality than ocamllex, but lexer
construction is online.

There is also a stub for (re)defining the Str functions in terms of
Lexer functions, but it is incomplete at the moment.

The regular expressions are egrep/awk style.  The lexer compiles regex
-> NFA -> DFA, but the DFA step is lazy--it is constructed as the input
is scanned.  Documentation for the regular expression syntax is under
the omake documentation page
http://cvs.metaprl.org:12000/omake/omake.html#section_171

Jason

-- 
Jason Hickey                  http://www.cs.caltech.edu/~jyh
Caltech Computer Science      Tel: 626-395-6568 FAX: 626-792-4257



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