PCRE = Perl-compatible regular expressions
P5RE = moteur d'expressions régulières de Perl 5
NFA = nondeterministic finite automaton
DFA = deterministic finite automaton
proviennent de
PCRE
Perl 5
Perl 6
CPAN
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
exemple
"aaaa" =~ /(a+)a/; # $1 contient "aaa" "aaaa" =~ /(a+?)a/; # $1 contient "a" "aaaa" =~ /(a++)a/; # échoue
\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
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
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
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é
(*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)/
(*FAIL)
, (*F)
équivalent à (?!)
force le retour arrière
similaire à la recherche exhaustive de Perl 6
(*ACCEPT)
force l'acceptation de la correspondance courante du motif
return
pour regexp
(*PRUNE)
, (*PRUNE:NAME)
si retour arrière dessus, fait échouer la correspondance à la position de départ courante
(*SKIP)
, (*SKIP:NAME)
si retour arrière dessus, saute jusqu'à la position du verbe ou au (*MARK)
correspondant
(*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
(*COMMIT)
si retour arrière dessus, arrêt immédiat par échec de la correspondance
opérateur :::
(commit) en Perl 6
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
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;
(?<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")
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
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
(?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é
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;
(?(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
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
"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
avant : fonction regmatch()
récursive
maintenant : gestion manuelle de la récursion
consommation mémoire moindre
suppression de plusieurs limitations
suppression de nombreux bugs
fonction pcre_exec()
récursive par match()
mais plusieurs protections pour limiter la casse
/[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
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
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}
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
exemple
"abcdgu" =~ /abcdefg|cdgu/
abcdgu |||| abcdefg cdgu ^
permet typiquement d'optimiser ce genre de constructions
my $words_str = join "|", @words; if ($string =~ /($words_str)/) { # le mot capturé est dans $1 }
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
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;
publié dans Linux Magazine France n°106