8
\$\begingroup\$

Write the shortest program you can in any language that reads a context-free grammar from and the number of sentences to produce from stdin, and generates that many random sentences from the grammar.

Input

Input will come in the following format:

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

n is the number of sentences to generate. <START> is identifier of the starting nonterminal symbol.

The grammar is enclosed in the {} and is formatted as follows:

  • Rules are of the form "<S>":[productions]. <S> is the identifier of the nonterminal.
    • Rules are delimited with commas.
    • The right-hand side of a rule is a double-quoted string whose first and last characters are "<" and ">", respectively. The remaining character should be in [A-Z] (upper-case alpha).
  • productions is a comma-delimited list of double-quoted strings, representing productions. All characters, including whitespace, in the rule are terminal symbols, except those that are enclosed in angle brackets ("<" and ">"), which are non-terminal symbols and will be the left-hand side of another rule. An open angle bracket may be escaped, but there is no need to escape a close angle bracket.
    • Productions will not contain newlines or the newline escape sequence.

Output

You should print each generated sentence to stdout with a trailing newline.

Test Cases
5 sets of balanced parentheses:

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

Example result:

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

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

4 postfix arithmetic expressions (note whitespace within strings is significant, whitespace elsewhere is not):

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

Example result:

1535235 76451 +
973812
312 734 99 3 + / *
1 1 1 1 1 + - * +
Improve this question
\$\endgroup\$
7
  • 2
    \$\begingroup\$ Can we have some sample input/output? (I know the exact output would be different in every case, but just for reference). \$\endgroup\$
    – Dogbert
    Commented Feb 10, 2011 at 10:46
  • \$\begingroup\$ Good challenge, but I think the input format is more complicated than it could be. Also, seeing as how the input format appears to be based primarily on JSON, wouldn't that give JavaScript and languages with built-in JSON parsing an unfair advantage. Also, what does the backslash in \<<T>> indicate? \$\endgroup\$
    – Joey Adams
    Commented Feb 11, 2011 at 3:00
  • 1
    \$\begingroup\$ The backslash escapes the open bracket, so if T produced "1", that the pattern \<<T>> would produce \<1>, which would produce a <1> as the final output. Yes, languages with JSON support would have a slight advantage, (though the escaped angle brackets should throw a wrench in that), but it at least levels the playing field for those languages not named "Perl". \$\endgroup\$
    – Hoa Long Tam
    Commented Feb 11, 2011 at 3:13
  • \$\begingroup\$ The rules and examples don't seem to be entirely consistent on the amount of whitespace in the input. \$\endgroup\$
    – Peter Taylor
    Commented Feb 11, 2011 at 15:19
  • \$\begingroup\$ @Peter: Whitespace outside of strings is insignificant; whitespace within strings is. \$\endgroup\$
    – Hoa Long Tam
    Commented Feb 11, 2011 at 15:34

1 Answer 1

Reset to default
5
\$\begingroup\$

I felt like doing a little JavaScript. Also, I cried a little on the inside when I wrote "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>

Input:

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

Output:

ccaaceeeeezeeeeedbbdd
accccceeeezeeeedddddb
aecezedeb
eaezebe
ccccaacezedbbdddd
eeeaaaceecacezedbdeedbbbeee
acaecaeaaeacccceeeeeeeaeeezeeebeeeeeeeddddbebbebdebdb
aaceezeedbb
aacezedbb
ceeaceecacaacezedbbdbdeedbeed
Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ I think you can shorten this a bit by writing d=document; and reusing the value afterwards. Also, you might want to provide the character count. \$\endgroup\$
    – Element118
    Commented Feb 9, 2016 at 7:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.