Nazwa tego typu analizatora składni, LUB dlaczego nie istnieje

Konwencjonalne analizatory składniowe zużywają cały wkład i tworzą pojedyncze drzewo analizy. Szukam takiego, który zużywa ciągły strumień i tworzy parsowany las [ edytuj: zobacz dyskusję w komentarzach na temat tego, dlaczego takie użycie tego terminu może być niekonwencjonalne ]. Moje przeczucie mówi, że nie mogę być pierwszą osobą, która potrzebuje (lub wydaje mi się , że potrzebuję) takiego parsera, ale szukałem i szukałem od miesięcy bezskutecznie.

Rozumiem, że może mnie złapać problem XY. Moim ostatecznym celem jest przeanalizowanie strumienia tekstu, zignorowanie większości tego tekstu i utworzenie strumienia parsowania drzew z rozpoznanych sekcji.

Moje pytanie jest więc warunkowe: jeśli istnieje klasa parserów o tych cechach, jak się nazywa? A jeśli nie, dlaczego nie? Jaka jest alternatywa? Być może brakuje mi jakiegoś sposobu, w jaki mogę sprawić, że konwencjonalne parsery zrobią to, co chcę.

Analizator składni, który zwraca wynik (częściowy) przed wykorzystaniem całego wejścia, nazywany jest analizatorem przyrostowym . Analiza przyrostowa może być trudna, jeśli w gramatyce występują lokalne niejednoznaczności, o których decyduje dopiero później. Kolejną trudnością jest udawanie tych części parsowanego drzewa, które nie zostały jeszcze osiągnięte.

Parser, który zwraca las wszystkich możliwych drzew parsujących - to znaczy zwraca drzewo parsowania dla każdej możliwej pochodnej niejednoznacznej gramatyki - nazywa się… Nie jestem pewien, czy te rzeczy mają jeszcze nazwę. Wiem, że generator parserów Marpa jest w stanie to zrobić, ale każdy parser oparty na Earley lub GLR powinien być w stanie to zrobić.

Jednak wydaje się, że nie chcesz tego. Masz strumień z wieloma osadzonymi dokumentami, ze śmieciami pomiędzy:

 garbagegarbage{key:42}garbagegarbage[1,2,3]{id:0}garbage...

Wydaje się, że potrzebujesz parsera, który przeskakuje śmieci i (leniwie) daje sekwencję AST dla każdego dokumentu. Można to uznać za parser przyrostowy w najbardziej ogólnym znaczeniu. Ale w rzeczywistości zaimplementowałbyś taką pętlę:

while stream is not empty:
  try:
    yield parse_document(stream at current position)
  except:
    advance position in stream by 1 character or token

parse_docmentFunkcja będzie wówczas konwencjonalną, dla przyrostowego parser. Występuje niewielka trudność w zapewnieniu, że przeczytałeś wystarczającą ilość strumienia wejściowego do udanej analizy. Sposób obsługi tego zależy od typu używanego parsera. Możliwości obejmują zwiększenie bufora dla niektórych błędów analizy lub użycie opóźnionego tokenizacji.

Leniwa tokenizacja jest prawdopodobnie najbardziej eleganckim rozwiązaniem ze względu na strumień wejściowy. Zamiast tego, aby faza leksykalna tworzyła stałą listę tokenów, analizator składni leniwie zażąda następnego tokenu od wywołania zwrotnego lexera ^[1] . Lexer zużyłby wtedy tyle strumienia, ile potrzeba. W ten sposób analizator składni może się nie powieść tylko wtedy, gdy osiągnięty zostanie prawdziwy koniec strumienia lub wystąpi prawdziwy błąd analizy (tj. Rozpoczęliśmy parsowanie, gdy nadal jesteśmy w śmieciach).

^{[1] leksykon zwrotny jest dobrym pomysłem również w innych kontekstach, ponieważ pozwala to uniknąć problemów z dopasowaniem najdłuższego tokena .}

Jeśli wiesz, jakiego rodzaju dokumentów szukasz, możesz zoptymalizować pomijanie, aby zatrzymać tylko w obiecujących lokalizacjach. Np. Dokument JSON zawsze zaczyna się od znaku {lub [. Dlatego śmieci to dowolny ciąg znaków, który nie zawiera tych znaków.

Nie ma jednej konkretnej nazwy dla parsera, który to robi. Podkreślę jednak jeden algorytm, który to robi: parsowanie z pochodnymi .

Zużywa dane wejściowe, jeden token na raz. Na końcu danych wejściowych utworzy las analizujący. Alternatywnie można uzyskać cały las analizy składniowej podczas analizowania ( częściowa analiza składni).

Przetwarzanie z pochodnymi obsługuje gramatyki bezkontekstowe i tworzy parsowany las dla niejednoznacznych gramatyk.

To naprawdę elegancka teoria, ale jest dopiero w powijakach i nie jest szeroko stosowana. Matt Might ma listę linków do różnych wdrożeń w Scali / Racket / etc.

Teorii łatwiej jest się nauczyć, jeśli zaczniesz od rozpoznawania pochodnych (to znaczy zacznij od pochodnych języków , w celu rozpoznania pewnych danych wejściowych w celu ustalenia, czy jest poprawna, czy nie), a następnie zmień program, aby analizował pochodne ( to znaczy zmień to tak, aby zamiast pobierać pochodne języków , pobiera pochodne parserów i oblicza parsowany las).

Dalekie od ideału, ale widziałem, że robiono to więcej niż raz: w każdej linii wejściowej spróbuj parsować. jeśli się nie powiedzie, zachowaj linię i dodaj następną. W pseudokodzie:

buffer = ''
for each line from input:
    buffer = buffer + line
    if can parse buffer:
        emit tree
        buffer = ''

Dużym problemem jest to, że w niektórych językach nie można sprawdzić, czy wyrażenie jest kompletne przed przeczytaniem następnego wiersza. W takim przypadku wydaje się, że możesz przeczytać następny i sprawdzić, czy jest to prawidłowy początek, czy też kontynuacja ... Ale do tego potrzebujesz dokładnej składni języka

Co gorsza, w tych językach nie jest trudno stworzyć patologiczny przypadek, którego nie można przeanalizować do końca pliku, nawet jeśli nie byłby to pojedynczy długi komunikat.

W skrócie

Wydaje się, że szybkim rozwiązaniem Twojego problemu jest zdefiniowanie REGEX lub FSA (automat skończony), który rozpoznaje wszystkie możliwe początki dokumentów (dozwolone są fałszywe alarmy, które w rzeczywistości nie odpowiadają dokumentowi). Następnie możesz uruchomić go bardzo szybko na podstawie danych wejściowych, aby określić następne miejsce, w którym dokument mógłby zacząć z niewielką liczbą błędów. Może to spowodować kilka błędnych pozycji na początku dokumentu, ale zostaną one rozpoznane przez analizator składni i porzucone.

Zatem automat skończony może być nazwą analizatora składni, której szukasz. :)

Problem

Zawsze trudno jest zrozumieć praktyczny problem, zwłaszcza gdy słownictwo może mieć wiele interpretacji. Słowo parsowanie lasu zostało wymyślone (afaik) do bezkontekstowego (CF) parsowania dwuznacznych zdań, które zawierają kilka parsowania. Można go w pewnym stopniu uogólnić na parsowanie sieci zdań lub na inne typy gramatyki. Stąd wszystkie odpowiedzi dotyczące parserów Earley, GLR, Marpa i pochodnych (istnieje wiele innych), które nie były istotne w tym przypadku.

Ale najwyraźniej nie to masz na myśli. Chcesz przeanalizować unikatowy ciąg znaków, który jest sekwencją jednoznacznych dokumentów, i uzyskać drzewo analizy składniowej dla każdego lub jakiegoś uporządkowanego przedstawienia, ponieważ tak naprawdę nie mówisz, jak zdefiniowana jest składnia twoich dokumentów, skąd się ona bierze formalny punkt widzenia języka. To, co masz, to algorytm i tabele, które wykonają parsowanie po uruchomieniu na początku dokumentu. Niech tak będzie.

Rzeczywistym problemem jest to, że strumień dokumentów zawiera znaczne śmieci, które oddzielają dokumenty. Wygląda na to, że Twoim problemem jest wystarczająco szybkie skanowanie tych śmieci. Twoja obecna technika polega na tym, aby zacząć od początku i spróbować skanować od pierwszego znaku i przeskakiwać do ponownego uruchomienia od następnego znaku, gdy tylko się nie powiedzie, aż do zeskanowania całego dokumentu. Następnie powtarzasz stwierdzanie od pierwszego znaku po zeskanowaniu dokumentu.

Takie jest również rozwiązanie sugerowane przez @amona w drugiej części jego odpowiedzi .

To może nie być bardzo szybkie rozwiązanie (nie mam możliwości przetestowania), ponieważ jest mało prawdopodobne, aby kod parsera został zoptymalizowany pod kątem bardzo skutecznego uruchamiania na początku dokumentu. W normalnym użyciu robi to tylko raz, dzięki czemu nie jest gorącym punktem z punktu widzenia optymalizacji. Dlatego Twoje umiarkowane szczęście z tego rozwiązania nie jest zbyt zaskakujące.

Tak więc naprawdę potrzebujesz algorytmu, który może szybko znaleźć początek dokumentu, który zaczyna się od dużej ilości śmieci. I masz szczęście: takie algorytmy istnieją. I jestem pewien, że o tym wiesz: nazywa się to poszukiwanie REGEX.

Proste rozwiązanie

Musisz przeanalizować specyfikację swoich dokumentów, aby dowiedzieć się, jak te dokumenty się zaczynają. Nie mogę dokładnie powiedzieć, jak to zrobić, ponieważ nie jestem pewien, jak formalnie zorganizowana jest ich specyfikacja składniowa. Być może wszystkie zaczynają się od jakiegoś słowa ze skończonej listy, być może pomieszanego z interpunkcją lub cyframi. To jest do sprawdzenia.

Musisz zdefiniować automat skończony (FSA) lub równoważnie dla większości programistów wyrażenie regularne (REGEX), które może rozpoznać kilka pierwszych znaków dokumentu: im więcej, tym lepiej, ale nie musi być bardzo duże (ponieważ może to zająć czas i przestrzeń). Powinno to być względnie łatwe do wykonania ze specyfikacji dokumentów i prawdopodobnie można to zrobić automatycznie za pomocą programu, który odczytuje specyfikację dokumentów.

Po utworzeniu wyrażenia regularnego możesz uruchomić go w strumieniu wejściowym, aby bardzo szybko przejść do początku pierwszego (lub następnego) dokumentu w następujący sposób:

Zakładam:
- docstartjest wyrażeniem regularnym pasującym do początku wszystkich dokumentów
- search(regex, stream)jest funkcją, która wyszukuje streampasujący podciąg regex. Po zwróceniu strumień jest redukowany do swojego podrzędnego przyrostka rozpoczynającego się na początku pierwszego pasującego podciągu lub do pustego strumienia nie znaleziono dopasowania.
- parse(stream)próbuje parsować dokument od początku strumienia (co pozostało z niego) i zwraca drzewo parsowania w dowolnym formacie lub nie powiedzie się. Po zwróceniu strumień jest redukowany do podrzędnego przyrostka, zaczynając od pozycji znajdującej się bezpośrednio za końcem analizowanego dokumentu. W przypadku niepowodzenia analizy wywołuje wyjątek.

forest = empty_forest
search(docstart, stream)
while stream is not empty:
  try:
    forest = forest + parse(stream)
  except
    remove first character from stream
  search(docstart, stream)

Pamiętaj, że usunięcie pierwszego znaku jest konieczne, aby następne wyszukiwanie nie znalazło ponownie tego samego dopasowania.

Oczywiście skrócenie strumienia jest obrazem. Może to być tylko indeks w strumieniu.

Ostatnia uwaga jest taka, że ​​wyrażenie regularne nie musi być zbyt dokładne, o ile rozpoznaje wszystkie początki. Jeśli czasami rozpoznaje ciąg znaków, który nie może być początkiem dokumentu (fałszywie dodatni), jedyną karą jest koszt jednego bezużytecznego wywołania parsera.

Może to pomóc w uproszczeniu wyrażenia regularnego, jeśli jest to przydatne.

O możliwości szybszego rozwiązania

Powyższe rozwiązanie powinno działać całkiem dobrze w większości przypadków. Jeśli jednak masz naprawdę dużo śmieci i terabajtów pliku do przetworzenia, mogą istnieć inne algorytmy, które działają szybciej.

Pomysł wywodzi się z algorytmu wyszukiwania ciągów Boyera-Moore'a . Algorytm ten może bardzo szybko przeszukać strumień w poszukiwaniu pojedynczego ciągu, ponieważ wykorzystuje analizę strukturalną ciągu, aby pominąć czytanie większości strumienia, przeskakując fragmenty, nawet na nie nie patrząc. Jest to najszybszy algorytm wyszukiwania pojedynczego ciągu.

Trudność polega na tym, że jej dostosowanie do wyrażenia regularnego wyszukiwania, a nie pojedynczego łańcucha, wydaje się bardzo delikatne i może również nie działać, w zależności od funkcji wyrażenia regularnego, które rozważasz. To z kolei może zależeć od składni analizowanych dokumentów. Ale nie ufajcie mi zbytnio w tej sprawie, ponieważ nie miałem czasu na uważną lekturę znalezionych dokumentów.

Pozostawiam wam jeden lub dwa wskaźniki , które znalazłem w sieci, w tym jeden, który najwyraźniej jest recenzowanym artykułem badawczym , ale powinieneś rozważyć to jako bardziej spekulacyjne, być może badawcze, które należy wziąć pod uwagę tylko wtedy, gdy masz poważne problemy z wydajnością. I prawdopodobnie nie ma takiego programu półkowego, który to zrobiłby.

To, co opisujesz, można opisać jako SAX vs. SOM.

SAX - (Simple API for XML) to API parsera sekwencyjnego dostępu do zdarzeń opracowane przez listę mailingową XML-DEV dla dokumentów XML.

SOM - (XML Schema Object Model) losowy dostęp do reprezentacji pliku XML w pamięci

Istnieją implementacje obu typów w języku C # i Javie i prawdopodobnie wiele innych. Zwykle XSD lub DTD jest opcjonalne.

Radość SAX polega na tym, że jest to niewielki narzut pamięci, co jest świetne w przypadku dużych plików XML. Kompromis polega na tym, że losowy dostęp przy użyciu SAX jest albo nieistniejący, albo powolny, a co gorsza, czas programowania jest zwykle znacznie dłuższy niż w przypadku SOM. Oczywistym problemem związanym z SOM są potencjalnie duże wymagania pamięci RAM.

Ta odpowiedź nie dotyczy wszystkich platform i wszystkich języków.