# A grammar is a set of rewrite rules:
import random

G1 = { 'ip': [('dp','i1')],
       'dp': [('d0','N0'),('N0',)],
       'i1': [('i0','vp')],
       'i0': [('will',),('can',),('should',)],
       'vp': [('v0','dp')],
       'v0': [('eat',),('kiss',),('trample',)],
       'd0': [('the',)],
       'N0' : [('mares',),('does',),('people',),('oats',)]
     }


def generate(cat,G):
    R = []
    if cat[-1]=='0': return random.choice(G[cat])[0]
    elif cat not in G:
        raise ValueError, 'Category not in grammar'
    else:
        Nu = random.choice(G[cat])
        return [generate(ct,G) for ct in Nu]