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

• Every initial declaration of an identifier should appear in bold face red.
• Indentation and inter-token spacing should be determined by your program, not by the Java source.

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:

• implemented grammar
• FIRST sets for implemented grammar
• full grammar (which you have to implement)
• FIRST sets for full grammar

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:

• For the trivia assignment: noon, Tuesday November 7.
• For the main assignment: 11:59 p.m., Friday November 17.

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:

• Develop heuristics to
  • format comments more nicely.
  • split and format statements that are too long to fit comfortably in the width of a browser window.
  • align parallel constructs in columns, e.g.:

          int          count  = 3;
          boolean      done;              // termination condition
          const double pi     = 3.1416;   // won't change
          

• Arrange to avoid the newline and extra level of indentation between an else and an immediately subsequent if.
• Where possible, create links from uses of an identifier back to its declaration. (This is hard. Java's scoping rules are quite complicated, and the possibility of out-of-order declarations will require at least two passes over the source.)
• Recover gracefully from syntax errors. These are much more common than lexical errors, and harder to handle. For ideas, see pp. 58-60 in Programming Language Pragmatics (the CSC 254 text).

Back to the course home page