Assignment #4: Lexical Analysis

Due: .

Do the programming exercise "Lexical Analysis", from Appel, 2nd, page 34. Turn in phase02.jar containing your Java source code (no class files) and the scanner input written for JavaCC. Create an executable jar file named scan.jar. (See the project overview document.) The lexer or scanner performs lexical analysis of MiniJava programs. Your scanner must not terminate abnormally or raise an exception regardless of the input. Your scanner must print one and only one line of output to the standard output stream. This line should report the number of errors reported (possibly 0) and have exactly the following form:

filename=./path/Error02.java, errors=3

If the number of errors in the input is greater than zero, your scanner must issue error messages in the format below. The message contains the file name, the line number, the character position, and a good error message. Only printable US-ASCII characters are allowed in error messages.

./path/Error02.java:001.011: ERROR -- illegal character &
./path/Error02.java:001.014: ERROR -- illegal character ^
./path/Error02.java:002.002: ERROR -- illegal character \
In this example, three errors were detected and three error message are written to the standard error stream. The number of errors and the errors messages themselves are not specified.

Standard error message formats are useful. Please use the format above for all error messages. If three errors are reported in the standard input stream, then three error messages must be in the standard output stream.

Following the format for this and all the compiler milestones allows me to detect exactly what your compiler determined.

The scanner for MiniJava may detect just one kind of error: illegal character. Other languages might have other lexical errors. For example, scanners for a langauge with strings might detect an unterminated strings. However, an unterminated comment in MiniJava /* ... may just be an illegal slash character. Note that all characters are legal in a comment including those that would otherwise be illegal outside a comment.

We will use JavaCC. You will need to consult the JavaCC documentation. Javacc 5.0 (not 6 ror 7) is installed on andrew.cs.fit.edu.

Futhermore, all output (in the standard output and standard error streams), must be in human-readable (i.e., printable) US-ASCII characters. Even if the input contains non-printable US-ASCII characters, the output must not.

MiniJava Language

The definition of the language Mini-Java can be found at the back of the text. A summary of the grammar can be found on the WWW.

In Java, comments do not nest. You do not have to implement nested comments in MiniJava (despite what Appel says on page 484). You may use nested comments if you wish, as that is an interesting exercise.

Identifers

Identifiers in Mini-Java do not quite follow the Java definition of identifiers. In Mini-java the dollar sign $ is not allowed. The underscore _ is allowed, but not as the first character.

A Mini-Java identifier cannot be a Java keyword like: if, goto, or the Java literals: true, false, or null. The definition of an identifier in Java is found here 3.8 Identifiers

White Space

The definition of white space is found in 3.6 White Space We will take white space to mean any one or more of the following characters.
  Java  octal dec  hex  name
HT  \t   011   9  0x09  horizontal tab
LF  \n   012  10  0x0A  line feed
FF  \f   014  12  0x0C  form feed
CR  \r   015  13  0x0D  carriage return
SP       040  32  0x20  space
Mini-Java does not permit the ASCII, control character "sub" at the end of the program file (except in comments).

Of particular interest is the definition of a newline, because, without it, we cannot agree on line numbers for errors. A line may be determined by the underlying operating system. This is so ugly we might be tempted to write a pre-scanner that takes care of this. Instead we will define a newline to be the line-feed character (the way Unix does). Thus, the number of lines in a program is the number of line-feed characters (if the program ends in a line feed). Since carriage-return characters are ignored, DOS/Windows files will work in the expected fashion. Unlike Java we do not accept CR alone as a line terminator.

Be careful with the regular expression '.' --- it may not match \n or \r.

Integer Literals

At this point integer literals may be arbitrarily long. Later we can reject integer literals which have no representation as a Java int, a 32 bit signed integer.

Mini-Java does not permit binary, octal, or hexadecimal interer literals.

We do not require underscores be permited in integer literals, but it is easy enough to do what Java does.

Compiling and Testing the Scanner

I will build your project like this:

jar -xf phase02.jar
find . -name '*.class' -delete
# Assumes Makefile in current directory
make
# Assume scan.jar created in current directory
Your makefile may assume javacc is in the execute path. And I will test your project like this:
java -jar dir1/scan.jar dir2/test01.java
java -jar dir1/scan.jar dir2/test02.java
java -jar dir1/scan.jar dir2/test03.java

If test01.java contains no errors, then "errors=0" must appear in the one and only line of output to standard output. If test01.java contains errors, then "errors=x" must appear in the one and only line of output to standard output, where x is a positive number.

Makefile

JAVAC := javac
JAVACC:= javacc


default	:	compiler

compiler :      scan.jar

# options: c--create; f--name of jar file; e--entry piont
scan.jar	:
        $(JAVAC) */*.java
	jar cfe $@ main.Scan error/*.class parser/*.class main/*.class

clean	:
	-/bin/rm *~ */*~
	-/bin/rm */*.class
Makefiles must have tabs, and must end in \n not \n\r!

JavaCC

  1. Where can I find JavaCC? Go to JavaCC Home Page and download the binaries.
  2. Using JavaCC
  3. What does a scanner specification look like in JavaCC?
    PARSER_BEGIN(ExampleScanner)
    package parser;
    public class ExampleScanner {}
    PARSER_END(ExampleScanner)
    
    TOKEN : {
         < IF:      "if" >
       | < ELSE:    "else" >
       | < GT:      ">" >
       | < INVALID: ~[" ", "\t", "\n", "\b", "\f", "\r"] >
    
    }
    
    SKIP : {
         <"//" (~["\n", "\r"])* ("\n" | "\r" | "\r\n")>
       | " "
    }
    
  4. How do I run JavaCC? Use the sh or batch script in the bin directory.
  5. What happens when I run JavaCC? Seven Java files are created from the .jj file. Three of these files actually depend on the your intput and must be recreated everytime the .jj input is changed.
  6. Where does JavaCC put the Java files? JavaCC puts the files in the current directory unless you specify otherwise
          javacc -OUTPUT_DIRECTORY=path/dir file.jj
          
    This is important if you put your parser in a Java package.
  7. Do I need any productions (parsing rules) to get the scanner to work? No, you may omit all productions. Productions are not needed for the scanner, but are needed, naturally, for the parser. The function getNextToken will be generated.
  8. How do you call the scanner from the main program?
      final MiniJavaScanner lexer = new MiniJavaScanner (new FileInputStream (filename));
      if (trace) lexer.enable_tracing(); else lexer.disable_tracing(); // for parsing only
      final Token t = lexer.getNextToken ();
    
  9. How do I know if the next token is the last token in the file?
      import static javacc.[scanner]Constants.EOF;
    
      final Token t = lexer.getNextToken ();
      if (t.kind=EOF) // ...
    
  10. Do I have to define the EOF token as I do the other tokens in my scanner? No, it is defined automatically for every scanner.
  11. Do I need anything from JavaCC when I run my scanner/parser as opposed to when I create it? No, with the seven Java files, you no longer need any class files from JavaCC.

Example Output

Appel's sample programs can be found here: Cambridge WWW site. We an one of his sample programs and show the compiler output.

Normal

Just print the file and the number of errors to the standard output.
> java -jar scan.jar ../../minijava/appel/Factorial.java      
filename=../../minijava/appel/Factorial.java, errors=0
Your program must print exactly one line to the standard output. (Error messages get printed to the standard error stream.)

Verbose

The verbose output is not required it is shown here just to help understand the scanner.
> java -jar scan.jar ../../minijava/appel/Factorial.java      
filename=../../minijava/appel/Factorial.java, errors=0
Note: debug/verbose output should be sent to a file, not the standard output stream nor the standard error stream. We specify that the standard output stream should have exactly one line in it. We specify that the standard error stream should have error messages (if any) and nothing else. So, there is no other place for debug/verbose output to go.

The verbose output for the scanner might look like this:

../../minijava/appel/Factorial.java:001.001: CLASS "class"
../../minijava/appel/Factorial.java:001.007: IDENTIFIER "Factorial"
../../minijava/appel/Factorial.java:001.016: LeftBrace "{"
../../minijava/appel/Factorial.java:002.005: PUBLIC "public"
../../minijava/appel/Factorial.java:002.012: STATIC "static"
       * * *
../../minijava/appel/Factorial.java:014.027: MULT "*"
../../minijava/appel/Factorial.java:014.029: LeftParen "("
../../minijava/appel/Factorial.java:014.030: THIS "this"
../../minijava/appel/Factorial.java:014.034: DOT "."
../../minijava/appel/Factorial.java:014.035: IDENTIFIER "ComputeFac"
../../minijava/appel/Factorial.java:014.045: LeftParen "("
../../minijava/appel/Factorial.java:014.046: IDENTIFIER "num"
../../minijava/appel/Factorial.java:014.049: MINUS "-"
../../minijava/appel/Factorial.java:014.050: INTEGER_LITERAL "1"
../../minijava/appel/Factorial.java:014.051: RightParen ")"
../../minijava/appel/Factorial.java:014.052: RightParen ")"
../../minijava/appel/Factorial.java:014.054: SEMICOLON ";"
../../minijava/appel/Factorial.java:015.009: IDENTIFIER "return"
../../minijava/appel/Factorial.java:015.016: IDENTIFIER "num_aux"
../../minijava/appel/Factorial.java:015.024: SEMICOLON ";"
../../minijava/appel/Factorial.java:016.005: RightBrace "}"
../../minijava/appel/Factorial.java:018.001: RightBrace "}"
../../minijava/appel/Factorial.java:018.002: EOF

Token Names

Javacc uses the tokens names provided in the .jj to generate the scanner. But to Java the tokens are just numbers. This is inconvenient in debugging. It would be nice to recover the user's token names as in the verbose output above. (Of course, different programmers may choose different names.) This is easy with reflection since javacc uses the token names as Java variables names. Study the following class:
import java.util.TreeMap;
import java.lang.reflect.Field;

public final class FieldNames extends TreeMap  {

   public FieldNames (final String class_name) {
      try {
	 final Class c = Class.forName (class_name);
	 final Field [] f = c.getDeclaredFields();
	 for (int i=0; i<f.length; i++) {
	    if (f[i].getType()==int.class) put (f[i].getInt(null), f[i].getName());
	 }
      } catch (final Exception e) {
	 e.printStackTrace (System.err);
      }
   }
}

Turning it in

Please turn in one Java jar file named phase02.jar using the submit server.

For example, I expect you to submit something approximately like the following list of files:

  1. Makefile -- must not be in a subdirectory
  2. parser/scanner.jj -- should put all code in subdirectory/packages
  3. main/Scan.java -- hypothetical main program
  4. global/Files.java -- hypothetical support files
  5. compile -- script 'java -jar scan.jar $1' (not really needed yet)
Turn in all source files that you need to make your project in the single jar file. No Java *.class files are permitted. Notice that the subdirectory structure must be preserved in order for Java packages to work correctly.

All submitted files must be encoded in US-ASCII characters to avoid unintended misinterpretation of the transmitted files.

The submit project tag for this assignment is asgn3. For your convenience, here is a submission form for this assignment.