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

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

[Diego Olivier Fernandez Pons]

    Bonjour,

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.

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

A priori ce doit être beaucoup plus rapide. Y-a-il des mesures de
performance par rapport aux autres bibliothèques Caml ? à des
bibliothèques C ?

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 ?

    Cordialement,

        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

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

[Xavier Leroy]

> 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

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

[Diego Olivier Fernandez Pons]

    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