Work Note 1, DM516, Spring 2012
Lecture January 30
-
Introduction to the course.
-
Overview of a compiler.
-
Lexical Analysis (scanning).
Background material: Appel Chapter 1 and 2, Flex-documentation.
With regards to literature and material on flex, see the
literature page.
The tool flex is used in combination with the programming
language C. If you have not programmed in C before, then
it would be a good idea to read about it and try to write
a few small programs. References to material on C can be
found via the literature page.
Exercises January 31
-
If you do not know C, then read about it,
write some small programs, and ask questions at the
exercises, if there is anything you are in doubt of.
If you have diffulties with the problems below,
then pose your own programming problems. The most important
is to get started with the language.
In particular, it is important to look at addresses, structs, and pointers.
Pointers fill the role of references in languages such as Java
and Python, for instance, but in C, pointers are a datatype.
This gives extra possibilities as well as difficulties compared
with reference-based languages.
-
Implement the following primitive hash table with the operations
insert
, delete
, and lookup
.
The elements in the hash table are referred to as keys.
They are integers and they are
placed in an array. The size of the array must be a prime.
The hash function, which is used to decide where a given
key should be placed in the array, should be of the form
a * x mod "table size"
,
where a
is a different prime.
As a simplification compared with a normal hash table,
you can assume that no keys are placed in the same entry in the array.
The implementation should be made in ANSI-C
.
Use the compiler gcc
.
Make a few tests.
-
Implement binary search trees with the operations
insert
, delete
, and lookup
.
You do not have to implement any kind of rebalancing.
The implementation should be made in ANSI-C
.
Use the compiler gcc
.
Make a few tests.
-
Read about
make
and explain the fundamental principles
and features. You do not have to go into detail with any advanced
applications. As a start, read the entire introductory section
and the section on syntax. Then
familiarize yourself with the remaining content,
e.g., by reading the introduction to each chapter.
-
Students familiar with C, but who are not doing the bachelor
project in Compiler Construction, may find it more interesting
and (slightly more) challenging to program the first part of
the project
instead of the C-related exercises above.
However, this will not be covered in the exercise class.
With regards to literature and material on C
and
make
, see the
literature page.
Announcements
-
If you have changed your mind regarding doing your bachelor project
in Compiler Construction, or if you want it as a so-called individual study
activity (which does not exclude group work), then it is not necessarily
too late to sign up, depending on various issues. Contact me immediately.
Last modified: Fri Jan 20 14:59:50 CET 2012
Kim Skak Larsen
(kslarsen@imada.sdu.dk)