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
|