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

13

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?

Guy Coder
quelle
Ich vermute, dass der Lexer wahrscheinlich keine Token finden kann, die kleiner als ein Byte / Wort sind. Wenn Sie es brauchen, bietet Erlang hervorragende Unterstützung für das Parsen von Binärdateien: user.it.uu.se/~pergu/papers/JFP_06.pdf
Dave Clarke
3
Ich glaube nicht, dass Ihre Annahme wahr ist. Nicht-kontextfreie Daten werfen natürlich Probleme auf (die häufig umgangen werden können), aber Sie können Grammatiken für binäre Wörter angeben. Sie werden wahrscheinlich keine gängigen Parser-Generatoren verwenden können, da diese eine Texteingabe voraussetzen. Das ist jedoch ein anderes Problem.
Raphael
@GuyCoder: Viele klassische Beispiele für Grammatiken verwenden binäre Alphabete, zB . S0S10S
Raphael
1
Übrigens: "nur eine Art von Token haben, ein Token für Byte." - Nun, nein, das würde Byte-Token ergeben. 28
Raphael
5
@GuyCoder: Alle Daten, die von einem anderen Programm erzeugt werden, können durch eine Grammatik beschrieben werden. Es kann jedoch sein, dass es nicht kontextfrei ist.
Raphael

Antworten:

10

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.

Ein Programmierer
quelle
"die sprachen sind normal" Wenn "aber auch kontextsensitiv" bedeutet, dass die binären Daten eine Grammatik sind, werde ich in der Antwort klarstellen. Das wird zu einem Teil des Problems; die Leute neigen dazu, Grammatiken oder normale Sprachen zu denken, sobald Sie
Guy Coder
7

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

Alex ten Brink
quelle
2
Dies ist eine schöne Perspektive, aber ich habe das Gefühl, dass sie die Frage nicht beantwortet.
Raphael
LANGSEC: Language-theoretic Securitybietet eine interessante Perspektive. In einem Artikel geht es um "seltsame Maschinen": Ad-hoc-Parser eines bekannten Formats, die die Eingabehandhabungseinrichtungen eines Systems bilden. Sie funktionieren möglicherweise nicht wie beabsichtigt. Aufgrund falscher Annahmen führt die fehlerhafte Maschine bei einer speziell gestalteten Eingabe unvorhergesehene Zustandsübergänge durch und führt Berechnungen durch, die nicht möglich sein sollten. Dies erzeugt einen Angriffsvektor. Die Verwendung formaler Grammatiken würde nachweislich korrekte Algorithmen ergeben.
Matheus Moreira
0

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:ein+b×(c-d)+eeher 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.

Gilles 'SO - hör auf böse zu sein'
quelle
Was ist der Sinn der ersten beiden Absätze? Auch wenn Sie keine Redundanz haben, benötigen Sie einen Parser. Auch der erste Absatz ist falsch: Es gibt Beispiele, in denen alle Wörter erlaubt sind, aber Sie analysieren, um die Struktur zu erhalten (z. B. Vorhersage der Sekundärstruktur von RNA).
Raphael
@Raphael Ein nicht-trivialer Parser impliziert normalerweise Redundanz (ja, wie Sie betonen, gibt es Ausnahmen). Ich hatte keine Sprachen in Betracht gezogen, die weder für Menschen noch für Computer gedacht waren. Dies ist ein interessantes Beispiel. In den ersten beiden Absätzen werden typische Unterschiede zwischen binären und von Menschen lesbaren Formaten erläutert (was normalerweise bedeutet, dass Sie nach Ausnahmen suchen, wenn Sie sie finden).
Gilles 'SO- hör auf böse zu sein'