11 avril 2013 : Écriture en C++ d'un analyseur descendant
- Projet
- Étape 0 : le cadre du programme
- Étape 1 : version simplifiée à un seul
type de parenthèses
- Étape 2 : généralisation aux 4 types de
parenthèses
- Étape 5 : mise en ligne
- Variantes (16/04/2013)
On explicite le discours tenu au cours précédent sur le
principe de
l'analyse descendante,
sous la forme d'un programme C++ qui produit
- la dérivation gauche associée au mot candidat, si ce mot
appartient au langage
- une erreur dans le cas contraire.
-
Appliquer ce principe à la grammaire non-ambiguë proposée au cours 19
pour les systèmes de parenthèses.
S -> ε
S -> (S)S
S -> [S]S
S -> {S}S
S -> <S>S
Exemple : le mot <<<>[(())]<{[]}>>>
est engendré par la dérivation gauche 5551322111543111111
-
- Choix d'une classe
pile
provenant du cours de
M.-A. Moreaux
(fichiers pilecar.h
et pilecar.cpp
).
- Mise en place d'une commande de compilation (fichier
cp.sh
).
- Rédaction d'un embryon de programme (fichier
pp0.cpp
).
- Essai !
Correction des premières erreurs (on ne pense jamais à tout...).
-
- Emploi direct de la pile : déclaration
pile p('S');
- Choix d'une boucle
while (true).
- Adjonction d'un marqueur final '
$
' qui fournit
le test d'arrêt.
Fichier pp1.cpp
.
-
- 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
- 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');
- On masque l'impression de la dérivation pas-à-pas, et à la
place on exhibe la pile par
p->show();
Fichier pp2.cpp
.
-
- 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.
- 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;
}
}
- 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
.
-
- 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).
- 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).
- 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 ?