Last active
December 14, 2018 07:02
-
-
Save ewestern/5789237 to your computer and use it in GitHub Desktop.
A python implementation of TAPL chpt 4
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import ply.lex as lex | |
import ply.yacc as yacc | |
dummyinfo = '' | |
class Term(object): | |
def __init__(self, info): | |
self.info = info | |
def __repr__(self): | |
return self.__class__.__name__ + str(self.__dict__) | |
def eval(self): | |
return self | |
def isnumericalvalue(self): | |
return False | |
class TmTrue(Term): | |
pass | |
class TmFalse(Term): | |
pass | |
class TmIf(Term): | |
def __init__(self, info, t1, t2, t3): | |
super(TmIf, self).__init__(info) | |
self.t1, self.t2, self.t3 = t1, t2, t3 | |
def eval(self): | |
if type(self.t1) is TmTrue: return self.t2.eval() | |
elif type(self.t1) is TmFalse: return self.t3.eval() | |
else: return TmIf(self.info, self.t1.eval(), self.t2, self.t3) | |
class TmZero(Term): | |
def isnumericalvalue(self): | |
return True | |
class TmSucc(Term): | |
def __init__(self, info, t1): | |
super(TmSucc, self).__init__(info) | |
self.t1 = t1 | |
def eval(self): | |
return TmSucc(self.info, self.t1.eval()) | |
def isnumericalvalue(self): | |
return self.t1.isnumericalvalue() | |
class TmPred(Term): | |
def __init__(self, info, t1): | |
super(TmPred, self).__init__(info) | |
self.t1 = t1 | |
def eval(self): | |
if type(self.t1) is TmZero: return TmZero(dummyinfo) | |
elif type(self.t1) is TmSucc: return self.t1.t1 | |
else: return TmPred(self.info, self.t1.eval()) | |
class TmIsZero(Term): | |
def __init__(self, info, t1): | |
super(TmIsZero, self).__init__(info) | |
self.t1 = t1 | |
def eval(self): | |
if type(self.t1) is TmZero: return TmTrue(dummyinfo) | |
elif type(self.t1) is TmSucc and self.t1.isnumericalvalue(): return TmFalse(dummyinfo) | |
else: return TmIsZero(self.info, self.t1.eval1()) | |
class NoRuleApplies(Exception): | |
pass | |
reserved = { | |
'iszero':'ISZERO', | |
'succ': 'SUCC', | |
'pred': 'PRED', | |
'true': 'TRUE', | |
'false': 'FALSE', | |
'if': 'IF', | |
'then': 'THEN', | |
'else': 'ELSE' | |
} | |
tokens = tuple(reserved.values()) +\ | |
( | |
'ZERO', | |
'LPAREN', | |
'RPAREN', | |
'ID' | |
) | |
t_ZERO = r'0' | |
t_LPAREN = r'\(' | |
t_RPAREN = r'\)' | |
t_ignore = ' \t' | |
def t_ID(t): | |
r'[a-zA-Z_][a-zA-Z_0-9]+' | |
t.type = reserved.get(t.value, "ID") | |
return t | |
def t_error(t): | |
print "Illegal character '%s'" % t.value[0] | |
t.lexer.skip(1) | |
lexer = lex.lex() | |
def p_exp(p): | |
'expression : optterm' | |
p[0] = p[1] | |
def p_optterm(p): | |
'optterm : term optterm' | |
p[0] = [p[1]] + p[2] | |
def p_optterm_empty(p): | |
'optterm : ' | |
p[0] = [] | |
def p_succ(p): | |
'term : SUCC LPAREN term RPAREN' | |
p[0] = TmSucc('', p[3]) | |
def p_pred(p): | |
'term : PRED LPAREN term RPAREN' | |
p[0] = TmPred('', p[3]) | |
def p_expression_if(p): | |
'term : IF term THEN term ELSE term' | |
p[0] = TmIf('', p[2], p[4], p[6]) | |
def p_true(p): | |
'term : TRUE' | |
p[0] = TmTrue('') | |
def p_false(p): | |
'term : FALSE' | |
p[0] = TmFalse('') | |
def p_zero(p): | |
'term : ZERO' | |
p[0] = TmZero('') | |
def p_error(p): | |
print "Syntax error in input!" | |
parser = yacc.yacc() | |
data = """ | |
if iszero(succ(0)) then succ(0) else pred(succ(succ(0))) | |
""" | |
results = parser.parse(data) | |
for r in results: | |
print r.eval() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment