Institutt for Informatikk
Universitetet i Bergen
INF 225 - Introduction to program translation - H09

Project Part 2 - Recursive-Descent Parser

This part is highly recommended to be solved in groups of two, but each student is to hand in his/hers own program!


You are going to implement a recursive-descent parser recognising valid C- programs, checking whether the program is type correct, and outputting the syntax tree and symbol table for the program. If the program is invalid, an error message is to be printed. Note, that you have also to design a syntax tree structure for C-, suitable for generation by your parser and for later use by a code generator.


Deadline for hand-in is Tuesday October 20th 12:00.

Contents of hand-in

The answers handed in must include:

The answers are to be mailed to Uwe Wolter (, no later than the specified deadline. Answers handed in after the deadline will NOT be considered.

The program

The program is to read source code for a C- program, and print the abstract syntax tree and symbol table to standard out after the program has finished. Any errors found in the source code should be reported to standard err. All output should be in English.

We give some examples of what the output may look like. The output from your program should be very similar to this!

We should be able to run your parser by typing something like:
  Java -CPA my-compiler.jar Parse inputfile.c-
And your scanner by typing something like:
  Java -cp mycompiler.jar Scan inputfile.c-


Read the C- specifications on page 491-496 very, very carefully!

We also make a few additional specifications:

  1. Local variables shadowing formal parameters are allowed, i.e. you may declare a function with a formal parameter and a local variable of the same name, with the result that the formal parameter is of no use whatsoever. In such a case, a warning should be issued.
  2. Void variables, void arrays, and void parameters are not allowed (a void parameter list is of course allowed).
  3. Identifiers may not be overloaded within the same scope, i.e., the same identifier cannot be used both for a function and for a global variable. (You may of course declare local variables with the same identifier as a variable or function in an outer scope.)

Error messages

We require the program to continue parsing after some errors:

Symbol table

In the next hand-in, you will need more attributes for functions and local variables, on top of those required here. It may be wise to take this into account even at this point.

To handle local variables, you may use a stack of symbol tables. When you come to a compound statement, you add a new table on top of the stack, and when you reach the end, you pop the stack. Each node in the syntax tree may keep a reference to the symbol table stack that is valid in this particular node. Thus the symbol tables are available from the syntax tree, even if the parser routine throws them away. To print the symbol tables, you may for example traverse the syntax tree and print the top-most table in each node starting or ending a scope.

Type checking


We give you a few examples of what the output may look like. Your output doesn't have to look exactly like this, but it should be close.

Please use the example files!