Algorithme de Cocke-Younger-Kasami

Sans perte de généralité, on suppose que la grammaire ${\displaystyle G}$ n'engendre pas le mot vide ${\displaystyle \epsilon }$. Ainsi, on peut supposer que la grammaire ${\displaystyle G}$ est sous forme normale de Chomsky et qu'elle ne contient pas de règles de la forme ${\displaystyle N\rightarrow \epsilon }$ (on parle de grammaire propre, voir grammaire non contextuelle).

Soit ${\displaystyle m}$ un mot non vide à analyser. L'algorithme emploie la programmation dynamique. Les sous-problèmes sont les suivants : ${\displaystyle P[i,j]}$ est l'ensemble des non-terminaux qui engendrent le mot ${\displaystyle m[i..j]}$ pour tout ${\displaystyle i,j}$ tels que ${\displaystyle 1\leq i\leq j\leq |m|}$ où ${\displaystyle |m|}$ est la longueur du mot ${\displaystyle m}$.

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

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

• Cas de base : ${\displaystyle P[i,i]}$ est l'ensemble des non-terminaux ${\displaystyle N}$ tel que ${\displaystyle N\rightarrow m[i]}$ est une règle de la grammaire.
• Cas récursif : Si ${\displaystyle i<j}$, ${\displaystyle P[i,j]}$ est l'ensemble des non-terminaux ${\displaystyle N}$ tels qu'il existe une règle ${\displaystyle N\rightarrow BC}$ où ${\displaystyle B}$ et ${\displaystyle C}$ sont des non-terminaux et un entier ${\displaystyle k\in \{i,\dots ,j-1\}.}$ tels que ${\displaystyle B}$ est dans ${\displaystyle P[i,k]}$ et ${\displaystyle C}$ est dans ${\displaystyle 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 ${\displaystyle P[i,j]}$. Le mot ${\displaystyle m}$ est engendré par la grammaire si et seulement si ${\displaystyle S}$ est dans ${\displaystyle P[1,|m|]}$ où ${\displaystyle S}$ est l'axiome de la grammaire et ${\displaystyle |m|}$ est la longueur du mot ${\displaystyle m}$.

Considérons la grammaire suivante en forme normale de Chomsky :

${\displaystyle {\begin{array}{lcl}{\mathit {S}}&\to &{\mathit {GN}}\;{\mathit {GV}}\\{\mathit {GV}}&\to &{\mathit {GV}}\;{\mathit {C}}\\{\mathit {GV}}&\to &{\mathit {V}}\;{\mathit {GN}}\\{\mathit {GV}}&\to &{\textit {mange}}\\{\mathit {C}}&\to &{\mathit {P}}\;{\mathit {GN}}\\{\mathit {GN}}&\to &{\mathit {Det}}\;{\mathit {N}}\\{\mathit {GN}}&\to &{\textit {elle}}\\{\mathit {V}}&\to &{\textit {mange}}\\{\mathit {P}}&\to &{\textit {avec}}\\{\mathit {N}}&\to &{\textit {poisson}}\\{\mathit {N}}&\to &{\textit {fourchette}}\\{\mathit {Det}}&\to &{\textit {du}}\\{\mathit {Det}}&\to &{\textit {une}}\end{array}}.}$

où l'ensemble des non-terminaux est ${\displaystyle \{S,GV,C,GN,V,P,N,Det\}.}$ et l'ensemble des terminaux (lettres) est ${\displaystyle \{elle,poisson,fourchette,mange,du,avec,une\}.}$. Ici, « elle » s'appelle une lettre (bien que c'est un mot) et une phrase comme « elle mange du poisson avec une fourchette » s'appelle un mot.

Maintenant, analysons le mot ${\displaystyle m}$ qui est la phrase « elle mange du poisson avec une fourchette » avec l'algorithme CYK. Dans la table suivante, on indique les valeurs de ${\displaystyle P[i,j]}$ :

Le mot « elle mange du poisson avec une fourchette » est reconnu car l'axiome ${\displaystyle S}$ est dans ${\displaystyle P[1,7]}$.

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

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

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

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

• 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
• Exemple d'implémentation en Python

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

• Alfred Aho, Monica Lam, Ravi Sethi et Jeffrey Ullman, Compilateurs : principes, techniques et outils : avec plus de 200 exercices, Paris, Pearson, 2007, 2^e éd., 928 p. (ISBN 978-2-7440-7037-2 et 2744070378, BNF 41172860) — Exercice 4.4.9 du Dragon book.
• (de) Katrin Erk et Lutz Priese, Theoretische Informatik : Eine umfassende Einführung, Berlin, Springer, 2008, 485 p. (ISBN 978-3-540-76319-2, 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, 594 p. (ISBN 978-0-201-02955-0, 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, 2^e éd., 521 p. (ISBN 978-0-201-44124-6 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 978-0-7637-1422-2 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 978-0-521-86572-2 et 0521865727) — Section 5.1 Recognition and parsing in general grammars p. 141-144

• Analyse Earley
• Modèle de Markov caché
• Automate fini
• Théorie des automates
• Grammaire algébrique probabiliste
• Algorithme de Viterbi
• Programmation dynamique
• Bio-informatique
• Reconnaissance automatique de la parole
• Complexité de la multiplication de matrices