Computer Science 210
Data Structures

Fall 2017, Siena College

Home     Syllabus     Schedule     Examples     Style Guide

This programming assignment is described in Section 10.5 of Bailey. You will learn about the PostScript language, and gain experience using stacks and making use of an existing partial implementation.

You may work alone or in a group of two or three on this project. Of course, collaboration with your partner(s) is unrestricted. You may discuss the assignment with your classmates and give and receive some help, but your submission must be your own work (or that of you and your teammates, if you choose to form a group).

This will be graded as a programming assignment, so be sure to refresh your memory about the submission guidelines.

Getting Set Up

You will receive an email with the link to follow to set up your GitHub repository ps-project-yourgitname for this Programming Project. One member of the group should follow the link to set up the repository on GitHub, then that person should email the instructor with the other group members' GitHub usernames so they can be granted access. This will allow all members of the group to clone the repository and commit and push changes to the origin on GitHub.

Please answer lab questions in the README.md file in your group's GitHub repository.

Before we meet for lab on Wednesday, each group should create and clone the starter repository. Familiarize yourself with the three given classes and make sure you understand how they work, especially how you would use them. Also, carefully read the lab description in the text and on this page. You are certain to have questions, but hopefully you will think enough about this project before this week's lab, so that many of those questions can be addressed during our lab meeting.

A PostScript Interpreter

Your task is to develop the Interpreter class. Start by developing a sketch of this class. Interpreter is where you will process the tokens being delivered to your interpreter by the provided Iterator class. You are strongly encouraged to discuss your sketch of this class with your instructor during lab or by email for comment and discussion before you begin significant implementation.

Notes and Guidelines

In addition to everything in the Bailey lab description, keep the following in mind while completing your program.

• Please name the file with your interpreter and main method Interpreter.java.
• Make use of the functionality of the classes you are given to start. Be careful not to spend time developing code that replicates functionality that is already there!
• Make your main method very short. All it should do is create an Interpreter object and tell it to start parsing the PostScript program presented at the command line. Create a method interpret that takes a single parameter of type java.util.Iterator<Token> (which will be an instance of the provided Reader class, but that detail is not important to your implementation) and processes the PostScript tokens returned by that Iterator<Token>. This will allow you a convenient way to store your stack, symbol table, and other information in instance variables to be shared among all of the methods you write.
• A "debugging mode" for your program may prove useful to facilitate debugging and testing. In my version, if I specify the word "debug" as a command-line parameter, the program enters a debugging mode and prints out informative messages about what it is doing as it processes the PostScript tokens. This is not a requirement for your completed program, but is likely to be very helpful during development.
• Develop your interpret method incrementally. Get the simple opertations like pushing a token encountered on the input, pop, and pstack working, then move on to the arithmetic operators, and finally the definition and usage of symbols.
• Your program should throw exceptions when it encounters invalid input, but these should contain meaningful error messages. You can use Assert.condition() and Assert.fail() for this.

    Assert.fail("some message");
  

  will throw an exception and print that message. You can use it if there's a case in your interpreter that should just never happen. More likely, you'll be using

    Assert.condition(x==7, "x should have been 7");
  

  This says you know x must be 7 or something must have gone wrong. In your code for this project, you would be more likely to do something like:

    Assert.condition(op1.isNumber(), 
       "add requires numeric operands");
  

  or

    Assert.condition(!stack.isEmpty(), 
       "pop requires a value on the stack");
  

  This will allow your program to "crash nicely" with a more meaningful message when presented with invalid PostScript input. The Assert methods are provided by structure5. Java provides similar functionality through the assert keyword.

• Your finished program should produce no output other than the precise required output from the pstack and ptable operations. This would include extraneous information and punctuation produced by a data structure's toString method. The exception is debugging output when executing in a debugging mode.
• For testing, you might want to run your program from the command prompt instead of directly within BlueJ, so you can redirect your input from a .ps file. This would allow you to test without having to type in all of your PostScript tokens over and over in the terminal window. No code changes are needed to make this happen, you just need to run from your operating system's command prompt (Terminal on a Mac, the Command Prompt on Windows) and use input redirection.

Bonus Opportunity

For 5 bonus points, you can implement procedures as described in thought question 3. If you design everything else properly, this should be almost a trivial extension.

For another 5 bonus points, you can implement the if operator as described in thought question 4.

Related Questions

Note: one word or one sentence answers are not sufficient here for full credit. Please be thorough and justify your answers.

Submitting

Your submission requires that all required deliverables are committed and pushed to the master for your repository's origin on GitHub. That's it! If you see everything you intend to submit when you visit your repository's page on GitHub, you're set.

Grading

This assignment is worth 60 points, which are distributed as follows:

The program design grade will be based on the design choices you make in the implementation of the Interpreter class. The program style grade will be based on code formatting and approriate use of Java naming conventions. The program documentation grade is, of course, based on the comments you provide. The program correctness grade is based on how well your program meets the functionality requirements.