Teaching‎ > ‎CS210 Fall 2009 TF‎ > ‎

2009-10-14

posted Oct 17, 2009, 10:19 AM by Likai Liu   [ updated Oct 21, 2009, 10:26 AM ]
Transforming high-level structured control flow into either conditional or unconditional jump in C, in a form that is closer to how assembly language does control flow.
  • In C, we have goto for unconditional jump. The goto targets are labels, which is an identifier at the beginning of a line followed by a colon.
     the_label:
    The goto statement can jump below,  or jump above,
      /* do something... */
    
      goto label_below;
    
      /* this code is skipped... */
    
     label_below:
      /* continue... */
     
     label_above:
    
      /* do something... */
    
      goto label_above;
  • Conditional jump in C is simulated by an if statement with only a goto in the then-clause.
      if (cond)
        goto label;
  • Structured if's can be translated to conditional and unconditional jump like this.
    Original  Translated
      if (cond) {
        /* then-statement */
      } else {
        /* else-statement */
      }
      /* ... */
     
      if (!cond) goto else_begin;
      /* then-statement */
      goto else_end;
    
     else_begin:
      /* else-statement */
    
     else_end:
      /* ... */
Translating loops:
  • While loop
    Original  translates into
    while (cond) {
      /* while-body */
    }
     
     loop_begin:
      if (!cond)
        goto loop_end;
    
      /* while-body */
    
      goto loop_begin;
     loop_end:
  • For loop like this:
    for (initialize; cond; update) {
      /* for-body */
    }
    is first translated into a while loop
    initialize;
    while (cond) {
      /* for-body */
      update;
    }
    Then it can be translated into goto like above.
Examples and exercises:
  • Fibonacci, using while loop (see fib.c below) and using goto (fib-goto.c below).
  • Factorial, using while loop (see factorial.c below). Exercise.
  • Prime factorization, using for loop (see prime-factor.c below). Exercise.
(Note that their original location in my home directory has been removed.)
ċ
factorial.c
(0k)
Likai Liu,
Oct 17, 2009, 10:41 AM
ċ
fib-goto.c
(0k)
Likai Liu,
Oct 17, 2009, 10:43 AM
ċ
fib.c
(0k)
Likai Liu,
Oct 17, 2009, 10:42 AM
ċ
prime-factor.c
(0k)
Likai Liu,
Oct 17, 2009, 10:43 AM
Comments