Algorytm Earleya

Algorytm Earleya – algorytm służący do analizy składniowej na podstawie dowolnej gramatyki bezkontekstowej. Stosuje się go między innymi do przetwarzania języków naturalnych, gdyż inaczej niż większość algorytmów analizy składniowej działa również z gramatykami niejednoznacznymi. Korzysta się też z niego przy tworzeniu interpreterów i kompilatorów języków programowania, zwłaszcza języków specjalizowanych, ponieważ szkielety projektowe oparte na tym algorytmie ułatwiają szybkie tworzenie prototypów (RAD). Górne ograniczenie czasu analizy n symboli terminalnych przez parser oparty na tym algorytmie rośnie proporcjonalnie do n3 w ogólnym przypadku, do n2 dla gramatyk jednoznacznych i do n dla sporej klasy gramatyk bezkontekstowych, w tym większości gramatyk języków programowania. Algorytm ten opracował w 1968 roku Jay Earley z Carnegie Mellon University w swojej pracy doktorskiej promowanej przez Roberta W. Floyda. W 1970 roku Earley opublikował go w Communications of the ACM w artykule, który w 1983 roku zaliczono do 21 najbardziej znaczących publikacji w ćwierćwieczu istnienia tego czasopisma.