Exercise 36: Simple Calculator

This challenge is to create a simple algebraic calculator using everything you've learned about parsing. You'll need to devise a language for doing basic math with variables, create an ABNF for the language, and write the Scanner, Parser, Analyzer, and Interpreter for it. This may actually be overkill for a simple calculator language since there won't be any nested structures like functions, but do it anyway to understand the full process.

Exercise Challenge

A simple algebraic language can mean many things to different people, so I want you to play with the Unix command bc. Here's an example of me running the bc command:

$ bc
bc 1.06
Copyright 1991-1994, 1997, 1998, 2000 Free Software Foundation, Inc.
This is free software with ABSOLUTELY NO WARRANTY.
For details type `warranty'.
x = 10
y = 11
j = x * y
j
110

You'll want to be able to create variables, enter numbers (both integers and floating point), and have as many operators as you can devise. You can most likely play with bc, or even Python's shell, and work out the ABNF for it as you go. Remember that your ABNF is almost pseudo-code and doesn't have to be formally correct, just close enough for you to create your Scanner and Parser.

Once you have a "sketch" of the grammar in ABNF form, you can sit down to create the Scanner and Parser. I would write a set of simple scripts that exercise what you think the language should do and then have your test suite run them through your calculator at each stage. Doing that makes it easier to test the calculator.

After you have the Parser you should write an Analyzer to solidify and check the input for semantic meaning. In a simple language like this it may be more than you need, but this is an exercise in completing the entire process with a small little toy language. Remember that a big job for the Analyzer is to keep track of variable definitions at different points in the script so they can be accessed by the Interpreter during execution.

After you have your Analyzer creating an executable parse tree you can then write an Interpreter that runs it. As mentioned in Exercise 35 there's two ways you can write an Interpreter. One has you creating a "machine" that knows how to run the grammar productions as a sequence of inputs. This treats your grammar production classes (Expression, Assignment, etc.) as if they are machine code and simply does what they contain. The other style for an OOP language like Python is to have each production class know how to run itself. In this style the classes are "smart" and, given their environment, simply do what they need to make things happen. You then just "walk" the list of grammar productions calling run until you run out of them.

Which one you choose determines where you have to store the state for your little interpreter. If you make an Interpreter class that simply executes production data objects, then the Interpreter can keep track of all the state and be the computer, but the language is harder to extend since you have to improve the Interpreter for every production class. If you have the production classes know how to execute their own code, then it's easy to extend the language, but you have to find a way to pass the state of the computer around between each production.

When working on this, I suggest you start with only a tiny expression, such as addition. Get that to work first for the whole system, from Scanner all the way to running simple addition. Then, if you don't like this design you can throw it out and do it again with a different design. Once you have your design working, you can then extend the language with more features.