29
Conozco 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 el análisis de paquetes?
¿Qué es? ¿Vale la pena estudiar?
A
Respuesta
3
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 el FAQ page de la wiki de pyparsing, que también incluye enlaces a la tesis original de Bryan Ford sobre el análisis de paquetes.
27
El análisis de Packrat es una manera de proporcionar mejor rendimiento asintóticamente para parsing expression grammars (PEG); específicamente para PEGs, se puede garantizar el análisis linear time.
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, intenta adaptarse a otra posible las expresiones pueden beneficiarse de la aprobación/falla conocida de las subexpresiones en los puntos de la cadena donde ya se han probado.
Cuestiones relacionadas
- 1. ¿Qué es el análisis especulativo?
- 2. ¿Qué es el análisis de código estático?
- 3. ¿Qué Lisp es mejor en el análisis?
- 4. ¿Qué es el "análisis ad-hoc"?
- 5. Análisis monoidal - ¿qué es eso?
- 6. ¿Qué es la biblioteca de análisis de nombre de Java?
- 7. ¿por qué el análisis sax es más rápido que el análisis dom? y ¿cómo funciona el stax?
- 8. C++ ¿Por qué mi fecha de análisis no es insegura?
- 9. ¿Qué pasó con el explorador de paquetes en Eclipse?
- 10. ¿Por qué Socket.BeginReceive pierde paquetes de UDP?
- 11. tcpdump vs tcpflow (o "¿Por qué no es tcpdump datos de paquetes ASCII legibles por humanos?")
- 12. ¿Qué es un buen índice de mantenimiento utilizando el análisis de código de Visual Studio 2008?
- 13. ¿Qué herramientas de análisis de roscado recomiendan?
- 14. ¿Qué herramientas usas para el análisis de código estático?
- 15. ¿Cuál es el algoritmo de análisis de sentimiento existente?
- 16. El método de análisis de NSXMLParser es asincrónico
- 17. error de análisis de ocamlyacc: ¿qué token?
- 18. npm no instalará paquetes localmente. ¿Qué pasa?
- 19. ¿Qué contienen los paquetes * -dev en los repositorios de paquetes de Linux?
- 20. ¿Qué quiere decir la gente cuando dice "Perl es muy bueno en el análisis"?
- 21. Promedio de pérdida de paquetes UDP y reordenación de paquetes
- 22. ¿Es posible registrar paquetes dinámicamente en Symfony2?
- 23. Análisis de imágenes en R
- 24. Virtualenv: paquetes de sitio globales frente a los paquetes de sitio en el entorno virtual
- 25. ¿Qué es diferente acerca de los paquetes de Java EE? (SDK/normal frente a perfil web)
- 26. ¿Qué es un "análisis de montón de mapa de bits" en un plan de consulta?
- 27. ¿De qué versiones de paquetes puede depender mi paquete Haskell?
- 28. Asignación entre paquetes Oracle y paquetes Java
- 29. Número de análisis con el sufijo negativo
- 30. ¿Qué analizador HTML es el mejor?
Corrígeme si me equivoco, pero la posibilidad de intentar hacer coincidir varios símbolos diferentes no terminales en una posición dada (una característica de los PEG) implica también una búsqueda anticipada ilimitada. Esto significa que es posible que deba mantener porciones significativas de la entrada tokenizada en la memoria. ¿Derecha? – Honza
@Honza: Es una clásica compensación de tiempo/espacio. ¿Preferirías potencialmente seguir N rutas una tras otra antes de encontrar la correcta, o preferirías potencialmente seguir N rutas al mismo tiempo manteniendo cada una en la memoria? De cualquier manera, si mira demasiado lejos, apesta, y si no mira hacia adelante, no hay costo. Estoy seguro de que mi 2G ram lappy no va a sudar si miro hacia delante 1 token, 2 tokens, 3 tokens ... siempre y cuando no intentes analizar los lenguajes naturales, estarás bien. – efrey
Si se usa 'lazy vals' (Scala Parser Combinators), entonces ¿se ha logrado el' packrat de análisis '? En otras palabras, si estoy usando 'lazy val' para almacenar en caché los tokens ya analizados, ¿ya estoy usando' packrat parsing'? –