title: How can I generate all possible strings given a grammar rule?
body: <p>I would like to, given a JSGF grammar, generate all the terminal strings it would map to. For example, given <code>A (B | C) D [E]</code>, my desired output would be:</p>
  
  <pre><code>A B D E
  A C D E
  A B D
  A C D
  </code></pre>
  
  <p>I decided to start with the easiest item, the optional brackets, but soon ran into a brick wall. It sort of works for 1 item, but not for an item with alternatives. Any advice would be appreciated. </p>
  
  <p>What I have now: </p>
  
  <pre><code>import re
  rule = raw_input('Enter the rule you want to test: ')
  items = re.findall(r"\w[\w ]*\w|\w|\[|\]|\(|\)", rule)
  for anitem in range(len(items)):
      bracketc = items[:anitem].count('[') - items[:anitem].count(']')
      if items[anitem] != '[' and items[anitem] != ']':
          if bracketc &gt; 0:
              optional = True
          else:
              optional = False
          while optional == True:
              print ' '.join(items)
              it2 = items[:]
              it2.remove(it2[anitem])
              print ' '.join(it2)
              break
  </code></pre>
  
  <p>It works for 1 item, and given a string A B [C] D, returns:</p>
  
  <pre><code>A B [ C ] D
  A B [ ] D
  </code></pre>
  
  <p>but breaks down at increasing complexity, so I am guessing I need something completely different. </p>