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]. À 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

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

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

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.

Le calcul démarre avec   contenant les items de la forme    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 exécute l'étape 0, 1, ..., jusqu'à l'étape n.

L'objectif de l'étape   est de calculer puis de stocker 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 attendaient la reconnaissance de  .

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

Exemple

modifier

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:    

A l'étape 2, 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:    

A l'étape 3, 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

Complexité en espace

modifier

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

É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. À la suite de 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

Ce qui mettait la complexité en O(n3) é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   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

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
  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