Les grammaires algébriques sont utilisées en informatique pour définir une syntaxe structurée, par exemple la syntaxe d'un langage de programmation avec des constructions imbriquées comme des conditionnelles, boucles, définitions de fonctions et procédures. Ce module enseigne les grammaires algébriques d'abord d'un point de vue pratique : comprendre et pouvoir écrire des grammaires, constructions d'analyseurs grammaticales descendants (technique LL1) et ascendants (technique LR1), utilisation d'un générateur d'analyse grammaticale moderne (menhir), interaction avec l'analyse lexicale et construction d'un arbre de syntaxe abstraite. Pendant les dernières semaines, les aspects fondamentaux des grammaires seront étudiés, comme leur relation avec les automates à pile, et les limites d'expressivité des grammaires.

1. Rappel des expressions rationnelles et de l'analyse lexicale
2. Grammaires algébriques, dérivations et arbres de dérivation, grammaires ambiguës
3. Relation entre langages rationnels et langages algébriques
4. Grammaires LL(1) : calcul des ensembles FIRST et FOLLOW, transformation de grammaires en forme LL(1), programmation d'analyseurs descendants
5. Principe de l'analyse ascendante (shift/reduce)
6. Construction d'un automate caractéristique LR(0) et LR(1), construction d'une table d'analyse LR(0) et LR(1)
7. Utilisation d'un générateur d'analyse ascendante comme menhir.
8. Programmation de la chaîne d'analyse syntaxique jusqu'à la génération d'une syntaxe abstraite
9. Limitations des grammaires algébriques : le lemme d'itération des grammaires

• Formalismes équivalents aux grammaires (diagrammes de syntaxe, forme de Backus-Naur étendue)
• Études de cas : analyse syntaxique de langages connus aux étudiants comme XML, JSON, YAML, bash, python, OCaml, Java, …
• Propriétés de clôture de la classe des langages algébriques
• Automates à pile (acceptation par pile vide, ou par état acceptant), traductions entre grammaires et automates à pile

• Cours Automates et Analyse Lexicale du L2 :
  • Expressions rationnelles
  • Automates déterministes, non-déterministes et avec epsilon-transitions
  • Déterminisation, et élimination des epsilon-transitions
  • Lemme d'itération des langages rationnels (lemme de l'étoile)
  • Utilisation d'un générateur d'analyseur lexicale, du type lex.

• Cours Programmation Fonctionnelle du L3 :
  • Programmation fonctionnelle en OCaml
  • Programmer avec des structures de données algébriques (arbres) en OCaml
  • Utilisation basique des modules en OCaml (fichiers séparés pour interface et corps d'un module)
  • Compilation d'un projet OCaml consistant en plusieurs modules pour créer un exécutable autonome, en utilisant une des techniques comme dune, ocamlbuild, make, …