CS 4120 - Introduction to Compilers

General Information

CS 4120 and CS 4121 - Practicum in Compilers are co-requisites and enrollment in one requires enrollment in the other. Total: 5 credits.

Prerequisites

• CS 2110 - Object-Oriented Programming and Data Structures
• CS 3410 - Computer System Organization and Programming or ECE 3140 / CS 3420 - Embedded Systems

Topics Covered

• Lexical Analysis (Tokenizing things)
• Recursive Descent Parsing
• Automated generation of LL(0) and LL(1) parsers (don’t worry, this is very intuitive)
• Automated generation of LR(0), LR(1), and LALR parsers (also intuitive)
• Typechecking
• Syntax-directed translations and how to translate your source language into a lower intermediate representation (IR) form
• Instruction selection (IR -> assembly) and dynamic programming
• Register Allocation
• Data/control flow Analysis and other optimization (this is the fun part, you get to learn what complete partial orders and maximal fixed points are)
• Memory management
• Object Oriented stuff (no one took this seriously)

Workload

Seven programming assignments, a few homeworks. 20 to 40+ hours a week towards the end of the semester (group dependent)

EDIT: In 2013 it was 6 programming assignments, 5 written homeworks, no exams, quizzes, etc. Actual commitment varies a lot. I probably spent ~30 hours a week on it although had people in my group that spent about 0 hours a week on it after the first month. Although Ross Tate says the course structure will be much different in 2015. Stay tuned.

General Advice

My advice is to go into the class with a group (3-4 students in years past). You’re going to be working together a lot and it’s important to find people that you trust you can work with and that will be committed. If you go in cold and get paired with someone you can’t work with, doing this class with a 1-2 person group is extremely tough. You can get away with this in other classes like 2110, 3110, 3410. For your own sake, you don’t want to do this in compilers.

The other thing is you should have some experience writing software in groups. If you don’t know some version control like git, you’ll have a very tough time, because you’ll have (if you do it right) 3-4 people all writing a significant amount of code. I would say on top of any prerequisite (other than like 2110 and knowing how to program) you should know git before going into this class because it is the first time you won’t be able to get away with like e-mailing your code to each other.

I also made the mistake of taking this before 3410 (in fact 3 of our 4 members had not taken it). You should really know how to program in C and like what a makefile is (I did not know these things) or else you’ll spend a lot of time figuring out stuff like that. ~Ashwin Murthy

Testimonials

WHY SHOULD YOU TAKE COMPILERS YOU ASK???

• it’ll make you good at c++
• it’ll make you good at programming
• you’ll still often have over 100 hours a week to do things that aren’t compilers
• you will learn how to write compilers you have to take 4121 if you take 4120

FAQ:

Q: Should I take Compilers?

A: Yes.

Q: default

A: You should take Compilers.” ~Gregor Stocks

If you want to truly understand how your program makes things happen in your computer, take this class. If you want to improve your programming skills, take this class. If you have an amazing group who will carry you through this class (and don’t mind a non-negligible amount of guilt afterwards), take this class. If you don’t meet the previous condition and want to have a lot of free time, don’t take this class.

• G

My honest review from 2013 fa:

tl;dr It had a nice blend of both interesting theory and hands-on implementation unlike any other cs class, or any class for that matter, that I’ve taken. That being said, way too much work.

The basic structure of the class is you have one semester long project where you write a compiler. You compile from Cubex (language specs given here if you’re curious) to C and the compiler is written in Java, although cubex will probably be replaced with a different language in later years. The course used to compile to assembly, but that is no longer true, so if you suck at assembly it’s not a problem. Each of the 6 projects is just a component of this project, so it’s very easy to fall behind. If you screw up the first one, or don’t finish all of it in time, you now have to finish it before moving onto the next project, otherwise you now have a ceiling on the possible points for the next project. For some perspective, our scores on each of the projects respectively were roughly 100, 70, 50, 30, 10, 80. So yea, we got our shit together by the end and fixed most of the things but most of the year was pretty stressful, especially after getting a 10 on PA 5.

That being said the whole theory of how everything worked was quite interesting especially at the end when we got a full working implementation. The course was set up to dive deep into the theory in class to supplement what you learned by actually writing the compiler. The problem was, most of the theory taught was not applicable to getting the project done, so many people just stopped going to class altogether (myself included) because we were just so busy trying to get that done (we occasionally met up during the allotted class time to get it done). This became a problem when the due date for the occasional written assignment came around and people scrambled to learn the material to do them.

All in all I thought there was a lot of interesting material, but just wish I was able to actually get more out of the class. Definitely was a valuable experience going through and writing the compiler from top to bottom, just feel it could have been done without a lot of the stress. I trust Ross will fix a lot of the problems from this semester. My thoughts on what I would have done differently are in the advice section. ~Ashwin Murthy

Past Offerings

Resources