théorie des automates et langages formels

grammaires de recherche de correspondances

• DFA : deterministic finite automaton

• NFA : nondeterministic finite automaton

principale différence : la gestion du retour arrière (backtracking)

UNIX : qed, ed, grep (BRE, puis ERE)

POSIX regex (BRE, ERE)

Perl 5, PCRE, Onigurama, (RE2 (DFA amélioré))

Perl 6

correspondance de caractères

motif composé de :

• caractères normaux

•     "Hello World" =~ /World/;       # correspond

•     "Hello World" =~ /lo Wo/;       # correspond aussi

•     "That hat is red" =~ /hat/;     # le "hat" de "That" correspond

ensemble de caractères possibles pour un emplacement de caractère

notées par [...]

    /[bcr]at/;          # cherche "bat", "cat", "rat"

    /[yY][eE][sS]/;     # cherche "yes", "Yes", YES", etc

    /yes/i;             # pareil, mais plus lisible

intervalles de caractères

    /[0-9]/;    # équivalent à /[0123456789]/

    /[a-z]/;    # équivalent à /[abcde...xyz]/

    /[0-9a-fA-F]/;  # chiffre hexadécimal

    /item[0-9]/;    # correspond à "item0", "item1"...

négation de classe : [^...]

    /[^0-9]/;   # cherche un caractère qui n'est pas un chiffre

classes prédéfinies :

• . : tout caractère sauf \n

• \d : chiffre décimal

• \w : caractère de mot (alphanumérique plus _)

• \s : espace normale, tabulation, saut de ligne

• \h : espace horizontal

• \v : espace vertical

• \R : saut de ligne

classes négatives prédéfinies :

• \D : ce qui n'est pas un chiffre décimal

• \W : ce qui n'est pas un caractère de mot

• \S : ce qui n'est pas un espace usuel

• \H : ce qui n'est pas un espace horizontal

• \V : ce qui n'est pas un espace vertical

exemples :

•     /\d\d:\d\d:\d\d/;   # format d'heure hh:mm:ss

•     /[-+]\d/;       # correspond à +2, -3, etc

•     /end\./;        # correspond à "end."
      /end[.]/;       # pareil

pour ancrer la recherche dans certains points

^ : en début de chaine

    "beausoleil" =~ /^soleil/;      # ne correspond pas

$ : en fin de chaine

    "beausoleil" =~ /beau$/;        # ne correspond pas

    "beausoleil" =~ /soleil$/;      # correspond

    "beausoleil\n" =~ /soleil$/;    # correspond aussi

\b : frontière de mot, intervient entre \w et \W

    "beausoleil" =~ /\bbeau/;       # correspond

    "beausoleil" =~ /\bbeau\b/;     # ne correspond pas

    "beausoleil" =~ /\bsoleil/;     # ne correspond pas

répétition d'un sous-motif

• * : zéro ou plusieurs fois

• + : une ou plusieurs fois

• ? : zéro ou une fois

• {n} : exactement n fois

• {n,} : au moins n fois

• {n,m} : entre n et m fois

exemples :

    "kraaack" =~ /kra+ck/;      # correspond

    "kraaack" =~ /kra{1,}ck/;   # correspond aussi

    "kraaack" =~ /kra{5,}ck/;   # ne correspond pas

    /\w+\d{2}/;                 # "item04", "machine42", "Kevin68", etc

    /\d+\.\d+\.\d+\.\d+/;       # recherche simple d'une adresse IPv4

    /<[-.\w]+\@[-.\w]+>/;       # recherche simple d'une adresse mail

    "aaaa" =~ /a+/;             # correspond avec "aaaa"

quantifieurs non avides :

• *? : zéro ou plusieurs fois, au plus tôt

• +? : une ou plusieurs fois, au plus tôt

• ?? : zéro ou une fois, au plus tôt

• {n}? : exactement n fois, au plus tôt

• {n,}? : au moins n fois, au plus tôt

• {n,m}? : entre n et m fois, au plus tôt

exemples :

    "aaaa" =~ /a+?/;            # correspond avec "a"
     ^

    "aaaabbbb" =~ /a+?b*?/;     # correspond avec "a"
     ^

    "aaaabbbb" =~ /a+?b+?/;     # correspond avec "aaaab"
     ^^^^^

quantifieurs possessifs (nouveauté de Perl 5.10 et PCRE 7)

• *+ : zéro ou plusieurs fois, et ne rend jamais

• ++ : une ou plusieurs fois, et ne rend jamais

• ?+ : zéro ou une fois, et ne rend jamais

• {n}+ : exactement n fois, et ne rend jamais

• {n,}+ : au moins n fois, et ne rend jamais

• {n,m}+ : entre n et m fois, et ne rend jamais

exemples :

    "aaaa" =~ /a+a/;   # /a+/ correspond avec "aaa"
     ^^^

    "aaaa" =~ /a+?a/;  # /a+?/ correspond avec "a"
     ^

    "aaaa" =~ /a++a/;  # /a++/ ne correspond pas

résumé :

                            "Lorem ipsum dolor sit amet"
  recherche avide :          <<--| <<--| <<--| <<<<<--|
  recherche non-avide :      |--->>> |---> |--->> |--->
  recherche possessive :     |---| |---| |---| |------|

pour grouper des sous-motifs : (...)

par défaut, groupes capturant

référencées par \1, \2... dans le motif

référencées par $1, $2... en dehors du motif

groupes non-capturant : (?:...)

exemples :

    /(\w+\d+ )+/;           # "item04 machine42 Kevin68 "

    /(?:\d+\.){3}\d+/;     # recherche simple d'une adresse IPv4

    /((?:\d+\.){3}\d+)/;    # recherche simple d'une adresse IPv4

    /(\w+) +\1/;            # recherche d'un mot répété

disjonction de sous-motifs au sein d'un groupe

exemple :

    /^(add|del|list) +(addr|route|rule|table) .../
        # "add addr ..."
        # "del rule ..."
        # "list route ..."

problème de la numérotation des captures

    / ( a )  (?: x ( y ) z | (p (q) r) | (t) u (v) ) ( z ) /x
    # 1            2         3  4        5     6     7

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;

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

modificateurs : /i, /m, /s, /x, /p, /r, /g, /c, /a, /d, /l, /u

assertion keep, \K

assertion \G

assertions de longueur nulle de recherche alentours, positive ou négative : (?=..), (!..), (?<=..)>, (?<!..)

ensembles de classes (?[...])

évaluation de code à la volée : (?{ code }), (??{ code })

verbes de contrôle : (*PRUNE), (*SKIP), (*THEN), (*COMMIT), (*FAIL), (*ACCEPT)

Unicode

possibles en Perl 5.8, mais de manière horrible

syntaxe mis au propre dans PCRE

principe : réinvocation d'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

 my $log = "192.168.1.11 -> 192.168.1.12 connect tcp 80";

 $log =~ 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