Generator Kalimat Acak

8

Tulis program terpendek yang dapat Anda gunakan dalam bahasa apa pun yang membaca tata bahasa bebas konteks dari dan jumlah kalimat yang dihasilkan stdin, dan menghasilkan banyak kalimat acak dari tata bahasa.

Memasukkan

Input akan datang dalam format berikut:

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

nadalah jumlah kalimat yang dihasilkan. <START>adalah pengidentifikasi simbol nonterminal awal.

Tata bahasanya terlampir dalam {} dan diformat sebagai berikut:

  • Aturannya berbentuk "<S>":[productions]. <S>adalah pengidentifikasi nonterminal.
    • Aturan dibatasi dengan koma.
    • Sisi kanan aturan adalah string yang dikutip ganda, yang karakter pertama dan terakhirnya masing-masing "<" dan ">". Karakter yang tersisa harus dalam [A-Z](huruf besar alfa).
  • productionsadalah daftar koma dari string ganda dikutip, mewakili produksi. Semua karakter, termasuk spasi putih, dalam aturan adalah simbol terminal, kecuali yang tertutup dalam tanda kurung sudut ( "<"dan ">"), yang merupakan simbol non-terminal dan akan menjadi sisi kiri dari aturan lain. Braket sudut terbuka dapat diloloskan, tetapi tidak perlu melepaskan diri dari braket sudut dekat.
    • Productions tidak akan mengandung baris baru atau urutan pelarian baris baru.

Keluaran

Anda harus mencetak setiap kalimat yang dihasilkan stdoutdengan baris baru tambahan.

Test Case
5 set tanda kurung seimbang:

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

Contoh hasil:

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

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

4 ekspresi aritmatika postfix (perhatikan spasi putih dalam string adalah signifikan, spasi putih di tempat lain tidak):

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

Contoh hasil:

1535235 76451 +
973812
312 734 99 3 + / *
1 1 1 1 1 + - * +
Hoa Long Tam
sumber
2
Bisakah kita memiliki beberapa input / output sampel? (Saya tahu keluaran pasti akan berbeda dalam setiap kasus, tetapi hanya untuk referensi).
Dogbert
Tantangan bagus, tapi saya pikir format input lebih rumit daripada yang seharusnya. Juga, mengingat bagaimana format input tampaknya didasarkan terutama pada JSON, bukankah itu memberikan JavaScript dan bahasa dengan JSON bawaan yang menguraikan keuntungan yang tidak adil. Juga, apa yang \<<T>>diindikasikan oleh garis miring terbalik ?
Joey Adams
1
Garis miring terbalik dari braket terbuka, jadi jika T menghasilkan "1", bahwa pola \<<T>>akan menghasilkan \<1>, yang akan menghasilkan a <1>sebagai hasil akhir. Ya, bahasa dengan dukungan JSON akan memiliki sedikit keuntungan, (meskipun kurung sudut yang lolos harus melemparkan kunci pas dalam hal itu), tetapi setidaknya tingkat lapangan bermain untuk bahasa yang tidak disebut "Perl".
Hoa Long Tam
Aturan dan contoh tampaknya tidak sepenuhnya konsisten pada jumlah spasi putih pada input.
Peter Taylor
@ Peter: Ruang kosong di luar string tidak signifikan; spasi dalam string adalah.
Hoa Long Tam

Jawaban:

4

Saya merasa ingin melakukan sedikit JavaScript. Juga, saya menangis sedikit di dalam ketika saya menulis "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>

Memasukkan:

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

Keluaran:

ccaaceeeeezeeeeedbbdd
accccceeeezeeeedddddb
aecezedeb
eaezebe
ccccaacezedbbdddd
eeeaaaceecacezedbdeedbbbeee
acaecaeaaeacccceeeeeeeaeeezeeebeeeeeeeddddbebbebdebdb
aaceezeedbb
aacezedbb
ceeaceecacaacezedbbdbdeedbeed
Mitch
sumber
Saya pikir Anda dapat mempersingkat ini sedikit dengan menulis d=document;dan menggunakan kembali nilai setelahnya. Juga, Anda mungkin ingin memberikan jumlah karakter.
Element118