Dlaczego używanie leksykera / parsera na danych binarnych jest tak nieprawidłowe?

13

Często pracuję z lexer / parserami , w przeciwieństwie do kombinatora parserów i widzę osoby, które nigdy nie brały udziału w analizie składniowej, pytają o przetwarzanie danych binarnych. Zazwyczaj dane są nie tylko binarne, ale także kontekstowe. Zasadniczo prowadzi to do posiadania tylko jednego rodzaju tokena, tokena bajtu.

Czy ktoś może wyjaśnić, dlaczego analizowanie danych binarnych za pomocą leksera / parsera jest tak błędne, z wystarczającą jasnością dla studenta CS, który nie wziął udziału w analizie, ale opierając się na teorii?

Guy Coder
źródło
Domyślam się, że leksykon prawdopodobnie nie może znaleźć tokenów, które są mniejsze niż bajt / słowo. W razie potrzeby Erlang ma doskonałe wsparcie dla parsowania plików binarnych: user.it.uu.se/~pergu/papers/JFP_06.pdf
Dave Clarke
3
Nie sądzę, aby twoje założenie było prawdziwe. Oczywiście, nie bezkontekstowych Poses danych problemów (co może być często circumvente), ale może dać gramatyk dla słów binarnych. Prawdopodobnie nie będzie mógł korzystać z popularnych generatorów parsera, jak te zakładają wprowadzanie tekstu. To jednak inna kwestia.
Raphael
@GuyCoder: Wiele klasycznych przykładów gramatyki wykorzystuje alfabet binarny, np. . S0S10S
Raphael
1
Nawiasem mówiąc: „mając tylko jeden typ tokena, token bajtu”. - no nie, to dałoby bajtów tokenów. 28
Raphael
5
@GuyCoder: Wszystkie dane generowane przez inny program można opisać gramatyką. Jednak może nie być kontekstem.
Raphael

Odpowiedzi:

10

W zasadzie nie ma nic złego.

W praktyce,

  • większość nietekstowych formatów danych, które znam, nie są kontekstowe i dlatego nie są odpowiednie dla popularnych generatorów parserów. Najczęstszym powodem jest to, że mają pola długości określające, ile razy produkcja musi być obecna.

    Oczywiście posiadanie języka bezkontekstowego nigdy nie uniemożliwiło użycia generatorów analizatora składni: analizujemy nadzbiór języka, a następnie używamy reguł semantycznych, aby zredukować go do tego, czego chcemy. Takie podejście można zastosować w przypadku formatów nietekstowych, jeśli wynik byłby deterministyczny. Problem polega na znalezieniu czegoś innego niż liczy się synchronizacja, ponieważ większość formatów binarnych pozwala na osadzenie dowolnych danych; pola długości określają, ile to jest.

    Następnie możesz zacząć grać w sztuczki, takie jak posiadanie ręcznie napisanego leksera, który jest w stanie sobie z tym poradzić za pomocą informacji zwrotnej od analizatora składni (na przykład obsługa języka C / Lex w yacc używa tego rodzaju sztuczek do obsługi typedef). Ale potem dochodzimy do drugiego punktu.

  • większość nietekstowych formatów danych jest dość prosta (nawet jeśli nie są one kontekstowe). Gdy powyższe liczby są ignorowane, języki są regularne, w najgorszym LL1, a zatem dobrze nadają się do ręcznych technik parsowania. Obsługa obliczeń jest łatwa w przypadku ręcznych technik parsowania, takich jak rekurencyjne zejście.

AProgrammer
źródło
„języki są zwykłe” Jeśli „, ale także kontekstowe” oznacza, że ​​dane binarne są gramatyką, wyjaśnię to w odpowiedzi. To dotyczy części problemu; ludzie zwykle myślą gramatyki lub zwykłe języki wzmiankę o parserze
Guy Coder
7

Podzielmy dane na trzy kategorie: dane czytelne dla ludzi (zwykle teksty, od książek do programów), dane przeznaczone do odczytu przez komputery i inne dane (parsowanie obrazów lub dźwięku).

W przypadku pierwszej kategorii musimy je przetworzyć na coś, czego może użyć komputer. Ponieważ języki używane przez ludzi na ogół mogą być przechwycone przez parsery, zwykle używamy do tego parserów.

Przykładem danych w trzeciej kategorii może być zeskanowany obraz strony z książki, który chcesz przetworzyć na tekst. W tej kategorii prawie zawsze potrzebujesz bardzo szczegółowej wiedzy na temat swoich danych wejściowych, dlatego potrzebujesz konkretnego programu do ich analizy. Standardowa technologia analizy nie zaprowadzi cię daleko.

Twoje pytanie dotyczy drugiej kategorii: jeśli mamy dane w formacie binarnym, prawie zawsze jest to produkt programu komputerowego, przeznaczony dla innego programu komputerowego. To natychmiast oznacza również, że format danych jest wybierany przez program odpowiedzialny za jego utworzenie.

Programy komputerowe prawie zawsze wytwarzają dane w formacie o przejrzystej strukturze. Jeśli parsujemy jakieś dane wejściowe, zasadniczo próbujemy ustalić ich strukturę . W przypadku danych binarnych ta struktura jest na ogół bardzo prosta i łatwa do przeanalizowania przez komputery.

Innymi słowy, zwykle trochę marnotrawstwem jest ustalenie struktury danych wejściowych, dla których już znasz tę strukturę. Ponieważ parsowanie nie jest darmowe (zajmuje dużo czasu i zwiększa złożoność programu), dlatego używanie lexerów / parserów na danych binarnych jest „tak złe”.

Alex ten Brink
źródło
2
To ładna perspektywa, ale wydaje mi się, że nie odpowiada na pytanie.
Raphael
LANGSEC: Language-theoretic Securityoferuje ciekawą perspektywę. Jeden z artykułów mówi o „dziwnych maszynach”: parserach ad hoc o znanym formacie, tworzących funkcje obsługi danych wejściowych systemu. Mogą one faktycznie nie działać zgodnie z przeznaczeniem. Z powodu niepoprawnych założeń uszkodzona maszyna wykona nieprzewidziane przejścia stanu na podstawie specjalnie spreparowanych danych wejściowych, wykonując obliczenia, które nie powinny być możliwe. To tworzy wektor ataku. Korzystanie z gramatyki formalnej dałoby możliwe do udowodnienia poprawne algorytmy.
Matheus Moreira,
0

Jeśli język musi zostać przeanalizowany w jakiś nietrywialny sposób, zwykle oznacza to, że elementy strukturalne muszą zostać dopasowane, więc język wejściowy zawiera redundancję , ponieważ wiele danych wejściowych jest odwzorowanych na to samo drzewo analizy lub ponieważ niektóre ciągi wejściowe są nieprawidłowe. Ludzie lubią redundancję. Na przykład większość ludzi uważa, że ​​operatory binarne są bardziej czytelne niż czysty przedrostek lub notacja sufiksu dla elementarnej arytmetyki: zamiast luba+b×(cd)+e(+ a (* b (- c d)) e)a b c d - * + e +. Zwykła notacja matematyczna ma większą redundancję niż Lisp (która wymaga więcej nawiasów, ale otrzymuje zmienne ariesze za darmo, więc wymaga mniej symboli do wyrażania wyrażeń przy użyciu dużych arian) lub RPL (która nigdy nie potrzebuje nawiasów). Taka nadmiarowość rzadko jest przydatna dla komputerów - a tam, gdzie to jest, kiedy mogą wystąpić błędy w danych, logika korekcji błędów jest zwykle oddzielona od funkcjonalnego znaczenia danych, na przykład za pomocą kodów korekcji błędów, które mają zastosowanie do dowolnych sekwencje bajtów niezależnie od tego, co reprezentują.

Formaty binarne są zwykle zaprojektowane tak, aby były zwarte, co oznacza kilka prostych funkcji językowych, takich jak zrównoważone nawiasy, które są wyrażane przez gramatyki bezkontekstowe. Ponadto często przydatne jest, aby binarne reprezentacje danych były kanoniczne, tj. Miały jedną reprezentację każdego obiektu. Wyklucza to czasami zbędne funkcje, takie jak nawiasy. Inną, mniej godną pochwały konsekwencją mniejszej nadmiarowości jest to, że jeśli każde wejście jest poprawne pod względem składniowym, oszczędza to sprawdzania błędów.

Innym czynnikiem przeciwko nietrywialnym parserom danych binarnych jest to, że wiele formatów binarnych zaprojektowano do analizowania za pomocą kodu niskiego poziomu, który lubi pracować w stałej pamięci z niewielkim narzutem. Stałe rozmiary są preferowane, gdy ma to zastosowanie, aby umożliwić dowolne powtórzenie elementu. Format taki jak TLV, który umożliwia parserowi od lewej do prawej przydzielenie najpierw odpowiedniej ilości pamięci dla obiektu, a następnie odczytanie reprezentacji obiektu. Analiza od lewej do prawej jest zaletą, ponieważ pozwala na przetwarzanie danych w stanie, w jakim się znajdują, bez bufora pośredniego.

Gilles „SO- przestań być zły”
źródło
Jaki jest sens dwóch pierwszych akapitów? Nawet jeśli nie masz redundancji, potrzebujesz parsera. Również pierwszy akapit jest błędny: istnieją przykłady, w których wszystkie słowa są dozwolone, ale analizujesz, aby uzyskać strukturę (np. Przewidywanie struktury wtórnej RNA).
Raphael
@Raphael Nietrywialny parser zwykle oznacza redundancję (tak, jak zauważyłeś, są wyjątki). Nie rozważałem języków, które nie zostały zaprojektowane ani dla ludzi, ani dla komputerów, to ciekawy przykład. Pierwsze dwa akapity omawiają typowe różnice między formatami binarnymi i czytelnymi dla człowieka (typowe oznacza, że ​​jeśli szukasz wyjątków, znajdziesz je).
Gilles 'SO - przestań być zły'