Informatique pour les sciences humaines

Deuxième année (BA3a)

Tp4 : Piles

Date de reddition le 13 décembre 2005 à 9h

Les piles ont la propriété que le dernier élément inséré est le premier à pouvoir en être extrait. On appelle cet élément le sommet de la pile. La pile obéit au protocole LIFO (Last In First Out). Elle est utilisée en informatique pour :

- la réalisation de fonction "Undo"

- analyse des expressions par un compilateur

- Allocation de la mémoire pour les variables locales lors de l'exécution des procédures

Représentation et implémentation

Il y a plusieurs façons de représenter une pile. Entre autres types de représentation, il y a les représentations séquentielles (par tableaux) et les représentations chaînées (par pointeurs). Nous choisissons de faire une représentation chaînée (dynamique) vu que nous ne connaissons pas la taille des données.

Spécification

Type

Liste = POINTER TO RECORD

elem : CHAR

next : Liste

END ;

Pile = RECORD

Element : Liste

END

Procédures liées

Constrcuteurs/Modifieurs de pile

Clear*() , procédure d'initialisation de la pile. Elle met la pile passée en paramètre à vide.

Push*(e: CHAR), procédure d'empilement d'un élément en sommet de pile.

Pop* (OUT e: CHAR):BOOLEAN, procédure de dépilement de l’élément en sommet de pile.

Sélecteurs de pile

Sommet(): e, retourne l'élément en sommet de pile

IsEmpty (): BOOLEAN, retourne vrai si la pile est vide, faux autrement

NumItem():INTEGER; retourne la profondeur de la pile, la profondeur correspond aux nombre d'éléments que contient la pile.

 
Interface des modules « Info2Tp4» et « Info2ClientTp4»
 

DEFINITION Info2Tp4;

TYPE

Pile = RECORD

(VAR p: Pile) Clear, NEW;

(VAR p: Pile) IsEmpty (): BOOLEAN, NEW;

(IN p: Pile) NumItem (): INTEGER, NEW;

(VAR p: Pile) Pop (OUT e: CHAR), NEW; (* Pré-condition : ~p.IsEmpty() *)

(VAR p: Pile) Push (e: CHAR), NEW;

(IN p: Pile) Sommet (OUT e: CHAR), NEW (* Pré-condition : ~p.IsEmpty() *)

END;

END Info2Tp4.
 

DEFINITION Info2ClientTp4;

(*Les symboles à considerer *)

CONST

symb1Fermant = "}";

symb1Ouvrant = "{";

symb2Fermant = "]";

symb2Ouvrant = "[";

symb3Fermant = ")";

symb3Ouvrant = "(";

VAR

d: RECORD

text: ARRAY 1200 OF CHAR;

result-: ARRAY 32 OF CHAR (*résulta de l’analyse *)

END;

PROCEDURE ParseFile; (*analyse un fichier texte*)

PROCEDURE ParseText; (*analyse la chaîne d.text Pré-Condition : d.text # «» *)

END Info2ClientTp4.
 
Enoncé 

Faire un programme d'analyse syntaxique qui permet de détecter et vérifier les paires de symboles ouvrant/fermant tels que parenthèses, accolades etc. Le programme doit détecter les paires suivantes : [], {} et ().

Exemple :

 LEN[d] : correct
 Set :={1,2,8} : correct
 Chaîne:= « {e[b}] » : incorrect 
 
Ce type de problème peut facilement être résolu grâce à l’utilisation d’une pile. 
 
Pour ce faire :
Il s’agit de lire le texte d’entrée caractère par caractère et de considérer les cas de figures suivants : 
1. si on trouve un symbole ouvrant, on l’empile, 
2. si on trouve un symbole fermant et que l’élément en sommet de pile est un symbole ouvrant de même type, on dépile
3. si on trouve un symbole fermant et que l’élément en sommet de pile est un symbole ouvrant de type différent alors c’est mal formé
4. si on atteint la fin du fichier et que la pile n’est pas vide alors c’est mal formé
5. si on atteint la fin du fichier et que la pile est vide alors c’est bien formé
 
A rendre en fichier encodé à l’adresse : mar.ndiaye@lettres.unige.ch
 - le module « fournisseur »
 - le module « client »
 - la documentation
 - la boite de dialogue