Attributs, examen de compilation, janvier 1997
Sujet
Soit G la grammaire des listes suivante :
S -> (L) | id
L -> L,S | S
Soit par exemple la liste u = (a, (b,c), a) ;
a (de même que b ou c) est un atome de u,
et (b,c) (de même que a) un composant de u.
Ecrire un programme,
dans le format reconnu par yacc,
qui calcule (et affiche) simultanément :
-
le nombre d'atomes (distincts ou non) d'une liste
(dans le cas de u, le résultat est 4) ;
-
le nombre de composants (distincts ou non) d'une liste
(dans le cas de u, le résultat est 3) ;
-
la profondeur d'emboîtement d'une liste
(dans le cas de u, le résultat est 2).
Corrigé
%{
struct attribut {
int atome, composant, profondeur;
};
#define YYSTYPE struct attribut
void afficher (struct attribut a);
%}
%token id
%%
axiome : S '\n' { afficher($1); }
;
S : '(' L ')' { $$ = $2; $$.profondeur++; }
| id { $$.atome = 1;
$$.composant = 1;
$$.profondeur = 0;
}
;
L : L ',' S { $$.atome = $1.atome + $3.atome;
$$.composant = $1.composant + 1;
$$.profondeur = max ($1.profondeur, $3.profondeur);
}
| S { $$.composant = 1; }
;
%%
void afficher (struct attribut a) {
printf ("%d atome(s), %d composant(s), profondeur %d\n",
a.atome, a.composant, a.profondeur);
}
Note : pour que ce programme soit réellement exécutable, il faut bien entendu
définir aussi la fonction (ou la macro) max, et un analyseur lexical.