Algorytm Earleya

Algorytm Earleya

Algorytm Earleya to metoda analizy składniowej, która działa na podstawie dowolnej gramatyki bezkontekstowej. Jest wykorzystywana m.in. w przetwarzaniu języków naturalnych, ponieważ w przeciwieństwie do wielu innych algorytmów, potrafi radzić sobie z gramatykami niejednoznacznymi. Znalazł również zastosowanie przy tworzeniu interpreterów i kompilatorów języków programowania, szczególnie tych specjalizowanych, jako że wzorce projektowe oparte na tym algorytmie ułatwiają szybkie prototypowanie (RAD).

W przypadku analizy n symboli terminalnych przez parser oparty na tym algorytmie, górne ograniczenie czasu działania wynosi O(n³) w ogólnym przypadku, O(n²) dla gramatyk jednoznacznych oraz O(n) dla dużej klasy gramatyk bezkontekstowych, w tym większości gramatyk języków programowania.

Algorytm ten został opracowany w 1968 roku przez Jaya Earleya z Carnegie Mellon University w jego pracy doktorskiej, której promotorem był Robert W. Floyd. W 1970 roku Earley opublikował go w czasopiśmie Communications of the ACM, a w 1983 roku jego artykuł został uznany za jedną z 21 najbardziej znaczących publikacji w ćwierćwieczu istnienia tego czasopisma.

Zasada działania

Algorytm Earleya, podobnie jak algorytm CYK, należy do klasy tablicowych metod analizy składniowej (ang. chart parsers). Wykorzystuje on wstępującą analizę składniową z lewa na prawo, opierając się na przewidywaniach zstępujących. Wyniki algorytmu są generowane na podstawie wcześniejszych częściowych rezultatów, zgodnie z techniką programowania dynamicznego.

Analiza składniowa z zastosowaniem tego algorytmu operuje na zbiorze sytuacji Earleya (ang. Earley items), które przedstawiają produkcje gramatyki z dodaną kropką oraz dwoma indeksami. W trakcie działania algorytmu, sytuacje Earleya odzwierciedlają dotychczasowe zastosowane produkcje i służą do przewidywania kolejnych. Po przetworzeniu poprawnego ciągu wejściowego powinna powstać sytuacja, która reprezentuje 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 muszą spełniać warunki 0 ≤ h ≤ i ≤ n (jeśli symbole terminalne są numerowane od t0 do tn−1), a kropka może znajdować się w dowolnym miejscu pomiędzy początkiem a końcem prawej strony produkcji A → X0 … Xq−1, co oznacza 0 ≤ p ≤ q. Indeks h wskazuje pierwszy symbol terminalny wchodzący do drzewa rozbioru danej produkcji, indeks i wskazuje pierwszy nierozpatrzony symbol terminalny, a położenie kropki informuje o postępie analizy danej produkcji. 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 (gdzie małe litery greckie α, β, γ, … oznaczają dowolne, w tym 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’ to pomocniczy symbol startowy spoza zbioru symboli gramatyki. Następnie, dopóki zbiór ten się powiększa, algorytm dodaje do niego nowe sytuacje, bazując na wejściowych symbolach terminalnych oraz sytuacjach już istniejących w zbiorze. Jeśli nowo utworzona sytuacja już należy do zbioru, nie ulega zmianie. Nowe sytuacje powstają w wyniku trzech działań:

• wczytywanie (ang. scanning) polega na zaakceptowaniu 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ą znajduje się bieżący symbol terminalny, to do zbioru dodawana jest sytuacja [A →h αti •i+1 η], z kropką przesuniętą za ten symbol oraz zwiększonym indeksem nierozpatrzonego symbolu terminalnego 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 tuż za kropką znajduje się symbol nieterminalny B, to dla każdej produkcji B → β dodawana jest sytuacja [B →i •i β], co przygotowuje algorytm na ewentualne rozpoznanie tej produkcji od najbliższego nierozpatrzonego symbolu terminalnego;
• uzupełnianie (ang. completion) jest wstępującym komponentem algorytmu: jeśli istnieje sytuacja [A →h α •i], co oznacza rozpoznanie całej produkcji A → α, to dla każdej sytuacji [B →g β •h Aγ], w której oczekiwano symbolu nieterminalnego A tam, gdzie została rozpoznana produkcja A → α, dodawana jest sytuacja [B →g βA •i γ] z kropką przesuniętą za symbol A oraz zaktualizowanym indeksem nierozpatrzonego symbolu terminalnego.

Wyprowadzenie ciągu symboli terminalnych t0, … , tn−1 z symbolu startowego danej gramatyki istnieje wtedy i tylko wtedy, gdy algorytm wytworzył sytuację Earleya [S’ →0 S •n].

Przykład

Rozważmy gramatykę dla „pikogramatyki” języka angielskiego:

• S → NP VP
• NP → Det N
• NP → Det Adj N
• VP → V
• VP → V NP

oraz wejściowy ciąg symboli: TheDet blackAdj catN ateV aDet whiteAdj mouseN. Algorytm tworzy następujący zbiór sytuacji Earleya:

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 także tworzą poprawne zdanie w danej gramatyce.

Złożoność obliczeniowa

W implementacjach algorytmu Earleya zamiast jednego zbioru sytuacji korzysta się z listy zbiorów, a wewnątrz sytuacji pomija się indeks nierozpatrzonego symbolu wejściowego. W i-tym zbiorze przechowuje się sytuacje w postaci:

[A →h α • η]. Spotyka się również notację [A → α • η, h] i inne. Algorytm przegląda kolejno zbiory z tej listy, co pozwala mu 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ą tylko raz. Wymaga to jednak modyfikacji algorytmu, aby działał poprawnie dla gramatyk zawierających produkcje z pustą prawą stroną. Aby wydajnie przeglądać sytuacje w jednym zbiorze, powinny one tworzyć kolejkę, a przy próbie dodania sytuacji do kolejki należy efektywnie sprawdzić, czy kolejka już ją zawiera; sytuacje z każdej kolejki powinny być dodatkowo związane z tablicą asocjacyjną. Wydajne uzupełnianie sytuacji, w których kropka nie leży na końcu produkcji, wymaga jeszcze jednej tablicy asocjacyjnej, która przechowuje 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ą oraz z indeksu nierozpatrzonego symbolu terminalnego. Dodatkowo, aby wydajnie przewidywać nowe sytuacje, należy z każdym symbolem nieterminalnym powiązać listę wszystkich produkcji, które mają ten symbol po lewej stronie.

Jeśli zastosujemy tablice asocjacyjne jako tablice mieszające, to krok związany z tworzeniem nowej sytuacji Earleya i próbą poszerzenia o nią zbioru sytuacji można wykonać w oczekiwanym czasie O(1).

Earley stwierdził w swoim artykule, że w ogólnym przypadku:

• i-ty zbiór liczy O(i) sytuacji, ponieważ górne ograniczenie ich liczby jest równe 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ę, ponieważ w najgorszym przypadku musi dodać O(h) sytuacji należących do h-tego zbioru, a h = O(i), więc 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 w i-tym zbiorze sytuacji wykonuje O(i) kroków, co skutkuje kwadratową złożonością algorytmu. Klasa gramatyk, dla których algorytm Earleya działa w czasie liniowym, obejmuje gramatyki, dla których liczba sytuacji w każdym zbiorze jest ograniczona stałą. Do tej klasy należą niemal wszystkie gramatyki LR(k), z wyjątkiem pewnych gramatyk prawostronnie rekursywnych, w tym gramatyki większości języków programowania.

Algorytm Earleya działa szczególnie efektywnie z gramatykami o lewostronnie rekursywnych produkcjach. Jako przykład użyjemy gramatyki:

• S → Sa
• S → a

która służy do analizy ciągu aaa. Algorytm Earleya tworzy wówczas następujące sytuacje:

Liczba sytuacji z każdą wartością indeksu przy kropce wynosi 3, co sprawia, że 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

prowadzi do powstania następujących sytuacji Earleya:

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

Puste produkcje

Jeśli algorytm Earleya rozpatruje sytuacje z i-tego zbioru jednokrotnie, w kolejności ich dodawania, może działać niepoprawnie dla gramatyk zawierających produkcje o pustej prawej stronie (zwane również ε-produkcjami, ponieważ ε tradycyjnie oznacza pusty ciąg symboli gramatyki). Przy uzupełnianiu sytuacji [E →i •i], która odpowiada pustej produkcji E → ε, należy przejrzeć niepełny jeszcze i-ty zbiór. Jeśli sytuacja:

[A →h α •i Eη]

zostanie dodana do tego zbioru po uzupełnieniu sytuacji [E →i •i], to uzupełnianie nigdy nie doda sytuacji [A →h αE •i η]. Nie zostaną również dodane sytuacje bezpośrednio i pośrednio z niej wynikające. Może to skutkować odrzuceniem poprawnego ciągu wejściowego, co ilustruje 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, mimo że powinien.

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, jak długo kolejne iteracje powiększają jego liczebność;
• Earley zaproponował, aby przy uzupełnianiu sytuacji zapamiętywać symbole nieterminalne, z których można wyprowadzić ciąg pusty (ang. nullable symbols), które rozpoznaje się po tym, że stoją po lewej stronie produkcji z pustą prawą stroną lub złożonej tylko z symboli sprowadzalnych do pustego ciągu. Przy dodawaniu do zbioru sytuacji [A →h α •i Bη], jeśli z symbolu B stojącego za kropką można wyprowadzić pusty ciąg, dodawana jest również sytuacja [A →h αB •i η];
• Podobne rozwiązanie zaproponowane przez J. Aycocka i R.N. Horspoola polega na modyfikacji przewidywania sytuacji: „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ć pusty ciąg, dodaj też sytuację [A →h αB •i η]”, przy czym zbiór symboli nieterminalnych sprowadzalnych do pustego ciągu można łatwo określić z góry;
• Każdą gramatykę, z której symbolu startowego nie można wyprowadzić pustego ciągu, można przekształcić na równoważną gramatykę bez pustych produkcji.

Rozpoznawanie a analiza składniowa

Opisany powyżej algorytm jedynie rozpoznaje, czy dany ciąg symboli terminalnych jest poprawnym zdaniem danej gramatyki bezkontekstowej (taki algorytm nazywany jest w języku angielskim recognizer), ale nie buduje jego drzewa składni. Zaproponowano kilka metod tworzenia na jego podstawie właściwego parsera. Komplikację stanowi liczba drzew rozbioru, która może być 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.

W artykule Earleya przedstawiono, jak przekształcić algorytm rozpoznawania w parser, poprzez 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łnieniu, które powoduje 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 przedstawił 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 dla ciągu aaa, ale również niepoprawne drzewa rozbioru dla ciągów aa i aaaa.

Można temu zaradzić, dodając do sytuacji [B →g βA •i γ], która powstała 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, czas działania algorytmu mógłby przekroczyć O(n³), co pokazuje przykład 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 Ω(nm). 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 algorytmu budowy drzew rozbioru na podstawie grafu sytuacji połączonych tymi wskaźnikami. Wówczas złożoność czasowa samego parsera bez budowy drzew rozbioru nie przekracza rzędu O(n³).

E. Scott opublikowała algorytm, który w czasie O(n³) przetwarza graf sytuacji na wersję znanego z parserów GLR współdzielonego, upakowanego lasu analizy (ang. shared packed parse forest), w którym każdy węzeł ma najwyżej dwóch synów.

Na innej zasadzie opiera się propozycja D. Grunego i C.J.H. Jacobsa, która dotyczy tworzenia drzew rozbioru ze zbioru sytuacji przy użyciu parsera Ungera.

Podgląd symboli terminalnych

Operacja przewidywania w algorytmie Earleya może korzystać z podglądu (ang. lookahead). Wówczas działa w następujący sposób: „jeśli istnieje sytuacja [A →h α •i Bη], to dla każdej produkcji B → β dodaj sytuację [B →i •i β], pod warunkiem, że zbiór FIRST ciągu symboli β zawiera symbol terminalny ti”. Jak zwykle przy podglądzie, najwygodniej na końcu analizowanego ciągu symboli ustawić wartownika tn = $ spoza zbioru symboli terminalnych.

W oryginalnym artykule Earleya zaproponowano stosowanie podglądu w operacji uzupełniania. Przy uzupełnianiu, w przeciwieństwie do przewidywania, nie da się z góry określić 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’ →0 •0 S] ma jeden element – wartownika $;
• przy wczytywaniu, nowa sytuacja [A →h αti •i+1 η] dziedziczy zbiór dopuszczalnych następników swojej poprzedniczki [A →h α •i tiη];
• przy przewidywaniu sytuacji [B →i •i β] na podstawie sytuacji [A →h α •i Bη], zbiór dopuszczalnych następników NA dla nowo powstałej sytuacji wyznacza się jako zbiór FIRST(Bη), jeśli FIRST(Bη) nie zawiera symbolu pustego ε, lub jako suma zbiorów FIRST(Bη) ∪ NA, 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 ti.

Można również 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 porównaniu do wersji bez podglądu, natomiast narzut związany z zastosowaniem jakiegokolwiek podglądu przy uzupełnianiu przewyższał korzyści z niego płynące. Wiele implementacji algorytmu Earleya nie korzysta wcale z podglądu, przez co mogą bezpośrednio posługiwać się daną gramatyką, pomijając jej wcześniejsze przetwarzanie w celu określenia zbiorów FIRST.

Modyfikacje algorytmu

W artykule F.C.N. Pereiry i D.H.D. Warrena zaprezentowano, jak uogólnić tablicowe metody analizy składniowej na dowolne formalizmy gramatyczne oparte na unifikacji, w tym kontekstowe. Zapoczątkowało to falę artykułów opisujących wersje algorytmu Earleya dla formalizmów 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) itp. 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, opracowując razem z W.R. Ruzzo algorytm analizy składniowej, który stanowi hybrydę tych dwóch algorytmów.

J. Aycock i N. Horspool pokazali, jak skonstruować deterministyczny automat skończony, podobny do automatu LR(0), który parsuje dane wejściowe znacznie szybciej niż tradycyjne implementacje algorytmu Earleya.

A. Päseler opracowała wariant algorytmu Earleya, który zamiast listy symboli terminalnych analizuje kratę słów (ang. word lattice). Kraty słów znajdują zastosowanie w rozpoznawaniu mowy oraz analizie tekstów pisanych bez odstępów między wyrazami, np. w niektórych 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, są w stanie działać dla danych wejściowych o brakujących, nadmiarowych lub nieznanych fragmentach.

Kod źródłowy

W serwisie wikibooks dostępny jest kod źródłowy parsera Earleya w Pythonie, który nie wykorzystuje podglądu, przetwarza puste produkcje według pomysłu Earleya i tworzy drzewa rozbioru zgodnie z ideą Łapszyna. Program ten wypisuje kolejno tworzone sytuacje oraz wszystkie drzewa rozbioru dla ciągu wejściowego, zapisane w notacji nawiasowej.

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

Przypisy

Linki zewnętrzne

Implementacja w JavaScript