1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
|
import types
from prng import prng
class SymbolError(Exception):
""" Error finding a symbol.
"""
class DepthError(Exception):
""" Tree tried to grow beyond the configured maximum depth.
"""
class language(object):
max_depth = 20
dont_cross = ['ST'] # dont perform crossovers at the start symbol node
def __init__(self,lang):
self.lang = lang
self.dsc = 0
def generate(self):
new = self._gen()
new.generate_symbol_table()
return new
def _gen(self, cur_sym = 'ST', active_node = None, depth = 0):
#short circuit really large trees
if(active_node and depth > self.max_depth):
self.dsc = self.dsc + 1
active_node.root().delete_circulars()
raise DepthError
depth = depth + 1
#reset derivation symbol
if(str(cur_sym) == 'ST' or self.derive_type == ''):
if(type(cur_sym) == types.StringType):
self.derive_type = cur_sym
else: self.derive_type = cur_sym.node_type
new_active_node = active_node
if type(cur_sym) == types.StringType:
if self.lang.has_key(cur_sym):
rule = prng.choice(self.lang[cur_sym])
for sym in rule:
new_active_node = self._gen(sym,new_active_node,depth)
else:
active_node.root().delete_circulars()
raise SymbolError, "non-terminal symbol not found:%s" % cur_sym
else:
parent = new_active_node
new_active_node = cur_sym.create(parent)
new_active_node.derive_type = self.derive_type
self.derive_type = ''
if parent:
parent.add_child(new_active_node)
while new_active_node.filled() and new_active_node.get_parent():
new_active_node =new_active_node.get_parent()
return new_active_node
|
