Skip to content

Instantly share code, notes, and snippets.

@avli
Created May 2, 2020 14:59
Show Gist options
  • Save avli/ca391b7aa6aa6d33a2786dda786370ae to your computer and use it in GitHub Desktop.
Save avli/ca391b7aa6aa6d33a2786dda786370ae to your computer and use it in GitHub Desktop.
An arithmetic expression evaluator in Python.
"""
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