Generador de oraciones aleatorias

8

Escriba el programa más corto que pueda en cualquier idioma que lea una gramática libre de contexto y el número de oraciones para producir stdin, y genere tantas oraciones aleatorias de la gramática.

Entrada

La entrada vendrá en el siguiente formato:

n <START>
{"<A>":["as<A>df","0<A>","<B><C>","A<A>", ...], "<B>":["1<C>1","\<<T>>",...], ...}

nes el número de oraciones a generar. <START>es el identificador del símbolo no terminal inicial.

La gramática está encerrada en {} y tiene el siguiente formato:

  • Las reglas son de la forma "<S>":[productions]. <S>es el identificador del no terminal.
    • Las reglas están delimitadas con comas.
    • El lado derecho de una regla es una cadena entre comillas dobles cuyos primeros y últimos caracteres son "<" y ">", respectivamente. El carácter restante debe estar en [A-Z](mayúscula alfa).
  • productionses una lista delimitada por comas de cadenas entre comillas dobles, que representan producciones. Todos los caracteres, incluido el espacio en blanco, en la regla son símbolos terminales, excepto los que están encerrados entre paréntesis angulares ( "<"y ">"), que son símbolos no terminales y serán el lado izquierdo de otra regla. Se puede escapar un soporte de ángulo abierto, pero no hay necesidad de escapar de un soporte de ángulo cerrado.
    • Las producciones no contendrán nuevas líneas o la secuencia de escape de nueva línea.

Salida

Debe imprimir cada oración generada stdoutcon una nueva línea final.

Casos de prueba
5 conjuntos de paréntesis equilibrados:

5 <S>
{"<S>":["<S><S>", "(<S>)", ""]}

Resultado de ejemplo:

(())()
()
()()()

(())(()())((((()))()()))

4 expresiones aritméticas postfix (tenga en cuenta que el espacio en blanco dentro de las cadenas es significativo, el espacio en blanco en otro lugar no lo es):

4 <S>
{"<S>":["<N>", "<S> <S> <O>"], "<O>":["+","-","*","/"], "<N>":["<D><N>", "<D>"],
 "<D>":["1","2","3","4","5","6","7","8","9","0"]}

Resultado de ejemplo:

1535235 76451 +
973812
312 734 99 3 + / *
1 1 1 1 1 + - * +
code-golf string grammars Hoa Long Tam
fuente
2
¿Podemos tener alguna muestra de entrada / salida? (Sé que el resultado exacto sería diferente en cada caso, pero solo como referencia).
Dogbert
Buen desafío, pero creo que el formato de entrada es más complicado de lo que podría ser. Además, dado que el formato de entrada parece estar basado principalmente en JSON, ¿no le daría eso a JavaScript e idiomas con JSON incorporado una ventaja injusta? Además, ¿qué indica la barra diagonal inversa en \<<T>>?
Joey Adams
1
La barra invertida escapa del corchete abierto, por lo que si T produce "1", el patrón \<<T>>produciría \<1>, lo que produciría a <1>como salida final. Sí, los idiomas con soporte JSON tendrían una ligera ventaja (aunque los corchetes de escape deberían arrojar una llave en eso), pero al menos nivela el campo de juego para aquellos idiomas que no se llaman "Perl".
Hoa Long Tam
Las reglas y ejemplos no parecen ser completamente consistentes en la cantidad de espacios en blanco en la entrada.
Peter Taylor
@ Peter: el espacio en blanco fuera de las cadenas es insignificante; el espacio en blanco dentro de las cadenas es.
Hoa Long Tam

Respuestas:

4

Sentí ganas de hacer un poco de JavaScript. Además, lloré un poco por dentro cuando escribí "document.write"

<body>
    <script type='text/javascript'>
    function foo(){
        t=document.getElementById('ta').value.split("\n");
        eval('p='+t[1]);
        t[0]=t[0].split(' ');
        while(t[0][0]--) {
            s=t[0][1]
            while(x=s.match(/<\w+>/)) {
                ps=s;
                s=s.replace(x,p[x][Math.floor(Math.random()*p[x].length)]);
            }
            document.write(s+"<br>");
        }
    }
    </script>
    <textarea id='ta' cols='80'></textarea>
    <button onclick="foo()">go</button>
</body>

Entrada:

10 <A>
{"<A>":["a<A>b","c<A>d","<B>"],"<B>":["e<C>e"],"<C>":["z","<A>","<B>"]}

Salida:

ccaaceeeeezeeeeedbbdd
accccceeeezeeeedddddb
aecezedeb
eaezebe
ccccaacezedbbdddd
eeeaaaceecacezedbdeedbbbeee
acaecaeaaeacccceeeeeeeaeeezeeebeeeeeeeddddbebbebdebdb
aaceezeedbb
aacezedbb
ceeaceecacaacezedbbdbdeedbeed
Mitch
fuente
Creo que puede acortar esto un poco escribiendo d=document;y reutilizando el valor después. Además, es posible que desee proporcionar el recuento de caracteres.
Element118