CSC121, Data Structures and Algorithms
Project #1 -- Operator Precedence Parser

Due Date:  	Wednesday, March 21, at the beginning of class
             You will lose 10% for each 24-hour period this is turned in late.
		 For 5 points of extra credit on this project, turn it in by Friday, March 9 at 5pm.
	
What to Turn In:  You will turn in a printout of all of your code.  In addition, we will run your completed project from your account (see class handout for details on how to set this up).

Acceptable Collaboration:  You are allowed to discuss this project with your classmates, but everyone should complete the project individually.

Motivation:  Parsers play a vital part in the construction of compilers.  While you are not ready to implement an entire compiler, it is important to know various ways to implement operations we take for granted.  This project will give you a better understanding of everything that must go on behind the scenes in order for you to add a string of numbers.

Administrative Details:   The story goes… There were two neighbors.  Each had a large tree in his front yard that he wanted to cut down.  Both trees (and both neighbors, if it matters) were about the same size.  They decided to make a day out of it, and got up really early to start chopping.  Every hour, one of the neighbors took a short break, went around to the back of his house, and then came back after about 10 minutes.  The first few hours went really well -- there was much laughing and joking.  As the day wore on, the workers wore down.  At the end of the day, one neighbor's tree toppled.  He stood up, brushed off his pants, and turned to go home.  The other neighbor called out to him, "I have to ask… I worked here nonstop all day long and you took a 10 minute break every hour.  Yet you still finished before me.  How is that possible?"  As the first neighbor went inside he said, "Every time I took a break, I was sharpening my axe."  

The moral of the story:  If you procrastinate, you will have to chop down a tree.    

Seriously, it is essential that you start this project early and pace yourselves as it is likely that other small homework assignments will be assigned before this is due. I will not be very helpful if you come to me in the last few days before the project is due and it is clear that you have not been working on the project all along.
 
Overview:  You are to implement an operator precedence parser for arithmetic expressions generated by the following grammar:	E --> E+E | E*E | E-E | E/E | E^E | (E) | i 
where "i" is a non-negative integer consisting of one or more digit.

A sample run might look like:		Welcome to SuperSpecialCalc:
>2
2
>22+4
26
>6  +  *  18
Error in expression
>((3))*(10-14)
-12
>{return pressed here}
Program terminating.

The legal inputs to your program are precisely the ones generated by the above grammar; as with any programming language there will also be an implicit limit on the magnitude of the integers you can handle.  This is due to the constraints of the machine; it is nothing that you need to worry about explicitly.  Note that although it is possible for your program to generate a negative output (for example by typing: (5 - 9), it is not possible for the user to explicitly enter a negative value as input.  In other words the user cannot enter something like:  (-5 + 9)  Also, it is acceptable for your output to be an integer, although you can convert things to float if necessary.

Initially your program can make use of an array-based stack object which I will supply (see notes below under "resources").  Once your program is working with my stack, you will implement your own (pointer-based) stack object and replace my stack with it.  Thus the final project you turn in should work with both my array-based stack AND your pointer-based stack.

Resources:
(1) Be sure you fully understand the operator precedence parsing handout presented in class.  Your primary task is to implement the algorithm found on this handout, and the handout will be a great resource.

(2) The program parse.cpp will be a useful starting point for the project.  A copy of it along with token.h, line.h and pstack.h are ~vanbusum/public.  Use cp to copy these files to your own directory.

(3) The file pstack.h contains an implementation of an array-based parse stack; you may or may not need to use all of the routines defined as part of that class.

(4) If you #include <math.h> you can compute powers using the C++ pow() function.  For the statement z = pow(x, y); raises x to the power y and assigns the result to z.

Specific steps to follow:

(1) You will need to declare integer constants for LT, GT, EQ, ER at the top of the parse.cpp program before you begin.  It does not matter what values you assign these constants as long as they are distinct from each other.

(2) Implement the function parse so that it carries out the operator precedence parsing algorithm using shift-reduce parsing as mentioned in class.  You will probably want to have parse() call other routines as well.  For example you will almost certainly want the following functions:

int prec (char row, char col)

void pop_right_hand_side(tokenarr arr, int &num_in_array, pstackclass &thestack)

int is_valid_rhs(tokenarr arr, int num_in_array)

void compute_and_push(tokenarr arr, pstackclass &thestack)

Note that you can initially write a "dummy" is_valid_rhs() function which ignores its parameters and returns true (1) all the time.  If you do this you will be able to test your program as long as you only enter valid inputs.

(3) Test the parser systematically.  First try single integer expressions like:  2   then advance to expressions with one operation like 2+2 then try parens (2)  then parens and operations 2 * (3 + 3) etc.  If the parser is not working you will have to print (or use the debugger to view) the contents of your variables at each step of the algorithm.  The s.dump() routine will also be useful in debugging and it is strongly suggested that while debugging you dump the contents of the stack and print the current token every time you come to the top of the loop (and maybe at other points as well.)

(4) Once the parser has been thoroughly tested create a new file called mypstack.h.  This file should contain definitions of a pointer-based version of a pstack object.  Each of the routines which I implemented in pstack.h should be reimplemented in mypstack.h using pointers.  Change the include statement in your main program from #include "pstack.h" to #include "mypstack.h".  Then test your program with the stack definitions.

Important Warning:

For technical reasons which will become clear when we talk about "copy constructors" and "destructors" it is very important that you do not pass objects of type  stack class as a value parameter at any point.  Whenever you pass a stack as a parameter you should be sure it is a reference parameter. 

Extra Credit:  

For 10 points of extra credit on this project, extend the grammar and modify your code so that it accepts any string specified by your new grammar.  Make sure you specify the grammar your parser accepts in comments at the top of your program.

Comments/Style:

All programs in this course will be graded on style as well as correctness.  I expect neatly formatted, modular, well-commented programs.  State clear (and correct!) pre- and post- conditions for all functions, and include a brief description of the program near the top.  Also include a comment with your name, the date the project is due, the filename it is saved as, your login, and the pledge.

	Tips:
•	Do NOT do anything too fancy with pointers, including traversing arrays.  It is too difficult to read and is in poor style.  You will be penalized if you do this.
•	Please try to print out a copy of your final project that does not have comments wrapping around to the next line.   

Grading:
	This project will be worth 140 pts:
	10 points for precedence relation table
	45 points for correctness of operator precedence parsing algorithm
	45 points for correctness of list-based stack
	40 points for style, modularity, comments, etc. 
	
	You can also get up to 15 points of extra credit on this project.