Trying to generate all sentences of a simple formal grammar

Question

I am new to python and trying to generate all sentences possible in the grammar. Here is the grammar:

  #set of non terminals
  N = ('<subject>', '<predicate>', '<noun phrase>', '<noun>', '<article>', '<verb>',   '<direct object>')
  #set of teminals

  T = ('the', 'boy', 'dog', 'bit')
  #productions
  P = [ ('Sigma',           ['<subject>', '<predicate>']), \
  ('<subject>',       ['<noun phrase>']),            \
  ('<predicate>',     ['<verb>']),                   \
  ('<predicate>',     ['<verb>','<direct object>']), \
  ('<noun phrase>',   ['<article>','<noun>']),       \
  ('<direct object>', ['<noun phrase>']),            \
  ('<noun>',          ['boy']),                      \
  ('<noun>',          ['dog']),                      \
  ('<article>',       ['the']),                      \
  ('<verb>',          ['bit'])                       ]

Here is my attempt, I am using a queue class to implement it methodically,

# language defined by the previous grammar.
Q = Queue()
Q.enqueue(['Sigma'])
found = 0
while 0 < len(Q):
    print "One while loop done"
    # Get the next sentential form
    sf = Q.dequeue()
    sf1 = [y for y in sf]
    for production in P:
        for i in range(len(sf1)):
                if production[0] == sf1[i]:
                        sf[i:i+1] = [x for x in production[1]]
                        Q.enqueue(sf)
                        Q.printQ()

I am getting in infinite loop, and also I am facing some issue with shallow-deep copy, if I change one copy of sf, everything in queue changes too. Any help is appreciated, any directions, tips would be great

Here is the expected output:

       The dog bit the boy
       The boy bit the dog
       The boy bit the boy
       The dog bit the dog
       The dog bit
       The boy bit

Answer 1

I am facing some issue with shallow-deep copy, if I change one copy of sf, everything in queue changes too

Yes. In Python, a list is an object with its own identity. So:

Q.enqueue(['Sigma'])

creates a (one-element) list and enqueues a reference to it.

sf = Q.dequeue()

pops that reference from Q and assigns it to variable 'sf'.

sf[i:i+1] = ...

makes a change to that list (the one that 'sf' refers to).

Q.enqueue(sf)

enqueues a reference to that same list.

So there's only one list object involved, and Q just contains multiple references to it.

Instead, you presumably want each entry in Q to be a reference to a separate list (sentential form), so you have to create a new list for each call to Q.enqueue.

Depending on how you fix that, there might or might not be other problems in the code. Consider:

(1) Each sentence has multiple derivations, and you only need to 'find' one (e.g., the leftmost derivation).

(2) In general, though not in your example grammar, a production's RHS might have more than one occurrence of a non-terminal (e.g. if COND then STMT else STMT), and those occurrences need not derive the same sub-forms.

(3) In general, a grammar can generate an infinite set of sentences.

---

By the way, to copy a list in Python, instead of saying

copy = [x for x in original]

it's simpler to say:

copy = original[:]

Answer 2

I created a simple grammar that allows to specify different sentences in terms of alternatives and options. Sentences that are described with that grammar can be parsed. The attributed grammar is described using Coco/R for which there is a python version (http://www.ssw.uni-linz.ac.at/Coco/#Others). I am more familiar with C# so I created a C# project here that can work as an example for you: https://github.com/abeham/Sentence-Generator.

For instance, parsing "(This | That) is a [nice] sentence" with the parser of that simple grammar creates four sentences: * This is a sentence * This is a nice sentence * That is a sentence * That is a nice sentence

Only finite sentences can be created with that grammar since there is no symbol for repetition.

I know that there already exists an accepted answer, but I hope that this answer will also be of value to those, like me, that arrived here looking for a generic solution. At least I didn't find anything like that on the web, which is why I created the github project.