CSC 173, Fall 2006

Assignment 4: Parsing


Continuing in the vein of Assignment 3, you are to build a more sophisticated program to format Java programs as HTML. As before, keywords should appear in bold face black, literals (numbers, character and string constants, and the words true, false, and null) should appear in bold face green, and comments should appear in black italics. In addition

Initial declarations of identifiers include class names, local variable names, formal parameter names (including parameters to catch blocks), field names, method names, and constructor names. For example:

      static class foo { ...
  
      const int pi = 3.1416;
  
      my_type my_method(int a, my_class b) ...
  

Note that identifiers should remain normal face black in all contexts other than their definition. In the example above, my_type and my_class are not printed in red.

Indentation and spacing rules are described in more detail on a SEPARATE PAGE.

I am providing source code for a significant fraction of the project; your task is to extend this source to produce a working program. (For those who prefer, the source code is available as a gzip-ed tar file.) This source code includes a solution to Assignment 3. Rather than focus on the scanner, however, you will spend most of your time in file parser.c, which contains a recursive descent parser for Java.

As in Assignment 3, I have simplified the code somewhat by "covering" the language--accepting constructs that are not really valid Java--and you may continue in this vein. Your program should work correctly when given valid Java as input. You are also, however, expected to perform some basic error recovery. The assignment details with respect to error recovery are listed on this page.

On companion pages you can find the LL(1) grammar on which the current code is based, together with the full grammar you are to implement. In both cases you can also find the FIRST sets for all non-terminals in the grammar. These should help you to understand the case labels in the current code, and to create the labels in the new code you will write:

The official grammar from the Java reference manual is also available on-line if you feel the need to double-check something. Note that this grammar is designed for "bottom-up" parsing in the style of yacc and bison; it won't work directly for recursive descent.

Note that you are required to retain the recursive structure of the parser; ad-hoc approaches are not allowed for this assignment.

Trivia assignment

Send email to cs173@cs.rochester.edu containing the results of the following tasks:

  1. Compile the provided source code. Feed it the following tiny Java program and include the output in your email.
          import java.io.*;
          public class hello {
          public static void main(String[] args) {
          // execution starts here
          for(int i=0; i<10; i++){System.out.println("Hello, world");}}}
      

  2. Format this same Java program by hand with respect to indentation and inter-token space. (You do not have to include the HTML tags for bold, color, italics, etc.) Include the formatted program in your email.

  3. You will notice in the output of the provided code that the bodies of methods are indented one level (4 spaces). A little inspection of the code will reveal that this is because the global variable indent_level is incremented and decremented at the beginning and end of function parse_compound_stmt. Why doesn't that function automatically cause the bodies of while loops, if statements, etc. to be indented, too?

  4. In function parse_field_tail in parser.c there is a comment noting a problem for your formatting program: in a field of a class, if the first token after any modifiers is an identifier, that identifier may name a type or it may be the name of a constructor. You need to print it in red in the latter case, but not the former. Unfortunately, the code doesn't know which case applies at the time of the call to parse_qualified_name, so when that routine matches the identifier it won't know what to do. Discuss how you might solve this problem. (This answer should be written in prose. Don't send code.)

  5. Identify the spot in the provided code (it's a single line) where you will need to make changes to control the spacing between tokens within a line of Java source.

DUE DATES:

NO EXTENSIONS.

What/how to turn in

As in Assignment 3, you will want to feed your program a variety of Java source files. Watch the newsgroup for any updates on what to put in your README file. As in previous assignments, you will submit your work using the turnin script. Please clean up your directory before submitting. Do not submit any executable, *.o, or core files (hint: use make clean). Watch the newsgroup for any late-breaking details.

Extra Credit Suggestions

For extra credit (to be used for grade adjustment at the end of the semester — see here), you might consider the following options:


Back to the grading page

Back to the course home page

Last Change: 31 October 2006