|
#!/usr/bin/env python3 |
|
|
|
# ############################################################################### |
|
# # |
|
# TOKENS TYPES # |
|
# # |
|
# ############################################################################### |
|
INT = "INTEGER" |
|
ADD = "ADD" |
|
SUB = "SUBTRACT" |
|
MUL = "MULTIPLY" |
|
DIV = "DIVIDE" |
|
EOF = "EOF" |
|
|
|
|
|
# ############################################################################### |
|
# # |
|
# TOKEN CLASS # |
|
# # |
|
# ############################################################################### |
|
class Token: |
|
def __init__(self, ttype, tvalue): |
|
self.type = ttype |
|
self.value = tvalue |
|
|
|
def __repr__(self): |
|
return self.__str__() |
|
|
|
def __str__(self): |
|
return "Token({}, {})".format(self.type, self.value) |
|
|
|
|
|
# ############################################################################### |
|
# # |
|
# SCANNER # |
|
# # |
|
# ############################################################################### |
|
class Scanner: |
|
""" |
|
Scanner Class. |
|
Scans an input string lazily. |
|
""" |
|
def __init__(self, input_text): |
|
self.curr_pos = 0 |
|
self.input_text = input_text |
|
self.curr_char = input_text[self.curr_pos] |
|
|
|
def error(self, token): |
|
raise Exception("Invalid token: {!r}".format(token)) |
|
|
|
def advance(self): |
|
self.curr_pos += 1 |
|
if self.curr_pos >= len(self.input_text): |
|
# None as EOF |
|
self.curr_char = None |
|
else: |
|
self.curr_char = self.input_text[self.curr_pos] |
|
|
|
def ignore_ws(self): |
|
while self.curr_char is not None and self.curr_char.isspace(): |
|
self.advance() |
|
|
|
def scan_integer(self): |
|
result = "" |
|
while self.curr_char is not None and self.curr_char.isdigit(): |
|
result += self.curr_char |
|
self.advance() |
|
return int(result) |
|
|
|
def next_token(self): |
|
while self.curr_char is not None: |
|
# WHITESPACE |
|
if self.curr_char.isspace(): |
|
self.ignore_ws() |
|
continue |
|
|
|
# INTEGER |
|
if self.curr_char.isdigit(): |
|
integer = self.scan_integer() |
|
return Token(INT, integer) |
|
|
|
# OPERATIONS |
|
if self.curr_char == "+": |
|
self.advance() |
|
return Token(ADD, "+") |
|
|
|
if self.curr_char == "-": |
|
self.advance() |
|
return Token(SUB, "-") |
|
|
|
if self.curr_char == "*": |
|
self.advance() |
|
return Token(MUL, "*") |
|
|
|
if self.curr_char == "/": |
|
self.advance() |
|
return Token(DIV, "/") |
|
|
|
# Raise an error |
|
self.error(self.curr_char) |
|
|
|
# Finished, return EOF |
|
return Token(EOF, None) |
|
|
|
|
|
# ############################################################################### |
|
# # |
|
# ABSTRACT SYNTAX TREE # |
|
# # |
|
# ############################################################################### |
|
class AST: |
|
pass |
|
|
|
|
|
class Int(AST): |
|
""" |
|
Integer AST Node Class. |
|
""" |
|
def __init__(self, value): |
|
self.value = value |
|
|
|
def __str__(self): |
|
return "Int({})".format(self.value) |
|
|
|
def __repr__(self): |
|
return self.__str__() |
|
|
|
|
|
class BinOp(AST): |
|
""" |
|
Binary Operation AST Node Class. |
|
""" |
|
def __init__(self, left, oper_token, right): |
|
self.left = left |
|
self.oper = oper_token |
|
self.right = right |
|
|
|
def __str__(self): |
|
return "BinOp({}, {}, {})".format(self.left, self.oper.type, self.right) |
|
|
|
def __repr__(self): |
|
return self.__str__() |
|
|
|
|
|
# ############################################################################### |
|
# # |
|
# PARSER - GENERIC TOP-DOWN # |
|
# # |
|
# ############################################################################### |
|
class Parser: |
|
""" |
|
The Parser Component. |
|
Implements a generic iterative Top-Down Parsing algorithm. |
|
""" |
|
def __init__(self, scanner): |
|
self.scanner = scanner |
|
self.curr_token = scanner.next_token() |
|
|
|
def error(self, expected_token_type): |
|
raise Exception("ERROR: Expected token of type '{}', but got '{}' instead!".format( |
|
expected_token_type, self.curr_token.type)) |
|
|
|
def consume(self, expected_token_type): |
|
if self.curr_token.type == expected_token_type: |
|
self.curr_token = self.scanner.next_token() |
|
else: |
|
self.error(expected_token_type) |
|
|
|
def parse(self): |
|
return self.p_expr() |
|
|
|
# ############################## PARSING RULES ########################### |
|
def p_expr(self): |
|
""" |
|
expr ::= subexpr ((ADD|SUB) subexpr)* |
|
""" |
|
result = self.p_subexpr() |
|
|
|
while self.curr_token.type in [ADD, SUB]: |
|
token = self.curr_token |
|
self.consume(token.type) |
|
result = BinOp(left=result, oper=token, right=self.p_subexpr()) |
|
|
|
return result |
|
|
|
def p_subexpr(self): |
|
""" |
|
subexpr ::= integer ((MUL|DIV) integer)* |
|
""" |
|
result = self.p_integer() |
|
|
|
while self.curr_token.type in [MUL, DIV]: |
|
token = self.curr_token |
|
self.consume(token.type) |
|
result = BinOp(left=result, oper=token, right=self.p_subexpr()) |
|
|
|
return result |
|
|
|
def p_integer(self): |
|
""" |
|
integer ::= INTEGER |
|
""" |
|
token = self.curr_token |
|
self.consume(INT) |
|
return Int(value=token.value) |
|
|
|
|
|
# ############################################################################### |
|
# # |
|
# EVALUATOR # |
|
# # |
|
# ############################################################################### |
|
class Evaluator: |
|
""" |
|
Evaluator Class. |
|
Implements a Depth-First Search Node-Visitor pattern. |
|
""" |
|
def __init__(self, parser): |
|
self.parser = parser |
|
|
|
def eval(self): |
|
ast = self.parser.parse() |
|
if ast is None: |
|
return "" |
|
return self.visit(ast) |
|
|
|
# ############################## DFS NODE VISITORS ######################### |
|
def visit(self, node): |
|
if isinstance(node, Int): |
|
return self.visit_Int(node) |
|
elif isinstance(node, BinOp): |
|
return self.visit_BinOp(node) |
|
|
|
def visit_Int(self, node): |
|
return node.value |
|
|
|
def visit_BinOp(self, node): |
|
if node.oper.type == ADD: |
|
return self.visit(node.left) + self.visit(node.right) |
|
elif node.oper.type == SUB: |
|
return self.visit(node.left) - self.visit(node.right) |
|
elif node.oper.type == MUL: |
|
return self.visit(node.left) * self.visit(node.right) |
|
elif node.oper.type == DIV: |
|
return self.visit(node.left) // self.visit(node.right) |
|
|
|
|
|
# ############################################################################### |
|
# # |
|
# REPL LOOP # |
|
# # |
|
# ############################################################################### |
|
def main(): |
|
import subprocess |
|
|
|
while True: |
|
try: |
|
expr_text = input("typreter> ") |
|
except EOFError: |
|
break |
|
|
|
if not expr_text: |
|
continue |
|
elif expr_text == ":clear": |
|
ret = subprocess.call("clear") |
|
elif expr_text == ":quit": |
|
break |
|
else: |
|
try: |
|
scanner = Scanner(expr_text) |
|
parser = Parser(scanner) |
|
evaluator = Evaluator(parser) |
|
result = evaluator.eval() |
|
print(result) |
|
except Exception as err: |
|
print(str(err)) |
|
|
|
print("Goodbye!") |
|
|
|
|
|
if __name__ == "__main__": |
|
main() |
|
|
