Grammaires et langages algébriques

Documents

1. Grammaires et Langages Algébriques (handouts)  

2. Parsers LL et LR; automates à piles (handouts)  

3. Résumé de cours (M. Pantel)  

Compétences travaillées

• grammaires et langages algébriques; notions d’axiomes, de terminaux et de non-terminaux; notion d’ambiguité
• classe simple: grammaire régulière droite
• transformation de grammaires: substitution, factorisation, élimination de la récursivité gauche
• calcul des premiers, des suivants et des symboles directeurs (NULL, FIRST, FOLLOW and SD)
• classe simple: LL(k) et les parsers descendants
• relation avec les automates à pile (pushdown automata)
• quelques notions sur la complexité et les parsers LR