De quoi parle-t-on ? / What are we talking about?

La théorie des langages, initialement conçue par des linguistes pour analyser le langage courant, s'est avérée particulièrement adaptée à l'informatique. Ce cours en explore un domaine appelé la théorie des automates et des grammaires ainsi que certaines de ses applications, en particulier dans le cadre de la compilation :

Les expressions régulières, qui sont une manière simple de décrire de manière finie des ensembles potentiellement infinis, et que l'on applique en particulier à la recherche de motifs dans des données. Dans le cadre d'un compilateur, on les applique à l'analyse lexicale, afin de découper un flux d'entrée en jetons interprétables.

Le parsing, qui permet d'interpréter des ensembles de mots plus complexes que ceux décrits par les expressions régulières. Il n'existe toutefois pas d'algorithme de parsing universel efficace, on décrira donc une famille de méthodes applicables à différents cas. Un compilateur utilise un parser pour effectuer une analyse du code source (analyse syntaxique) et produire ainsi un arbre syntaxique.

À l’issue de ce cours, les étudiants sont capables de :
- Formuler un langage rationnel sous forme d'expression régulière.
- Analyser des grammaires et des langages.
- Calculer des parsers LL et LR pour des grammaires hors-contextes.
- Implémenter ces parsers à la main ou grâce aux logiciels Flex et Bison.