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 OAA25852; Thu, 16 Sep 2004 14:07:27 +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 OAA27333 for ; Thu, 16 Sep 2004 14:07:26 +0200 (MET DST) Received: from yquem.inria.fr (yquem.inria.fr [128.93.8.37]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id i8GC7OaO008191; Thu, 16 Sep 2004 14:07:25 +0200 Received: by yquem.inria.fr (Postfix, from userid 18041) id DD5A9BC3F; Thu, 16 Sep 2004 14:07:24 +0200 (CEST) Date: Thu, 16 Sep 2004 14:07:24 +0200 To: Diego Olivier Fernandez Pons Cc: skaller , caml-list Subject: Re: [Caml-list] Need NFA/DFA conversion help Message-ID: <20040916120724.GB16633@yquem.inria.fr> References: <1095291341.27775.1164.camel@pelican.wigram> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.3.28i From: luc.maranget@inria.fr (Luc Maranget) X-Miltered: at concorde with ID 414981FC.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Loop: caml-list@inria.fr X-Spam: no; 0.00; caml-list:01 pcre:01 context-free:99 --luc:01 regexp:01 regexp:01 maranget:02 maranget:02 lex:04 textbook:04 textbook:04 implement:05 luc:05 luc:05 ocamllex:05 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk > > What doesn't work is sub-group matching, look ahead, etc -- things > > requiring actions in the middle of a regexp (rather than at the > > end). > > Here is the second problem. You did exactly what was expected (taking > a textbook on formal languages and implement what is said). The > problem is that tools like PCRE, Lex, Yacc, etc. do not work as > textbook say. They do not accept rational or context-free languages, > they do not use DFA, NFA or LR(k) automata as claimed. > Perhaps I should make my previous post (on the theoretic side of ocamllex) a bit more precise. The cited articles relate to << sub-group matching >> in DFA implementation of regexp matching. The proposed technique is an extension of the Dragon-Book technique (Glukov ?) --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