COMP2100/2500/6442
Lab 2: Expression Parser and Evaluator
and design for Handling Colour in Gaga
Summary
You will do some implementation and testing work to modify a program that uses a recursive data
structure: an expression parser and evaluator. This uses
Expression Version 3 from the second of the Recursive Data Structures lectures;
and then explore how to handle colours in Gaga, the SVG assistant program that is the subject of the assignments.
Aims
To give you practical experience with simple program code to build and traverse recursive data structures by recursive methods and by a Visitor.
To give you some direct familiarity with the architecture and code of the assignment project.
Preparation
Read through your lecture notes from Lecture 7, Lecture 8 and Lecture 9 on Recursive Data
Structures.
Read the specification of assignment 1, Task 3 Detect and handle colours.
PART 1 Simple expresssion trees and implementing a Visitor
Exercise 1.1. Getting started
Download and unpack the Jar file ExpressionParser.jar.
This program deals with simple integer expressions reasd from input. It reads simple arithmentic expressions over integer constants, that are written in ordinary algebraic notation, and stores them in a tree structure. It can then print them out and evaluate them. Its implementation uses the same code as Expression Version 3 from Lectures.
We will use the expressions (1 + 2) * 3 and 1 + (2 * 3) as examples. These expressions are represented as:
* +
/ \ / \
+ 3 1 *
/ \ / \
1 2 2 3
The program will only accept expressions which satisfy a very simple grammar. The rules are:
In other words, an expression consists either of a single term, or two terms separated by one of the four binary operators; a term consists either of an expression in parentheses, or a constant; and a constant consists of a string of one or more digits. The only characters allowed are digits, the four operators, and parentheses. Spaces are also allowed, but are ignored. Parentheses are compulsory around every sub-expression, even when the normal rules of arithmetic say you don't need them.
Track these expressions through the grammar to the tree structure
Before you run the program, take a minute to follow the two
example expressions through the grammar above, and see how they
give rise to the tree structures pictured.
Take a few minutes to read through the code.
The classes
representing expressions should be familiar to you from the
lectures, but the rest of the program is new. The Lexer
breaks expression strings into tokens, meaningful items
of data like parentheses, arithmetic operators and numbers.
The Parser uses the grammar above to turn that stream
of tokens into a tree.
Now compile and run the program (any version of Java 1.4 or later).
The root class is Calculator.
Try entering one of the example expressions above, and see what
the other commands do. Remember to read the instructions
carefully. You have to enter a new expression with the
‘n’ command before you can do anything
interesting.
Comment
You will discover that the program doesn't yet do what it is
supposed to. In fact, the evaluation feature, subtraction and
division operations, and the pre- and post-order printing
operations have not yet been implemented.
Task 1.2: implement 'v' command: evaluate
Your first task is to implement the
‘v’ command which evaluates the current
expression.
Where should the code be placed? Look at the code
and work it out. (Try to do this without looking back at your
lecture notes.)
The default result for v is 0 (zero). When you run the program on the two example expressions, the output should look like this:
> n (1+2)*3 > n 1+(2*3)
> i > i
In-order : ((1 + 2) * 3) In-order : (1 + (2 * 3))
> v > v
Value = 9 Value = 7
Having done that, add subtraction and division expressions to the system. This will mean adding two new sub-classes of class Expression and also making some minor modifications to some of the other classes, like Parser. When you implement class Division you will need to think about what to do if the user tries to divide by zero.
PART 2 WORK IN TEAMS OF 3
Collaborate with the people around you to form a team of 3 people to work on the next 2 tasks. It does not matter who does the typing but you should all contribute ideas. The idea is to work quickly and share your understanding to learn quicklky from each other.
Exercise 2.1. Post-order printing
Add a new feature which enable the calculator to print expressions in post-order, as well as the standard ‘in-order’ or ‘infix’ form.
In post-order, or reverse Polish notation, you print the two sub-expressions, then the operator. (This is also the input notation for the stack-based calculator.) There is no need for brackets, because there is no ambiguity about what constitutes the sub-expressions.
Here are our two example expressions printed in all three orders:
In-order: (1 + 2) * 3 In-order: 1 + (2 * 3)
Post-order: 1 2 + 3 * Post-order: 1 2 3 * +
Exercise 2.2. The Visitor pattern
Refactor your code using the design of Expression Version 4, with the Visitor pattern. You will hardly need to add any new code; it's more a matter of reorganising the existing code.
This exercise is particularly important, because this is the same style of implementation as is used in the project software that you will be working on in the assignments.
PART 3 Handling Colours in Gaga
This is a paper design exercise only, not a full programming exercise.The idea is for your team of 3 to explore and share ideas about how to implement the colour functionality for Gaga, as required for assignment 1. By doing a paper design you can discover where the difficulties are likely to arise, and can estimate how much effort you will need for this part of the assignment.
You may want to divide up these research questions among the team and then share answers to make sensible conclusions.
Ideas and questions:
first some research
- what are defects in the distribution version of gaga? (look at the bug tracker forum, look at the code, run the code over some simple examples with various kinds of colours)
- what is the correct meaning of colour #579? (look in the SVG standard) (test: compare a simple svg file with this colour viewed in gaga and in a web browser)
- what are the 16 colours with names in HTML 3.2? what are the 147 names in full SVG? (look in the SVG standard, search on the web)
- is there anything in the Java API library to help solve these problems?
- is "none" equivalent to a colour that can be set in Java2D graphic context, or does it have to be handled separately?
some questions about designing the code
- the keys to the solution:
- how would you design program code to handle just 16 named colours? how would you handle all 147 colours? how would you do this efficiently?
- how can you handle the 3 digit colours?
- the program design
- where should the exsiting program code be changed and extended, for good design?
estimation
Now you have an idea about the concepts in the solution, estimate how many lines of code and how long it will take to develop according to your PSP experience.Some teams will be asked to report to the class on their design and estimates, better have a coherent story ready.
PART 4 Extension work
Starred exercises are extension work. You do not have to complete them. They may be significantly more difficult than the other exercises. You will learn more about the topics if you put private study time into these optional extensions.
*Exercise 3.1 The Stack Calculator
Work through the stack-based calculator exercises.
*Exercise 3.2. Order of operations
We shouldn't really have to put parentheses in an expression like 1+(2*3), since the rules of arithmetic say that the multiplication should be done first anyway. Rewrite the grammar for our parser so that the precedence is built in, and parentheses are only needed where mathematics says they're needed. Now rewrite the parser to reflect this change. While you're at it, you might want to think about allowing negation as well.
Hint: You will need a new syntactic element. The usual name for this is a Factor. Roughly, an Expression is a sum or difference of Terms; a Term is a product or quotient of Factors, and a Factor is either a Constant or an Expression in parentheses.
