INTEGER, PLUS, MINUS, MUL, DIV, LPAREN, RPAREN, EOF = (
'INTEGER', 'PLUS', 'MINUS', 'MUL', 'DIV', '(', ')', 'EOF'
)
class Token(object):
def __init__(self, type, value):
XXXXXXXXXXself.type = type
XXXXXXXXXXself.value = value
def __str__(self):
"""String representation of the class instance.
XXXXXXXXXXExamples:
XXXXXXXXXXToken(INTEGER, 3)
XXXXXXXXXXToken(PLUS, '+')
XXXXXXXXXXToken(MUL, '*')
"""
XXXXXXXXXXreturn 'Token({type}, {value})'.format(
XXXXXXXXXXtype=self.type,
XXXXXXXXXXvalue=repr(self.value)
)
def __repr__(self):
XXXXXXXXXXreturn self.__str__()
class Lexer(object):
def __init__(self, text):
# client string input, e.g. "4 + 2 * 3 - 6 / 2"
XXXXXXXXXXself.text = text
# self.pos is an index into self.text
XXXXXXXXXXself.pos = 0
XXXXXXXXXXself.cu
ent_char = self.text[self.pos]
def e
or(self):
XXXXXXXXXXraise Exception('Invalid character')
def advance(self):
"""Advance the `pos` pointer and set the `cu
ent_char` variable."""
XXXXXXXXXXself.pos += 1
XXXXXXXXXXif self.pos > len(self.text) - 1:
XXXXXXXXXXself.cu
ent_char = None # Indicates end of input
XXXXXXXXXXelse:
XXXXXXXXXXself.cu
ent_char = self.text[self.pos]
def skip_whitespace(self):
XXXXXXXXXXwhile self.cu
ent_char is not None and self.cu
ent_char.isspace():
XXXXXXXXXXself.advance()
def integer(self):
"""Return a (multidigit) integer consumed from the input."""
XXXXXXXXXXresult = ''
XXXXXXXXXXwhile self.cu
ent_char is not None and self.cu
ent_char.isdigit():
XXXXXXXXXXresult += self.cu
ent_cha
XXXXXXXXXXself.advance()
XXXXXXXXXXreturn int(result)
def get_next_token(self):
"""Lexical analyzer (also known as scanner or tokenizer)
XXXXXXXXXXThis method is responsible for
eaking a sentence
XXXXXXXXXXapart into tokens. One token at a time.
"""
XXXXXXXXXXwhile self.cu
ent_char is not None:
XXXXXXXXXXif self.cu
ent_char.isspace():
XXXXXXXXXXself.skip_whitespace()
XXXXXXXXXXcontinue
XXXXXXXXXXif self.cu
ent_char.isdigit():
XXXXXXXXXXreturn Token(INTEGER, self.integer())
XXXXXXXXXXif self.cu
ent_char == '+':
XXXXXXXXXXself.advance()
XXXXXXXXXXreturn Token(PLUS, '+')
XXXXXXXXXXif self.cu
ent_char == '-':
XXXXXXXXXXself.advance()
XXXXXXXXXXreturn Token(MINUS, '-')
XXXXXXXXXXif self.cu
ent_char == '*':
XXXXXXXXXXself.advance()
XXXXXXXXXXreturn Token(MUL, '*')
XXXXXXXXXXif self.cu
ent_char == '/':
XXXXXXXXXXself.advance()
XXXXXXXXXXreturn Token(DIV, '/')
XXXXXXXXXXif self.cu
ent_char == '(':
XXXXXXXXXXself.advance()
XXXXXXXXXXreturn Token(LPAREN, '(')
XXXXXXXXXXif self.cu
ent_char == ')':
XXXXXXXXXXself.advance()
XXXXXXXXXXreturn Token(RPAREN, ')')
XXXXXXXXXXself.e
or()
XXXXXXXXXXreturn Token(EOF, None)
###############################################################################
# #
# PARSER #
# #
###############################################################################
class AST(object):
pass
class BinOp(AST):
def __init__(self, left, op, right):
XXXXXXXXXXself.left = left
XXXXXXXXXXself.token = self.op = op
XXXXXXXXXXself.right = right
class Num(AST):
def __init__(self, token):
XXXXXXXXXXself.token = token
XXXXXXXXXXself.value = token.value
class Parser(object):
def __init__(self, lexer):
XXXXXXXXXXself.lexer = lexe
# set cu
ent token to the first token taken from the input
XXXXXXXXXXself.cu
ent_token = self.lexer.get_next_token()
def e
or(self):
XXXXXXXXXXraise Exception('Invalid syntax')
def eat(self, token_type):
# compare the cu
ent token type with the passed token
# type and if they match then "eat" the cu
ent token
# and assign the next token to the self.cu
ent_token,
# otherwise raise an exception.
XXXXXXXXXXif self.cu
ent_token.type == token_type:
XXXXXXXXXXself.cu
ent_token = self.lexer.get_next_token()
XXXXXXXXXXelse:
XXXXXXXXXXself.e
or()
def factor(self):
"""factor : INTEGER | LPAREN expr RPAREN"""
XXXXXXXXXXtoken = self.cu
ent_token
XXXXXXXXXXif token.type == INTEGER:
XXXXXXXXXXself.eat(INTEGER)
XXXXXXXXXXreturn Num(token)
XXXXXXXXXXelif token.type == LPAREN:
XXXXXXXXXXself.eat(LPAREN)
XXXXXXXXXXnode = self.expr()
XXXXXXXXXXself.eat(RPAREN)
XXXXXXXXXXreturn node
def term(self):
"""term : factor ((MUL | DIV) factor)*"""
XXXXXXXXXXnode = self.factor()
XXXXXXXXXXwhile self.cu
ent_token.type in (MUL, DIV):
XXXXXXXXXXtoken = self.cu
ent_token
XXXXXXXXXXif token.type == MUL:
XXXXXXXXXXself.eat(MUL)
XXXXXXXXXXelif token.type == DIV:
XXXXXXXXXXself.eat(DIV)
XXXXXXXXXXnode = BinOp(left=node, op=token, right=self.factor())
XXXXXXXXXXreturn node
def expr(self):
"""
XXXXXXXXXXexpr : term ((PLUS | MINUS) term)*
XXXXXXXXXXterm : factor ((MUL | DIV) factor)*
XXXXXXXXXXfactor : INTEGER | LPAREN expr RPAREN
"""