Algorytm Earleya

174 jpg' alt='Algorytm_Earleya'>
Algorytm Earleya – w informatyce algorytm służący do analizy składniowej na podstawie dowolnej gramatyki bezkontekstowej. Stosuje się go między innymi do analizy 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 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 Algorytm Earleya należy, podobnie jak algorytm CYK, do klasy tablicowych metod parsowania (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 teoria_kategorii .php'>produkcji gramatyki z dodaną kropką i dwoma indeksami Podczas działania algorytmu sytuacje Earleya odzwierciedlają dotychczas zastosowane teoria_kategorii .php'>produkcje oraz służą do przewidywania kolejnych teoria_kategorii .php'>produkcji Po przeanalizowaniu poprawnego ciągu wejściowego powinna powstać sytuacja, która odzwierciedla jego wyprowadzenie z symbolu startowego gramatyki.Sytuacje Earleya mają postać , gdzie teoria_kategorii .php'>produkcja A → X0 … Xq 1 należy do zbioru teoria_kategorii .php'>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 teoria_kategorii .php'>produkcji A → X0 … Xq 1 włącznie, czyli 0 ≤ p ≤ q. Indeks h określa pierwszy symbol terminalny wchodzący do drzewa rozbioru danej teoria_kategorii .php'>produkcji indeks i – pierwszy nierozpatrzony jeszcze symbol terminalny, a położenie kropki oznacza postęp analizy danej teoria_kategorii .php'>produkcji Ujmując rzecz formalnie, sytuacja Earleya oznacza, że algorytm przeanalizował podciąg t0 … ti 1 jako część formy zdaniowej t0 … th−1X0 … Xq 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 , 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ń: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 .Dla „pikogramatyki” języka angielskiegoi wejściowego ciągu symboli TheDet blackAdj catN ateV aDet whiteAdj mouseN algorytm tworzy następujący zbiór sytuacji Earleya:Ostatnia sytuacja Earleya odpowiada pełnemu rozbiorowi wszystkich siedmiu symboli ciągu wejściowego. Sytuacja Earleya 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 . Spotyka się też notację 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 teoria_kategorii .php'>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 teoria_kategorii .php'>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 teoria_kategorii .php'>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: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 matematyka .php'>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 teoria_kategorii .php'>produkcjach lewostronnie rekursywnych. Jako przykład posłuży gramatykaużyta 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 więc algorytm działa w czasie liniowym.Dla porównania użycie do analizy tego samego ciągu aaa gramatyki prawostronnie rekursywnejpowoduje powstanie następujących sytuacji Earleya: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ą teoria_kategorii .php'>produkcje o pustej prawej stronie (zwane też ε teoria_kategorii .php'>produkcjami bo ε tradycyjnie oznacza pusty ciąg symboli gramatyki). Przy uzupełnianiu sytuacji , która odpowiada pustej teoria_kategorii .php'>produkcji E → ε, trzeba przejrzeć niepełny jeszcze i-ty zbiór Jeśli sytuacja zostanie do niego dodana po uzupełnieniu sytuacji , to uzupełnianie nigdy nie doda sytuacji . 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 gramatykido analizy pustego ciągu ε. W zbiorze sytuacji Earleya na czerwono zaznaczono te sytuacje, których algorytm nie dodał do zbioru, choć powinien.Opublikowano kilka rozwiązań tego problemu: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 rozbioru składniowego. Zaproponowano kilka sposobów tworzenia na jego podstawie właściwego parsera. Komplikację stanowi liczba drzew rozbioru, potencjalnie wykładnicza w matematyka .php'>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 podano, jak przekształcić algorytm rozpoznawania w parser przez dodanie do wystapień symboli nieterminalnych wewnątrz prawych stron teoria_kategorii .php'>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 , tworzy się wskaźnik od wystąpienia symbolu A w tej sytuacji do sytuacji . M. Tomita podał jednak kontrprzykład: dla gramatykii 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 powstałej w wyniku uzupełniania nie jeden, lecz parę wskaźników: do sytuacji oraz do sytuacji . 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ć n3, jak pokazuje przykład, pochodzący z artykułu M. Johnsona : dla gramatykialgorytm 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 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 n3. E. Scott opublikowała natomiast algorytm, który w czasie O(n3) przetwarza graf sytuacji na taką wersję znanego z parserów GLR współdzielonego upakowanego lasu parsowania (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 , to dla każdej teoria_kategorii .php'>produkcji B → β dodaj sytuację , o ile 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, 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: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 matematyka .php'>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 parsowania na dowolne formalizmy gramatyczne oparte na unifikacji, również te 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 ciagu 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 wikiźródłach zamieszczono kod źródłowy w Pythonie parsera Earleya bez podglądu, przetwarzającego puste teoria_kategorii .php'>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: