Użycie wektora Earleya jako rozpoznającego jest dość proste: po osiągnięciu końca struny wystarczy sprawdzić, czy produkcja aksjomatyczna została rozpoczęta w pozycji 0. Jeśli masz przynajmniej jeden ciąg, łańcuch jest akceptowany.
Użycie wektora Earleya do odtworzenia drzewa przetwarzania jest mniej oczywiste. Właściwie nie jestem w stanie ustalić, jak mogłaby działać procedura algorytmiczna, a ponadto jedyne znalezione przeze mnie odniesienia były niejasne lub ponadtechniczne. Czy ktoś mógłby rzucić na to trochę światła?
context-free
dynamic-programming
parsers
ambiguity
syntax-trees
Stefano Sanfilippo
źródło
źródło
Odpowiedzi:
Używam terminologii i notacji z pracy Earleya . Możliwe, że opis, który czytasz, jest inny.
Wydaje się często, że ogólne algorytmy parsowania CF są najpierw przedstawiane w formie modułu rozpoznającego, a następnie zarządzanie informacją potrzebne do faktycznej budowy drzew i lasów jest dodawane w późniejszym czasie. Jednym z powodów może być to, że przechowywanie informacji potrzebnych do budowy współdzielonego lasu wymaga przestrzeni sześciennej gdzie jest długością analizowanego ciągu wejściowego, ale wymagane miejsce to tylko kwadrat do rozpoznania , gdy ta informacja nie jest zachowana. Powód tego wzrostu złożoności przestrzeni jest dość prosty: wielkość parsowania lasu może być sześcienna.O (n3)) n O (n2))
Najgorszy przypadek to złożoność czasuO (n3)) , Jak wiadomo.
Najlepszym odniesieniem do algorytmu Earleya jest oczywiście praca Earleya , ale nie jest ona bardzo jednoznaczna na temat budowania parsowanego lasu. To może być bałaganiarski biznes, o wiele bardziej niż pozwala na to szybka dyskusja z rozdziału 7 na stronie 101. Prawdą jest, że Earley nie mówi o parsowaniu lasu ani o lesie, ale o „ faktorowej reprezentacji wszystkich możliwych drzew parsowania ”. I jest ku temu dobry powód: gdyby próbował stworzyć las zgodnie z jego gramatyką, jego złożoność przestrzenna (stąd czasowa) musiałaby wzrosnąć doO (ns + 1) gdzie s jest wielkości najdłuższej reguły po prawej stronie. Dlatego inne algorytmy używają gramatyki w formie binarnej (niekoniecznie Chomsky Normal Form (CNF)).
W rzeczywistości Earley używa domyślnie postaci binarnej , ponieważ jest to konieczne ze względu na złożoność czasu sześciennego. Jest to jedna z głównych ról kropki reguły w stanach. Ale ta niejawna forma binarna tworzy parsowania i lasy zgodnie z binarną gramatyką, a nie pierwotną, która, obawiam się, jest głównym źródłem niejasności. Jest to szczegółowo opisane poniżej.
Dobrym sposobem na zrozumienie sposobu pozyskiwania lasu jest prawdopodobnie spojrzenie na niego w prostszym przypadku, algorytm CYK . Jest również często opisywany jako program rozpoznający, a aspekt parsera jest dodawany na końcu. Możesz obejrzeć opis w wikipedii. Informacje potrzebne do zbudowania lasu są tym, co przechowują w tabeli „backpointerów”. Wskaźniki wsteczne są w zasadzie wskaźnikami do podciągów (powiązany symbol), które tworzą składniki ciągu zgodnie z pewną regułą. Podają wszystkie możliwe sposoby parsowania podciągu. Przypomnij sobie, że CYK używa postaci binarnej, zwykle CNF, aby rzeczy były prostsze. Parser CYK ma zasadniczo taką samą dynamiczną strukturę programowania jak Earley, ale jest znacznie prostszy. Dlatego zrozumienie tego może być znaczącą pomocą.
Wracając do algorytmu Earleya, nie sądzę, że potrzebujesz wektora Earley do podjęcia decyzji o akceptacji lub budowy parsowania drzew i lasów. To, co Earley nazywa wektorem w swoim artykule, pojawia się tylko na stronie 97, w trzecim akapicie implementacji. Jest to tylko urządzenie przyspieszające wyszukiwanie stanów wskazujących wstecz na daną pozycję ciągu k, aby uzyskać większą złożoność. Ale wszystkie informacje znajdują się w zestawach stanów, zaimplementowanych jako listy stanów. Jednak ta informacja nie jest wystarczająca do zbudowania lasu parsowania drzew, ponieważ algorytm nie śledzi sposobu (sposobów) uzyskania stanu. Rzeczywiście, wektor jest nawet używany do skutecznego odrzucenia już znalezionego stanu, niezależnie od tego, jak został znaleziony.
W sekcji 7 artykułu Earleya wyjaśnia, że aby „przekształcić moduł rozpoznający w analizator składni”, tj. Aby móc odzyskać parsowane drzewa, konieczne jest śledzenie sposobu wykonania uzupełnień.
Pamiętaj, że w tym tekścief i g są indeksami w przeanalizowanym łańcuchu, wskazującymi miejsce, w którym zaczęło się rozpoznawanie reguły po lewej stronie (jak przewidziano symbol po prawej stronie. f jest indeksem łańcuchowym, w którym rozpoznanie D→γ rozpoczęło się i zakończyło na indeksie g . Te „wskaźniki ukończenia” są odpowiednikiem Earleya wskaźników wstecznych opisanych (niezbyt dobrze w wikipedii) dla wersji analizatora CYK.
Z takiego wskaźnika (jak opisano w cytacie) wiemy, żeD
w instancji reguły E→αD.βg może zostać przekształcony w drzewo (lub las), które analizuje ciąg wejściowy w z indeksu f+1 Indeksować g , co zauważamy wf+1:g . Węzły bezpośrednio poniżejD są podane przez regułę D→γ . Szukając ukończenia, które doprowadziło doD→γ.f możemy wtedy znaleźć inne takie wskaźniki, które mówią, jak ostatni symbol D uzyskano, a zatem więcej informacji na temat możliwych drzew parsujących. Patrząc również na zakończenie, które rozpoznało ten symbol w zestawach stanu Earleira, można dowiedzieć się, w jaki sposób zostało uzyskane i tak dalej.
Zakładając, że zachowałeś wszystkie potrzebne wskaźniki, jak wskazano w artykule, możesz uzyskać wszystkie wspólne reprezentacje drzewa, zaczynając od ostatniego symbolu rozpoznawanego przez analizator składni, który jest oczywiście początkowym symbolem gramatyki.
Ale pominąłem też ten bałagan . Załóżmy, że masz regułęU→XYZ , który wybieram prawą stroną dłuższą niż 2 symbole i inną zasadą W→UV , dla niejednoznacznej gramatyki.
Może się zdarzyć, że parser będzie parsowałwf+1:g w X ,
wg+1:h w Y i oboje wh+1:i i wh+1:j w
Z . Więc z regułąU→XYZ , Obie wf+1:i i
wf+1:j parsować w U .
Może być tak, że jedno i drugiewi+1:k i wj+1:k oba parsują na V . Następnie z regułąW→UV , ciąg
wf+1:k parsować w W na dwa różne sposoby, co odpowiada dwuznaczności gramatyki.
Oczywiście, aby uniknąć powtarzania obliczeń, algorytm Earleya będzie próbował udostępnić jak najwięcej z dwóch obliczeń parsujących. To, co faktycznie podzieli, to oczywiście rozpoznanie (i analiza)wf+1:g i wg+1:h w X i Y . Ale faktycznie zrobi to nieco więcej: podzieli także początek dwóch odrębnych analizowanych parsówU z regułą U→XYZ . Mam na myśli to, że państwoU→XY.Zf zostanie znaleziony tylko raz (w odniesieniu do tego, co opisuję), w zestawie stanów Sh . Będzie to wspólna część dwóch parsów. Oczywiście rzeczy będą się tymczasowo różnić podczas analizowaniaZ ponieważ odpowiadają one rozróżniającym podciągom, aż zbiegną się ponownie, gdy wszystko parsuje w W, gdy stan W→UV.f jest tworzony dwukrotnie w zestawie stanowym Sk .
Zatem las drzew składniowych może być bardzo dziwny, z rodzajem bliźniaków syjamskich, które mogą dzielić pierwsze dwie krawędzie jakiegoś węzła, ale nie trzecią krawędź. Innymi słowy, może to być bardzo niezręczna struktura. To może wyjaśniać, dlaczego Earley nazywa to „ faktorową reprezentacją wszystkich możliwych drzew parsujących ”, nie będąc bardziej szczegółowym.
Każda próba chirurgicznego oddzielenia bliźniaków syjamskich bez zmiany gramatyki spowoduje zwiększenie złożoności. Właściwym sposobem na to jest binaryzacja gramatyki.
Mam nadzieję, że to Ci pomoże. Daj mi znać. Ale nalegam, aby dobre zrozumienie analizy CYK mogło pomóc. Istnieją inne algorytmy, prostsze niż Earley, które mogą skutecznie analizować wszystkie języki CF.
Więcej ogólnych informacji na temat tego problemu z analizowaniem lasu można znaleźć w dwóch innych odpowiedziach: /cstheory/7374#18006 i https://linguistics.stackexchange.com/questions/4619#6120 . Ale nie zajmują się szczegółowymi szczegółami algorytmu Earleya.
źródło