Due: Friday, May 28 at the beginning of class. Turn in a printed listing of your code and a listing of some sample input and the output produced (we'll try to come up with some test programs -- watch the mailing list for announcements). If you were working with a partner for the previous assignment, you should continue working with the same person.
For this assignment, add a recursive descent D parser and symbol tables to your compiler. The resulting program should parse D programs, build and print a symbol table for each function, and, at the end of the program, print a global symbol table showing the names of all functions. For now, each symbol table only needs to contain identifiers. We will add more information later.
The Parser class should include a separate method to parse each major D construct. The constructor for this class should include a scanner parameter that the parser can use to read the source program as a sequence of tokens.
The test program for this assignment should initialize the scanner and parser, open any additional files needed, then parse the program by calling the method for the nonterminal program. A rough sketch of the main program could look something like this.
// parser test program
public static void main (String [] args) {
InputStream sourceFile; // D source program
// use a file dialog to select and open sourceFile
...
// create scanner object to read tokens from sourceFile
Scanner scan = new Scanner(sourceFile, ...);
// create parser object to parse the program
Parser parse = new Parser(scan, ...);
// parse source program and print a trace
parse.startTrace();
parse.program();
}
The test program for the parser should produce the following output:
The trace should be produced by printing a suitable message at the beginning and end of each parser method. You should include appropriate methods in the parser to turn the trace on or off. A sketch of this mechanism follows (where outputStream is the stream on which the source program and symbol tables are written).
public class Parser {
...
boolean tracing; // = "print parser trace"
// start or stop tracing
public void startTrace() { tracing = true; }
public void stopTrace() { tracing = false; }
// print trace messages
void traceEnter(String method) { outputStream.println("entering " + method); }
void traceExit (String method) { outputStream.println("leaving " + method); }
...
// term ::= factor | term * factor
void term() {
traceEnter("term");
[code to parse a term]
traceExit("term");
}
There should be a similar mechanism to turn the symbol table printouts on and off. That allows us to turn off the symbol table output without having to modify the parser source code.
The parser should contain two symbol tables: one for the parameters and local variables in the function currently being compiled, and a second for the (global) function names. These tables are similar, but will eventually contain different information. For now, they only need to contain identifiers.
Entries are added to the local and global symbol tables at different times. Local parameters and variables are supposed to be declared before being used. If you are checking for errors, a good way to handle undeclared variables is to print an error message, then add the variable to the symbol table to prevent additional error messages if it is used again.
Functions may be called before they are defined in a program. When a function is first used or defined (whichever comes first), it should be added to the global symbol table. It might be useful to have a boolean variable with each function entry indicating whether it has been declared yet to allow detection of functions that are used without ever being declared. You could also keep track of the number of parameters for each function and print an error message if the function is called with the wrong number of arguments.
There are many ways to implement symbol tables: lists, trees, etc. We suggest you take advantage of the available Java library routines and implement the symbol tables as instances of Java class Hashtable.