Project 3 - Calculator Language Interpreter

Objectives

  • Build a fully functional calculator language interpreter.

Starter Files

Download proj3.zip. Inside the archive, you will find the pair.py library and test files for this project.

Introduction

In this project you will build an interactive interpreter for the Calculator language that we have discussed in class.

The interpreter will allow the user to enter valid Calculator expressions, in which case it will return the value of the expression, or the word exit in order to end the interactive session. If an invalid expression is entered, it will print an error and then prompt for another expression.

Valid Calculator expressions are of the form:

(<operator> <operand 1> <operand 2> [...])

where the operator is one of the valid operator symbols (+, -, *, and /) and the operands are the values to be operated on. All operators require at least two operands but can accept more.

When more than two operands are provided for a given operator, the operation is applied between the first and second operand, then it is applied to the result of the previous operation and the next operand, and so on until all the operands are used. For example, the expression (+ 3 4 5 6) evaluates to $((3+4)+5)+6 = 18$ while the expression (/ 20 4 5) evaluates to $(20/4)/5 = 1$.

You will be writing nearly all of the interpreter from scratch but we will walk you through the process in this project. For grading purposes, you will need to implement the function names exactly as specified with the specified argument list. The names you give to the arguments are up to you but they should make sense.

Part 1 - The Interactive Loop

We'll start by setting up the interactive part of the interpreter that prompts the user for input and displays the results. We'll then add in the code to parse the input and evaluate it in later parts of the project. Let's get started.

Task 1 - Getting Started

Start by copying your calculator.py file from Homework 6. If you haven't done it yet, add in our if __name__ == "__main__" statement to allow it to run as a program. Again, you can create a main() function or just write the main part of the program below that if statement.

Add code to your program that will print the following greeting:

Welcome to the CS 111 Calculator Interpreter.

followed by a newline.

Add a comment for yourself that the main loop should follow that greeting. We'll come back and fill in that main loop in the next task.

Add code that prints the following farewell message:

Goodbye!

If you run your program now, it should just print the greeting followed by the farewell.

Task 2 - The Main Loop

For this task, only implement steps 1, 2, 3, 7, & 8. For now, in step 7, you should just print out the string containing the expression the user supplied. That will change as you implement more of the interpreter.

The main loop of your program should do the following:

  1. Print a prompt. The cursor should remain on the line with the prompt after printing. For this project your prompt should be calc >> . The autograder will be looking for this prompt in the output so be sure you get it exactly correct with the space between the word 'calc' and the greater than symbols and a space after the greater than symbols.
  2. Read input from the user. The program should read the entire line as a single string to be parsed.
  3. If the supplied string is the word exit, the program should stop.
  4. Parse the supplied string and validate that it is a valid expression.
  5. If not, print an error and return to step 1.
  6. Evaluate the valid expression to get the result
  7. Print the result
  8. Return to step 1

Try running the program now. It should print the greeting and give you the calc >> prompt and print out anything you type until you type exit at which point the program should print the farewell and end.

Now that the interactive loop is done, it's time to actually start processing the input.

Part 2 - Parsing the Input

In this part of the project, you will write code that will parse the input from the user, validate that it is correct, and build a syntax tree that we can evaluate to get the value of the provided expression. If there are problems we will report the error to the user via exceptions. These are steps 4 & 5 from the main loop. You've already written most of the code for steps 4 and 5 as your work in Lab 16 and Homework 6.

Task 1 - Getting the Token List

This task generates the token list from the user supplied expression. All you need to do is add code to your main loop to call your tokenize() function you wrote in Lab 16. Modify your print code (step 7) to print the token list instead of the user supplied string.

Task 2 - Creating the Expression Tree

You wrote most of the code for this task as your parse_tokens() recursive function in Homework 6; however, that function takes as input both the token list and a starting index, and it also returns both the expression tree and the next index to process. The code calling that function is always going to pass in 0 as the starting index and has to worry about catching the final index value that comes out; however, that index is really an implementation detail that other programmers should not have to consider when calling parse_tokens().

To hide that detail, you are going to write a parse() function that hides the implementation. Your parse function will simply take the token list as input and return the final expression tree (a Pair object).

def parse(tokens):

You could write this as a separate function that calls your parse_token() function.

def parse_token(tokens, index):
    # parse_token code here

def parse(tokens):
    # code that uses parse_token()

Or you could make parse_token() an inner function that is defined inside the parse() function.

def parse(tokens):
    def parse_tokens(tokens, index):
        # parse_token code here	

    # code that calls parse_token()

whichever you choose is up to you.

With the parse() function written, we can call it in our main loop. Add code to your main loop to pass the token list created by tokenize() and capture the Pair object that is the root of our expression tree that comes out.

Since parse(), by way of the recursive function you wrote, can throw exceptions, you need to make the call in a try/except block. Modify step 7 so that if an exception is thrown, the program prints out the error. If not, the program should print out the Pair object returned. Pair has a __str__() function so you can just have your loop print that object instead of the token list string.

Try some simple examples and make sure it's working.

Part 3 - Evaluating the Syntax Tree

It's now time to do the final steps (6 & 7) from the main loop, evaluating the expression and printing the results.

There are three parts to this process and we'll tackle them in turn.

Task 1 - The reduce() Function

Since the operators can have any number of operands instead of just two, we need a function that will apply the operator to any number of operands.

Create a reduce() function, that takes as input a function to apply, a Pair object that is the start of a list of arguments to apply the function to, and an initial value to start with.

def reduce(func, operands, initial):

The passed in function should take two arguments and return a single value as a result. The function we will be passing in are the math functions add, sub, mul, and truediv. Import each of these functions from the operator library. (This library comes preinstalled with Python.)

The reduce() function should traverse the pair list, applying the function to all the values in the pair list starting with the initial value. For the first value in the operands list, call the function with the initial value and the list value and capture the return value. For all later list elements, apply the function to the current list element and the result from the previous step. Once all elements have been processed, return the final result.

from operator import add, sub, mul, truediv
operands = Pair(3, Pair(4, Pair(5, nil)))

the function call

reduce(add, operands, 0)

would return 12. It would call add(0, 3) and get 3, then call add(3, 4) and get 7 and finally call add(7, 5) and get 12.

Task 2 - Applying the Operators

Next up is our apply() function that does the correct operation based on the operator in the expression. Since the calculator language only has four operators, this is a fairly straightforward function. You can imagine that if you had a more complex language, this function have a lot of different parts.

The apply() method takes two arguments: a string containing the operator and a Pair object that is a list of the operands to apply the operator on.

def apply(operator, operands):

For each operator (+, -, *, and /), you should call your reduce() function with the appropriate arguments. For addition and multiplication, the values are all added or multiplied together, so you can just pass the entire Pair object to the reduce() function directly along with the appropriate initial value. For division and subtraction, the initial value should be the first operand of the Pair list, and the list passed to reduce() should begin with the second operand.

If the operator passed in is not one of the allowed operators, the function should raise and TypeError indicating that the operator is invalid.

Task 3 - Evaluating the Syntax Tree.

Now that we can process the operators, it's time to tackle the full evaluations. This will be done in our eval() function that takes as its argument an expression represented by a Pair object that is the root of the syntax tree. Since our syntax tree is a recursive structure, this will be a recursive function as well.

def eval(syntax_tree):

The algorithm for evaluation is actually simpler than the one for parsing. Here is what the function needs to do:

  1. If the expression is a primitive (int or float), we just return the value

  2. If the expression is a Pair object it is some sort of expression

    1. If the first item in the Pair is a Pair itself, we have a subexpression
      1. We need to call eval() on the first item in the Pair
      2. We also need to evaluate all the items in the rest of tree that is defined by Pair. This will evaluate all the sub-expressions and replace them with their values. We can do this using the map() method that is part of the Pair class. Since the rest item in the Pair is a Pair object, we can just call .rest.map() and pass the eval function to it.
      3. Return a Pair object where first is the results of step 2.1.1 and rest is the results of 2.1.2
    2. If the first item in the Pair is an operator
      1. Apply eval() to the rest of the pair (using map() just like in 2.1.2) to get a Pair list with the operands as the values.
      2. Call our apply() function passing in the operator and the results of step 2.2.1. Return the results of apply().

  3. If the expression is not a primitive or a Pair, raise a TypeError exception.

Just like with the parsing algorithm, you should probably work through some simple examples by hand to make sure you understand what is happening. You should also write some doctests or pytests to verify that things are working properly.

Task 4 - Printing the Results

Now that we can evaluate the syntax tree, it's time to add that into our main loop. Add code that takes the results of the parse() method and calls your eval() method. Again, this can throw exceptions so it should be inside the try/except block that you added earlier. If no exceptions are raised, your loop should print the value returned by evaluating the expression. If there was an exception, it should print the exception message.

And that's it. You've written a complete interpreter for the Calculator language.

Turn in your work

You'll submit your calculator.py file on Canvas via Gradescope where it will be checked via the auto grader. We'll run a series of tests that test the parse(), reduce(), apply(), and eval() functions so make sure that they have the correct names and arguments. We'll also run your full program and pass it input to verify that all is working.

Going Further

Now that you have a basic interpreter, you can add additional functionality. You might consider adding any of the following operators to your interpreter:

  • // - integer division
  • % - the modulus operator
  • sqrt - the square root operator
  • pow - the exponent operator
  • any other math operation you like to use

You might also consider how you could accept command line arguments to allow the program to:

  • evaluate a single expression entered on the command line.
  • accept a filename that it opens, reads, and evaluates the expressions contained therein, either a single expression or one per line in the file.
  • when reading a file, you could output the results to the screen or also take an output filename as another command line argument and write the results to that file.

© 2023 Brigham Young University, All Rights Reserved