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 PAA11469; Sat, 13 Dec 2003 15:40:21 +0100 (MET) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id PAA11765 for ; Sat, 13 Dec 2003 15:40:20 +0100 (MET) Received: from pauillac.inria.fr (pauillac.inria.fr [128.93.11.35]) by nez-perce.inria.fr (8.11.1/8.11.1) with ESMTP id hBDEe8109236; Sat, 13 Dec 2003 15:40:08 +0100 (MET) Received: (from xleroy@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id PAA11769; Sat, 13 Dec 2003 15:40:08 +0100 (MET) Date: Sat, 13 Dec 2003 15:40:07 +0100 From: Xavier Leroy To: Diego Olivier Fernandez Pons Cc: caml-list@inria.fr Subject: [Caml-list] Re: =?iso-8859-1?Q?=5BCaml-list=5D_Biblioth=E8ques_d'expressions_r=E9guli=E8?= =?iso-8859-1?Q?res_de_Caml_3=2E07?= Message-ID: <20031213154007.A11444@pauillac.inria.fr> References: Mime-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit X-Mailer: Mutt 1.0i In-Reply-To: ; from Diego.FERNANDEZ_PONS@etu.upmc.fr on Thu, Dec 11, 2003 at 06:16:50PM +0100 X-Loop: caml-list@inria.fr X-Spam: no; 0.00; caml-list:01 3.07:01 3.07:01 arriere:01 semantique:01 automates:01 arriere:01 represente:01 courante:01 regexps:01 regex:01 font:99 regex:01 consommation:01 camlp:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk > Je viens d'examiner la nouvelle bibliothèque d'expressions régulières > incluse dans Caml 3.07 (Str). > > Je ne suis pas certain d'avoir compris la totalité de son code mais il > semblerait qu'elle transforme l'expression régulière en un automate > avec retour en arrière (backtracking automata) compilé ensuite vers du > byte-code spécialisé. Ensuite en fonction de la sémantique désirée, un > petit interprète C exécute ce code. Oui, c'est exact. > Cette méthode d'implémentation est pour le moins inusuelle, les plus > courantes étant les interprètes récursifs pour les automates avec > retour en arrière (par exemple SML/NJ) ou la génération d'un automate > déterministe représenté par des tables soit statiquement (Lex) soit > dynamiquement (Regexp, LibRE). Représenter un automate avec backtrack par une sorte de bytecode est une pratique courante, au moins dans le "monde" Unix. Un exemple bien connu est la bibliothèque de regexps de Henry Spencer. La bibliothèque GNU regex (utilisée dans Emacs et par l'ancienne implémentation de la bibliothèque Str de Caml) font de même. > A priori ce doit être beaucoup plus rapide. C'est moins rapide qu'un automate déterministe (DFA), mais cela permet de traiter certaines constructions (nommage de sous-chaînes filtrées, "backreference") qui sont difficiles / impossibles à traiter avec un DFA. > Y-a-il des mesures de > performance par rapport aux autres bibliothèques Caml ? à des > bibliothèques C ? J'avais fait pas mal de mesures par-rapport à GNU regex. Le nouveau code est de 1 à 10 fois plus rapide. Mais regex a de sérieux problèmes de rapidité et de consommation mémoire. > Ce même byte-code semble pouvoir servir aussi comme cible pour > d'autres applications de même type tel un YACC qui génèrerait des > parseurs dynamiquement ou encore le CamlP4. Ce byte-code sera-t-il > stabilisé ? L'équipe Cristal a-t-elle des projets en ce sens ? Le bytecode en question est fortement spécialisé pour le modèle d'exécution utilisé (automate sans pile avec backtrack). Pour Yacc p.ex. il faudrait un automate à pile. Et d'ailleurs la représentation de cet automate à pile sous forme de tables, standard dans les différentes implémentations de Yacc, est d'une certaine manière un "bytecode" spécialisé pour Yacc. Donc, non, il n'y a pas de projet de généraliser ou de réutiliser ce bytecode. La beauté de ce type d'approche est justement qu'on construit un bytecode minimal et spécialisé au problème à traiter. - Xavier Leroy ------------------- 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