CSC 173, Fall 2006

Assignment 3: Scanning


DUE DATES:

NO EXTENSIONS.

Warning Read the whole assignment, paying close attention to the two separate parts due on different dates. Follow the instructions on turning in the assignments carefully.


You are to build, in C, a program that formats Java programs as HTML. When your output is viewed in a web browser, 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. Everything else should appear in normal face black, all on a white background.

We are providing you with source code for a significant fraction of the project; your task is to extend this source to produce a working program. The heart of the program is a scanner that identifies Java tokens. (Special thanks to Michael Scott for the provided code.)

We are also providing several Java source files and matching HTML files, which you can use to test your code.

Token definitions

You are required to recognize nine kinds of Java tokens: keyword, identifier, literal, left_brace, right_brace, other_symbol, white_space, comment, and end_of_file.

The definitions below simplify the actual Java rules in many ways. They categorize correct Java tokens correctly, but also generate some things that aren't valid in Java. The intent is to minimize the amount of work you have to do, while maintaining correct behavior when your Java input is correct.

Several tokens are entirely straightforward. White space is a contiguous (maximal length) string of space, tab, newline, carriage return, and form feed characters. End of file is an artificial token that the scanner will return after it has returned all real tokens. The provided source already recognizes these correctly.

The lbrace and rbrace characters are the left ({) and right (}) curly braces, respectively. (You won't actually rely on the difference between braces and other symbols in the current assignment, but you will in assignment 4.) Other symbols are the following: 

      [       ]       ;       ,       .       (       )
      =       >       <       !       ~       ?       :
      ==      <=      >=      !=      &&      ||      ++      --
      +       -       *       /       &       |       ^       %
      +=      -=      *=      /=      &=      |=      ^=      %=
      <<      >>      >>>     <<=     >>=     >>>=
For the purposes of this assignment, you can cover these symbols (imprecisely) with the regular expression
punctuation*
where punctuation generates any of the characters in any of the symbols shown above.

Keywords are the following: 

      abstract   boolean    break         byte        case     catch
      char       class      const         continue    default  do
      double     else       extends       final       finally  float
      for        goto       if            implements  import   instanceof
      int        interface  long          native      new      package
      private    protected  public        return      short    static
      super      switch     synchronized  this        throw    throws
      transient  try        void          volatile    while

An identifier is a contiguous (maximal length) string of letters and digits that begins with a letter and that isn't a keyword or literal. The regular expression for this is

letter (letter | digit)*
where letter generates all the upper and lower-case letters, plus the underscore and the dollar sign; digit generates all the decimal digits, including 0; and we assume that the scanner looks candidate identifiers up in a set to filter out the keywords and literals. (There are of course many possible implementations of the set; a hash table would be fastest.)

Comments come in both C (/* ... */) and C++ (// ...) styles. We can generate these with the following regular expression:

// not_eoln* | /* (not_star | * not_slash)* ** */
where not_eoln generates any character other than a newline or carriage return, not_star generates any character other than a star (asterisk), and not_slash generates any character other than a slash. Comments of the same kind do not nest, but the /* and */ sequences have no meaning inside a // comment, and the // sequence has no meaning inside a /* */ comment.

Literals are the messiest tokens. They include integer and real constants, character and string literals, and the words true, false, and null. The definitions of real numbers and of escape sequences within character and string literals are particularly messy. The following regular expression is a major simplification, but (with the exception of true, false, and null; see below) will distinguish valid Java literals from other valid Java tokens in a valid Java program:

(. | ) digit (. | (e | E) (+ | - | ) | abcdflx | digit)*
| ' (ch_char | \ char)* '
| " (str_char | \ char)* "
where represents the empty string (no input — nothing at all); abcdflx generates any of the letters a, b, c, d, f, l, x, A, B, C, D, F, L, and X; char generates any character other than newline or carriage return; ch_char generates any character other than newline, carriage return, backslash, or single quote; and str_char generates any character other than newline, carriage return, backslash, or double quote. As with keywords, we assume that true, false, and null are distinguished from identifiers by looking them up in a predefined set.

As noted above, this definition for literals will fail to catch many errors in Java programs, including malformed escape sequences in character and string literals, character literals with more than one character inside, and malformed numbers of various sorts. Java afficianados may also note that Unicode escapes (\uXXXX) are allowed outside of character and string constants in Java (and in fact the Unicode escapes for newline and and carriage return are not allowed inside character and string constants), but you may ignore these subtleties for this assignment. The official Java language specification is available on-line if you feel the need to consult it.

Program structure

You should begin by carefully reading the provided source code. This source consists of four ".c" files, three ".h" files, a hand-written "makefile", and an automatically generated subsidiary makefile named makefile.dep. The makefiles contain the information needed to rebuild your program when you make changes to one or more source files. Specifically, if you type 

      make format
at the shell prompt, the make tool will tell the C compiler to recompile all and only those files whose behavior would be altered by your changes, and (assuming there are any such files) link the new versions together with old versions of any unaffected files to create a new version of your executable program. You should not need to modify the makefiles unless you change the set of source files required to build your program. IMPORTANT: If you add or delete #include directives in any of your source files, you must regenerate file makefile.dep by typing 
      make depend
You will also need to run this command if you port the code to a different version of Unix (e.g. Solaris).

When you run the executable format program, function main first calls a "reader" function to bring the entire source file into memory, constructing a linked list of lines. It then repeatedly calls the scanner to identify the next token, which it echoes to standard output, surrounded by square brackets. You will need to take out the brackets and insert formatting information where appropriate.

The scan function is implemented as an explicit automaton, in the form of nested switch statements. You are required to preserve this style of implementation. If you encounter a lexical error (example, unterminated string), you should do the following

 Read the source code carefully. Notice that the reader reads in the whole file and stores it as a list of lines. This should be helpful in performing the above error recovery.

You may use any of the functions in the C strings library, including strdup. You may also want to use the C hash table or binary search functions; type 

      man 3 hsearch
      man 3 bsearch

What you need to know about HTML

Your HTML output should begin with a header that looks something like this:
<html>
<head>
<title> Formatted java output </title>
</head>
<body bgcolor=white>
<pre>

Your output should end with a footer that looks something like this:
</pre>
</body>
</html>

To set text in bold, surround it with <b> </b> tags. To set text in italics, surround it with <i> </i> tags. To set text in color, surround it with <font color=xxx> </font> tags, where xxx is the name of the color you want.

If you need more information, here's a handy HTML reference guide on-line.

Trivia assignment

Because of the scope of this assignment, you will submit two pieces. The first will be an email to cs173@cs.rochester.edu with the answers to the following questions. The idea here is to get you looking at the project and the code well before the due date.

  1. Devise a deterministic finite automaton that recognizes Java comments. You will probably want to do this first as a circles-and-arrows drawing using pencil and paper. You should define transititions for all possible input characters, including a dead state if necessary. In your email, indicate
    • The number of states. Let state zero be the start state.
    • The final state(s).
    • The transition function, written as (state, input_char, new_state) triples.
    As shorthand, you may define classes of characters (e.g. not_eoln) to use in the transition function.

  2. Compile the provided source code. Feed it the source file main.c and include the output in your email. (Yes, this is supposed to be a Java scanner, not a C scanner, but the file is handy and the provided code is too dumb to tell the difference.)

  3. Produce (by hand) the output that your completed program should produce when fed the following tiny Java program. Include this output in your email. 
          import java.io.*;
      
          public class hello {
      
          public static void main(String[] args) {
              // execution starts here
              System.out.println("Hello, world");
          }
      
          }

DUE DATES:

NO EXTENSIONS.

What/how to turn in

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 e-mail/the whitboard for any late-breaking details.

Extra Credit Suggestions

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