Warum ist die Verwendung eines Lexers / Parsers für Binärdaten so falsch?

Ich arbeite oft mit Lexer / Parser im Gegensatz zu einem Parser-Kombinator und sehe, dass Leute, die noch nie eine Klasse in Parsing besucht haben, nach dem Parsen von Binärdaten fragen. Typischerweise sind die Daten nicht nur binär, sondern auch kontextsensitiv. Dies führt im Grunde dazu, dass nur eine Art von Token vorhanden ist, ein Token für Byte.

Kann jemand erklären, warum das Parsen von Binärdaten mit einem Lexer / Parser so falsch ist, und zwar mit ausreichender Klarheit für einen CS-Studenten, der keine Parsing-Klasse besucht hat, aber theoretisch fundiert ist?

Im Prinzip gibt es nichts auszusetzen.

In der Praxis,

• Die meisten mir bekannten nicht-textuellen Datenformate sind nicht kontextfrei und daher nicht für gängige Parsergeneratoren geeignet. Der häufigste Grund ist, dass sie Längenfelder haben, die angeben, wie oft eine Produktion vorhanden sein muss.

  Offensichtlich hat eine nicht kontextfreie Sprache die Verwendung von Parser-Generatoren nie verhindert: Wir analysieren eine Obermenge der Sprache und verwenden dann semantische Regeln , um sie auf das zu reduzieren, was wir wollen. Dieser Ansatz könnte für nicht-textuelle Formate verwendet werden, wenn das Ergebnis deterministisch wäre. Das Problem besteht darin, etwas anderes als die Anzahl der zu synchronisierenden Elemente zu finden, da die meisten Binärformate die Einbettung beliebiger Daten ermöglichen. Längenfelder geben an, wie viel es ist.

  Sie können dann Streiche spielen, beispielsweise einen manuell geschriebenen Lexer, der mit dem Feedback des Parsers umgehen kann (lex / yacc-Behandlung von C verwendet diese Art von Stichen beispielsweise für typedef). Aber dann kommen wir zum zweiten Punkt.

• Die meisten nicht-textuellen Datenformate sind recht einfach (auch wenn sie nicht kontextfrei sind). Wenn die oben genannten Zählungen ignoriert werden, sind die Sprachen regulär, im schlimmsten Fall LL1, und eignen sich daher gut für manuelle Analysetechniken. Bei manuellen Analysetechniken wie dem rekursiven Abstieg ist die Handhabung einfach.

Lassen Sie uns Daten in drei Kategorien einteilen: Daten, die von Menschen gelesen werden können (normalerweise Texte, von Büchern bis zu Programmen), Daten, die von Computern gelesen werden sollen, und andere Daten (Analysieren von Bildern oder Ton).

Für die erste Kategorie müssen wir sie zu etwas verarbeiten, das ein Computer verwenden kann. Da die von Menschen verwendeten Sprachen von Parsern in der Regel relativ gut erfasst werden können, verwenden wir hierfür in der Regel Parser.

Ein Beispiel für Daten in der dritten Kategorie wäre ein gescanntes Bild einer Seite aus einem Buch, die Sie in Text zerlegen möchten. Für diese Kategorie benötigen Sie fast immer sehr spezifisches Wissen über Ihre Eingabe, und daher benötigen Sie ein spezifisches Programm, um diese zu analysieren. Mit der Standard-Parsing-Technologie kommen Sie hier nicht weit.

Ihre Frage bezieht sich auf die zweite Kategorie: Wenn wir binäre Daten haben, handelt es sich fast immer um ein Produkt eines Computerprogramms, das für ein anderes Computerprogramm bestimmt ist. Dies bedeutet sofort auch, dass das Format der Daten von dem Programm ausgewählt wird, das für deren Erstellung verantwortlich ist.

Computerprogramme erzeugen Daten fast immer in einem Format, das eine klare Struktur aufweist. Wenn wir eine Eingabe analysieren, versuchen wir im Wesentlichen, die Struktur der Eingabe herauszufinden . Bei binären Daten ist diese Struktur im Allgemeinen sehr einfach und kann von Computern leicht analysiert werden.

Mit anderen Worten, es ist normalerweise eine Verschwendung, die Struktur einer Eingabe herauszufinden, für die Sie die Struktur bereits kennen. Da das Parsen nicht kostenlos ist (es kostet Zeit und erhöht die Komplexität Ihres Programms), ist die Verwendung von Lexern / Parsern für Binärdaten „so falsch“.

Wenn eine Sprache auf eine nicht triviale Weise analysiert werden muss, bedeutet dies normalerweise, dass Strukturelemente abgeglichen werden müssen, sodass die Eingabesprache Redundanz enthält , entweder weil mehrere Eingaben demselben Analysebaum zugeordnet sind oder weil einige Eingabezeichenfolgen ungültig sind. Menschen mögen Redundanz. Beispielsweise finden die meisten Menschen Binäroperatoren lesbarer als eine reine Präfix- oder Suffixnotation für elementare Arithmetik:$a + b \times (c - d) + e$eher als (+ a (* b (- c d)) e)oder a b c d - * + e +. Die übliche mathematische Notation hat mehr Redundanz als Lisp (für die mehr Klammern erforderlich sind, die aber kostenlos variable Aritäten erhalten, sodass weniger Symbole zum Ausdrücken von Ausdrücken mit großen Aritäten erforderlich sind) oder RPL (für die keine Klammern erforderlich sind). Eine solche Redundanz ist für Computer selten nützlich - und wo sie sich befindet, wird die Fehlerkorrekturlogik normalerweise von der funktionalen Bedeutung der Daten getrennt gehalten, beispielsweise unter Verwendung von Fehlerkorrekturcodes, die für beliebige Daten gelten Bytefolgen, unabhängig davon, was sie darstellen.

Binärformate sind in der Regel kompakt gestaltet, was bedeutet, dass nur wenige einfache Sprachmerkmale wie ausgeglichene Klammern in kontextfreien Grammatiken ausgedrückt werden können. Darüber hinaus ist es häufig nützlich, dass binäre Darstellungen von Daten kanonisch sind, dh eine einzige Darstellung jedes Objekts haben. Dies schließt manchmal redundante Funktionen wie runde Klammern aus. Eine andere, weniger empfehlenswerte Folge der geringeren Redundanz ist, dass bei syntaktisch korrekten Eingaben die Fehlerprüfung eingespart wird.

Ein weiterer Faktor gegen nicht-triviale Parser für Binärdaten ist, dass viele Binärformate so konzipiert sind, dass sie von Low-Level-Code analysiert werden, der gerne in konstantem Speicher mit geringem Overhead arbeitet. Wenn möglich, werden feste Größen bevorzugt, um eine willkürliche Wiederholung eines Elements zu ermöglichen. Ein Format wie TLV , mit dem ein Parser von links nach rechts zuerst die richtige Speichermenge für ein Objekt zuweisen und dann die Darstellung des Objekts lesen kann. Das Parsen von links nach rechts ist von Vorteil, da die Daten ohne Zwischenpuffer direkt verarbeitet werden können.