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

Due: April 19, 2006

Objective

You will extend your compiler to provide some important additions to the source language:

Of these, while and if statements introduce interesting control flow, for the first time allowing programs that do something other than continue in a straight-line path. Compound statements are important in conjunction with while and if statements, in order to allow a loop body (for example) to perform more than one action. Moreover, introducing compound statements gives us a natural context for variable scoping. The comparison operators are the only addition of no real substance: they are fundamentally similar to the arithmetic operators, and could equally well have been in the compiler the whole time. The only reason to add them now is that they become particularly handy to have now that we have loops and conditional statements.

Some notes on the new language features

We will follow the lead of C, rather than Java, in using integers to represent truth values, rather than having a separate boolean type. If the condition of a while or if evaluates to a non-zero value it counts as true, while a zero value counts as false. The comparison operations should all produce 1 for true and 0 for false; you can use the MIPS opcodes slt, sgt, sle, sge, seq, and sne. The comparison operators should be usable anywhere any other operator (e.g., +) could be used. So, for example, there is nothing wrong with
x = y > z;
which assigns x the value 1 or 0, or
printInt((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. 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; they form part of the compound statement. For example, the following three while loops are all legal:

while(x >= 10)
  x = x / 10;     // body is an assignment statement

while(x >= 10){   // body is a compound statement, which
  x = x / 10;     // happens to only have one statement in it
  }

while(x >= 10){   // body is a more general compound statement
  int d = x % 10;
  x = x / 10;
  printInt(d);
  }

Each brace-enclosed compound statement constitutes a new scope, nested inside the surrounding scope. It is legal to redeclare a variable that was declared in some outer, surrounding scope, but not legal to redeclare a variable in the exact same scope.

Symbol table

In the preceding lab you used a HashMap; now you'll want to use some class of your own creation that supports not only the put and get methods (or close analogs of them), but also methods for entering and exiting scopes. We already talked once in class about how this can be represented, and we can review this material during the lab preview day.

Shift/reduce conflicts

Our textbook mentions (p. 263) that YACC will resolve a shift/reduce conflict in favor of shifting and that this correctly resolves the dangling-else ambiguity that you are likely to encounter when you incorporate the two forms of if statements. The same is true for CUP, but only if you give an option telling it how many conflicts to expect. That is, in the build.xml file, you can change the action
    <cup srcfile="${cup}/Parser.cup" 
         destdir="${java}" 
         parser="Parser"
    />
to
    <cup srcfile="${cup}/Parser.cup" 
         destdir="${java}" 
         parser="Parser"
         expect="1"
    />
if your grammar has one shift/reduce conflict in it that can be correctly resolved in favor of shifting. You should make the corresponding change in the cup_dump target of the build.xml file as well if you decide to go this route.

There are at least two other ways you could deal with the dangling-else ambiguity. The easiest one is just to declare a precedence for the else terminal at the top of your CUP file. Then you won't need to modify the build.xml and yet CUP will still resolve the shift/reduce conflict in favor of shifting, much like it would for an expression such as 3+4*5. The other approach, conceptually clean but messy in practice, would be to write an unambiguous grammar in the first place, as shown on page 175 of the textbook.

Postlab

Write a lab report highlighting the differences from the code for your previous compiler. You should also describe the tests you ran and any problems uncovered.


Course web site: http://www.gac.edu/~max/courses/S2006/MCS-388/
Instructor: Max Hailperin <max@gustavus.edu>