Théorie des Langages

L’étudiant, par cette matière, doit connaître et maîtriser les concepts issus de la théorie des langages et plus particulièrement des langages algébriques, des grammaires, des dérivateurs et des automates à pile. Ces derniers sont en fait à la base de tous les algorithmes d’analyse syntaxique (utilisés par les compilateurs des langages de programmation). Ce module est composé de huit chapitres qui traitent les systèmes générateurs des langages (grammaires) et les systèmes reconnaisseurs des langages (automates). Pour la plupart des langages issus de la classification de Chomsky, l’automate correspondant sera décrit en détail. Pour chaque type d’automate (d’état finis, à pile de mémoire ou machine de Turing), un ensemble d’exercices, est offert aux étudiants, permettant de bien maîtriser son fonctionnement. Un intérêt particulier sera porté sur les automates d’états finis qui sont utilisés par les analyseurs lexicaux et les automates à pile qui sont utilisés par les analyseurs syntaxiques (phases d’un compilateur). Toutes les connaissances acquises seront utilisées pour bien comprendre les différentes phases d’implémentation des compilateurs des langages de programmation. En effet, les travaux pratiques porteront essentiellement sur les automates d’états finis et les grammaires. Ils seront la base pour l’implémentation des deux phases d’un compilateur, à savoir l’analyseur lexical et l’analyseur syntaxique.