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.
s1 ( s2 s3 ( s6 s7 ( s8 s9 s10 ) ) s4 s5 ) s1 |----- s2 | |----- s3 ----- s6 | | | | ----- s7 | | -----s8 | | -----s9 | | -----s10 |----- s4 |----- s5
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()
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
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
void PUT( ) { /* ... */ } // affichant que le caractere courant est accepte void ERR( ) { /* ... */ } // affichant qu'il y a une erreurOn ne cherchera pas a recuperer d'une erreur de reconnaissance.
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.