Odzyskiwanie parsowanego lasu z parsera Earley?

Niedawno czytałem parser Earley i uważam, że jest to jeden z najbardziej eleganckich algorytmów, jakie do tej pory widziałem. Jednak algorytm w tradycyjnym znaczeniu jest rozpoznawaczem, a nie analizatorem składni, co oznacza, że ​​może wykryć, czy łańcuch pasuje do określonego CFG, ale nie wygenerować dla niego drzewa analizy. Moje pytanie brzmi: jak odzyskać nie drzewo analizy , a raczej las analizy wszystkich możliwych analiz danego ciągu wejściowego.

W „Technikach analizowania: praktyczny przewodnik” Grune i Jacoba ilustrują algorytm, którego można użyć do odzyskania parsowanego lasu z wyniku programu rozpoznającego Earley, ale jest on oparty na metodzie analizy Ungera, której czas działania wynosi O (n ^{k + 1} ), gdzie k jest długością najdłuższej produkcji w gramatyce. Oznacza to, że środowisko wykonawcze nie jest wielomianem pod względem gramatyki. Ponadto oryginalny artykuł Earleya na temat algorytmu, który sugeruje algorytm odzyskiwania lasów analizowanych, jest niepoprawny (patrz na przykład strona 762 tego artykułu autorstwa Tomity), chociaż wiele źródeł wciąż podaje go jako odpowiedni sposób na odzyskanie lasu analizowanego .

Moje pytanie brzmi, czy w czasie wielomianowym można odzyskać las analizujący dla danego ciągu wejściowego. Znalazłem tutaj artykuł , który zawiera algorytm do tworzenia reprezentacji lasu parsowanego wielkości sześciennej dla dowolnej analizy przy użyciu symulacji PDA, więc wydaje się, że to powinno być możliwe, ale jeszcze nie znalazłem sposobu, aby to zrobić. Idealnie, chciałbym to zrobić bez konwersji gramatyki wejściowej na CNF (co rzeczywiście rozwiązałoby problem), ponieważ wynikowy las analizowania byłby dość niechlujny.

Dzięki za wszelką pomoc, którą możesz zaoferować!

Zrobienie tego będzie oczywiście zależeć od właściwej reprezentacji „spakowanego lasu”, który reprezentuje wszystkie drzewa parsowania dla danego zdania.

Myślę, że miejscem, w którym chcesz zacząć, jest praca Joshua Goodmana (parsowanie na lewą stronę, Harvard, 1999). Zasadniczo chodzi o to, że można zdefiniować algorytm analizowania w ramach określonego semirowania. W zależności od okresu, możesz wyliczyć wszystkie wielkości i struktury zamiast nagiego drzewa analizy (jako program rozpoznający lub jako analizator składni). Jednym semirem, który można zdefiniować (co robi Goodman w swojej pracy) jest semiring, w którym wartości są zestawami parsowania. Gdy w końcu zakończysz parsowanie zdania, wszystkie drzewa analizy zostaną umieszczone w głównym węźle analizy.

Ponownie musisz uważać, aby było to możliwe dzięki odpowiedniej reprezentacji.

Jest artykuł opisujący jak to zrobić:

Parsowanie w stylu SPPF od Earley Recognisers autorstwa Elisabeth Scott

Opisuje, jak zbudować binarny las analizujący w czasie sześciennym.

Nigdy nie potrzebujesz CNF. Ma tę wadę, że zmienia strukturę gramatyki. Ale trzeba wprowadzić pośrednie nieterminale, aby żadna prawa strona nie była dłuższa niż 2 (forma 2), ponieważ długość RHS determinuje złożoność. Najlepszą próbą wyjaśnienia tego intuicyjnie jest, jeśli pamięć służy, artykuł Beau Shiel, „Observations on Context Free Parsing”, opublikowany w 1976 r. Na konferencji lingwistyki obliczeniowej. Algorytm Earleya domyślnie używa 2-form. Jest po prostu ukryty w algorytmie. Jeśli chodzi o odzyskiwanie i obsługę parsowania lasu, powinieneś spojrzeć na sieć w „parsowaniu lasu przecięcia”. To jest naprawdę bardzo proste. Wiele artykułów znajduje się w Internecie, jeśli otrzymujesz (z cytatów lub spisów treści) tytuły lub autorów, aby bezpośrednio je przeszukać.

W rzeczywistości możesz zrobić znacznie więcej niż CF i nadal uzyskać parse-lasy w czasie wielomianowym. Czasami pojawia się pytanie: co możesz z tym zrobić, kiedy już go masz?

Jednym z celów ostatniego wspomnianego artykułu jest pokazanie, że złożone algorytmy (takie jak GLR) niekoniecznie kupują cokolwiek w czasie lub w przestrzeni i mogą zmienić parsowany las.

Jedna uwaga na temat nauczania. Myślę, że Earley, choć przełomowy, jest zbyt skomplikowany do nauczania i można go zastąpić prostszymi algorytmami o zasadniczo takich samych treściach edukacyjnych. Nauczanie dotyczy pojęć lub technologii. W algorytmie Earleya podstawowe pojęcia są ukryte w złożoności szczegółów, a z technologicznego punktu widzenia są przestarzałe. To był świetny artykuł, ale to nie znaczy, że jest to najlepsze podejście pedagogiczne.

W literaturze z zakresu językoznawstwa komputerowego może być więcej informacji niż w zwykłych kanałach informatycznych. Nie mam książki Ceriel-Grune-Jacobs, ale byłbym zaskoczony, gdyby nie mieli wszystkich odpowiednich referencji (choć nie jestem pewien co do ich kryteriów wyboru).

Uzupełnienie w następstwie wniosku w komentarzu (7 lipca 2013 r.)

To uzupełnienie dotyczy istnienia prostszych algorytmów niż Earley.

Jak już powiedziałem, wyszukiwanie w Internecie w „parsing intersection forest” powinno szybko dać ci referencje, z których możesz kopać dalej.

Podstawową ideą jest to, że wszystkie ścieżki analizujące z budową wspólnego lasu to nic innego jak stara konstrukcja skrzyżowania Bar Hillel, Perles i Shamir dla zwykłego języka i języka bezkontekstowego, przy użyciu skończonego automatu i gramatyki bezkontekstowej. Biorąc pod uwagę gramatykę CF, zastosujesz konstrukcję do trywialnego automatu, który rozpoznaje tylko twój ciąg wejściowy. To wszystko. Wspólny las to tylko gramatyka skrzyżowania. Jest on związany z oryginalną gramatyką poprzez homomorfizm, rozpoznaje tylko podany ciąg, ale ze wszystkimi parsami oryginalnej gramatyki aż do tego homomorfizmu (tj. Prosta zmiana nazwy nieterminalnych).

Powstała gramatyka zawiera wiele niepotrzebnych rzeczy, nieterminale i reguły, które są albo nieosiągalne z aksjomatu (nie można go znaleźć w ciągu pochodzącym od początkowego symbolu), albo które są nieproduktywne (nie można ich wyprowadzić do terminala strunowy).

Następnie albo musisz go wyczyścić dobrym pędzlem na końcu (być może długim, ale algorytmicznie prostym), albo możesz spróbować ulepszyć konstrukcję, aby na końcu było mniej bezużytecznego puchu.

Na przykład konstrukcja CYK jest dokładnie taka, ale zorganizowana w taki sposób, że wszystkie utworzone reguły i nieterminale są produktywne, chociaż wiele może być nieosiągalnych. Tego należy się spodziewać po technice oddolnej.

Techniki odgórne (takie jak oparte na LR (k)) pozwolą uniknąć nieosiągalnych reguł i terminali, ale stworzą nieproduktywne.

Myślę, że dużo szczotkowania można osiągnąć poprzez odpowiednie użycie wskaźników, ale nie patrzyłem na to przez długi czas.

Wszystkie istniejące algorytmy są zgodne z tym modelem. To jest naprawdę sedno sprawy i jest bardzo proste. Dlaczego więc pogrzebać to w złożoności?

W literaturze zaproponowano wiele „optymalizacji” często opartych na rodzinie parserów LR (k), LL (k), być może z pewnym statycznym faktoringiem tych konstrukcji (Earley nie ma faktorowania statycznego). Można go faktycznie zastosować do wszystkich znanych technik, w tym do starych analizatorów pierwszeństwa. Umieszczam „optymalizację” między cudzysłowami, ponieważ zwykle nie jest jasne, co optymalizujesz, ani nawet czy tak naprawdę optymalizujesz, czy też korzyść z ulepszenia jest warta większej złożoności twojego parsera. Na ten temat znajdziesz niewiele obiektywnych danych, formalnych lub eksperymentalnych (jest ich kilka), ale wiele innych twierdzeń. Nie twierdzę, że nie ma nic interesującego. Istnieje kilka inteligentnych pomysłów.

Teraz, gdy poznasz podstawowy pomysł, „optymalizacje” lub ulepszenia mogą być często wprowadzane statycznie (być może przyrostowo) poprzez zbudowanie automatyki przesuwającej z gramatyki, zgodnie z interesującą Cię techniką budowy parsera, a następnie zastosowanie konstrukcja krzyżowa produktu dla skrzyżowania z tym automatem (prawie to samo, co robienie tego z gramatyką) lub gramatyki wyprowadzonej z tego automatu.

Następnie możesz wprowadzić dzwonki i gwizdki, ale są to głównie szczegóły technologiczne.

Philosophiæ Naturalis Principia Mathematica Izaaka Newtona jest podobno wielkim dziełem fizyki i matematyki. Nie sądzę, że jest na liście czytelniczej wielu studentów. Ponieważ wszystkie inne rzeczy są równe, nie sądzę, aby nauczanie algorytmu Earleya było bardzo przydatne, chociaż jest to ważny kawałek historyczny. Studenci mają wystarczająco dużo do nauczenia się. Ryzykując, że zostanie zestrzelony przez wiele osób, myślę tak samo w przypadku artykułu Knuth LR (k). Jest to znakomity fragment analizy teoretycznej i prawdopodobnie ważna lektura dla teoretyka. Głęboko wątpię, czy jest to tak istotne dla budowy parserów, biorąc pod uwagę obecny stan technologii, zarówno sprzętu, jak i oprogramowania. Minęły czasy, kiedy parsowanie było znaczącą częścią czasu kompilacji, lub gdy szybkość kompilatorów była krytycznym problemem (znałem jedną korporację, która zmarła z powodu kompilacji kosztów jakieś 30 lat temu). Specjalista od analizy może chcieć nauczyć się tej wiedzy specjalistycznej w pewnym momencie, ale przeciętny student informatyki, programowania lub inżynierii jej nie potrzebuje.

Jeśli uczniowie muszą spędzać więcej czasu na analizie, istnieją inne rozszerzenia, które mogą być bardziej przydatne i bardziej kształtujące, takie jak te używane w językoznawstwie komputerowym. Pierwszą rolą nauczania jest wydobycie prostych pomysłów, które kształtują wiedzę naukową, a nie zmuszanie studentów do cierpienia tego, co musieli ponieść naukowcy (z wyjątkiem doktorantów: jest to rytuał przejścia :-).

Licencja CC BY-SA 3.0 od autora

Artykuł opisujący, jak zbudować binarny las analizujący w czasie sześciennym (wspomniany w poście przez Angelo Borsotti), brzmi: „Parsing w stylu SPPF od Earley Recognizers” autorstwa Elizabeth Scott. Można go znaleźć tutaj: http://dx.doi.org/10.1016/j.entcs.2008.03.044

W tym artykule opisano budowę wspólnego upakowanego lasu analizującego (SPPF), który reprezentuje wszystkie możliwe drzewa analizowania. Pod drzewa są współużytkowane, gdy tylko jest to możliwe, i węzły odpowiadające różnym pochodnym tego samego podłańcucha z tego samego nieterminala są łączone.

Chciałbym powtórzyć powyższe odpowiedzi, sugerując przeczytanie tego artykułu:

http://dx.doi.org/10.1016/j.entcs.2008.03.044

Chciałbym się jednak zakwalifikować, mówiąc, że zaimplementowałem algorytm w tym artykule i uważam, że wystąpił błąd. W szczególności pierwsze zdanie drugiego akapitu punktu 4. Etykiety poprzedników, które robisz dla tego, co Earley miałby wywołać w fazie „skanowania”, powinny wskazywać od p do q, a nie na odwrót.

W szczególności następujący wiersz:

Ustaw E0 jako pozycje (S :: = · α, 0). Dla i> 0 zainicjuj Ei poprzez dodanie elementu p = (A :: = αai · β, j) dla każdego q = (A :: = α · aiβ, j) ∈ Ei − 1 i, jeśli α =, utworzenie poprzedni wskaźnik oznaczony i - 1 od q do p

Powinien brzmieć „od p do q”, a nie „od q do p”

Zaimplementowałem algorytm, jak pierwotnie stwierdzono, co dało mi błędy w niektórych ręcznie zbudowanych przypadkach testowych, które zostały naprawione, kiedy zmieniłem tutaj kierunek wskaźnika.