¿Por qué es tan incorrecto usar un lexer / parser en datos binarios?

A menudo trabajo con lexer / parsers , a diferencia de un combinador de analizadores y veo personas que nunca tomaron una clase de análisis, preguntan sobre el análisis de datos binarios. Por lo general, los datos no solo son binarios, sino también sensibles al contexto. Básicamente, esto lleva a tener solo un tipo de token, un token para byte.

¿Alguien puede explicar por qué analizar datos binarios con un lexer / analizador es tan incorrecto con suficiente claridad para un estudiante de CS que no ha tomado una clase de análisis, pero con una base teórica?

En principio, no hay nada malo.

En la práctica,

• La mayoría de los formatos de datos no textuales que conozco no están libres de contexto y, por lo tanto, no son adecuados para generadores de analizadores comunes. La razón más común es que tienen campos de longitud que indican la cantidad de veces que una producción tiene que estar presente.

  Obviamente, tener un lenguaje sin contexto nunca ha impedido el uso de generadores de analizadores: analizamos un superconjunto del lenguaje y luego usamos reglas semánticas para reducirlo a lo que queremos. Ese enfoque podría usarse para formatos no textuales si el resultado fuera determinista. El problema es encontrar algo más que recuentos para sincronizar, ya que la mayoría de los formatos binarios permiten incrustar datos arbitrarios; los campos de longitud te dicen cuánto es.

  Luego puede comenzar a jugar trucos como tener un lexer escrito manualmente capaz de manejar eso con la retroalimentación del analizador (el manejo de lex / yacc de C usa ese tipo de trucos para manejar typedef, por ejemplo). Pero luego llegamos al segundo punto.

• La mayoría de los formatos de datos no textuales son bastante simples (incluso si no están libres de contexto). Cuando se ignoran los recuentos mencionados anteriormente, los idiomas son regulares, LL1 en el peor de los casos, y por lo tanto son muy adecuados para las técnicas de análisis manual. Y el manejo del conteo es fácil para las técnicas de análisis manual, como el descenso recursivo.

Clasifiquemos los datos en tres categorías: datos legibles por humanos (generalmente textos, que varían de libros a programas), datos destinados a ser leídos por computadoras y otros datos (análisis de imágenes o sonido).

Para la primera categoría, necesitamos procesarlos en algo que una computadora pueda usar. Como los lenguajes utilizados por los humanos generalmente pueden ser capturados relativamente bien por los analizadores sintácticos, generalmente usamos analizadores para esto.

Un ejemplo de datos en la tercera categoría sería una imagen escaneada de una página de un libro que desea analizar en texto. Para esta categoría, casi siempre necesita un conocimiento muy específico sobre su entrada y, por lo tanto, necesita un programa específico para analizarlo. La tecnología de análisis estándar no lo llevará muy lejos aquí.

Su pregunta es sobre la segunda categoría: si tenemos datos que están en binario, casi siempre es un producto de un programa de computadora, destinado a otro programa de computadora. Esto también significa inmediatamente que el programa responsable de su creación elige el formato en el que se encuentran los datos.

Los programas de computadora casi siempre producen datos en un formato que tiene una estructura clara. Si analizamos alguna entrada, esencialmente estamos tratando de descubrir la estructura de la entrada. Con datos binarios, esta estructura es generalmente muy simple y fácil de analizar por computadoras.

En otras palabras, normalmente es un desperdicio descubrir la estructura de una entrada para la que ya conoce la estructura. Como el análisis no es gratuito (lleva tiempo y agrega complejidad a su programa), esta es la razón por la cual el uso de lexers / analizadores en datos binarios es 'tan incorrecto'.

Si un lenguaje necesita analizarse de una manera no trivial, generalmente significa que los elementos estructurales deben coincidir, por lo que el idioma de entrada contiene redundancia , ya sea porque varias entradas se asignan al mismo árbol de análisis o porque algunas cadenas de entrada no son válidas. A los humanos les gusta la redundancia. Por ejemplo, la mayoría de los humanos encuentran que los operadores binarios son más legibles que un prefijo puro o una notación de sufijo para la aritmética elemental:$a + b \times (c - d) + e$en lugar de (+ a (* b (- c d)) e)o a b c d - * + e +. La notación matemática habitual tiene más redundancia que Lisp (que requiere más paréntesis, pero obtiene aridades variables de forma gratuita, por lo que requiere menos símbolos para expresar expresiones usando aridades grandes) o RPL (que nunca necesita paréntesis). Tal redundancia rara vez es útil para las computadoras, y donde lo es, es decir, cuando puede haber errores en los datos, la lógica de corrección de errores generalmente se mantiene separada del significado funcional de los datos, por ejemplo, utilizando códigos de corrección de errores que se aplican a secuencias de bytes independientemente de lo que representan.

Los formatos binarios generalmente están diseñados para ser compactos, lo que significa pocas características simples del lenguaje, como paréntesis equilibrados que se expresan mediante gramáticas libres de contexto. Además, a menudo es útil que las representaciones binarias de datos sean canónicas, es decir, que tengan una única representación de cada objeto. Esto descarta características a veces redundantes, como paréntesis. Otra consecuencia menos encomiable de tener menos redundancia es que si cada entrada es sintácticamente correcta, ahorra en la comprobación de errores.

Otro factor contra los analizadores no triviales para datos binarios es que muchos formatos binarios están diseñados para ser analizados por código de bajo nivel que le gusta operar en memoria constante con poca sobrecarga. Se prefieren los tamaños fijos cuando corresponde para permitir la repetición arbitraria de un elemento. Un formato como TLV que permite que un analizador de izquierda a derecha asigne primero la cantidad correcta de memoria para un objeto y luego lea la representación del objeto. Analizar de izquierda a derecha es una ventaja porque permite que los datos se procesen como vienen, sin búfer intermedio.