CMSC 350b: Compiler Design
Instructor: David Wonnacott
Semester & Year: Spring 2014
Schedule: Lecture 10:00-11:30 T/Th in KINSC H108;
Scheduled Labs Tuesday either 11:30-12:15 or 2:30-3:15 in KINSC H110
NOTE: If there are more than 18 students in the class,
we'll either expand to two one-hour labs,
or (better yet) add a third 45-minute section Tuesday afternoon or on Wednesday.
Lab attendance is required for students who have not submitted the current lab project.
Concurrent enrollment in this and two other CMSC lab courses requires permission of the instructor.
- The CS 350 S14 Google Docs folder
- The course calendar on Google Calendar
- Moodle (requires Bi-Co login)
- For learning to use Regular Expressions,
we'll explore some online tools to see if they give the same results as flex with faster feedback.
Note that most tools are not suitable,
as they are based on systems that don't find the longest match by default,
and thus produce different results from flex.
(This site, and Ruby,
should work like flex,
at least according to Table 9-2 of
Flanagan and Matsumoto's "The Ruby Programming Language":
''By default, repetition is "greedy" --- as many occurrences as possible are matched.''...).
We have found a few differences that must be noted if one is to cut and paste between flex and Rubular:
If one follows those conventions, and sticks to just the constructors we've discussed in class and Appel's Figure 2.1
(literal characters, ., special characters such as \n, \t, \f, spaces preceded by \, character classes in [ ], and regular expressions built up from concatenation, |, *, +, and ?)
then it should be possible to copy/paste expressions between Rubular and flex and get the same result.
If you wish, you may experiment with the full set of regular expression constructors
listed in the flex manual,
but I've not checked to see which ones are allowed in Rubular and whether they mean the same things.
- Use only \, not ", to quote characters that have special meanings (Rubular does not accept " as a way of removing special meanings)
- Put a \ in front of each / (Rubular treats / as the end of the RegEx, and thus would not accept some things flex allows)
- Put a \ in front of each space (flex treats a space as the end of the RegEx, and thus would not accept some things Rubular allows)
(might work; succeeds for my simple test of
matching the regex (y*|x)*x* to the input xyx).
- (Firas Dib's otherwise-excellent regex101.com site
seems to have systems that don't always make the longest match;
Description: An introduction to compiler design. Students undertake
a semester-long laboratory project, building a compiler to turn Andrew
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
In so doing,
it also serves as a vehicle for several advanced topics in the design, analysis, and use of
algorithms and data structures:
- Lexical analysis
- Syntax analysis
- Syntax-directed translation
- Type checking and other static analysis
- Run-time environments
- Code generation
- Program analysis and optimization (in lecture but not lab projects)
- 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).
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 beyond the "basic" level,
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 up to 3 days
late just due
to difficulty scheduling work (please notify me in advance if you want
to take advantage of this last rule).
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.
The lab projects are undergoing substantial revision for 2014,
so see the information in the
CS 350 S14 Google Docs folder.
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-homeworks will be assigned regularly to review or prepare for a given class.
The mini-homework assigments will be posted on Moodle
as they are relevant.
- 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.