a small expression language: lexer, parser, eval

Licence CC BY-NC-ND, Thierry Parmentelat

the pipeline¶

we’re building a tiny calculator that only knows about integers and the 4 operators + - * /, with parentheses for grouping.

three stages, three files:

stage	file	signature	input	output
lex	`lexer.py`	`tokenize(file)`	a file-like object	a generator of tokens (strings)
parse	`parser.py`	`parse(tokens)`	a list of tokens	an AST
eval	`eval.py`	`eval(ast)`	an AST	a number

an AST node is either

an int (a leaf), or
a 3-tuple (op, left, right) where op is one of "+" "-" "*" "/" and left, right are themselves AST nodes

for example the expression 1 + 2 * 3 gets tokenized into

['1', '+', '2', '*', '3']

then parsed into

('+', 1, ('*', 2, 3))

and finally evaluates to 7

the lexer¶

works on: generators, string methods
the input: any file-like object (an open file, or an io.StringIO) that contains a simple arithmetic expression, e.g.
```
(1 + 2) * 30
```
todo: write a generator function
```
def tokenize(file):
    ...
```
that reads through file and yields the tokens one at a time, as strings:
- a run of digits becomes one token, e.g. "30"
- each one of + - * / ( ) is its own token
- whitespace (including newlines) is simply skipped
tip: don’t call file.read(1) in a loop (that’s slow); instead iterate over file - which naturally yields lines - and then iterate over the characters of each line
bonus: also write a small convenience helper
```
def tokenize_string(string):
    ...
```
that wraps string in an io.StringIO and returns the list of tokens directly - handy for quick tests

def tokenize(file):
    ...

def tokenize_string(string):
    ...

and then you can check your code with

tokenize_string("1 + 2 * 3")

assert tokenize_string("1 + 2 * 3") == ['1', '+', '2', '*', '3']

---------------------------------------------------------------------------
AssertionError                            Traceback (most recent call last)
Cell In[3], line 1
----> 1 assert tokenize_string("1 + 2 * 3") == ['1', '+', '2', '*', '3']

AssertionError:

assert tokenize_string("(1 + 2) * 30") == ['(', '1', '+', '2', ')', '*', '30']

---------------------------------------------------------------------------
AssertionError                            Traceback (most recent call last)
Cell In[4], line 1
----> 1 assert tokenize_string("(1 + 2) * 30") == ['(', '1', '+', '2', ')', '*', '30']

AssertionError:

# whitespace, including newlines, is not significant
assert tokenize_string("  12\n+\n  7 ") == ['12', '+', '7']

---------------------------------------------------------------------------
AssertionError                            Traceback (most recent call last)
Cell In[5], line 2
      1 # whitespace, including newlines, is not significant
----> 2 assert tokenize_string("  12\n+\n  7 ") == ['12', '+', '7']

AssertionError:

the parser¶

works on: recursive-descent parsing, tuples

now that we can turn a string into a stream of tokens, we need to turn that stream into an AST.

we use a classic top-down (recursive-descent) parser, with one function per grammar rule; the grammar we implement is:

expr   := term (("+"|"-") term)*
term   := factor (("*"|"/") factor)*
factor := int | "(" expr ")"

todo: write
```
def parse(tokens):
    ...
```
that takes the list of tokens produced by the lexer, and returns the AST
you will probably want to write it as a set of mutually recursive helper functions, all shaped like tokens -> (ast, remaining_tokens):
- expr(tokens)
- term(tokens)
- factor(tokens)
parse itself just calls expr and makes sure there are no tokens left over

And now it’s your turn:

def parse(tokens):
    ...

parse(tokenize_string("1 + 2 * 3"))

assert parse(tokenize_string("1 + 2 * 3")) == ('+', 1, ('*', 2, 3))

---------------------------------------------------------------------------
AssertionError                            Traceback (most recent call last)
Cell In[8], line 1
----> 1 assert parse(tokenize_string("1 + 2 * 3")) == ('+', 1, ('*', 2, 3))

AssertionError:

# parentheses change the shape of the tree, not just the value
assert parse(tokenize_string("(1 + 2) * 3")) == ('*', ('+', 1, 2), 3)

---------------------------------------------------------------------------
AssertionError                            Traceback (most recent call last)
Cell In[9], line 2
      1 # parentheses change the shape of the tree, not just the value
----> 2 assert parse(tokenize_string("(1 + 2) * 3")) == ('*', ('+', 1, 2), 3)

AssertionError:

# left-associativity: a - b - c is (a - b) - c, not a - (b - c)
assert parse(tokenize_string("10 - 2 - 3")) == ('-', ('-', 10, 2), 3)

---------------------------------------------------------------------------
AssertionError                            Traceback (most recent call last)
Cell In[10], line 2
      1 # left-associativity: a - b - c is (a - b) - c, not a - (b - c)
----> 2 assert parse(tokenize_string("10 - 2 - 3")) == ('-', ('-', 10, 2), 3)

AssertionError:

eval¶

works on: recursion, dict-as-a-switch
todo: write
```
def eval(ast):
    ...
```
that computes the value described by ast

def eval(ast):
    ...

assert eval(parse(tokenize_string("1 + 2 * 3"))) == 7

---------------------------------------------------------------------------
AssertionError                            Traceback (most recent call last)
Cell In[12], line 1
----> 1 assert eval(parse(tokenize_string("1 + 2 * 3"))) == 7

AssertionError:

assert eval(parse(tokenize_string("(1 + 2) * 3"))) == 9

---------------------------------------------------------------------------
AssertionError                            Traceback (most recent call last)
Cell In[13], line 1
----> 1 assert eval(parse(tokenize_string("(1 + 2) * 3"))) == 9

AssertionError:

assert eval(parse(tokenize_string("10 - 2 - 3"))) == 5

---------------------------------------------------------------------------
AssertionError                            Traceback (most recent call last)
Cell In[14], line 1
----> 1 assert eval(parse(tokenize_string("10 - 2 - 3"))) == 5

AssertionError:

assert eval(parse(tokenize_string("(30 + 40 + 50) * (20 - 15)"))) == 600

---------------------------------------------------------------------------
AssertionError                            Traceback (most recent call last)
Cell In[15], line 1
----> 1 assert eval(parse(tokenize_string("(30 + 40 + 50) * (20 - 15)"))) == 600

AssertionError:

putting it all together¶

now that the 3 stages are in place, you can write a one-liner that goes straight from source to value:

def run(string):
    return eval(parse(tokenize_string(string)))

assert run("2 * (3 + 4) - 5") == 9

---------------------------------------------------------------------------
AssertionError                            Traceback (most recent call last)
Cell In[17], line 1
----> 1 assert run("2 * (3 + 4) - 5") == 9

AssertionError:

going further (optional)¶

a few ways you could extend this toy language, if you want to keep going:

support unary minus, e.g. -3 + 4 or -(1 + 2)
support floats, not just integers
raise a proper, informative exception (instead of an obscure crash) when the input is malformed, e.g. "1 +" or "(1 + 2"
replace the list of tokens with the generator returned by tokenize directly - does parse still work if it can only look one token ahead, and can’t index or slice into it?