Problem 1

Interpret mathematical programs developed in Exercise 11, Problem 1.

Instead of passing in the values for the expression evaluator, the variables are assigned values in the program.

(We exclude the part of the problem related to implementing a REPL as handling the user input/output is out-of-scope of this corpus.)

Classes:

TokenKind(value)	Define the token.
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.
Node()	Represent a node of an abstract syntax tree (AST) of a program.
Expr()	Represent a mathematical expression in an AST.
Constant(value)	Represent a constant in 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.
Function(value)	Enumerate the available functions.
Call(function, argument)	Represent a function call in the AST.
Statement()	Represent a statement in the AST.
Assign(target, expr)	Represent an assignment statement.
Program(body)	Represent a parsed program.
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_program(tokens)	Parse the given tokens into an abstract syntax tree of a program.
unparse(program)	Convert the AST back to the source code.
interpret(program)	Interpret the given program and return the values of the assigned variables.

class TokenKind(value)

Define the token.

Attributes:

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

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.)

ASSIGN = 8

Assignment

SEMICOLON = 9

Semicolon

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(8, re.compile('=')), TokenizationRule(9, re.compile(';')), TokenizationRule(7, re.compile('\\s+', re.MULTILINE))]

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.ASSIGN: 8>: TokenizationRule(8, re.compile('=')), <TokenKind.SEMICOLON: 9>: TokenizationRule(9, re.compile(';')), <TokenKind.WHITESPACE: 7>: TokenizationRule(7, re.compile('\\s+', re.MULTILINE))}

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

• len(value) == end - start

• 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)

Initialize with the given values.

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

Initialize with the given values.

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 Node

Represent a node of an abstract syntax tree (AST) of a program.

Methods:

__repr__()

Represent the instance as a string for debugging.

abstract __repr__() → str

Represent the instance as a string for debugging.

class Expr

Represent a mathematical expression in an AST.

Methods:

__repr__()

Represent the instance as a string for debugging.

abstract __repr__() → str

Represent the instance as a string for debugging.

class Constant(value: float)

Represent a constant in 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 Function(value)

Enumerate the available functions.

Attributes:

SIN	Sine
COS	Cosine
TAN	Tangent

SIN = 'sin'

Sine

COS = 'cos'

Cosine

TAN = 'tan'

Tangent

class Call(function: Function, argument: Expr)

Represent a function call in the AST.

Methods:

__init__(function, 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__(function: Function, argument: 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 Statement

Represent a statement in the AST.

Methods:

__repr__()

Represent the instance as a string for debugging.

abstract __repr__() → str

Represent the instance as a string for debugging.

class Assign(target: Identifier, expr: Expr)

Represent an assignment statement.

Methods:

__init__(target, expr)	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: Identifier, expr: 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 Program(body: List[Statement])

Represent a parsed program.

Methods:

__init__(body)	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__(body: List[Statement]) → 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 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_program(tokens: Sequence[Token]) → Program

Parse the given tokens into an abstract syntax tree of a program.

unparse(program: Program) → str

Convert the AST back to the source code.

Ensures

• parse_program(tokenize(result)) == program

interpret(program: Program) → Mapping[Identifier, float]

Interpret the given program and return the values of the assigned variables.