Algorithme d'Earley

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 !