Gerador de frases aleatórias

8

Escreva o programa mais curto possível em qualquer idioma que leia uma gramática livre de contexto e o número de frases a serem produzidas stdine gere muitas frases aleatórias a partir da gramática.

Entrada

A entrada virá no seguinte formato:

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

né o número de frases a serem geradas. <START>é o identificador do símbolo não terminal inicial.

A gramática está entre {} e está formatada da seguinte maneira:

  • As regras são da forma "<S>":[productions]. <S>é o identificador do não-terminal.
    • As regras são delimitadas por vírgulas.
    • O lado direito de uma regra é uma sequência de aspas duplas cujos primeiro e último caracteres são "<" e ">", respectivamente. O caractere restante deve estar em [A-Z](letra maiúscula alfa).
  • productionsé uma lista delimitada por vírgula de seqüências de caracteres com aspas duplas, representando produções. Todos os caracteres, incluindo o espaço em branco, na regra são símbolos terminais, exceto aqueles que estão entre colchetes angulares ( "<"e ">"), que são símbolos não terminais e serão o lado esquerdo de outra regra. Um suporte de ângulo aberto pode ser escapado, mas não há necessidade de escapar de um suporte de ângulo fechado.
    • As produções não conterão novas linhas ou a sequência de escape da nova linha.

Resultado

Você deve imprimir cada frase gerada stdoutcom uma nova linha à direita.

Casos de teste
5 conjuntos de parênteses balanceados:

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

Resultado de exemplo:

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

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

4 expressões aritméticas postfix (observe que o espaço em branco nas cadeias é significativo, o espaço em outro lugar não é):

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 exemplo:

1535235 76451 +
973812
312 734 99 3 + / *
1 1 1 1 1 + - * +
code-golf string grammars Hoa Long Tam
fonte
2
Podemos ter alguma amostra de entrada / saída? (Eu sei que a saída exata seria diferente em todos os casos, mas apenas para referência).
Dogbert
Bom desafio, mas acho que o formato de entrada é mais complicado do que poderia ser. Além disso, vendo como o formato de entrada parece se basear principalmente no JSON, isso não daria ao JavaScript e aos idiomas o JSON interno uma análise injusta da vantagem. Além disso, o que a barra invertida \<<T>>indica?
Joey Adams
1
A barra invertida escapa do suporte aberto, portanto, se T produz "1", o padrão \<<T>>produziria \<1>, o que produziria a <1>como saída final. Sim, os idiomas com suporte a JSON teriam uma pequena vantagem (embora os colchetes angulares escapados devessem ser uma chave nisso), mas pelo menos nivela o campo de jogo para os idiomas não nomeados "Perl".
Hoa Long Tam
As regras e exemplos não parecem ser totalmente consistentes com a quantidade de espaço em branco na entrada.
Peter Taylor
@ Peter: O espaço em branco fora das strings é insignificante; espaço em branco dentro de strings é.
Hoa Long Tam

Respostas:

4

Eu senti vontade de fazer um pouco de JavaScript. Além disso, chorei um pouco por dentro quando escrevi "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>"]}

Resultado:

ccaaceeeeezeeeeedbbdd
accccceeeezeeeedddddb
aecezedeb
eaezebe
ccccaacezedbbdddd
eeeaaaceecacezedbdeedbbbeee
acaecaeaaeacccceeeeeeeaeeezeeebeeeeeeeddddbebbebdebdb
aaceezeedbb
aacezedbb
ceeaceecacaacezedbbdbdeedbeed
Mitch
fonte
Eu acho que você pode reduzir um pouco isso escrevendo d=document;e reutilizando o valor posteriormente. Além disso, você pode fornecer a contagem de caracteres.
precisa