Institutt for Informatikk
Universitetet i Bergen
INF 225 - Innføring i Programoversettelse - H04
Project Part 2 - Recursive-Descent Parser
This part is highly recommended to be solved and handed in groups of two.
Goal
You are going to implement in Java, C, or C++ 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
structue for C- suitable for generation by your parser.
Deadline
You have to hand in your answers no later than Monday October 18th
at 12:00 am.
Contents of hand in
The answers handed in must include:
- Complete, fully documented, source code. Including the code from part1.
- Archive file with all classes we need to run the program.
- A description of your program, in a seperate text file. Emphasize the parts requiring special consideration and
report shortly your design decisions. Avoid repeating descriptions, even when your code is repeated.
Do not include general text about program analysis and restrict
yourselves to your own code.
- Instructions how to run your program (command line syntax and options).
The answers are to be mailed to
Magnus Hoff (s1696@lstud.ii.uib.no), no later
than the specified deadline. Answers handed in after deadline will NOT be considered.
The program
The program is to read source code for a C- program from standard in,
and print the abstract syntax tree and symbol table to standard out
after the program having finished.
If errors are found in the source code, the program should report
the error to standard err.
We give some examples of what the output may look like. See Fillager->Project->test_x.c-
Specifications
Read the C- specifications on page 491-496 very, very carefully!
We also make a few additional specifications:
- 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 gcc(1) would issue a
warning, but you don't have to check for this.
- Void variables, void arrays, and void parameters are not allowed.
(A void parameter list is of course allowed.)
- 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
-
When the parser finds errors during syntax analysis, it should determine
the type and cause of the errors as exactly as possible.
-
Each reference should be reported with reference to line number and
column number in the source file.
- The parser should attempt to recover after an error.
We require the program to continue parsing after some errors:
Symbol table
- All symbols in the program must be reported after analysis,
not only the global ones.
- For each symbol, the program must report name and type.
- Remember that parameters to functions work as local variables.
In the next handin, 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 which is valid in this particular node. Thus the symbol tables
are available from the syntax tree, even if the parser routines throws
them away.
To print the symbol table, you may travers the syntax tree and print
the top-most table in each node ending a scope.
Type checking
- All variables and functions must be declared before use.
-
Function calls must have the right number of parameters, which must
be of correct type.
-
Assignments must be of compatible types (integers in practice).
- A return statement must be of correct type, i.e., non-empty in int functions and empty in
void functions. You do however not need to check that an int function actually contains a return statement.
-
The last declaration in a program must be a function declaration of the form
void main(void)
Examples
A first example with syntax tree output.
Hint
- Start with the simple things, and expand the program as you go.
- Write documentation and source code in parallel.
Afterwards everything appears simple or forgotten.
- There is no one way to solve the problem.
- Discuss the exercise with your partner and with other students,
perhaps on the newsgroup.
- Start early. This takes time.
- Start early. This takes time.