KOI: Lab 1

Getting started. Debugging. The "2.9" program. Compiler phases. Recursion.

Obs! Innan man får lämna in eller redovisa uppgifter i den här kursen ska man fylla i en särskild fusk-enkät!

Part A: Getting friendly with your development environment

The purpose of this exercise is to try out the compiler and debugger that you are using, especially for those of you who haven't used it before. If you haven't, take some time to get familiar with the system!

If you are using Visual Studio, you might want to look at some instructions for Visual Studio 2008.

Fix this large, meaningless program that doesn't work:

On a Linux or Unix system, the file debug-exercise.tar.gz can be unpacked using the command tar xvzf debug-exercise.tar.gz.

Use a debugger to find out where the program crashes, and why. It's a rather large and intentionally obscure program, so it's probably hard to find the problem without a debugger.

Fix the problem and recompile the program, so it can execute without crashing. It's sufficient just to comment out lines that don't work.

Discuss:

  1. Where was the problem?
  2. Why did the program crash?
  3. What did you do to fix the problem?

Part B: The simple compiler from chapter 2

The purpose of this exercise is to get a bit familiar with a simple compiler from the (old) course book. In a later exercise, we will modify it.

Compile and try out these two programs from the (old) course book:

Both programs translate from infix to postfix notation. They are text-only programs, which read text from the standard input (usually the keyboard) and write text to the standard output (usually a window on the screen), but other than that it is a part of the exercise to find out how to use them, and what input they expect.

Discuss:

  1. Which of the phases and other parts of a compiler are present in the 2.9 program?
  2. How are they implemented?
  3. Which are missing?
  4. If you were to modify the 2.9 program so it actually calculates the values of the expressions, and not just prints out postfix code, how would you do that? (Don't actually do it yet, just discuss how it can be done.)

Part C: Recursive and not recursive

In C, a function that adds two integers could be written as a function, or as a preprocessor macro:
int plus(int x, int y) {
  return x + y;
}

#define PLUS(x, y) ((x) + (y))
Write a function in C that computes n! by calling itself recursively. To save you some work, I've written it for you:
int factorial(int n) {
  if (n == 0)
    return 1;
  else
    return n * factorial(n - 1);
}
Now, try to do the same, but with a preprocessor macro. (Hint: instead of an if statement, you'll have to use the ?: operator. Read more in Wikipedia.) Will this macro work? Why, or why not?

Later in the course, you will come into contact with context-free grammars (which are recursive) and regular expressions (which are not). In that sense (but only in that sense!) context-free grammars are similar to C functions, and regular expressions are similar to C macros.

Some hints about the C preprocessor:

C file Preprocessing result
#define FOO 4711
i = FOO;

i = 4711;
#define TIMES(x, y) x * y
i = TIMES(7, 4);
i = TIMES(7, 2 + 2);
i = TIMES(++, {);

i = 7 * 4;
i = 7 * 2 + 2;
i = ++ * {;
#define SQR(n) n*n
#define CUBE(n) n*SQR(n)
i = CUBE(3);


i = 3*3*3;

Det kan vara upplysande att titta på resultatet av preprocessningen:

Discuss:

  1. Does the macro work?
  2. Why, or why not?
  3. If it doesn't work: Explain how the C preprocessor would have to be modified for the macro to work!

Report

Show your results and discuss them with the teacher,
or,
send an e-mail to the teacher with your factorial macro from part B, and with short answers to all the discussion questions on this page. (There are ten of them.) If you use attachments, send them as PDF and not Word.

Even if you don't send a report by e-mail, we advise that you write down your answers, to facilitate communication and for your own later use.


Thomas Padron-McCarthy (thomas.padron-mccarthy@oru.se) August 28, 2015