Course Overview
Course Learning Objectives
This course examines the fundamental theory and practice of
implementing
today's programming languages.
Students should emerge with a good appreciation for the implementation
issues and strategies behind making programs in high level programming
languages work correctly
and efficiently on a target machine.
A major part of the course is
the practical experience of implementing various phases of a compiler for
a small object-oriented programming language.
Students learn translation
methodology that is useful in many other situations in addition to compilation, including
command interpreters, report-generating systems, programmable applications,
configuration file handling, preprocessors, debuggers, static program analysis tools, testing tools,
virtual machines, integrated development environments, and many other software engineering
tools.
Why Study Compilers?
Everything that computers do is the result of some program, and all of the millions of programs in the world are written in one of the many thousands of programming languages that have been developed over the last 60 years. Designing and implementing a programming language requires understanding of the particular programming constructs and the architecture on which the program will execute. The study of compiler construction touches upon programming languages, machine architecture, language theory, algorithms and software engineering. Learning something about compilers demonstrates the interplay of theory and practice in computer science, especially how powerful general ideas combined with engineering insight can lead to practical solutions to very hard problems. Knowing how a compiler works will also make you a better programmer and increase your ability to learn new programming languages quickly. Basic principles and techniques are needed to develop compilers which are applicable to many other domains that they are likely to be reused many times in the career of a computer scientist.
You should consider taking CISC 672/471 if you are curious about:
- the inner workings of a basic compiler
- the implementation of object-oriented programming language features
- building a large software system starting with a base library of useful utilities
- the answers to many of your questions about how programming languages work
- useful compiler technology for building tools for software engineering
AND you have the proper prerequisites. Note: There is no assumption of previous coursework in compilers.
Prerequisite: CISC 320: Algorithms and Advanced Programming or permission of instructor.
Additional Recommended Background:
We will utilize and briefly cover material
concerning regular languages, finite automata, and the definitions
related to context-free grammars.
Meeting Times: TTh 12:30-1:45 PM (3 hours) Gore 304.
Important announcements are usually made at the beginning of class.
Quizzes are also given at the beginning of class EVERY TUESDAY.
Instructor:
Lori Pollock, pollock cis udel edu
436 Smith Hall (831-1953)
Office Hours:
Wednesdays 2:30-3:30PM, Thursdays 10:00 - 11:00 AM and by appointment.
Teaching Assistant:
Rob Searles
rsearles udel edu
201 Smith Hall
TA Office Hours:
TBA, 201 Smith
Content
- Dealing with the form of programs:
- Specification of a language's lexical and syntactic components
- Scanning (lexical analysis) and automatic scanner generation (e.g., lex, flex, JLex)
- Parsing (syntax analysis) and automatic parser generation (e.g., yacc, bison, JavaCup)
- From form to meaning in a portable way:
- Intermediate code representations
- Semantic analysis, type checking and intermediate code generation
- Handling scope through symbol table creation and management
- Managing the runtime environment:
- Implementing program flow through the runtime stack
- Managing storage based on object lifetimes
- Specifics to implementing object-oriented languages
- Automatic garbage collection strategies
- Optimizing translated code:
- allocating registers to eliminate extra loads/stores
- code transformation strategies for code improvement
The Learning Process and Skills Development
Classtime will be devoted to discussions about programming language design choices and the
associated challenges and strategies for implementing the features. Students will be actively
involved in both individual and group projects to
gain experience with the state-of-the-art
tools for implementing programming languages. Each student will learn to automatically
generate scanners and parsers, build analyzers that traverse intermediate representations for
different program analysis and code instrumentation tasks, generate an alternate code representation, and
manage runtime storage.
Why am I teaching this course?
I'm teaching this course because I believe that programmers have more appreciation for the efficiency of their programs and tradeoffs in language choice when they understand compilation and its challenges, compiler technology has many practical uses beyond building a compiler, and facilitating the learning about compilers is fun.I have been leading research in compilers for a long time - over 20 years. My dissertation was in incremental compilation - the problem of reusing results from previous compilations of the same program in future compilations. We developed techniques to examine a programmer's edits and redo the compilation work to deal only with the edits, without redoing all of the compilation from scratch. In particular, my dissertation focused on the problem of how to perform incremental compilation when the compiler performs optimizing transformations to improve the program's performance. My research group here at UD has made contributions in optimizations of parallel programs to automatically overlap communication and computation, compiler techniques to integrate register allocation and instruction scheduling for better overall program performance, using dynamic compilers for solving software engineering problems, and developing compilation-based techniques for providing mobile code integrity. I also lead a group that applies compiler technology to developing tools for helping programmers during software testing and maintenance.
Course Requirements
Readings
Required Textbook
No textbook is required for the class. However, you may find a textbook useful as a reference or to learn more details of some of the ideas discussed in the course. There are a number of good textbooks on compilers; here are a few good references. The course calendar has associated readings for the Aho et.al. and Cooper and Torczon books.
Suggested References
- Torben Mogensen, The Basics of Compiler Design (free online).
- Alfred Aho, Monica Lam, Ravi Sethi, and Jeffrey D. Ullman, Compilers: Principles, Techniques, and Tools, 2/E, Addison-Wesley, 2007, or 1986 edition.
- John Levine, lex & yacc, O'Reilly and Associates, Inc., 1992.
- Engineering a Compiler, Keith D. Cooper, Linda Torczon, Morgan Kaufman Publishers, 2003, ISBN 1-55860-698-X.
- Programming Languages Pragmatics, Michael L. Scott, Morgan Kaufmann Publishers, 2005, ISBN 0126339511.
- Modern Compiler Implementation in Java (Tiger book), A.W. Appel, Cambridge University Press, 1998, ISBN 0-52158-388-8.
Assignments and Grading
Your grade will be based on your performance in the various activities in the course. Some of the activities will be done in groups, and some will be done individually. There will be two in-class examinations. The first exam (at midterm time) will concentrate on the first half of the course, while the second exam (during the last week of class) will concentrate on the second half of the course. The relative weights of the components of the grade will be approximately: The relative weights of the components of the grade will be approximately:- (5%) PA0: Github, Team and Other Setup
- (5%) PA1: MeggyJava Programming and AVR Warmup
- (5%) PA2: Lexer, Grammar, and Syntax-directed Translation
- (10%) PA3: AST Construction, Visitors, and Simple Code Generation
- (10%) PA4: Runtime Stack and Code Generation for Methods
- (10%) PA5: Implementing Classes, Variables, Arrays, and Assignments
- (5%) PA6: Register Allocation
- (5%) Weekly Quizzes
- (5%) Class participation and in-class activities, or (approved) department speaker seminars. All of these efforts count toward the class participation grade.
- (5%) Homeworks
- (17%) First Exam - first half of course
- (18%) Second Exam - second half of course
Supportive Readings:
The assigned readings will be posted on the web as the course progresses. The material presented in class will correspond roughly, but not exactly, to the material covered in the readings.Project Materials:
The course web site has links to all needed project handouts (gmake, flex, bison, spim, ...). The project files will be made available on sakai as the course progresses.Programming Environment and Computer Usage:
You will be writing a compiler for a subset of Java called MeggyJava. We compile MeggyJava to the assembly language for the ATmega328p microcontroller in the Meggy Jr RGB devices. You will write your compiler in Java as 6 separate programming assignments. You will use the JLex and JavaCup tools for generating the lexer and parser. Some projects are done individually. Other projects are typically done in teams of 2, but you are welcome to tackle them individually if desired. The assignment sheet will specify. All homeworks are to be done individually.
Many of the programming assignments can use a Meggy Jr device to run programs; however, you do NOT have to get a Meggy Jr device for this class. There is a simulator for Meggy AVR assembly for grading purposes. Students can check out an assembled Meggy Jr from the instructor. You are expected to turn the device back in at the end of the semester in good working condition for the next set of students to use. Otherwise, you will be charged for the device.
All programming assignments will be checked in through github. All homework assignments will be submitted through
sakai.
Each quiz will take about 5 minutes at the beginning of class. If you are late for class,
you may miss the quiz. It
will contain 1-2 short questions based on recent class discussions and
readings.
There will be a quiz EVERY TUESDAY, unless announced otherwise. The
quiz will focus on the previous week's classroom and reading topics.
Each student's lowest quiz grade will not be counted toward their
final grade.
Thus, there WILL BE NO MAKEUP quizzes. Any missed quizzes will be counted
as zeros in the grading scheme above. Thus, if you miss more than one
quiz, all additional missed quizzes and all other quiz grades will be
counted toward your final grade.
My philosophy on late assignments is:
(1) Everyone should try their best to complete all assignments by the
specified due date. (2) People who work conscientiously to make the deadlines should
be rewarded for their promptness and sacrifice of sleep. Thus, allowing others to hand
in late assignments without some penalty is not fair to these people. However, there
are various circumstances that may prevent you from completing an assignment by
the due date. Allowing no late assignments would not give you much incentive to
continue to work on the assignment, which is a major source of learning in this course.
Thus, I believe late assignments are better than no assignment.
Unless otherwise stated, late assignments will be penalized 5% off the total possible points if turned
in within the first 24-hour period after the specified due date and time,
and 5% per 24-hour period (or fraction of a day) (including weekends)
after that time, up to a week after the due date.
Late assignments will be accepted with penalty up to one week after
the due date. Assignments submitted at any later time without
an approved excuse will not be accepted.
It is up to you to determine the version of your assignment
to be graded. You must weigh the
late penalty against the completeness of your assignment.
If you are dissatisfied with a grade on a homework, programming assignment,
or exam,
you should consult the instructor directly within a week of the day the
graded assignment was returned to you. No regrade requests will be considered
after this week period.
You will be told specifically which assignments are to be done collaboratively
in groups, and which ones should be done individually without collaboration.
For individual assignments, you should be directing your questions to
the instructor, not to other students, unless the question is a clarification
question.
Any evidence of collaboration other than this kind
will be handled as stated in the Official Student Handbook of the University of Delaware.
You should not be using or examining any program code used for projects for
this course in any prior instantiations of this course.
If you are in doubt regarding the requirements,
please consult with me before you complete any requirement of this course.
This course requires a significant amount of programming. Each assignment specification
will clearly specify whether you work in groups or individually.
For the purposes of the collaboration policy, students
choosing to work with a partner are effectively considered as one entity, and
are freely allowed to exchange, help, design, and code with one other, but the
guidelines below apply outside the partnership (neither of you should be
debugging, sharing code, etc. with other people or teams). There are also some
specific rules that apply within the partnership.
Two students engaging in a more detailed discussion of the project specifics
can cross into the area of collaboration that is acceptable only if documented.
I require that you include the name of those whom you received specific
assistance from and properly credit their contribution, as you would cite a
reference in a research paper. Some examples: Above all you should use your common sense. If you suspect
that what you are about to do is a violation, play it safe and ask a staff
member first rather than take risks with your academic career. Cheating is taken very seriously in this course.
Please do your part in maintaining a community where academic work is
done with a high standard of integrity! Some parts of this document are based on a similar
collaboration policy for CS courses at Brown, Drexel, and Stanford.
Weekly Quizzes
The goals of the weekly quizzes are as follows:
How to Increase your Learning in CISC 672/471
Course Policies
The due dates are to be taken seriously and you should not expect
them to be extended. The pace of work is implicit in the due
dates and necessary if you expect to finish by the end of the semester.
Homeworks to be graded should be turned in at the start of class on the specified due date.
Programming assignments should be dated before 11:59 PM on the due date.
NO late programs or homeworks will be accepted FOR FULL CREDIT without
discussion with me prior to the due date. If you can not reach me, leave a message on my voicemail.
All other assignments not delivered
by the due date are considered late.
Regrading Policy:
Policy on Academic Dishonesty
Collaboration Policy:
General philosophy
Things that are always allowed
These things are encouraged and allowed
at all times for all students.
Collaboration that is allowed if documented
Collaboration that is NOT allowed
Basically, the rule is that you should
be handing in code which represents your original, independent work. It should
not be based on, influenced by, or copied from anyone else's.
Resource Usage Policy:
Under no circumstances should you be copying code from a compiler
project written by others
found on the internet or provided by others in other ways.
There is no learning taking place in such actions.
Closing thoughts