Algorytm Earleya

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 n³ w ogólnym przypadku, do n² 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.

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 X₀ … X_p−1 •_i X_p … X_q−1], gdzie produkcja A → X₀ … X_q−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 t₀ do t_n−1), a kropka może leżeć gdziekolwiek pomiędzy początkiem a końcem prawej strony produkcji A → X₀ … X_q−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 X₀ … X_p−1 •_i X_p … X_q−1] oznacza, że algorytm przeanalizował podciąg t₀ … t_i−1 jako część formy zdaniowej t₀ … t_h−1X₀ … X_q−1α do symbolu X_p−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’ →₀ •₀ 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 t_iη], w której bezpośrednio za kropką występuje bieżący symbol terminalny, to dodaj do zbioru sytuację [A →_h αt_i •_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 t₀, … , t_n−1 z symbolu startowego danej gramatyki istnieje wtedy i tylko wtedy, gdy algorytm utworzył sytuację Earleya [S’ →₀ S •_n].

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 The_Det black_Adj cat_N ate_V a_Det white_Adj mouse_N algorytm tworzy następujący zbiór sytuacji Earleya:

 

 

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’ →₀ S •₇] odpowiada pełnemu rozbiorowi wszystkich siedmiu symboli ciągu wejściowego. Sytuacja Earleya [S’ →₀ S •₄] oznacza, że pierwsze cztery symbole tego ciągu również tworzą poprawne zdanie w danej gramatyce.

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 t_i 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 (A_p, 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(i²) kroków;
• sumowanie od i równego 0 do n daje O(n³) kroków działania algorytmu i O(n²) 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:

 

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:

 

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]
[S →1 •1 a]	przewidziano S w sytuacji [S →0 a •1 S]
[S’ →0 S •1]	uzupełniono S w sytuacji [S’ →0 •0 S]
[S →1 a •2 S]	wczytano a w sytuacji [S’ →1 •1 aS]
[S →1 a •2]	wczytano a w sytuacji [S’ →1 •1 a]
[S →2 •2 aS]	przewidziano S w sytuacji [S →1 a •2 S]
[S →2 •2 a]	przewidziano S w sytuacji [S →1 a •2 S]
[S →0 aS •2]	uzupełniono S w sytuacji [S’ →0 a •1 S]
[S’ →0 S •2]	uzupełniono S w sytuacji [S’ →0 •0 S]
[S →2 a •3 S]	wczytano a w sytuacji [S’ →2 •2 aS]
[S →2 a •3]	wczytano a w sytuacji [S’ →2 •2 a]
[S →3 •3 aS]	przewidziano S w sytuacji [S →2 a •3 S]
[S →3 •3 a]	przewidziano S w sytuacji [S →2 a •3 S]
[S →1 aS •3]	uzupełniono S w sytuacji [S’ →1 a •2 S]
[S →0 aS •3]	uzupełniono S w sytuacji [S’ →0 a •1 S]
[S’ →0 S •3]	uzupełniono S w sytuacji [S’ →0 •0 S]

Liczba sytuacji o danej wartości indeksu przy kropce rośnie liniowo ze wzrostem tego indeksu, zatem dla tej gramatyki algorytm działa z kwadratową złożonością czasową.

Jeśli algorytm Earleya rozpatruje sytuacje z i-tego zbioru jednokrotnie, w kolejności ich dodawania, to może działać niepoprawnie dla gramatyk, które zawierają produkcje o pustej prawej stronie (zwane też ε-produkcjami, bo ε tradycyjnie oznacza pusty ciąg symboli gramatyki). Przy uzupełnianiu sytuacji [E →_i •_i], która odpowiada pustej produkcji E → ε, trzeba przejrzeć niepełny jeszcze i-ty zbiór. Jeśli sytuacja [A →_h α •_i Eη] zostanie do niego dodana po uzupełnieniu sytuacji [E →_i •_i], to uzupełnianie nigdy nie doda sytuacji [A →_h αE •_i η]. Nie zostaną też dodane sytuacje bezpośrednio i pośrednio z niej wynikające. Może to spowodować odrzucenie poprawnego ciągu wejściowego, jak pokazuje poniższy przykład użycia gramatyki

S → E A A A
A → E
E → ε

do analizy pustego ciągu ε. W zbiorze sytuacji Earleya na czerwono zaznaczono te sytuacje, których algorytm nie dodał do zbioru, choć powinien.

 

Sytuacja Earleya	Powód dodania do zbioru sytuacji
[S’ →0 •0 S]	inicjalizacja
[S →0 •0 E A A A]	przewidziano S w sytuacji [S’ →0 •0 S]
[E →0 •0]	przewidziano E w sytuacji [S →0 •0 E A A A]
[S →0 E •0 A A A]	uzupełniono E w sytuacji [S →0 •0 E A A A]
[A →0 •0 E]	przewidziano A w sytuacji [S →0 E •0 A A A]
[A →0 E •0]	nie uzupełniono E w sytuacji [A →0 •0 E]
[S →0 E A •0 A A]	nie uzupełniono A w sytuacji [S →0 E •0 A A A]
[S →0 E A A •0 A]	nie uzupełniono A w sytuacji [S →0 E A •0 A A]
[S →0 E A A A •0]	nie uzupełniono A w sytuacji [S →0 E A A •0 A]
[S’ →0 S •0]	nie uzupełniono S w sytuacji [S’ →0 •0 S]

Opublikowano kilka rozwiązań tego problemu:

• A.V. Aho i J.D. Ullman zalecają wielokrotne wykonywanie w pętli przewidywania i uzupełniania wszystkich sytuacji z i-tego zbioru tak długo, dopóki kolejne iteracje powiększają jego liczebność;
• Earley zaproponował, by przy uzupełnianiu sytuacji zapamiętywać symbole nieterminalne, z których da się wyprowadzić ciąg pusty (ang. nullable symbols), które poznaje się po tym, że stoją po lewej stronie produkcji o prawej stronie pustej lub złożonej tylko z symboli sprowadzalnych do ciągu pustego, a przy dodawaniu do zbioru sytuacji [A →_h α •_i Bη], jeśli z symbolu B stojącego po kropce da się wyprowadzić ciąg pusty, dodać do zbioru także sytuację [A →_h αB •_i η];
• podobne rozwiązanie J. Aycocka i R.N. Horspoola polega na zmianie przewidywania sytuacji na „jeśli istnieje sytuacja [A →_h α •_i Bη], to dla każdej produkcji B → β dodaj sytuację [B →_i •_i β]; jeśli z symbolu B można wyprowadzić ciąg pusty, to dodaj również sytuację [A →_h αB •_i η]”, przy czym zbiór symboli nieterminalnych sprowadzalnych do ciągu pustego można łatwo wyznaczyć z góry;
• każdą gramatykę, z której symbolu startowego nie da się wyprowadzić ciągu pustego, można przekształcić na równoważną gramatykę bez pustych produkcji.

Opisany powyżej algorytm tylko rozpoznaje, czy dany ciąg symboli terminalnych stanowi poprawne zdanie danej gramatyki bezkontekstowej (taki algorytm nazywa się po angielsku recognizer), ale nie buduje jego drzewa składni. Zaproponowano kilka sposobów tworzenia na jego podstawie właściwego parsera. Komplikację stanowi liczba drzew rozbioru, potencjalnie wykładnicza w stosunku do rozmiaru danych wejściowych, a dla gramatyk z cyklami nawet nieskończona. Istnieją jednak sposoby kodowania wszystkich drzew rozbioru w strukturach danych o rozmiarze wielomianowym względem długości ciągu wejściowego.

Poprawne drzewa rozbioru ciągu aaa
Niepoprawne drzewa rozbioru ciągu aaa

W artykule Earleya podano, jak przekształcić algorytm rozpoznawania w parser przez dodanie do wystąpień symboli nieterminalnych wewnątrz prawych stron produkcji w sytuacjach Earleya zbioru wskaźników do sytuacji, które spowodowały uzupełnienie tych symboli: przy każdym uzupełnianiu, powodującym powstanie sytuacji [B →_g βA •_i γ], tworzy się wskaźnik od wystąpienia symbolu A w tej sytuacji do sytuacji [A →_h α •_i]. M. Tomita podał jednak kontrprzykład: dla gramatyki

S → S S
S → a

i ciągu wejściowego aaa parser zaproponowany przez Earleya tworzy nie tylko poprawne drzewa rozbioru ciągu aaa, ale też niepoprawne drzewa rozbioru ciągów aa i aaaa.

Można temu zaradzić, dodając do sytuacji [B →_g βA •_i γ] powstałej w wyniku uzupełniania nie jeden, lecz parę wskaźników: do sytuacji [B →_g β •_h Aγ] oraz do sytuacji [A →_h α •_i]. Gdyby naiwnie skorzystać z tego pomysłu przez dodanie tej pary wskaźników do zestawu etykiet odróżniających sytuacje, to rząd czasu działania algorytmu mógłby przekroczyć n³, jak pokazuje przykład, pochodzący z artykułu M. Johnsona: dla gramatyki

S → S … S (m + 2 powtórzenia symbolu S)
S → S S
S → a

algorytm Earleya z tak zdefiniowanymi sytuacjami analizuje ciąg wejściowy a … a (n + 1 powtórzeń symbolu a, przy czym n > m) w czasie Ω(n^m). Od W.A. Łapszyna pochodzi pomysł przechowywania zbiorów takich par wskaźników jako wartości tablicy asocjacyjnej, której klucze to sytuacje Earleya, oraz algorytm budowy drzew rozbioru na podstawie grafu sytuacji połączonych tymi wskaźnikami. Wówczas złożoność czasowa samego parsera bez budowania drzew rozbioru nie przekracza rzędu n³. E. Scott opublikowała natomiast algorytm, który w czasie O(n³) przetwarza graf sytuacji na taką wersję znanego z parserów GLR współdzielonego upakowanego lasu analizy (ang. shared packed parse forest), w której każdy węzeł ma najwyżej dwóch synów.

Na innej zasadzie opiera się propozycja D. Grunego i C.J.H. Jacobsa: tworzenie drzew rozbioru ze zbioru sytuacji za pomocą parsera Ungera.

Operacja przewidywania w algorytmie Earleya może korzystać z podglądu (ang. lookahead). Działa ona wówczas następująco: „jeśli istnieje sytuacja [A →_h α •_i Bη], to dla każdej produkcji B → β dodaj sytuację [B →_i •_i β], o ile zbiór FIRST ciągu symboli β zawiera symbol terminalny t_i”. Jak zwykle przy podglądzie, najwygodniej na końcu analizowanego ciągu symboli ustawić wartownika t_n = $ spoza zbioru symboli terminalnych.

W oryginalnym artykule Earleya zaproponowano stosowanie podglądu w operacji uzupełniania. Przy uzupełnianiu, inaczej niż przy przewidywaniu, nie da się z góry wyznaczyć zbioru dopuszczalnych następników, jeśli nie brać pod uwagę jego mniej wydajnej i ograniczonej wersji opartej na zbiorach FOLLOW. Wydajny podgląd przy uzupełnianiu polega na następujących modyfikacjach algorytmu:

• zbiór dopuszczalnych następników początkowej sytuacji [S’ →₀ •₀ S] ma jeden element – wartownika $;
• przy wczytywaniu nowo powstała sytuacja [A →_h αt_i •_i+1 η] dziedziczy zbiór dopuszczalnych następników swojej poprzedniczki [A →_h α •_i t_iη];
• przy przewidywaniu sytuacji [B →_i •_i β] na podstawie sytuacji [A →_h α •_i Bη] o zbiorze dopuszczalnych następników N_A dopuszczalne następniki nowo powstałej sytuacji wyznacza się jako zbiór FIRST(Bη) jeśli FIRST(Bη) nie zawiera symbolu pustego ε lub jako sumę zbiorów FIRST(Bη) ∪ N_A jeśli FIRST(Bη) zawiera symbol pusty ε;
• przy uzupełnianiu sytuacji [A →_h α •_i] nowe sytuacje [B →_g βA •_i γ] dodaje się tylko wtedy, jeśli zbiór dopuszczalnych następników sytuacji [A →_h α •_i] zawiera i-ty symbol terminalny t_i.

Można też stosować podgląd więcej niż jednego symbolu terminalnego.

Warianty algorytmu Earleya z podglądem różnej liczby symboli przy przewidywaniu i uzupełnianiu badali M. Bouckaert, A. Pirotte i M. Snelling. W ich symulacjach najlepszy okazał się podgląd jednego symbolu przy przewidywaniu, który zmniejszał liczbę sytuacji o 20–50% w stosunku do wersji bez podglądu, natomiast narzut stosowania jakiegokolwiek podglądu przy uzupełnianiu przewyższał zyski z niego płynące. Wiele implementacji algorytmu Earleya wcale nie używa podglądu, dzięki czemu mogą bezpośrednio korzystać z danej gramatyki, pomijając jej wstępne przetwarzanie służące wyznaczeniu zbiorów FIRST.

W artykule F.C.N. Pereiry i D.H.D. Warrena pokazano, jak uogólnić tablicowe metody analizy składniowej na dowolne formalizmy gramatyczne oparte na unifikacji, również kontekstowe. Zapoczątkował on falę artykułów opisujących wersje algorytmu Earleya dla formalizmu unifikacji PATR-II, gramatyk przyłączania drzew (ang. tree adjoining grammar), gramatyk S-atrybutywnych (ang. S-attribute grammar), gramatyk hipergrafowych (ang. hypergraph grammar), gramatyk sekwencyjnie indeksowanych (ang. sequentially indexed grammars) itd. Technika zbiorów magicznych (ang. magic sets) w dedukcyjnych bazach danych również opiera się na ideach Pereiry i Warrena.

S.L. Graham i M.A. Harrison zwrócili uwagę na wspólne cechy algorytmu Earleya i algorytmu CYK i opracowali wraz z W.R. Ruzzo algorytm analizy składniowej, stanowiący hybrydę tych dwóch algorytmów.

J. Aycock i N. Horspool podali, jak skonstruować podobny do automatu LR(0) deterministyczny automat skończony, który parsuje dane wejściowe kilkukrotnie szybciej od tradycyjnych implementacji algorytmu Earleya.

A. Päseler opracowała wariant algorytmu Earleya, która zamiast listy symboli terminalnych analizuje kratę słów (ang. word lattice). Kraty słów znajdują zastosowanie przy rozpoznawaniu mowy i analizie tekstów pisanych bez odstępów między wyrazami, np. w językach Dalekiego Wschodu.

 

A. Stolcke opublikował algorytm, który zwraca najbardziej prawdopodobny rozbiór składniowy wejściowego ciągu symboli dla danej probabilistycznej gramatyki bezkontekstowej.

Wersje algorytmu Earleya, opracowane przez G. Lyona i B. Langa, działają dla danych wejściowych o brakujących, nadmiarowych lub nieznanych fragmentach.

W wikibooks zamieszczono kod źródłowy w Pythonie parsera Earleya bez podglądu, przetwarzającego puste produkcje według pomysłu Earleya i tworzącego drzewa rozbioru zgodnie z ideą Łapszyna. Program wypisuje kolejno tworzone sytuacje oraz wszystkie drzewa rozbioru ciągu wejściowego, zapisane w notacji nawiasowej.

Program ten znajduje cztery drzewa rozbioru niejednoznacznego zdania time flies like an arrow. Narysowane np. za pomocą programu phpSyntaxTree, drzewa te wyglądają następująco:

muchy czasu lubią strzałę	czas leci jak strzała	mierz czas much podobnych do strzały	mierz czas much jak strzałę/jak strzała
Drzewa rozbioru zdania time flies like an arrow

• Implementacja w JavaScript