11 avril 2013 : Écriture en C++ d'un analyseur descendant

Jean-François Perrot

1. Projet
2. Étape 0 : le cadre du programme
3. Étape 1 : version simplifiée à un seul type de parenthèses
4. Étape 2 : généralisation aux 4 types de parenthèses
5. Étape 5 : mise en ligne
6. Variantes (16/04/2013)

• la dérivation gauche associée au mot candidat, si ce mot appartient au langage
• une erreur dans le cas contraire.

1. Projet

   Appliquer ce principe à la grammaire non-ambiguë proposée au cours 19 pour les systèmes de parenthèses.
   
   
   1. S -> ε
   2. S -> (S)S 
   3. S -> [S]S 
   4. S -> {S}S 
   5. S -> <S>S

   
   Exemple : le mot <<<>[(())]<{[]}>>>
   est engendré par la dérivation gauche 5551322111543111111
   
   

2. Étape 0 : le cadre du programme

   1. Choix d'une classe pile provenant du cours de M.-A. Moreaux (fichiers pilecar.h et pilecar.cpp).
      
   2. Mise en place d'une commande de compilation (fichier cp.sh).
   3. Rédaction d'un embryon de programme (fichier pp0.cpp).
   4. Essai !
      Correction des premières erreurs (on ne pense jamais à tout...).
   
   

3. Étape 1 : version simplifiée à un seul type de parenthèses

   1. Emploi direct de la pile : déclaration pile p('S');
      
   2. Choix d'une boucle while (true).
   3. Adjonction d'un marqueur final '$' qui fournit le test d'arrêt.
      
      
   Fichier pp1.cpp.
   
   

4. Étape 2 : généralisation aux 4 types de parenthèses

   1. On installe une procédure de service pour empiler les membres droits
      void mpush (pile p, string mbd) {
    int k = mbd.size();
    while( true ){
        if( k == 0 ){
            return;
        }else{
            p.push ( mbd[k-1] );
            k--;
        }
    }
}//mpush
      
      
   2. On constate son inefficacité, on incrimine le passage par valeur de l'argument p.
      On passe donc à une écriture avec pointeur sur pile (à la Java) :
      void mpush (pile* p, string mbd) {
    int k = mbd.size();
    while( true ){
        if( k == 0 ){
            return;
        }else{
            p->push ( mbd[k-1] );
            k--;
        }
    }
}//mpush
      
      et déclaration pile* p = new pile('S');
      
      
   3. On masque l'impression de la dérivation pas-à-pas, et à la place on exhibe la pile par p->show();
      
   
   Fichier pp2.cpp.
   
   

5. Étape 5 : mise en ligne

   1. On veut récupérer la dérivation gauche (qui avait disparu).
      Pour cela on introduit  un accumulateur dg (comme dérivation gauche), que l'on imprime juste avant de sortir.
      
      
   2. GRAVE ! On rectifie la séquence de sortie en contrôlant que la pile est vide (ce qui avait été négligé en cours)
      pour ne pas accepter des mots du genre "((((((..."
                      case '$' : {
                    dg += "1";
                    p->pop();
                    p->show();
                    if( p->empty() ){ // succès
                        cout << dg << endl; // avant de sortir !
                        return 0;
                    }else{
                        cout << "erreur pile non vide" << endl;
                        return 3;
                    }
                }   


   3. On remanie l'écriture du switch afin de ne pas répéter la même séquence de code pour chaque fermante.
      
      
   Fichier pp.cpp.
   
   

6. Variantes (16/04/2013)

   
   
   1. La procédure mpush avec un argument passé par référence
      void mpush (pile& p, string mbd) {
    int k = mbd.size();
    while( true ){
        if( k == 0 ){
            return;
        }else{
            p.push ( mbd[k-1] );
            k--;
        }
    }
}//mpush
      
      en fonctionnement dans le programme pp1R.cpp (un seul type de parenthèses).
      
      
   2. En dire plus quand il manque des fermantes : combien ?
      
      Exemple :
      jfp$ ./pp
Donnez un mot candidat
((((()()
222221211
erreur pile non vide, il manque 4 fermantes
) S ) S ) S ) S
jfp$
      
      grâce à une fonction auxiliaire dont l'argument est passé par valeur :
      
      int nbFerm(pile p){// appelée sur pile NON VIDE
    int k = 0;
    while( true ){
        char t = p.top();
        if( fermante(t) ){
            k++;
        }
        p.pop();
        if( p.empty() ){
            return k;
        }
    }
}//nbFerm
      
      en fonctionnement dans le programme pp1R.cpp (un seul type de parenthèses).
      
      
   3. Généralisation aux quatre types de parenthèses
      Compter ne suffit plus !
      Il faut extraire de la pile un complément minimal qui ferme toutes des ouvrantes dans le bon ordre.
      Exemple :
      jfp$ ./pp
Donnez un mot candidat
(([[]{{<<>(([[]{{<<>
erreur pile non vide
voici comment compléter votre candidat : >}}]))>}}]))
jfp$ ./pp
Donnez un mot candidat
(([[]{{<<>(([[]{{<<>>}}]))>}}]))
223314455122331445511111111111111
jfp$
      
      grâce à une fonction auxiliaire :
      
      string contPile(pile* p){// appelée sur pile NON VIDE
    string k = "";
    while( true ){
        char t = p->top();
        if( fermante(t) ){
            k = k+t;
        }
        p->pop();
        if( p->empty() ){
            return k;
        }
    }
}//contPile
      
      en fonctionnement dans le programme ppE.cpp.
      
      Question : si, dans ce dernier programme, on veut imiter le programme prédédent pp1R.cpp
      en demandant "p->show();" après le calcul du complément, que va-t-on obtenir ?