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 OAA00448; Mon, 15 Dec 2003 14:53:22 +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 OAA00446 for ; Mon, 15 Dec 2003 14:53:20 +0100 (MET) Received: from shiva.jussieu.fr (shiva.jussieu.fr [134.157.0.129]) by nez-perce.inria.fr (8.11.1/8.11.1) with ESMTP id hBFDrJX21543; Mon, 15 Dec 2003 14:53:19 +0100 (MET) Received: from ibm3.cicrp.jussieu.fr (ibm3.cicrp.jussieu.fr [134.157.15.3]) by shiva.jussieu.fr (8.12.10/jtpda-5.4) with ESMTP id hBFDrJcV049244 ; Mon, 15 Dec 2003 14:53:19 +0100 (CET) X-Ids: 165 Received: from ibm1.cicrp.jussieu.fr (ibm1.cicrp.jussieu.fr [134.157.15.1]) by ibm3.cicrp.jussieu.fr (8.8.8/jtpda/mob-V8) with ESMTP id OAA73974 ; Mon, 15 Dec 2003 14:52:18 +0100 Received: from localhost (fernande@localhost) by ibm1.cicrp.jussieu.fr (AIX5.1/8.11.6p2/jtpda/mob-v8) with ESMTP id hBFDqHC4628582 ; Mon, 15 Dec 2003 14:52:17 +0100 Date: Mon, 15 Dec 2003 14:52:13 +0100 (NFT) From: Diego Olivier Fernandez Pons To: Xavier Leroy 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?= In-Reply-To: <20031213154007.A11444@pauillac.inria.fr> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=iso-8859-1 Content-Transfer-Encoding: QUOTED-PRINTABLE X-Miltered: at shiva.jussieu.fr by Joe's j-chkmail ("http://j-chkmail.ensmp.fr")! X-Antivirus: scanned by sophie at shiva.jussieu.fr X-Loop: caml-list@inria.fr X-Spam: no; 0.00; pons:01 pons:01 etu:99 caml-list:01 3.07:01 font:99 langages:01 langages:01 camlp:01 fortement:01 d'execution:01 certaine:01 vues:01 revise:01 minimise:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk Bonjour, > C'est moins rapide qu'un automate d=E9terministe (DFA), mais cela > permet de traiter certaines constructions (nommage de sous-cha=EEnes > filtr=E9es, "backreference") qui sont difficiles / impossibles =E0 > traiter avec un DFA. De nombreuses constructions fournies par les biblioth=E8ques d'expressions r=E9guli=E8res font sortir les langages d=E9crits de la class= e rationnelle vers les langages contextuels ou les transducteurs. D=E8s lors il est tout =E0 fait normal que l'impl=E9mentation de ces constructions soit difficile avec un DFA. > > d'autres applications de m=EAme type tel un YACC qui g=E9n=E8rerait des > > parseurs dynamiquement ou encore le CamlP4. Ce byte-code sera-t-il > > stabilis=E9 ? L'=E9quipe Cristal a-t-elle des projets en ce sens ? > > Le bytecode en question est fortement sp=E9cialis=E9 pour le mod=E8le > d'ex=E9cution utilis=E9 (automate sans pile avec backtrack). Pour Yacc > p.ex. il faudrait un automate =E0 pile. Et d'ailleurs la > repr=E9sentation de cet automate =E0 pile sous forme de tables, standard > dans les diff=E9rentes impl=E9mentations de Yacc, est d'une certaine > mani=E8re un "bytecode" sp=E9cialis=E9 pour Yacc. Les tables peuvent =EAtre certes vues comme un bytecode sp=E9cialis=E9 mais =E0 la diff=E9rence de ce que vous avez fait pour Str, il n'a pas =E9t=E9 r=E9vis=E9 pour s'adapter aux nouveaux besoins par exemple dans le filtrage de motifs ou le non-d=E9terminisme : [Je suppose construit l'automate LR(0) minimis=E9, on s'int=E9resse au m=E9canisme de r=E9solution des conflits (lookahead)] Bison supporte correctement le filtrage (lookahead) de type | "a" -> aller en 1 | _ -> aller en 2 mais pas | "aaa" -> aller en 1 | _ -> aller en 2 Le seul g=E9n=E9rateur de parseurs que je connaisse =E0 faire du k-lookahea= d o=F9 k varie en chaque noeud selon le degr=E9 d'ambiguit=E9 de la construction est ANTLR (qui est un parseur r=E9cursif descendant). De m=EAme qu'il a fallu faire des circonvolutions pour que Bison supporte le backtracking-LR (en cas de conflit non r=E9solu, essayer successivement les deux options) ou le fail dans les actions (une action peut lever une exception qui produit un retour en arri=E8re jusqu'au dernier point de branchement - noter que cela donne la puissance des grammaires contextuelles =E0 Bison et rend le probl=E8me de reconnaissance NP-complet). > La beaut=E9 de ce type d'approche est justement qu'on construit un > bytecode minimal et sp=E9cialis=E9 au probl=E8me =E0 traiter. Cela requiert une compr=E9hension s=E9rieuse des m=E9canismes de compilatio= n ce qui n'est pas =E0 la port=E9e de tout le monde. Il me semble d'ailleurs que la plupart des avanc=E9es et des impl=E9mentations efficaces dans ce domaine sont d=FBes =E0 des chercheurs en "langages et compilation". Diego Olivier ------------------- 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