Analyse Earley

En théorie des langages, l'algorithme d'Earley est un algorithme d'analyse syntaxique pour les grammaires non contextuelles décrit pour la première fois par Jay Earley. À l'instar des algorithmes CYK et GLR, l'algorithme d'Earley calcule toutes les analyses possibles d'une phrase (et pas seulement une de ces analyses). Il repose sur de la programmation dynamique.

On peut construire un analyseur Earley pour toute grammaire non contextuelle. Il s'exécute en temps cubique (O (n³), où n est la longueur de la chaîne d'entrée). Pour une grammaire non ambiguë, l'analyse Earley s'effectue en temps quadratique (O (n²)).

L'algorithme d'Earley

Considérons une grammaire non contextuelle ainsi qu'une chaîne d'entrée de longueur $n$ notée $a_{1}\ ...\ a_{n}$. L'analyse par l'algorithme d'Earley a pour but de reconnaître la chaîne, donc de dire si la chaîne fait partie du langage engendré par la grammaire.

Items Earley et tables Earley

L'algorithme d'Earley manipule des items Earley, appelés plus simplement des items. Un item est la donnée :

• d'une règle de production de la grammaire notée $S\ \rightarrow \ \alpha$ ;
• un indice de début $i$ dans le mot d'entrée, tel que $0\leq i\leq n$;
• un indice de position dans la partie droite de la règle, que l'on représente par un point.

On représente un item sous la forme $(A\ \rightarrow \ \alpha \bullet \beta ,i)$, où $0\leq i\leq n$.

Principe de l'algorithme

On dispose d'une table $T$ de taille $n+1$ où on stocke des ensembles d'items d'Earley, où $n$ est la longueur de la chaîne d'entrée.

Le calcul démarre avec $T[0]$ contenant les items de la forme $(S\ \rightarrow \ \bullet \alpha ,0)$ où $S$ est l'axiome de la grammaire et $S\ \rightarrow \ \alpha$ est une règle de production. Un item $(S\ \rightarrow \ \bullet \alpha ,0)$ représente la situation où l'on n'a encore rien reconnu, mais où l'on cherche à reconnaître l'axiome à partir du début de la chaîne d'entrée. Puis on exécute l'étape 0, 1, ..., jusqu'à l'étape n.

L'objectif de l'étape $j$ est de calculer puis de stocker dans une table $T[j]$, l'ensemble des items $(A\ \rightarrow \ \alpha \bullet \beta ,i)$ tels que $a_{i}\ ...\ a_{j-1}$ est reconnu par $\alpha$.

À l'étape $j$, on calcule $T[j]$ à partir des tables $T[0],\dots ,T[j-1]$ en saturant dans l'ordre les trois opérations suivantes :

• Lecture (Scanner en anglais). L'opération de lecture s'effectue pour $j\geq 1$. Pour tout item de $T[j-1]$ de la forme $(A\ \rightarrow \ \alpha \bullet a_{j}\ \beta ,i)$ on ajoute dans $T[j]$ l'item $(A\ \rightarrow \ \alpha \ a_{j}\bullet \beta ,i)$. Autrement dit, on fait avancer les points dans les items de $T[j-1]$ s'il précède la lettre lue $a_{j}$.
• Prédiction (Predictor en anglais). Si un item de la forme $(A\ \rightarrow \ \alpha \ \bullet B\beta ,i)$ est dans $T[j]$ où $B$ est un non-terminal, alors pour toutes les règles $B\ \rightarrow \ \delta$, on ajoute l'item $(B\ \rightarrow \ \bullet \delta ,j)$ à l'ensemble $T[j]$. Autrement dit, s'il faut reconnaître, on teste toutes les règles où $B$ est en partie gauche.$a_{i}\ ...\ a_{j-1}$
• Complétion (Completor en anglais). Si un item de la forme $(A\ \rightarrow \ \alpha \ \bullet ,i)$ est dans $T[j]$, alors pour tous items de la table $T[i]$ de la forme $(C\ \rightarrow \ \delta \bullet \ A\ \gamma ,k)$, on ajoute $(C\ \rightarrow \ \delta \ A\ \bullet \gamma ,k)$ dans $T[j]$. Autrement dit, si $A$ a reconnu $a_{i}\ ...\ a_{j}$, on fait avancer les règles qui attendaient la reconnaissance de $A$.

L'analyse réussit si la table $T[n]$ contient un item de la forme $(S\ \rightarrow \ \alpha \bullet ,0)$, où $S\ \rightarrow \ \alpha$ est une production.

Exemple

Considérons la grammaire suivante des expressions arithmétiques :

$S\rightarrow E$ $E\rightarrow E+N$ $E\rightarrow E-N$ $E\rightarrow N$

$N\rightarrow N*F$ $N\rightarrow N/F$ $N\rightarrow F$

$F\rightarrow a$ $F\rightarrow -F$ $F\rightarrow +F$ $F\rightarrow (E)$

$S$ est l'axiome de la grammaire.

Analysons la chaîne d'entrée $a+a$. On obtient alors les tables suivantes.Nous y noterons "P:" une opération de prédiction ; "C:" une opération de complétion et "L:" une opération de lecture.

A l'étape 0, le calcul démarre avec $(S\rightarrow \bullet E,0)$. Puis on sature avec l'opération de prédiction.

$T[0]$
$S\rightarrow \bullet E$ $,\,0$ P: $E\rightarrow \bullet E+N$ $,\,0$ P: $E\rightarrow \bullet E-N$ $,\,0$ P: $E\rightarrow \bullet N$ $,\,0$ P: $N\rightarrow \bullet N*F$ $,\,0$ P: $N\rightarrow \bullet N/F$ $,\,0$ P: $N\rightarrow \bullet F$ $,\,0$ P: $F\rightarrow \bullet a$ $,\,0$ P: $F\rightarrow \bullet -F$ $,\,0$ P: $F\rightarrow \bullet +F$ $,\,0$ P: $F\rightarrow \bullet (E)$ $,\,0$

A l'étape 1, on obtient $\color {Red}(F\rightarrow a\bullet ,0)$ par l'opération de lecture. L'opération de prédiction ne produit rien car l'indice de position est à la fin de la partie droite. L'item $\color {Red}(F\rightarrow a\bullet ,0)$ est utilisé par l'opération de complétion pour obtenir $\color {Red}(N\rightarrow F\bullet ,0)$, puis $\color {Red}(E\rightarrow N\bullet ,0)$, etc. jusqu'à saturation de l'opération de complétion.

$T[1]$
L: $\color {Red}F\rightarrow a\bullet$ $\color {Red},\,0$ C: $\color {Red}N\rightarrow F\bullet$ $\color {Red},\,0$ C: $\color {Red}E\rightarrow N\bullet$ $\color {Red},\,0$ C: $N\rightarrow N\bullet *F$ $,\,0$ C: $N\rightarrow N\bullet /F$ $,\,0$ C: $\color {Red}S\rightarrow E\bullet$ $,\,0$ C: $E\rightarrow E\bullet +N$ $,\,0$ C: $E\rightarrow E\bullet -N$ $,\,0$

A l'étape 2, on obtient $(E\rightarrow E+\bullet N,0)$ par opération de lecture. Comme $N$ est juste après l'indice de position dans la première ligne de $T[2]$ , on rajoute toutes les règles $(N\rightarrow \alpha )$ en prédiction, avec l'indice 2 qui est l'indice de position courant.

$T[2]$
L: $E\rightarrow E+\bullet N$ $,\,0$ P: $N\rightarrow \bullet N*F$ $,\,2$ P: $N\rightarrow \bullet N/F$ $,\,2$ P: $N\rightarrow \bullet F$ $,\,2$ P: $F\rightarrow \bullet a$ $,\,2$ P: $F\rightarrow \bullet -F$ $,\,2$ P: $F\rightarrow \bullet +F$ $,\,2$ P: $F\rightarrow \bullet (E)$ $,\,2$

A l'étape 3, on lit $F$, donc on complète $(N\rightarrow \bullet F,2)$ de $T[2]$ en $(N\rightarrow F\bullet ,2)$. Ainsi il existe une règle $(N\rightarrow F\bullet ,2)$ donc la règle $(E\rightarrow E+\bullet N,0)$ se complète en $(E\rightarrow E+N\bullet ,0)$.

On sature par complétion.

$T[3]$
L: $\color {Red}F\rightarrow a\bullet$ $\color {Red},\,2$ C: $\color {Red}N\rightarrow F\bullet$ $\color {Red},\,2$ C: $\color {Red}E\rightarrow E+N\bullet$ $\color {Red},\,0$ C: $N\rightarrow N\bullet *F$ $,\,2$ C: $N\rightarrow N\bullet /F$ $,\,2$ C: $\color {Red}S\rightarrow E\bullet$ $\color {Red},\,0$ C: $E\rightarrow E\bullet +N$ $,\,0$ C: $E\rightarrow E\bullet -N$ $,\,0$

Comme $\color {Red}(S\rightarrow E\bullet ,0)$ est dans $T[3]$, le mot d'entrée est reconnu.

Complexité

Complexité en espace

Soit $I$ le nombre de d'items distincts à l'indice de début près. Celui-ci peut être majoré à l'aide de la taille de la grammaire: pour chaque élément dans la grammaire, l'indice de position peut avoir un nombre fini de place, et pour chacune de ces positions, on obtient un item différent. On obtient $I$ en comptant ces items. En pratique, cela revient revient à compter le nombre d'emplacements possibles du symbole $\bullet$ dans les règles de production de la grammaire. Dans l'exemple précédent on a donc $I=34$.

À la table $T[j]$, chacun des $I$ items peuvent apparaître avec un indice de début entre $0$ et $j$. Il y a donc au plus $I.(j+1)$ éléments dans la table $T[j].j$ est majoré par $n$ où $n$ est la taille du mot d'entrée. En sommant les $I.(j+1)$ pour $j$ allant de $0$ à $n$, on obtient $I.(n+1).(n+2)/2$éléments au plus dans les tables. La complexité en espace est donc en O(n²).

Complexité en temps (cas général)

Étudions la complexité des opérations lecture, prédiction et complétion sur le tableau $T[j]$:

La lecture analyse les éléments de $T[j-1]$ chacun en temps constant. Étant donné la taille de $T[j-1]$, l'opération de lecture se fait en $O(j)$. La prédiction opère sur chacun des éléments déjà présents en temps constant. À la suite de la lecture, le nombre d'éléments présents est en $O(j)$, donc la prédiction se fait en $O(j)$. La complétion opère sur chaque élément présent en un temps dépendant de la taille du tableau auquel son indice de début renvoie. On peut au pire cas se limiter à un seul parcours de chacun des tableaux précédents, ce qui donne une complexité en O(j²).

En sommant ces complexités sur les $n$ tableaux, on obtient une complexité en temps finale en O(n³).

Complexité en temps (grammaire non-ambiguë)

Ce qui mettait la complexité en O(n³) était l'action de complétion. Or, si la grammaire est non-ambiguë, il n'existe qu'un seul moyen d'obtenir chaque item, et la taille du tableau $T[j]$ après complétion est en $O(j)$. Donc chacun de ces éléments n'ont pu être obtenu qu'en un temps en $O(j)$. On obtient alors en sommant une complexité en temps en O(n²).

Variante

L'analyse Earley peut se faire avec un graphe orienté acyclique en entrée plutôt qu'une chaîne de caractères. Cela permet de mettre en entrée plusieurs mots de façon plus compacte, ainsi que de faire l'analyse sur plusieurs mots en même temps, la rendant donc plus efficace. Les indices des tables sont alors les indices correspondant au tri topologique du graphe. De plus, pour le nœud d'indice j, l'opération de lecture n'utilise plus $T[j-1]$ mais $T[k]$ où k est l'indice du nœud parent du nœud étudié.