310 lines
8.1 KiB
Python
310 lines
8.1 KiB
Python
#!/usr/bin/env python
|
|
|
|
class Token:
|
|
def __init__(self,data=None):
|
|
self.data = data
|
|
def __repr__(self):
|
|
return "%s<%s>" % (self.__class__.__name__, repr(self.data))
|
|
|
|
class AddOpToken(Token):
|
|
pass
|
|
|
|
class SubtractOpToken(Token):
|
|
pass
|
|
|
|
class MultiplyOpToken(Token):
|
|
pass
|
|
|
|
class DivideOpToken(Token):
|
|
pass
|
|
|
|
class NumToken(Token):
|
|
pass
|
|
|
|
class PLeftToken(Token):
|
|
pass
|
|
|
|
class PRightToken(Token):
|
|
pass
|
|
|
|
class EOLToken(Token):
|
|
pass
|
|
|
|
def lex(text):
|
|
END = object()
|
|
it = iter(text)
|
|
c = next(it,END)
|
|
while True:
|
|
if c == END:
|
|
break
|
|
elif c in "0123456789":
|
|
s = ""
|
|
vtype = int
|
|
while c != END and c in "0123456789.":
|
|
s+=c
|
|
if(c == "."):
|
|
vtype = float
|
|
c = next(it,END)
|
|
yield NumToken(vtype(s))
|
|
continue
|
|
elif c == "+":
|
|
yield AddOpToken()
|
|
elif c == "-":
|
|
yield SubtractOpToken()
|
|
elif c == "*":
|
|
yield MultiplyOpToken()
|
|
elif c == "/":
|
|
yield DivideOpToken()
|
|
elif c == "(":
|
|
yield PLeftToken()
|
|
elif c == ")":
|
|
yield PRightToken()
|
|
elif c == " ":
|
|
pass
|
|
else:
|
|
raise Exception("Unexpected character %s" % c)
|
|
c = next(it,END)
|
|
|
|
class OperatorNode:
|
|
operator = "?"
|
|
def __init__(self, left, right):
|
|
self.left = left
|
|
self.right = right
|
|
self.vtype = None
|
|
|
|
def calculate(self):
|
|
raise Exception("Not implemented")
|
|
|
|
def __repr__(self):
|
|
return "%s < %s, %s >" % (self.__class__.__name__, repr(self.left), repr(self.right))
|
|
|
|
def printAST(self,tab=0):
|
|
self.left.printAST(tab+1)
|
|
print("\t"*tab,self.operator)
|
|
self.right.printAST(tab+1)
|
|
|
|
def getType(self):
|
|
if self.vtype is None:
|
|
vlefttype = self.left.getType()
|
|
vrighttype = self.left.getType()
|
|
if vrighttype == float or vlefttype == float:
|
|
self.vtype = float
|
|
else:
|
|
self.vtype = int
|
|
return self.vtype
|
|
|
|
class AdditionNode(OperatorNode):
|
|
operator = "+"
|
|
def calculate(self):
|
|
return self.left.calculate() + self.right.calculate()
|
|
|
|
class SubtractionNode(OperatorNode):
|
|
operator = "-"
|
|
def calculate(self):
|
|
return self.left.calculate() - self.right.calculate()
|
|
|
|
class MultiplicationNode(OperatorNode):
|
|
operator = "*"
|
|
def calculate(self):
|
|
return self.left.calculate() * self.right.calculate()
|
|
|
|
class DivisionNode(OperatorNode):
|
|
operator = "/"
|
|
def calculate(self):
|
|
right = self.right.calculate()
|
|
if right == 0:
|
|
raise Exception("Division by Zero Error")
|
|
return self.left.calculate() // right
|
|
|
|
class NumNode:
|
|
def __init__(self, value):
|
|
self.value = value
|
|
|
|
def calculate(self):
|
|
return self.value
|
|
|
|
def __repr__(self):
|
|
return "NumNode < %d >" % self.value
|
|
|
|
def printAST(self,tab=0):
|
|
print("\t"*tab,self.value)
|
|
|
|
def getType(self):
|
|
if(type(self.value) == int):
|
|
return int
|
|
else:
|
|
return float
|
|
|
|
# 1. S -> E
|
|
# 2. E -> E+T
|
|
# 3. E -> E-T
|
|
# 4. E -> T
|
|
# 5. T -> T*F
|
|
# 6. T -> T/F
|
|
# 7. T -> F
|
|
# 8. F -> ( E )
|
|
# 9. F -> num
|
|
|
|
def reduce_left_right(stack):
|
|
stack.pop() #state
|
|
right = stack.pop()
|
|
stack.pop() #state
|
|
stack.pop() #operator
|
|
stack.pop() #state
|
|
left = stack.pop()
|
|
|
|
return left, right
|
|
|
|
|
|
def parse(text):
|
|
it = lex(text)
|
|
T_NUM = NumToken
|
|
T_ADD = AddOpToken
|
|
T_SUB = SubtractOpToken
|
|
T_MUL = MultiplyOpToken
|
|
T_DIV = DivideOpToken
|
|
T_LPAR = PLeftToken
|
|
T_RPAR = PRightToken
|
|
END = EOLToken
|
|
|
|
NTS_E = object()
|
|
NTS_T = object()
|
|
NTS_F = object()
|
|
|
|
a = object()
|
|
r = object()
|
|
s = object()
|
|
|
|
table = [
|
|
{ T_NUM: (s,4), T_LPAR: (s,3) },
|
|
{ T_ADD: (s,8), T_SUB: (s,9), END: (a,0) },
|
|
{ T_ADD: (r,4), T_SUB: (r,4), T_MUL: (s,12), T_DIV: (s,13), T_RPAR: (r,4), END: (r,4) },
|
|
{ T_NUM: (s,4), T_LPAR: (s,3) },
|
|
{ T_ADD: (r,9), T_SUB: (r,9), T_MUL: (r,9), T_DIV: (r,9), T_RPAR: (r,9), END: (r,9) },
|
|
{ T_ADD: (r,7), T_SUB: (r,7), T_MUL: (r,7), T_DIV: (r,7), T_RPAR: (r,7), END: (r,7) },
|
|
{ T_ADD: (s,8), T_SUB: (s,9), T_RPAR: (s,7) },
|
|
{ T_ADD: (r,8), T_SUB: (r,8), T_MUL: (r,8), T_DIV: (r,8), T_RPAR: (r,8), END: (r,8) },
|
|
{ T_NUM: (s,4), T_LPAR: (s,3) },
|
|
{ T_NUM: (s,4), T_LPAR: (s,3) },
|
|
{ T_ADD: (r,2), T_SUB: (r,2), T_MUL: (s,12), T_DIV: (s,13), T_RPAR: (r,2), END: (r,2) },
|
|
{ T_ADD: (r,3), T_SUB: (r,3), T_MUL: (s,12), T_DIV: (s,13), T_RPAR: (r,3), END: (r,3) },
|
|
{ T_NUM: (s,4), T_LPAR: (s,3) },
|
|
{ T_NUM: (s,4), T_LPAR: (s,3) },
|
|
{ T_ADD: (r,5), T_SUB: (r,5), T_MUL: (r,5), T_DIV: (r,5), T_RPAR: (r,5), END: (r,5) },
|
|
{ T_ADD: (r,6), T_SUB: (r,6), T_MUL: (r,6), T_DIV: (r,6), T_RPAR: (r,6), END: (r,6) }
|
|
]
|
|
|
|
goto = [
|
|
{ NTS_E: 1, NTS_T:2, NTS_F: 5 },
|
|
{},
|
|
{},
|
|
{ NTS_E: 6, NTS_T:2, NTS_F: 5 },
|
|
{},
|
|
{},
|
|
{},
|
|
{},
|
|
{ NTS_T:10, NTS_F: 5 },
|
|
{ NTS_T:11, NTS_F: 5 },
|
|
{},
|
|
{},
|
|
{ NTS_F: 14 },
|
|
{ NTS_F: 15 },
|
|
{},
|
|
{}
|
|
]
|
|
|
|
stack = []
|
|
stack.append(0)
|
|
lookahead = next(it,END())
|
|
|
|
while True:
|
|
try:
|
|
op, dat = table[stack[-1]][lookahead.__class__]
|
|
except KeyError:
|
|
raise Exception("Unexpected token: %s" % repr(lookahead))
|
|
|
|
if op == s:
|
|
stack.append( lookahead )
|
|
stack.append( dat )
|
|
lookahead = next(it,END())
|
|
elif op == r:
|
|
# 1. S -> E
|
|
# 2. E -> E+T
|
|
# 3. E -> E-T
|
|
# 4. E -> T
|
|
# 5. T -> T*F
|
|
# 6. T -> T/F
|
|
# 7. T -> F
|
|
# 8. F -> ( E )
|
|
# 9. F -> num
|
|
if dat == 2:
|
|
left, right = reduce_left_right(stack)
|
|
pstate = stack[-1]
|
|
nts = NTS_E
|
|
stack.append( AdditionNode( left, right ) )
|
|
elif dat == 3:
|
|
left, right = reduce_left_right(stack)
|
|
pstate = stack[-1]
|
|
nts = NTS_E
|
|
stack.append( SubtractionNode( left, right ) )
|
|
elif dat == 4:
|
|
stack.pop() #state
|
|
v = stack.pop()
|
|
pstate = stack[-1]
|
|
nts = NTS_E
|
|
stack.append( v )
|
|
elif dat == 5:
|
|
left, right = reduce_left_right(stack)
|
|
pstate = stack[-1]
|
|
nts = NTS_T
|
|
stack.append( MultiplicationNode( left, right ) )
|
|
elif dat == 6:
|
|
left, right = reduce_left_right(stack)
|
|
pstate = stack[-1]
|
|
nts = NTS_T
|
|
stack.append( DivisionNode( left, right ) )
|
|
elif dat == 7:
|
|
stack.pop() #state
|
|
v = stack.pop()
|
|
pstate = stack[-1]
|
|
nts = NTS_T
|
|
stack.append( v )
|
|
elif dat == 8:
|
|
stack.pop() #state
|
|
stack.pop() #rpar
|
|
stack.pop() #state
|
|
v = stack.pop() # inner
|
|
stack.pop() #state
|
|
stack.pop() #lpar
|
|
pstate = stack[-1]
|
|
nts = NTS_F
|
|
stack.append( v )
|
|
elif dat == 9:
|
|
stack.pop() #state
|
|
tok = stack.pop()
|
|
pstate = stack[-1]
|
|
nts = NTS_F
|
|
stack.append( NumNode( tok.data ) )
|
|
else:
|
|
raise Exception("Rule %d not found" % dat)
|
|
|
|
try:
|
|
stack.append( goto[pstate][nts] )
|
|
except:
|
|
raise Exception("WTF")
|
|
elif op == a:
|
|
break
|
|
|
|
stack.pop()
|
|
return stack.pop()
|
|
|
|
if __name__ == '__main__':
|
|
l = input("> ")
|
|
print('"%s"' % l)
|
|
print(list(lex(l)))
|
|
ast = parse(l)
|
|
ast.printAST()
|
|
print("Result is of type: %s" % (repr(ast.getType())))
|
|
print(l," = ",ast.calculate())
|
|
|