Jak zrekonstruować las drzew składniowych z wektora Earley?

9

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?

Stefano Sanfilippo
źródło
2
Pomogłoby to, gdybyś wymienił znalezione referencje, które według ciebie były niejasne, a które uważasz za zbyt techniczne. W przeciwnym razie odpowiedź może być wskaźnikiem do już znalezionych referencji.
Wandering Logic
1
Być może to, co nazywasz wektorem, nie jest tym, co Earley nazywa w swoim oryginalnym artykule. Lub może być tak, że nie odgrywa dokładnie tej samej roli. Autorzy wprowadzają zmiany w algorytmach. Nie ma sposobu, aby się dowiedzieć, ponieważ nie podajesz żadnych odniesień do dokumentów, z których korzystałeś ... a my i tak możemy nie mieć do nich dostępu. Pomocne może być bardziej precyzyjne określenie definicji. Odpowiadając, założyłem, że użyłeś tych samych definicji, co Earley.
babou
@babou, to, co nazwałem „wektorem Earleya”, to tabelaryczna reprezentacja struktury danych zbudowanej przez analizator składni. Był to termin używany przez mojego profesora języków formalnych w odniesieniu do niego. Należy zauważyć, że moim podstawowym językiem nie jest angielski, więc może to być zła próba przetłumaczenia terminologii. Odwołanie techniczne, o którym wspomniałem, to sam artykuł Earleya. Podszedłem do tego, ale było to trochę przerażające dla takiego prawdziwego początkującego jak ja.
Stefano Sanfilippo
Możesz chcieć sprawdzić, czy profesor używa „wektora Earleya” w znaczeniu tej samej struktury, co Earley nazywa „wektorem” w swojej pracy. Może być przydatny do komunikacji. Co do reszty, jak widać, musisz zachować dodatkowe informacje, aby móc odzyskać parsowane drzewa, ale Earley tak naprawdę nie zagłębia się w szczegóły. Istnieją teraz inne algorytmy i obawiam się, że złożoność algorytmu Earleya kryje w sobie nieco kluczowe idee tego typu technik. Powodzenia.
babou
Czy moje wyjaśnienie było pomocne, czy potrzebujesz bardziej szczegółowego opisu części technicznej?
babou

Odpowiedzi:

9

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)nO(n2)

Najgorszy przypadek to złożoność czasu O(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 sjest 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ń.

Za każdym razem, gdy wykonujemy operację uzupełniającą, dodając stan EαD.βg (ignorując lookahead) konstruujemy wskaźnik z instancji D w tym stanie do państwa Dγ.fco spowodowało, że wykonaliśmy operację. To wskazuje na toD został przeanalizowany jako γ. W przypadku, gdy D jest niejednoznaczny, będzie od niego zestaw wskaźników, po jednym dla każdej operacji uzupełniającej, która spowodowałaEαD.βgdo dodania do określonego zestawu stanów. Każdy symbol w γ będzie miał również wskaźniki od niego (chyba że jest to terminal) i tak dalej, reprezentując w ten sposób drzewo pochodnych dla D.

Pamiętaj, że w tym tekście f 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, że D 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 Duzyskano, 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łę UXYZ, który wybieram prawą stroną dłuższą niż 2 symbole i inną zasadą WUV, 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łąUXYZ, Obie wf+1:i i wf+1:j parsować w U.

Może być tak, że jedno i drugie wi+1:k i wj+1:k oba parsują na V. Następnie z regułąWUV, 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łą UXYZ. Mam na myśli to, że państwoUXY.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 WUV.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.

Babou
źródło
Oprócz parsowania CYK warto również przyjrzeć się parsowaniu GLR.
pseudonim
1
@Pseudonim Znajomość i zrozumienie różnych form ogólnego analizowania CF na pewno nie zaszkodzi, i sugeruję tyle samo z dwoma odnośnikami na końcu odpowiedzi. Mój wybór CYK nie był jednak przypadkowy. Dzieli z algorytmem Earleya właściwość interpretacji, bezpośredniego korzystania z gramatyki, zamiast korzystania z tabel utworzonych przez kompilację gramatyki w automatyce push-down (jak w GLR, GLL, GPrec). Dlatego relacja między procesem rozpoznawania a generacją drzew / lasów jest bardziej widoczna. CKY jest również najprostszym algorytmem, z jednym wyjątkiem.
babou