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

[Xavier Leroy <xavier.leroy@inria.fr>]

> 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