INF 424 A : Des grammaires formelles aux documents XML


Retour
Imprimer la fiche programme
Code analytique: EDOINFMA2
Responsable  :    
Programmé en UV2 MAJ INF

Présentation :

La théorie des langages fait partie des fondements de l'informatique. Dans ce module nous allons aborder certaines notions de cette théorie (les automates d'états finis, les expressions régulières, les grammaires formelles, les traitements semantiques) suivies d'une application directe : la structuration de documents à travers la norme XML, définie par le consortium W3C.

Un langage est un ensemble de «mots» définis sur un «alphabet». Les expressions régulières (que l'on retrouve dans tous les langages de programmation modernes) sont un moyen de définir une classe particulière de langages, appelés langages réguliers. Les automates en donnent une description analytique (un mot appartient à un langage s'il peut être obtenu par une suite de transitions entre états de l'automate) et les grammaires formelles une description générative (un mot appartient à un langage s'il peut être obtenu par une suite de productions à partir d'un axiome de départ).

La norme XML (= langage de balisage extensible) se propose d'exprimer, à travers des balises explicites, la structure d'un document. Un document XML peut être décrit comme un arbre d'«éléments» dont les feuilles peuvent être des éléments ou des chaînes de caractères dans le codage Unicode.

Une chaîne de caractères peut être considérée comme un mot d'un langage décrit par Unicode. À l'aide d'un automate on peut vérifier l'appartenance d'une chaîne au langage Unicode.

La norme XML prévoit un certain nombre de formalismes de grammaires : les DTD, les schémas Web, les schémas Relax NG, etc. Un document XML «valide» est un mot du langage XML qui appartient au sous-langage spécifié par un de ces formalismes.

Mais déterminer si un mot appartient à un langage décrit par une grammaire (= si un document XML est valide) n'est pas suffisant. Très souvent on associe des traitements aux diverses étapes d'une analyse (transitions d'un arbre, ou productions d'une grammaire). C'est ainsi qu'un compilateur va non seulement vérifier par le biais d'une analyse syntaxique si une expression donnée est valide dans le cadre d'un langage de programmation donné, mais aussi la convertir en code binaire, pour qu'elle puisse être exécutée par la suite. On appelle cela un «traitement sémantique».

Dans le cadre de XML on parle de «transformation de documents», un cas très fréquent étant la conversion de données XML en site Web XHTML. Dans un souci de normalisation, le consortium W3C a défini une norme basée sur XML pour décrire de telles transformations, il s'agit de XSLT (= langage extensible de feuilles de style de transformation). Mais il existe d'autres approches : l'approche évènementielle SAX et l'approche orientée objet DOM.

Objectifs (obsolète):

1) comprendre les notions d'automate, de langage formel, d'expression régulière, de grammaire formelle ;

2) comprendre le fonctionnement des technologies basées sur la norme XML et leur lien avec les notions de la théorie des langages

3) utiliser les expressions régulières dans plusieurs contextes

4) être capable de concevoir une DTD ou un schéma pour une application précise

5) comprendre le principe de traitement sémantique et ses applications (compilation, transformation de document)

6) être capable de développer une transformation de documents XML selon un cahier de charges

Pré-requis :

Quelques connaissances en PHP pour le TP sur SAX et DOM. Voici une très bonne Introduction à PHP.

Liens :

L'URL du module est : http://omega.enstb.org/yannis/cours/isi431/

Volume horaire : 21h


Contenu détaillé :

Premier cours (3 h) : Langages formels, langages réguliers, expressions régulières, automates, grammaires formelles

Deuxième cours (3 h) : Grammaires hors-contexte, analyse et traitements sémantiques

Troisième cours (3 h) : Unicode et XML, DTD, espaces de nommage, schémas Web

Quatrième cours (3 h) : XPath et XSLT

Travaux personnels encadrés :

PC (1h30) : Automates

TP 1 (1h30) : Expressions régulières sous AWK

TP 2 (3 h) : SAX et DOM sous PHP

TP 3 (3 h) : XPath et XSLT


Année 2007/2008
Dernière mise à jour le 05-JUL-07
Validation par le responsable de programme le


IMT Atlantique
Campus de Brest
Technopôle Brest-Iroise
CS 83818
29238 Brest Cedex 3
France

Tél  +33 (0)2 29 00 11 11
Fax +33 (0)2 29 00 10 00