Les nouvelles expressions régulières de Perl 5.10 et PCRE 7

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

Terminologie

  • PCRE = Perl-compatible regular expressions

  • P5RE = moteur d'expressions régulières de Perl 5

  • NFA = nondeterministic finite automaton

  • DFA = deterministic finite automaton

Nouveautés

  • proviennent de

    • PCRE

    • Perl 5

    • Perl 6

    • CPAN

Nouveaux quantifieurs

  • quantifieurs possessifs

  •     *+      correspond 0 ou plusieurs fois, et ne rend jamais
        ++      correspond 1 ou plusieurs fois, et ne rend jamais
        ?+      correspond 0 ou 1 fois, et ne rend jamais
        {n}+    correspond exactement n fois et ne rend jamais
        {n,}+   correspond au moins n fois et ne rend jamais
        {n,m}+  correspond au moins n fois mais pas plus que m fois, 
                et ne rend jamais

Nouveaux quantifieurs

  • exemple

  •     "aaaa" =~ /(a+)a/;   # $1 contient "aaa"
        "aaaa" =~ /(a+?)a/;  # $1 contient "a"
        "aaaa" =~ /(a++)a/;  # échoue

Assertions de caractères

  • \h, \H : espaces horizontaux

    • TAB, SPC, NBSP, 12 types d'espaces typographiques, séparateur de voyelles mongoles, espace mathématique moyen, espace idéographique

  • \v, \V : espaces verticaux

    • VT, LF, FF, CR, NEL, LS, PS

  • \R : saut de ligne

    • LF, CR, CRLF, VT, FF, NEL

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

Nouveaux verbes

  • P5RE et PCRE : NFA

  • utilisation du retour arrière (backtracking) pour offrir des fonctionnalités avancées

  • mais coût non négligeable

  • objectif des verbes : contrôler le retour arrière

Nouveaux verbes

  • forme : (*VERB:ARG)

  • si succès, $REGMARK = nom du dernier (*MARK:NAME) exécuté

  • si échec, $REGERROR = argument du dernier verbe exécuté, ou dernier (*MARK:NAME) exécuté

Nouveaux verbes

  • (*MARK:NAME), (*:NAME)

  • marque la position courante dans la chaîne

  • permet de voir le chemin suivi par le moteur pour établir une correspondance

  •     /z+lonk(*MARK:zlonk)|qun+ck+(*MARK:qunck)|cr+a+ck(*MARK:crack)/

Nouveaux verbes

  • (*FAIL), (*F)

  • équivalent à (?!)

  • force le retour arrière

  • similaire à la recherche exhaustive de Perl 6

Nouveaux verbes

  • (*ACCEPT)

  • force l'acceptation de la correspondance courante du motif

  • return pour regexp

Nouveaux verbes

  • (*PRUNE), (*PRUNE:NAME)

  • si retour arrière dessus, fait échouer la correspondance à la position de départ courante

Nouveaux verbes

  • (*SKIP), (*SKIP:NAME)

  • si retour arrière dessus, saute jusqu'à la position du verbe ou au (*MARK) correspondant

Nouveaux verbes

  • (*THEN), (*THEN:NAME)

  • à utiliser au sein d'un groupe d'alternatives

  • si retour arrière dessus, fait passer le moteur à la branche suivante

  • opérateur :: (cut group) en Perl 6

  •     /( COND1 (*THEN) SUBPATTERN1 | COND2 (*THEN) SUBPATTERN2 )/x

Nouveaux verbes

  • (*COMMIT)

  • si retour arrière dessus, arrêt immédiat par échec de la correspondance

  • opérateur ::: (commit) en Perl 6

Captures numérotées

  • remise à zéro de branche : (?|..)

  • numérote les captures des branches d'une alternative comme s'il n'y en avait qu'une seule

  •     # before  ------------branch-reset-------------  after
        / ( a )  (?| x ( y ) z | (p (q) r) | (t) u (v) ) ( z ) /x
        # 1            2         2  3        2     3     4

Captures numérotées

  • nouvelle syntaxe de référencement : \g{N}

  • N positif : numéro de capture usuel

  • N négatif : référencement arrière relatif

  • \g{-1} == précédente capture

  • exemple

        my $find_dup = qr/ (\w+) \s+ \g{-1} /x;

Captures nommées

  • (?<name>pattern) pour nommer une capture

  • \k<name>, \k{name} ou \g{name} pour s'y référer

  • exemple

        my $find_dup = qr/ (?<dup_word>\w+) \s+ \k<dup_word> /x;
  • syntaxe Python supportée

        find_dup = re.compile("(?P<dup_word>\w+) \s+ (?P=dup_word)", "x")

Captures nommées

  • variables lexicales %+ et %-

  • $+{name} == \g{name}

  • $-{name} == référence vers un tableau de toutes les captures de ce nom

  • Tie::Hash::NamedCapture pour avoir des noms plus clairs

Motifs récursifs

  • possibles en Perl 5.8, mais de manière horrible

  • syntaxe mis au propre dans PCRE

  • principe : permettre de ré-invoquer un groupe capturant avec (?PARNO)

  • PARNO == numéro de parenthèse (groupe capturant)

  • si précédé d'un signe, compris de manière relative

Motifs récursifs

  • (?2) => le 2e groupe déclaré

  • (?-1) => dernier groupe déclaré

  • (?+1) => prochain groupe qui sera déclaré

  • (?0) ou (?R) pour ré-invoquer le motif complet

  • (?&name) => invoque un groupe nommé

Motifs récursifs

  • reconnaissance de parenthèses imbriquées :

  •   $s  = "( crack ( kapow ) ( klang ) ouch )";
    
      $re = qr{ (           # groupe #1
                            \(             # parenthèse ouvrante
                            (?:
                                  (?> [^()]+ )    # groupe sans retour arrière
                              |
                                  (?1)            # groupe avec parenthèses 
                            )*
                            \)             # parenthèse fermante
                          )
                      }x;

Motifs récursifs

  • (?(condition)yes-pattern|no-pattern) => construction conditionnelle, accepte :

    • un numéro de groupe (1), (2)...

    • un nom de groupe <name>

    • un bout de code Perl (?{ CODE })

    • (R) pour vérifie si évaluée au sein d'une récursion

    • avec numéro ((R1), (R2)..) ou nom ((R&name)) d'un groupe pour vérifier si évaluée pendant l'exécution du groupe

Motifs récursifs

  • cas particulier : (DEFINE)

  • seule la partie yes-pattern est autorisée

  • n'est pas directement exécutée

  • mais peut entrer dedans en récursion

  • permet donc de définir des fonctions de regexps

Motifs récursifs

  •     "192.168.1.11 -> 192.168.1.12 connect tcp 80";
    
        m{
                (?<src_addr>(?&ip_addr))    # adresse IP source
                \s+ -> \s+
                (?<dest_addr>(?&ip_addr))   # adresse IP destination
    
                (?(DEFINE)
                        (?<ip_addr>...)     # motif pour reconnaître une 
                )                       # addresse IP
        }x

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
        }

Internes P5RE - plugins

  • moteur de regexp de Perl5 désintriqué des internes de Perl5

  • cf. perlreapi

  • support d'autres moteurs

re::engine::PCRE

  • moteur PCRE

  • a encore des extensions non reconnues par P5RE

  •     use re::engine::PCRE;
    
        if ("Hello, world" =~ /(?<=Hello|Hi), (world)/) {
            say "OH HAI \U$1"
        }
  • P5RE : "Variable length lookbehind not implemented"

re::engine::POSIX

  • moteur POSIX (IEEE Std 1003.1-2001) natif de l'OS

  •     use re::engine::POSIX;
    
        if ("mooh!" =~ /\([mo]*\)/) {
            say $1    # "moo"
        }

re::engine::TRE

  • moteur TRE, "strictement" conforme POSIX

  •     use re::engine::TRE;
        if ("the string" =~ /\(.\{3\}\)/) {
            say $1    # "the"
        }
  • support de correspondance floue, en utilisant la distance de Levenshtein

re::engine::PCR

  • moteur Pugs::Compiler::Rule

  •     use re::engine::PCR;
    
        if ("123" =~ q/$<x> := (.) $<y> := (.)/) {
            # on stocke le premier caractère dans le buffer 
            # nommé "x" et le second dans le buffer "y"
            say "x=$+{x}, y=$+{y}";    # "x=1, y=2"
        }

re::engine::Oniguruma

  • moteur Oniguruma (utilisé par Ruby 1.9)

  • support d'une trentaine d'encodage de caractères différents

  • support de la syntaxe PCRE

  • inclus dans la distribution

re::engine::Plugin

  • permet d'étendre la syntaxe des regexps en Perl

  • utilisé pour re::engine::PCR

Internes P5RE - debug lexical

  • pragma re lexicale :

  •     use re "debug";
        "moo" =~ /m[aeiouy]+/;
    
        no re "debug";
        "meh" =~ /m\w+/;
  • contexte retenu dans les regexps compilées :

  •     use re "debug";
        $reg = qr/m[aeiouy]+/;
    
        no re "debug";
        "moo" =~ $reg;

Article

Questions ?

Merci