MCS-388 Lab 4: Control Flow and Scoping (Spring 2002)

Due: April 22, 2002




Some notes on the new language features

x = y > z;
which assigns x the value 1 or 0, or
print_int((x > y) + (z > w));
which prints one of 0, 1, or 2.

The syntax of while and if statements should be as in C (and C++ and Java). For example, the controlling expression in each case must be parenthesized, and there is no keyword (like then or do) between the parenthesized expression and the following statement. Remember that any statement can be used as the body of a loop, or as an alternative in an if statement: there is no requirement of curly braces. They have nothing to do with the while or if statement, and are only present if a compound statement is used, as part of the compound statement. For example, the following three while loops are all legal:

while(x >= 10)


  int d = x % 10;
  x = x / 10;


  int x;          // declaration 1
  x = 3;          // reference (a)
  while(x){       // reference (b)
    print_int(x); // reference (f)
    print_int(x); // reference (g)
    int x = 2;    // declaration 3
  print_int(x);   // reference (h)

Quality expectations for generated code

Ideally, your compiler should include the optimizations from the prior lab. However, if you were unsuccesful with these in the prior lab, adding them now should be a lower priority than adding the new features.

If you do have the new features and the prior optimizations working, it would be desirable to also turn relational operators around when appropriate to be able to take advantage of immediate operands. For example, if the source code contains 3>x, it would be better to turn this around to x<3 so that you can generate an instruction like slt $t0, $s0, 3.

For while loops, it is preferable to generate code like this:

   jump to label1
   code for the body goes here
   code for the test goes here
   branch if true to label2
rather than:
   code for the test goes here
   branch if false to label2
   code for the body goes here
   jump to label1

Normally if statements translate into something like

   code for the test goes here
   branch if false to label1
   code for the first alternative goes here
   jump to label2
   code for the "else" part (2nd alternative) goes here
However, when the if statement has no else part, or where the else part is sufficiently vacuous that it translates to an empty string of assembly code, it would be preferable not to generate the jump to label2, since it is a waste of time to jump to the next instruction.


Code to start from

Code from prior lab

Most students seem to have at least the general AST infrastructure from the prior lab more or less working, if not the optimizations. This should provide a sufficient base for the new lab since you can just omit the optimizations. For most of you it will therefore be preferable to continue building on that base, rather than throwing it out and starting over from code I supply. It would be nice to fix the problems I identified in my grading comments, though the new features are sufficiently de-coupled from many typical problem areas that failure to fix all the old problems won't necessarily cause any difficulty in doing the new stuff.

If any of you thinks your difficulties with the prior lab would put you at a disadvantage for doing the new lab, you are welcome to ask me for my code from the prior lab, to use as a starting point.

Sample ScopedIdentifier class

To help get you off on a good start with the scoping, I'm providing (linked onto the web version of this lab assignment) the interface documentation for my scoped version of the Identifier class. This class is available to you as compiled code in my JavaLib, if you choose not to build your own. It uses the "dictionary of stacks" approach we discussed in class. Note that this class is nearly, but not quite, compatible with the lab3 Identifier class, so I called it ScopedIdentifier rather than Identifier. This means that you will have to alter the other files to use ScopedIdentifier rather than Identifier. (Or you could write and use your own class.) The incompatibility is that the declare method now no longer allows you to register an arbitrary Object with the ScopedIdentifier, but instead only ones that implement the Declaration interface. This ensures that there is the leavingScope callback. The LocalInt class should now be changed to implement the Declaration interface; its leavingScope method would deallocate the Register back into the RegisterAllocator.

My intention is that call all the ScopedIdentifier class's method's during the parsing process, not during the AST's later code generation. This includes enterScope, exitScope, get, declare, getDeclaration and (when errors need reporting) toString. Of course, not all of these need to be literally called directly from parser.cup. It is OK if you want to call some of them indirectly, from something called from the parser. (As one example, you may well be calling the get method from the scanner rather than the parser -- but the parser calls the scanner.)


A constant-folding subtlety

Now that a program can contain code that is never executed, some subtleties arise with regard to division by zero. These issues shouldn't distract you from the main goals of the lab, but the perfectionists among you should care.


Worse yet, it turns out that SPIM (our MIPS simulator) doesn't recognize that some instructions aren't executed, and so it won't load in an assembly language program that has a division instruction with an immediate 0 operand. Thus you'll need to be careful not to generate such instructions. (You can use register $zero instead.)



Course web site:
Instructor: Max Hailperin <>