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

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?

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.

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”.

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 lub$a + b \times (c - d) + 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.