Cours n° 21, 5 avril 2012
Analyseurs descendants en C++
- Une
pile de caractères
- L'interface
de la classe pile
(fichier pile.h)
- Son
implémentation (fichier pile.cpp)
- Un
programme d'essai
- Un
parseur pour les expressions arithmétiques en notation
complètement parenthésée.
- La
grammaire
- Un
parseur qui effectue exactement les actions prévues
par la
théorie
- Variante
allégée
- Construction
effective de l'arbre d'expression.
- Un
parseur descendant léger pour les expressions
arithmétiques en notation polonaise préfixée
- Le
parseur, sur le modèle précédent
- Transformation
du parseur en traducteur
- Exercices
:
But : réalisations minimales destinées à montrer précisément les
mécanismes en jeu.
La pile est représentée et gérée explicitement : on a renoncé à la
descente récursive,
trop puissante et où les mécanismes élémentaires sont occultés.
-
class pile {
private :
char
locpile[10] ; // le tableau contenant la pile
int
sompile ; // indice du sommet de pile dans le tableau
public
:
pile() ;
// le constructeur par défaut doit être public
pile(char);
void push
(char);
char top
();
void pop
();
bool
empty ();
void
show(); // montrer le contenu de la pile
} ;
-
sans aucun mystère !
Mais notez bien que l'utilisateur de la classe n'est pas censé connaître son implémentation...
Le fichier d'interface assorti que quelques commentaires sur le comportement attendu des instances
doit suffire.
#include "pile.h"
#include <iostream>
using namespace std;
pile::pile () {
sompile = 0;
};
pile::pile(char x) {
sompile = 1;
locpile[1] = x;
};
void
pile::push (char n) {
locpile[++sompile] = n;
};
char
pile::top () {
return locpile[sompile];
};
void
pile::pop () {
sompile--;
};
bool
pile::empty () {
return (sompile == 0);
};
void
pile::show () {
int i;
for( i = sompile; i>0; i-- ){
cout
<< locpile[i] << " ";
}
cout << endl;
}
-
pour vérifier le bon fonctionnement de notre instrument (fichier
pilex.cpp)
Version 2012 écrite avec une boucle while.
#include
<iostream>
using namespace std;
#include "pile.h"
int main() {
pile* p = new pile('S') ;
int k;
char v;
for (cin >> k ; 0 <= k ; k--) {
cin >> v;
p->push(v);
}
p->show();
while ( !p->empty() ) {
cout << p->top();
p->pop();
}
cout << endl;
return 0;
}
Compilation : jfp% g++ pile.h
pile.cpp pilex.cpp
Exécution :
jfp% ./a.out
3
u
v
w
x
x w v u S
xwvuS
jfp%
-
Pour faire fonctionner l'analyse descendante
de manière déterministe,
il est impératif d'écrire la grammaire avec deux non-terminaux S
et O (comme "Opérateur")
afin d'avoir une seule règle dont le membre droit commence par la
parenthèse ouvrante.
S -> (S O S) S -> v S-> i O -> + O -> *
Les actions prévues par la théorie générale sont :
- On commence avec l'axiome seul dans la pile.
- Tant que la pile n'est pas vide et qu'il y a des
caractères
à lire sur le mot d'entrée :
- Si le sommet de la pile porte un non-terminal
X,
on le remplace par le membre droit w d'une
des règles dont il est le membre gauche : X -> w.
Attention ! ledit membre droite doit être écrit "à l'envers",
de manière à ce que son initiale se retrouve au sommet de la pile.
- Si le sommet de la pile porte une lettre
terminal
a,
alors cette lettre doit être identique au prochain caractère à lire sur
le mot d'entrée.
Si tel est le cas, on supprime a du
sommet de la pile et on avance dans la lecture ;
sinon l'analyse échoue : la dérivation en cours n'est pas la bonne, il
faut en cherhcer une autre (non-déterminisme)
et si elle était la seule possible (parseur déterministe) alors le mot
d'entrée est incorrect : Syntax error !
- On doit arriver à la fin du mot d'entrée avec une pile
vide.
Si la pile se vide avant la fin, et si elle n'est pas vide à la fin de
la lecture, l'analyse échoue (cf. ci-dessus).
Avec cette grammaire, la connaissance du prochain caractère à lire
détermine de manière univoque
le choix de la seule règle qui a une chance de succès, il n'y a plus
qu'à l'écrire !
-
fichier
dcp1.cpp
#include "pile.h"
#include <iostream>
using namespace std;
int main(void) {
string lu;
getline(cin, lu);
pile* p = new pile('S');
int k = lu.length();
int i = 0;
while( i < k ){
char
carlu = lu[i];
// La
pile ne doit jamais se vider avant la fin de la lecture du mot
if(
p->empty() ){
cout << "Erreur : trop
long";
return 1;
}
//
Visualiser le processus
cout
<< carlu << " -- ";
p->show();
char sp =
p->top();
switch(
sp ){ // décision en fonction du non-terminal en sommet de pile
case 'S' : {
switch
(carlu) {
case '(' : { p->pop(); //
attention à l'ordre des push !!!
p->push(')');
p->push('S');
p->push('O');
p->push('S');
p->push('(');
break;
}
case 'x' :
case 'y' :
case 'z' :
case '1' :
case '2' :
case '3' : { p->pop();
p->push(carlu);
break;
}
default : { cout <<
"Erreur sur S : " << carlu << endl;
return 1;
}
} //
switch carlu pour 'S' en sommet de pile
break;
} // case 'S'
case'O' : {
switch (carlu) {
case '+' :
case '*' : { p->pop();
p->push(carlu);
break;
}
default : { cout <<
"Erreur sur O : " << carlu << endl;
return 1;
}
}//
switch carlu pour 'O' en sommet de pile
break;
} // case 'O'
// Cas des symboles terminaux :
confrontation avec sp
case '+' :
case '*' :
case 'x' :
case 'y' :
case 'z' :
case '1' :
case '2' :
case '3' :
case '(' :
case ')' : {
if( carlu == sp ){
p->pop();
i++;
//------------------------ avance de la lecture
}else{
cout << "Erreur sur : sp vs. " << carlu
<< endl;
return 1;
}
break;
} // case ')'
default :
{ cout << "Erreur
symbole inconnu : " << sp << endl;
return 1;
}
} //
switch( p->top() )
}// while
// À la fin de la lecture la pile doit
être vide
if( !p->empty() ){
cout
<< "Erreur : pas fini"<< endl;
return 1;
}else{
cout
<< "OK" << endl;
return 0;
}
}// main
Exécution :
jfp% ./a.out
((x+(y*(z+2)))*(y+3))
( -- S
( -- ( S O S )
( -- S O S )
( -- ( S O S ) O S )
x -- S O S ) O S )
x -- x O S ) O S )
+ -- O S ) O S )
+ -- + S ) O S )
( -- S ) O S )
( -- ( S O S ) ) O S )
y -- S O S ) ) O S )
y -- y O S ) ) O S )
* -- O S ) ) O S )
* -- * S ) ) O S )
( -- S ) ) O S )
( -- ( S O S ) ) ) O S )
z -- S O S ) ) ) O S )
z -- z O S ) ) ) O S )
+ -- O S ) ) ) O S )
+ -- + S ) ) ) O S )
2 -- S ) ) ) O S )
2 -- 2 ) ) ) O S )
) -- ) ) ) O S )
) -- ) ) O S )
) -- ) O S )
* -- O S )
* -- * S )
( -- S )
( -- ( S O S ) )
y -- S O S ) )
y -- y O S ) )
+ -- O S ) )
+ -- + S ) )
3 -- S ) )
3 -- 3 ) )
) -- ) )
) -- )
OK
jfp%
-
Comme les actions du parseur sont déclenchées au vu des
lettres lues dans le mot d'entrée,
et qu'elles donnent lieu à une séquence invariable :
- suppression du non-terminal sur la pile (pop)
- empilement du membre droit, dont on sait qu'il commence
par
la lettre lue
- constatation que la lettre lue se trouve bien en sommet
de
pile
- suppression de la lettre lue en sommet de pile et
avancée
dans la lecture du mot d'entrée.
on peut anticiper la constatation, ne pas empiler la première lettre du
membre droit (qui va être illico supprimée)
et avancer systématiquement dans la boucle de lecture.
Ladite boucle de lecture peut alors s'écrire comme une boucle for
(ce
qui est toujours préférable) :
fichier dcp2.cpp
Version 2012 écrite avec une boucle while.
for( i = 0; i< k;
i++
){
char
carlu = lu[i];
// La
pile ne doit jamais se vider avant la fin de la lecture du mot
if(
p->empty() ){
cout << "Erreur : trop
long";
return 1;
}
//
Visualiser le processus
cout
<< carlu << " -- ";
p->show();
char
sp =
p->top();
switch(
sp ){
case 'S' : {
switch
(carlu) {
case '(' : { p->pop(); //
attention à l'ordre des push !!!
p->push(')');
p->push('S');
p->push('O');
p->push('S');
break;
}
case 'x' :
case 'y' :
case 'z' :
case '1' :
case '2' :
case '3' : { p->pop();
break;
}
default : { cout <<
"Erreur sur S : " << carlu << endl;
return 1;
}
} //
switch carlu pour 'S' en sommet de pile
break;
} // case 'S'
case'O' : {
switch (carlu) {
case '+' :
case '*' : { p->pop();
break;
}
default : { cout <<
"Erreur sur O : " << carlu << endl;
return 1;
}
}//
switch carlu pour 'O' en sommet de pile
break;
} // case 'O'
case ')' : {
if( carlu == ')' ){
p->pop();
}else{
cout << "Erreur sur : ')' " << carlu
<< endl;
return 1;
}
break;
} // case ')'
default :
{ cout << "Erreur
symbole inconnu : " << sp << endl;
return 1;
}
} //
switch( p->top() )
}// for
Exécution :
jfp% ./a.out
((x+(y*(z+2)))*(y+3))
( -- S
( -- S O S )
x -- S O S ) O S )
+ -- O S ) O S )
( -- S ) O S )
y -- S O S ) ) O S )
* -- O S ) ) O S )
( -- S ) ) O S )
z -- S O S ) ) ) O S )
+ -- O S ) ) ) O S )
2 -- S ) ) ) O S )
) -- ) ) ) O S )
) -- ) ) O S )
) -- ) O S )
* -- O S )
( -- S )
y -- S O S ) )
+ -- O S ) )
3 -- S ) )
) -- ) )
) -- )
OK
jfp%
-
Elle demande des ressources programmatiques supplémentaires, à savoir
une classe
ArbExp (fichiers ArbExp.h
et ArbExp.cpp)
et une seconde pile propre à contenir des arbres (et non plus des
caractères
comme notre pile actuelle),
qui nous est fournie par la classe pilArb
(fichiers pilArb.h
et pilArb.cpp).
La classe ArbExp dispose d'un constructeur sans
argument ArbExp()
qui crée un (pointeur sur un) arbre vide,
et de procédures de "greffe" permettant de "remplir" progressivement
cet arbre
en lui ajoutant un opérateur (caractère) et deux sous-arbres gauche et
droit.
C'est la pile de caractères qui pilote le processus, la pile
des arbres lui étant asservie
(de sorte que conceptuellement on a bien affaire à une seule pile).
Voici la chose en acte :
fichier dcp2Arb.cpp
#include "../pile.h"
#include "../pilArb.h"
#include "../ArbExp.h"
#include <iostream>
using namespace std;
int main(void) {
string lu;
getline(cin, lu);
pile* p = new pile('S');
ArbExp* init = new ArbExp();
pilArb* pA = new pilArb(init);
int k = lu.length();
int i;
for( i = 0; i< k; i++ ){
char
carlu = lu[i];
// La
pile ne doit jamais se vider avant la fin de la lecture du mot
if(
p->empty() ){
cout << "Erreur : trop
long" << endl;
return 1;
}
//
Visualiser le processus
cout
<< carlu << " -- ";
p->show();
char sp
= p->top();
switch( sp
){
case 'S' : {
switch
(carlu) {
case '(' : { ArbExp* tp =
pA->top();
ArbExp* opg = new ArbExp();
ArbExp* opd = new ArbExp();
tp->donner_fg(opg);
tp->donner_fd(opd);
pA->pop();
pA->push(opd); // attention à l'ordre !!!
pA->push(tp); // en attente d'opérateur
pA->push(opg);
p->pop(); // attention à l'ordre des push !!!
p->push(')');
p->push('S');
p->push('O');
p->push('S');
break;
}
case 'x' :
case 'y' :
case 'z' :
case '1' :
case '2' :
case '3' : { ArbExp* tp =
pA->top();
tp->donner_etiq(carlu);
pA->pop();
p->pop();
break;
}
default : { cout <<
"Erreur sur S : " << carlu << endl;
return 1;
}
} //
switch carlu pour 'S' en sommet de pile
break;
} // case 'S'
case'O' : {
switch (carlu) {
case '+' :
case '*' : { ArbExp* tp =
pA->top();
tp->donner_etiq(carlu);
pA->pop();
p->pop();
break;
}
default : { cout <<
"Erreur sur O : " << carlu << endl;
return 1;
}
}//
switch carlu pour 'O' en sommet de pile
break;
} // case 'O'
case ')' : {
if( carlu == ')' ){
p->pop();
}else{
cout << "Erreur sur : ')' " << carlu
<< endl;
return 1;
}
break;
} // case ')'
default : { cout <<
"Erreur symbole inconnu : " << sp << endl;
return 1;
}
} //
switch( p->top() )
}// for
// À la fin de la lecture la pile doit
être vide
if( !p->empty() ){
cout
<< "Erreur : pas fini"<< endl;
return 1;
}else{
init->printPref();
cout
<< endl;
init->printPost();
cout << endl << "OK" << endl;
return 0;
}
}// main
Exécution
jfp% ./a.out
((x+y)*((x+(y*(z+2)))*(y+3)))
( -- S
( -- S O S )
x -- S O S ) O S )
+ -- O S ) O S )
y -- S ) O S )
) -- ) O S )
* -- O S )
( -- S )
( -- S O S ) )
x -- S O S ) O S ) )
+ -- O S ) O S ) )
( -- S ) O S ) )
y -- S O S ) ) O S ) )
* -- O S ) ) O S ) )
( -- S ) ) O S ) )
z -- S O S ) ) ) O S ) )
+ -- O S ) ) ) O S ) )
2 -- S ) ) ) O S ) )
) -- ) ) ) O S ) )
) -- ) ) O S ) )
) -- ) O S ) )
* -- O S ) )
( -- S ) )
y -- S O S ) ) )
+ -- O S ) ) )
3 -- S ) ) )
) -- ) ) )
) -- ) )
) -- )
*+xy*+x*y+z2+y3
xy+xyz2+*+y3+**
OK
-
fichier
dpref.cpp
#include "pile.h"
#include <iostream>
using namespace std;
int main(void) {
string lu;
getline(cin, lu);
pile* p = new pile('S');
int k = lu.length();
int i;
for( i = 0; i< k; i++ ){
char
carlu = lu[i];
if(
p->empty() ){
cout << "Erreur : trop
long" << endl;
return 1;
}
//
Visualiser le processus
cout
<< carlu << " -- ";
p->show();
switch
(carlu) {
case '+' :
case '*' : { p->push('S');// pour
p->pop(); p->push('S'); p->push('S');
break;
}
case 'x' :
case 'y' :
case 'z' :
case '1' :
case '2' :
case '3' : { p->pop();
break;
}
default : { cout <<
"Erreur : " << carlu << endl;
return 1;
}
}// switch
}// for
if( !p->empty() ){
cout
<< "Erreur : pas fini" << endl;
return 1;
}else{
cout << "OK" << endl;
return 0;
}
}// main
Exécution
jfp% ./a.out
*+x*y+z2+y3
* -- S
+ -- S S
x -- S S S
* -- S S
y -- S S S
+ -- S S
z -- S S S
2 -- S S
+ -- S
y -- S S
3 -- S
OK
jfp%
-
En modifiant la gestion de la pile, on peut utiliser les processus
d'analyse pour traduire
de la polonaise préfixée vers la notation complètement parenthésée.
L'inverse vous semble-t-il possible ?
On ajoute une variable string res qui
contiendra la chaîne-traduction à
la fin de la boucle.
Le corps de la boucle devient (fichier tradpref.cpp)
:
switch
(carlu) {
case '+' :
case '*' : { p->pop();
p->push(')');
p->push('S');
p->push(carlu);
p->push('S');
res += '('; // Tout opérateur suppose une parenthèse
break;
}
case 'x' :
case 'y' :
case 'z' :
case '1' :
case '2' :
case '3' : { p->pop();
res += carlu; // Variables et constantes ne changent pas de
place
break;
}
default : { cout <<
"Erreur : " << carlu << endl;
return 1;
}
}// switch
while(
!p->empty() && p->top() != 'S' ){
res += p->top(); // Les souvenirs
enfouis dans la pile reparaissent à la surface
p->pop();
}
Exécution :
jfp% ./a.out
*+x*y+z2+y3
* -- S
+ -- S * S )
x -- S + S ) * S )
* -- S ) * S )
y -- S * S ) ) * S )
+ -- S ) ) * S )
z -- S + S ) ) ) * S )
2 -- S ) ) ) * S )
+ -- S )
y -- S + S ) )
3 -- S ) )
OK
((x+(y*(z+2)))*(y+3))
jfp%
-
- Sur le même modèle, réalisez un traducteur de la polonaise
préfixée
vers la postfixée.
- La construction de l'arbre pour la notation polonaise
préfixée vous est
également proposée en exercice.