An interpreter for a calculator
The Python interpreter is the program that reads your code and carries it out. In this last lesson you write an interpreter of your own. It is much smaller than Python's: it understands one kind of line, arithmetic such as 2 * (3 + 4), and prints the line's value. By the end you will have a calculator that reads one line after another, prints each answer, and reports a clear error for a line it cannot work out.
That sounds easy until you look at what the program is given. 2 + 3 * 4 is 14, because * goes before +. Type it at Python's >>> prompt and Python prints 14, even though the + comes first in the line. Yet all Python received was nine characters. Something had to find the numbers and operators among them, work out that 3 * 4 belongs together, and only then do the arithmetic.
Our calculator has to do the same work, and we will build it in three stages, each taking the previous stage's result. Python and C++ run the first two stages on every program you write:
| Stage | Takes | Gives | For 2 * (3 + 4) |
|---|---|---|---|
| 1. Tokenize | the text | a list of tokens | 2 * ( 3 + 4 ) |
| 2. Parse | the tokens | an expression tree | (* 2 (+ 3 4)) |
| 3. Evaluate | the tree | a value | 14 |
The calculator language and its rules
Before writing any code, let's fix exactly what a line may contain and what its value is. A line of the calculator is an expression made of whole numbers, the operators +, -, * and /, and parentheses, with spaces allowed anywhere between them. Its value follows these rules:
- Parentheses are worked out first.
*and/have higher precedence than+and-, so they are done first.- Operators of the same precedence go from left to right, so
7 - 2 - 1means(7 - 2) - 1. /drops the fraction, which rounds toward zero, the way C++'s/does:7 / 2is 3 and(1 - 8) / 2is −3.- A number has no sign, so −3 is written
0 - 3.
Here are some lines and their values:
| Line | Value | Why |
|---|---|---|
2 + 3 * 4 | 14 | * before +: 2 + 12 |
(2 + 3) * 4 | 20 | parentheses first: 5 × 4 |
7 - 2 - 1 | 4 | left to right: 5 − 1 |
7 / 2 | 3 | the fraction of 3.5 is dropped |
(1 - 8) / 2 | −3 | −3.5 rounds toward zero |
8 / (3 - 3) | error | division by zero |
(2 + 3 | error | the ( is never closed |
Tokenizing: from characters to tokens
The first stage deals with the characters themselves. In 12*(3+45) the number twelve is two characters, and in 2 * 3 the spaces mean nothing. The later stages want the pieces 12, *, (, 3, +, 45, ). Each piece is a token, and a function that splits text into tokens is a tokenizer, also called a lexer. Ours walks the string with an index i and looks at the character there:
- a space is skipped;
- a digit starts a number, and the tokenizer keeps moving while it sees digits, so the whole run becomes one token;
- an operator or a parenthesis is a token of its own;
- any other character is not part of the language, and the tokenizer reports an error.
def tokenize(text):
tokens = []
i = 0
while i < len(text):
ch = text[i]
if ch == ' ':
i += 1
elif '0' <= ch <= '9':
start = i
while i < len(text) and '0' <= text[i] <= '9':
i += 1
tokens.append(text[start:i])
elif ch in '+-*/()':
tokens.append(ch)
i += 1
else:
raise ValueError('unknown character ' + ch)
return tokens
print(' '.join(tokenize(input())))Python details
'0' <= ch <= '9' compares character codes, which put the ten digits in order. text[start:i] is the slice from start up to, but not including, i.
The last branch is new. For a character the tokenizer does not know, such as $ in 2 $ 3, it raises an error of its own with raise ValueError(...). That stops the function at once, and every function waiting for its result, until some code catches the error. Nothing catches it yet, so the program stops with the message. The last part of the lesson catches it.
Expression trees
The tokens 2 * ( 3 + 4 ) are still a flat list. Nothing in it says that 3 + 4 has to happen before the *; to the program, the parentheses are just two more tokens. So the second stage turns the list into a tree. You have drawn trees like this before: max(abs(-8), min(5, 2 * 3)) became an expression tree with each call above its arguments. Here each operator sits above its two operands, and each number is a leaf:
Read it from the bottom up: the + node stands for , and the * above it for . The parentheses are gone, because the tree records that 3 + 4 belongs together by making it one operand of *. A node can be worked out only after its children, so the shape of the tree fixes the order of the work.
In the program, a leaf is just an int, and an operator node is a tuple (op, left, right). This tree is ('*', 2, ('+', 3, 4)).
To check what the second stage built, we need a way to print a tree on one line. The listings write each node as its operator followed by its two operands, inside parentheses: (* 2 (+ 3 4)). Every node gets its own pair of parentheses, so this form can be read without any precedence rules. Compilers call a tree like this an abstract syntax tree, or AST.
A grammar with one rule per level of precedence
Now for the stage that builds the tree, the parser. The simplest idea is to read the tokens left to right and attach each operator to everything before it. For 2 + 3 * 4 that builds (* (+ 2 3) 4), which is 20. The * should have taken the 3 and the 4 first, so the parser has to know about precedence.
The usual way to give it that knowledge is to describe the language with one rule for each level of precedence. A set of rules like this is a grammar:
expression = term, then any number of (+ or -) termterm = factor, then any number of (* or /) factorfactor = a number, or ( expression )A factor is a number or a whole expression in parentheses. A term is one or more factors joined by * and /, and an expression is one or more terms joined by + and -. So 2 + 3 * 4 is an expression with two terms, 2 and 3 * 4, and its second term has two factors. So the grammar groups 3 * 4 into one term before the + joins anything to it.
The grammar turns straight into code. Each rule becomes a function, and wherever a rule mentions another rule, its function calls that rule's function. "Any number of" becomes a while loop: read a term, then keep going while the next token is + or -. factor mentions expression for the part inside parentheses, so the three functions call each other: mutual recursion. Parsing with one function per grammar rule is called recursive descent.
Parsing: from tokens to a tree
Here is the parser. It is a class because its three functions share two pieces of data: the list of tokens, and pos, the position of the next token to read. Keeping data together with the functions that use it is what classes are for.
peek looks at the next token without using it up, and take uses it up; both give an empty string once the tokens run out. show prints a tree on one line, in the form from the last part.
def tokenize(text):
tokens = []
i = 0
while i < len(text):
ch = text[i]
if ch == ' ':
i += 1
elif '0' <= ch <= '9':
start = i
while i < len(text) and '0' <= text[i] <= '9':
i += 1
tokens.append(text[start:i])
elif ch in '+-*/()':
tokens.append(ch)
i += 1
else:
raise ValueError('unknown character ' + ch)
return tokens
class Parser:
def __init__(self, tokens):
self.tokens = tokens
self.pos = 0
def peek(self):
if self.pos < len(self.tokens):
return self.tokens[self.pos]
return ''
def take(self):
token = self.peek()
self.pos += 1
return token
def expression(self):
tree = self.term()
while self.peek() == '+' or self.peek() == '-':
op = self.take()
tree = (op, tree, self.term())
return tree
def term(self):
tree = self.factor()
while self.peek() == '*' or self.peek() == '/':
op = self.take()
tree = (op, tree, self.factor())
return tree
def factor(self):
token = self.take()
if token.isdigit():
return int(token)
if token == '(':
tree = self.expression()
if self.take() != ')':
raise ValueError('missing )')
return tree
if token == '':
raise ValueError('expression ends too early')
raise ValueError('unexpected ' + token)
def parse(text):
parser = Parser(tokenize(text))
tree = parser.expression()
if parser.peek() != '':
raise ValueError('unexpected ' + parser.peek())
return tree
def show(tree):
if type(tree) == int:
return str(tree)
op, left, right = tree
return '(' + op + ' ' + show(left) + ' ' + show(right) + ')'
print(show(parse(input())))Python details
type(tree) == int tells a leaf from an operator node, and op, left, right = tree unpacks a node's three parts.
factor takes one token. A number becomes a leaf; an opening parenthesis means an expression follows, so factor calls expression and then checks that the next token is ).
parse calls expression and then checks that every token was used. Without that check, 2 + 3) would parse as 2 + 3 and ignore the ).
Parsing 2 + 3 * 4 call by call
For 2 + 3 * 4 the parser prints the correct tree, (+ 2 (* 3 4)). The calls show how:
expressioncallsterm, which callsfactor, which takes2. Back interm, the next token is+, which is neither*nor/, sotermreturns the leaf 2.expressiontakes the+and callstermfor the right side. That call parses3, takes the*, parses4and returns the node(* 3 4).expressionmakes the node(+ 2 (* 3 4)), finds no more tokens and returns.
The multiplication was finished inside term before expression built its + node. An operator handled by a lower rule ends up deeper in the tree, so it is worked out first.
The loops group equal operators from the left. For 7 - 2 - 1, expression first builds (- 7 2), and at the second - that tree becomes the left operand of (- (- 7 2) 1), whose value is 4.
The tree for 7 - 2 - 1
Evaluating: from a tree to a value
Once the tree is right, the third stage is short. A tree is either a number or an operator with two subtrees, and the evaluator has the same two cases. A leaf's value is its number: that is the base case. For an operator node, the evaluator calls itself on the left subtree, then on the right, and combines the two results with the node's operator. Each call handles one node and trusts the calls below it for the rest: the recursive leap of faith.
def tokenize(text):
tokens = []
i = 0
while i < len(text):
ch = text[i]
if ch == ' ':
i += 1
elif '0' <= ch <= '9':
start = i
while i < len(text) and '0' <= text[i] <= '9':
i += 1
tokens.append(text[start:i])
elif ch in '+-*/()':
tokens.append(ch)
i += 1
else:
raise ValueError('unknown character ' + ch)
return tokens
class Parser:
def __init__(self, tokens):
self.tokens = tokens
self.pos = 0
def peek(self):
if self.pos < len(self.tokens):
return self.tokens[self.pos]
return ''
def take(self):
token = self.peek()
self.pos += 1
return token
def expression(self):
tree = self.term()
while self.peek() == '+' or self.peek() == '-':
op = self.take()
tree = (op, tree, self.term())
return tree
def term(self):
tree = self.factor()
while self.peek() == '*' or self.peek() == '/':
op = self.take()
tree = (op, tree, self.factor())
return tree
def factor(self):
token = self.take()
if token.isdigit():
return int(token)
if token == '(':
tree = self.expression()
if self.take() != ')':
raise ValueError('missing )')
return tree
if token == '':
raise ValueError('expression ends too early')
raise ValueError('unexpected ' + token)
def parse(text):
parser = Parser(tokenize(text))
tree = parser.expression()
if parser.peek() != '':
raise ValueError('unexpected ' + parser.peek())
return tree
def truncate_divide(a, b):
q = abs(a) // abs(b)
if (a < 0) != (b < 0):
return -q
return q
def evaluate(tree):
if type(tree) == int:
return tree
op, left, right = tree
a = evaluate(left)
b = evaluate(right)
if op == '+':
return a + b
if op == '-':
return a - b
if op == '*':
return a * b
if b == 0:
raise ValueError('division by zero')
return truncate_divide(a, b)
print(evaluate(parse(input())))Python details
As Operators showed, Python's // rounds down, so -7 // 2 is −4. The calculator rounds toward zero, so truncate_divide divides the sizes of the two numbers and puts the sign back: (1 - 8) / 2 gives −3.
The check for division by zero sits in the evaluator because only the evaluator knows the value of a right operand. 8 / (3 - 3) tokenizes and parses without trouble; the zero appears once 3 - 3 has been worked out.
Step through evaluate
This diagram steps through evaluate one frame at a time. The tree is written out in the program instead of parsed, and this evaluate handles only +, - and *.
In 2 * (3 + 4), stop where the leaf 4 is being evaluated. f1, for the whole tree, waits for b; f3, for (+ 3 4), also waits for its b; f5 is the call on the leaf. The open frames are always the path from the root of the tree down to the node being worked on.
In 7 - 2 - 1 the larger subtree is on the left, so the deep calls happen while the first call waits for a.
Deeper read: Python's own tree and bytecode
Python runs the same stages on your code. ast.dump(ast.parse('2 + 3 * 4', mode='eval')) prints its tree: a BinOp with op=Add() whose right operand is a BinOp with op=Mult(), the shape of (+ 2 (* 3 4)). Python then compiles the tree into bytecode, a list of simple instructions, and runs those. The dis module prints them: for a + b * c they load a, b and c, multiply, then add, the order in which evaluate finishes its calls. For 2 + 3 * 4 there is one instruction that loads 14, because the compiler works out arithmetic on constants in advance.
Python's eval runs all these stages on a string, so eval('2 + 3 * 4') is 14. It is no substitute for the calculator: eval('7 / 2') gives 3.5, and eval runs any Python code in the string, so a user could type a line that deletes files.
Reporting errors from each stage
Each stage reports the errors it can see:
- the tokenizer, for a character the language does not have, as in
2 $ 3; - the parser, for a missing
)in(2 + 3, a token left over in2 + 3), and a line that stops too early,2 +; - the evaluator, for division by zero in
8 / (3 - 3).
try runs a block of code. If anything inside it raises a ValueError, the program jumps to the except block, which prints the message, and carries on after it.
The finished calculator evaluates each line inside a try, so a bad line prints a message and the loop goes on. A program that reads, evaluates and prints in a loop like this is a read-eval-print loop, or REPL; Python's >>> prompt is one.
def tokenize(text):
tokens = []
i = 0
while i < len(text):
ch = text[i]
if ch == ' ':
i += 1
elif '0' <= ch <= '9':
start = i
while i < len(text) and '0' <= text[i] <= '9':
i += 1
tokens.append(text[start:i])
elif ch in '+-*/()':
tokens.append(ch)
i += 1
else:
raise ValueError('unknown character ' + ch)
return tokens
class Parser:
def __init__(self, tokens):
self.tokens = tokens
self.pos = 0
def peek(self):
if self.pos < len(self.tokens):
return self.tokens[self.pos]
return ''
def take(self):
token = self.peek()
self.pos += 1
return token
def expression(self):
tree = self.term()
while self.peek() == '+' or self.peek() == '-':
op = self.take()
tree = (op, tree, self.term())
return tree
def term(self):
tree = self.factor()
while self.peek() == '*' or self.peek() == '/':
op = self.take()
tree = (op, tree, self.factor())
return tree
def factor(self):
token = self.take()
if token.isdigit():
return int(token)
if token == '(':
tree = self.expression()
if self.take() != ')':
raise ValueError('missing )')
return tree
if token == '':
raise ValueError('expression ends too early')
raise ValueError('unexpected ' + token)
def parse(text):
parser = Parser(tokenize(text))
tree = parser.expression()
if parser.peek() != '':
raise ValueError('unexpected ' + parser.peek())
return tree
def truncate_divide(a, b):
q = abs(a) // abs(b)
if (a < 0) != (b < 0):
return -q
return q
def evaluate(tree):
if type(tree) == int:
return tree
op, left, right = tree
a = evaluate(left)
b = evaluate(right)
if op == '+':
return a + b
if op == '-':
return a - b
if op == '*':
return a * b
if b == 0:
raise ValueError('division by zero')
return truncate_divide(a, b)
for line in sys.stdin:
line = line.rstrip('\n')
if line == '':
continue
try:
print(evaluate(parse(line)))
except ValueError as error:
print('error:', error)Python details
for line in sys.stdin reads one line per pass until the input ends, and rstrip('\n') removes the newline each line ends with.
In (2 + 3, factor takes ( and calls expression, which parses 2 + 3 and returns at the end of the tokens; factor then expects ) and gets the empty string. Each open parenthesis is a factor call still waiting for its ).
Parentheses nested hundreds deep, like ((((1)))) but longer, pass all three stages' checks and can still stop the program, because each ( keeps three calls open: expression, term and factor. Python's recursion limit allows about 1,000 open calls, so about 330 nested parentheses raise a RecursionError, which the loop does not catch, and the program stops.
Checking parentheses with a depth counter
You can catch such a line before the parser starts, with no recursion at all. Checking only the parentheses takes one number, the depth: how many ( are open at each point of the line. Walk along the line, add 1 at each ( and subtract 1 at each ). The parentheses match when the depth never drops below zero and ends at zero. In (2 + 3 it ends at 1, one ) short; in 2 + 3) it drops to −1, one ( short. A calculator that counts the depth of each line first can report an error for a line nested more than, say, 100 deep, and its parser never sees that line.
The depth counter is also all you need for the next problem, which asks you to repair a line of parentheses instead of rejecting it. Where the depth drops below zero, a ( is missing; where it ends above zero, that many ) are missing:
You are given a string of characters, each ( or ). Insert some ( and ) characters anywhere in to make a correct bracket sequence, one in which every parenthesis is matched, such as (())(). Print the shortest sequence you can get; if there are several, print the one that comes first in dictionary order.
Constraints
- consists of
(and)
Sample 1 · Input
3 ())
Output
(())
Sample 2 · Input
6 )))())
Output
(((()))())
Sample 3 · Input
8 ))))((((
Output
(((())))(((())))
Common mistakes
Writing
expressionas a term, then-, then a recursive call toexpressionfor the rest.- Where it breaks
7 - 2 - 1becomes(- 7 (- 2 1))and prints 6 instead of 4.- The fix
- Use a loop that keeps the tree built so far on the left of each new node.
Reading
tokens[pos]directly instead of throughpeek.- Where it breaks
- On
2 +, Python raisesIndexErrorand C++ reads past the end of the vector (undefined behavior). - The fix
- Read tokens only through
peekandtake, which return the empty string at the end.
Recall What tree does the parser build for `(2 + 3) * 4`, and which call handles the `+`?
(* (+ 2 3) 4), whose value is 20. The + is handled by an expression call that factor makes after taking (, so it ends up as the left operand of *.
Recall Which stage reports the error in `8 / (3 - 3)`, and why not an earlier one?
The evaluator. Every character is a known token and the tokens fit the grammar. The divisor is zero only once 3 - 3 has been evaluated.
Key terms
| Term | Meaning |
|---|---|
| token | One meaningful piece of the text, such as 12, * or (. |
| tokenizer (lexer) | A function that splits text into tokens. |
| abstract syntax tree (AST) | The tree a parser builds: an operator at each inner node and a number at each leaf. |
| parser | The stage that turns tokens into a tree. |
| grammar | Rules that describe the structure of a language. |
| recursive descent | Parsing with one function per grammar rule. |
| raise / throw | Stop the current work and report an error, until a try block catches it. |
| read-eval-print loop (REPL) | A program that reads a line, evaluates it, prints the result and repeats. |
| depth (of parentheses) | How many ( are open at a point in the line. |
