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.
Zasada działania Algorytm Earleya należy, podobnie jak algorytm CYK, do klasy tablicowych metod analizy składniowej (ang. chart parsers). Stosuje się w nim wstępującą analizę składniową z lewa na prawo na podstawie zstępujących przewidywań. Wyniki algorytmu powstają na podstawie wcześniejszych wyników częściowych, zgodnie z techniką programowania dynamicznego.
Analiza składniowa z zastosowaniem tego algorytmu operuje na zbiorze sytuacji Earleya (ang. Earley items) lub krótko sytuacji, czyli produkcji gramatyki z dodaną kropką i dwoma indeksami. Podczas działania algorytmu sytuacje Earleya odzwierciedlają dotychczas zastosowane produkcje oraz służą do przewidywania kolejnych produkcji. Po przeanalizowaniu poprawnego ciągu wejściowego powinna powstać sytuacja, która odzwierciedla jego wyprowadzenie z symbolu startowego gramatyki.
Sytuacje Earleya mają postać [A →h X0 … Xp−1 •i Xp … Xq−1], gdzie produkcja A → X0 … Xq−1 należy do zbioru produkcji danej gramatyki. Indeksy przy strzałce →h i kropce •i spełniają nierówności 0 ≤ h ≤ i ≤ n (jeśli symbole terminalne ponumerować od t0 do tn−1), a kropka może leżeć gdziekolwiek pomiędzy początkiem a końcem prawej strony produkcji A → X0 … Xq−1 włącznie, czyli 0 ≤ p ≤ q. Indeks h określa pierwszy symbol terminalny wchodzący do drzewa rozbioru danej produkcji, indeks i – pierwszy nierozpatrzony jeszcze symbol terminalny, a położenie kropki oznacza postęp analizy danej produkcji. Ujmując rzecz formalnie, sytuacja Earleya [A →h X0 … Xp−1 •i Xp … Xq−1] oznacza, że algorytm przeanalizował podciąg t0 … ti−1 jako część formy zdaniowej t0 … th−1X0 … Xq−1α do symbolu Xp−1 włącznie (małe litery greckie α, β, γ, ... oznaczają dowolne, także puste ciągi symboli terminalnych lub nieterminalnych).
Na początku działania algorytmu zbiór sytuacji zawiera jeden element [S’ →0 •0 S], gdzie S oznacza właściwy symbol startowy danej gramatyki, a S’ – pomocniczy symbol startowy spoza zbioru symboli gramatyki. Następnie dopóty, dopóki ten zbiór rośnie, algorytm dodaje do niego nowe sytuacje na podstawie wejściowych symboli terminalnych i sytuacji już należących do zbioru. Jeżeli nowo utworzona sytuacja już należy do tego zbioru, nie zmienia się go. Do powstawania nowych sytuacji prowadzą trzy rodzaje działań: wczytywanie (ang. scanning) oznacza zaakceptowanie przez algorytm symbolu terminalnego zgodnego z oczekiwaniami analizatora zstępującego: jeśli istnieje sytuacja [A →h α •i tiη], w której bezpośrednio za kropką występuje bieżący symbol terminalny, to dodaj do zbioru sytuację [A →h αti •i+1 η] z kropką przesuniętą za ten symbol i indeksem nierozpatrzonego symbolu terminalnego zwiększonym o 1;
przewidywanie (ang. prediction) tworzy sytuacje, odpowiadające dalszym oczekiwaniom analizatora zstępującego: jeśli istnieje sytuacja [A →h α •i Bη], w której bezpośrednio za kropką występuje symbol nieterminalny B, to dla każdej produkcji B → β dodaj do zbioru sytuację [B →i •i β], która przygotowuje algorytm na ewentualne rozpoznanie tej produkcji poczynając od najbliższego nierozpatrzonego symbolu terminalnego;
uzupełnianie (ang. completion) stanowi wstępujący komponent algorytmu: jeśli istnieje sytuacja [A →h α •i], czyli rozpoznano całą produkcję A → α, to dla każdej sytuacji [B →g β •h Aγ], w której oczekiwano symbolu nieterminalnego A tam, gdzie zaczyna się rozpoznana produkcja A → α, dodaj do zbioru sytuację [B →g βA •i γ] z kropką przesuniętą za symbol A i uaktualnionym indeksem nierozpatrzonego symbolu terminalnego.
Wyprowadzenie wejściowego ciągu symboli terminalnych t0, … , tn−1 z symbolu startowego danej gramatyki istnieje wtedy i tylko wtedy, gdy algorytm utworzył sytuację Earleya [S’ →0 S •n].
Przykład Dla „pikogramatyki” języka angielskiego S → NP VP NP → Det N NP → Det Adj N VP → V VP → V NP
i wejściowego ciągu symboli TheDet blackAdj catN ateV aDet whiteAdj mouseN algorytm tworzy następujący zbiór sytuacji Earleya:
thumb|Drzewo rozbioru zdania the black cat ate a white mouse
thumb|Drzewo rozbioru zdania the black cat ate
{| class="wikitable" |- style="background: #efefef;" ! Sytuacja Earleya ! Powód dodania do zbioru sytuacji |- | [S’ →0 •0 S] | inicjalizacja |- | [S →0 •0 NP VP] | przewidziano S w sytuacji [S’ →0 •0 S] |- | [NP →0 •0 Det N] | przewidziano NP w sytuacji [S →0 •0 NP VP] |- | [NP →0 •0 Det Adj N] | przewidziano NP w sytuacji [S →0 •0 NP VP] |- | [NP →0 Det •1 N] | wczytano Det w sytuacji [NP →0 •0 Det N] |- | [NP →0 Det •1 Adj N] | wczytano Det w sytuacji [NP →0 •0 Det Adj N] |- | [NP →0 Det Adj •2 N] | wczytano Adj w sytuacji [NP →0 Det •1 Adj N] |- | [NP →0 Det Adj N •3] | wczytano N w sytuacji [NP →0 Det Adj •2 N] |- | [S →0 NP •3 VP] | uzupełniono NP w sytuacji [S →0 •0 NP VP] |- | [VP →3 •3 V] | przewidziano VP w sytuacji [S →0 NP •3 VP] |- | [VP →3 •3 V NP] | przewidziano VP w sytuacji [S →0 NP •3 VP] |- | [VP →3 V •4] | wczytano V w sytuacji [VP →3 •3 V] |- | [VP →3 V •4 NP] | wczytano V w sytuacji [VP →3 •3 V NP] |- | [S →0 NP VP •4] | uzupełniono VP w sytuacji [S →0 NP •3 VP] |- | [NP →4 •4 Det N] | przewidziano NP w sytuacji [VP →3 V •4 NP] |- | [NP →4 •4 Det Adj N] | przewidziano NP w sytuacji [VP →3 V •4 NP] |- | [S’ →0 S •4] | uzupełniono S w sytuacji [S’ →0 •0 S] |- | [NP →4 Det •5 N] | wczytano Det w sytuacji [NP →4 •4 Det N] |- | [NP →4 Det •5 Adj N] | wczytano Det w sytuacji [NP →4 •4 Det Adj N] |- | [NP →4 Det Adj •6 N] | wczytano Adj w sytuacji [NP →4 Det •5 Adj N] |- | [NP →4 Det Adj N •7] | wczytano N w sytuacji [NP →4 Det Adj •6 N] |- | [VP →3 V NP •7] | uzupełniono NP w sytuacji [VP →3 V •4 NP] |- | [S →0 NP VP •7] | uzupełniono VP w sytuacji [S →0 NP •3 VP] |- | [S’ →0 S •7] | uzupełniono S w sytuacji [S’ →0 •0 S]
Ostatnia sytuacja Earleya [S’ →0 S •7] odpowiada pełnemu rozbiorowi wszystkich siedmiu symboli ciągu wejściowego. Sytuacja Earleya [S’ →0 S •4] oznacza, że pierwsze cztery symbole tego ciągu również tworzą poprawne zdanie w danej gramatyce.
Złożoność obliczeniowa W implementacjach algorytmu Earleya zamiast jednego zbioru sytuacji korzysta się z listy zbiorów i pomija wewnątrz sytuacji indeks nierozpatrzonego symbolu wejściowego. W i-tym zbiorze przechowuje się sytuacje postaci [A →h α • η]. Spotyka się też notację [A → α • η, h] i inne. Algorytm przegląda wówczas po kolei zbiory z tej listy, dzięki czemu przyrostowo bada symbole wejściowe ti w kolejności rosnących indeksów i.
Wewnątrz zbiorów sytuacje Earleya przegląda się zazwyczaj w kolejności ich dodawania, każdą jeden raz. Wymaga to jednak modyfikacji algorytmu, jeśli ma on poprawnie działać dla gramatyk zawierających produkcje z pustą prawą stroną, o czym poniżej. Aby wydajnie przeglądać sytuacje jednego zbioru, powinny one tworzyć kolejkę, aby zaś przy próbie dodania sytuacji do kolejki wydajnie sprawdzać, czy kolejka już ją zawiera, sytuacje z każdej kolejki powinny dodatkowo należeć do tablicy asocjacyjnej. Wydajne uzupełnianie sytuacji, w których kropka nie leży na końcu produkcji, wymaga jeszcze jednej tablicy asocjacyjnej, przechowującej jako wartości listy takich sytuacji, a jako klucze – pary (Ap, i), złożone z symbolu leżącego w tych sytuacjach bezpośrednio za kropką i z indeksu nierozpatrzonego symbolu terminalnego. Ponadto, by wydajnie przewidywać nowe sytuacje, z każdym symbolem nieterminalnym powinno się związać listę wszystkich produkcji, po których lewej stronie stoi ten symbol.
Jeśli jako wymienione powyżej tablice asocjacyjne zastosować tablice mieszające, to krok polegający na tworzeniu nowej sytuacji Earleya i próbie poszerzenia o nią zbioru sytuacji można wykonać w oczekiwanym czasie O(1).
Earley wskazał w swoim artykule, że w ogólnym przypadku: i-ty zbiór liczy O(i) sytuacji, bo ograniczenie górne ich liczby równa się iloczynowi liczby możliwych wartości indeksu h (zależnej od i) oraz liczby produkcji i liczby możliwych położeń kropek w ich prawych stronach (dwa ostatnie czynniki nie przekraczają stałych zależnych od danej gramatyki, ale niezależnych od i); działania wczytywania i przewidywania wykonują O(1) kroków na sytuację Earleya w dowolnym zbiorze, zatem w i-tym zbiorze sytuacji wykonują O(i) kroków; działanie uzupełniania wykonuje O(i) kroków na każdą przetwarzaną sytuację, bo w najgorszym przypadku musi dodać O(h) sytuacji należących do h-tego zbioru, a h = O(i), zatem w i-tym zbiorze sytuacji wykonuje O(i2) kroków; sumowanie od i równego 0 do n daje O(n3) kroków działania algorytmu i O(n2) sytuacji.
W tym samym artykule wykazano również, że dla gramatyk jednoznacznych działanie uzupełniania wykonuje w i-tym zbiorze sytuacji O(i) kroków, co owocuje kwadratową złożonością algorytmu, oraz że klasa gramatyk, dla których algorytm Earleya działa w czasie liniowym, obejmuje gramatyki, dla których liczbę sytuacji w każdym zbiorze ogranicza z góry pewna stała. Do tej klasy należą prawie wszystkie gramatyki LR(k), oprócz niektórych gramatyk prawostronnie rekursywnych, więc także gramatyki większości języków programowania.
Algorytm Earleya działa szczególnie wydajnie z gramatykami o produkcjach lewostronnie rekursywnych. Jako przykład posłuży gramatyka S → Sa S → a
użyta do analizy ciągu aaa. Algorytm Earleya tworzy wówczas następujące sytuacje:
thumb|Drzewo rozbioru ciągu aaa w gramatyce lewostronnie rekursywnej
{| class="wikitable" |- style="background: #efefef;" ! Sytuacja Earleya ! Powód dodania do zbioru sytuacji |- | [S’ →0 •0 S] | inicjalizacja |- | [S →0 •0 Sa] | przewidziano S w sytuacji [S’ →0 •0 S], a potem w sytuacji [S →0 •0 Sa] |- | [S →0 •0 a] | przewidziano S w sytuacji [S’ →0 •0 S], a potem w sytuacji [S →0 •0 Sa] |- | [S →0 a •1] | wczytano a w sytuacji [S →0 •0 a] |- | [S’ →0 S •1] | uzupełniono S w sytuacji [S’ →0 •0 S] |- | [S →0 S •1 a] | uzupełniono S w sytuacji [S →0 •0 Sa] |- | [S →0 Sa •2] | wczytano a w sytuacji [S →0 S •1 a] |- | [S’ →0 S •2] | uzupełniono S w sytuacji [S’ →0 •0 S] |- | [S →0 S •2 a] | uzupełniono S w sytuacji [S →0 •0 Sa] |- | [S →0 Sa •3] | wczytano a w sytuacji [0S → S •2 a] |- | [S’ →0 S •3] | uzupełniono S w sytuacji [S’ →0 •0 S] |- | [S →0 S •3 a] | uzupełniono S w sytuacji [S →0 •0 Sa]
Liczba sytuacji z każdą wartością indeksu przy kropce wynosi 3, więc algorytm działa w czasie liniowym.
Dla porównania użycie do analizy tego samego ciągu aaa gramatyki prawostronnie rekursywnej S → aS S → a
powoduje powstanie następujących sytuacji Earleya:
thumb|Drzewo rozbioru ciągu aaa w gramatyce prawostronnie rekursywnej
{| class="wikitable" |- style="background: #efefef;" ! Sytuacja Earleya ! Powód dodania do zbioru sytuacji |- | [S’ →0 •0 S] | inicjalizacja |- | [S →0 •0 aS] | przewidziano S w sytuacji [S’ →0 •0 S] |- | [S →0 •0 a] | przewidziano S w sytuacji [S’ →0 •0 S] |- | [S →0 a •1 S] | wczytano a w sytuacji [S’ →0 •0 aS] |- | [S →0 a •1] | wczytano a w sytuacji [S’ →0 •0 a] |- | [S →1 •1 aS] | przewidziano S w sytuacji [S →0 a •1 S] |-