CSE 413 Winter 2001

Assignment 6 -- D Parser & Symbol Tables

Electronic turnin of programming part due Tuesday, Feb. 27, by 10:00 pm.
Turnin receipt and test output due in class Wednesday, Feb. 28.

Overview

For this assignment, add a recursive descent parser and symbol tables to your D compiler. The resulting compiler should parse D programs and print a trace of the parser methods showing the order in which they were executed; 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.

Parser

The methods (functions) that make up the recursive descent parser should be placed in a class named Parser.  This class should include a separate method to parse each major D construct (expression, statement, different kinds of statements, function_def, parameters, etc.).  Class Parser should also include any other methods or data that you need.

The constructor for Parser should have a Scanner parameter.  The parser should get the tokens that make up the input program by calling the nextToken method of the supplied Scanner object as needed.  The constructor should also have an EchoIO parameter that that can be used to print trace output, symbol tables and (if implemented) error messages.  This EchoIO object should be the same one the scanner is using to read and echo-print the source program, so any output from the parser will appear interspersed with lines from the source program.

In addition to parsing the input program, the parser should do the following:

• Create a local symbol table containing names of parameters and local variables declared in each function.  Class Parser should include a method that can be called to control whether this table is printed after each function definition has been processed.  
• Create a global symbol table containing the names of all functions in the program.  If local symbol tables are being printed, this table should also be printed after processing the complete source file.
• Each parser procedure should, if requested, be able to print a message each time it is entered and right before it exits.  This trace will help you visualize how the parser works, and can be a useful debugging tool.  More details below.  When the trace is being printed, the trace messages should appear along with the source program in the parser output.  Don't worry if the trace output doesn't appear to be exactly synchronized with the echoed input lines.  Some of the trace output corresponding to one input line may not appear until after the next line of the D program has been read and printed.  That's perfectly normal - a parser often doesn't realize it's done parsing a construct until the beginning of the next construct has been read.
• (optional) Print meaningful error messages and recover from some syntax errors.  Don't spend a lot of effort here, but it is a useful exercise to try to implement some simple error detection.

Symbol Tables

The parser should contain two symbol tables: one for parameters and local variables of the function currently being compiled, and a second, global one, containing function names. These tables are similar, but will eventually contain different information. For now, they only need to contain identifiers.

The local symbol table should contain the names of all identifiers and parameters declared in the current function.  An empty table should be initialized each time the compiler reaches the beginning of a function definition.  As each parameter or local variable declaration is parsed, the name of that variable or parameter should be added to the local symbol table.  When the entire definition of the function has been parsed, this table should be printed if symbol table output has been requested.

For this assignment, the main use of the local symbol table is to verify that all declarations were parsed successfully and that names of parameters and local variables have been recorded properly.  If you are doing some error checking, you could use this information to detect duplicate declarations of identifiers or use of undeclared identifiers in statements and expressions. If you do this, it's best if your compiler only complains once about each undeclared identifier.  (Redundant error messages tend to annoy users and can hide other, useful information.)  A good strategy to avoid redundant "undeclared identifier" messages is to add the undeclared identifier to the symbol table after it is first seen and an error message has been printed.

The global symbol table should contain one entry for each function name used in the program.  Remember that in D, as in Java, a function does not need to be declared before it can be used.  So the first occurrence of a function name might be in a function call expression in some other function, instead of the actual function declaration.  To deal with this, put a function name in the global symbol table when it is first encountered, no matter how.

If you want to check for errors, there are a couple of things that can be detected easily.  First, you can include an boolean value with each function entry indicating whether the function definition has been encountered yet.  This should be set to false if the name is first encountered in a function call.  When a function declaration is parsed, set this variable to true.  If it was already true when the function definition is reached, then the function name is being declared twice - an error that you could report.  When the end of the program is reached, you could scan the global symbol table and report any functions that were used (called) but never defined.

Another useful piece of information about each function is the number of parameters.  If you record this when you first encounter the function, you can detect when the function is called with the wrong number of arguments, or if the function definition contains a different number of parameters than were used in an earlier call.

The D language includes two functions, get and put, that provide input and output of integer values.  These functions are not defined in D programs, but are available and no error messages should be generated if they are used.  The simplest way to handle this is to initialize the global symbol table so it contains appropriate entries for get and put before parsing the program.

There are many ways to implement symbol tables: lists, trees, etc. But the Java library has collection classes that you should use.  In particular, HashMap is a likely candidate.  You might want to create symbol table classes to hide this underlying data structure and provide suitable operations that the parser can use to access it.

Trace Output

The trace should be produced by printing a suitable message at the beginning and end of each parser method. You should include a method in the parser to turn tracing on or off. Here's a sketch of how this could work.

   public class Parser {
      private EchoIO eio;       // I/O object for parser output
      private Scanner scan;     // source of input tokens
      private boolean tracing;  // = "print parser trace"

      // constructors, etc. here....

      // start or stop tracing
      public void setTracing(boolean onOff) { tracing = onOff; }

      // print trace messages when entering and leaving named method
      private void traceEnter(String method) { eio.println("entering " + method); }
      private void traceExit (String method) { eio.println("leaving  " + method); }

      ...
      // term ::= factor | term * factor
      private 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.

Test Program

Class Parser should contain a main method that tests the parser.  This test program should initialize I/O, the scanner, and the parser, then parse a D program by calling the method for the nonterminal program. The test program might look something like this.

   // parser test program
   public static void main (String [] args) {

      // create I/O object and open files specified by args
      EchoIO eio = new EchoIO(args);

      // create scanner object (source of tokens)
      Scanner scan = new Scanner(eio);

      // create parser object
      Parser parse = new Parser(scan, eio);

      // parse source program and print a trace
      parse.setTracing(true);
      parse.program();
   }

Hints

• Some of the rules in the D grammar contain left recursion and similar problems.  Your parser routines won't be able to implement these rules literally.  Make the necessary adjustments.
• Recursion in the grammar is often used to define sequences of various things like the list of function definitions that make up a program, the factors to be multiplied together to calculate the value of a term, etc. You can often use a simple loop to handle these sequences.
• It is a good idea to introduce separate parser methods for things that are similar in the grammar, but mean different things in a D program. An example is the rules for parameters and declarations.  While these are syntactically almost the same, the processing needed to handle them in the final compiler may well be different.  The compiler structure will be cleaner if you define different methods for these non-terminals.
• Define simple helper methods to avoid redundant code in the parser.  A couple of obvious ones: a method that skips past the current input token and advances to the next one; a method that checks whether the current token is what is expected and advances to the next one if it is.  If you find yourself using cut-n-paste to copy chunks of code repeatedly, it may be a sign that you should abstract those operations into a separate method.
• Print the source code lines, trace output, and symbol tables as you go; don't attempt to build a huge string containing multiple lines of output or otherwise buffer the data in your code.
• While error checking is not required, it is good to have a simple strategy for handling syntax errors.  A key principle is that no matter what sort of junk is found in the input, the parser should continue to make progress through the source file.  Be sure your error handling strategy doesn't leave the parser stuck somewhere in the input, repeatedly examining the same token without advancing.
• Finally, start small.  Get a few pieces of the parser for a small part of the grammar working first.  Then add to this until you have a parser for the complete langauge.

Test Programs

There are some test programs on the course web site in the assignments section.  It would also be great if you want to contribute additional test programs by either posting them to the class mailing list, or sending them to the course staff.

You should demonstrate that your parser works by parsing some sample D programs.  The output should show the parser trace and symbol tables, along with the corresponding lines from the source code.  Be sure that your test program(s) use all of the constructs in the grammar to verify that all of the parser methods work properly.

If you have added any error checking, include output that demonstrates these checks.

Project Turnin

Turn in your program electronically using this turnin form.

Hand in the online receipt along with test output and your written problems in class on February 2.