Planche : 1

Plan

À quoi ça sert ? À jouer aux mots-croisés (entre autres) ! Mais aussi :

Planche : 2

Jeux avec les mots

Soient A et B deux humains, A joue aux mots croisés, B l’aide :

Dans les questions de A, il y a une partie typiquement humaine, et une autre plus simple.

Si B est un ordinateur, on peut donner des motifs…

Si on dispose d’un fichiers de mots, on peut extraire les mots qui conviennent par egrep, par exemple egrep -x ’.x...n.’ file

Planche : 3

La répétition

Pour se donner plus de liberté, on introduit *

Essayez pour voir : 

# egrep -x '.*k.*k.*' /usr/share/dict/french
bookmaker
bookmakers
  ...

Planche : 4

Les mots

Planche : 5

Opérations sur les mots

Un mot est par exemple m = a0a1⋯an−1 (n longueur de m).

Planche : 6

Les mots sont des chaînes

La classe String, du package (importé par défaut) java.lang.

Planche : 7

Opérations sur les langages

Planche : 8

Les expressions régulières

Une représentation p d’un langage L.

Pour l’informaticien, la définition mérite une décomposition en syntaxe et sémantique.

Planche : 9

Syntaxe des expressions régulières

Un motif p est défini ainsi.

Important C’est une définition de structure d’arbre, sans plus de précisions.

P = { є } ⊎ Σ ⊎ (P × { |, · } × P) ⊎ (P × { * })

Planche : 10

Exemple de motif

En pratique on écrit (syntaxe concrète)

(a·(b*))|(b·(a*)) ou plus simplement ab*|ba*

Planche : 11

Priorités des opérateurs

C’est comme pour les expressions arithmétiques. Par ordre croissant de priorité.



Donc

Planche : 12

Encore plus précis

Planche : 13

Les priorités ne résolvent pas tout

Comment comprendre abc, comme a(bc) ou (ab)c ?

Cela n’a au final pas d’importance, en raison de l’associativité de la concaténation.

Mais il y a bien deux arbres possibles.

Un dernier détail : on peut représenter le motif vide par ().

Planche : 14

Sémantique des expressions régulières

La fonction [[·]], définie des motifs dans les ensembles de mots, associe une valeur à chaque motif.

[[є]]={ є }
[[c]]={ c }
[[p1|p2]]=[[p1]] ⋃ [[p2]]
[[p1·p2]]=[[p1]] · [[p2]]
[[p*]]=[[p]]*

Inversement,

Un langage L est dit régulier quand il existe un motif p tel que [[p]] = L.

Planche : 15

Exemples de langages réguliers
(01)*|(01)*0|(10)*|(10)*1

Planche : 16

Ou mieux (|1)(01)*(|0)

Mots constitués de 0 et 1 alternés.

Soit (01)*|(01)*0|1(01)*|1(01)*0.

(L · L1) ⋃ (L · L2) = L ·  (L1 ⋃ L2)
L · { є } = L

Soit ((01)*|(|0))|(1(01)*(|0)).

(L1 · L) ⋃ (L2 · L) = (L1 ⋃ L2) · L
{ є } · L = L

Soit (|1)(01)*(|0).

Planche : 17

Filtrage

Si m ∈ [[p]], on dit que p filtre m, noté p ≼ m.

Définition formelle par axiomes et règles d’inférences.

Empty
є ≼ є
Char
c ≼ c
Seq
p1 ≼ m1           p2 ≼ m2
p1p2 ≼ m1m2
OrLeft
p1 ≼ m
p1|p2 ≼ m
OrRight
p2 ≼ m
p1|p2 ≼ m
StarEmpty
p* ≼ є
StarSeq
p ≼ m1           p* ≼ m2
p* ≼ m1m2

Planche : 18

Arbre de dérivation

Un tel arbre donne une preuve, par exemple de ab*|ba* ≼ baa.

b ≼ b          
a ≼ a          
a ≼ a          a* ≼ є
a* ≼ a
a* ≺ aa
ba* ≼ baa
ab*|ba* ≼ baa



C’est un premier emploi de la définition formelle du filtrage.

Autres emplois (des règles d’inférence).

Planche : 19

Notations supplémentaires

Exprimables avec les constructions de base, elle n’étendent pas la classe des langages réguliers.

Planche : 20

Notations supplémentaires

Il y a aussi les citations, introduites par « \ ».

Les entiers décimaux.

0|[1-9][0-9]*, ou plus tolérant [0-9]+

Planche : 21

Les entiers de Java
(0|[1-9][0-9]*)|0[xX][0-9a-fA-F]+|0[0-7]+

Conclusion, pour Java, 0 est décimal, 0x0 est hexadécimal, et 00 est octal.

Planche : 22

Les commentaires de Java

Première sorte de commentaire

//[^\n]*\n

Seconde sorte de commentaire.

/\*([^*]|\*+[^*/])*\*+/

Planche : 23

Le shell et les expressions régulières

Ces expressions régulières s’appliquent aux noms de fichier. La syntaxe est spéciale.



Exemples

Planche : 24

Recherche de lignes dans un fichier

La commande egrep 

% egrep motif nom1 nom2 …

Affiche les lignes de nom1 nom2 … dont un sous-mot est filtré par motif.

Planche : 25

Changements automatisés

La commande sed -e ’s/p/m/g’ permet de remplacer les mots qui filtrés par p par m.

Exemple : le dictionnaire sans diacritiques français : 

# sed -e 's/à\|â/a/g' -e 's/ë\|é\|ê\|è/e/g' \
    -e 's/ï\|î/i/g' -e 's/ô/o/g' -e 's/ü\|û\|ù/u/g' \
    -e 's/ç/c/g' /usr/share/dict/french

Syntaxe bizarre de l’alternative : « \| ».

Planche : 26

Implémentation des expressions régulières

Planche : 27

Classe des arbres de syntaxe abstraite

C’est du déjà-vu (amphi 05)

class Re {
  private final static int EMPTY=0, CHAR=1, WILD=2,
    OR=3, SEQ=4, STAR=5 ;

  private int tag ;
  private char asChar ;
  private Re p1, p2 ;

  private Re(int tag) { this.tag = tag ; }
    …
}

Planche : 28

Fabriquer les nœuds de l’arbre

On reprend le modèle « factory » (des méthodes statiques de la classe Re qui appellent le constructeur).

private Re empty() { return  Re (EMPTY) ; }

static empty = empty() ; // Pour éviter quelques allocations

static Re charPat(char c) { // Impossible à nommer « char »
  Re r = new Re(CHAR) ; r.asChar = c ;
  return r ;
}

static Re star(Re p) {
  Re r = new Re(STAR) ; r.p1 = p ;
  return p ;
}
…

Planche : 29

Rien n’empêche…

D’ajouter d’autres méthodes statiques « de construction ».


static Re plus(Re p) {
  return seq(p, star(p)) ;
}

static Re opt(Re p) {
  return or(empty(), p) ;
}

Planche : 30

Le motif i.*….*i
static Re buildAtLeast(int k, char c) {
  if (k <= 0) {
    return Re.empty() ;
  } else if (k == 1) {
    return Re.charPat(c) ;
  } else {
    return
      Re.seq
       (Re.charPat(c),
        Re.seq(Re.star(Re.wild()), buildAtLeast(k-1, c)))
  }
}

Appeler par ex. atLeast(6, 'i')

Planche : 31

Écrire EGrep nous même, main

Que du classique (normalement).

class EGrep {
  public static void main(String [] arg) {
    try {
      BufferedReader in =
        new BufferedReader (new FileReader (arg[1])) ;
      grep(arg[0], in) ;
      in.close() ;
    } catch (IOException e) {
      System.err.println("Malaise: " + e.getMessage()) ;
      System.exit(2) ;
    }
  }
  ⋮
}

Planche : 32

Méthode grep
// Affiche les lignes de in dont un sous-mot est filtré par p  
static void grep(String p, BufferedReader in)
  throws IOException {
    Re pat = Re.parse(p) ; // ▷ 431
    String line = in.readLine() ;
    while (line != null) {
      if (submatches(pat, line)) {
        System.out.println(line) ;
      }
      line = in.readLine() ;
    }
  }

Planche : 33

Enfin le vrai travail ?

Supposons donnée, dans la classe Re (pourquoi ? tout est privé dans Re), une méthode

static boolean matches(Re pat, String text, int i, int j)

Qui nous dit si pat filtre le sous-mot text[i…j[, ou pas.

Alors, il suffit d’essayer tous les sous-mots de text.

static boolean submatches(Re pat, String text) {
  for (int i = 0 ; i <= text.length() ; i++)
    for (int j = i ; j <= text.length() ; j++)
      if (Re.matches(pat, text, i, j)) return true
  return false ;
}

Planche : 34

Filtrage, cas faciles
// Test  de pat ≼ text[i…j[
static boolean matches(String text, Re pat, int i, int j) {
  switch (pat.tag) {
    case EMPTY:
      return i == j ;
    case CHAR:
      return i+1 == j && text.charAt(i) == pat.asChar ;
    case WILD:
      return i+1 == j ;
    ⋮
  }
  throw new Error ("Arbre Re incorrect") ;
}

Planche : 35

L’alternative

Essayer les deux règles possibles.

OrLeft
p1 ≼ m
p1|p2 ≼ m
OrRight
p2 ≼ m
p1|p2 ≼ m
    case OR:
      return
        matches(text, pat.p1, i, j) ||
        matches(text, pat.p2, i, j) ;

Planche : 36

La séquence

Essayer la règle

Seq
p1 ≼ m1           p2 ≼ m2
p1p2 ≼ m1m2

Pour toutes les divisions m1 = t[i⋯k[, m2 = t[k⋯j[.

    case SEQ:
      for (int k = i ; k <= j ; k++) {
        if (matches(text, pat.p1, i, k) &&
            matches(text, pat.p2, k, j))
          return true ;
      }
      return false ;

Planche : 37

La répétition

Deux règles,

StarEmpty
p* ≼ є
StarSeq
p ≼ m1           p* ≼ m2
p* ≼ m1m2

Il faut appliquer la seconde « de toutes les façons possibles ».

    case STAR:
      if (i == j) {
        return true ;
      } else {
        for (int k = i+1 ; k <= j ; k++) {
          if (matches(text, pat.p1, i, k) &&
              matches(text, pat, k, j))
            return true ;
        }
        return false ;
      }

Planche : 38

Un détail qui a son importance

Pourquoi ?

Planche : 39

Expressions régulières en Java

Classes Pattern et Matcher du package java.util.regexp.

Architecture en deux classes :

Planche : 40

Les filtreurs

Un objet Matcher cache un motif (this lors de l’appel à matcher) et une entrée (l’argument input de l’appel à matcher).

Par ex. savoir si sub est présent deux fois dans text.

static boolean twice(String sub, String text) {
  Pattern pat = Pattern.compile(sub + ".*" + sub) ;
  Matcher m = pat.matcher(text) ;
  return m.find() ;
}

Planche : 41

Justification de la classe Matcher

Les objets Matcher cachent un état qui évolue lors du filtrage.

Planche : 42

Un problème sémantique

Sommes nous bien sûr que allInts affiche tous les entiers de text ?

Autrement dit, quel sous-mot de text est filtré par "[0-9]+" ?

12
1 
34
2
1
1
2
2 
3
3
4
4
12 
34
1

Deux règles possibles :

Attention, la bibliothèque Java a une autre seconde règle. Elle spécifie que + est avide, ici cela revient au même.

Planche : 43

Retour sur notre submatches

Le voici, qui renvoie le sous-mot filtré.

static String submatches(Re pat, String text) {
  for (int i = 0 ; i <= text.length() ; i++) // Plus à gauche, ok.
    for (int j = i ; j <= text.length() ; j++) // Plus court
      if (Re.matches(pat, text, i, j))
        return text.substring(i,j) ;
  return null ;
}

Code pour le plus à gauche–le plus long.

static String submatches(Re pat, String text) {
  for (int i = 0 ; i <= text.length() ; i++) // Plus à gauche, ok.
    for (int j = text.length() ; j >= i ; j--) // Plus long
      if (Re.matches(pat, text, i, j))
         return text.substring(i,j) ;
  return null ;
}

Planche : 44

Dérivation des motifs

Soit L langage et c caractère, on définit le langage dérivé c−1·L.

c−1·L ={ m ∣ c·m ∈ L }

Exemples

Planche : 45

Théorème (carrément)

Si L est régulier, alors c−1·L est régulier.

C’est à dire il faut trouver un motif c−1·p tel que

[[c−1·p]] = c−1·[[p]]

Si le thérorème est vrai (et si nous savons décider p ≼ є) il permet de décider le filtrage de m par p facilement.

  1. Si m = є
    1. Si p ≼ є, alors renvoyer vrai.
    2. Sinon, renvoyer, faux.
  2. Si m = cm′, poser p = c−1·p et m = m′, aller en 1.

Planche : 46

Dérivation, cas faciles

Commençons par étendre les motifs, soit ∅ le motif tel que [[∅]] = ∅.

c−1·∅=∅
c−1·є=∅
c−1·c=є
c−1·c′=∅pour c ≠c′
c−1·(p1|p2)=(c−1·p1)|(c−1·p2)

Planche : 47

Décider p ≼ є

Définir un prédicat N tel que p ≼ є  ⇐⇒ N(P).

N(∅)  = faux 
N(є) = vrai 
N(c) = faux 
N(p1|p2)  =  N(p1) ∨ N(P2) 
N(p1·p2) =  N(p1) ∧ N(P2) 
N(p*)  =  vrai

Bout de preuve.

Planche : 48

Dérivation, p*
c−1·p*  = (c−1·p)·p*

Preuve Par définition :

StarSeq
p ≼ m1           p* ≼ m2
p* ≼ m1m2

Et donc :

p* ≼ c·m  ⇐⇒ ∧⎧
⎪
⎨
⎪
⎩
m = m1·m2
p ≼ c·m1
p* ≼ m2

Conclure par induction (p ≼ c·m1  ⇐⇒ c−1·p ≼ m1).

Planche : 49

Dérivation, p1·p2

La règle :

Seq
p1 ≼ m1           p2 ≼ m2
p1p2 ≼ m1m2

Analysons p1·p2 ≼ c·m. Deux sous-cas:

Planche : 50

Dérivation, récapitulatif
c−1·∅=∅
c−1·є=∅
c−1·c=є
c−1·c′=∅pour c ≠c′
c−1·(p1|p2)=(c−1·p1)|(c−1·p2)
c−1·(p1·p2)=(c−1·p1)·p2si p1 ⊀є
c−1·(p1·p2)=((c−1·p1)·p2)|(c−1·p2)si p1 ≼ є
c−1·p*=(c−1·p)·p*
Ce document a été traduit de LATEX par HEVEA