mercredi 28 juillet

Accueil :: Dépêches :: Entretiens :: Journaux :: Forums :: Sondages :: Suivi :: Statistiques :: Contact :: Plan

Articles précédents : Développeur

[42] C++ 0xB enfin finalisé ?
[95] Du côté de chez Xorg
[66] Les technos web cools du moment
[30] OsmocomBB : Pour un GSM complètement libre !
[24] Drupal 7.0 alpha 1 est sortie
[4] Venez jouer avec playframework
[67] Sortie de Qt 4.6
[1] Nuit de l'info 2009
[35] Sortie de la version 2.11 de la bibliothèque standard C GNU (glibc)
[113] Go : Un nouveau langage chez Google

Liens connexes

L'annonce de Google (598 clics)
Les explications de l'auteur (506 clics)
Le code source de la librairie RE2 (393 clics)

Dépêche modérée par

Ragnagna

Dépêche éditée par

Développeur : Google libère la bibliothèque d'expressions rationnelles RE2

Posté par weeber (). Modéré le 16 mars 2010.

Le 11 mars Google a libéré le code source d'une bibliothèque d'expressions rationnelles appelée RE2.
RE2 a été faite pour répondre aux besoins de Google, elle est optimisée pour la rapidité, a une empreinte mémoire réduite, gère les threads et propose une alternative aux méthodes utilisées jusqu'à présent.

Cet article revisite brièvement l'histoire des expressions rationnelles, puis le problème posé par les références arrières et, enfin, l'apport de RE2 par rapport aux implémentations existantes.

L'annonce de Google (598 clics)
Les explications de l'auteur (506 clics)
Le code source de la librairie RE2 (393 clics)

> Lire la suite (48 commentaires, moyenne: 3,2). [dépêche : 2951 caractères]

Qu'est-ce-que c'est?

Les expressions rationnelles sont une notation pour décrire un jeu de chaînes de caractères.
Elles se présentent sous la forme d'une suite de caractères, on appelle cette suite un motif.
Ce motif décrit une ou plusieurs chaînes de caractères pour permettre de les trouver dans du texte, de la récupérer et de lui appliquer des traitements tels que les remplacer.

Par exemple:
couleurs? trouvera couleur et couleurs

L'histoire des expressions rationnelles

Leurs prémices remontent aux années 50 avec le mathématicien Cole Kleene. Il créa les modèles réguliers afin de décrire des machines d'état simples.
Michael Rabin et Dana Scott ont ensuite proposé un traitement mathématique de ces modèles dans un article qui leur a valu le Prix Turing.
Le langage SNOBOL a été la première implémentation des modèles rationnelles, mais il ne comprenait pas encore toutes les fonctionnalités des expressions rationnelles.
Ken Thompson a ensuite implémenté la notation de Kleene dans un éditeur de texte appelé QED afin d'utiliser les motifs pour rechercher du texte.
Il a ensuite ajouté ces fonctionnalités dans l'éditeur ed. Depuis ce temps, beaucoup de variations de l'adaptation originale de Thompson sont utilisées dans les outils tels qu'awk, Emacs, vi et lex.

Les références arrières

Les références arrière permettent d'ajouter de nombreuses fonctionnalités aux expressions rationnelles.

Par exemple:
(chat|chien)\1 détecte chatchat et chienchien mais pas chatchien ni chienchat.

Cependant, la puissance que les références arrières apportent amène aussi un coût très élevé.
Dans le cas le plus défavorable, les implémentations connues telles que celle du langage Perl utilisent des algorithmes de recherche qui ont un coût exponentiel.
Les références arrière sont indispensables, elles ne peuvent être supprimées des langages.
Cependant leurs implémentations peuvent êtres améliorées, c'est ce qu'a fait Russ Cox.

Les optimisations

Afin de réduire leurs coûts, Russ Cox a revu les algorithmes a partir de ceux créés par Ken Thompson.
Il a - entre autres - réécrit ceux qui sont implémentés dans le programme grep et a aussi ajouté d’autres algorithmes afin de prendre en charge des fonctionnalités supplémentaires.
Est ainsi née la bibliothèque RE2, qui offre la plupart des fonctionnalités des expressions rationnelles implémentées dans le langage Perl (PCRE).
RE2 est une bibliothèque C++ qui a l'avantage de garantir un temps d'exécution linéaire - et non plus exponentiel - avec une empreinte mémoire limitée. Allez donc voir les comparaisons de performances entre PCRE et RE2 sur cette page.
Cette bibliothèque est très utilisée chez Google, par exemple dans Code Search, ou dans certains de leurs outils internes.

Cette discussion est archivée, il n'est plus possible de laisser des commentaires.

Note : les commentaires appartiennent à ceux qui les ont postés. Nous n'en sommes pas responsables.

Dur

Posté par Snarky (Jabber id, page perso, ) le 16/03/2010 à 13:50. (lien). Évalué à 7.

J'aime pas l'ampleur Google... Mais je l'aime bien quand même... Je crois qu'il faut que j'aille voir un psy.

--
Milite pour un about:black sur les navigateurs ! ( シ Sauvons la planète ツ )

[^]Re: Dur

Posté par Elie Roux (page perso, ) le 16/03/2010 à 14:56. (lien). Évalué à 4.
> Milite pour un about:black sur les navigateurs ! ( シ Sauvons la
> planète ツ )

Si je ne m'abuse c'est (très très) légèrement plus coûteux en électricité de produire du noir (il faut filtrer la backlight) que du blanc (où on laisse plus ou moins passer toute la lumière) sur les LCD (contrairement aux CRT)... donc je suis pas sûr qu'un about:black sauve la planète... par contre ça la sauvera sûrement quand tout le monde aura un écran à LED !
- [^]Re: Dur
  
  Posté par Anglès d'Auriac Jean-Alexandre (Jabber id, ) le 16/03/2010 à 18:41. (lien). Évalué à 1.
  Et puis, pourquoi un Shi et un Tsu ? Je ne parles pas japonais, et je n'ai absolument aucune idée de ce que ça pourrait bien vouloir dire…
  
  --
  Je suis un «connard amer.» ™
  Constaté et certifié par Tristan Nitot.
  - [^]Re: Dur
    
    Posté par Mounir (page perso, ) le 17/03/2010 à 10:30. (lien). Évalué à 1.
    シツ ça veut pas dire "trône des WC" en japonais ?
    
    --> []
    
    --
    Ce n'est pas sur linux...
  - [^]Re: Dur
    
    Posté par B. (Jabber id, page perso, ) le 17/03/2010 à 10:38. (lien). Évalué à 0.
    Je pense que ça se traduit par :-) et (-:

comparatif graphique

Posté par zero heure (Jabber id, page perso, ) le 16/03/2010 à 13:50. (lien). Évalué à 6.

le petit graphique en haut de cette page est très parlant
http://swtch.com/~rsc/regexp/regexp1.html

les trolleurs fous sont priés de noter que l'échelle de temps du second graphique est graduée en microsecondes

--
J'ai vu bien des choses dans ma petite vie, et je mesure amèrement l'impuissance à les dire. (JP Rosnay, Le 13ème apôtre) http://www.poesie.net/apotre2.htm

[^]Re: comparatif graphique

Posté par vjm () le 16/03/2010 à 14:57. (lien). Évalué à 8.
Et les trolleurs ils doivent aussi noter que tu pointes vers un papier de recherche qui date de 2007 alors que l'article décrivant l'implémentation de RE2, datant de 2010, est là : http://swtch.com/~rsc/regexp/regexp3.html ?

Cela dit ça reste flatteur pour RE2 avec juste comme bémol que l'algo de RE2 a un temps de setup un peu long par rapport à PCRE qui n'est amorti que pour des tailles de texte supérieure à 64 octets.

--
vjm

[^]Re: comparatif graphique

Posté par Troy McClure (page perso, ) le 16/03/2010 à 14:59. (lien). Évalué à 8.
Le graphique est parlant, mais il prend un cas pathologique qui ne correspond pas à une regexp qui ait du sens. C'est rare de faire des recherches sur a?a?a?a?a?a?a?a?a.

Je m'étais un peu interessé à cette histoire de regexp via DFA qui serait plus rapide que les implementations usuelles à base de NFA après avoir lu la page de russ cox il y a quelques temps, j'avais même fait l'effort d'en implementer un pour finalement constater que ça allait notablement moins vite que pcre sur les classes de regexp "utiles". Au final on perd beaucoup de souplesse (bye bye les backreferences, et les {n} coutent chers puisqu'il faut ajouter n etats dans l'automate) pour gagner la garantie que le temps de calcul n'explosera pas exponentiellement dans des cas merdiques.
- [^]Re: comparatif graphique
  
  Posté par alenvers () le 17/03/2010 à 13:38. (lien). Évalué à 6.
  Ton post est un peu confu du fait que tu utilises NFA à la place du terme NFA avec backtracking.
  
  Il faut différencier la construction d'un automate fini (FA : DFA/NFA) et l'exécution de celui-ci pour être correct. Tous les algos, que je connaisse, construisent un automate fini.
  
  Un automate fini non-déterministe se construit facilement en un temps linéaire en la taille de l'expression. Un automate fini déterministe quant à lui se construit en un temps qui peut-être exponentiel (car le nombre d'état peut exploser car il s'agit +/- de construire des ensembles d'état du NFA).
  
  Au niveau de l'exécution d'un automate fini déterministe, le temps d'exécution est linéraire en la taille du texte à matcher.
  
  Dans le cas d'un automate non-déterministe (sans références arrières et autres joyeusetés), c'est proportionnel au produit la taille de l'expression et de la taille du texte à matcher. Cela consiste +/- à construire le DFA à la volée à l'exécution.
  
  Dans le cas non-déterministe avec excutation avec backtracking, qui n'est nécessaire réellement que quand on sort des langages réguliers (référence arrières, ...), on passe en exponentiel.
  
  Pour résumer,
  - DFA est le plus rapide en exécution : nul doute. DFA a coût important à la création. Ce qui probablement est la cause des lenteurs de ton test. Mais c'est surement la plus efficace si tu ré-utilises beaucoup de fois la DFA sur des textes différents avec une seule compilation
  - NFA sans backtracking est probablement le plus rapide en pratique (en moyenne).
  - NFA avec backtracking est dans la majorité des cas comme NFA sans backtracking mais à des cas limites (et des effets de bord qui font que aa* est plus rapide que a+, par exemple) qui peuvent être ennuyeux. C'est surtout la méthode la plus expressive au niveau langage.

Démocratisation

Posté par Sytoka Modon (page perso, ) le 16/03/2010 à 15:24. (lien). Évalué à 3.

Bonne dépêche. Je rajouterais cependant que les expressions rationnelles ont été surtout démocratisé par le langage Perl qui l'a mis au coeur du langage dès ses débuts.

De plus, la communauté Perl est toujours très active sur ce thème avec Perl6 dont la grammaire est écrite en expression rationnelle mais aussi via le mouvement "Modern Perl" ont l'ont peut (doit) utiliser le modificateur 'x' qui permet de mettre des espaces, des retours chariots et même des commentaires dans ses regex ! Cela permet d'avoir des expressions plus facilement compréhensible et donc au final moins de bogue et un code plus maintenable.

[^]Re: Démocratisation

Posté par Mathieu Stumpf (Jabber id, page perso, ) le 16/03/2010 à 15:37. (lien). Évalué à 10.
Oui et non, si on regarde un peu l'historique des logiciels, les uns s'inspirant des autres on a ed>sed>awk>perl. Alors oui, les expressions régulières sont au cœur de perl, mais cela découle de son historique aux origines qui fleur bon l'Unix.

--
Le wiki de l'association culture libre : venez participer !
- [^]Re: Démocratisation
  
  Posté par zaurus (page perso, ) le 16/03/2010 à 16:10. (lien). Évalué à 4.
  Apparemment du meme auteur, je trouve cette page plus interessante:
  
  http://swtch.com/~rsc/regexp/regexp1.html
  
  On y voit grep et awk poutrer Perl, Python, Ruby et PCRE:
  
  http://pdos.csail.mit.edu/~rsc/regexp-img/grep1p.png
  
  Ca force le respect envers les "bons vieux outils a papa"...
  - [^]Re: Démocratisation
    
    Posté par tuXico () le 16/03/2010 à 16:29. (lien). Évalué à 3.
    Un bon vieil opinel coupe mieux le bois qu'un couteau suisse. Indeed.
    De la différence entre les petits outils dédiés et les gros outils qui font tout.
    
    J'entends par là que je ne suis pas moultement surpris que grep poutre des langages de programmation. Celui qui m'impressionne le plus (sur ce graphique), c'est awk...
    
    --
    La République (C) garantit que, pour le lièvre comme pour la tortue, la ligne de départ est la même.
    - [^]Re: Démocratisation
      
      Posté par gbetous () le 16/03/2010 à 21:02. (lien). Évalué à 3.
      Un bon vieil opinel coupe mieux le bois qu'un couteau suisse.
      
      Le steack, sans aucun doute, mais le bois... t'as déjà essayé de couper du bois avec un Opinel ? Je pense que je préfère encore l'option "scie" du couteau suisse !
      - [^]Re: Démocratisation
        
        Posté par Albert_ () le 17/03/2010 à 16:59. (lien). Évalué à 2.
        L'opinel est outils de choix pour la sculture sur bois comme tu peux le voir sur cette page.
        
        http://pagesperso-orange.fr/laurence.faraut/sculpture/index.(...)
        
        Couper ne veut pas dire scier :) et faire de la sculpture sur bois avec un couteau suisse tel que:
        
        http://lecolporteur.files.wordpress.com/2009/05/couteau-suis(...)
        
        c'est beaucoup moins facile.
- [^]Re: Démocratisation
  
  Posté par Sytoka Modon (page perso, ) le 16/03/2010 à 18:12. (lien). Évalué à 1.
  Attention, ne me faites pas dire ce que je n'ai pas dis ! Je n'ai pas dis que Perl avait inventé les regex ! Je sais bien que cela vient en gros de ed et que cela a été repris dans awk, puis dans Perl.
  
  Je parle de démocratisation à grande échelle. Ce n'est pas avec ed ni avec awk que les regex se sont démocratisées. D'ailleurs, la plupart des monolignes awk se résument à récupérer la colonne X..., chose qu'il fait très bien.
  
  Sinon, j'évoque l'avenir des regex et je vois que du coté de Perl, les évolutions proposées en 15 ans sont énormes. J'ai l'impression que les autres langages suivent. C'est peut être juste une impression.
  - [^]Re: Démocratisation
    
    Posté par gato () le 16/03/2010 à 22:06. (lien). Évalué à 9.
    Ben non, il y a plein de gens qui utilisent tous les jours des regexp dans sed/awk/vi/grep/php et qui ne veulent surtout pas s'approcher de perl. Je ne vois pas en quoi perl démocratise les regexp de ce point de vue, ni pourquoi ces langages "suivraient" perl.
    
    Le principal défaut des mongueurs est qu'ils sont persuadés que perl est à la fois l'apogée des langages, et la source ultime de tout progrès. Je n'y vois qu'un exemple de ce qu'il ne faut pas faire en programmation : le code write-only.

[+] [^]Re: Démocratisation

Posté par Jean B () le 16/03/2010 à 20:24. (lien). Évalué à -1.
le modificateur 'x' qui permet de mettre des espaces, des retours chariots et même des commentaires dans ses regex !

Woah révolutionnaire !
http://docs.python.org/library/re.html#re.VERBOSE
- [^]Re: Démocratisation
  
  Posté par Bobinours () le 16/03/2010 à 22:02. (lien). Évalué à 1.
  Je ne comprends pas bien cette remarque avec une comparaison avec le langage Python ? Tu sembles suggérer que cette fonctionnalité a implémenté dans Python depuis longtemps.
  
  Le modificateur 'x' existe depuis que je connais Perl (au moins 10 ans) et de ce que j'ai pu lire, ce serait plutôt Python qui se serait calqué sur le modèle Perl des regex et non l'inverse.
  
  The re module was added in Python 1.5, and provides Perl-style regular expression patterns. Earlier versions of Python came with the regex module, which provided Emacs-style patterns. The regex module was removed completely in Python 2.5.
  Source : http://docs.python.org/dev/howto/regex.html
- [^]Re: Démocratisation
  
  Posté par __o () le 16/03/2010 à 22:04. (lien). Évalué à 6.
  Forcément tu vas retrouver les mêmes features dans tous les langages qui utilisent la lib PCRE ;-) (PCRE = Perl Compatible Regular Expression).
  - [^]Re: Démocratisation
    
    Posté par Jean B () le 17/03/2010 à 08:56. (lien). Évalué à 2.
    au temps pour moi, c'était présenté comme une fonctionnalité révolutionnaire de Perl 6.
    - [^]Re: Démocratisation
      
      Posté par Sytoka Modon (page perso, ) le 17/03/2010 à 09:14. (lien). Évalué à 2.
      Pas du tout. J'ai juste écrit que la grammaire Perl6 était écrite sous forme d'expression rationnelle. Ensuite, je parle de "Modern Perl" qui est plutôt un mouvement qui cherche à profiter des avancées sur Perl6 pour en intégrer dans Perl5 et qui de ce fait écrit du code Perl5 d'une autre manière...
      
      Je ne parle donc pas de révolution mais d'évolution ;-)

[^]Re: Démocratisation

Posté par Christophe Garault (page perso, ) le 16/03/2010 à 22:07. (lien). Évalué à 7.
et un code plus maintenable.
Heu...on parle bien de Perl là ?

Ok --->[]
- [^]Re: Démocratisation
  
  Posté par Sytoka Modon (page perso, ) le 16/03/2010 à 23:27. (lien). Évalué à 3.
  J'ai jamais réussi à bidouiller correctement un serveur de mail sauf justement qpsmtpd car le code est lisible et même moi, j'ai réussit à modifier des greffons et à écrire les miens ;-)
  
  De même, Email::Filter est un bonheur pour bidouiller les mails via le .forward. Au moins, tes filtres sont clairs et les possibilités proche du CPAN !
  
  C'est juste deux exemples de petits trucs que j'ai du toucher ces derniers temps.
- [^]Re: Démocratisation
  
  Posté par Le Pnume () le 17/03/2010 à 11:58. (lien). Évalué à 3.
  Comment faire pour générer une chaîne de caractères aléatoires ? On utilise le code d'un programme écrit en Perl !
  
  Je sors aussi
  
  --
  "l'existence précède l'essence. Mais de peu !" (JBB)

Corrections

Posté par ChrisJ (page perso, ) le 16/03/2010 à 19:06. (lien). Évalué à 2.

Dans « Qu'est-ce que c'est » :
- « un jeu de chaînes » : « un ensemble de chaînes »
- « de les trouver..., de LES récupérer, de LEUR appliquer... »

Dans « L'histoire des expressions rationnelles » :
- « machines d'états » : ajouter « automates » ?
- « modèles rationnelles » : « modèles rationnels »

Dans « Les optimisations » :
- « Les références arrière sont indispensables, elles ne peuvent être supprimées des langages » : à mon avis, il faudrait préciser, parce qu'on peut très bien les supprimer d'un langage d'expressions rationnelles. Cela diminue son pouvoir d'expressivité, c'est tout.

[^]Re: Corrections

Posté par kenden () le 16/03/2010 à 19:52. (lien). Évalué à 5.
Merci pour l'article, il manquait juste un extrait de wikipedia je trouve :

De l'anglais regular expression dont l’abrégé est regexp, regex ou encore expreg. On emploie couramment le terme expression régulière car le terme anglais est regular expression qui s'abrège en regexp. Mais ne nous y trompons pas, en français, ce sont bien des expressions rationnelles.
- [^]Re: Corrections
  
  Posté par vermillon () le 16/03/2010 à 20:07. (lien). Évalué à 1.
  C'est la deuxième fois que je vois cette remarque aujourd'hui, mais je n'en n'ai pas vu l'explication. Une expression "régulière" suivrait une ou des règles, ce qui me semble être le cas. "rationnel", ça semble sous-entendre que l'expression est douée de raison et si je vais un peu plus loin, qu'elle réfléchit. Alors que les expressions régulières ne font qu'appliquer les règles données.
  
  Alors d'où vient l'utilisation de "rationnelle"? Est-ce que c'est simplement l'usage qui veut ça, ou y a-t-il de vraies "raisons"?
  
  --
  Membre de l'April - « promouvoir et défendre le logiciel libre » - http://www.april.org
  - [^]Re: Corrections
    
    Posté par Diagonale de Cantor (Jabber id, ) le 16/03/2010 à 21:41. (lien). Évalué à 3.
    "rationnel", ça semble sous-entendre que l'expression est douée de raiso
    Non pas du tout ! Rationnel ne veut pas seulement dire doué de raison (au sens intelligence). Par exemple on parle de nombres rationnels (les fractions), on parle aussi de la raison d'une suite géométrique. On retrouve ce sens dans le mot «ratio» (proportion entre deux valeurs de même nature). C'est un terme "courant" en math. Après le rapport exacte avec les expressions rationnelles, je ne sais pas trop. Mais ce n'est pas choquant à utiliser.
    si je vais un peu plus loin, qu'elle réfléchit.
    Euh non, là tu confond avec un miroir...
    ----> []
    
    --
    Debian Gnu/Emacs
    Membre de l'April
    - [^]Re: Corrections
      
      Posté par vermillon () le 16/03/2010 à 21:57. (lien). Évalué à 2.
      J'intègre bien le fait que rationnel a plusieurs sens. J'ai utilisé "ça semble sous-entendre" car justement, j'ai l'impression que l'emploi dans "expression rationnelle" pourrait être plus proche de "raisonnement" que d'un ratio.
      
      Cette impression est peut-être fausse, je cherche simplement à comprendre.
      
      --
      Membre de l'April - « promouvoir et défendre le logiciel libre » - http://www.april.org
  - [^]Re: Corrections
    
    Posté par B. (Jabber id, page perso, ) le 17/03/2010 à 10:50. (lien). Évalué à 3.
    Parce que ce n'est pas une question de « règles », mais parce que ces expressions peuvent décrire un langage rationnel, tout comme peut le faire un automate fini déterministe. Il existe d'autres langages qui utilisent également des règles mais ne sont pas pour autant des langages rationnels.
    - [^]Re: Corrections
      
      Posté par Mounir (page perso, ) le 17/03/2010 à 11:25. (lien). Évalué à 3.
      Justement, j'avais vu ça sous le nom de "langages réguliers" (différents des langages algébriques représentés par un automate à pile si ma mémoire est bonne).
      
      Ce serait bien de comprendre exactement ce qu'entend le sens "rationnel".
      
      --
      Ce n'est pas sur linux...
      - [^]Re: Corrections
        
        Posté par B. (Jabber id, page perso, ) le 17/03/2010 à 13:23. (lien). Évalué à 3.
        Je pense qu'il faut comprendre rationnel ici comme mécanique, reposant sur une méthode déductive. En effet, les règles de productions sont linéaires gauche ou droite (mais on ne mélange pas). Les mots du langages ne se construisent que dans un seul sens, comme dans une déduction logique.
  - [^]Re: Corrections
    
    Posté par fmaz fmaz () le 19/03/2010 à 09:02. (lien). Évalué à 1.
    Attention, je vais peut-être raconter des conneries ou tout du moins être dangereusement imprécis.
    
    Le "rationnel" vient des fractions rationnelles.
    
    En gros, si tu prends une fraction rationnelle que tu développes, tu obtiens un mot infini qui se reconnait très facilement avec un automate fini. Par exemple, 123/13=9.(461538)*.
    
    Pour les fractions d'entier, ça reste quand même très simple mais si on considère des trucs plus évolué à base de fraction polynomiales, on obtient des mots qui correspondent bien aux automates finis.
- [^]Re: Corrections
  
  Posté par Samuel Thibault (page perso, ) le 16/03/2010 à 20:43. (lien). Évalué à 1.
  Dans le cours d'informatique que j'avais eu, il y avait une distinction entre un langage rationnel et un langage régulier: l'un était défini par les règles:
  
  - le langage vide
  - des langages de mots d'une lettre.
  - des combinaisons de langages par union (\| en regexp).
  - des combinaisons de langages par concaténation (juxtaposition en regexp).
  - des répétitions d'un langage (* en regexp)
  
  et l'autre par le fait qu'il est reconnu par un automate fini. Je ne me souviens plus du tout lequel était nommé comment :)
  - [^]Re: Corrections
    
    Posté par Diagonale de Cantor (Jabber id, ) le 16/03/2010 à 21:46. (lien). Évalué à 3.
    Si mes souvenir sont bons, on parle d'expression régulière (définit par des règles algébriques) et de langage rationnel (définit par un automate).
    Par exemple l'expression régulière "(a|b)?c" représente le langage rationnel {c,ac,bc}
    
    --
    Debian Gnu/Emacs
    Membre de l'April

[^]Re: Corrections

Posté par weeber () le 16/03/2010 à 20:46. (lien). Évalué à 1.
Merci pour les corrections.
Pour les références arrières, ce que je voulais dire c'est qu'on ne peut pas les enlever d'un langage comme Perl, car comme tu le dis cela diminue leur expressivité mais aussi car on n'enlève pas une fonctionnalitée d'un langage comme cela simplement parce qu'elle est gourmande.

RE2 et références arrières.

Posté par jeberger (Jabber id, page perso, ) le 16/03/2010 à 20:01. (lien). Évalué à 6.

Les références arrière sont indispensables, elles ne peuvent être supprimées des langages.

Sauf que justement, RE2 les supprime! C'est comme ça qu'ils obtiennent le gain de vitesse...

[^]Re: RE2 et références arrières.

Posté par Franck V (Jabber id, ) le 16/03/2010 à 20:46. (lien). Évalué à 2.
En effet, d'après le site du projet [3] :

The one significant exception is that RE2 drops support for backreferences and generalized zero-width assertions, because they cannot be implemented efficiently
- [^]Re: RE2 et références arrières.
  
  Posté par weeber () le 16/03/2010 à 20:50. (lien). Évalué à 1.
  L'aspect important est le travail d'optimisation qui a été fait sur les algorithmes par l'auteur.
  RE2 n'implémente en effet pas toutes les expressions disponibles dans Perl:
  http://code.google.com/p/re2/wiki/Syntax
- [^]Re: RE2 et références arrières.
  
  Posté par Sytoka Modon (page perso, ) le 16/03/2010 à 23:21. (lien). Évalué à 2.
  Lorsqu'en Perl, on met
  
  m/toto.*?titi/
  
  je crois me souvenir qu'il ne fait pas de référence arrière du fait du ? après l'étoile. Il y a aussi la variante avec le + à la place du ? mais je ne l'ai jamais utilisé.
  - [^]Re: RE2 et références arrières.
    
    Posté par Duncan Idaho (page perso, ) le 17/03/2010 à 10:33. (lien). Évalué à 5.
    le ? après l'étoile ne sert pas plutôt pour éviter la "gloutonnerie" de l'* ?
    
    par exemple, si l'on veut matcher des balises façon XML
    
    <a>blabla</a>
    <a>blibli</a>
    
    si l'on fait m:<a>.*</a>: on va matcher blabla</a><a>blibli
    si l'on fait m:<a>.*?</a>: on va matcher blabla, puis blibli
    - [^]Re: RE2 et références arrières.
      
      Posté par zecrazytux (Jabber id, page perso, ) le 17/03/2010 à 10:49. (lien). Évalué à 3.
      si, c'est ça (greedy en anglais)
  - [^]Re: RE2 et références arrières.
    
    Posté par Moonz () le 21/03/2010 à 21:06. (lien). Évalué à 1.
    La variante avec le +, c’est pour empêcher le moteur d’enregistrer des états pour le backtracking ; en gros, c’est "ce que je prend, je le rend jamais" (d’où le nom: opérateur possessif)
    
    Si tu veux en savoir plus, je te conseille ça: http://oreilly.com/catalog/9781565922570
    
    En gros, a++a ne fonctionnera jamais, au contraire de a+a. Cas d’utilisation typique: matcher une string C/C++: un machin entre guillemets doubles pouvant contenir des guillemets doubles échappés et des caractères d’échappement échappés (de tête):
    
    "(\.|[^"\])++"
    
    Sans le ++, cette expression reconnaît très bien : "hello\" alors qu’on ne le veut pas
    
    --
    Saying that Java is good because it works on all platforms is like saying anal sex is good because it works on all genders.

Bon, résultat ?

Posté par yoho (page perso, ) le 17/03/2010 à 23:26. (lien). Évalué à 1.

Est-ce que perl, python, etc... vont finir par utiliser RE2 ou non ?

Utilisant perl en tant qu'administrateur système, mis à part les backreference style "\1", il n'y a rien qui me manquerait dans RE2 (et encore, je les utilises rarement) quand je regarde les expressions grisées ici : http://code.google.com/p/re2/wiki/Syntax

Question subsidiaire : il y a-t-il une différence entre "expressions rationnelles" et "expressions régulières" ?

[^]License = frein ?

Posté par yoho (page perso, ) le 17/03/2010 à 23:27. (lien). Évalué à 1.
Ah, mais en fait, la license n'est pas vraiment GPL. C'est plus du "faîtes ce que vous voulez avec ce morceau de code" : http://code.google.com/p/re2/source/browse/LICENSE

[^]Re: Bon, résultat ?

Posté par rictus (page perso, ) le 18/03/2010 à 14:07. (lien). Évalué à 2.
Question subsidiaire : il y a-t-il une différence entre expressions rationnelles et expressions régulières ?

Oui, « expression régulière » est une traduction pas très heureuse de l'anglais « regular expression ». C'est plus correct en français d'utiliser « expression rationnelle ». Mais à part cela, c'est la même chose.

[^]Re: Bon, résultat ?

Posté par __o () le 18/03/2010 à 18:44. (lien). Évalué à 2.
J'ai cru voir qu'il y avait déjà un module en développement pour PHP, je suppose qu'il y en aura aussi pour d'autres langages (il suffit que quelqu'un s'y mette).

Revenir en haut de page

Articles précédents : Développeur

Liens connexes

Dépêche modérée par

Dépêche éditée par

Développeur : Google libère la bibliothèque d'expressions rationnelles RE2

Dur

[^]Re: Dur

[^]Re: Dur

[^]Re: Dur

[^]Re: Dur

comparatif graphique

[^]Re: comparatif graphique

[^]Re: comparatif graphique

[^]Re: comparatif graphique

Démocratisation

[^]Re: Démocratisation

[^]Re: Démocratisation

[^]Re: Démocratisation

[^]Re: Démocratisation

[^]Re: Démocratisation

[^]Re: Démocratisation

[^]Re: Démocratisation

[+] [^]Re: Démocratisation

[^]Re: Démocratisation

[^]Re: Démocratisation

[^]Re: Démocratisation

[^]Re: Démocratisation

[^]Re: Démocratisation

[^]Re: Démocratisation

[^]Re: Démocratisation

Corrections

[^]Re: Corrections

[^]Re: Corrections

[^]Re: Corrections

[^]Re: Corrections

[^]Re: Corrections

[^]Re: Corrections

[^]Re: Corrections

[^]Re: Corrections

[^]Re: Corrections

[^]Re: Corrections

[^]Re: Corrections

RE2 et références arrières.

[^]Re: RE2 et références arrières.

[^]Re: RE2 et références arrières.

[^]Re: RE2 et références arrières.

[^]Re: RE2 et références arrières.

[^]Re: RE2 et références arrières.

[^]Re: RE2 et références arrières.

Bon, résultat ?

[^]License = frein ?

[^]Re: Bon, résultat ?

[^]Re: Bon, résultat ?