Quiz 27: Other Control Structures

If you came so far your current code is already worth 20 points. You can increase your score by implementing more control structures. The fun you will have will be priceless.

Other Control Structures

Other control structures like do-while loops, for loops and if statements can be realized very similarly. Here the grammar:

For all loops it is required that the loop body is a compound statement. The then-branch of an if statement is also required to be a compound statement. The else-branch of an if-statement can be either an if statement or a compound statement. This avoids the dangling else problem (See Session 10, Page 2).

Parsing the statements can be done by following the usual rules. For each control structure the code generation can be implemented once we agreed on a flow chart representation for it (if there are multiple options).

Code Generation: Do-While Loop (Worth: 20 Points)

We actually do not have much to choose here:

Test your implementation with the program below. It reads in an unsigned integer and should print its decimal digits in reverse order:

1
2
3
4
5

$> x;
do {
    $< x % 10;
    x = x / 10;
} while (x != 0);

Here an example:

theon$ echo "123456789" | ./dowhile
9
8
7
6
5
4
3
2
1
theon$ 

Code Generation: For Loop (Worth: 20 Points)

The control flow for an for loop statement of the form

1
2
3

for (initial-clause; condition; update) {
    loop-body;
}

can be realized as follows:

Note that all expressions in the for loop are optional. Hence

1
2

for (;;) {
}

is legal by the grammar. It is also semantically legal. It is a busy loop that never terminates. You will see that in the implementation the behavior that an empty expression for the condition is treated as true comes for free. Support of empty expressions for the condition makes more sense when after we have added break statements in the next session.

Test your implementation with the program below. It computes the factorial of a non-negative integer using a for loop.

1
2
3
4
5
6

$> n;
res = 1;
for (i = 1; i <= n; i = i + 1) {
    res = res * i;
}
$< res;

Here an example:

theon$ echo "5" | ./factorial_for
120
theon$ 

Code Generation: If Statement (Worth: 40 Points)

The control flow for an if statement with an else-branch can be realized as follows:

Technically a missing else-branch could be treated like an empty else-branch. This means after the then-branch we would have an unconditional jump that jumps forward by one instruction. This is not elegant and certainly not how we do things in Ulm. An if statement without else-branch should be realized as follows:

Tired of computing the factorial? Let's compute the greatest common divisor. Of course this could be done with this program:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

$> a;
$> b;

while (b) {
    t = b;
    b = a % b;
    a = t;
}

$< a;

Here an example:

theon$ time echo "2 100001" | ./gcd_mod
1
theon$ 

But this would not really test the if statement. It is also too fast in case \(a\) is much larger than \(b\). We need some chill out test. So let's use this program:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

$> a;
$> b;

while (a != b) {
    if (a > b) {
        a = a - b;
    } else {
        b = b - a;
    }
}

$< a;

Here an example:

theon$ time echo "2 100001" | ./gcd_sub
1

real    0m0.441s
user    0m0.434s
sys     0m0.010s
theon$ 

Of course we also should test an if statement with an else-if. Use this:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

$> x;

if (x % 2) {
    x = 1;
} else if (x > 5) {
    x = 2;
} else {
    x = 3;
}

$< x;

Here an example:

theon$ echo "3" | ./elseif
1
theon$ echo "6" | ./elseif
2
theon$ echo "4" | ./elseif
3
theon$ 

Of course you should try to test even cooler stuff. For example, nesting all kind of control structures. Even cooler test can be done once we have operators for a logical not, logical or and logical and ;-)

How to Submit

You have to submit a tarball quiz27.tgz of your project. In your project directory do the following:

• Run make clean

• Create the tarball with

  1	tar cfvz quiz27.tgz *

• On theon you can submit the tarball with submit hpc quiz27 quiz27.tgz