image University of Washington Computer Science & Engineering
  CSE 401Sp '04:  Assignment #1, Due Wednesday, 4/7/02
  CSE Home   About Us    Search    Contact Info 

Individual homework

#1 - #3 should be done and turned in individually, not as a group.

  1. ASU 3.7abch. ("In order," or "in lexicographic order" means for example that "p" preceeds "r", with or without arbitrary intervening characters. You may not use the not operator except for the simple case where not(a, b, ..., c) means all single letters except the letters a, b, ... or c. You do not need to distinguish between upper- and lower-case letters.)

  2. ASU 3.16cd

  3. ASU 3.17 (for 3.16cd only) Be sure to use Algorithm 3.2.


If you have formed a group, the following may be done by your group; turn in only one solution per group.

To form a group, send email to our TAs giving the names and unix login of each group member. Max 3 persons per group (2 recommended).

In this part of the project you will be extending the description of the PL/0 lexical structure to include all the new language features described in the PL/0 Project Description, and making the associated changes to the scanner portions of the project code. The extensions will require the scanner to handle various new features including comments, some new punctuation tokens ([ and ]), and new reserved words such as bool, true and false, etc. See the PL/0 Project Description for full details.

[Note: don't use TRUE/FALSE as the token names for the Boolean constants in the SYMBOL enum in token.h; those names conflict with standard C #defines. Instead, I'd suggest TRUETOKEN/FALSETOKEN.]


  1. First, copy and build the base pl/0 compiler, using the directions here. Test it on the sample program here.

  2. Extend the PL/0 scanner to scan the extended language. Use the -T option to stop compiling after scanning. You will also likely be interested in the -t option that prints tokens as they are read, and perhaps the -c (print characters) and -l (print lines) options. In this and subsequent phases, you should extend the various print() methods as needed to support your extensions, both to facilitate your testing and ours.

    For all implementation projects, you will be graded on correctness of your implementation, on clarity and good design of your implementation, and on sufficiency of your test cases.

    See these pages for information on printing and electronically sumbitting your files to us. Please read the turnin instructions carefully, so that we get all the files we need and no other junk.

Optional, Extra Credit, Project Extension

It's spring, life's a breeze, you've got tons of time on your hands before graduation, and compilers are groovey, baby. So, if you'd like to dig into it more, a modest number of extra credit points and a significant number of techno-karma points are to be had by implementing a substantive addition to PL/0: add records (structs) to the language (a tiny step towards PL/OO). You/your group get to design the syntax and semantics, and carry through the implementation from scanner through code generation. Ideally, you will turn in various benchmark pieces of this in parallel with the regular assignments, e.g. scanning now, parsing next time, etc., but we can be a little flexible about the schedule. (You may also work on extensions individually if your partner(s) aren't interested in doing it. Please make this clear on your EC turnin so we know. Also note that version control becomes a slightly bigger deal in this case. Check out the facilities provided by RCS, CVS and similar tools to help with this, e.g. to merge your EC scanner code with your group's non-EC parser code.)

  1. What to do: start by designing your extensions. Give us written descriptions of the syntax and semantics that you intend to implement, at least at a level of detail comparable to the project description. Where possible, try to think ahead to the types of processing that will be required in later phases, such as the sorts of legality checks that you'll need, issues of scopes of names, parameter passing, storage allocation, etc. Document them briefly. Obviously, I don't expect you to be experts on all those things (until June 13th), but the point is that there are actually a fair number of choices to be made, and some of them will make your life much easier in the later phases, so it pays to try to anticipate the key issues.
  2. What not to do: (a) Don't be overly ambitious about what you decide to implement. E.g., records with overloaded polymorphic multiple inheritance, while tempting, is perhaps best left to students at schools on the semester system. (b) Do NOT let work on the extensions interfere with finishing the basic course requirements on time. I'd suggest you not even think about the extensions until you've turned in a clean, debugged version of the basic code, with test cases.
  3. What to turn in: For this first turnin, give us documentation for your planned extensions (see 1 above), together with code and test cases for scanning. Next time, you give us your parsing code, and test cases, etc. Also, if you later decide to change any of your initial design specs, tell us that, and sketch why ("We now realize that doing X will be way easier than Y because it nicely fits in with Z" or whatever). You may turn in your documentation on paper, but especially for providing updated information in context with your turnin of future phases, it might be easier to write your documentation online, too. A plain text file, called Phase1Documentation.txt, Phase2Documentation.txt, etc. is recommended. (We grade on unix; Word files, e.g., are a pain.)
  4. EC turnin is separate: You should first turn in your compiler implementing the required functionality as described in the Project section above. Then, after you have implemented the EC additions and possibly added the Phase1Documentation.txt file, turn in the compiler again by following same instructions but running the following turnin command instead:
         turnin -c cse401 -p scannerEC pl0
    It differs by the `-p scannerEC' option which will be announced for each subsequent project part.
The TAs and I will be happy to talk about any of these design/implementation issues, so you don't need to dive in blind.

CSE logo Computer Science & Engineering
University of Washington
Box 352350
Seattle, WA  98195-2350
(206) 543-1695 voice, (206) 543-2969 FAX
[comments to cse401-webmaster at]