CMSC 350b: Compiler Design
Instructor: David Wonnacott
Semester & Year: Spring 2008
Schedule: Lecture 1:00-2:30 T/Th in KINSC H110;
Lab 2:00-4:00 Friday, also in KINSC H110
Texts:
Prerequisites: CMSC 245
Description: An introduction to compiler design. Students undertake
a semester-long laboratory project, building a compiler to turn Andrew
Appel's "Tiger"
language into an equivalent HERA
assembly language program that can then be executed on the HERA-C simulator
or assembled using the Hassem assembler and run on (simulated) HERA microprocessors
created in CMSC 240.
Lectures combine practical topics such as the use of compiler construction tools
and techniques with more abstract discussions of the algorithms upon which these
tools are based and discussions of techniques that are beyond the scope of our
one-semester lab project.
This course covers the classic steps of compilation, specifically
- Lexical analysis
- Syntax analysis
- Syntax-directed translation
- Type checking and other static analysis
- Run-time environments
- Code generation
- Program optimization (if time permits)
and, in so doing,
serves as a vehicle for several advanced topics in the design, analysis, and use of
algorithms and data structures:
- The interplay between theoretical foundations and practical results
(in terms of matching patterns during lexical and grammar analyses).
- The relative strengths of the pure functional, object-oriented, and imperative paradigms
(in terms of tree traversals during type checking and later phases of compilation).
- The importance of techniques for managing larger software projects,
including code clarity, documentation, attention to invariants
(in terms of a variety of practical issues during the labs).
A course syllabus from 2006 is available in
html or
PDF formats.
It is correct for 2008 except that it says 2006 and the "review questions"
will become "mini-homework".
Requirements:
Midterm and Final exam, Lab projects, "mini-homework" assignments and other class participation.
Late Submission of Projects:
The lab projects for this course are cumulative, and getting behind on
one can cause a "cascade of lateness" that can leave an insurmountable
amount of work for the end of the semester.
Thus, lab work must be submitted on time to recieve credit,
except in case of illness or other emergency qualifying for a note
from a dean,
or one instance in which a lab can be submitted late just due
to difficulty scheduling work (please notify me in advance if you want
to take advantage of this last rule).
Collaboration:
You are encouraged to discuss the lecture material and the weekly labs
and "mini-homework" problems with other students, subject to the following
restriction: for labs, the only "product" of your discussion should be your
memory of it - you may not write up solutions together, or exchange
written work or computer files.
Unlimited collaboration is allowed on "mini-homework" assignments,
which may be written up jointly.
Collaboration is not allowed on exams.
Labs:
The above labs make use of C++ files designed to work with Appel's textbook. Anyone
outside of Haverford who is interested in these files, or planning to use Appel's
book with C++, is encouraged to contact davew.
Mini-homework assignments:
Mini-homeworks will be assigned regularly to review or prepare for a given class.
- Each will include a time limit after which no work is required.
- Each is due at the start of class on the given date.
- Any amount of collaboration is allowed.
- Grading will be strictly "binary":
Full credit will be given for a complete answer (correct or not)
or for spending the full time limit attempting the work
(alone or as part of a group).
- If everyone gets it right, we just get to move on faster to new material.
The mini-homework assigments are:
- For 1/24,
write regular expressions for Tiger lexical scanning.
- For 1/31,
convert a regular expression into an N.F.A. and run it on three input strings.
- For 2/05,
convert some N.F.A.'s into D.F.A.'s.
- For 2/12,
run the LR parsing algorithm on some inputs,
and also
run the LR(0) and SLR parse-table-building algorithms.
- For the final exam practice, draw the graphs produced by the the LR(1) and LALR(1)
parse-table-building algorithms for Grammar 3.5 from the textbook.
Check your answer against Table 3.33 --- Do you get the same pattern of conflicts?
- For 2/21, ,
label a parse tree with attributes and define some attributes.
- For 2/26,
give the iteration space sets and data flow arcs for some programs.
- For 4/03,
run the Sethi-Ullman algorithm by hand on simple examples.
- For 4/08,
run the Sethi-Ullman algorithm by hand on a slightly more complicated example.
- For 4/10,
generate code for if's and comparisons, and produce basic blocks.
- For 4/15,
produce basic blocks and re-build a new set of traces.
- For 4/22,
Create some "tree pattern" tiles for HERA and apply "maximal munch" and dynamic-programming-based instruction selection.
- For 4/24, Question 10.1 Parts (a) and (b) from the textbook (20 minutes).
- For 4/25, Question 10.1 Part (c), and color it using the heuristic from the textbook (20 minutes).
