Cours ENSIIE Langages et Systèmes Formels (LSF) 2024

Horaire: lundi 9:00-12:45, du 2 septembre au 7 octobre 2024, examen le 18 novembre 2024

Lieu: ENSIIE

Intervenants: Frédéric Blanqui (cours + TD)

Planning (TBC):

• 2 septembre, 9:00-12:45, amphi 101: cours 1 (grammaires algébriques)
• 9 septembre, 9:00-12:45, amphi 101 + salle 222: cours 2 (automates) + TD 1
• 16 septembre, 9:00-12:45, amphi 101 + salle 222: cours 3 (minimisation) + TD 2
• 23 septembre, 9:00-12:45, amphi 101 + salle 222: cours 4 (expressions régulières) + TD 3
• 30 septembre, 9:00-12:45, amphi 101 + salle 133: cours 5 (grammaires LL(k)) + TP
• 7 octobre, 11:00-12:45, salle 222: TD 5
• 18 novembre, 9:00-10:45, amphi 101: examen

Résumé:

Dans ce cours, nous nous intéressons à différentes manières de définir des langages pour représenter des données (e.g. XML) ou des programmes (e.g. C, Java, OCaml), et comment vérifier qu'un fichier est bien un fichier XML ou un programme C, Java, etc. sans erreurs syntaxiques.

Nous verrons plusieurs manières de définir des langages: avec une grammaire (nous ne considérons que des grammaires dites algébriques ou hors-contextes), des ``machines'' (automate ou automate à pile), ou une ``expression régulière''.

Dans le 1er cours, nous introduirons la notion de grammaire algébrique et établirons un certain nombre de propriétés fondamentales des grammaires algébriques et de la classe des langages définissables par une grammaire algébrique. Nous verrons également un certain nombre de transformations permettant de simplifier la présentation d'une grammaire ou de la mettre sous une forme particulière.

Dans le 2e cours, nous introduirons la notion d'automate. Nous verrons que l'analyse syntaxique d'un langage défini par une forme très simple de grammaire dite linéaire peut être implémentée de manière très efficace en utilisant un automate (cela fera l'objet d'un TP).

Dans le 3e cours, nous verrons comment minimiser le nombre d'états d'un automate. Nous verrons également que les automates avec $\vep$-transitions ne sont pas plus puissants que les automates standards, et quels sont les propriétés de la classe des langages reconnaissables par automate.

Dans le 4e cours, nous introduirons la notion d'expression régulière. Nous verrons alors que grammaires linéaires, automates et expressions régulières sont en fait équivalents et définissent la même classe de languages, mais que ces trois techniques sont limitées: elles ne permettent pas de traiter les langages bien parenthésés.

C'est ainsi que, dans le 5e et dernier cours, nous considérons la classe des langages dits LL(k) qui peuvent être analysés efficacement en utilisant un automate à pile.

Pour plus de détails, voir par exemple:

• ``Langages formels, calculabilité et complexité'', Olivier Carton, Editions Vuibert, ISBN : 978-2-311-01400-6.
• ``The theory of parsing, translation, and computing. Volume I: Parsing'', Alfred Aho et Jeffrey Ullman, Prentice-Hall.

Exemples de grammaires:

• Grammaire Yacc d'ANSI C
• Grammaire de C11
• Grammaire de Python
• Liste de grammaires ANTLR (cf. ANTLR)
• Grammaire d'OCaml 5.0