[Caml-list] Re: [Caml-list] Bibliothèques d'expressions régulières de Caml 3.07

[Diego Olivier Fernandez Pons <Diego.FERNANDEZ_PONS@etu.upmc.fr>]

    Bonjour,

> 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.

De nombreuses constructions fournies par les bibliothèques
d'expressions régulières font sortir les langages décrits de la classe
rationnelle vers les langages contextuels ou les transducteurs. Dès
lors il est tout à fait normal que l'implémentation de ces
constructions soit difficile avec un DFA.

> > 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.

Les tables peuvent être certes vues comme un bytecode spécialisé mais
à la différence de ce que vous avez fait pour Str, il n'a pas été
révisé pour s'adapter aux nouveaux besoins par exemple dans le
filtrage de motifs ou le non-déterminisme :

[Je suppose construit l'automate LR(0) minimisé, on s'intéresse au
mécanisme de résolution 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énérateur de parseurs que je connaisse à faire du k-lookahead
où k varie en chaque noeud selon le degré d'ambiguité de la
construction est ANTLR (qui est un parseur récursif descendant).

De même qu'il a fallu faire des circonvolutions pour que Bison
supporte le backtracking-LR (en cas de conflit non résolu, essayer
successivement les deux options) ou le fail dans les actions (une
action peut lever une exception qui produit un retour en arrière
jusqu'au dernier point de branchement - noter que cela donne la
puissance des grammaires contextuelles à Bison et rend le problème de
reconnaissance NP-complet).

> La beauté de ce type d'approche est justement qu'on construit un
> bytecode minimal et spécialisé au problème à traiter.

Cela requiert une compréhension sérieuse des mécanismes de compilation
ce qui n'est pas à la portée de tout le monde. Il me semble d'ailleurs
que la plupart des avancées et des implémentations efficaces dans ce
domaine sont dûes à 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