2012-06-25 26 views
5

¿Es posible? ¿Alguna herramienta disponible para esto?Generando expresiones aleatorias pero aún válidas basadas en la gramática yacc/bison/ANTLR

+0

no ha recibido su pregunta, ¿está pidiendo este http://flex.sourceforge.net/ si no, entonces elabore –

+0

No, no sobre flexión. Ya sabes, yacc/bison/ANTLR analiza * expresiones * usando * gramática * específica. Necesito generar expresiones * aleatorias * válidas para * gramática * especificada. Por ejemplo, usando la gramática de la calculadora, me gustaría tener una herramienta para producir expresiones como "1 + 2 + 3", "1 + 4 * 8", etc., de forma infinita y aleatoria. –

+0

@ nav-jan: ¿por qué debería ser fácil? Las afirmaciones sin respaldo no son realmente útiles. (Bueno, un lenguaje de calculadora numérica podría ser fácil). –

Respuesta

2

yacc y bison convierten su gramática en una máquina de estados finitos. Debería poder atravesar la máquina de estados aleatoriamente para encontrar entradas válidas.

Básicamente, en cada estado puede cambiar un token nuevo a la pila y pasar a un nuevo estado o reducir el token superior en la pila en función de un conjunto de reducciones válidas. (Consulte el Bison manual para obtener detalles sobre cómo funciona esto).

Su generador aleatorio atravesará la máquina de estados realizando cambios o reducciones al azar pero válidos en cada estado. Una vez que alcanzas el estado terminal, tienes una entrada válida.

Para una descripción legible por humanos de los estados, puede usar la opción -v o --report=state para bisontar.

Me temo que no puedo indicarle ninguna herramienta existente que pueda hacer esto.

2

Puede hacerlo con cualquier sistema que le dé acceso a la gramática base. ANTLR y YACC recopilan tu gramática para que no la tengas más. En el caso de ANTLR, la gramática se convirtió en código; no vas a recuperarlo. En el caso de YACC, terminas con tablas de analizador, que contienen la esencia de la gramática; Podrías recorrer esas tablas sintácticas si las entendías lo suficientemente bien como para hacer lo que describo a continuación como.

Es bastante fácil atravesar un conjunto de reglas gramaticales explícitamente representadas y elegir al azar expansiones/derivaciones. Por definición, esto le dará una sintaxis válida.

Lo que no hará es que te valide código. El problema aquí es que la mayoría de los lenguajes realmente tienen sintaxis sensible al contexto; la mayoría de los programas no son válidos, a menos que los identificadores declarados se utilicen de forma coherente con sus reglas de declaración y alcance. Esto último requiere un control semántico completo.

Nuestro DMS Software Reengineering Toolkit se usa para analizar código en lenguajes arbitrarios [usando una gramática], crear AST, permite analizar y transformar esos árboles, y finalmente imprimir bastante el texto válido (sintáctico). DMS proporciona acceso directo a las reglas de gramática y las instalaciones de construcción de árboles, por lo que es bastante fácil generar árboles sintácticos aleatorios (y copias bonitas). Asegurarse de que sean semánticamente válidos también es difícil con DMS; sin embargo, muchos de los frontales de DMS pueden tomar un árbol (aleatorio) y hacer una comprobación semántica, por lo que al menos sabría si el árbol era semánticamente válido.

Lo que debe hacer si dice "no" sigue siendo un problema. Quizás pueda generar nombres de identificadores de manera que garanticen un uso al menos no inconsistente, pero sospecho que dependería del idioma.

+0

Sí, los nombres son una pregunta siguiente ... Necesito generar AST aleatorios hasta el primer paso. –

Cuestiones relacionadas