Développement : Algorithme d'Earley

Détails/Enoncé :

L'algorithme d'Earley sert à vérifier si un mot $w$ appartient au langage d'une grammaire $G$. Il le fait en temps $O(\lvert w\rvert^3)$, comme l'algorithme CYK, mais on peut de plus prouver que la complexité n'est que de l'ordre de $O(\lvert w\rvert^2)$ dans le cas d'une grammaire non ambigüe, et même linéaire si la gramaire est rationnelle, ce qui en fait un des meilleurs algorithmes connus en pratique !

Recasages pour l'année 2024 :

  • Pas de recasages pour cette année.

Versions :

Références utilisées dans les versions de ce développement :

Le Langage des machines, Floyd, Beigel (utilisée dans 7 versions au total)