import sys
import os
import unittest
EOF = ""
SEGMENT_GAP = "\xff"
class TracException(Exception):
pass
def list_get(list_, index, default=EOF):
try:
return list_[index]
except:
return default
class Io(object):
def __init__(self, s=""):
self.buffer = []
self.buffer += s
def pop(self, default=EOF):
try:
return self.buffer.pop(0)
except:
return default
def push(self, s):
self.buffer[0:0] += s
def delete(self, i, j):
del self.buffer[i:j]
def peek(self, count=1):
try:
chars = self.buffer[0:0 + count]
except:
chars = [EOF]
return "".join(chars)
def get_trac_string(self):
chars = []
c = self.pop()
while True:
if c == '#':
if self.peek(1) == '(' or self.peek(2) == '#(':
break
elif c in "(),":
break
else:
chars.append(c)
c = self.pop()
if c != EOF:
self.push(c)
s = "".join(chars)
return s
def get_trac_protected_string(self):
chars = []
paren_count = 0
matched = False
c = self.pop()
while c != EOF and not matched:
if c == '(':
paren_count += 1
elif c == ')':
paren_count -= 1
chars.append(c)
if paren_count != 0:
c = self.pop()
else:
matched = True
if not matched:
raise TracException, "%s: can't find matching end parenthesis" %("get_trac_protected_string")
s = "".join(chars[1:-1])
return s
class Tag(object):
CLOSE_PAREN = ')'
COMMA = ','
NONE = -1
STRING = 300
OPEN_ACTIVE_FUNC = 400
OPEN_NEUTRAL_FUNC = 500
DONE = 600
class Token(object):
def __init__(self, t, value=''):
self.tag = t
self.value = value
def __str__(self):
return "Token([%s] [%s])" % (str(self.tag), str(self.value))
class String(Token):
def __init__(self, v):
Token.__init__(self, Tag.STRING, v)
class Lexer(object):
def __init__(self):
self.lookahead = None
self.output = "" # last string printed to output by ps for unit testing
self.trace = True # flag for printing trace results of function evaluation
self.primitives = {"ds":self.ds, \
"ps":self.ps, \
"ss":self.ss, \
"cl":self.cl, \
"ad":self.ad, \
"su":self.su, \
"ml":self.ml, \
"dv":self.dv, \
"tn":self.tn, \
"tf":self.tf, \
"eq":self.eq \
}
def initialize(self, program=""):
self.forms = {}
self.io = Io(program)
def tn(self, args):
self.trace = True
return ""
def tf(self, args):
self.trace = False
return ""
def ds(self, args):
key = list_get(args, 0)
value = list_get(args, 1)
self.forms[key] = value
return ""
def ps(self, args):
try:
s = list_get(args, 0)
print s
self.output = s
except:
pass
return ""
def ad(self, args):
try:
num1 = int(list_get(args, 0))
num2 = int(list_get(args, 1))
return str(num1 + num2)
except:
return ""
def su(self, args):
try:
num1 = int(list_get(args, 0))
num2 = int(list_get(args, 1))
return str(num1 - num2)
except:
return ""
def ml(self, args):
try:
num1 = int(list_get(args, 0))
num2 = int(list_get(args, 1))
return str(num1 * num2)
except:
return ""
def dv(self, args):
try:
num1 = int(list_get(args, 0))
num2 = int(list_get(args, 1))
return str(num1 / num2)
except:
return ""
def eq(self, args):
try:
s1 = list_get(args, 0)
s2 = list_get(args, 1)
eq_result = list_get(args, 2)
neq_result = list_get(args, 3)
if s1 == s2:
return eq_result
else:
return neq_result
except:
return ""
def ss(self, args):
try:
form_key = args.pop(0)
form = self.forms[form_key]
form_marked = form
for i in range(len(args)):
arg = args[i]
marker = "%s%s" % (SEGMENT_GAP, chr(i))
form_marked = form_marked.replace(arg, marker)
self.forms[form_key] = form_marked
form_list = []
form_list += form_marked
return ""
except:
return ""
def cl(self, args):
try:
form_key = args.pop(0)
form = self.forms[form_key]
form_processed = form
for i in range(len(args)):
arg = args[i]
marker = "%s%s" % (SEGMENT_GAP, chr(i))
form_processed = form_processed.replace(marker, arg)
return form_processed
except:
return ""
def lexan(self):
token = None
while not token:
c = self.io.pop()
if c == '\t' or c == '\n':
pass # strip out white space
elif c == '(':
self.io.push(c)
s = self.io.get_trac_protected_string()
token = String(s)
elif c == ')':
token = Token(Tag.CLOSE_PAREN)
elif c == '#' and self.io.peek(1) == '(':
self.io.delete(0,1)
token = Token(Tag.OPEN_ACTIVE_FUNC)
elif c == '#' and self.io.peek(2) == '#(':
self.io.delete(0,2)
token = Token(Tag.OPEN_NEUTRAL_FUNC)
elif c == ',':
token = Token(Tag.COMMA)
elif c == EOF:
token = Token(Tag.DONE)
else:
self.io.push(c)
s = self.io.get_trac_string()
token = String(s)
return token
def func(self, tag=""):
result = ""
args = []
token = self.lookahead
if token.tag == Tag.STRING:
args.append(token.value)
self.factor()
while True:
token = self.lookahead
if token.tag in (Tag.STRING, Tag.OPEN_ACTIVE_FUNC,
Tag.OPEN_NEUTRAL_FUNC, Tag.COMMA):
if token.tag == Tag.STRING:
args.append(token.value)
result = self.factor()
if token.tag == Tag.OPEN_NEUTRAL_FUNC:
args.append(result)
else:
if tag:
result = self.eval_func(args)
break
return result
def factor(self):
result = None
token = self.lookahead
if token.tag == Tag.OPEN_ACTIVE_FUNC:
self.match(Tag.OPEN_ACTIVE_FUNC)
result = self.func(token.tag)
self.match(Tag.CLOSE_PAREN, result)
elif token.tag == Tag.OPEN_NEUTRAL_FUNC:
self.match(Tag.OPEN_NEUTRAL_FUNC)
result = self.func(token.tag)
self.match(Tag.CLOSE_PAREN)
elif token.tag == Tag.COMMA:
self.match(Tag.COMMA)
elif token.tag == Tag.STRING:
self.match(Tag.STRING)
elif self.lookahead.tag == Tag.DONE:
self.match(Tag.DONE)
else:
raise TracException("factor: bad token tag - %s" % token)
return result
def match(self, tag, result=None):
if self.lookahead.tag == tag:
if result != None:
self.io.push(result)
self.lookahead = self.lexan()
else:
raise TracException("match: tag %s doesn't match %s" % (tag, self.lookahead))
def eval_func(self, args):
result = ""
try:
func_name = args[0]
args = args[1:]
primitive = self.primitives.get(func_name, None)
if primitive:
result = primitive(args)
if self.trace:
print "eval: %s %s -> [%s]" % (func_name, args, result)
except Exception, e:
raise TracException, "%s: failed - %s" %("eval", e)
return result
def parse(self):
self.lookahead = self.lexan()
while self.lookahead.tag != Tag.DONE:
self.func()
self.match(Tag.DONE)
print "Forms: %s" % self.forms
print "Output: %s" % self.output
return self
class TestTrac(unittest.TestCase):
def setUp(self):
pass
def __test(self, program, output):
self.lexer = Lexer()
self.lexer.initialize(program)
self.lexer.parse()
self.assertEqual(self.lexer.output, output)
def test_1_ps(self):
self.__test("#(ps,Hello world)", "Hello world")
def test_2_equal(self):
self.__test("#(ps,#(eq,A,A,=,!=))", "=")
def test_3_not_equal(self):
self.__test("#(ps,#(eq,Cat,Dog,equal,not equal))", "not equal")
def test_4_ds(self):
self.__test("#(ds,AA,Cat)#(ps,#(cl,AA))", "Cat")
def test_5_protect_parens(self):
self.__test("#(ds,AA,Cat)#(ds,BB,(#(cl,AA)))#(ps,(#(cl,BB)))", "#(cl,BB)")
def test_6_neutral_func(self):
self.__test("#(ds,AA,Cat)#(ds,BB,(#(cl,AA)))#(ps,##(cl,BB))", "#(cl,AA)")
def test_7_indirection(self):
self.__test("#(ds,AA,Cat)#(ds,BB,(#(cl,AA)))#(ps,#(cl,BB))", "Cat")
def test_8_ss(self):
self.__test("#(ds,AA,Hello X)#(ss,AA,X)#(ps,#(cl,AA,world))", "Hello world")
def test_9_factorial(self):
self.__test("""
#(ds,Factorial,(#(eq,X,1,1,(#(ml,X,#(cl,Factorial,#(su,X,1)))))))
#(ss,Factorial,X)
#(ps,#(cl,Factorial,5))
""", "120")
if __name__ == "__main__":
print __file__
unittest.main()
