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.

Study Drills

1. The best study drill for this is to create functions to perform calculations and return results. If you can do that then your design will probably work for a larger language.
2. The next thing to try is implementing flow control with if-statements and boolean checks. It's quite alright if this is too daunting, but give it a try.

Further Study

Research as much of the bc or Python language as you can. Try to find other grammar files to read and study, especially any IETF protocol descriptions. IETF specifications are about as exciting a read as wet toilet paper, but they are good practice.