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 = a0a1an−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)

((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é pm.

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 p1p2 ;

  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(pstar(p)) ;
}

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

Planche : 30


Le motif i.*.*i
static Re buildAtLeast(int kchar 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 pBufferedReader in)
  throws IOException {
    Re pat = Re.parse(p) ; // ▷ 431
    String line = in.readLine() ;
    while (line != null) {
      if (submatches(patline)) {
        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 patString textint iint j)

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

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

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

Planche : 34


Filtrage, cas faciles
// Test  de pat ≼ text[i…j[
static boolean matches(String textRe patint iint 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(textpat.p1ij) ||
        matches(textpat.p2ij) ;

Planche : 36


La séquence

Essayer la règle

Seq
p1 ≼ m1           p2 ≼ m2
p1p2 ≼ m1m2

Pour toutes les divisions m1 = t[ik[, m2 = t[kj[.

    case SEQ:
      for (int k = i ; k <= j ; k++) {
        if (matches(textpat.p1ik) &&
            matches(textpat.p2kj))
          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(textpat.p1ik) &&
              matches(textpatkj))
            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 subString 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 patString 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(pattextij))
        return text.substring(i,j) ;
  return null ;
}

Code pour le plus à gauche–le plus long.

static String submatches(Re patString 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(pattextij))
         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 cc
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 (pc·m1  ⇐⇒ c−1·pm1).


Planche : 49


Dérivation, p1·p2

La règle :

Seq
p1 ≼ m1           p2 ≼ m2
p1p2 ≼ m1m2

Analysons p1·p2c·m. Deux sous-cas:


Planche : 50


Dérivation, récapitulatif
c−1·=
c−1·є=
c−1·c=є
c−1·c=pour cc
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