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 :
  1. le nombre d'atomes (distincts ou non) d'une liste (dans le cas de u, le résultat est 4) ;
  2. le nombre de composants (distincts ou non) d'une liste (dans le cas de u, le résultat est 3) ;
  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.