Algorithme de Cocke-Younger-Kasami

En informatique théorique et en théorie des langages, l'algorithme de Cocke-Younger-Kasami (CYK) est un algorithme d'analyse syntaxique pour les grammaires non contextuelles, publié par Itiroo Sakai en 1961. Il permet de déterminer si un mot est engendré par une grammaire, et si oui, d'en donner un arbre syntaxique. L'algorithme est nommé d'après les trois personnes qui l'ont redécouvert indépendamment, J. Cocke, dont l'article n'a jamais été publié, D. H. Younger et T. Kasami qui a publié un rapport interne aux US-AirForce. L'algorithme opère par analyse ascendante et emploie la programmation dynamique. L'algorithme suppose que la grammaire est en forme normale de Chomsky. Cette restriction n'est pas gênante dans la mesure où toute grammaire non contextuelle admet une grammaire en forme normale de Chomsky équivalente. Le temps de calcul de cet algorithme est en , où est la longueur du mot à analyser et est la taille de la grammaire. Sans perte de généralité, on suppose que la grammaire n'engendre pas le mot vide . Ainsi, on peut supposer que la grammaire est sous forme normale de Chomsky et qu'elle ne contient pas de règles de la forme (on parle de grammaire propre, voir grammaire non contextuelle). Soit un mot non vide à analyser. L'algorithme emploie la programmation dynamique. Les sous-problèmes sont les suivants : est l'ensemble des non-terminaux qui engendrent le mot pour tout tels que où est la longueur du mot . thumb|380x380px|Principe de l'algorithme CYK : cas de base et cas récursif. On peut calculer les ensembles par récurrence sur . Cas de base : est l'ensemble des non-terminaux tel que est une règle de la grammaire. Cas récursif : Si , est l'ensemble des non-terminaux tels qu'il existe une règle où et sont des non-terminaux et un entier tels que est dans et est dans . La figure à droite montre le cas de base et le cas récursif. On en déduit un algorithme de programmation dynamique qui calcule tous les ensembles . Le mot est engendré par la grammaire si et seulement si est dans où est l'axiome de la grammaire et est la longueur du mot .