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)). 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 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 L'algorithme d'Earley ma
À 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.
Publications associées

Chargement

Personnes associées

Chargement

Unités associées

Chargement

Concepts associés

Chargement

Cours associés

Chargement

Séances de cours associées

Chargement