Stack Tracking

The goal of this lab is to practice predicting the behavior of programs using the stack model of computation and understanding how C statements expressions evaluate through operator precedence and associativity.

Expression Exercises

Use C's rules of operator precedence and associativity to fully parenthesize the following expressions.

a * b - c * d + e
a / b % c / d
- a - b + c - + d
i += j += k

Acknowledgment: King, K.N. Exercises 4.10 and 4.14.

Program Exercises

For each of the following programs, give the state of the stack and what has been printed to the console at each of the commented program points (e.g., write five stack diagrams for program 1 below). Make sure to reproduce your diagrams exactly for each program state!

Note that it's common to abbreviate the program counter as simply PC. You may set the program counter to be one line after the comment.

(Hint: the labels are in order of where execution flows through the program!)

Program Exercise 1

void                //  1
f1 (void) {         //  2
    printf ("0");   //  3
    // Point (B, D) //  4
    return;         //  5
}                   //  6
                    //  7
void                //  8
f2 (void) {         //  9
    printf ("1");   // 10
    // Point (C)    // 11
    f1();           // 12
    printf ("2");   // 13
    return;         // 14
}                   // 15
                    // 16
int                 // 17
main (void) {       // 18
    // Point (A)    // 19
    printf ("3");   // 20
    f1();           // 21
    f2();           // 22
    // Point (E)    // 23
    return 0;       // 24
}                   // 25

Program Exercise 2

void                    //  1
f1 (void) {             //  2
    printf ("0");       //  3
    // Points (A, C, E) //  4
    return;             //  5
}                       //  6
                        //  7
void                    //  8
f2 (void) {             //  9
    // Points (B, D)    // 10
    printf ("1");       // 11
    f1();               // 12
    return;             // 13
}                       // 14
                        // 15
void                    // 16
f3 (void) {             // 17
    f2();               // 18
    printf ("2");       // 19
    return;             // 20
}                       // 21
                        // 22
int                     // 23
main (void) {           // 24
    printf ("3");       // 25
    f1();               // 26
    f2();               // 27
    f3();               // 28
    // Point (F)        // 29
    return 0;           // 30
}                       // 31

For those with extra time

The previous lab demonstrated this particularly atrocious program segment:

int a = 2;
int b = 4;

a /= (b++) % (++a);

printf("%d\n",a);

1. Fully parenthesize the assignment statement.
2. Combine the stack and substitution models by tracking the value of all the local variables as each subexpression is evaluated. Clearly identify which subexpression is evaluated at each step.
3. If you have not already, verify your final answer is correct by compiling and running this program segment. Note that you may need to compile directly using clang, rather than with make.