Les nouveautés des expressions régulières de Perl 5.10 et PCRE 7

Sébastien Aperghis-Tramoni, sebastien@aperghis.net

Assertion keep

  • cf. Regexp::Keep de Jeff Pinyan sur le CPAN

  • préserve la partie à gauche de \K

  • s/(save)delete/$1/ devient s/save\Kdelete//

  • identique mais bien plus rapide

    • fonctionne par simple déplacement de pointeur, au lieu de réaliser des sauvegardes et copies de chaînes

  • <( et )> en Perl 6

Internes P5RE - dérécursion du moteur

  • avant : fonction regmatch() récursive

  • maintenant : gestion manuelle de la récursion

  • consommation mémoire moindre

  • suppression de plusieurs limitations

  • suppression de nombreux bugs

Internes PCRE - gestion de la récursion du moteur

  • fonction pcre_exec() récursive par match()

  • mais plusieurs protections pour limiter la casse

Internes P5RE - optimisation des classes à un caractère

  • /[a]/

  • maintenant transformée en a

  • petit gain en mémoire

  • gain en vitesse car les classes interfèrent avec les optimisations de Boyer-Moore

Internes P5RE - optimisation par tries

  • trie (retrieval), ou prefix-tree

  • structure d'arbre ordonné utilisée pour stocker un tableau associatif

  • construites par le chemin parcouru pour arriver jusqu'à chaque nœud

  • accès en O(m) (avec m la longueur de la clé)

  • aussi utilisé pour déterminer déterminer le plus long préfixe commun

  • exemple : correcteurs orthographiques

Internes P5RE - optimisation par tries

  • ici utilisé pour optimiser les branches d'une alternative

  • branches littérales fusionnées en un trie

  • comparaison simultanée de N branches en temps constant au lieu de O(N)

  • ${^RE_TRIE_MAXBUF}

Internes P5RE - optimisation Aho-Corasick

  • augmente le trie de liens internes

  • chaque nœud pointe vers le nœud représentant le plus long suffixe correspondant

  • puis recherche des plus longs suffixes qui sont aussi des préfixes d'autres alternatives du trie

Internes P5RE - optimisation Aho-Corasick

  • exemple

        "abcdgu" =~ /abcdefg|cdgu/
  •         abcdgu
            ||||
            abcdefg
              cdgu
               ^

Internes P5RE - tries + Aho-Corasick

  • permet typiquement d'optimiser ce genre de constructions

  •     my $words_str = join "|", @words;
    
        if ($string =~ /($words_str)/) {
            # le mot capturé est dans $1
        }

Questions ?

Merci