CC21 - COMPLEXITE,COMPILATION - TP NOTE

Le TP peut etre realise en binome.
Voir les indications pour la remise du travail.

On propose des etapes vers une reconnaissance de fichiers XML. Les exemples a
traiter sont a prendre dans le sujet lui-meme, ou bien a fabriquer manuellement
(prendre des exemples simples et significatifs). On fournit aussi quelques
exemples su[[;entaires : data1.txt, data2.txt, data3.txt. La demarche est
decomposee et guidee. Les questions 1 et 2 sont independantes.
La question 3 combine les resultats de Q1.2 et Q2, puis elargit.

1 - ANALYSE LEXICALE SEULE (9.5 points)

NOTE. Attention, dans les exemplesdu 1.1 et 1.2, un espace artificiel a ete
insere apres le caractere <, pour affichage correct dans le navigateur.
Il DOIT etre supprimme, car non admis en XML.

1.1 - RECONNAISSANCE DE QUELQUES BALISES DE L'EN-TETE (5.5 points)

Les 3 balises a reconnaitre sont introduites par les exemples suivants :
< ?xml version="1.0" encoding="ISO-8859-1" ?>
< ?xml-stylesheet href="catalog.xsl" type="text/xsl" ?>
< !DOCTYPE catalog SYSTEM "catalog.dtd">

En situation reelle, les valeurs de champs peuvent etre differentes, mais on
veut verifier que les balises sont correctes. Pour la clarte on va specifier
separement 3 analyseurs, chacun dedie a une de ces balises. Indications :
- c'est + clair/efficace d'utiliser des "sous-expressions" (Memento Flex,IV.1-b)
- on peut aussi proceder graduellement, en particularisant de plus en plus

a) BALISES DU TYPE DU 1er EXEMPLE : Specification lex1.1a.l :
. admettre dans le 2e champ un no de version general MM.NN, MM et NN entiers
. faire que le 3e champ soit optionnel, avec valeur prise parmi :
  ISO-8859-X (X entier dans [1,5]), ....

b) BALISES DU TYPE DU 2eme EXEMPLE : Specification lex1.1b.l :
. admettre text/css ou text/xsl pour valeur de type
. admettre XXX.xsl pour valeur de href, XXX etant un symbole avec des '/'
  possibles, sauf a la fin, ni deux / consecutifs

c) BALISES DU TYPE DU 3eme EXEMPLE : Specification lex1.1c.l :
. admettre n'importe quel nom XXX (sans caractere special) dans le 2e champ
. admettre "XXX.dtd" comme dernier champ, avec XXX symbole comme defini en b)

1.2 - RECONNAISSANCE DES BALISES DU CORPS (4 points)

(Resultats reutilises en question 2). Il s'agit de reconnaitre les balises :
- "ouvrante" :	< XXXX ............>
- "fermante" :	< /XXXX>
- "simple" :	< XXXX ............ />
Dans les 3 cas XXXX est le nom de la balise (donc suivi d'un ' ' ou d'un '>')

a) RECONNAISSANCE SEULE
   Preparer un analyseur lexical lex1.2a.l : reconnaissant et signalant ces
   3 balises, au moyen de 3 regles expression-action. Hypothese : supposer
   ici qu'une balise "simple" ne peut pas etre de la forme : <.../... />

b) RECONNAISSANCE AVEC EXTRACTION DU NOM
   Deriver un analyseur lex1.2b.l, qui de plus extraira le nom de la balise
   et l'imprimera avec encadrement. Indications : on peut par exemple :
- ecrire une fonction char * getFieldFrom( int beg ), appelable depuis
  differents blocs d'actions, retournant un pointeur sur une chaine
- beg est l'indice du debut du champ dans le fragment yytext, et le champ
  s'etend jusqu'a un delimiteur (prevoir les differents cas de balise)

c) (Facultatif/bonus) Ameliorer votre specification pour la balise "simple",
   pour admettre les formes <.../... />, mais pas les formes <...//... />

2 - GRAMMAIRES D'ARBRES (8 points)

On veut reconnaitre une structure d'arbre, codee par balises comme dans un
fichier XML, mais pour l'instant sans les details lexicaux. Les noeuds
(avec enfants) et les feuilles sont tous etiquettes d'un nom.
Un noeud definit ses enfants par une liste de symboles, encadr� par des
balises "OPxx" (debut) et "CLxx" (fin). Les marques "OP" et "CL" sont a
utiliser telles que, les suffixes xx correspondent au nom du noeud. Une
feuille est definie par une balise Syy, S=chaine imposee, yy=nom au choix

  1		L'arbre ci-contre est represente par :
  |__ 2		OP1  OP2  S3  S4  CL2  OP5  S6  CL5  S7  CL1
  |   |__3
  |   |__4	On admet qu'un noeud puisse (contrairement au vocabulaire
  |		de la theorie des graphes) etre muni d'une liste vide.
  |__ 5
  |   |__6	Pour representer la structure seule on ommet les noms ; ici
  |		la structure est decrite par : OP OP S S CL OP S CL S CL
  |__ 7

2.1 - Reconnaissance de structure (5 pts)

a) Realiser un analyseur : lex2.1a.l,, gram2.1a.y (3 points). Indications :
  - definir des regles syntaxiques pour reconnaitre :
   . une notion de Bloc, encadre par OP et CL
   . une notion de Liste, correspondant au contenu d'un bloc
  - supposer pour l'instant que les donnees en entree sont sur une seule ligne
  - analyseur lexical : il pourra absorber espaces/tabulations.
    Il peut etre realise avec flex (ou eventuellement manuellement).
  - analyseur syntaxique : pour traiter le '\n' final, on peut reconnaitre
    comme axiome la notion de "Texte" = la succession d'un Bloc et du '\n'
    Noter qu'un 2eme \n en fin de fichier creera une erreur d'analyse

b) Variante immediate : entree sur plusieurs lignes (1 point)
   En vue du traitement de fichiers XML, on considere maintenant que les unites
   lexicales OPxx, CLxx, Sxx figurent en entree a raison d'une seule par ligne.
   Modifier votre analyseur en gram2.1b.y (on gardera lex2.1b.l = lex2.1a.l)

2.2) Reconnaissance d'arbre etiquette (3 points)

Modifier votre analyseur pour que, en plus de l'arrangement structurel correct
des blocs OP/CL, il verifie que les symboles OPxx et CLyy qui se correspondent
structurellement portent aussi le meme nom, cad. que xx == yy. Indications :
- dans l'analyseur syntaxique gram2.2.y :
. utiliser la directive %union pour affecter un type adequat a yylval
. bison exigera des types pour les symboles non terminaux; on pourra leur
  donner le meme type (de toute facon on n'affectera pas de valeur a $$)
. associer une action a la reconnaissance d'un Bloc : imprimer les noms des deux
  balises, puis si difference imprimer une erreur et terminer l'analyse

- pour l'analyseur lexical, deriver une variante du precedent, qui extrait le
  nom de chaque balise (comme en 1.2b) et le passe a l'analyseur syntaxique

3 - TRAITEMENT DU CORPS D'UN FICHIER XML (2.5 points)

Le corps d'un fichier XML decrit un arbre etiquette, selon le principe de balise
precedent. Au lieu des balises simplifiees OP, CL, S de la question 2, il s'agit
des balises (ouvrante, fermante, simple) de la question 1.2.

3.1 - Reconnaissance de l'arbre etiquette (1.5 points)

En adaptant vos resultats pour Q1.2 et Q2.2, definir un analyseur reconnaissant
l'arbre etiquette decrit dans le corps d'un fichier XML :
- lex3.1.l : derive directement de 1.2b.l, passe le nom de balise via yylval,
  puis retourne la categorie lexicale. Penser aussi a retourner '\n'
- gram3.1.y : deduit directement de gram2.2.y
  Il pourra etre utile de definir une forme alternative pour un Block :
  pour le cas ou balises ouvrante et fermantes seraient sur 1 meme ligne

3.2 - Construction d'une structure d'arbre (1 point) (Elements fournis)

On pourra chercher a deduire de l'analyseur precedent des variantes lex3.2.l,
gram3.2.y capables de construire une structure de donn�s reproduisant celle
de l'arbre etiquette produit par le corps du fichier XML.
Elements fournis (fichier lists.c) :
- fonctions pour creer des objets List, Node, Block
- fonction de listage d'une structure d'arbre
- main() de demonstration