From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id XAA31437; Fri, 17 Sep 2004 23:00:21 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id XAA31768 for ; Fri, 17 Sep 2004 23:00:20 +0200 (MET DST) Received: from swordfish.cs.caltech.edu (swordfish.cs.caltech.edu [131.215.44.124]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id i8HL0Jhv027293 for ; Fri, 17 Sep 2004 23:00:20 +0200 Received: from [127.0.0.1] (adsl-67-120-175-89.dsl.lsan03.pacbell.net [67.120.175.89]) by swordfish.cs.caltech.edu (Postfix) with ESMTP id 07FC7DF27C; Fri, 17 Sep 2004 14:00:08 -0700 (PDT) Message-ID: <414880F6.6050900@cs.caltech.edu> Date: Wed, 15 Sep 2004 10:50:46 -0700 From: Jason Hickey Organization: Caltech User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.7) Gecko/20040616 X-Accept-Language: en-us, en MIME-Version: 1.0 To: skaller@users.sourceforge.net, caml-list@inria.fr Subject: Re: [Caml-list] Need NFA/DFA conversion help References: <1095260758.27775.1047.camel@pelican.wigram> In-Reply-To: <1095260758.27775.1047.camel@pelican.wigram> Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit X-Miltered: at concorde with ID 414B5063.001 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Loop: caml-list@inria.fr X-Spam: no; 0.00; hickey:01 caml-list:01 pointers:01 pcre:01 rtn:99 mli:01 stub:01 compiles:01 regex:01 hickey:01 626:99 626:99 792:99 regexp:01 ocaml:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk 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