Analyse 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 ${\displaystyle S\ \rightarrow \ \alpha }$ ;
• un indice de début ${\displaystyle i}$ dans le mot d'entrée, tel que ${\displaystyle 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 ${\displaystyle (A\ \rightarrow \ \alpha \bullet \beta ,i)}$, où ${\displaystyle 0\leq i\leq n}$.

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

Le calcul démarre avec ${\displaystyle T[0]}$ contenant les items de la forme ${\displaystyle (S\ \rightarrow \ \bullet \alpha ,0)}$ où ${\displaystyle S}$ est l'axiome de la grammaire et ${\displaystyle S\ \rightarrow \ \alpha }$ est une règle de production. Un item ${\displaystyle (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 ${\displaystyle j}$ est de calculer puis de stocker dans une table ${\displaystyle T[j]}$, l'ensemble des items ${\displaystyle (A\ \rightarrow \ \alpha \bullet \beta ,i)}$ tels que ${\displaystyle a_{i}\ ...\ a_{j}}$ est reconnu par ${\displaystyle \alpha }$.

À l'étape ${\displaystyle j}$, on calcule ${\displaystyle T[j]}$ à partir des tables ${\displaystyle 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 ${\displaystyle j\geq 1}$. Pour tout item de ${\displaystyle T[j-1]}$ de la forme ${\displaystyle (A\ \rightarrow \ \alpha \bullet a_{j}\ \beta ,i)}$ on ajoute dans ${\displaystyle T[j]}$ l'item ${\displaystyle (A\ \rightarrow \ \alpha \ a_{j}\bullet \beta ,i)}$. Autrement dit, on fait avancer les points dans les items de ${\displaystyle T[j-1]}$ s'il précède la lettre lue ${\displaystyle a_{j}}$.
• Prédiction (Predictor en anglais). Si un item de la forme ${\displaystyle (A\ \rightarrow \ \alpha \ \bullet B\beta ,i)}$ est dans ${\displaystyle T[j]}$ où ${\displaystyle B}$ est un non-terminal, alors pour toutes les règles ${\displaystyle B\ \rightarrow \ \delta }$, on ajoute l'item ${\displaystyle (B\ \rightarrow \ \bullet \delta ,j)}$ à l'ensemble ${\displaystyle T[j]}$. Autrement dit, s'il faut reconnaître, on teste toutes les règles où ${\displaystyle B}$ est en partie gauche.
• Complétion (Completor en anglais). Si un item de la forme ${\displaystyle (A\ \rightarrow \ \alpha \ \bullet ,i)}$ est dans ${\displaystyle T[j]}$, alors pour tous items de la table ${\displaystyle T[i]}$ de la forme ${\displaystyle (C\ \rightarrow \ \delta \bullet \ A\ \gamma ,k)}$, on ajoute ${\displaystyle (C\ \rightarrow \ \delta \ A\ \bullet \gamma ,k)}$ dans ${\displaystyle T[j]}$. Autrement dit, si ${\displaystyle A}$ a reconnu ${\displaystyle a_{i}\ ...\ a_{j}}$, on fait avancer les règles qui attendait la reconnaissance de ${\displaystyle A}$.

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

Soit ${\displaystyle 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 ${\displaystyle I}$ en comptant ces items. En pratique, cela revient revient à compter le nombre d'emplacements possibles du symbole ${\displaystyle \bullet }$ dans les règles de production de la grammaire. Dans l'exemple précédent on a donc ${\displaystyle I=34}$.

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

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

La lecture analyse les éléments de ${\displaystyle T[j-1]}$ chacun en temps constant. Étant donné la taille de ${\displaystyle T[j-1]}$, l'opération de lecture se fait en ${\displaystyle 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 ${\displaystyle O(j)}$, donc la prédiction se fait en ${\displaystyle 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 ${\displaystyle n}$ tableaux, on obtient une complexité en temps finale en O(n³).

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 ${\displaystyle T[j]}$ après complétion est en ${\displaystyle O(j)}$. Donc chacun de ces éléments n'ont pu être obtenu qu'en un temps en ${\displaystyle O(j)}$. On obtient alors en sommant une complexité en temps en O(n²).