Algoritmo Earley

O algoritmo de análise gramatical Earley é um tipo de programa que subdivide uma entrada (input) para que um outro possa atuar sobre ela mais comumente usado em linguística computacional, nomeado após seu inventor, . O algoritmo faz uso de programação dinâmica. Os analisadores gramaticais Earley são interessantes porque podem analisar todas as linguagens livre de contexto. O algoritmo Earley tem tempo de execução O(n³) (onde n é o comprimento da cadeia de caracteres analisada), no caso geral, tempo quadrático (O(n²)) para gramáticas não ambígua, e tempo linear para quase toda as gramáticas LR(k)?. Seu desempenho é relativamente bom quando as regras são escritas de forma recursiva.