KOI: Lab 1

Part A: Getting friendly with your development environment

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:

• The source code for a 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, and how did you find that reason?
3. What did you do to fix the problem?

Part B: The simple compiler from chapter 2

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

• The source code for the program in section 2.5 of ASU-86, the old course book.
• The source code for the very simple compiler in section 2.9 of ASU-86, 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.

If the function strdup is missing in your programming environment, you can use this alternative:

static char *my_strdup(const char *original) {
    char *copy = malloc(strlen(original) + 1);
    strcpy(copy, original);
    return copy;
}

Discuss:

4. Which of the phases and other parts of a compiler are present in the 2.9 program?
5. How are they implemented?
6. Which are missing?
7. 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

int plus(int x, int y) {
  return x + y;
}

#define PLUS(x, y) ((x) + (y))

int factorial(int n) {
  if (n == 0)
    return 1;
  else
    return n * factorial(n - 1);
}

If you call this function in your program, for example as factorial(3), it will return the value 6. There will be a total of four activations of this function: first your own call with the value 3, then it calls itself with the value 2, then it calls itself again with the value 1, and finally it calls itself again with the value 0. Since the variable n has the value 0, the condition in the if statement is true, and the recursion ends.

Now, try to do the same, but with a preprocessor macro. Instead of an if statement, you'll need to use the ?: operator, which has this syntax:
condition-expression ? expression-if-true : expression-if-false
For example, 2<3?4+5:6+7 will evaluate to 9. You can 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:

#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 SQUARE(n) n*n
#define CUBE(n) n*SQUARE(n)
i = CUBE(3);

i = 3*3*3;

It might be enlightening to look at the results of the preprocessing:

• In gcc you can use the -E flag.
• In Visual Studio 2012, you could go to PROJECT -> project name Properties... -> Configuration Properties -> C/C++ -> Preprocessor -> Generate Preprocessed File and change Preprocess to a File from No to Yes (/P). Click OK. Build the project, and ignore the error message that the object file cannot be opened. Now a file has been created with the preprocessed output. It has the extension .i and is located in the Debug subdirectory of the project directory. (In Visual Studio you have to select All Files (*.*) to see it in the file picker.)

Discuss:

8. Show your factorial macro. Does it work?
9. Why, or why not?
10. If it doesn't work: Explain how the C preprocessor would have to be modified for the macro to work!

Report

If you send an e-mail with a file, please use a descriptive subject line in the e-mail, and call the file something along the lines of Firstname-Lastname-compilers-1.pdf. The teacher will usually teach several courses at the same time, with several assignments each, and it can be confusing if every report sent in by the students is called Assignment.pdf.

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.