# Simple interpreter from scratch in Python

The thing that attracted me most to computer science in college was the compiler. I thought it was almost magical how compilers could read even my poorly written source code and generate complicated programs. When I finally took a course in compilers, I found the process to be a lot simpler than I expected.

In this series of articles, I will attempt to capture some of this simplicity by writing an interpreter for a basic imperative language called IMP. The interpreter will be written in Python since it’s a simple, widely known language. Python code looks like pseudocode, so even if you don’t know Python, you’ll be able to understand it. Parsing will be done with a simple set of parser combinators made from scratch (explained in the next article in this series). No external libraries will be used except for `sys` (for I/O), `re` (for regular expressions in the lexer), and `unittest` (to make sure everything works).

## The IMP language

Before we start writing, let’s discuss the language we’ll be interpreting. IMP is a minimal imperative language with the following constructs:

Assignment statements (all variables are global and can only store integers):

`x := 1`

Conditional statements:

```if x = 1 then
y := 2
else
y := 3
end
```

While loops:

```while x < 10 do
x := x + 1
end
```

Compound statements (separated by semicolons):

```x := 1;
y := 2
```

Okay, so it’s just a toy language, but you could easily extend it to be something more useful like Lua or Python. I wanted to keep things as simple as possible for this tutorial.

Here’s an example of a program which computes a factorial:

```n := 5;
p := 1;
while n > 0 do
p := p * n;
n := n - 1
end
```

IMP provides no way to read input, so the initial state must be set with a series of assignment statements at the beginning of the program. There is also no way to print results, so the interpreter will print the values of all variables at the end of the program.

## Structure of the interpreter

The core of the interpreter is the intermediate representation (IR). This is how we represent IMP programs in memory. Since IMP is such a simple language, the intermediate representation will correspond directly to the syntax of the language; there will be a class for each kind of expression or statement. In a more complicated language, you would want not only a syntactic representation but also a semantic representation which is easier to analyze or execute.

The interpreter will execute in three stages:

1. Split characters in the source code into tokens
2. Organize the tokens into an abstract syntax tree (AST). The AST is our intermediate representation.
3. Evaluate the AST and print the state at the end

The process of splitting characters into tokens is called lexing and is performed by a lexer. Tokens are short, easily digestible strings that contain the most basic parts of the program such as numbers, identifiers, keywords, and operators. The lexer will drop whitespace and comments, since they are ignored by the interpreter.

The process of organizing tokens into an abstract syntax tree (AST) is called parsing. The parser extracts the structure of the program into a form we can evaluate.

The process of actually executing the parsed AST is called evaluation. This is actually the simplest part of the interpreter.

This article will focus solely on the lexer. We will write a generic lexer library, then use it to create a lexer for IMP. The next articles will focus on the parser and the evaluator.

## The lexer library

The operation of the lexer is fairly simple. It is heavily based on regular expressions, so if you’re not familiar with them, you might want to read up. In short, a regular expression is a specially formatted string that describes other strings. You can use them to match strings like phone numbers or e-mail addresses, or in our case, different kinds of tokens.

The input to the lexer will be just a stream of characters. To keep things simple, we will read an entire input file into memory. The output will be a list of tokens. Each token comprises a value (the string it represents) and a tag (to indicate what kind of token it is). The parser will use both to decide how to create the AST.

Since the operation of a lexer for any language is pretty similar, we will create a generic lexer which takes a list of regular expressions and corresponding tags. For each expression, it will check whether the input text matches at the current position. If a match is found, the matching text is extracted into a token, along with the regular expression’s tag. If the regular expression has no tag associated with it, the text is discarded. This lets us get rid of junk characters, like comments and whitespace. If there is no matching regular expression, we report an error and quit. This process is repeated until there are no more characters left to match.

Here is the code from the lexer library:

```import sys
import re

def lex(characters, token_exprs):
pos = 0
tokens = []
while pos < len(characters):
match = None
for token_expr in token_exprs:
pattern, tag = token_expr
regex = re.compile(pattern)
match = regex.match(characters, pos)
if match:
text = match.group(0)
if tag:
token = (text, tag)
tokens.append(token)
break
if not match:
sys.stderr.write('Illegal character: %s\\n' % characters[pos])
sys.exit(1)
else:
pos = match.end(0)
```

Note that the order we pass in the regular expressions is significant. `lex` will iterate over the expressions and will accept the first one that matches. This means, when using `lex`, we should put the most specific expressions first (like those matching operators and keywords), followed by the more general expressions (like those for identifiers and numbers).

## The IMP lexer

Given the `lex` function above, defining a lexer for IMP is very simple. The first thing we do is define a series of tags for our tokens. IMP only needs three tags. `RESERVED` indicates a reserved word or operator. `INT` indicates a literal integer. `ID` is for identifiers.

```import lexer

RESERVED = 'RESERVED'
INT      = 'INT'
ID       = 'ID'
```

Next we define the token expressions that will be used in the lexer. The first two expressions match whitespace and comments. These have no tag, so `lex` will drop any characters that they match.

```token_exprs = [
(r'[ \n\t]+',              None),
(r'#[^\n]*',               None),
```

After that, we have all our operators and reserved words. Remember, the “r” before each regular expression means the string is “raw”; Python will not handle any escape characters. This allows us to include backslashes in the strings, which are used by the regular expression engine to escape operators like “+” and “*”.

```    (r'\:=',                   RESERVED),
(r'\(',                    RESERVED),
(r'\)',                    RESERVED),
(r';',                     RESERVED),
(r'\+',                    RESERVED),
(r'-',                     RESERVED),
(r'\*',                    RESERVED),
(r'/',                     RESERVED),
(r'<=',                    RESERVED),
(r'<',                     RESERVED),
(r'>=',                    RESERVED),
(r'>',                     RESERVED),
(r'=',                     RESERVED),
(r'!=',                    RESERVED),
(r'and',                   RESERVED),
(r'or',                    RESERVED),
(r'not',                   RESERVED),
(r'if',                    RESERVED),
(r'then',                  RESERVED),
(r'else',                  RESERVED),
(r'while',                 RESERVED),
(r'do',                    RESERVED),
(r'end',                   RESERVED),
```

Finally, we have expressions for integers and identifiers. Note that the regular expression for identifiers would match all of the reserved words above, so it is important that this comes last.

```    (r'[0-9]+',                INT),
(r'[A-Za-z][A-Za-z0-9_]*', ID),
]
```

Now that our regular expressions are defined, we need to create an actual lexer function.

```def imp_lex(characters):
return lexer.lex(characters, token_exprs)
```

If you’re curious to try this, here’s some driver code to test it out:

```import sys
from imp_lexer import *

if __name__ == '__main__':
filename = sys.argv[1]
file = open(filename)
file.close()
tokens = imp_lex(characters)
for token in tokens:
print token
```

## What are parser combinators?

There are many, many ways to build a parser. Combinators are probably the easiest and fastest way to get a parser up and running.

You can think of a parser as a function. It accepts a stream of tokens as input. If successful, the parser will consume some tokens from the stream. It will return part of the final AST, along with the remaining tokens. A combinator is a function which produces a parser as its output, usually after taking one or more parsers as input, hence the name “combinator”. You can use combinators to create a complete parser for a language like IMP by creating lots of smaller parsers for parts of the language, then using combinators to build the final parser.

## A minimal combinator library

Parser combinators are fairly generic, and can be used with any language. As we did with the lexer, we’ll start by writing a language agnostic library of combinators, then use that to write our IMP parser.

First, let’s define a `Result` class. Every parser will return a `Result` object on success or `None` on failure. A `Result` comprises a `value` (part of the AST), and a position (the index of the next token in the stream).

```class Result:
def __init__(self, value, pos):
self.value = value
self.pos = pos

def __repr__(self):
return 'Result(%s, %d)' % (self.value, self.pos)
```

Next, we’ll define a base class, `Parser`. Earlier, I said parsers are functions which take a stream of tokens as input. We will actually be defining parsers as objects with a `__call__` method. This means that a parser object will behave as if it were a function, but we can also provide additional functionality by defining some operators.

```class Parser:
def __call__(self, tokens, pos):
return None  # subclasses will override this

return Concat(self, other)

def __mul__(self, other):
return Exp(self, other)

def __or__(self, other):
return Alternate(self, other)

def __xor__(self, function):
return Process(self, function)
```

The method that actually does the parsing is `__call__`. The input is the full list of tokens (returned by the lexer) and an index into the list indicating the next token. The default implementation always returns `None` (failure). Subclasses of `Parser` will provide their own `__call__` implementation.

The other methods, `__add__``__mul__``__or__`, and `__xor__` define the `+``*``|`, and `^` operators, respectively. Each operator provides a shortcut for calling a different combinator. We’ll cover each of these combinators shortly.

Next, we’ll look at the simplest combinator, `Reserved``Reserved` will be used to parse reserved words and operators; it will accept tokens with a specific value and tag. Remember, tokens are just value-tag pairs. `token[0]` is the value, `token[1]` is the tag.

```class Reserved(Parser):
def __init__(self, value, tag):
self.value = value
self.tag = tag

def __call__(self, tokens, pos):
if pos < len(tokens) and \
tokens[pos][0] == self.value and \
tokens[pos][1] is self.tag:
return Result(tokens[pos][0], pos + 1)
else:
return None
```

At this point, you might stop and say, “I thought combinators were going to be functions returning parsers. This subclass doesn’t look like a function.” It is like a function though, if you think of a constructor as a function which returns an object (which in this case also happens to be callable). Subclassing is an easy way to define a new combinator since all we need to do is provide a constructor and a `__call__` method, and we still retain other functionality (like the overloaded operators).

Moving on, the `Tag` combinator is very similar to `Reserved`. It matches any token which has a particular tag. The value can be anything.

```class Tag(Parser):
def __init__(self, tag):
self.tag = tag

def __call__(self, tokens, pos):
if pos < len(tokens) and tokens[pos][1] is self.tag:
return Result(tokens[pos][0], pos + 1)
else:
return None
```

The `Tag` and `Reserved` combinators are our primitives. All combinators will be built out of them at the most basic level.

The `Concat` combinator will take two parsers as input (left and right). When applied, a `Concat` parser will apply the left parser, followed by the right parser. If both are successful, the result value will be a pair containing the left and right results. If either parser is unsuccessful, `None` is returned.

```class Concat(Parser):
def __init__(self, left, right):
self.left = left
self.right = right

def __call__(self, tokens, pos):
left_result = self.left(tokens, pos)
if left_result:
right_result = self.right(tokens, left_result.pos)
if right_result:
combined_value = (left_result.value, right_result.value)
return Result(combined_value, right_result.pos)
return None
```

`Concat` is useful for parsing specific sequences of tokens. For instance, to parse `1 + 2`, you could write:

```parser = Concat(Concat(Tag(INT), Reserved('+', RESERVED)), Tag(INT))
```

or more concisely using the `+` operator shorthand:

```parser = Tag(INT) + Reserved('+', RESERVED) + Tag(INT)
```

The `Alternate` combinator is similar. It also takes left and right parsers. It starts by applying the left parser. If successful, that result is returned. If unsuccessful, it applies the right parser and returns its result.

```class Alternate(Parser):
def __init__(self, left, right):
self.left = left
self.right = right

def __call__(self, tokens, pos):
left_result = self.left(tokens, pos)
if left_result:
return left_result
else:
right_result = self.right(tokens, pos)
return right_result
```

`Alternate` is useful for choosing among several possible parsers. For instance, if we wanted to parse any binary operator:

```parser = Reserved('+', RESERVED) |
Reserved('-', RESERVED) |
Reserved('*', RESERVED) |
Reserved('/', RESERVED)
```

`Opt` is useful for optional text, such as the else-clause of an if-statement. It takes one parser as input. If that parser is successful when applied, the result is returned normally. If it fails, a successful result is still returned, but the value of that result is `None`. No tokens are consumed in the failure case; the result position is the same as the input position.

```class Opt(Parser):
def __init__(self, parser):
self.parser = parser

def __call__(self, tokens, pos):
result = self.parser(tokens, pos)
if result:
return result
else:
return Result(None, pos)
```

`Rep` applies its input parser repeatedly until it fails. This is useful for generating lists of things. Note that `Rep` will successfully match an empty list and consume no tokens if its parser fails the first time it’s applied.

```class Rep(Parser):
def __init__(self, parser):
self.parser = parser

def __call__(self, tokens, pos):
results = []
result = self.parser(tokens, pos)
while result:
results.append(result.value)
pos = result.pos
result = self.parser(tokens, pos)
return Result(results, pos)
```

`Process` is a useful combinator which allows us to manipulate result values. Its input is a parser and a function. When the parser is applied successfully, the result value is passed to the function, and the return value from the function is returned instead of the original value. We will use `Process` to actually build the AST nodes out of the pairs and lists that `Concat` and `Rep` return.

```class Process(Parser):
def __init__(self, parser, function):
self.parser = parser
self.function = function

def __call__(self, tokens, pos):
result = self.parser(tokens, pos)
if result:
result.value = self.function(result.value)
return result
```

As an example, consider the parser we built with `Concat`. When it parses `1 + 2`, the result value we actually get back is `(('1', '+'), '2')`, which is not very useful. With `Process` we can change that result. For example, the following parser would sum the parsed expression.

```def process_func(parsed):
((l, _), r) = parsed
return int(l) + int(r)

better_parser = parser ^ process_func
```

`Lazy` is a less obviously useful combinator. Instead of taking an input parser, it takes a zero-argument function which returns a parser. `Lazy` will not call the function to get the parser until it’s applied. This is needed to build recursive parsers (like how arithmetic expressions can include arithmetic expressions). Since such a parser refers to itself, we can’t just define it by referencing it directly; at the time the parser’s defining expression is evaluated, the parser is not defined yet. We would not need this in a language with lazy evaluation like Haskell or Scala, but Python is anything but lazy.

```class Lazy(Parser):
def __init__(self, parser_func):
self.parser = None
self.parser_func = parser_func

def __call__(self, tokens, pos):
if not self.parser:
self.parser = self.parser_func()
return self.parser(tokens, pos)
```

The next combinator, `Phrase`, takes a single input parser, applies it, and returns its result normally. The only catch is that it will fail if its input parser did not consume all of the remaining tokens. The top level parser for IMP will be a `Phrase` parser. This prevents us from partially matching a program which has garbage at the end.

```class Phrase(Parser):
def __init__(self, parser):
self.parser = parser

def __call__(self, tokens, pos):
result = self.parser(tokens, pos)
if result and result.pos == len(tokens):
return result
else:
return None
```

The last combinator is unfortunately the most complicated. `Exp` is fairly specialized; it’s used to match an expression which consists of a list of elements separated by something. Here’s an example with compound statements:

```a := 10;
b := 20;
c := 30
```

In this case, we have a list of statements separated by semicolons. You might think that we don’t need `Exp` since we can do the same thing with the other combinators. We could just write a parser for the compound statement like this:

```def compound_stmt():
return stmt() + Reserved(';', RESERVED) + stmt()
```

Think about how `stmt` might be defined though.

```def stmt():
return Lazy(compound_stmt) | assign_stmt()
```

So `stmt` starts by calling `compound_stmt`, which starts by calling `stmt`. These parsers will call each other over and over without getting anything done until we get a stack overflow. This problem is not limited to compound statements; arithmetic and Boolean expressions have the same problem (think about operators like `+` or `and` as the separators). This problem is called left recursion, and parser combinators are bad at it.

Fortunately, `Exp` provides a way to work around left recursion, just by matching a list, similar to the way `Rep` does. `Exp` takes two parsers as input. The first parser matches the actual elements of the list. The second matches the separators. On success, the separator parser must return a function which combines elements parsed on the left and right into a single value. This value is accumulated for the whole list, left to right, and is ultimately returned.

Let’s look at the code:

```class Exp(Parser):
def __init__(self, parser, separator):
self.parser = parser
self.separator = separator

def __call__(self, tokens, pos):
result = self.parser(tokens, pos)

def process_next(parsed):
(sepfunc, right) = parsed
return sepfunc(result.value, right)
next_parser = self.separator + self.parser ^ process_next

next_result = result
while next_result:
next_result = next_parser(tokens, result.pos)
if next_result:
result = next_result
return result
```

`result` will always contain everything that’s been parsed so far. `process_next` is a function that can be used with `Process``next_parser` will apply `separator` followed by `parser` to get the next element of the list. `process_next` will create a new result by applying the separator function to the current `result` and the newly parsed element. `next_parser` is applied in a loop until it can’t match any more elements.

Let’s see how `Exp` can be used to solve our `compound_stmt` problem.

```def assign_stmt():
...

def compound_sep():
def process_sep(parsed):
return lambda l, r: CompoundStmt(l, r)
return Reserved(';', RESERVED) ^ process_sep

def compound_stmt():
return Exp(assign_stmt(), compound_sep())
```

We could also write this as:

```def compound_stmt():
return assign_stmt() * compound_sep()
```

## Defining the AST

Before we can actually start writing our parsers, we need to define the data structures that will be the output of our parser. We will do this with classes. Every syntactic element of IMP will have a corresponding class. Objects of these classes will represent nodes in the AST.

There are three kinds of structures in IMP: arithmetic expressions (used to compute numbers), Boolean expressions (used to compute conditions for if- and while-statements), and statements. We will start with arithmetic expressions, since the other two elements depend on them.

An arithmetic expression can take one of three forms:

• Literal integer constants, such as `42`
• Variables, such as `x`
• Binary operations, such as `x + 42`. These are made out of other arithmetic expressions.

We can also group expressions together with parenthesis (like `(x + 2) * 3`. This isn’t a different kind of expression so much as a different way to parse the expression.

We will define three classes for these forms, plus a base class for arithmetic expressions in general. For now, the classes won’t do much except contain data. We will include a `__repr__` method, so we can print out the AST for debugging. All AST classes will subclass `Equality` so we can check if two AST objects are the same. This helps with testing.

```from equality import *

class Aexp(Equality):
pass

class IntAexp(Aexp):
def __init__(self, i):
self.i = i

def __repr__(self):
return 'IntAexp(%d)' % self.i

class VarAexp(Aexp):
def __init__(self, name):
self.name = name

def __repr__(self):
return 'VarAexp(%s)' % self.name

class BinopAexp(Aexp):
def __init__(self, op, left, right):
self.op = op
self.left = left
self.right = right

def __repr__(self):
return 'BinopAexp(%s, %s, %s)' % (self.op, self.left, self.right)
```

Boolean expressions are a little more complicated. There are four kinds of Boolean expressions.

• Relational expressions (such as `x < 10`)
• And expressions (such as `x < 10 and y > 20`)
• Or expressions
• Not expressions

The left and right sides of a relational expression are arithmetic expressions. The left and right sides of an “and”, “or”, or “not” expression are Boolean expressions. Restricting the type like this helps us avoid nonsensical expressions like “x < 10 and 30”.

```class Bexp(Equality):
pass

class RelopBexp(Bexp):
def __init__(self, op, left, right):
...

class AndBexp(Bexp):
def __init__(self, left, right):
...
class OrBexp(Bexp):
def __init__(self, left, right):
...

class NotBexp(Bexp):
def __init__(self, exp):
...
```

Statements can contain both arithmetic and Boolean expressions. There are four kinds of statements: assignment, compound, conditional, and loop.

```class Statement(Equality):
pass

class AssignStatement(Statement):
def __init__(self, name, aexp):
...

class CompoundStatement(Statement):
def __init__(self, first, second):
...

class IfStatement(Statement):
def __init__(self, condition, true_stmt, false_stmt):
...

class WhileStatement(Statement):
def __init__(self, condition, body):
...
```

## Primitives

Now that we have our AST classes and a convenient set of parser combinators, it’s time to write our parser. When writing a parser, it’s usually easiest to start with the most basic structures of the language and work our way up.

The first parser we’ll look at is the `keyword` parser. This is just a specialized version of the `Reserved` combinator using the `RESERVED` tag that all keyword tokens are tagged with. Remember, `Reserved` matches a single token where both the text and tag are the same as the ones given.

```def keyword(kw):
return Reserved(kw, RESERVED)
```

`keyword` is actually a combinator because it is a function that returns a parser. We will use it directly in other parsers though.

The `id` parser is used to match variable names. It uses the `Tag` combinator, which matches a token with the specified tag.

```id = Tag(ID)
```

The `num` parser is used to match integers. It works just like `id`, except we use the `Process` combinator (actually the `^` operator, which calls `Process`) to convert the token into an actual integer value.

```num = Tag(INT) ^ (lambda i: int(i))
```

## Parsing arithmetic expressions

Parsing arithmetic expressions is not particularly simple, but since we need to parse arithmetic expressions in order to parse Boolean expressions or statements, we will start there.

We’ll first define the `aexp_value` parser, which will convert the values returned by `num` and `id` into actual expressions.

```def aexp_value():
return (num ^ (lambda i: IntAexp(i))) | \
(id  ^ (lambda v: VarAexp(v)))
```

We’re using the `|` operator here, which is a shorthand for the `Alternate` combinator. So this will attempt to parse an integer expression first. If that fails, it will try to parse a variable expression.

You’ll notice that we defined `aexp_value` as a zero-argument function instead of a global value, like we did with `id` and `num`. We’ll do the same thing with all the other parsers. The reason is that we don’t want the code for each parser to be evaluated right away. If we defined every parser as a global, each parser would not be able to reference parsers that come after it in the same source file, since they would not be defined yet. This would make recursive parsers impossible to define, and the source code would be awkward to read.

Next, we’d like to support grouping with parenthesis in our arithmetic expressions. Although grouped expressions don’t require their own AST class, they do require another parser to handle them.

```def process_group(parsed):
((_, p), _) = parsed
return p

def aexp_group():
return keyword('(') + Lazy(aexp) + keyword(')') ^ process_group
```

`process_group` is a function we use with the `Process` combinator (`^` operator). It just discards the parenthesis tokens and returns the expression in between. `aexp_group` is the actual parser. Remember, the `+` operator is shorthand for the `Concat` combinator. So this will parse `'('`, followed by an arithmetic expression (parsed by `aexp`, which we will define soon), followed by `')'`. We need to avoid calling `aexp` directly since `aexp` will call `aexp_group`, which would result in infinite recursion. To do this, we use the `Lazy` combinator, which defers the call to `aexp` until the parser is actually applied to some input.

Next, we combine `aexp_value` and `aexp_group` using `aexp_term`. An `aexp_term` expression is any basic, self-contained expression where we don’t have to worry about operator precedence with respect to other expressions.

```def aexp_term():
return aexp_value() | aexp_group()
```

Now we come to the tricky part: operators and precedence. It would be easy for us just to define another kind of `aexp` parser and throw it together with `aexp_term`. This would result in a simple expression like:

```1 + 2 * 3
```

being parsed incorrectly as:

```(1 + 2) * 3
```

The parser needs to be aware of operator precedence, and it needs to group together operations with higher precedence.

We will define a few helper functions in order to make this work.

```def process_binop(op):
return lambda l, r: BinopAexp(op, l, r)
```

`process_binop` is what actually constructs `BinopAexp` objects. It takes any arithmetic operator and returns a function that combines a pair of expressions using that operator.

`process_binop` will be used with the `Exp` combinator (`*` operator). `Exp` parses a list of expressions with a separator between each pair of expressions. The left operand of `Exp` is a parser that will match individual elements of the list (arithmetic expressions in our case). The right operand is a parser that will match the separators (operators). No matter what separator is matched, the right parser will return a function which, given the matched separator, returns a combining function. The combining function takes the parsed expressions to the left and right of the separator and returns a single, combined expression. Confused yet? We’ll go through the usage of `Exp` shortly. `process_binop` is actually what will be returned by the right parser.

Next, we’ll define our precedence levels and a combinator to help us deal with them.

```def any_operator_in_list(ops):
op_parsers = [keyword(op) for op in ops]
parser = reduce(lambda l, r: l | r, op_parsers)
return parser

aexp_precedence_levels = [
['*', '/'],
['+', '-'],
]
```

`any_operator_in_list` takes a list of keyword strings and returns a parser that will match any of them. We will call this on `aexp_precedence_levels`, which contains a list of operators for each precedence level (highest precedence first).

```def precedence(value_parser, precedence_levels, combine):
def op_parser(precedence_level):
return any_operator_in_list(precedence_level) ^ combine
parser = value_parser * op_parser(precedence_levels[0])
for precedence_level in precedence_levels[1:]:
parser = parser * op_parser(precedence_level)
return parser
```

`precedence` is the real meat of the operation. Its first argument, `value_parser` is a parser than can read the basic parts of an expression: numbers, variables, and groups. That will be `aexp_term``precedence_levels` is a list of lists of operators, one list for each level. We’ll use `aexp_precedence_levels` for this. `combine` will take a function which, given an operator, returns a function to build a larger expression out of two smaller expressions. That’s `process_binop`.

Inside `precedence`, we first define `op_parser` which, for a given precedence level, reads any operator in that level and returns a function which combines two expressions. `op_parser` can be used as the right-hand argument of `Exp`. We start by calling `Exp` with `op_parser` for the highest precedence level, since these operations need to be grouped together first. We then use the resulting parser as the element parser (`Exp`‘s left argument) at the next level. After the loop finishes, the resulting parser will be able to correctly parse any arithmetic expression.

How does this work in practice? Let’s work it through.

```E0 = value_parser
E1 = E0 * op_parser(precedence_levels[0])
E2 = E1 * op_parser(precedence_levels[1])
```

`E0` is the same as `value_parser`. It can parse numbers, variables, and groups, but no operators. E1 can parse expressions containing anything E0 can match, separated by operators in the first precedence level. So `E1` could match `a * b / c`, but it would raise an error as soon as it encountered a `+` operator. `E2` can match expressions `E2` can match, separated by operators in the next precedence level. Since we only have two precedence levels, `E2` can match any arithmetic expression we support.

Let’s do an example. We’ll take a complicated arithmetic expression, and gradually replace each part by what matches it.

```4 * a + b / 2 - (6 + c)
E0(4) * E0(a) + E0(b) / E0(2) - E0(6+c)
E1(4*a) + E1(b/2) - E1(6+c)
E2((4*a)+(b/2)-(6+c))
```

We use `precedence` to directly define `aexp`:

```def aexp():
return precedence(aexp_term(),
aexp_precedence_levels,
process_binop)
```

We probably could have defined precedence in a less abstract way, but its strength is that it applies to any situation where operator precedence is a problem. We will use it again to parse Boolean expressions.

## Parsing Boolean expressions

With arithmetic expressions out of the way, we can move on to Boolean expressions. Boolean expressions are actually simpler than arithmetic expressions, and we won’t need any new tools to parse them. We’ll start with the most basic Boolean expression, the relation:

```def process_relop(parsed):
((left, op), right) = parsed
return RelopBexp(op, left, right)

def bexp_relop():
relops = ['<', '<=', '>', '>=', '=', '!=']
return aexp() + any_operator_in_list(relops) + aexp() ^ process_relop
```

`process_relop` is just a function that we use with the `Process` combinator. It just takes three concatenated values and creates a `RelopBexp` out of them. In `bexp_relop`, we parse two arithmetic expressions (`aexp`), separated by a relational operator. We use our old friend `any_operator_in_list` so we don’t have to write a case for every operator. There is no need to use combinators like `Exp` or `precedence` since relational expressions can’t be chained together in IMP like they can in other languages.

Next, we define the `not` expression. `not` is a unary operation with high precedence. This makes it much easier to parse than `and` and `or` expressions.

```def bexp_not():
return keyword('not') + Lazy(bexp_term) ^ (lambda parsed: NotBexp(parsed[1]))
```

Here, we just concatenate the keyword `not` with a Boolean expression term (which we will define next). Since `bexp_not` will be used to define `bexp_term`, we need to use the `Lazy` combinator to avoid infinite recursion.

```def bexp_group():
return keyword('(') + Lazy(bexp) + keyword(')') ^ process_group

def bexp_term():
return bexp_not()   | \
bexp_relop() | \
bexp_group()
```

We define `bexp_group` and `bexp_term` pretty much the same way we did for the arithmetic equivalents. Nothing new here.

Next, we need to define expressions which include the `and` and `or` operators. These operators actually work the same way arithmetic operators do; both are evaluated left to right, and `and` has higher precedence.

```bexp_precedence_levels = [
['and'],
['or'],
]

def process_logic(op):
if op == 'and':
return lambda l, r: AndBexp(l, r)
elif op == 'or':
return lambda l, r: OrBexp(l, r)
else:
raise RuntimeError('unknown logic operator: ' + op)

def bexp():
return precedence(bexp_term(),
bexp_precedence_levels,
process_logic)
```

Just like `process_binop``process_logic` is intended to be used with the `Exp` combinator. It takes an operator and returns a function which combines two sub-expressions into an expression using that operator. We pass this along to `precedence`, just like we did with `aexp`. Writing generic code pays off here, since we don’t have to repeat the complicated expression processing code.

## Parsing statements

With `aexp` and `bexp` finished, we can start parsing IMP statements. We’ll start with the humble assignment statement.

```def assign_stmt():
def process(parsed):
((name, _), exp) = parsed
return AssignStatement(name, exp)
return id + keyword(':=') + aexp() ^ process
```

Nothing particularly interesting for this one. Next, we’ll look at `stmt_list`. This will parse a series of statements separated by semicolons.

```def stmt_list():
separator = keyword(';') ^ (lambda x: lambda l, r: CompoundStatement(l, r))
return Exp(stmt(), separator)
```

Remember, we need to use the `Exp` combinator here instead of doing something simple like `stmt() + keyword(';') + stmt()` to avoid left recursion.

Next up is the `if`-statement:

```def if_stmt():
def process(parsed):
(((((_, condition), _), true_stmt), false_parsed), _) = parsed
if false_parsed:
(_, false_stmt) = false_parsed
else:
false_stmt = None
return IfStatement(condition, true_stmt, false_stmt)
return keyword('if') + bexp() + \
keyword('then') + Lazy(stmt_list) + \
Opt(keyword('else') + Lazy(stmt_list)) + \
keyword('end') ^ process
```

The only complexity here is the fact that the `else`-clause is optional. This makes the `process` function a little more complicated.

Finally, we have the `while`-loop:

```def while_stmt():
def process(parsed):
((((_, condition), _), body), _) = parsed
return WhileStatement(condition, body)
return keyword('while') + bexp() + \
keyword('do') + Lazy(stmt_list) + \
keyword('end') ^ process
```

We’ll wrap it all up with `stmt`:

```def stmt():
return assign_stmt() | \
if_stmt()     | \
while_stmt()
```

You’ll notice that both the `if` and `while` statements use `stmt_list` for their bodies rather than `stmt``stmt_list` is actually our top level definition. We can’t have `stmt` depend directly on `stmt_list`, since this would result in a left recursive parser. And since we want `if` and `while` statements to be able to have compound statements for their bodies, we use `stmt_list` directly.

## Putting it all together

We now have a parser for every part of the language. We just need to make a couple top level definitions:

```def parser():
return Phrase(stmt_list())
```

`parser` will parse an entire program. A program is just a list of statements, but the `Phrase` combinator ensures that we use every token in the file, rather than ending prematurely if there is are garbage tokens at the end.

```def imp_parse(tokens):
ast = parser()(tokens, 0)
return ast
```

`imp_parse` is the function that clients will call to parse a program. It takes the full list of tokens, calls `parser`, starting with the first token, and returns the resulting AST.

To test out our parsers (in addition to unit tests), here’s a simple driver program:

```import sys
from imp_parser import *

if __name__ == '__main__':
if len(sys.argv) != 3:
sys.stderr.write('usage: %s filename parsername' % sys.argv[0])
sys.exit(1)
filename = sys.argv[1]
file = open(filename)
file.close()
tokens = imp_lex(characters)
parser = globals()[sys.argv[2]]()
result = parser(tokens, 0)
print result
```

This program will read a file (first argument) and parse it with one of the parsers in imp_parse.py (second argument). For example:

```\$ echo '1 + 2 * 3' >foo.imp
\$ python imp_parser_driver.py foo.imp aexp
Result(BinopAexp(+, IntAexp(1), BinopAexp(*, IntAexp(2), IntAexp(3))), 5)
```

This should provide a good sandbox for experimentation.

Let’s think about how a program is evaluated normally. At any given time, there is some “point of control,” which indicates what statement the program is going to evaluate next. When the next statement is evaluated, it modifies the state of the program, both by advancing the “point of control” and by changing the values of variables.

To evaluate an IMP program, we need three things.

1. Point of control – we need to know the next statement or expression to evaluate.
2. Environment – we need a way to model the “state of the program.”
3. Evaluation functions – we need to know how the state and point of control should be modified for each statement or expression.

Point of control is the easiest, at least for IMP. We have arranged our intermediate representation in a tree-like structure. We’ll just call the evaluation function for the top-level statement, which will recursively call evaluation functions for statements and expressions inside it. We will essentially be using Python’s point of control as our own point of control. This wouldn’t be as easy for languages with more complicated control structures like functions or exceptions, but we can keep it simple for IMP.

The environment is also easy. IMP only has global variables, so we can model the environment with a simple Python dictionary. Whenever an assignment is made, we will update the variable’s value in the dictionary.

Evaluation functions are really the only thing we need to think about. Each kind of expression will have an evaluation function which will take the current environment and return a value. Arithmetic expressions will return integers, and Boolean expressions will return true or false. Expressions have no side effects, so the environment will not be modified. Each kind of statement will also have an evaluation function. Statements act by modifying the environment so no result will be returned.

## Defining evaluation functions

We will define the evaluation functions as methods on our AST classes. This gives each function direct access to the structure it is evaluating. Here are the functions for arithmetic expressions:

```class IntAexp(Aexp):
...
def eval(self, env):
return self.i

class VarAexp(Aexp):
...
def eval(self, env):
if self.name in env:
return env[self.name]
else:
return 0

class BinopAexp(Aexp):
...
def eval(self, env):
left_value = self.left.eval(env)
right_value = self.right.eval(env)
if self.op == '+':
value = left_value + right_value
elif self.op == '-':
value = left_value - right_value
elif self.op == '*':
value = left_value * right_value
elif self.op == '/':
value = left_value / right_value
else:
raise RuntimeError('unknown operator: ' + self.op)
return value
```

You’ll notice we have some extra logic for the case where the programmer uses a variable that hasn’t been defined yet (one that isn’t in the environment dictionary). To keep things simple and to avoid writing an error handling system, we give all undefined variables a 0 value.

In `BinopAexp` we handle the “unknown operator” case by raising a `RuntimeError`. The parser cannot create an AST with unknown operators, so we don’t have to worry about this in practice. However, if someone constructs their own AST without the parser, all bets are off.

Here are the functions for Boolean expressions:

```class RelopBexp(Bexp):
...
def eval(self, env):
left_value = self.left.eval(env)
right_value = self.right.eval(env)
if self.op == '<':
value = left_value < right_value
elif self.op == '<=':
value = left_value <= right_value
elif self.op == '>':
value = left_value > right_value
elif self.op == '>=':
value = left_value >= right_value
elif self.op == '=':
value = left_value == right_value
elif self.op == '!=':
value = left_value != right_value
else:
raise RuntimeError('unknown operator: ' + self.op)
return value

class AndBexp(Bexp):
...
def eval(self, env):
left_value = self.left.eval(env)
right_value = self.right.eval(env)
return left_value and right_value

class OrBexp(Bexp):
...
def eval(self, env):
left_value = self.left.eval(env)
right_value = self.right.eval(env)
return left_value or right_value

class NotBexp(Bexp):
...
def eval(self, env):
value = self.exp.eval(env)
return not value
```

These are pretty straightforward. They just use the built-in Python relational and logic operators.

Here are the evaluation functions for each kind of statement:

``` class AssignStatement(Statement):
...
def eval(self, env):
value = self.aexp.eval(env)
env[self.name] = value

class CompoundStatement(Statement):
...
def eval(self, env):
self.first.eval(env)
self.second.eval(env)

class IfStatement(Statement):
...
def eval(self, env):
condition_value = self.condition.eval(env)
if condition_value:
self.true_stmt.eval(env)
else:
if self.false_stmt:
self.false_stmt.eval(env)

class WhileStatement(Statement):
...
def eval(self, env):
condition_value = self.condition.eval(env)
while condition_value:
self.body.eval(env)
condition_value = self.condition.eval(env)
```

For `AssignStatement`, we just evaluate the arithmetic expression on the right side, and update the environment with the resulting value. The programmer is free to redefine variables that have already been assigned.

In `CompoundStatement`, we just evaluate each statement, one after the other. Keep in mind that a `CompoundStatement` is allowed anywhere a statement is allowed, so long chains of statements are encoded as nested compound statements.

In `IfStatement`, we first evaluate the Boolean expression condition. If it’s true, we evaluate the true statement. If it’s false and a false statement was provided, we evaluate the false statement.

In `WhileStatement` we evaluate the condition at the beginning to check whether the loop body should even be executed once. The condition is evaluated after each iteration of the loop to check if it’s still true.

## Putting it all together

We have now built every major component of our interpreter. We just need a driver program to integrate them:

```#!/usr/bin/env python

import sys
from imp_parser import *
from imp_lexer import *

def usage():
sys.stderr.write('Usage: imp filename\\n')
sys.exit(1)

if __name__ == '__main__':
if len(sys.argv) != 2:
usage()
filename = sys.argv[1]
tokens = imp_lex(text)
parse_result = imp_parse(tokens)
if not parse_result:
sys.stderr.write('Parse error!\\n')
sys.exit(1)
ast = parse_result.value
env = {}
ast.eval(env)

sys.stdout.write('Final variable values:\\n')
for name in env:
sys.stdout.write('%s: %s\\n' % (name, env[name]))
```

The program expects exactly one argument: the name of the file to interpret. It reads in the file and passes it through the lexer and parser, reporting an error if it finds one. We extract the AST from the parse result and evaluate it using an empty dictionary as the starting environment. Since IMP has no way to output any values to the terminal, we just print everything in the environment after the program is finished so we know that something actually happened.

Here is the canonical factorial example:

```n := 5;
p := 1;
while n > 0 do
p := p * n;
n := n - 1
end
```

We evaluate this as follows:

```\$ ./imp.py hello.imp
Final variable values:
p: 120
n: 0
```

## Conclusion

[In the last four articles,] we built an interpreter for a simple language from scratch. While the language itself is not very useful, the interpreter is extensible, and its major components (the lexer and parser combinator libraries) are reusable.

I hope this provides a good starting point for people to start experimenting with language design. Here are some ideas for exercises:

• Make variables local to the scope they are defined in (for instance, a variable defined in a loop should not be valid outside of the loop).