- Présentation
du magistère M.M.F.A.I.
- Dérivation
formelle de l'algorithme d'analyse syntaxique d'Earley par abstraction
d'une sémantique des grammaires algébriques.
École normale supérieure de Cachan, 15 mai 2003.
Nous introduisons rapidement quelques concepts mathématiques (treillis, points fixes, systèmes de règles, correspondance de Galois, abstraction de point fixes, etc) qui nous permettent de dériver formellement l'algorithme d'analyse syntaxique d'Earley par un abstraction d'une sémantique de dérivation d'arbres dont on montre qu'elle raffine la sémantique de point fixe de Schützenberger associant à chaque non-terminal de la grammaire le langage terminal fini qu'il engendre, cequi montre la correction de l'algorithme.
Cet exposé est basé sur un travail avec R. Cousot publié dans Theoret. Comput. Sci., 290:531--544, 2003.
\bibitem{Cousot03-Cachan}
P{.} Cousot.
\newblock D\'erivation formelle de l'algorithme d'analyse syntaxique
d'Earley par abstraction d'une s\'emantique des grammaires
alg\'ebriques.
\newblock Journ\'ee de pr\'esentation des cursus en informatique, \'Ecole
normale sup\'erieure de Cachan, 15 mai 2003.
@unpublished{Cousot03-Cachan,
author = {P{.} Cousot},
title = {D\'erivation formelle de l'algorithme d'analyse syntaxique
d'Earley par abstraction d'une s\'emantique des grammaires
alg\'ebriques},
note = {Journ\'ee de pr\'esentation des cursus en informatique, \'Ecole
normale sup\'erieure de Cachan, 15 mai 2003},
}