~~NOTOC~~

====== Grammaires et Analyse Syntaxique (GAS6) ======

===== Description =====

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.

===== Syllabus =====

==== Sujets centraux ====

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

===== Pré-requis =====

  * Cours [[..:l2:aal3|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 [[pf5|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, ...