CSE 413 Autumn 2007 -- Assignment 7

Context Free Grammars, & D Parser

Due: Electronic turnin of the entire compiler (so far) due no later than 8am, Friday, Nov. 30. Printouts of your parser code (only) and tests, and answers to written questions due at the beginning of class on Friday, Nov. 30.

Overview

The main goal of this assignment is to 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 functions showing the order in which they were executed; build and print a symbol table for each function; and, at the end of the source 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 (a little) more information later.

Written problems

Here are a few problems involving context free grammars.  You should do these problems individually, even if you have a partner for the compiler project.

1. Consider the following grammar:
   S ::= aAS | a
   A ::= SbA | SS | ba
                  
1. What are the terminals, nonterminals, and start symbol for this grammar?
2. Draw parse trees for the following sentences:
1. aabbaa
2. aabaaabaa
3. Give top down, leftmost derivations of the sentences in (b).
   
2. Give a context free grammar that generates
   1. The language containing strings with an equal number of a's and b's.
   2. The language containing strings of the form ww^Rcaⁿb²ⁿ, where w is a string of 1 or more a's and b's; w^R denotes the reversal of w, and the superscript n stands for any positive integer, meaning that the end of the string should contain 1 or more a's followed by twice as many b's as a's.
      

Parser

The functions that make up the recursive descent parser should be placed in a source file named parser.c, and you should create a header file parser.h with definitions of the function(s) that compile a program and control the parser.  This file should include a separate function to parse each major D construct (expression, statement, different kinds of statements, function_def, parameters, etc.).  You should include any other functions and variables that you need in this file. Everything except functions declared in parser.h should be static so they are not visible outside parser.c. (If this file seems to get too large, you might want to split it into a handful of files, but you definitely don't want to have a huge collection of files each of which contains only one or two functions.)

The parser should get the tokens that make up the input program by calling the scanner's next_token() function as needed.  The parser should use functions from io.[hc] to print the parser trace, symbol table output and, if you implement them, error messages. This is the same set of I/O routines used by the scanner to read the program, and the result is that output produced by the parser will appear interspersed with the lines read from the source program, which helps visualize the relationship between the program and the parser actions. You should turn off any tracing of scanner output (token printouts) except when (or if) you need to do this during debugging.

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 D function.  The parser should include a function or functions to control whether this table is printed after each D function definition has been processed.
• Create a global symbol table containing the names of all functions in the D program.  If local symbol tables are being printed, this table should also be printed after processing the complete source file.
• Each parser function 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 interspersed with the source program lines in the output file.  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. You should use the symbol tables you created for assignment 5 to implement this.

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 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 another function.  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 a 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 without declaration, 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.

Trace Output

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

      /* true if producing parser trace output, false if not */
      static int tracing = 1;

      /* start or stop tracing */
      void set_tracing(int on_off) { tracing = on_off; }

      /* print trace messages when entering and leaving the named parser function */
      void enter(char* function) { 
         if (tracing) { putstr("entering "); putline(function); }
      }
      void exit (char* function) {
         if (tracing) { putstr("leaving "); putline(function); }
      }

      ...
      /* parse:  term ::= factor | term * factor   */
      private void term() {
         enter("term");
         code to parse a term
         exit("term");
      }
   }

If you want to get fancy, you could keep track of the nesting depth of the calls (number of parser functions called that are not yet finished) and indent the trace lines to reflect this nesting.

There should be a similar mechanism to turn the symbol table printouts on and off.

Test Program

Your compiler should contain a main function that tests the parser.  This test program should initialize I/O and any other necessary routines, then parse the D program by calling the function for the nonterminal program.

Hints

• Some of the rules in the D grammar contain left recursion and similar problems.  Your parser routines won't be able to use 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 loop to simplify handling of these sequences.
• It is a good idea to introduce separate parser functions 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 is likely to be different.  The final compiler structure will be cleaner if you define different functions for these non-terminals.
• Define simple helper functions to avoid redundant code in the parser.  A couple of obvious ones: a function that skips past the current input token and advances to the next one; a function that checks whether the current token is what is expected and advances to the next one if it is (if you have some error checking).  If you find yourself using cut-n-paste to copy chunks of code repeatedly, that is likely to be a sign that you should abstract those operations into separate functions.
• 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 language.

Test Programs

There are some test programs on the course web site in the assignments section.  It would also be great if you would contribute additional test programs.

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 functions work properly.

If you have added any error checking, include output that demonstrates these checks. (Addendum: you can save including this output until next week's turn-in of the entire working compiler.)

Project Turnin

Electronic: Turn in your program electronically using the link on the assignments page. If you worked with a partner only one person should submit. You should submit all files required to make your compiler so far (scanner and parser code).

Paper: Hand in a printout of your code, test output and written problems in class on November 30. You should turn in your complete compiler online, but you only need to hand in printed copies of the parser and tests in class (i.e., the new stuff). Note that if you worked with a partner on the compiler each partner must still turn in solutions to the written problems individually.