Browse thread
[Caml-list] Need NFA/DFA conversion help
[
Home
]
[ Index:
by date
|
by threads
]
[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: | 2004-09-15 (20:54) |
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