![[UMN logo]](http://www.umn.edu/images/syssesqui.jpg)
Final Compiler Project Due: May 1, 2022, 11:59 p.m.
There will be no final exam in this course.
Online discussion using Piazza
New Information:
Posted April 16, 2023
Posted April 14, 2023
Posted April 12, 2023
Posted April 11, 2023
Posted April 4, 2023
Posted April 2, 2023
Posted Jan 16, 2023
Modern Compiler Implementation in ML, Andrew Appel, Cambridge University Press, ISBN 0521607647.
This book is available in online form through the University library; the link I have included will take you to it.
Appel's book is good for our course because it emphasizes all aspects of compiler implementation evenly and it will complement well a process of learning by constructing. However, it is a little incomplete in its coverage of classic issues such as parsing. You might want to look up a book such as
Compilers: Principles, Techniques and Tools, Aho, Lam, Sethi and Ullman, ISBN: 0-321-48681-1, Addison-Wesley Pressto learn more about these aspects. The core of this book has been around for many years, and I have used an earlier version in preparing relevant parts of my lecture slides. There is a copy of this book and an earlier version of it at the Walter Library, but it is only available in hard-copy form. Look on the web, though, you might be able to find PDF versions of it there.
There is a fair amount of programming involved in this course, most of it to be done in the Standard ML (SML) language. If you would like to have an ML programming reference in hand, you might consider consulting
Elements of ML Programming, J.D. Ullman.New copies of this book are rather pricey, especially in light of its limited long-term utility, but you can get used copies at places such as AbeBooks. Rather than trying to purchase such a copy, my suggestion would be to read Bob Harper's Introduction to Standard ML and Mads Tofte's Four Lectures on Standard ML. After you have assimilated the material in these tutorials, you should be ready to use the links to SML documentation at the end of this page to find out whatever you need to write your programs for this course.
You will need to have significant familiarity with programming and
with programming languages as such. This
course will require you to think flexibly about programming language
constructs---you need this before you can understand how to
translate them---and you will also have to write and debug a
reasonably large SML program. The background in programming languages
can be obtained at the University of Minnesota by taking CSCI 5106,
the programming languages course, and a number of undergraduate
courses could help you develop the skills needed for writing big
programs. Prior familiarity with SML will be useful, but you
should be fine if you have programmed a fair amount in some other
language, especially one that supports functional programming.
However, you should be interested in, and not overwhelmed by, the
prospect of building a big and reasonably complicated program in order
to fully enjoy this course. Most of the grade will be determined by
the compiler that you will build. For undergraduates taking this
course, the programming will be significantly more complex than
anything you would have seen in CSci 1133, CSci 1933 or CSci
3081W. This is not meant to deter you---many of the top students
over the years in this course have been undergraduates---but
rather to prepare you for the work ahead that, with the right mental
preparation, can be quite exciting.
You will have to do a fair amount of reading outside of
class. Specifically, you will have to look at manuals for tools for
constructing parsers and lexers that will only be discussed cursorily
in class. You can get help with these from the people involved with
teaching the course during office hours and through discussions on
Piazza. In
short, reasonable forms of help will be available throughout the
term. However, there is a basic theshhold that is needed to benefit
from all this: If you like to have everything explained
in detail in lectures before you undertake the assignments, then you
will have difficulty with this course. Please make this
determination at the very outset, using the first couple of
homeworks as a guide, so as to save agony or trauma in the middle of
the semester.
You would most likely want to
develop your programs on your own machines before testing on the CSE-IT cluster. To be able to do this, you
should set up Standard ML of NJ in that environment. This is easy to
do under ubuntu: essentially you must download the smlnj, ml-lex
and ml-yacc packages. There are instructions on the
Standard ML of New Jersey page for
setting the system up on Windows and MacOS platforms in addition to
Linux ones. Please try to do this as soon as possible, within the
first week of classes, and ask questions on Piazza if you encounter
any problems. Likewise, if you encountered problems but were able to
resolve them, you should think of posting something on Piazza to
help your classmates.
There will be an in-class midterm in the course that will count for
20% of the grade. This midterm will take place on March 15, 2023,
i.e., the week after the Spring Break. The exam will be an open book
one, but you are restricted to consulting only the text book and a
clean copy, i.e. a copy with no annotations, of the lecture slides
used in the course.
The last 10% of the grade is reserved for class participation. This
participation may occur through Piazza discussions, questions posed
or responses provided in class, etc. The message here is that I would
like to see you all attending class regularly and participating
enthusiastically in the the material we study; if this actually
happens, you can count on the full 10 points in this category.
Certain topics, such as those
related to parsing and programming tools for constructing parsers,
will be covered somewhat cursorily in lectures. In this case, the onus
will be on you to fill in the missing parts. The relevant sources will
usually be mentioned in class and you can also ask for these through
Piazza. The knowledge you obtain from such readings will usually be
relevant to the programming assignments and may also be
needed for the exams.
Grades for programming assignments will usually be determined by
a combination of the completeness of coverage as determined by
(published and secret) test cases, the clarity and elegance
of the code and how well you have structured the presentation
of the material. The last is not a whimsical matter; an
important component of any large piece of software (such as a
compiler) is structuring that facilitates modifiability and
documentation that supports understanding. There will be partial
credit for homeworks but to obtain any of this we have to be able to
understand your code in an essential way and we will also typically
expect you to have been able to at least compile the program and run
it successfully on some of the test cases.
Deadlines will be announced for each homework at the time the homework
is posted. These deadlines are meant to be adhered to strictly, with
one proviso. Each of you will have 5 grace days off the
bat that you may distribute across the homework submissions (but not the final project) in
the way you need to. So long as you have not exhausted this allotment,
you may turn in a homework late, no questions asked. However, once you
have exhausted this allotment, you will not get credit for the work
and you may also not receive feedback on it. However, you must still
complete the work because the final project will be broken without
it. Note also that I may give you some credit for completing earlier
parts when I look at your overall project in May.
While collaboration is both natural and useful, carrying it too far
can interfere with learning as well as with the assessment of what has
been learnt. Any work that you turn in for credit must
be indicative of your own effort and understanding. To be even more
specific, each of you is expected to write the
programs that you turn in completely independently. In particular,
you must not share or copy any of this code. Violations of these
requirements are usually easy to detect---for example, electronic
tools are available for determining similarities between
programs and these tools are highly effective for their purpose.
If such violations are encountered, they will be dealt with as a
breach of the academic honesty guidelines for this course. Penalties
for such transgressions will range, at my discretion, from no credit
for the assignment in question to a failing grade in the course. To
ensure fairness and in keeping with University requirements,
suspected breaches of the policy will be reported to
the Office of Community
Standards. At a personal level, this kind of dishonesty interferes
seriously with intellectual development and it also sours
relationships. I sincerely hope, therefore, that we will not have to
get into a realm where we have to deal with such issues.
A comment on a related point. For those of you who seem to be
understanding the material in the course well and are enthused by
this, I would like to encourage your being helpful to
others. However, please be aware that, if taken beyond a reasonable
point, such help can be detrimental to someone else's learning.
One particular situation
to be aware of is when you respond to queries on the discussion fora.
Give thought to whether or not you will be letting out solutions to
problems that your colleagues should have a chance to think through
for themselves. The instructional staff will try to monitor this aspect
towards guiding you in deciding when responses
have the danger of crossing the boundary of legitimacy, but, for the
situation to be manageable, they will need you to be cooperative and
responsible as well.
Note: The department has a default set of policies regarding
academic conduct that you will
find here. These policies are effective for
anything that is not explicitly covered above.
Course Description
The translation of high-level directives into
machine-executable instructions is a spectacular success of applied
computer science. This course teaches formal and systematic techniques
for syntax-directed translation. Topics include lexical analysis,
parsing, abstract syntax, semantic analysis and elements of code
generation. A compiler will be built for a small Algol-like
block-structured programming language called Tiger. The
compiler will be implemented in the language SML.
Syllabus
We will cover the first part of the book, i.e. Chapters
1-12. We will also build a compiler for the Tiger language that is
described in the book as we go along.
Course Prerequisites
The formal prerequisites for this course are CSci 2021 and CSci 5106.
Computing Resources
All of you must have accounts on the CSE-IT cluster and should quickly
find out how to compile and run SML programs in this setup. We will
test whatever we put up in that environment. Likewise, when you submit
work, you must make sure that what you submit will work correctly
in that environment. We will need to run your code to assess it,
and if it fails this basic test, then we will not be able to look much
further. Note also that the starting code that we will give you
for the different assignments will be Unix/Linux based and will be
guaranteed to work only in the CSE Labs setup.
Required Work and Grading
70% of the grade in this course will be determined by programming
assignments. All but the first assignment will correspond to different
parts of a compiler. The first assignment will count for 5%. For the
remaining homeworks (65% of the grade), half the credit, i.e. 32.5% of the aggregate, will
be reserved for the work you turn in through the semester. The other
half, i.e. the remaining 32.5%, will be reserved for an overall
assessment based on the final version of the compiler that you turn
in. The expectation is that this will be a complete compiler for
the Tiger language that is described in the appendix of the
book. This final program/project is due by 11:59 p.m. on May 1,
2023.
Policies and Related Information
Collaboration and Academic Honesty
Discussions related to the homework assignments and especially related
to the construction of the compiler are strongly encouraged. Right
before we start on this project, I will ask you to organize yourselves
into groups of three individuals to facilitate such
interactions. Piazza bulletin boards have also been set up for this
purpose; these will allow you to interact even across the groups you form
initially.
Appropriate Use of Class Notes and Course Materials
Material that is made available to the class during the term, such as
notes and videos prepared by the instructor and solutions that may be
provided to problems are meant only for the participants in the course
and for the purpose of enhancing learning. All these materials remain
the intellectual property of the instructor and must not be
distributed outside the class without his expressed permission. For
more information on this, check out the
Administrative
Policy on Student Responsibilities in Teaching and Learning,
paying special attention to item 6 therein.
Makeup Work for Legitimate Absences
Students will not be penalized for absence during the semester due to
unavoidable or legitimate circumstances. Such circumstances include
verified illness, participation in intercollegiate athletic events,
subpoenas, jury duty, military service, bereavement, and religious
observances. For information on what constitutes a legitimate absence
and the attendant policies, please check out the
Administrative Policy on Makeup Work for Legitimate Absences
.
Equity, Diversity, Equal Opportunity, and Affirmative Action
The University is committed to providing equal access and opportunity
to all in its programs and facilities, without regard to race, color,
creed, religion, national origin, gender, age, marital status,
disability, public assistance status, veteran status, sexual
orientation, gender identity, or gender expression. For more
information, please
consult Board of Regents Policy on Equity,
Diversity, Equal Opportunity, and Affirmative Action.
Disability Accommodations
The University of Minnesota views disability as an important aspect of
diversity, and is committed to providing equitable access to learning
opportunities for all students. The Disability Resource Center (DRC)
is the campus office that collaborates with students who have
disabilities to provide and/or arrange reasonable accommodations.
Additional information is available on the
DRC website.
Students may also email drc@umn.edu with questions.
Mental Health and Stress Management
As a student you may experience a range of issues that can cause
barriers to learning, such as strained relationships, increased
anxiety, alcohol/drug problems, feeling down, difficulty concentrating
and/or lack of motivation. These mental health concerns or stressful
events may lead to diminished academic performance or reduce your
ability to participate in daily activities. University of Minnesota
services are available to assist you with addressing these and other
concerns you may be experiencing. You can learn more about the broad
range of confidential mental health services available on campus from
the Student Mental Health
website.
Last modified: April 16, 2023 by ngopalan atsign umn dot edu.