Cours n° 7, 22 novembre 2012

Jean-François Perrot

Mise en œuvre par programme C++

  1. Principe
    1. Représentation d'un automate en XML
    2. Traduction d'un automate déterministe en C++

  2. Catalogue d'automates
    1. Commentaires en C
    2. L'exemple américain
    3. Interrogation écrite 2010
    4. Ponctuation (interrogation écrite 2011)

  3. Mise en œuvre de la boucle d'analyse
    1. Mise en œuvre minimale : accepter ou refuser une chaîne-candidate
    2. Mise en œuvre plus classique "match":
    3. "matchAll" : Trouver toutes les sous-chaînes maximales...



  1. Principe

    1. Représentation d'un automate en XML

      Exemple1 (fichier Ex1.xml)

      Alphabet : x, y

      Expression régulière : xy*xx*y

      Exemple 1
      <?xml version="1.0" ?>
      <automate>
          <alphabet>
              <lettre nom="x"></lettre>
              <lettre nom="y"/>
          </alphabet>
          <états initial="0">
              <état nom="0"/>
              <état nom="1"/>       
              <état nom="2"/>
              <état nom="3" terminal="oui"/>
          </états>
          <transitions>
              <transition source="0" lettre="x" but="1" />
              <transition source="1" lettre="x" but="2" />
              <transition source="1" lettre="y" but="1" />
              <transition source="2" lettre="x" but="2" />
              <transition source="2" lettre="y" but="3" />
          </transitions>
      </automate>


    2. Traduction d'un automate déterministe en C++

      La table de transitions d'un automate déterministe se traduit directement en C++ (ou dans n'importe quel langage de programmation)
      sous la forme d'un programme
      • qui prend comme argument une chaîne de caractères (en C++, du type string)
      • qui renvoie un message : oui ou non selon que la chaîne est acceptée ou non par l'automate.

      Exemple (automate minimal) : fichier Ex1.cpp 

      Transformation de XML vers programme : à votre service
  2. Catalogue d'automates

    1. Commentaires en C

      fichier Ex2.xml

      Alphabet : x, y, z

      Expression régulière : xy(z|x)*y(y|z(z|x)*y)*x

      Comm C
      <?xml version="1.0" ?>
      <automate>
          <alphabet>
              <lettre nom="x"></lettre>
              <lettre nom="y"/>
              <lettre nom="z"/>
          </alphabet>
          <états initial="0">
              <état nom="0"/>
              <état nom="1"/>        
              <état nom="2"/>
              <état nom="3"/>
              <état nom="4" terminal="oui"/>
          </états>
          <transitions>
              <transition source="0" lettre="x" but="1" />
              <transition source="1" lettre="y" but="2" />
              <transition source="2" lettre="x" but="2" />
              <transition source="2" lettre="y" but="3" />
              <transition source="2" lettre="z" but="2" />
              <transition source="3" lettre="x" but="4" />
              <transition source="3" lettre="y" but="3" />
              <transition source="3" lettre="z" but="2" />
          </transitions>
      </automate>

      Programme : Ex2.cpp
    2. L'exemple américain

      (cours n° 4)

      fichier  Fx1.xml

      Alphabet : a, b

      Expression régulière : (aa | b)*ab(bb)*
      = b*a(ab*a)*b|b*a(ab*a)*bb(bb)*b

      Ex Am
      <?xml version="1.0" ?>
      <automate>
          <alphabet>
              <lettre nom="a"></lettre>
              <lettre nom="b"/>
          </alphabet>
          <états initial="0">
              <état nom="0"/>
              <état nom="1"/>       
              <état nom="2" terminal="oui"/>
              <état nom="3" />
          </états>
          <transitions>
              <transition source="0" lettre="a" but="1" />
              <transition source="0" lettre="b" but="0" />
              <transition source="1" lettre="b" but="2" />
              <transition source="1" lettre="a" but="0" />
              <transition source="2" lettre="b" but="3" />
              <transition source="3" lettre="b" but="2" />       
          </transitions>
      </automate>

      Programme : Fx1.cpp
    3. Interrogation écrite 2010

      fichier

      Alphabet : a, b

      Expression régulière : (a*b)*a
      = (b | ab | aaa*b)*a
      = b*a(b+a)*|b*a(b+a)*a((b+a)*a)*(b+a)+

      Int Ecr 10



    4. Ponctuation (interrogation écrite 2011)

      fichier  Ponct.xml

      Alphabet : a, b

      Expression régulière : ab+s|ad|abb+d|(s|d)(a|bb+a)

      PonctF
      <?xml version="1.0" ?>
      <automate>
          <alphabet>
              <lettre nom="a"/>
              <lettre nom="b"/>
              <lettre nom="d"/>
              <lettre nom="s"/>
          </alphabet>
          <états initial="0">
              <état nom = "0" />
              <état nom = "1" />
              <état nom = "2" />
              <état nom = "3" />
              <état nom = "4" terminal="oui"/>
              <état nom = "5" />
              <état nom = "6" />
              <état nom = "7" />
          </états>
          <transitions>
              <transition source="0" lettre="a" but="2" />
              <transition source="0" lettre="d" but="1" />
              <transition source="0" lettre="s" but="1" />
              <transition source="1" lettre="b" but="3" />
              <transition source="1" lettre="a" but="4" />
              <transition source="2" lettre="b" but="5" />
              <transition source="2" lettre="d" but="4" />
              <transition source="3" lettre="b" but="6" />
              <transition source="5" lettre="b" but="7" />
              <transition source="5" lettre="s" but="4" />
              <transition source="6" lettre="a" but="4" />
              <transition source="6" lettre="b" but="6" />
              <transition source="7" lettre="b" but="7" />
              <transition source="7" lettre="d" but="4" />
              <transition source="7" lettre="s" but="4" />
          </transitions>
      </automate>
      Programme : Ponct.cpp

  3. Mise en œuvre de la boucle d'analyse

    Nous avons vu la manière la plus simple de mettre en œuvre effectivement la boucle traduisant un automtate fini.
    Nous allons à présent examiner deux procédés qui sont en usage courant (nous les retrouverons en Perl).
    Pour cela, il est préférable de séparer le travail de l'automate de la mécanique qui le met en œuvre.
    On modifie donc la transformation XML -> C++ de manière à obtenir une fonction

    Pour simplifier les opérations, nous insèrerons cette fonction dans le fichier contenant la procédure main
    (mais vous pouvez aussi la loger dans un fichier séparé, avec une interface et une commande de compilation adéquate).

    Voici la forme que prend notre premier exemple avec cette manière d'écrire : Ex1f.cpp
    Transformation de XML vers fonction : à votre service

    1. Mise en œuvre minimale : accepter ou refuser une chaîne-candidate

      Même usage que celui que nous avons vu au cours n° 7, mais cette fois-ci, en traitant plusieurs chaînes à la suite,
      sans devoir relancer le programme à chaque fois.
      fichier Ex1B.cpp


      #include <iostream>
      #include <string>
      using namespace std;

      //======================================================================================
      // insérer ici la déclaration de la fonction traduisant l'automate
      //======================================================================================

      int main () {
      cout << "Bonjour ! \nJe suis le programme de reconnaissance \nSortie par CTRL-D \n";
      while(true){
      string mot;
      cout << "Donnez une chaîne\n";
      if (!getline(cin, mot)){
      cout << "Au-revoir !\n";
      break; // sortie de la boucle, fin de l'exécution
      }
      // on a lu une chaîne...

      if( analyser(mot) ){
      cout << "Oui\n";
      }else{
      cout << "Non\n";
      }
      }//while
      return 0;
      }//main


    2. Mise en œuvre plus classique "match":

      trouver une sous-chaîne de la chaîne-candidate qui fait partie du langage
      • la première de gauche à droite
      • et la plus longue possible
      (implémentation "par force brutale", sans souci d'efficacité).

      fichier Ex1M.cpp

      // La première sous-chaîne, la plus longue

      #include <iostream>
      #include <string>
      using namespace std;

      //======================================================================================
      // insérer ici la déclaration de la fonction traduisant l'automate
      //======================================================================================

      int main () {
      cout << "Bonjour ! \nJe suis le programme de 'match'\n";
      string lu;
      cout << "Donnez une chaîne\n";
      getline(cin, lu);

      int k = lu.length();
      int d; // indice de début de la sous-chaîne à tester

      for( d = 0; d < k; d++ ){ // boucle extérieure
      //cout << d << "\n";
      int f; // indice de fin de la sous-chaîne à tester
      for( f = k; f >= d; f-- ){ // boucle intérieure
      string mot = lu.substr(d, f-d);
      //cout << mot << "\n";

      if( analyser(mot) ){
      cout << mot <<"\n";
      break; // sort de la boucle intérieure
      }
      } // for intérieur
      if( f >= d ) break; // on est sorti de la boucle avant la fin,
      // c'est donc qu'on a trouvé, et on sort
      } // for extérieur
      if( d == k ) cout << "no match\n";

      return 0;
      }//main


    3. "matchAll" : Trouver toutes les sous-chaînes maximales...

      fichier Ex1MA.cpp
      à utiliser avec redirection d'un fichier en entrée, par
      %./a.out < try.txt



      // Toutes les plus longues sous-chaînes

      #include <iostream>
      #include <string>
      using namespace std;

      //======================================================================================
      // insérer ici la déclaration de la fonction traduisant l'automate
      //======================================================================================

      int main () {

      string lu;
      getline(cin, lu, '\0'); // censé être un fichier par redirection
      int k = lu.length();

      int d;
      for( d = 0; d< k; d++ ){ // boucle extérieure
      int f;
      for( f = k; f > d; f-- ){ // boucle intérieure
      string mot = lu.substr(d, f-d);


      if( analyser(mot) ){
      cout << mot <<"\n";
      break; // sort de la boucle intérieure
      }
      }// for intérieur
      if( f > d ){
      d = f-1; // et on repart
      /* N.B. c'est "f-1" et non pas "f", car la variable d sera incrémentée par la boucle for
      avant de lancer la prochaine itération ! */
      }

      } // for extérieur

      return 0;
      }