Version française
Home     About     Download     Resources     Contact us    
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: -- (:)
From: Jason Hickey <jyh@c...>
Subject: Re: [Caml-list] Need NFA/DFA conversion help
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