Grammaires et analyseurs: un aperçu du traitement du langage

Cette séance de cours couvre les bases du traitement du langage informatique, en se concentrant sur les grammaires et les analyseurs. Il commence par une introduction aux grammaires formelles, les définissant comme des ensembles de règles de réécriture composées de symboles terminaux et non terminaux. L'instructeur explique la hiérarchie Chomsky, détaillant les différents types de grammaires: grammaires sans restriction, sensibles au contexte, sans contexte et régulières, ainsi que leurs propriétés et leurs complexités. La séance de cours traite également des expressions régulières et de leur rôle dans la description des langues régulières. Le concept d'analyse des arbres est introduit, illustrant comment ils représentent la structure syntaxique des mots reconnus. Les défis courants d'analyse tels que l'ambiguïté et la récursion infinie sont abordés, ainsi que les stratégies de désambiguïsation et d'affacturage gauche / droite. La séance de cours se termine par un aperçu des algorithmes d'analyse, mettant en évidence les différences entre les approches ascendantes et descendantes, et présente les combinateurs d'analyseurs en Scala, démontrant comment les analyseurs peuvent être composés pour gérer des structures de langage complexes.