Cours n° 9, 6 décembre 2011

Jean-François Perrot

Mise en œuvre par programme 1

1. Principe
   1. Traduction d'un automate déterministe en C++
   2. Mise en œuvre
   3. Compilation
      
      
2. Catalogue d'automates
   1. Commentaires en C
   2. L'exemple américain
   3. Interrogation écrite 2010
   4. Ponctuation (interrogation écrite 2011)

Principe

1. 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'une fonction
   
   • qui prend comme argument une chaîne de caractères (en C++, du type string)
     
   • qui renvoie une valeur booléenne : vrai ou faux selon que la chaîne est acceptée ou non par l'automate.
     
   
   Exemple (automate minimal) : fichier Exemple1.cpp 
   
   

   Alphabet : x, y Expression régulière : xy*xx*y

   #include "../auto.h" bool analyser( string aAnalyser , int & i){    int etat;    etat = 0;    --i ;    while(true){      ++i;      if(i==aAnalyser.length())return (etat==3);      switch(etat){       case 0:           if(aAnalyser[i]=='x') {etat = 1;break;}           return false;       case 1:           if(aAnalyser[i]=='x') {etat = 2;break;}           if(aAnalyser[i]=='y') {etat = 1;break;}           return false;       case 2:           if(aAnalyser[i]=='x') {etat = 2;break;}           if(aAnalyser[i]=='y') {etat = 3;break;}           return false;       case 3:           return false;      }    } }

   
   Cette traduction peut se faire à la main, mais elle est tout-à-fait à la portée d'un ordinateur !
   L'exemple ci-dessus a été obtenu au moyen du logiciel automate.
   
   

2. Mise en œuvre

   La fonction en question doit être appelée depuis un programme-cadre qui lui assigne un rôle dans un projet plus vaste.
   Nous en verrons divers exemples plus tard.
   
   Le plus simple est celui qui lit une chaîne et renvoie la réponse de l'automate pour cette même chaîne.
   Fichier accept_sg.cpp
   

   ---

   #include "../automates/auto.h"
#include <iostream>
#include <string>
using namespace std;

int main () {
    string lu;
    cout << "Bonjour ! \nJe suis le programme de reconnaissance.\nDonnez une chaîne :\n";

    getline(cin, lu);
       
    int start = 0;
    if( analyser(lu, start) ){
        cout << "Oui\n";
    }else{
        cout << "Non\n";
    }

    return 0;
}
   

   ---

   
   

3. Compilation

   Pour être exécuté, le couple (programme, fonction) doit être compilé par une commande de la forme
   
   g++ -o executable programme.cpp interface.h fonction.cpp

En l'occurrence, l'interface est le fichier auto.h
   

   ---

   #include <string>
using namespace std;

bool analyser(  string aAnalyser, int & );
   

   ---

   
   Exemple de commande exécutable depuis le répertoire qui contient le fichier Exemple1.cpp
(de préférence, à réaliser sous forme de shell-script) :
   
   g++ -o Exemple1_accept_sg ../../cadres/accept_sg.cpp ../auto.h Exemple1.cpp


   

Catalogue d'automates

1. Commentaires en C

   fichier CommC.cpp
   

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

   #include "../auto.h" bool analyser( string aAnalyser , int & i){    int etat;    etat = 0;    --i ;    while(true){      ++i;      if(i==aAnalyser.length())return (etat==4);      switch(etat){       case 0:           if(aAnalyser[i]=='x') {etat = 1;break;}           return false;       case 1:           if(aAnalyser[i]=='y') {etat = 2;break;}           return false;       case 2:           if(aAnalyser[i]=='x') {etat = 2;break;}           if(aAnalyser[i]=='y') {etat = 3;break;}           if(aAnalyser[i]=='z') {etat = 2;break;}           return false;       case 3:           if(aAnalyser[i]=='x') {etat = 4;break;}           if(aAnalyser[i]=='y') {etat = 3;break;}           if(aAnalyser[i]=='z') {etat = 2;break;}           return false;       case 4:           return false;      }    } }

   
   g++ -o CommC_accept_sg ../../cadres/accept_sg.cpp ../auto.h CommC.cpp
   
   

2. L'exemple américain

   (cours n° 4)
   
   fichier ExAmericain.cpp
   

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

   #include "../auto.h" bool analyser( string aAnalyser , int & i){    int etat;    etat = 0;    --i ;    while(true){      ++i;      if(i==aAnalyser.length())return (etat==2);      switch(etat){       case 0:           if(aAnalyser[i]=='a') {etat = 1;break;}           if(aAnalyser[i]=='b') {etat = 0;break;}           return false;       case 1:           if(aAnalyser[i]=='a') {etat = 0;break;}           if(aAnalyser[i]=='b') {etat = 2;break;}           return false;       case 2:           if(aAnalyser[i]=='b') {etat = 3;break;}           return false;       case 3:           if(aAnalyser[i]=='b') {etat = 2;break;}           return false;      }    } }

   
   g++ -o ExAmericain_accept_sg ../../cadres/accept_sg.cpp ../auto.h ExAmericain.cpp

   

3. Interrogation écrite 2010

   fichier IntEcr10.cpp
   

   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)+

   #include "../auto.h" bool analyser( string aAnalyser , int & i){    int etat;    etat = 0;    --i ;    while(true){      ++i;      if(i==aAnalyser.length())return (etat==1);      switch(etat){       case 0:           if(aAnalyser[i]=='a') {etat = 1;break;}           if(aAnalyser[i]=='b') {etat = 0;break;}           return false;       case 1:           if(aAnalyser[i]=='a') {etat = 2;break;}           if(aAnalyser[i]=='b') {etat = 0;break;}           return false;       case 2:           if(aAnalyser[i]=='a') {etat = 2;break;}           if(aAnalyser[i]=='b') {etat = 0;break;}           return false;      }    } }

   
   g++ -o IntEcr10_accept_sg ../../cadres/accept_sg.cpp ../auto.h IntEcr10.cpp
   
   

4. Ponctuation (interrogation écrite 2011)

   fichier PoncF.cpp
   

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

   #include "../auto.h" bool analyser( string aAnalyser , int & i){    int etat;    etat = 0;    --i ;    while(true){      ++i;      if(i==aAnalyser.length())return (etat==4);      switch(etat){       case 0:           if(aAnalyser[i]=='a') {etat = 2;break;}           if(aAnalyser[i]=='d') {etat = 1;break;}           if(aAnalyser[i]=='s') {etat = 1;break;}           return false;       case 1:           if(aAnalyser[i]=='a') {etat = 4;break;}           if(aAnalyser[i]=='b') {etat = 3;break;}           return false;       case 2:           if(aAnalyser[i]=='b') {etat = 5;break;}           if(aAnalyser[i]=='d') {etat = 4;break;}           return false;       case 3:           if(aAnalyser[i]=='b') {etat = 6;break;}           return false;       case 4:           return false;       case 5:           if(aAnalyser[i]=='b') {etat = 7;break;}           if(aAnalyser[i]=='s') {etat = 4;break;}           return false;       case 6:           if(aAnalyser[i]=='a') {etat = 4;break;}           if(aAnalyser[i]=='b') {etat = 6;break;}           return false;       case 7:           if(aAnalyser[i]=='b') {etat = 7;break;}           if(aAnalyser[i]=='d') {etat = 4;break;}           if(aAnalyser[i]=='s') {etat = 4;break;}           return false;      }    } }

   
   g++ -o PonctF_accept_sg ../../cadres/accept_sg.cpp ../auto.h PonctF.cpp