Différences

Ci-dessous, les différences entre deux révisions de la page.

@@ Ligne 1: / Ligne 1: @@
+~~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, ...

Outils pour utilisateurs

Outils du site

Différences

Outils de la page