Analyse Earley

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

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[1]. A 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(n3), 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(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 notée . 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[modifier | modifier le code]

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  ;
  • un indice de début dans le mot d'entrée, tel que ;
  • 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 , où .

Principe de l'algorithme[modifier | modifier le code]

On dispose d'une table de taille où on stocke des ensembles d'items d'earley. Où est la longueur de la chaîne d'entrée .

À l'étape , le calcul démarre avec les items de la forme en , où est l'axiome de la grammaire et est une règle de production. Un item 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 applique la même procédure que pour toutes les autres étape .

A l'étape , on calcule, puis stocke dans une table , l'ensemble des items tels que est reconnu par .

À l'étape , on calcule à partir des tables en saturant dans l'ordre les trois opérations suivantes ː

  • Lecture (Scanner en anglais). L'opération de lecture s'effectue pour . Pour tout item de de la forme on ajoute dans l'item . Autrement dit, on fait avancer les points dans les items de s'il précède la lettre lue .
  • Prédiction (Predictor en anglais). Si un item de la forme est dans est un non-terminal, alors pour toutes les règles , on ajoute l'item à l'ensemble . Autrement dit, s'il faut reconnaître, on teste toutes les règles où est en partie gauche.
  • Complétion (Completor en anglais). Si un item de la forme est dans , alors pour tous items de la table de la forme , on ajoute dans . Autrement dit, si a reconnu , on fait avancer les règles qui attendait la reconnaissance de .

L'analyse réussit si on obtient une table qui contient un item de la forme , où est une production.

Exemple[modifier | modifier le code]

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

est l'axiome de la grammaire.

Analysons la chaîne d'entrée . 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 . Puis on sature avec l'opération de prédiction.

P:
P:
P:
P:
P:
P:
P:
P:
P:
P:

A l'étape 1, on obtient 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 est utilisé par l'opération de complétion pour obtenir , puis , etc. jusqu'à saturation de l'opération de complétion.

L:
C:
C:
C:
C:
C:
C:
C:

Puis on obtient par opération de lecture. Comme est juste après l'indice de position dans la première ligne de , on rajoute toutes les règles en prédiction , avec l'indice 2 qui est l'indice de position courant

L:
P:
P:
P:
P:
P:
P:
P:

Puis on lit , donc on complète de en . Ainsi il existe une règle donc la règle se complète en .

On sature par complétion.

L:
C:
C:
C:
C:
C:
C:
C:

Comme est dans , le mot d'entrée est reconnu.

Complexité[2],[3][modifier | modifier le code]

Complexité en espace[modifier | modifier le code]

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

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

Complexité en temps (cas général)[modifier | modifier le code]

Étudions la complexité des opérations lecture, prédiction et complétion sur le tableau :

La lecture analyse les éléments de chacun en temps constant. Étant donné la taille de , l'opération de lecture se fait en . La prédiction opère sur chacun des éléments déjà présents en temps constant. Suite à la lecture, le nombre d'éléments présents est en , donc la prédiction se fait en . 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 tableaux, on obtient une complexité en temps finale en O(n3).

Complexité en temps (grammaire non-ambiguë)[modifier | modifier le code]

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

Variante[modifier | modifier le code]

L'analyse Earley peut se faire avec un graphe orienté acyclique en entrée[4] 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 mais où k est l'indice du nœud parent du nœud étudié.

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. « Parsing Techniques - A Practical Guide - Dick Grune »
  3. « An Efficient Context-Free Parsing Algorithm - Carnegie Mellon University »
  4. 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