Algorithme CYK

L'algorithme en pseudocode est le suivant :

Soit l'entrée une chaîne I de n caractères : a₁ … aₙ . Soit la grammaire r symboles non terminaux R₁ … Rₙ , avec R₁ comme symbole de départ . Soit P [ n , n , r ] un tableau de booléens. Initialisez tous les éléments de P à faux. Soit back [ n , n , r ] un tableau de listes de triplets pointant vers l' arrière . Initialisez tous les éléments de back à la liste vide.pour chaque s = 1 à n pour chaque unité de production R v → un ensemble s P [ 1 , s , v ] = vraipour chaque l = 2 à n -- Longueur de l'intervalle pour chaque s = 1 à n - l + 1 -- Début de l'intervalle pour chaque p = 1 à l - 1 -- Partition de l'intervalle pour chaque production R a → R b R c si P [ p , s , b ] et P [ l - p , s + p , c ] alors définir P [ l , s , a ] = vrai, ajouter <p,b,c> à l'arrière [ l , s , a ] Si P [n, 1 , 1 ] est vrai, alors I appartient au langage et retourner à l'origine . En remontant le parcours, on peut facilement construire tous les arbres d'analyse syntaxique possibles de la chaîne. Sinon, retourner « n'appartient pas au langage ».

Soit l'entrée une chaîne I composée de n caractères : a₁ … aₙ . Soit la grammaire r symboles non terminaux R₁ … Rₙ , avec R₁ comme symbole initial . Soit P [ n , n , r ] un tableau de nombres réels. Initialisez tous les éléments de P à zéro. Soit back [ n , n , r ] un tableau de triplets pointant vers l' arrière . Pour chaque s = 1 à n, pour chaque unité de production R <sub>v</sub> → a<sub> s</sub>, définir P [ 1 , s , v ] = Pr( R<sub> v</sub> → a <sub> s </sub> ) . Pour chaque l = 2 à n , la longueur de l'intervalle est définie pour chaque s = 1 à n - l + 1 , le début de l'intervalle est défini pour chaque p = 1 à l - 1 , la partition de l'intervalle est définie pour chaque production R <sub> a</sub> → R <sub> b</sub> R <sub> c </sub> . La probabilité de partitionnement est calculée comme suit : P [ p , s , b ] * P [ l - p , s + p , c ]. Si cette probabilité est supérieure à P [ l , s , a ] , alors P [ l , s , a ] = probabilité de partitionnement et l'intervalle [ l , s , a ] = <p, b, c> est défini .Si P [n, 1 , 1 ] > 0, alors trouver l'arbre d'analyse syntaxique en remontant le parcours et retourner l'arbre d'analyse syntaxique ; sinon, retourner « n'appartient pas au langage ».

En termes informels, cet algorithme considère chaque sous-chaîne possible de la chaîne d'entrée et définit

L'algorithme décrit ci-dessus est un module de reconnaissance qui détermine uniquement si une phrase appartient à la langue. Il est facile de l'étendre en un analyseur syntaxique qui construit également un arbre d'analyse , en stockant les nœuds de l'arbre comme éléments du tableau, au lieu du booléen 1. Le nœud est lié aux éléments du tableau qui ont servi à le produire, afin de construire la structure arborescente. Un seul nœud de ce type par élément du tableau est nécessaire si l'on ne doit produire qu'un seul arbre d'analyse. Cependant, si l'on souhaite conserver tous les arbres d'analyse d'une phrase ambiguë, il est nécessaire de stocker dans l'élément du tableau la liste de toutes les manières d'obtenir le nœud correspondant lors de l'analyse. Ceci est parfois réalisé à l'aide d'une seconde table B[n,n,r] de pointeurs de retour . Le résultat final est alors une forêt partagée d'arbres d'analyse possibles, où les parties communes aux arbres sont factorisées entre les différentes analyses. Cette forêt partagée peut être commodément lue comme une grammaire ambiguë ne générant que la phrase analysée, mais avec la même ambiguïté que la grammaire originale, et les mêmes arbres d'analyse jusqu'à un renommage très simple des non-terminaux, comme l'a montré

Comme l'ont souligné et Leiß (2009) , l'inconvénient de toutes les transformations connues en forme normale de Chomsky est qu'elles peuvent entraîner une augmentation indésirable de la taille de la grammaire. La taille d'une grammaire est la somme des tailles de ses règles de production, la taille d'une règle étant égale à un plus la longueur de son membre droit.) .

Il est également possible d'étendre l'algorithme CYK pour analyser des chaînes de caractères à l'aide de grammaires hors contexte pondérées et stochastiques . Les poids (probabilités) sont alors stockés dans la table P au lieu de booléens ; ainsi, P[i,j,A] contient le poids minimal (probabilité maximale) que la sous-chaîne de i à j puisse être extraite de A. D'autres extensions de l'algorithme permettent d'énumérer toutes les analyses d'une chaîne par poids croissant (probabilité décroissante).

Le temps d'exécution de CYK dans le pire des cas est den représente la longueur de la chaîne analysée et | G | la taille de la grammaire CNF G. Ceci en fait l'un des algorithmes les plus efficaces pour la reconnaissance des langages hors contexte généraux en pratique. des algorithmes de multiplication efficace de matrices binaires (0-1) peuvent être utilisés pour effectuer ce calcul.

En utilisant l' algorithme de Coppersmith-Winograd pour multiplier ces matrices, on obtient un temps d'exécution asymptotique dans le pire des cas de