We will go on maintaining this page, but you will have to get started
on the work ASAP ZULU. We will broadcast all changes on our mailing list
mailto:i125@ii.uib.no.
If you are not on the list, send a message to
mailto:i125-request@ii.uib.no
with the command `subscribe' in the body of the message.
Goal
You are going to make a 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.
You are to do the exercise in groups of two.
(If there is an odd number of students, you should ask us. We accept
one, but only one group of three.)
Deadline
You have to hand in your answers no later than Friday 26th Oct 2001
at 10:15 am.
You may hand in to lecturer Jean Blair at the lecture, or in advance
to group leader Ole Kåre Endresen.
Contents
The answers handed in must include:
- Print of the source code.
- Print of documentation
-
Path to a directory on the departemnet system, where we can find all
the classes we need to test your program.
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 below).
Feilrapportering
-
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).
-
All programs must have a main function which takes no parameters
and returns int.
Examples
A first example with syntax tree output.
Fibonacci
Two programs computing Fibonacci numbers:
-
#nor# Rekursivt:
#eng# Recursive:
fibrec.c-
-
#nor# Med tabellar:
#eng# With arrays:
fibarr.c-
Documentation
- Describe the structure of the program.
-
Emphasise the parts requiring special consideration or where you had
to make priorities.
-
Avoid repeating descriptions, even when your code is repeated.
-
Do not include general text about program analysis and restrict
yourselves to your own code.
-
Keep the documentation short. It is supposed to be easier
reading than the source code is.
-
If you use several classes, each of them must be described, and you
have to tell how they are supposed to interact.
-
You may use UML to describe part of the system if you desire.
-
Make a running example where you describe how analysis and type checking
is performed in real, on a simple sample of source code
(perhaps with type mismatch).
Include the source code which is used in this example.
(If you plan the example ahead of time, it may help you in the
implementation of the program.)
-
The running sample may very well be used to illustrate the
construction of the program.
-
Make a print of a test run for your running example.
You may want to use the script command to make this.
(You find documentation with
man script.)
You may add more examples.
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.
- Start early. This takes time.
- Do not wait till the topics are covered in lecture, lest you lose
time and fail to meet the deadline.
- There is no one way to solve the problem.
- Discuss the exercise with your partner and with other students,
perhaps on the newsgroup.
|