Les analyseurs syntaxiques LR sont implémentés par des automates à pile. Cette dernière est constituée d'états mais aussi de valeurs sémantiques qui ont des types hétérogènes. En général, les parseurs écrits en C ignorent ce problème en passant outre la vérification des types. Dans les langages typés comme ML, on utilise une structure de données étiquetée pour pouvoir vérifier que le type de la valeur sémantique correspond bien à celui attendu. Cependant, dans les deux cas, une erreur dans le générateur peut provoquer un plantage du parseur. Dans cet exposé, je montrerai comment utiliser les types algébriques généralisés pour capturer les invariants de la pile de l'automate. Le typeur prouve alors que le parseur ne peut pas planter à l'exécution.
Menhir est un générateur d'analyseurs syntaxiques LR(1) pour Objective Caml. Outre la partie arrière typée (inachevée, en attendant l'apparition des types algébriques généralisés dans Objective Caml), Menhir est supérieur à ocamlyacc en plusieurs points, tant en ce qui concerne le langage de spécification des grammaires que le moteur de construction des automates. J'exposerai donc les améliorations les plus intéressantes.