CSE 401 Autumn 2001 (Henry)

One of the challenges of the CSE401 programming project is to learn how to work with another person on a programming project.

• We want you to show us that you understand the meaning and the intent of the extensions.
• We want you to think about the corner cases of the language, before you start implementing the compiler.
• We want you to get some experience writing test cases.
• You will have a set of test cases that you can use for evaluating your compiler as you write it.

You should write three separate programs (separate .0 files) for each extension:

• The first program should be rather short, and should do a basic test of the extension, using only the base PL/0 language, if at all possible.
• The second program should be longer, and should use the other extensions only as needed for clarity of program structure, or to exercise features in combinations that interact with one another.
• The third program should exercise the compiler's ability to detect semantic errors; see below for more details.

You should use the comment extension in all programs so you can document you test cases. (It is unlikely that you're implementation of comments will be seriously broken.)

These programs should be complete and self standing. Assuming a correct compiler and run time system, the first two programs should compile without any errors of any kind, and should then run to completion.

You do NOT need to test that the base language and base implementation works as it should. Thus, for example, you can assume that integer arithmetic correctly implements 32 bit 2's complement arithmetic, that procedure calling works, that the basic control flow statements work, and so on.

When your test programs run, they should print out a sequence of values that makes it easy for you to tell if they have worked correctly. This is to say that the programs should be self diagnosing, and should produce some output that obviously indicates success or failure. More output is better when it comes to diagnosing possible failures.

The third program should scan and parse correctly, but should exercise the compiler's ability to detect semantic errors. It is unlikely that you'll ever be able to fully compile this program unless you put some kind of rudimentary semantic error recovery into the compiler.

Clearly, you will not yet be able to compile any of your test programs on your base PL/0 compiler, much less run the results! As the quarter progresses and you make your extensions, you should be able to scan, then parse, then attribute, and finally execute your programs.

We will provide a reference compiler (executable only!) for the extended language. You can use this reference to compile your programs, and as a basis for regression testing. We will provide some mechanisms for compiling and building SPIM executables from your test cases. This will be an implementation that the TA will write. It is likely that the reference implementation will be (initially) incorrect: we'll use your test cases to help us clean up our reference implementation!

Here are some things to consider when writing programs to test compilers:

• Test that a feature works by itself for common case(s).
• Test that a feature works when it embeds itself.
• Test that a feature works in combination with other features.
• Test for interesting boundary cases: 0 of something, 1 of something, all of something, boundaries near or on the maximum or minimums allowed in the specification.

It is quite possible to go overboard on this assignment. Remember that we'll try to design and implement the compiler so that orthogonal features of the language are implemented correctly in such a way that a feature's correctness has no impact on other feature's correctness. This minimizes the number of interactions you must consider.

Exercise some care in your test cases, walking the fine line between too simple and too complicated. Simple test cases don't find the deep bugs; complicated test cases are too hard to debug, and it is never clear if the test program is wrong, or if the compiler itself is wrong. Compiler writers spend an inordinate amount of time finding bugs in test cases, rather than bugs in the compiler.

The complexity of test cases should probably reflect the complexity of the language feature. You can probably test comments in only several lines; if then else in about 20 lines. Intervals, which introduce a new algebraic domain, new run time data structures, and more, are likely to take 100 or more lines to test thoroughly. Catch and throw require runtime support that deviates from the existing run time system may also take 100 or more lines to test thoroughly.

Overall, I expect that you will have to write between 300 and 400 lines of PL/0 to provide adequate coverage. You may find that you will want to extend your test cases as the quarter progresses, either in response to your understanding of how the compiler works, or in response to bugs you (or the teaching staff) may find.

You should name your test programs using this file name scheme: extension.N.0, where extension is the name of the extension, taken from this set:

  comment
  ite
  andor
  boolean
  interval
  function
  return
  catch

Take especial care in constructing test cases for the operators on intervals. Multiply and divide can be tricky, especially in the presence of negative numbers.

We will provide details via email or on the "details" part of the Web page, on (a) how to turn in this mass of programs; (b) how to run diff and other unix tools for regression testing. Later, we will show how to use some kinds of rudimentary coverage analysis tools to see how thorough your test cases are on your completed compiler.

Finally, remember that testing only shows the presence of bugs, and never the absence.