CC21 - 2004/5 - TP Noté

Sujet 'AA' : ARBRES ET AUTOMATES

Avec la question 1, on reconnait une description d'arbre et on construit sa structure, que l'on peut lister
a la fin, sur des arbres elementaires. En question 2, on fait de meme avec une representation simplifiee
de fichiers XML. La question 3 est independante des questions 1 et 2 ; elle propose d'implementer
un principe d'automate en utilisant les pointeurs de fonction C. La question 4 cherche a utiliser les
resultats des questions 2 et 3. Le bareme est indicatif.

1 - RECONNAISSANCE D'ARBRES (6 pts)

Une representation d'arbre est codee simplement :
- les sommets, noeuds ou feuilles, sont chacun nommes par un symbole
- un symbole est forme de lettres ou chiffres et commence par une lettre
- les enfants d'un noeud sont cites apres lui, entre parentheses
Exemple 1 :

s1 ( s2 s3 ( s6 s7 ( s8 s9 s10 ) ) s4 s5 )
   
   s1
   |----- s2
   |
   |----- s3 ----- s6
   |       |
   |       | ----- s7
   |               | -----s8
   |               | -----s9
   |               | -----s10
   |----- s4
   |----- s5

Q1a - Reconnaissance d'une description d'arbre :

Ecrire les specifications lex1.flex et gram1.bison pour reconnaitre une telle description d'arbre
Elements fournis : programme principal de lancement prin.c.
(Ce programme peut eventuellement faciliter le deboguage, en lancant l'analyseur avec pour argument
un nom de fichier. Il est alors possible de controler l'avancee par des getchar()).

Q1b - Construction d'une structure d'arbre :

Modifier la specification pour construire en memoire une structure "tree", a lister a la fin.
Elements fournis : fichiers tree_ops.h, tree_ops.c.

2 - RECONNAISSANCE DE DOCUMENT "A LA XML" (6 pts)

Maintenant l'entree schematise un document XML, simplifie par pretraitement (balises remplacees
par un simple nom, paires de balises remplacees par un nom et une paire de parentheses)

On commence par reconnaitre et construire la structure d'arbre, selon le pricipe vu en 1.
Q2 -Donner les specifications gram2.bison, lex2.flex pour construire et lister l'arbre correspondant a l'exemple 2.

Indications : - gram2.bison peut etre identique a gram1.bison
- lex2.flex devrait deriver simplement de lex1.flex :
. adjoindre a l'alphabet les caracteres supplementaires voulus
. autoriser les caracteres '\n' et '\t', traites lexicalement comme ' '
- le "listage" consiste comme + haut a utiliser la fonction DFSPrintTree()

3 - AUTOMATES : codage manuel d'une fonction de reconnaissance (5 pts)

Pour coder en C un automate de reconnaissance, un principe est d'utiliser 2 tables, et des pointeurs de
fonctions. Les tables sont indicees par des entiers, etat courant et valeur du caractere courant. Exemple :

  nextState[currState][currChar] indice du prochain etat  
  action[currState][currChar] 	 fournit un pointeur sur la fonction d'action
  				 a effecter lors de la transition

  Pour l'utilisation de tableaux de pointeurs de fonctions, voici un exemple : 
  	
	void act0( ) { printf("act0\n"); }
  	void act1( ) { printf("act1\n"); }

  	static void (* action [2][2])() = { 	// definition des actions
  	  { act0, act1 },
  	  { act1, act1 }
  	};
	
	void f() {
  	  (*action[0][0])();			// ex. d'appel d'une action
	}

  	int main(void) {
	  f();
  	}

Pour eviter des tables trop grandes, on peut aussi regrouper en une seule les colonnes de contenus
identiques. Si tous les caracteres d'un certain groupe ont les memes effets (pour un etat courant
et un caractere courant donnes, ils produisent les memes actions et transitions), on peut representer
leurs colonnes par une seule. On utilise alors une fonction : int group( currChar) pour determiner le
groupe du caractere courant, et les acces aux tables sont indices par le groupe du caractere courant :

  nextState[currState][currGroup] 
  action[currState][currGroup]

Q3 - Ecrire selon ce principe d'automate une fonction f() reconnaissant l'expression :

[aeiou]+pq[2-57-9]*z.*\n		
sur l'alphabet 	{ 'a', ... 'z', '0',... '9', '\0' }

Indications
- on se limite a traiter une seule entree, une chaine de char (en memoire) terminee par \0
- etablir le diagramme etats / transitions
Si on ne tient pas compte des erreurs il faut cinq etats, dont 1 etat terminal representant le cas ou la reconnaissance
reussit, a quoi on peut ajouter un 6eme etat d'erreur
- definir les groupes de caracteres necessaires (sept pour cet exemple) ;
coder la fonction int group( int ) en consequence.
- definir les contenus des tables nextState[ ][ ] et action[ ][ ] ; comme on se limite a une seule reconnaissance,
il n'y a pas besoin dans les tables de lignes pour les etats terminaux (succes ou echec)
- pour les actions, on peut se limiter a 2 fonctions:

    void PUT( ) { /* ... */ }	// affichant que le caractere courant est accepte
    void ERR( ) { /* ... */ }	// affichant qu'il y a une erreur

On ne cherchera pas a recuperer d'une erreur de reconnaissance.

4 - Recherche selective dans un arbre (3 points + bonus. Exploratoire)

Cette partie peut etre vue comme une introduction schematique au langage XPath, qui permet de designer
des portions dans un document XML. En parcourant la structure d'arbre reconstruite, il s'agit d'effectuer
un filtrage au niveau de chaque sommet. La fonction DFSVisitor(), fournie dans tree_ops.c, permet
d'appliquer a chaque sommet une fonction filtre f() passee en argument. Pour coder f() on ne va pas utiliser
flex [1], mais proceder manuellement, comme en 3.

Q4a) Preparer manuellement une fonction de filtrage RSfiltre() :
coder selon un principe d'automate (cf.3) une fonction reconnaissant l'expression reguliere :
([0-9].[0-9]+\.[0-9]+_02)|(.*\.cpp) sur l'alphabet defini en Q3

Q4b) Effectuer ce filtrage lors de l'exploration de l'arbre :
Incorporer la fonction RSfiltre() a votre analyseur, et la faire appliquer au niveau de chaque sommet
par la fonction DFSVisitor()

[1] Si on utilisait flex, on obtiendrait une 2eme fonction yylex(), en plus de celle qui sert a la lecture
de l'arbre. Aussi, un analyseur genere par flex est concu lit un flot d'entree. Ici, apres avoir lu l'entree
et construit l'arbre, il faut traiter les noms des sommets. Il est pratique d'operer sur des chaines en memoire.