Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.
Concept
Analyse Earley
Résumé
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. À 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)).
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.
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ù .
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 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 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 .
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.