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

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?

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(n^3)$$n$$O(n^2)$

Najgorszy przypadek to złożoność czasu $O(n^3)$, 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ąć do$O(n^{s+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ń.

Za każdym razem, gdy wykonujemy operację uzupełniającą, dodając stan $E\rightarrow \alpha D.\beta \; g$ (ignorując lookahead) konstruujemy wskaźnik z instancji $D$ w tym stanie do państwa $D\rightarrow \gamma. \; f$co spowodowało, że wykonaliśmy operację. To wskazuje na to$D$ został przeanalizowany jako $\gamma$. 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ła$E\rightarrow \alpha D.\beta \; g$do dodania do określonego zestawu stanów. Każdy symbol w $\gamma$ 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\rightarrow \gamma$ 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\rightarrow \alpha D.\beta \; 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 $w_{f+1:g}$. Węzły bezpośrednio poniżej$D$ są podane przez regułę $D\rightarrow \gamma$. Szukając ukończenia, które doprowadziło do$D\rightarrow \gamma. \; 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\rightarrow XYZ$, który wybieram prawą stroną dłuższą niż 2 symbole i inną zasadą $W\rightarrow UV$, dla niejednoznacznej gramatyki.

Może się zdarzyć, że parser będzie parsował $w_{f+1:g}$ w $X$, $w_{g+1:h}$ w $Y$ i oboje $w_{h+1:i}$ i $w_{h+1:j}$ w $Z$. Więc z regułą$U\rightarrow XYZ$, Obie $w_{f+1:i}$ i $w_{f+1:j}$ parsować w $U$.

Może być tak, że jedno i drugie $w_{i+1:k}$ i $w_{j+1:k}$ oba parsują na $V$. Następnie z regułą$W\rightarrow UV$, ciąg $w_{f+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)$w_{f+1:g}$ i $w_{g+1:h}$ w $X$ i $Y$. Ale faktycznie zrobi to nieco więcej: podzieli także początek dwóch odrębnych analizowanych parsów$U$ z regułą $U\rightarrow XYZ$. Mam na myśli to, że państwo$U\rightarrow XY.Z \; f$ zostanie znaleziony tylko raz (w odniesieniu do tego, co opisuję), w zestawie stanów $S_h$. Będzie to wspólna część dwóch parsów. Oczywiście rzeczy będą się tymczasowo różnić podczas analizowania$Z$ ponieważ odpowiadają one rozróżniającym podciągom, aż zbiegną się ponownie, gdy wszystko parsuje w W, gdy stan $W\rightarrow UV. \; f$ jest tworzony dwukrotnie w zestawie stanowym $S_k$.

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.