Problem 2

Evaluate mathematical expressions.

Please see page 3 and page 4 of Exercise 11.

First, provide a tokenizer and a parser for the mathematical expressions.

Second, evaluate the mathematical expressions. The functions cos, sin and tan need to be supported. The evaluation function is given a dictionary of parameter values.

An exception should be raised if a parameter has not been specified.

Classes:

TokenKind(value)	Define the token kind.
TokenizationRule(kind, pattern)	Define a regular expression which specifies a token.
Token(value, start, end, kind)	Represent a token of the source code.
UnOp(value)	Represent unary operators.
Associativity(value)	Represent the associativity of a binary operator.
BinOpInfo(precedence, associativity)	Specify precedence and associativity.
BinOp(value)	Represent binary operators.
Identifier(value)	Represent an identifier of a variable or of a function.
Expr()	Represent a valid expression as an abstract syntax tree (AST).
Constant(value)	Represent a constant in the AST.
Variable(identifier)	Represent a variable in the AST.
UnaryOperation(target, operator)	Represent an unary operation in the AST.
BinaryOperation(left, operator, right)	Represent a binary operation in the AST.
Call(name, argument)	Represent a function call in the AST.
TokensWoWhitespace(tokens)	Represent tokens without whitespace.

Data:

TOKENIZATION	Define rules so that we can map token kind 🠒 regular expression.
TOKENIZATION_MAP	Map token kind 🠒 rule to be matched for that token kind.
IDENTIFIER_RE	Express an identifier of a variable or a function.

Functions:

tokenize(text)	Tokenize the given text.
tokens_to_text(tokens)	Serialize the tokens back into the original text.
parse_tokens(tokens)	Parse the given tokens into an expression.
unparse(expr)	Convert the AST given as expr back to the source code as text.
evaluate(expr, lookup)	Evaluate the given expression expr substituting variables with lookup.
collect_variables(expr)	Go recursively over the expression and collect the variable names.

class TokenKind(value)

Define the token kind.

Attributes:

NUM	Number literal
VAR	Variable (or function) identifier
OP	Operator
OPEN	Opening parenthesis
CLOSE	Closing parenthesis
WHITESPACE	Whitespace (including tabs etc.)

NUM = 1

Number literal

VAR = 2

Variable (or function) identifier

OP = 4

Operator

OPEN = 5

Opening parenthesis

CLOSE = 6

Closing parenthesis

WHITESPACE = 7

Whitespace (including tabs etc.)

class TokenizationRule(kind: TokenKind, pattern: Pattern[str])

Define a regular expression which specifies a token.

Methods:

__init__(kind, pattern)	Initialize with the given values.
__repr__()	Represent the instance as a string for debugging.

__init__(kind: TokenKind, pattern: Pattern[str]) → None

Initialize with the given values.

__repr__() → str

Represent the instance as a string for debugging.

TOKENIZATION = [TokenizationRule(1, re.compile('(inf|0|[1-9][0-9]*)(\\.[0-9]+)?(e[+\\-]?[0-9]+)?')), TokenizationRule(2, re.compile('[a-zA-Z_][a-zA-Z_0-9]*')), TokenizationRule(4, re.compile('[+\\-*/^]')), TokenizationRule(5, re.compile('\\(')), TokenizationRule(6, re.compile('\\)')), TokenizationRule(7, re.compile('\\s+'))]

Define rules so that we can map token kind 🠒 regular expression.

TOKENIZATION_MAP: Mapping[TokenKind, TokenizationRule] = {<TokenKind.NUM: 1>: TokenizationRule(1, re.compile('(inf|0|[1-9][0-9]*)(\\.[0-9]+)?(e[+\\-]?[0-9]+)?')), <TokenKind.VAR: 2>: TokenizationRule(2, re.compile('[a-zA-Z_][a-zA-Z_0-9]*')), <TokenKind.OP: 4>: TokenizationRule(4, re.compile('[+\\-*/^]')), <TokenKind.OPEN: 5>: TokenizationRule(5, re.compile('\\(')), <TokenKind.CLOSE: 6>: TokenizationRule(6, re.compile('\\)')), <TokenKind.WHITESPACE: 7>: TokenizationRule(7, re.compile('\\s+'))}

Map token kind 🠒 rule to be matched for that token kind.

class Token(value: str, start: int, end: int, kind: TokenKind)

Represent a token of the source code.

Methods:

__init__(value, start, end, kind)	Initialize with the given values.
__eq__(other)	Compare against other of the same class based on all the properties.
__repr__()	Represent the instance as a string for debugging.

__init__(value: str, start: int, end: int, kind: TokenKind) → None

Initialize with the given values.

Requires

• start < end

• TOKENIZATION_MAP[kind].pattern.fullmatch(value)

__eq__(other: object) → bool

Compare against other of the same class based on all the properties.

Otherwise, propagate to object.__eq__.

__repr__() → str

Represent the instance as a string for debugging.

tokenize(text: str) → List[Token]

Tokenize the given text.

Ensures

• not (len(result) > 0)
  or result[0].start == 0
  

  (Text tokenized from the start)

• not (len(result) > 0)
  or result[-1].end == len(text)
  

  (Text tokenized till the end)

• all(
      token1.end == token2.start
      for token1, token2 in common.pairwise(result)
  )
  

  (Tokens consecutive)

• all(
      token.value == text[token.start:token.end]
      for token in result
  )
  

  (Token values correct)

• tokens_to_text(result) == text

tokens_to_text(tokens: Sequence[Token]) → str

Serialize the tokens back into the original text.

Ensures

• tokens == tokenize(result)

class UnOp(value)

Represent unary operators.

Attributes:

MINUS

Unary negative

MINUS = '-'

Unary negative

class Associativity(value)

Represent the associativity of a binary operator.

Attributes:

LEFT	Left associative
RIGHT	Right associative

LEFT = 'Left'

Left associative

RIGHT = 'Right'

Right associative

class BinOpInfo(precedence: int, associativity: Associativity)

Specify precedence and associativity.

Methods:

__init__(precedence, associativity)

__init__(precedence: int, associativity: Associativity) → None

class BinOp(value)

Represent binary operators.

Attributes:

ADD	Addition
SUB	Subtraction
MUL	Multiplication
DIV	Division
POW	Power

ADD = '+'

Addition

SUB = '-'

Subtraction

MUL = '*'

Multiplication

DIV = '/'

Division

POW = '^'

Power

IDENTIFIER_RE = re.compile('[a-zA-Z_][a-zA-Z0-9]*')

Express an identifier of a variable or a function.

class Identifier(value: str)

Represent an identifier of a variable or of a function.

Methods:

__new__(cls, value)

Enforce the identifier properties on value.

static __new__(cls, value: str) → Identifier

Enforce the identifier properties on value.

Requires

• IDENTIFIER_RE.fullmatch(value)

class Expr

Represent a valid expression as an abstract syntax tree (AST).

class Constant(value: float)

Represent a constant in the AST.

Methods:

__init__(value)	Initialize with the given values.
__eq__(other)	Compare against other of the same class based on the properties.
__repr__()	Represent the instance as a string for debugging.

__init__(value: float) → None

Initialize with the given values.

Requires

• not math.isnan(value)

• value >= 0.0

__eq__(other: object) → bool

Compare against other of the same class based on the properties.

Otherwise, propagate to object.__eq__.

__repr__() → str

Represent the instance as a string for debugging.

class Variable(identifier: Identifier)

Represent a variable in the AST.

Methods:

__init__(identifier)	Initialize with the given values.
__eq__(other)	Compare against other of the same class based on the properties.
__repr__()	Represent the instance as a string for debugging.

__init__(identifier: Identifier) → None

Initialize with the given values.

__eq__(other: object) → bool

Compare against other of the same class based on the properties.

Otherwise, propagate to object.__eq__.

__repr__() → str

Represent the instance as a string for debugging.

class UnaryOperation(target: Expr, operator: UnOp)

Represent an unary operation in the AST.

Methods:

__init__(target, operator)	Initialize with the given values.
__eq__(other)	Compare against other of the same class based on the properties.
__repr__()	Represent the instance as a string for debugging.

__init__(target: Expr, operator: UnOp) → None

Initialize with the given values.

__eq__(other: object) → bool

Compare against other of the same class based on the properties.

Otherwise, propagate to object.__eq__.

__repr__() → str

Represent the instance as a string for debugging.

class BinaryOperation(left: Expr, operator: BinOp, right: Expr)

Represent a binary operation in the AST.

Methods:

__init__(left, operator, right)	Initialize with the given values.
__eq__(other)	Compare against other of the same class based on the properties.
__repr__()	Represent the instance as a string for debugging.

__init__(left: Expr, operator: BinOp, right: Expr) → None

Initialize with the given values.

__eq__(other: object) → bool

Compare against other of the same class based on the properties.

Otherwise, propagate to object.__eq__.

__repr__() → str

Represent the instance as a string for debugging.

class Call(name: str, argument: Expr)

Represent a function call in the AST.

Methods:

__init__(name, argument)	Initialize with the given values.
__eq__(other)	Compare against other of the same class based on the properties.
__repr__()	Represent the instance as a string for debugging.

__init__(name: str, argument: Expr) → None

Initialize with the given values.

Requires

• re.fullmatch(r"(sin|cos|tan)", name)

__eq__(other: object) → bool

Compare against other of the same class based on the properties.

Otherwise, propagate to object.__eq__.

__repr__() → str

Represent the instance as a string for debugging.

class TokensWoWhitespace(tokens: Sequence[Token])

Represent tokens without whitespace.

Methods:

__new__(cls, tokens)	Enforce the properties on tokens.
__getitem__()	Get the token(s) at the given index.
__len__()	Return the number of the tokens.
__iter__()	Iterate over the tokens.

static __new__(cls, tokens: Sequence[Token]) → TokensWoWhitespace

Enforce the properties on tokens.

Requires

• all(token.kind != TokenKind.WHITESPACE for token in tokens)

__getitem__(index: int) → Token

__getitem__(index: slice) → TokensWoWhitespace

Get the token(s) at the given index.

__len__() → int

Return the number of the tokens.

__iter__() → Iterator[Token]

Iterate over the tokens.

parse_tokens(tokens: Sequence[Token]) → Expr

Parse the given tokens into an expression.

unparse(expr: Expr) → str

Convert the AST given as expr back to the source code as text.

Ensures

• parse_tokens(tokenize(result)) == expr

evaluate(expr: Expr, lookup: Mapping[Identifier, float]) → float

Evaluate the given expression expr substituting variables with lookup.

collect_variables(expr: Expr) → Set[Identifier]

Go recursively over the expression and collect the variable names.