CSCI 136 :: Spring 2021

Data Structures & Advanced Programming

Home | Schedule | Labs | Handouts | Links | CS@Williams

Lab 5: P.S. It's Just a Stack!

In this week's lab (described in Section 10.5 of Bailey) we will implement a small portion of the stack-based language Postscript, a language designed to describe graphical images. When you create a Postscript file or print to a PostScript printer, you actually create a file that contains a program written in this language. A printer or viewer interprets that program to render the image described by the file.

Pre-lab Task: Explore the Starter Code

For this lab, we provide you with several useful classes to serve as building blocks for your implementation. These starter files are well documented, but sometimes reading source code can be daunting. To help out, we will use the javadoc program to generate Javdoc-formatted webpages that we can use to get a handle on the ways these classes can fit into our lab program design.

To create Javadoc documentation from the files in your repository, we can use the javadoc program that is included with our Java installation. By default, javadoc will process the Javadoc-formatted comments in a source file and generate a series of webpages and resources in the current directory. We don't want to clutter our repositories, so we will tell Javadoc to place its output inside the javadoc/ folder that we have created. The command we suggest that you use is:

              $ javadoc -d javadoc/ *.java
    

Some notes on this command:

• The -d javadoc option tells the javadoc program to place its output in the javadoc/ directory.
• The *.java argument tells Javadoc to create documentation for every single file in your current directory that ends with the extension .java. The * is what is called a "wildcard character" (in *.java, the * will expand to match anything that it can, given the constraint that the string ends in .java).
• You may get some errors about "unknown tag" for pre and post. that's perfectly fine; you can ignore these errors. The errors are generated because pre and post conditions are not standard javadoc tags.

After you are done, you should see many new files in your javadoc/ directory:

          $ ls javadoc

            Interpreter.html         help-doc.html            package-tree.html
            Reader.html              index-all.html           resources
            SymbolTable.html         index.html               script-dir
            Token.html               member-search-index.js   script.js
            allclasses-index.html    member-search-index.zip  search.js
            allpackages-index.html   overview-tree.html       stylesheet.css
            constant-values.html     package-search-index.js  system-properties.html
            deprecated-list.html     package-search-index.zip type-search-index.js
            element-list             package-summary.html     type-search-index.zip
        

If I want to view my newly created documentation, I would open the file index.html. This is the webpage that forms the "root" of my Javadoc websites. In macOS, I could use the open command:

          $ open javadoc/index.html

This will open the javadoc page for your Interpreter class. To see the javadocs for all four classes, try:

          $ open javadoc/allclasses-index.html

I can also use my browser of choice (e.g., Firefox, Chrome, Safari, Edge, etc.) to open that local file.

Before lab, please do the following:

• Generate Javadoc for the starter files in your repository. You should not commit these files to your repository, but you should have them as a "local resource".
• Read through the javadoc that you generated for the Token, Reader, and SymbolTable classes. These classes will be helpful in your implementation.
• Really! Read through them carefully. Understanding the methods (including constructors) that these classes provide can save you a lot of time on this lab!
• For more implementation details, skim the Token.java, Reader.java, and SymbolTable.java source files (also in your private repository) before coming to lab.
  • Note: Be sure to use named constants, such as Token.NUMBER_KIND, Token.BOOLEAN_KIND, and so on, and not the underlying int values (1,2, etc.).
• Read this handout and think about your lab design. If generating a formal design document is helpful, we strongly encourage you to do so. If you are working with a partner, we suggest that you discuss the lab tasks and starter files together, then independently think about designs. Discussing your independently-generated designs will help you to compare approaches without being influenced early on in the design process, hopefully leading to a richer joint discussion--and better final product!

Lab Assignment

Complete Laboratory Assignment 10.5, which begins on page 247 of Bailey (PDF excerpt here). We have provided additional notes below.

In addition, answer the following Questions from page 246 of your text in PROBLEMS.md, and submit it with the rest of your code this week. Note that we have added additional text in italics below to help clarify the questions.

• Problem 10.3: Suppose you wish to fill a stack with a copy of another, maintaining the order of elements. Using only Stack operations (push and pop), describe how this would be done. How many stacks are necessary (including the source stack and any additional stacks that you use)? Note: the original stack and its contents should be preserved. After completing the steps that you describe, there should be two identical stacks.
• Problem 10.4: Suppose you wish to reverse the order of elements of a stack (when you are done, the "reversed elements" should be located in the original stack). Using only stacks and stack operations (push and pop), describe how this could be done. How many stacks are necessary (including the source stack and any additional stacks that you use)?
• Problem 10.5: Suppose you wish to move the contents of one queue into another, preserving the order of the elements. Using only Queue operations (enqueue and dequeue), describe how this would be done. Also indicate the number of queues needed, including the source queue, the destination queue, and any additional queues that you use.

Helpful Notes

• The starter files can be found online and in your private repository. In addition to starter Java files, we have included several sample postscript programs that will be useful for testing your code. Postscript files end with the .ps file extension.
• Make use of the functionality of the classes you are given. Be careful not to spend time developing code that is already there! Pay careful attention to the different class constructors, and ask questions if you have any.
• Name your interpreter class Interpreter. You should only need to modify the Interpreter class and nothing else.
• Your program should read commands from standard input. You can also redirect input from a file named sample.ps to your Interpreter program by using a command like:

  $ java Interpreter < sample.ps

• Make your main method very short. All it should do is create an Interpreter object and tell it to start parsing the postscript program provided as standard input. Create a method interpret that takes a single parameter of type Reader and processes the PostScript tokens returned by that Reader.
• Develop your interpret(Reader reader) method incrementally. Get your simple push, pop, and pstack operations working, then move on to the arithmetic operators, and finally the definition and usage of symbols. Decompose the program into small, manageable helper methods as you go! You may wish to use a large switch statement, but each "case" should call an appropriate helper.
• Your program should report errors when it encounters invalid input, and these should contain meaningful error messages. Printing appropriate messages is perfectly fine, but you can also use Assert.condition() and Assert.fail() for this (or use the Java assert statement). Think about the different operations that may share preconditions. Can you create helper methods that meaningfully handle multiple operations?
• The basic operation ne (not equal) is the opposite of eq. sub and div are for subtraction and division respectively. The other basic operations are defined in the handout.
• Implementing the basic operations (pstack, add, sub, mul, div, dup, exch, eq, ne, def, pop, quit, and ptable) will allow you to earn 4.5 out of 5 functionality points. You can earn the last functionality points by implementing the extensions outlined in thought questions 3, 4, and 5 from the book. In particular, you should implement procedure definitions and calls, the lt (less than) instruction, and the if instruction. Note that procedure calls only work if a space is left before and after the opening and closing braces. These extensions may require a little thought, but ought to be straight-forward to implement if you have designed your interpreter engine well.
• Experimenting with PostScript If you'd like to see how a real PostScript interpreter evaluates PostScript code, here are a few options.
  • This website lets you enter PostScript (into the Code textbox) and run it. Note: It's a bit fussy, sometimes we needed to reload the page.
  • You can use gs (GhostScript Interpreter) if you have it installed on your system. Type the command:

              $  gs -dNODISPLAY
            

    to get a text-only postscript interpreter (or to learn whether gs is installed on your system. You can type commands at the prompt as they appear in the lab assignment. Type quit to exit the interpreter. If PostScript is not installed, try the website above or search the web for a free GhostScript installation.

checkstyle requirements:

For this lab, we will be not be adding any new checkstyle rules to the set of rules that we have used in previous weeks. Last week we requested that you include Javadoc-style comments for each public method, and this week we are asking you to use the javadoc program to produce real Javadoc webpages. We hope that you generate these webpages using your comments in Interpreter.java, and use the generated files to help you improve your documentation.

We STRONGLY ENCOURAGE you to run checkstyle early and often when developing your code, and try to program in a way that minimizes WARNING messages. The checkstyle rules that we use in this course are based on real-world style guides; internalizing good style practices will help us write more readable code.

In total, checkstyle will enforce the following guidelines:

• All class variables that are not final must be declared private or protected (i.e., no public member variables unless they are constants). (We don't expect this to be an issue this week.)
• All public methods must include a “Javadoc” comment (starts with /** and ends with */; it should include descriptions of the function at the top, descriptions of return values after a @return tag, descriptions of each argument after a @param tag, and pre/post conditions after the @pre or @post tags).
• No methods should be longer than 30 lines (excluding whitespace and single-line comments). However, in this lab, it is relatively natural to process the "built-in" symbols (i.e., pstack, add, sub, mul, div, dup, exch, eq, ne, def, pop, quit, and ptable) using a switch statement. Even a crisply formatted switch statement may exceed the 30-line limit. So it is OK if the method with your symbol-processing logic triggers this particular makestyle error. That being said, we would consider it a style violation if you embed the logic for handling each operation directly inside your switch statement code. Instead, you should create helper methods, and call them from within your switch statement. For example:

      .
      .
      .
      switch (symbolToken.getSymbol()) {
      case "add":
          doAdd();
          break;
      .
      .
      .

  and

      .
      .
      .
      switch (symbolToken.getSymbol()) {
      case "add":
      case "sub":
      case "mul":
      case "div":
          doMathOp(symbolToken);
          break;
      .
      .
      .

  are two examples where the Java code that implements the logic for performing a PostScript operation are handled inside a helper method instead of directly inside the switch statement.

To run checkstyle, you would type the following command at the terminal:

          $ ./checkstyle

The ./ is peculiar to Unix: it tells the terminal to look for the checkstyle program in the current directory. This command will run checkstyle on every Java program in your directory. To run checkstyle on a specific Java file, type:

          $ ./checkstyle SomeFile.java

Lab Deliverables

For this lab, please submit the following:

• Your well-documented source code in Interpreter.java
• A PROBLEMS.md file that contains answers to the three questions described above.
• (the other starter files in your repository should not need to change)

If you worked with a partner, submit your collaborative solution in your shared repository.

As in all labs, you will be graded on design, documentation, style, and correctness. Be sure to document your program with appropriate comments, including class-level and method-level comments (with pre- and post-conditions where appropriate). Also use comments and descriptive variable names to clarify sections of the code which may not be clear to someone trying to understand it. The CS136 Style Guide may be helpful.

Whenever you see yourself duplicating functionality, consider moving that code to a helper method. There are several opportunities in this lab to simplify your code by using helper methods. Think carefully!

Submitting Your Lab

As you complete various milestones, you should commit your changes and push them. Commit early and often. When the deadline arrives, we will retrieve the latest version of your code. If you are confident that you are done, please include "Lab Submission" as the commit message for your final commit. If you later decide that you have more edits to make, it is OK. We will look at the latest commit before the deadline.

• Be sure to push your changes to GitLab
• Verify your changes appear on GitLab. You should see all changes reflected in the various files that you submit. If not, go back and make sure you committed and pushed.

We will know that the files are yours because they are in your git repository. Do not include identifying information in the code that you submit. Our goal is to grade the programs anonymously to avoid any bias. However, in your README.md file, please cite any sources of inspiration or collaboration (e.g., conversations with classmates). We take the honor code very seriously, and so should you. Please include the statement "I am the sole author of the work in this repository." In the comments at the top your Interpreter.java file.

Late Days

Remember that if‐for any reason‐you will be submitting your lab beyond submission deadline, you'll need to fill out the Late Lab Form. That form contains a description of the late lab submission policy for the course