[UMN logo]

CSCI 5161: Introduction to Compilers
Spring 2023, University of Minnesota


Exam Dates and Time

Midterm Exam: In class on March 15, 2023.

Final Compiler Project Due: May 1, 2022, 11:59 p.m.

There will be no final exam in this course.


News Flash: Online discussion using Piazza

Table of Contents


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


Contact Information


Course Texts

The text for this course is
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 Press
to 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.


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.

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.


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.

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.


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.

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.


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.

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.

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.

Sexual Harrassment

Sexual harassment means unwelcome sexual advances, requests for sexual favors, and/or other verbal or physical conduct of a sexual nature. Such conduct has the effect of unreasonably interfering with an individual's work or academic performance or creating an intimidating, hostile, or offensive working or academic environment in any University activity or program. Such behavior is not acceptable in the University setting. For additional information, please consult the Board of Regents Policy on this matter.

Academic Freedom

Academic freedom is a principle that is fundamental to intellectual inquiry. This notion includes the freedom to discuss relevant matters in the classroom, within the scope of the course as defined by the instructor. Students are encouraged to develop the capacity for critical judgment and to engage in a sustained and independent search for truth. Students are free to take reasoned exception to the views offered in any course of study and to reserve judgment about matters of opinion, even while they are responsible for learning the content of any course of study for which they are enrolled.


Manuals and Online Resources

Here are some links to software and manuals we will use in the course. More will be added as needed.


Last modified: April 16, 2023 by ngopalan atsign umn dot edu.


The views and opinions expressed in this page are strictly those of the page author(s). The contents of this page have not been reviewed or approved by the University of Minnesota.