Analyse Earley

L'algorithme d'Earley est un algorithme non déterministe d'analyse syntaxique pour les grammaires non contextuelles. Il a été décrit pour la première fois par Jay Earley. Il se range, aux côtés des algorithmes CYK et GLR, parmi les algorithmes qui font usage de la notion de partage (de calculs et de structures) et qui construisent toutes les analyses possibles d'une phrase (et pas seulement une de ces analyses). Ce sont donc des algorithmes non-déterministes qui font usage d'idées venues du domaine 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, voire la taille du DAG d'entrée, l'algorithme pouvant aisément s'étendre à l'analyse de DAG). 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 consiste à parcourir la chaîne linéairement, tant que c'est possible, et à faire toutes sortes de calculs entre chaque mot de cette chaîne. Il se déroule donc en $n+1$ étapes, numérotées de 0 (étape d'initialisation) à $n$ (étape finale). L'analyse réussit si on a réussi à atteindre la $n$-ième étape, et si le résultat des calculs que l'on y fait est positif.

Items Earley et tables Earley

L'algorithme d'Earley fait usage de ce que l'on appelle des items Earley, ou plus simplement des items. Un item est entièrement défini par une production de la grammaire, un entier $i$, appelé indice de début, tel que $0\le i\le n$, et un identifiant 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 $[i]\ A\ \rightarrow\ \alpha \bullet \beta$, où $0\le i\le n$. Un item privé de son indice de début (c'est-à-dire une production munie d'un identifiant de position dans sa partie droite) est appelé une production pointée. Une production pointée est donc de la forme $A\ \rightarrow\ \alpha \bullet \beta$.

Supposons que l'on soit à la $j$-ième étape (et donc à la position $j$ de la chaîne d'entrée). Un item est dit $j$-valide (ou valide s'il n'y a pas d'ambiguïté) s'il représente une production dont on est en train d'essayer de faire dériver une sous-chaîne $a_i\ ...\ a_k$ ($0\le i\le j \le k\le n$) de la chaîne d'entrée. Puisque l'on a vu que l'on avance de gauche à droite progressivement, une telle production a sa partie droite partagée entre une partie déjà reconnue (la sous-chaîne $a_i\ ...\ a_j$) puis une partie qu'il faut encore reconnaître (la sous-chaîne $a_{j+1}\ ...\ a_k$). L'une ou l'autre de ces parties peut être vide, voire les deux si la partie droite de la règle est vide.

On définit la table $T[j]$ comme l'ensemble des items $j$-valides. Un item de la table $T[j]$ est donc valide s'il représente une situation où l'on est à la $j$-ième étape (on a reconnu les $j$ premiers symboles de la chaîne d'entrée, c'est-à-dire le préfixe $a_1\ ...\ a_j$), et où l'on est en train d'essayer de construire un non-terminal $A$ couvrant une sous-chaîne commençant par $a_{i+1}$ à l'aide de la règle $A\ \rightarrow\ \alpha\ \beta$. Le point symbolise donc la position courante dans la règle, qui correspond à la position courante dans la chaîne d'entrée, à savoir $j$. Si $\alpha$ est vide (l'item est de la forme $[i]\ A\ \rightarrow\ \bullet \beta$), c'est que l'on n'a encore rien reconnu: la reconnaissance de $A$ à partir de la position $i$ n'a pas encore commencé). Si $\beta$ est vide (l'item est de la forme $[i]\ A\ \rightarrow\ \alpha \bullet$), c'est que la reconnaissance est un succès: on a réussi à construire un non-terminal $A$ couvrant la sous-chaîne $a_i\ ...\ a_j$.

Supposons que $S$ soit l'axiome de la grammaire. Les items de la forme $[0]\ S\ \rightarrow\ \bullet \alpha$, où $S\ \rightarrow\ \alpha$ est une production, sont valides, et forment la table $T[0]$: ils représentent la situation (étape 0) 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. Une analyse Earley réussit si on réussit à construire, à partir de ces items de départ, un item $n$-valide de la forme $[0] S \ \rightarrow\ \alpha \bullet$, où $S\ \rightarrow\ \alpha$ est une production.

Algorithme d'analyse

Le but de l'algorithme est donc de calculer en $n+1$ étapes tous les items valides et seulement les items valides. La $j$-ième étape va donc être chargée de construire la table $T[j]$ en construisant tous les items $j$-valides, et seulement ceux-ci.

Chacune des étapes exécute trois types d'opérations, nommées Lecture, Prédiction et Complétion (en anglais, respectivement Scanner, Predictor, Completor). À l'exception de l'étape 0, qui commence par la construction des items de départ comme dit ci-dessus (construction de la table $T[0]$), la $j$-ième étape commence par les opérations de Lecture. Le but de ces opérations est de faire avancer les points dans les items de la table précédente où le point est juste avant un terminal qui est précisément $a_j$. Autrement dit, pour tout item de $T[j-1]$ de la forme $[i]\ A\ \rightarrow\ \alpha \bullet a_j\ \beta$ on ajoute dans $T[j]$ l'item $[i]\ A\ \rightarrow\ \alpha\ a_j \bullet \beta$. S'il n'y a pas d'item de cette forme, l'analyse échoue. Les items créés par cette phase de Lecture sont appelés items noyau. La construction du non-terminal $A$ correspondant a donc avancé d'un terminal. Dans une règle donnée, cette avancée peut avoir trois conséquences:

• Soit $\beta$ commence par un terminal, et la phase Lecture de l'étape $j+1$ s'en occupera plus tard. On ne fait donc rien pour le moment.
• Soit $\beta$ commence par un non terminal $B$. Dans ce cas, il faut lancer (prédire) la reconnaissance du non-terminal $B$ à partir de la position courante $j$. On rajoute donc dans $T[j]$, pour toutes les règles $B\ \rightarrow\ \delta$ ayant $B$ en partie gauche, un item $[j]\ B\ \rightarrow\ \bullet \delta$. L'ajout d'un tel item est une opération dite de Prédiction.
• Soit $\beta$ est vide. On a donc terminé et réussi la reconnaissance de $A$ entre les positions $i$ et $j$. On va donc chercher tous les items qui avaient lancé la reconnaissance de $A$ à partir de la position $i$, c'est-à-dire les items de la table $T[i]$ de la forme $[k]\ C\ \rightarrow\ \delta \bullet\ A\ \gamma$, et on va ajouter dans $T[j]$ pour chacun d'entre eux l'item $[k]\ C\ \rightarrow\ \delta\ A\ \bullet \gamma$ qui prend acte de ce que l'on a reconnu $A$ entre $i$ et $j$. L'ajout d'un tel item est une opération dite de Complétion.

L'exécution d'une Prédiction ou d'une Complétion ajoute un item dans la table courante (la table $T[j]$). Ce nouvel item peut lui-même permettre de nouvelles Prédictions et de nouvelles Complétions. Celles-ci sont exécutées, et ainsi de suite jusqu'à ce que la table courante soit stable (et donc complète). Toutes ces opérations peuvent avoir pour effet de faire avancer le point dans des règles, si les non-terminaux que l'on franchit peuvent dériver dans le vide. Mais elles ne font pas avancer le point dans la chaîne d'entrée: on reste à la position $j$, et on ne remplit que la table $T[j]$.

On peut se convaincre facilement (quitte à lire une preuve dans la littérature) que l'on ne construit ainsi que des items valides destinés à la table $T[j]$, et qu'on les construit tous.

Une fois que l'on ne peut plus construire de nouvel item pour la table $T[j]$, on passe à l'étape $j+1$. L'analyse réussit si on arrive de cette façon à exécuter les $n$ étapes et si on obtient une table $T[n]$ comprenant des items de la forme $[0] S\ \rightarrow\ \alpha \bullet$, où $S\ \rightarrow\ \alpha$ est une production.