Tell me more ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.
up vote 2 down vote favorite

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

Input Specification
Input will come in from stdin 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 Specification

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

UPDATE

Sample Input
5 sets of balanced parentheses:

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

4 RPN (postfix) arithmetic expressions (note whitespace within strings is significant, whitespace elsewhere is not (the grammar spans multiple lines)):

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

Sample Output

First example (the empty string is in the language, so line 4 is intentionally blank):

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

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

Second example:

1535235 76451 +
973812
312 734 99 3 + / *
1 1 1 1 1 + - * +
share|improve this question
2  
Can we have some sample input/output? (I know the exact output would be different in every case, but just for reference). – Dogbert Feb 10 '11 at 10:46
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? – Joey Adams Feb 11 '11 at 3:00
1  
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". – Hoa Long Tam Feb 11 '11 at 3:13
The rules and examples don't seem to be entirely consistent on the amount of whitespace in the input. – Peter Taylor Feb 11 '11 at 15:19
@Peter: Whitespace outside of strings is insignificant; whitespace within strings is. – Hoa Long Tam Feb 11 '11 at 15:34
show 2 more comments

1 Answer

up vote 1 down vote accepted

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
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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