Pourquoi l'utilisation d'un lexer / analyseur sur des données binaires est-elle si mauvaise?

Je travaille souvent avec lexer / parsers , par opposition à un combinateur d'analyseurs et je vois des gens qui n'ont jamais suivi de cours d'analyse, poser des questions sur l'analyse des données binaires. En règle générale, les données sont non seulement binaires, mais également contextuelles. Cela conduit à n'avoir qu'un seul type de jeton, un jeton pour octet.

Quelqu'un peut-il expliquer pourquoi l'analyse des données binaires avec un lexer / analyseur est si mal avec suffisamment de clarté pour un étudiant CS qui n'a pas pris de cours d'analyse, mais avec un pied sur la théorie?

En principe, il n'y a rien de mal.

En pratique,

• la plupart des formats de données non textuels que je connais ne sont pas sans contexte et ne conviennent donc pas aux générateurs d'analyseurs courants. La raison la plus courante est qu'ils ont des champs de longueur donnant le nombre de fois qu'une production doit être présente.

  De toute évidence, le fait d'avoir un langage non dépourvu de contexte n'a jamais empêché l'utilisation de générateurs d'analyseurs: nous analysons un surensemble du langage, puis utilisons des règles sémantiques pour le réduire à ce que nous voulons. Cette approche pourrait être utilisée pour les formats non textuels si le résultat était déterministe. Le problème est de trouver autre chose que des nombres sur lesquels se synchroniser car la plupart des formats binaires permettent d'incorporer des données arbitraires; les champs de longueur vous indiquent combien il est.

  Vous pouvez ensuite commencer à jouer des tours comme avoir un lexer écrit manuellement capable de gérer cela avec les commentaires de l'analyseur (la gestion lex / yacc de C utilise ce genre de tours pour gérer typedef, par exemple). Mais nous arrivons ensuite au deuxième point.

• la plupart des formats de données non textuels sont assez simples (même s'ils ne sont pas hors contexte). Lorsque les décomptes mentionnés ci-dessus sont ignorés, les langages sont réguliers, LL1 au pire, et sont donc bien adaptés aux techniques d'analyse manuelle. Et la gestion des nombres est facile pour les techniques d'analyse manuelle comme la descente récursive.

Classons les données en trois catégories: données lisibles par l'homme (généralement des textes, allant des livres aux programmes), données destinées à être lues par des ordinateurs et autres données (analyse d'images ou de son).

Pour la première catégorie, nous devons les transformer en quelque chose qu'un ordinateur peut utiliser. Comme les langages utilisés par les humains peuvent généralement être capturés relativement bien par les analyseurs, nous utilisons généralement des analyseurs pour cela.

Un exemple de données dans la troisième catégorie serait une image numérisée d'une page d'un livre que vous souhaitez analyser en texte. Pour cette catégorie, vous avez presque toujours besoin de connaissances très spécifiques sur votre entrée, et donc vous avez besoin d'un programme spécifique pour l'analyser. La technologie d'analyse standard ne vous mènera pas très loin ici.

Votre question concerne la deuxième catégorie: si nous avons des données en binaire, il s'agit presque toujours d'un produit d'un programme informatique, destiné à un autre programme informatique. Cela signifie également immédiatement que le format des données est choisi par le programme responsable de leur création.

Les programmes informatiques produisent presque toujours des données dans un format qui a une structure claire. Si nous analysons une entrée, nous essayons essentiellement de comprendre la structure de l'entrée. Avec les données binaires, cette structure est généralement très simple et facile à analyser par les ordinateurs.

En d'autres termes, il est normalement un peu inutile de comprendre la structure d'une entrée pour laquelle vous connaissez déjà la structure. Comme l'analyse n'est pas gratuite (cela prend du temps et ajoute de la complexité à votre programme), c'est pourquoi l'utilisation de lexers / parsers sur les données binaires est `` si mauvaise ''.

Si un langage doit être analysé d'une manière non triviale, cela signifie généralement que les éléments structurels doivent être mis en correspondance, de sorte que le langage d'entrée contient une redondance , soit parce que plusieurs entrées sont mappées vers le même arbre d'analyse, soit parce que certaines chaînes d'entrée ne sont pas valides. Les humains aiment la redondance. Par exemple, la plupart des humains trouvent les opérateurs binaires plus lisibles qu'une notation de préfixe ou de suffixe pur pour l'arithmétique élémentaire:$a + b \times (c - d) + e$plutôt que (+ a (* b (- c d)) e)ou a b c d - * + e +. La notation mathématique habituelle a plus de redondance que Lisp (qui nécessite plus de parenthèses, mais obtient des arités variables gratuitement, donc nécessite moins de symboles pour exprimer des expressions en utilisant de grandes arités) ou RPL (qui n'a jamais besoin de parenthèses). Une telle redondance est rarement utile aux ordinateurs - et là où elle se trouve, c'est-à-dire lorsqu'il peut y avoir des erreurs dans les données, la logique de correction des erreurs est généralement séparée de la signification fonctionnelle des données, par exemple en utilisant des codes de correction d'erreurs qui s'appliquent à l'arbitraire. séquences d'octets indépendamment de ce qu'elles représentent.

Les formats binaires sont généralement conçus pour être compacts, ce qui signifie peu de fonctionnalités de langage simples telles que des parenthèses équilibrées qui sont exprimables par des grammaires sans contexte. De plus, il est souvent utile que les représentations binaires des données soient canoniques, c'est-à-dire qu'elles aient une seule représentation de chaque objet. Cela exclut les fonctionnalités parfois redondantes telles que les parenthèses. Une autre conséquence moins louable d'avoir moins de redondance est que si chaque entrée est syntaxiquement correcte, elle économise sur la vérification des erreurs.

Un autre facteur contre les analyseurs non triviaux pour les données binaires est que de nombreux formats binaires sont conçus pour être analysés par du code de bas niveau qui aime fonctionner en mémoire constante avec peu de surcharge. Les tailles fixes sont préférables, le cas échéant, pour permettre la répétition arbitraire d'un élément. Un format tel que TLV qui permet à un analyseur de gauche à droite d'allouer d'abord la bonne quantité de mémoire pour un objet, puis de lire la représentation de l'objet. L'analyse de gauche à droite est un avantage car elle permet de traiter les données telles quelles, sans tampon intermédiaire.