Source Code for Module nltk.parse.generate

 1  # Natural Language Toolkit: Generating from a CFG 
 2  # 
 3  # Copyright (C) 2001-2008 NLTK Project 
 4  # Author: Steven Bird <[email protected]> 
 5  # URL: <http://nltk.org> 
 6  # For license information, see LICENSE.TXT 
 7  # 
 8   
 9  from nltk import cfg 
10   
11 -def generate(grammar, start=None): 
12      if not start: 
13          start = grammar.start() 
14      return _generate_all(grammar, [start])[0] 
15   
16 -def _generate_all(grammar, items): 
17      frags = [] 
18      if len(items) == 1: 
19          if isinstance(items[0], cfg.Nonterminal): 
20              for prod in grammar.productions(lhs=items[0]): 
21                  frags.append(_generate_all(grammar, prod.rhs())) 
22          else: 
23              frags.append(items[0]) 
24      else: 
25          for frag1 in _generate_all(grammar, [items[0]]): 
26              for frag2 in _generate_all(grammar, items[1:]): 
27                  for frag in _multiply(frag1, frag2): 
28                      frags.append(frag) 
29      return frags 
30               
31 -def _multiply(frag1, frag2): 
32      frags = [] 
33      if len(frag1) == 1: 
34          frag1 = [frag1] 
35      if len(frag2) == 1: 
36          frag2 = [frag2] 
37      for f1 in frag1: 
38          for f2 in frag2: 
39              frags.append(f1+f2) 
40      return frags 
41   
42  grammar = cfg.parse_cfg(""" 
43    S -> NP VP 
44    NP -> Det N 
45    VP -> V NP 
46    Det -> 'the' 
47    Det -> 'a' 
48    N -> 'man' | 'park' | 'dog' | 'telescope' 
49    V -> 'saw' | 'walked' 
50    P -> 'in' | 'with' 
51  """) 
52   
53  for sent in generate(grammar): 
54      print sent 
55