Created
May 2, 2020 14:59
-
-
Save avli/ca391b7aa6aa6d33a2786dda786370ae to your computer and use it in GitHub Desktop.
An arithmetic expression evaluator in Python.
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
""" | |
An arithmetic expression evaluator in Python. | |
The language grammar: | |
prog : expr ; | |
expr : NUMBER ('+'|'-' NUMBER)* NEWLINE; | |
NUMBER : '0'..'9'+ ; | |
NEWLINE : '\n' ; | |
""" | |
class Token: | |
def __init__(self, type, lexeme, literal=None): | |
self.type = type | |
self.lexeme = lexeme | |
self.literal = literal | |
def __repr__(self): | |
return '<Token(%s, %s, %s)>' % (self.type, self.lexeme, self.literal) | |
# Token types | |
PLUS = 0 | |
MINUS = 1 | |
NUMBER = 2 | |
NEWLINE = 3 | |
class Lexer: | |
def __init__(self, source): | |
self._source = source | |
self._tokens = [] | |
self._current = 0 | |
self._start = 0 | |
def tokenize(self): | |
while not self._is_at_end(): | |
self._start = self._current | |
c = self._advance() | |
if c == '+': | |
self._tokens.append(Token(PLUS, c)) | |
elif c == '-': | |
self._tokens.append(Token(MINUS, c)) | |
elif c == '\n': | |
self._tokens.append(Token(NEWLINE, '\\n')) | |
elif self._is_digit(c): | |
self._digit() | |
elif self._is_whitespace(c): | |
continue | |
else: | |
raise RuntimeError("Unexpected character at position %d" % self._current) | |
return self._tokens | |
def _is_at_end(self): | |
return self._current >= len(self._source) | |
def _advance(self): | |
self._current += 1 | |
return self._source[self._current - 1] | |
def _is_digit(self, c): | |
return c in '0123456789' | |
def _digit(self): | |
while self._is_digit(self._peek()): | |
self._advance() | |
lexeme = self._source[self._start:self._current] | |
self._tokens.append(Token(NUMBER, lexeme, int(lexeme))) | |
def _peek(self): | |
if self._is_at_end(): | |
return '\0' | |
return self._source[self._current] | |
def _is_whitespace(self, c): | |
return c in ' \t\r' | |
class AST: | |
def accept(self, visitor): | |
return visitor.visit(self) | |
class Expr(AST): | |
def __init__(self, left, op, right): | |
self.left = left | |
self.op = op | |
self.right = right | |
def __repr__(self): | |
return "<Expr(%s, %s, %s)>" % (self.left, self.op, self.right) | |
class Number(AST): | |
def __init__(self, number): | |
self.number = number | |
def __repr__(self): | |
return "<Number(%s)>" % self.number | |
Andrey Lisin, [02.05.20 17:15] | |
class Parser: | |
def __init__(self, tokens): | |
self._tokens = tokens | |
self._current = 0 | |
def parse(self): | |
return self._prog() | |
def _prog(self): | |
return self._expr() | |
def _expr(self): | |
expr = self._number() | |
while self._match(PLUS, MINUS): | |
op = self._advance() | |
right = self._number() | |
expr = Expr(expr, op, right) | |
return expr | |
def _number(self): | |
if self._match(NUMBER): | |
return Number(self._advance()) | |
raise RuntimeError("Unexpected token %r" % self._peek()) | |
def _is_at_end(self): | |
return self._current <= len(self._tokens) | |
def _advance(self): | |
self._current += 1 | |
return self._tokens[self._current - 1] | |
def _match(self, *types): | |
for type in types: | |
if self._peek().type == type: | |
return True | |
return False | |
def _peek(self): | |
return self._tokens[self._current] | |
class Visitor: | |
def visit(self, node): | |
raise NotImplementedError | |
class AstPrinter(Visitor): | |
def print(self, root): | |
print(root.accept(self)) | |
def visit(self, node): | |
if isinstance(node, Number): | |
return node.number.literal | |
elif isinstance(node, Expr): | |
return '(%s %s %s)' % (node.op.lexeme, node.left.accept(self), node.right.accept(self)) | |
class Interpreter(Visitor): | |
def interpret(self, root): | |
return root.accept(self) | |
def visit(self, node): | |
if isinstance(node, Number): | |
return node.number.literal | |
elif isinstance(node, Expr): | |
if node.op.type == PLUS: | |
return node.left.accept(self) + node.right.accept(self) | |
else: | |
return node.left.accept(self) - node.right.accept(self) | |
def main(): | |
while True: | |
source = input('> ') | |
source += '\n' | |
try: | |
lexer = Lexer(source) | |
tokens = lexer.tokenize() | |
parser = Parser(tokens) | |
ast = parser.parse() | |
# ast_printer = AstPrinter() | |
# ast_printer.print(ast) | |
interpreter = Interpreter() | |
print(interpreter.interpret(ast)) | |
except RuntimeError as e: | |
print(e) | |
if __name__ == '__main__': | |
main() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment