#!/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?<@'] = '