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^[1]^,^[2]. 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é^[3], D. H. Younger^[4] et T. Kasami qui a publié un rapport interne aux US-AirForce^[5].

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^[6]. Le temps de calcul de cet algorithme est en $O(|m|^{3}\cdot |G|)$ , où $|m|$ est la longueur du mot $m$ à analyser et $|G|$ est la taille de la grammaire.

↑ (en) Itiroo Sakai, « Syntax in universal translation », dans 1961 International Conference on Machine Translation of Languages and Applied Language Analysis, Teddington, England, vol. II, London, Her Majesty’s Stationery Office, 1962, p. 593-608.
↑ (en) Dick Grune, Parsing techniques: a practical guide, New York, Springer, 2008, 2^e éd. (ISBN 978-0-387-20248-8), p. 579.
↑ Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées Cocke
↑ Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées Younger
↑ Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées Kasami
↑ (en) Sipser, Michael, Introduction to the Theory of Computation (1st ed.), 1997 (ISBN 978-0-534-94728-6).

[1] (en) Itiroo Sakai, « Syntax in universal translation », dans 1961 International Conference on Machine Translation of Languages and Applied Language Analysis, Teddington, England, vol. II, London, Her Majesty’s Stationery Office, 1962, p. 593-608.

[2] (en) Dick Grune, Parsing techniques: a practical guide, New York, Springer, 2008, 2^e éd. (ISBN 978-0-387-20248-8), p. 579.

[Cocke-3] Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées Cocke

[Younger-4] Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées Younger

[Kasami-5] Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées Kasami

[6] (en) Sipser, Michael, Introduction to the Theory of Computation (1st ed.), 1997 (ISBN 978-0-534-94728-6).

[1]

[2]

[3]

[4]

[5]

[6]