Modèles de Langage et Analyse Syntaxique
Cours 3 - Algorithmes d’analyse syntaxique - grammaires hors-contexte
Antoine Rozenknop
21 octobre 2010
Algorithme Cock -Younger-Kasami Principes de l’algorithme CYK
Complexité pire cas
Algorithme de Earley Fondements
Interprétation
Un exemple très simple
Intérêt des CFG : existence d’algorithmes efficaces de production de dérivations/arbres d’analyse.
efficace — complexité pire cas O(n3)
Les deux algorithmes les plus usuels :
I algorithme CYK (Cocke-Younger-Kasami) (milieu des années 60)
I algorithme Earley (1970)
Algorithme Cock -Younger-Kasami Principes de l’algorithme CYK
Complexité pire cas
Algorithme de Earley Fondements
Interprétation
Un exemple très simple
L’algorithme CYK est un algorithme tabulaire ascendant présentant deux avantages :
I sa complexité pire cas est optimale (O(n3)) ;
I très simple à comprendre et implémenter
Il présente cependant deux inconvénients :
I Nécessite la mise de la CFG sous forme normale de Chomsky
I Reste O(n3) sur des grammaires de complexité inférieure (par ex. régulières)
CYK est un analyseur tabulaire (« chart-parser ») : calcul efficace (en espace et en temps) de toutes les interprétations possibles de toutes les sous-séquences de la séquence à analyser). L’efficacité du calcul est fondée sur la propriété suivante :
Si la grammaire est sous forme normale, le calcul des interprétations d’une séquence W de longueur l nécecessite seulement l’exploration de toutes les décompositions de W en deux sous-séquences exactement.
Le nombre de paires de sous-séquences à explorer est donc l ? 1.
Idée : mettre les analyses des sous-séquences dans une table.
L’analyse syntaxique d’une séquence de n mots W = w1 wn est représentée dans une table triangulaire de cellules Ci,l
(1 ? i ? n, 1 ? l ? n ? i + 1).
La cellule Ci,l contient tous les non-terminaux pouvant dériver la sous-séquence wi wi+l?1 (la séquence de l mots commençant au iemot de W).
Remplissage de bas en haut
On reconsidère la grammaire mise sous CNF :
Règles de la grammaire originale |
Grammaire sous forme normale |
||||||
R1 : |
S |
? |
SN SV |
R1.1 : |
S |
? |
SN SV |
R1.2 : |
S |
? |
SN V |
||||
R2 : |
SN |
? |
Det N |
R2 : |
SN |
? |
Det N |
R3 : |
SN |
? |
Det N SNP |
R3.1 : |
SN |
? |
X1 SNP |
R3.2 : |
X1 |
? |
Det N |
||||
R4 : |
SNP |
? |
Prep SN |
R4 : |
SNP |
? |
Prep SN |
R5 : |
SV |
? |
V |
||||
R6 : |
SV |
? |
V SN |
R6 : |
SV |
? |
V SN |
R7 : |
SV |
? |
V SN SNP |
R7.1 : |
SV |
? |
X2 SNP |
R7.2 : |
X2 |
? |
V SN |
pour tout 2 ? i ? n (ligne) faire pour tout 1 ? j ? n ? i + 1 (colonne) faire pour tout 1 ? k ? i ? 1 (décomposition) faire pour tout X ? C[i ? k][j] faire pour tout Y ? C[k][j + i ? k] faire pour tout Z ? X Y ?R faire Ajouter Z à C[i][j] |
Algorithme Cock -Younger-Kasami Principes de l’algorithme CYK
Complexité pire cas
Algorithme de Earley Fondements
Interprétation
Un exemple très simple
I Le calcul des interprétations d’une cellule Ci,j nécessite (i ? 1) explorations de paires de cellules (1 ? k ? i ? 1), le nombre total d’explorations est donc :
(i ? 1) = (n ? i + 1).(i ? 1) ? O(n3).
i=2 j=1 i=1
I Le calcul des interprétations d’une cellule Ci,j nécessite (i ? 1) explorations de paires de cellules (1 ? k ? i ? 1), le nombre total d’explorations est donc :
(i ? 1) = (n ? i + 1).(i ? 1) ? O(n3).
i=2 j=1 i=1
I Une cellule contient au plus |NT | interprétations (nombre de non-terminaux de la grammaire)
I Le calcul des interprétations d’une cellule Ci,j nécessite (i ? 1) explorations de paires de cellules (1 ? k ? i ? 1), le nombre total d’explorations est donc :
(i ? 1) = (n ? i + 1).(i ? 1) ? O(n3).
i=2 j=1 i=1
I Une cellule contient au plus |NT | interprétations (nombre de non-terminaux de la grammaire)
I le coût de l’exploration croisée d’une paire de cellules est d’au plus |NT |2 accès à la grammaire.
D’où la complexité :
O(n3|NT |2).
Inconvénient de la forme normale, qui augmente la taille de NT .
Remarque : une fois la table remplie, on peut extraire un arbre d’analyse en O(n).
Algorithme top-down (prédictif).
3 avantages :
I meilleure complexité pire cas connue (de même que CYK) ;
I s’adapte à des langages moins complexes (par ex. les langages réguliers) ;
I ne requière pas une forme particulière de grammaire (pas de CNF).
deux inconvénients :
I pas très intuitif ;
I pas moyen de corriger / reconstruire des phrases incorrectes syntaxiquement, ni d’en donner des analyses partielles.
Algorithme Cock -Younger-Kasami Principes de l’algorithme CYK
Complexité pire cas
Algorithme de Earley Fondements
Interprétation
Un exemple très simple
Règle pointée : Objet de la forme
X ? X1 Xk • Xk+1 Xm
où X ? X1 Xm est une règle de la grammaire.
Earley item : une règle pointée et un entier i (avec 0 ? i ? n, n :
taille de la phrase).
? représente la portion d’une règle compatible avec le segment de phrase commençant à la position i + 1.
Exemple : (SV ? V • SN, 2) et (SV ? V • SN SNP, 2) sont des items pour la chaîne initiale : le chat mangea la souris.
1 2 3 4 5
Principe de l’algorithme : Construction en parallèle de toutes les
règles pointées compatibles avec des sous-chaînes de plus en plus grandes de la phrase à analyser.
? construction d’ensembles d’items Ej tels que :
wi
? ? ?? wi+1 wj
Exemple : dans l’exemple précédent, (SV ? V • SN, 2) ? E3.
? une phrase est syntaxiquement correcte s’il existe au moins un
(S ? X1 Xm •, 0) dans En
? Initialisation : Construction de E0
1. Pour toute règle S ? X1 Xn :
ajouter (S ? • X1 Xn, 0) à E0.
2. Pour tous les items (X ? •Y ?, 0) dans E0, et pour toute règle Y ? ? :
ajouter (Y ? •?, 0) à E0.
3. Répéter (2) jusqu’à stabilisation de E0.
? Itérations : Construction des Ej (1 ? j ? n) :
1. Pour tout (X ? ? • wj?, i) ? Ej?1 : ajouter (X ? ? wj • ?, i) à Ej.
? Itérations : Construction des Ej (1 ? j ? n) :
1. Pour tout (X ? ? • wj?, i) ? Ej?1 : ajouter (X ? ? wj • ?, i) à Ej.
2. Pour tout (X ? ? •, i) de Ej et tout (Y ? ? • X?, k) de Ei : ajouter (Y ? ? X • ?, k) à Ej.
? Itérations : Construction des Ej (1 ? j ? n) :
1. Pour tout (X ? ? • wj?, i) ? Ej?1 : ajouter (X ? ? wj • ?, i) à Ej.
2. Pour tout (X ? ? •, i) de Ej et tout (Y ? ? • X?, k) de Ei : ajouter (Y ? ? X • ?, k) à Ej.
? Itérations : Construction des Ej (1 ? j ? n) :
1. Pour tout (X ? ? • wj?, i) ? Ej?1 : ajouter (X ? ? wj • ?, i) à Ej.
2. Pour tout (X ? ? •, i) de Ej et tout (Y ? ? • X?, k) de Ei : ajouter (Y ? ? X • ?, k) à Ej.
3. Pour tous les (X ? ? • Y ?, i) ? Ej et toute règle Y ? ? :
ajouter (Y ? •?, j) à Ej.
4. Répéter (2) et (3) jusqu’à stabilisation de Ej.Algorithme Cock -Younger-Kasami Principes de l’algorithme CYK
Complexité pire cas
Algorithme de Earley Fondements
Interprétation
Un exemple très simple
? Itérations : Construction des interprétations de w1 wn (Ej)
1. Ancrage vers les mots :
Introduire le mot wj si on a une interprétation de w1 wj?1 qui peut « consommer » wj (c.-à-d. « un • avant le symbole wj »)
2. Progression dans l’interprétation :
Si le non-terminal X a été produit depuis wi+1 et si on a une interprétation terminant en wi qui peut « consommer » X, alors le faire !
3. Prédiction (des choses utiles) :
Si on cherche à consommer Y pour la suite de l’analyse, alors introduire toutes les règles susceptibles de produire (plus tard) Y .
Algorithme Cock -Younger-Kasami Principes de l’algorithme CYK
Complexité pire cas
Algorithme de Earley Fondements
Interprétation
Un exemple très simple
analyse de la phrase « Je pense » avec la grammaire suivante :
S? SN SV |
Pron ? Je |
SN ? Pron SN ? Det N SV ? V SV ? V S SV ? V SN |
V ? pense |
E0
(S ?• SN SV, 0)
E0
(S ?• SN SV, 0)
(SN ?• Pron, 0)
E0
(S ?• SN SV, 0)
(SN ?• Pron, 0) (SN?• Det N, 0)
E0
(S ?• SN SV, 0)
(SN ?• Pron, 0) (SN?• Det N, 0)
E0
(S ?• SN SV, 0)
(SN ?• Pron, 0) (SN?• Det N, 0)
(Pron ?• Je, 0)
E1
(Pron ?Je •, 0)
E0
(S ?• SN SV, 0)
(SN ?• Pron, 0) (SN?• Det N, 0)
(Pron ?• Je, 0)
E1
(Pron ?Je •, 0)
(SN ?Pron •, 0)
E0
(S ?• SN SV, 0) |
|
(SN ?• Pron, 0) (Pron ?• Je, 0) E1 (Pron ?Je •, 0) |
(SN?• Det N, 0) |
(SN ?Pron •, 0) |
(S?SN• SV, 0) |
E0
(S ?• SN SV, 0) |
|
(SN ?• Pron, 0) (Pron ?• Je, 0) E1 (Pron ?Je •, 0) |
(SN?• Det N, 0) |
(SN ?Pron •, 0) (SV?• V, 1) |
(S?SN• SV, 0) |
E0
(S ?• SN SV, 0) |
|
(SN ?• Pron, 0) (Pron ?• Je, 0) E1 (Pron ?Je •, 0) |
(SN?• Det N, 0) |
(SN ?Pron •, 0) |
(S?SN• SV, 0) |
(SV?• V, 1) |
(SV?• V S, 1) |
E0
(S ?• SN SV, 0) |
|
(SN ?• Pron, 0) (Pron ?• Je, 0) E1 (Pron ?Je •, 0) |
(SN?• Det N, 0) |
(SN ?Pron •, 0) |
(S?SN• SV, 0) |
(SV?• V, 1) (SV?• V SN, 1) |
(SV?• V S, 1) |
E0
(S ?• SN SV, 0) |
|
(SN ?• Pron, 0) (Pron ?• Je, 0) E1 (Pron ?Je •, 0) |
(SN?• Det N, 0) |
(SN ?Pron •, 0) |
(S?SN• SV, 0) |
(SV?• V, 1) |
(SV?• V S, 1) |
(SV?• V SN, 1) |
(V?• pense, 1) |
E0
(S ?• SN SV, 0) |
|
(SN ?• Pron, 0) (Pron ?• Je, 0) E1 (Pron ?Je •, 0) |
(SN?• Det N, 0) |
(SN ?Pron •, 0) |
(S?SN• SV, 0) |
(SV?• V, 1) |
(SV?• V S, 1) |
(SV?• V SN, 1) |
(V?• pense, 1) |
E2
(V ?pense•, 1)
E0
(S ?• SN SV, 0) |
|
(SN ?• Pron, 0) (Pron ?• Je, 0) E1 (Pron ?Je •, 0) |
(SN?• Det N, 0) |
(SN ?Pron •, 0) |
|
(SV?• V, 1) |
(SV?• V S, 1) |
(SV?• V SN, 1) |
(V?• pense, 1) |
E2
(V ?pense•, 1)
(SV ?V •, 1)
E0
(S ?• SN SV, 0) |
|
(SN ?• Pron, 0) (Pron ?• Je, 0) E1 (Pron ?Je •, 0) |
(SN?• Det N, 0) |
(SN ?Pron •, 0) |
(S?SN• SV, 0) |
(SV?• V, 1) |
(SV?• V S, 1) |
(SV?• V SN, 1) E2 (V ?pense•, 1) |
(V?• pense, 1) |
(SV ?V •, 1) |
(SV ?V • S, 1) |
E0
(S ?• SN SV, 0) |
|
(SN ?• Pron, 0) (Pron ?• Je, 0) E1 (Pron ?Je •, 0) |
(SN?• Det N, 0) |
(SN ?Pron •, 0) |
(S?SN• SV, 0) |
(SV?• V, 1) |
(SV?• V S, 1) |
(SV?• V SN, 1) E2 (V ?pense•, 1) |
(V?• pense, 1) |
(SV ?V •, 1) (SV ?V • SN, 1) |
(SV ?V • S, 1) |
E0
(S ?• SN SV, 0) |
|
(SN ?• Pron, 0) (Pron ?• Je, 0) E1 (Pron ?Je •, 0) |
(SN?• Det N, 0) |
(SN ?Pron •, 0) |
(S?SN• SV, 0) |
(SV?• V, 1) |
(SV?• V S, 1) |
(SV?• V SN, 1) E2 (V ?pense•, 1) |
(V?• pense, 1) |
(SV ?V •, 1) |
(SV ?V • S, 1) |
(SV ?V • SN, 1) |
(S?SN SV •, 0) |
E0
(S ?• SN SV, 0) |
|
(SN ?• Pron, 0) (Pron ?• Je, 0) E1 (Pron ?Je •, 0) |
(SN?• Det N, 0) |
(SN ?Pron •, 0) |
(S?SN• SV, 0) |
(SV?• V, 1) |
(SV?• V S, 1) |
(SV?• V SN, 1) E2 (V ?pense•, 1) |
(V?• pense, 1) |
(SV ?V •, 1) |
(SV ?V • S, 1) |
(SV ?V • SN, 1) (S ?• SN SV, 2) |
(S?SN SV •, 0) |
E0
(S ?• SN SV, 0) |
|
(SN ?• Pron, 0) (Pron ?• Je, 0) E1 (Pron ?Je •, 0) |
(SN?• Det N, 0) |
(SN ?Pron •, 0) |
(S?SN• SV, 0) |
(SV?• V, 1) |
(SV?• V S, 1) |
(SV?• V SN, 1) E2 (V ?pense•, 1) |
(V?• pense, 1) |
(SV ?V •, 1) |
(SV ?V • S, 1) |
(SV ?V • SN, 1) |
|
(S ?• SN SV, 2) |
(SN ?• Pron, 2) |
E0
(S ?• SN SV, 0) |
|
(SN ?• Pron, 0) (Pron ?• Je, 0) E1 (Pron ?Je •, 0) |
(SN?• Det N, 0) |
(SN ?Pron •, 0) |
(S?SN• SV, 0) |
(SV?• V, 1) |
(SV?• V S, 1) |
(SV?• V SN, 1) E2 (V ?pense•, 1) |
(V?• pense, 1) |
(SV ?V •, 1) |
(SV ?V • S, 1) |
(SV ?V • SN, 1) |
(S?SN SV •, 0) |
(S ?• SN SV, 2) |
(SN ?• Pron, 2) |
E0
(S ?• SN SV, 0) |
|
(SN ?• Pron, 0) (Pron ?• Je, 0) E1 (Pron ?Je •, 0) |
(SN?• Det N, 0) |
(SN ?Pron •, 0) |
(S?SN• SV, 0) |
(SV?• V, 1) |
(SV?• V S, 1) |
(SV?• V SN, 1) E2 (V ?pense•, 1) |
(V?• pense, 1) |
(SV ?V •, 1) |
(SV ?V • S, 1) |
(SV ?V • SN, 1) |
(S?SN SV •, 0) |
(S ?• SN SV, 2) |
(SN ?• Pron, 2) (Pron ?• Je , 2) |
E0
(S ?• SN SV, 0) |
|
(SN ?• Pron, 0) (Pron ?• Je, 0) E1 (Pron ?Je •, 0) |
(SN?• Det N, 0) |
(SN ?Pron •, 0) |
(S?SN• SV, 0) |
(SV?• V, 1) |
(SV?• V S, 1) |
(SV?• V SN, 1) E2 (V ?pense•, 1) |
(V?• pense, 1) |
(SV ?V •, 1) |
(SV ?V • S, 1) |
(SV ?V • SN, 1) |
(S?SN SV •, 0) |
(S ?• SN SV, 2) |
(SN ?• Pron, 2) (Pron ?• Je , 2) |