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. 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 trouvé 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(|m|^{3}\cdot |G|)$, où $|m|$ est la longueur du mot $m$ à analyser et $|G|$ est la taille de la grammaire.

Principe

L'algorithme emploie la programmation dynamique. Sans perte de généralité, on suppose que la grammaire $G$ n'engendre pas le mot vide $\epsilon$. Ainsi, on peut supposer que la grammaire $G$ est forme normale de Chomsky et qu'elle ne contient pas de règles de la forme $N\rightarrow \epsilon$ (on parle de grammaire propre, voir grammaire non contextuelle). Soit $m$ un mot non vide à analyser. Les sous-problèmes sont les suivants : $P[i,j]$ est l'ensemble des non-terminaux qui engendrent le mot $m[i..j]$ pour tout $i,j$ tels que $1\leq i\leq j\leq |m|$ où $|m|$ est la longueur du mot $m$.

Principe de l'algorithme CYK : cas de base et cas récursif

On peut calculer les ensembles $P[i,j]$ par récurrence sur $|j-i|$.

• Cas de base : $P[i,i]$ est l'ensemble des non-terminaux $N$ tel que $N\rightarrow m[i]$ est une règle de la grammaire.
• Cas récursif : Si $i<j$, $P[i,j]$ est l'ensemble des non-terminaux $N$ tels qu'il existe une règle $N\rightarrow BC$ où $B$ et $C$ sont des non-terminaux et un entier $k\in \{i,\dots ,j-1\}$ tels que $B$ est dans $P[i,k]$ et $C$ est dans $P[k+1,j]$.

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 $P[i,j]$. Le mot $m$ est engendré par la grammaire si et seulement si $S$ est dans $P[1,|m|]$ où $S$ est l'axiome de la grammaire et $|m|$ est la longueur du mot $m$.

Pseudo-code

Voici un pseudo-code inspiré de l'analyse de la section précédente :

Pour i = 1 à $|m|$
    $P[i,i]$ := ensemble des non-terminaux $N$ tel que $N\rightarrow m[i]$ est une règle de la grammaire
Pour d = 1 à $|m|-1$
    Pour i = 1 à $|m|$-d
         j := i+d
         $P[i,j]$ := ensemble des non-terminaux $N$ tels qu'il existe une règle $N\rightarrow BC$ et un entier $k\in \{i,\dots ,j-1\}$ tels que
                                $B$ est dans $P[i,k]$ et $C$ est dans $P[k+1,j]$

Retourne oui si $S$ est dans $P[1,|m|]$ ; non sinon.

On peut donner un pseudo-code qui montre la complexité cubique en $|m|$ :

Pour i = 1 à $|m|$
    $P[i,i]$ := ensemble des non-terminaux $N$ tel que $N\rightarrow m[i]$ est une règle de la grammaire
Pour d = 1 à $|m|-1$
    Pour i = 1 à $|m|$-d
         j := i+d
         $P[i,j]$ := ensemble vide
         Pour tout k = i à j-1
                  Pour tout $B$ est dans $P[i,k]$ et $C$ est dans $P[k+1,j]$
                            Pour tout non-terminal $N$ tel que $N\rightarrow BC$ est une règle
                                  Ajouter $N$ à $P[i,j]$
Retourne oui si $S$ est dans $P[1,|m|]$ ; non sinon. 

Variantes

Si la grammaire est pondérée, l'algorithme de CYK permet de générer l'arbre le plus lourd qui engendre la phrase.^{[réf. nécessaire]}

La restriction qui consiste à avoir une grammaire en forme normale de Chomsky est essentiellement esthétique et Lange et Leiß discutent une variante de l'algorithme CYK avec des restrictions plus faibles.

Démonstrations

• Une démonstration de l'algorithme CYK en Javascript
• Une autre démonstration de l'algorithme CYK en JavaScript
• Applet de l'université de Leipzig (site en allemand)
• Un exerciseur pour générer des exemples pour l'algorithme CYK

Bibliographie

L'algorithme est exposé dans les ouvrages théorique sur les langages formels.

• Alfred Aho, Monica Lam, Ravi Sethi et Jeffrey Ullman, Compilateurs : principes, techniques et outils : Avec plus de 200 exercices, Pearson, 2007, 2^e éd., 928 p. (ISBN 9782744070372 et 2744070378) — Exercice 4.4.9 du Dragon book.
• (de) Katrin Erk et Lutz Priese, Theoretische Informatik : eine umfassende Einführung, Berlin, Springer, 2008 (ISBN 9783540763192, OCLC 244015158) — 6.8.1 Das Wortproblem, p. 154-159.
• (en) Michael A. Harrison, Introduction to Formal Language Theory, Reading, Mass. [u.a.], Addison-Wesley, 1978 (ISBN 0201029553, OCLC 266962302) — Section 12.4 The Cocke-Kasami-Younger Algorithm, p. 430-442.
• (en) John E. Hopcroft, Rajeev Motwani et Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison Wesley, 2001, 521 p. (ISBN 9780201441246 et 0201441241) — Section 7.4.4 Testing Membership in a CFL, p. 298-304.
• (en) Peter Linz, An Introduction to Formal Languages and Automata, Jones & Bartlett Learning, 2001, 410 p. (ISBN 9780763714222 et 0763714224) — Section 6.3 A Membership Algorithm for Context Free Grammars, p. 172-174.
• (en) Jeffrey Shallit, A Second Course in Formal Languages and Automata Theory, Cambridge University Press, 2009, 240 p. (ISBN 9780521865722 et 0521865727) — Section 5.1 Recognition and parsing in general grammars p. 141-144

Voir aussi

• Analyse Earley