Note 1, DM546, fall 2019

Lecture February 5

• Introduction to the course.
• Overview of a compiler.
• Lexical Analysis (scanning).

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 much 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 February 7

• Review how to write programs in C by writing some small programs again, and ask questions at the exercises, if there is anything you are in doubt of. If you have difficulties with the problems below, then pose your own programming problems. The most important is to get going with the language again. 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.