algorithm - programacion - ¿Qué es el análisis de paquetes?

parser definicion

Question

Sé y uso bison / yacc. Pero en el mundo del análisis, hay un montón de rumores sobre el análisis de paquetes.

¿Qué es? ¿Vale la pena estudiar?

Answer 1

El análisis de Packrat es una forma de proporcionar un rendimiento asintóticamente mejor para analizar gramáticas de expresión (PEG); específicamente para PEG, se puede garantizar el análisis lineal del tiempo .

Básicamente, el análisis de Packrat solo significa almacenar en caché si las expresiones coinciden en la posición actual de la cadena cuando se prueban; esto significa que si el intento actual de encajar la cadena en una expresión falla, los intentos de encajar en otras expresiones posibles pueden beneficiarse de la aprobación / falla conocida de subexpresiones en los puntos en la cadena donde ya han sido probados.

Answer 2

Pyparsing es una biblioteca de análisis Python puro que admite el análisis de paquetes, por lo que puede ver cómo se implementa. Pyparsing utiliza una técnica de memorización para guardar intentos de análisis previos para una expresión de gramática particular en una ubicación particular en el texto de entrada. Si la gramática implica reintentar esa misma expresión en esa ubicación, omite la costosa lógica de análisis y solo devuelve los resultados o la excepción de la memoria caché.

Hay más información aquí en la página de preguntas frecuentes de la wiki de pyparsing, que también incluye enlaces a la tesis original de Bryan Ford sobre el análisis de paquetes.