Pendant mes études d’informatique, j’ai eu de nombreux projets pratiques à réaliser, souvent très intéressants. Je me souviens notamment d’un mini système d’exploitation, d’un projet de recherche de plus court chemin dans un graphe (appliqué à un réseau de stations de métro), de résolution approchée d’un système d’équations différentielles pour je ne sais plus quel besoin, etc. Mais il en est un dont je souhaitais parler ici et qui concerne les grammaires algébriques.
L’objectif de ce projet était d’écrire un programme prenant en entrée la description d’une grammaire algébrique G. Le programme devait donc être muni d’un analyseur lexical et syntaxique afin de pouvoir lire cette grammaire depuis un fichier texte, en entrée (nous avons utilisé pour cela les célèbres outils lex/yacc). Le programme devait ensuite transformer cette grammaire sous sa forme normale de Chomsky. Cette forme est beaucoup mieux adaptée à l’application de l’algorithme CYK qui permet de rechercher ensuite si un mot appartient ou non à L(G), le langage engendré par la grammaire G. Une fois la grammaire mise en forme normale de Chomsky, le programme demande à l’utilisateur de saisir un mot et applique l’algorithme CYK pour déterminer si le mot saisi appartient à L(G). Le programme boucle indéfiniment sur la saisie d’un mot et l’application de CYK sur les mots saisis.
La forme normale de Chomsky et les différentes étapes de transformation de G pour aboutir à cette forme sont décrit dans l’ouvrage [Le langage des machines, introduction à la calculabilité et aux langages formels] de Robert Floyd et Richar Biegel, chez International Thomson Publishing. L’algorithme CYK, permettant de rechercher ensuite si un mot appartient à L(G) est également décrit dans le même ouvrage.
Je m’arrête là, car tout est décrit dans le rapport PDF de l’époque: rapport.pdf.
Au cas où, j’ai récemment déposé les sources C de ce projet ici: GitHub.
