#!/usr/bin/env python # # unresistricted grammar with dictionary interface # v.11 # Written by Shea Kauffman # # based upon the thue langauage by: # John Colagioia # and the interpreter by: # Frederic van der plancke # # import string, re def find_all(s, pattern): """ return ordered list of indexes where [pattern] appears in [s]; """ shift_on_match = 1 indexes = [] i = re.search(pattern, s) if i: i, j, k = i.start(), i.end(), i.groups() indexes.append((i,j,k)) return indexes class Rule: def __init__(self, lhs, rhs, output=None): self.lhs = lhs self.rhs = rhs 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(object): rulebase = () def __init__(self, rules=()): self.rulebase = tuple(rules) self.trace = False def __call__(self, item): prev = None while prev != item: prev = item item = self[item] return item def __getitem__(self, tape): (match, rule) = self._matches(tape) if not match: '''If there are no matches then we're done''' if self.trace: print tape return tape startpos, endpos, matched = match middledata = self._transform(matched, rule) dataspace = tape[ : startpos] + middledata + tape[endpos : ] if self.trace: print tape, '->', dataspace, '\t\t::\t', rule return dataspace def __setitem__(self, lhs, rhs): self.rulebase = self.rulebase + (Rule(lhs, rhs), ) def __repr__(self): return '\n'.join([rule.__str__() for rule in self.rulebase]) def __add__(self, other): newg = grammar(self.rulebase+other.rulebase) newg.trace = self.trace and other.trace return newg def _matches(self, tape): '''iterate through rules returning first match''' for rule in self.rulebase: for i in find_all(tape, rule.lhs): return i, rule return False, None def _transform(self, matched, rule): if not matched: return rule.rhs return rule.rhs(*matched) if callable(rule.rhs) else rule.rhs % matched if __name__ == '__main__': TRACES = True #TESTS: #lengthdiv3 lengthdiv3 = grammar() lengthdiv3['ZZZ'] = '...' lengthdiv3.trace = TRACES assert lengthdiv3('ZZZZZZZZZZZZ') == '............' #bitshift bitshift = grammar() bitshift['0_']='0--' bitshift['1_']='0' bitshift['10--']='01' bitshift['00--']='0--1' bitshift['_1--']='@' bitshift['_0--']='1' bitshift['_0']='' bitshift.trace = TRACES assert bitshift('_1000000000000_') == '111111111111' #helloworld helloworld = grammar() helloworld['__']='Hello, World!' helloworld.trace = TRACES assert helloworld('__') == 'Hello, World!' #binarysucc binarysucc = grammar() binarysucc['1_']='1++' binarysucc['0_']='1' binarysucc['01\+\+']='10' binarysucc['11\+\+']='1++0' binarysucc['_0']='_' binarysucc['_1\+\+']='10' binarysucc.trace = TRACES assert binarysucc('_1111111111_') == '10000000000' #binaryadd binaryadd = grammar() binaryadd[r'_\+_'] = '<+|+>' binaryadd[r'\+\>0'] = '0?+>' binaryadd[r'\+\>1'] = '1?+>' binaryadd[r'\+\>_'] = '<@0C_' binaryadd[r'0\<\+'] = '<+0?' binaryadd[r'1\<\+'] = '<+1?' binaryadd[r'_\<\+'] = '_' binaryadd[r'0\@0\?'] = '0?0@' binaryadd[r'0\@1\?'] = '1?0@' binaryadd[r'1\@0\?'] = '0?1@' binaryadd[r'1\@1\?'] = '1?1@' binaryadd[r'0\@\|'] = '|0@' binaryadd[r'1\@\|'] = '|1@' binaryadd[r'0\@0\@0C'] = '<@0C0' binaryadd[r'0\@0\@1C'] = '<@0C1' binaryadd[r'0\@1\@0C'] = '<@0C1' binaryadd[r'0\@1\@1C'] = '<@1C0' binaryadd[r'1\@0\@0C'] = '<@0C1' binaryadd[r'1\@0\@1C'] = '<@1C0' binaryadd[r'1\@1\@0C'] = '<@1C0' binaryadd[r'1\@1\@1C'] = '<@1C1' binaryadd[r'0\?\<\@'] = '\s+)(.*)(?P=ws)'] = lambda x,y: ',%s' % y whitespace['\|,(.*)'] = lambda x: 'where(%s)' % x assert whitespace(''' z = y | baz = bar foo = blurk moo = cow ''').strip() == 'z = y where(baz = bar,foo = blurk,moo = cow)' assert whitespace(''' z = y | baz = bar | foo = blurk moo = cow ''').strip() == 'z = y where(baz = bar where(foo = blurk,moo = cow))' assert whitespace(''' z = y | baz = bar foo = blurk moo = cow z = y | baz = bar | foo = blurk moo = cow ''').strip() == ''' z = y where(baz = bar,foo = blurk,moo = cow) z = y where(baz = bar where(foo = blurk,moo = cow))'''.strip()