Generando n sentencias de gramáticas libres de contexto

Question

Para no reinventar la rueda, me gustaría saber qué se ha hecho para generar sentencias aleatorias a partir de un lenguaje sin contexto (como los producidos por yacc, etc.). Estas gramáticas son principalmente para el análisis, pero tal vez alguien ha hecho una generación para probar los analizadores sintácticos. Gracias

Answer 1

Echa un vistazo this blog post. Básicamente, aleatoriza el RHS elegido en cada aplicación de regla.

Answer 2

Hay un antiguo pero todavía interesante artículo here que muestra por qué es necesario un poco más de las restricciones para la generación de efectivo de las penas al azar de lo que hacen para el análisis - También sugiere una forma sencilla de proporcionar esas restricciones adicionales y da una complete el programa de ejemplo (... en Fortran IV ... pero, oye, es es más de 40 años ...! -).

Desafortunadamente, no conozco ningún trabajo más reciente sobre este tema (o implementaciones en idiomas más modernos, pero la transcodificación de la cubierta polvorienta de Fortran al lenguaje que prefiera no debería ser tan difícil como llegar a estos conceptos por su cuenta ;-) - este es el tipo de material ya antiguo que analicé en las bibliotecas reales en papel cuando estaba en la universidad, y me sorprende que las herramientas de búsqueda en línea de la ACM me hayan permitido localizar la referencia Recordaba vagamente, tan rápidamente (¡felicitaciones, ACM! -). Nunca he hecho ninguna investigación original sobre este tema.

Answer 3

La generación de una secuencia de tokens aleatorios como este es una especie de strightforward; comenzando con el símbolo de objetivo, elija cualquier expansión aleatoria de no terminales sin llenar. Es probable que desee algún tipo de búsqueda por ramas y límites en cualquier rama del árbol de análisis sintáctico generado para que pueda controlar la profundidad/tamaño.

Pero no veo mucho valor en probar analizadores de esta manera, al menos no si su generador de analizadores acepta directamente la descripción de idioma sin contexto. Esto sucede cuando utiliza un generador/herramienta de analizador libre de contexto completo, como GLR (que es lo que usamos en nuestro sistema de transformación de programa, DMS) o un analizador de Earley.

Tiene otro problema: si desea probar un analizador, necesita alimentarlo como lo desea, y seguramente no se trata de tokens. Ahora debe generar lexemas válidos para las hojas de la terminal. Tampoco es demasiado difícil, pero si quisieras ser purista acerca de este enfoque, escribirías tu gramática en un estilo sin exploraciones.

Pero el último problema es que es difícil encontrar una gramática libre de contexto para la mayoría de los idiomas. Así que ahora también debes depurar tu gramática de oro; ¿cómo lo harás? Una vez que llegas a esa etapa, es probable que te rindas, depure el analizador y continúes con tu vida.

Generación de subárboles aleatorios es útil en la recuperación de errores, si puede empalmar en el árbol aleatorio para corregir la secuencia de origen. Hacemos una forma simplificada de esto para el analizador sintáctico de DMS, lo que significa que solo tenemos una pieza de maquinaria para el manejo de errores.