Analyse Earley

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

L'algorithme d'Earley est un algorithme d'analyse syntaxique non déterministe pour les grammaires non contextuelles. Il a été décrit pour la première fois par Jay Earley[1]. 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(n3), 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[2]). Pour une grammaire non ambiguë, l'analyse Earley s'effectue en temps quadratique (O(n2)).

L'algorithme d'Earley[modifier | modifier le code]

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[modifier | modifier le code]

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 première sous-partie déjà reconnue (la sous-chaîne a_i\ ...\ a_j) puis une seconde sous-partie qu'il faut encore reconnaître (la sous-chaîne a_{j+1}\ ...\ a_k). L'une ou l'autre de ces sous-parties peut être vide. Elles sont nécessairement vides toutes les deux si la partie droite de la règle est elle-même 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[3] 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[modifier | modifier le code]

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.

Notes et références[modifier | modifier le code]

  1. Jay Earley, An efficient context-free parsing algorithm, Communication of the ACM, 13(2), 1970
  2. Il en est ainsi dans l'analyseur Earley du système SYNTAX, utilisé dans l'analyseur syntaxique SxLFG pour le formalisme LFG, dont une première version est décrite dans cet article
  3. En toute rigueur, un tel item est valide si on peut dériver une proto-phrase a_1\ ...\ a_i\ A\ \gamma et une proto-phrase a_1\ ...\ a_i\ a_{i+1}... a_{j}\ \beta\ \gamma.