Algorithmes d’analyse syntaxique

Modèles de Langage et Analyse Syntaxique

Cours 3 - Algorithmes d’analyse syntaxique - grammaires hors-contexte

Antoine Rozenknop

21 octobre 2010

Plan

Algorithme Cock -Younger-Kasami Principes de l’algorithme CYK

Complexité pire cas

Algorithme de Earley Fondements

Interprétation

Un exemple très simple

Analyse syntaxique

Intérêt des CFG : existence d’algorithmes efficaces de production de dérivations/arbres d’analyse.

efficace — complexité pire cas O(n³)

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

Algorithme CYK

L’algorithme CYK est un algorithme tabulaire ascendant présentant deux avantages :

^I sa complexité pire cas est optimale (O(n³)) ;

^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(n³) sur des grammaires de complexité inférieure (par ex. régulières)

Algorithme CYK : principes

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.

Algorithme CYK : principes (2)

L’analyse syntaxique d’une séquence de n mots W = w₁ w_n est représentée dans une table triangulaire de cellules C_i,l

(1 ? i ? n, 1 ? l ? n ? i + 1).

La cellule C_i,l contient tous les non-terminaux pouvant dériver la sous-séquence w_i w_i+l?₁ (la séquence de l mots commençant au i^emot 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

Algorithme formel

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 C_i,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(n³).

                                  i=2 j=1                           i=1

^I Le calcul des interprétations d’une cellule C_i,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(n³).

                                  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 C_i,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(n³).

                                  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 |² accès à la grammaire.

Complexité (2)

D’où la complexité :

O(n³|NT |²).

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 de Earley

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

Algorithme de Earley (2)

Idée : binarisation dynamique (en cours d’analyse) de la grammaire

Règle pointée : Objet de la forme

X ? X₁ X_k • X_k+₁ X_m

où X ? X₁ X_m 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

Algorithme de Earley (3)

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 E_j tels que :

w_i

? ? ?? wi+1 wj

Exemple : dans l’exemple précédent, (SV ? V • SN, 2) ? E₃.

? une phrase est syntaxiquement correcte s’il existe au moins un

(S ? X₁ X_m •, 0) dans E_n

Algorithme d’Earley (4)

? Initialisation : Construction de E₀

1.    Pour toute règle S ? X₁ X_n :

ajouter (S ? • X₁ X_n, 0) à E₀.

2.    Pour tous les items (X ? •Y ?, 0) dans E₀, et pour toute règle Y ? ? :

ajouter (Y ? •?, 0) à E₀.

3.    Répéter (2) jusqu’à stabilisation de E₀.

? Itérations : Construction des E_j (1 ? j ? n) :

1. Pour tout (X ? ? • w_j?, i) ? E_j?₁ : ajouter (X ? ? w_j • ?, i) à E_j.

? Itérations : Construction des E_j (1 ? j ? n) :

1.    Pour tout (X ? ? • w_j?, i) ? E_j?₁ : ajouter (X ? ? w_j • ?, i) à E_j.

2.    Pour tout (X ? ? •, i) de E_j et tout (Y ? ? • X?, k) de E_i : ajouter (Y ? ? X • ?, k) à E_j.

? Itérations : Construction des E_j (1 ? j ? n) :

1.    Pour tout (X ? ? • w_j?, i) ? E_j?₁ : ajouter (X ? ? w_j • ?, i) à E_j.

2.    Pour tout (X ? ? •, i) de E_j et tout (Y ? ? • X?, k) de E_i : ajouter (Y ? ? X • ?, k) à E_j.

3.    Pour tous les (X ? ? • Y ?, i) ? E_j et toute règle Y ? ? : ajouter (Y ? •?, j) à E_j.

? Itérations : Construction des E_j (1 ? j ? n) :

1.    Pour tout (X ? ? • w_j?, i) ? E_j?₁ : ajouter (X ? ? w_j • ?, i) à E_j.

2.    Pour tout (X ? ? •, i) de E_j et tout (Y ? ? • X?, k) de E_i : ajouter (Y ? ? X • ?, k) à E_j.

3.    Pour tous les (X ? ? • Y ?, i) ? E_j et toute règle Y ? ? :

ajouter (Y ? •?, j) à E_j.

4.    Répéter (2) et (3) jusqu’à stabilisation de E_j.Algorithme Cock -Younger-Kasami Principes de l’algorithme CYK

Complexité pire cas

Algorithme de Earley Fondements

Interprétation

Un exemple très simple

Algorithme d’Earley (Interprétation)

? Itérations : Construction des interprétations de w₁ w_n (E_j)

1.    Ancrage vers les mots :

Introduire le mot w_j si on a une interprétation de w₁ w_j?₁ qui peut « consommer » w_j (c.-à-d. « un • avant le symbole w_j »)

2.    Progression dans l’interprétation :

Si le non-terminal X a été produit depuis w_i+1 et si on a une interprétation terminant en w_i 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

Algorithme d’Earley (Exemple complet)

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

E₀

(S ?• SN SV, 0)

E₀

(S ?• SN SV, 0)

(SN ?• Pron, 0)

E₀

(S ?• SN SV, 0)

                                         (SN ?• Pron, 0)          (SN?• Det N, 0)

E₀

(S ?• SN SV, 0)

                                         (SN ?• Pron, 0)          (SN?• Det N, 0)

(Pron ?• Je, 0)

E₀

(S ?• SN SV, 0)

                                         (SN ?• Pron, 0)          (SN?• Det N, 0)

(Pron ?• Je, 0)

E₁

(Pron ?Je •, 0)

E₀

(S ?• SN SV, 0)

                                         (SN ?• Pron, 0)          (SN?• Det N, 0)

(Pron ?• Je, 0)

E₁

(Pron ?Je •, 0)

(SN ?Pron •, 0)

E₀

(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)

E₀

(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)

E₀

(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)

E₀

(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)

E₀

(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)

E₀

(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)

E₂

(V ?pense•, 1)

E₀

(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)

E₂

(V ?pense•, 1)

(SV ?V •, 1)

E₀

(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)

E₀

(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)

E₀

(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)

E₀

(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)

E₀

(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)

E₀

(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)

E₀

(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)

E₀

(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)