#!/usr/bin/python
#
# unresistricted grammar with dictionary interface
# v.01
# Written by Shea Kauffman
#
# based upon the thue langauage by:
# John Colagioia
# and the interpreter by:
# Frederic van der Plancke
#
#
import string
def find_all(s, pattern):
"""return ordered list of indexes where [pattern] appears in [s];
"""
shift_on_match = 1
i = 0
indexes = []
while 1:
i = string.find(s, pattern, i)
if i >= 0:
indexes.append(i)
i = i + shift_on_match
else:
break
return indexes
class Rule:
def __init__(self, lhs, rhs, output=None):
self.lhs = lhs
self.rhs = rhs
self.output = output # UNUSED in current version
def __str__(self):
return "%s :- %s" % (self.lhs, self.rhs)
def __repr__(self):
return "Rule(%s,%s)" % (repr(self.lhs), repr(self.rhs))
class grammar:
def __init__(self):
self.rulebase = []
self.trace = False
def __call__(self, item):
while self[item] != item:
item = self[item]
return item
def __getitem__(self, tape):
matches = []
for rule in self.rulebase:
indices = find_all(tape, rule.lhs)
for i in indices:
matches.append((i, rule))
if len(matches) == 0:
if self.trace:
print tape
return tape
# print matches
(pos, rule) = min(matches)
endpos = pos + len(rule.lhs)
dataspace = tape[ : pos] + rule.rhs + tape[endpos : ]
if self.trace:
print tape, '->', dataspace
return dataspace
def __setitem__(self, lhs, rhs):
self.rulebase.append(Rule(lhs, rhs))
def __repr__(self):
ret = ''
for rule in self.rulebase:
ret = ret+'\n'+rule.__str__()
return ret
if __name__ == '__main__':
#TESTS:
#t1
t1 = grammar()
t1['ZZZ'] = '...'
#t2
t2 = grammar()
t2['0_']='0--'
t2['1_']='0'
t2['10--']='01'
t2['00--']='0--1'
t2['_1--']='@'
t2['_0--']='1'
t2['_0']=''
#t3
t3 = grammar()
t3['__']='Hello, World!'
#t4
t4 = grammar()
t4['1_']='1++'
t4['0_']='1'
t4['01++']='10'
t4['11++']='1++0'
t4['_0']='_'
t4['_1++']='10'
#t5
t5 = grammar()
t5['_+_'] = '<+|+>'
t5['+>0'] = '0?+>'
t5['+>1'] = '1?+>'
t5['+>_'] = '<@0C_'
t5['0<+'] = '<+0?'
t5['1<+'] = '<+1?'
t5['_<+'] = '_'
t5['0@0?'] = '0?0@'
t5['0@1?'] = '1?0@'
t5['1@0?'] = '0?1@'
t5['1@1?'] = '1?1@'
t5['0@|'] = '|0@'
t5['1@|'] = '|1@'
t5['0@0@0C'] = '<@0C0'
t5['0@0@1C'] = '<@0C1'
t5['0@1@0C'] = '<@0C1'
t5['0@1@1C'] = '<@1C0'
t5['1@0@0C'] = '<@0C1'
t5['1@0@1C'] = '<@1C0'
t5['1@1@0C'] = '<@1C0'
t5['1@1@1C'] = '<@1C1'
t5['0?<@'] = '<?0@'
t5['1?<@'] = '<?1@'
t5['0?<?'] = '<?0?'
t5['1?<?'] = '<?1?'
t5['|<?'] = '<@|'
t5['_<?'] = '_'
t5['0?|<@'] = '|0@0@'
t5['1?|<@'] = '|1@0@'
t5['_<@|'] = '_|0@'
t5['_|<@'] = '_'
t5['_0C'] = '_'
t5['_1C'] = '_1'
t1.trace = True
print t1
assert t1('ZZZZZZZZZZZZ') == '............'
t2.trace = True
print t2
assert t2('_1000000000000_') == '111111111111'
t3.trace = True
print t3
assert t3('__') == 'Hello, World!'
t4.trace = True
print t4
assert t4('_1111111111_') == '10000000000'
t5.trace = True
print t5
assert t5('_111100_+_10010_') == '_1001110_'
d = grammar()
d["server"]="mpilgrim"
d["database"]="master"
print d["server"] # mpilgrim
print d["database"] # master
print d["server is offline"] # mpilgrim is offline
print d["database server is offline"] # master server is offline
print d("database server is offline") # master mpilgrim is offline
