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[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)).

Sommaire

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[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 ai + 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 α 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 β 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 aj. 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 β 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 β 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 β 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 de l'article

  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.


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Analyse Earley de Wikipédia en français (auteurs)

Regardez d'autres dictionnaires:

  • Analyse Syntaxique — Pour les articles homonymes, voir Analyseur. L analyse syntaxique consiste à mettre en évidence la structure d un texte, généralement un programme informatique ou du texte écrit dans une langue naturelle. Un analyseur syntaxique (parser, en… …   Wikipédia en Français

  • Analyse syntaxique — Pour les articles homonymes, voir Analyseur. L analyse syntaxique consiste à mettre en évidence la structure d un texte, généralement un programme informatique ou du texte écrit dans une langue naturelle. Un analyseur syntaxique (parser, en… …   Wikipédia en Français

  • Jay Earley — est un informaticien et psychologue américain. Il est l auteur de l algorithme dit algorithme d Earley, qui permet d effectuer l analyse syntaxique à l aide de grammaires non contextuelles quelconques (y compris les grammaires non contextuelles… …   Wikipédia en Français

  • Analyseur syntaxique — Analyse syntaxique Pour les articles homonymes, voir Analyseur. L analyse syntaxique consiste à mettre en évidence la structure d un texte, généralement un programme informatique ou du texte écrit dans une langue naturelle. Un analyseur… …   Wikipédia en Français

  • Parser — Analyse syntaxique Pour les articles homonymes, voir Analyseur. L analyse syntaxique consiste à mettre en évidence la structure d un texte, généralement un programme informatique ou du texte écrit dans une langue naturelle. Un analyseur… …   Wikipédia en Français

  • Parseur — Analyse syntaxique Pour les articles homonymes, voir Analyseur. L analyse syntaxique consiste à mettre en évidence la structure d un texte, généralement un programme informatique ou du texte écrit dans une langue naturelle. Un analyseur… …   Wikipédia en Français

  • Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… …   Wikipédia en Français

  • Liste des articles de mathematiques — Projet:Mathématiques/Liste des articles de mathématiques Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou probabilités et statistiques via l un des trois bandeaux suivants  …   Wikipédia en Français

  • Grammaire Indépendante du Contexte — Grammaire non contextuelle En linguistique et en informatique, une grammaire non contextuelle, grammaire hors contexte ou grammaire algébrique (type 2 dans la hiérarchie de Chomsky) est une grammaire formelle dans laquelle chaque règle de… …   Wikipédia en Français

  • Grammaire Non Contextuelle — En linguistique et en informatique, une grammaire non contextuelle, grammaire hors contexte ou grammaire algébrique (type 2 dans la hiérarchie de Chomsky) est une grammaire formelle dans laquelle chaque règle de production (ou simplement… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”